当前位置：首页 > news >正文

LeetCode热题100刷题16：74. 搜索二维矩阵、33. 搜索旋转排序数组、153. 寻找旋转排序数组中的最小值、98. 验证二叉搜索树

news 来源：原创 2024/9/21 22:42:19

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;elseleft = 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;}
};