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

二分查找栈堆

news 2025/7/16 16:10:03

35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

二分法；

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while(left <= right) {int mid = left + (right - left) / 2;if(nums[mid] > target) {right = mid - 1;}else if(nums[mid] < target){left = mid + 1;}else return mid;}return left;}
};

74. 搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵：
每行中的整数从左到右按非严格递增顺序排列。
每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

排除法；

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int row = matrix.size(), col = matrix[0].size();int r = 0, c = col - 1;while (r < row && c >= 0) {if(matrix[r][c] == target) return true;else if(matrix[r][c] < target){r++;}else c--;} return false;}
};

33. 搜索旋转排序数组

可以在常规二分查找的时候查看当前 mid 为分割位置分割出来的两个部分 [l, mid] 和 [mid + 1, r] 哪个部分是有序的，并根据有序的那个部分确定我们该如何改变二分查找的上下界，因为我们能够根据有序的那部分判断出 target 在不在这个部分：

如果 [l, mid - 1] 是有序数组，且 target 的大小满足 [nums[l],nums[mid])，则我们应该将搜索范围缩小至 [l, mid - 1]，否则在 [mid + 1, r] 中寻找。
如果 [mid, r] 是有序数组，且 target 的大小满足 (nums[mid+1],nums[r]]，则我们应该将搜索范围缩小至 [mid + 1, r]，否则在 [l, mid - 1] 中寻找。

class Solution {
public:int search(vector<int>& nums, int target) {int l = 0, r = nums.size() - 1;while(l <= r) {int mid = l + (r - l)/2;if(nums[mid] == target) return mid;if(nums[l] <= nums[mid]) {if(nums[l] <= target && nums[mid] > target){r = mid - 1;}else{l = mid + 1;}}else{if(nums[r] >= target && target > nums[mid]) {l = mid + 1;}else{r = mid - 1;}}}return -1;}
};

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

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。请你找出并返回数组中的最小元素。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findMin(vector<int>& nums) {int left = 0, right = nums.size() - 1;while(left <= right) {int mid = left + (right - left) / 2;if(nums[mid] > nums[right]) {left = mid + 1;}else {right = mid - 1;}}return nums[left];}
int main() {int n;cin >> n;vector<int> nums(n);for(int i = 0; i < n; i++) {cin >> nums[i];}cout << findMin(nums) << endl;return 0;
}
};

20 有效的括号

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。

class Solution {
public:bool isValid(string s) {if(s.size() % 2 != 0) return false;stack<char> st;for(int i = 0; i < s.size(); i++) {if(s[i] == '(') st.push(')');else if(s[i] == '{') st.push('}');else if(s[i] == '[') st.push(']');else if(st.empty() || s[i] != st.top()) return false;else {st.pop();}}return st.empty();}
};

155 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

维护前缀最小值思想

class MinStack {
public:stack <pair<int,int>> st;MinStack() {st.emplace(0, INT_MAX);}void push(int val) {st.emplace(val, min(getMin(), val));}void pop() {st.pop();}int top() {return st.top().first;}int getMin() {return st.top().second;}
};/*** Your MinStack object will be instantiated and called as such:* MinStack* obj = new MinStack();* obj->push(val);* obj->pop();* int param_3 = obj->top();* int param_4 = obj->getMin();*/