to do
2] Search Insert Position
int searchR (vector<int>& nums, int l, int r, int target) {
if (l==r-1 || l==r) {
if (target <= nums[l]) return l;
else if (nums[r] == target || (nums[l] < target && target <nums[r])) return r;
else if (nums[r] < target) return r+1;
}
int mid = (l+r)/2;
if (nums[mid]<target) return searchR(nums, mid, r, target);
else if (target<nums[mid]) return searchR(nums, l, mid, target);
else return mid;
}
int searchInsert(vector<int>& nums, int target) {
if (nums.empty()) return 0;
return searchR(nums, 0, nums.size()-1, target);
}
3] Search a 2D Matrix
ncols, nrows自己都记反了，多练养成自己的惯例
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.empty() || matrix[0].empty()) return false;
int nrows = matrix.size(), ncols = matrix[0].size();
int l=0, r=ncols * nrows-1;
while (l<r) {
int mid = (l+r)/2;
int curr = matrix[mid/ncols][mid%ncols];
if (curr<target) l = mid+1;
else if (curr>target) r = mid-1;
else return true;
}
return l==r? matrix[l/ncols][l%ncols]==target : false;
}
4] Subsets
- recursion
好吧其实要求有序的话，sort input once
vector<vector<int>> subsets(vector<int>& nums) {
if (nums.empty()) return vector<vector<int>> {{}};
int curr = nums.back();
nums.pop_back();
vector<vector<int>> lastSets = subsets(nums);
int size = lastSets.size();
for (int i=0; i<size; ++i) {
vector<int> newSet = lastSets[i];
newSet.push_back(curr);
lastSets.push_back(newSet);
}
return lastSets;
}
- iteration
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> ret{{}};
if (nums.empty()) return ret;
// each iteration add all vectors of length i+1, ending w/ nums[i]
for (int i=0; i<nums.size(); ++i) {
// iterate through inserted vectors of length i
int insertedSize = ret.size();
for (int j=0; j<insertedSize; ++j) {
vector<int> newv = ret[j];
newv.push_back(nums[i]);
ret.push_back(newv);
}
}
return ret;
}
还有二进制法，以后来看
