面试题 10.02. 变位词组
class Solution { public: vector<vector<string>> groupAnagrams(vector<string>& strs) { int len=strs.size(); map<string,vector<string>>m; for(int i=0;i<len;i++) { int l=strs[i].size(); string tmp=strs[i]; sort(tmp.begin(),tmp.end()); m[tmp].push_back(strs[i]); } vector<vector<string>>res; for(auto k=m.begin();k!=m.end();k++) { res.push_back(k->second); } return res; } };面试题 10.03. 搜索旋转数组
class Solution { public: int search(vector<int>& arr, int target) { if(arr.empty()) return -1; int left = 0, right = arr.size()-1; while(left <= right){ int mid = (left+right) >> 1; //左边有序 if(arr[left] < arr[mid]){ //目标值在左边 if(arr[left] <= target && target <= arr[mid]) right = mid; else left = mid+1; } //右边有序 else if(arr[left] > arr[mid]){ //目标值在右边 if(arr[mid] <= target && target <= arr[right] && arr[left] > arr[right]) left = mid; else right = mid-1; } //如果左值等于中值，可能是已经找到了目标，也可能是遇到了重复值 else if(arr[left] == arr[mid]){ //如果左值不等于目标，说明还没找到，需要逐一清理重复值。 if(arr[left] != target) left++; else return left; } } return -1; } };面试题 10.05. 稀疏数组搜索
class Solution { public: int findString(vector<string>& words, string s) { int left=0,right=words.size()-1; while(left<=right) { int mid=(left+right)/2; int tmp=mid; while(mid>=left&&words[mid]=="") { mid-=1; } if(words[mid]==s) { return mid; } else if(words[mid]>s) { right=mid-1; } else left=tmp+1; } return -1; } };面试题 10.09. 排序矩阵查找
class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { if(matrix.empty()||matrix[0].empty()) return false; int m=matrix.size(),n=matrix[0].size(); int i=0,j=n-1; while(i<m&&j>=0) { if(matrix[i][j]==target) return true; else if(matrix[i][j]>target) { j--; } else if(matrix[i][j]<target) { i++; } } return false; } };面试题 10.10. 数字流的秩
class StreamRank { public: map<int,int>tmp; StreamRank() { } void track(int x) { tmp[x]++; } int getRankOfNumber(int x) { int res=0; for(auto it=tmp.begin();it!=tmp.end();it++) { if(it->first<=x) res+=it->second; } return res; } };