/*o(n)的堆化方法*/
void myjust(vector<int>& A,int i)
{
int l=i*2+1;
int r=i*2+2;
int minn=i;
if(l<A.size()&&A[l]<A[minn])
minn=l;
if(r<A.size()&&A[r]<A[minn])
minn=r;
if(minn!=i)
{
swap(A[minn],A[i]);
myjust(A,minn);
}
}
void heapify(vector<int> &A) {
int lens=A.size();
if(lens==0) return;
for(int i=lens/2;i>=0;i--)
{
myjust(A,i);
}
}
求sqrt(double x)
键树 class Trie { public: struct TrieNode { bool isEnd; map<char, TrieNode*> myMap; TrieNode() { isEnd = false; } }; TrieNode* root; /** Initialize your data structure here. */ Trie() { root = new TrieNode(); } /** Inserts a word into the trie. */ void insert(string word) { TrieNode* current = root; for (int i = 0; i < word.length(); i++) { if (current->myMap.find(word[i]) != current->myMap.end()) { current = current->myMap[word[i]]; if (i == word.length() - 1) current->isEnd = true; } else { TrieNode* tmp = new TrieNode(); tmp->isEnd = (i == word.length() - 1 ? true : false); current->myMap[word[i]] = tmp; current = tmp; } } } /** Returns if the word is in the trie. */ bool search(string word) { TrieNode* current = root; for (int i = 0; i < word.length(); i++) { if (current->myMap.find(word[i]) != current->myMap.end()) { current = current->myMap[word[i]]; } else { return false; } } return current->isEnd == true ? true : false; } /** Returns if there is any word in the trie that starts with the given prefix. */ bool startsWith(string prefix) { TrieNode* current = root; for (int i = 0; i < prefix.length(); i++) { if (current->myMap.find(prefix[i]) != current->myMap.end()) { current = current->myMap[prefix[i]]; } else { return false; } } return true; } };
//寻找前k大小的数
int getIdx(vector<int>& nums,int left,int right) { int tmp=nums[left]; while(left<right) { while (left<right&&nums[right]>=tmp) right--; nums[left]=nums[right]; while (left<right&&nums[left]<tmp) left++; nums[right]=nums[left]; } nums[left]=tmp; return left; } vector<int> GetLeastNumbers_Solution(vector<int> input, int k) { vector<int> ans; if(input.size()<k||k<=0||input.size()==0) { return ans; } int idx=-1; int left=0,right=input.size()-1; while (idx!=k-1) { idx=getIdx(input,left,right); if(idx>k-1) { right=idx-1; } else { left=idx+1; } } for(int i=0;i<k;i++) { ans.push_back(input[i]); } return ans; }