阅读量:4
74. 搜索二维矩阵
class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { int row = matrix.size(); int col = matrix[0].size(); for(int i=0;i<row;i++) { //先排除一下不存在的情况 if(i>0&&matrix[i][0]>target && matrix[i-1][col-1]<target) return false; //锁定某一行之后使用二分查找 if(matrix[i][0] <=target && matrix[i][col-1]>=target) { int begin=0,end=col-1; while(begin<=end) { int mid = begin + (end-begin)/2; if(matrix[i][mid] > target) { end = mid-1; } else if(matrix[i][mid] < target) { begin = mid+1; } if(matrix[i][mid]==target) return true; } } } return false; } }; 33. 搜索旋转排序数组
二分法，稍微区分了一下左侧有序还是右侧有序
class Solution { public: int search(vector<int>& nums, int target) { if(nums.size()==0) return -1; if(nums.size()==1) return nums[0]==target?0:-1; int left = 0, right = nums.size()-1; while(left<=right) { int mid = left+(right-left)/2; if(nums[mid]==target) return mid; else if(nums[0] <= nums[mid]) { if(nums[0] <=target && target < nums[mid]) right = mid-1; else left = mid+1; } else { if(nums[mid] <target && target <= nums[nums.size()-1]) left = mid+1; else right = mid-1; } } return -1; } }; 153. 寻找旋转排序数组中的最小值
class Solution { public: int findMin(vector<int>& nums) { if(nums.size()==1) return nums[0]; int n = nums.size()-1; int left = -1,right = n; int res = nums[0]; if(nums[0] < nums[n]) return res; while(left+1<right) { int mid = left+(right-left)/2; if(nums[mid] < nums.back()) right = mid; else left = mid; } return nums[right]; } }; 98. 验证二叉搜索树
通过中序遍历，得到有序的数组，在判断数组是否严格递增
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: void traversal(TreeNode* root,vector<int>& res) { if(root==NULL) return; if(root->left) traversal(root->left,res); res.push_back(root->val); if(root->right) traversal(root->right,res); } bool isValidBST(TreeNode* root) { if(!root) return true; vector<int> res; traversal(root,res); for(int i=1;i<res.size();i++) { if(res[i] <= res[i-1]) return false; } return true; } }; 118. 杨辉三角
res即dp数组，寻找res[i][j]的更新规律
class Solution { public: vector<vector<int>> generate(int numRows) { vector<vector<int>> res(numRows); for(int i=0;i<numRows;i++) { res[i].resize(i+1); res[i][0] = res[i][i] = 1; for(int j=1;j<i;j++) { res[i][j] = res[i-1][j]+res[i-1][j-1]; } } return res; } }; 