leetcode-热题100(3)

leetcode-74-搜索二维矩阵

矩阵最后一列升序排序，在最后一列中查找第一个大于等于target的元素

然后在该元素所在行进行二分查找

bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target) {int n = matrixSize;int m = matrixColSize[0];int i;for(i = 0 ; i < n ; i++){if(target <= matrix[i][m-1]){int l = 0, r = m-1;while(l <= r){int mid = (r+l)/2;if(target > matrix[i][mid])l = mid+1;else if(target < matrix[i][mid])r = mid-1;else return true;}return false;}}return false;
}

leetcode-33-搜索旋转排序数组

题意为：在一个旋转过的数组中查找目标值target，若存在返回其下标，否则返回-1

将数组一分为二，其中一定有一个是有序的，另一个可能是有序，也能是部分有序。 此时有序部分用二分法查找。无序部分再一分为二，其中一个一定有序，另一个可能有序，可能无序。就这样循环.

int search(int* nums, int numsSize, int target) {int n = numsSize;if(n == 0)return -1;if(n ==1)return nums[0] == target ? 0 : -1;int l = 0, r = n-1;while(l <= r){int mid = (l+r)/2;if(nums[mid] == target)return mid;if(nums[0] <= nums[mid]){if(nums[0] <= target&& target <= nums[mid]){r = mid-1;}else{l = mid +1;}}else{if(nums[mid] < target && target <= nums[n-1]){l =mid+1;}else{r = mid-1;}}}return -1;
}

leetcode-153-寻找旋转排序数组中的最小值

如果nums[mid] > nums[right] ，那么最小值一定在(mid,right)中

如果nums[mid] <= nums[right] ，那么最小值一定在(left,mid)中

边界：left == right 此时最小值就是nums[left]

int findMin(int* nums, int numsSize) {if(numsSize == 1)return nums[0];int n = numsSize;int l = 0, r = n-1;int res = nums[0];while(l <= r){int mid = (l+r)/2;res = fmin(res,nums[mid]);if(nums[mid] > nums[r])l = mid+1;elser = mid-1;}return res;
}

leetcode-4-寻找两个正序数组的中位数

leetcode-155-最小栈

leetcode--394-字符串解码

leetcode-739-每日温度

leetcode-84-柱状图中最大矩形

leetcode-215-数组中的第K大元素

leetcode-121-买卖股票的最佳时机