二分查找
33. 搜索旋转排序数组
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：
输入：nums = [1], target = 0
输出：-1
提示：
1 <= nums.length <= 5000-104 <= nums[i] <= 104nums中的每个值都 独一无二- 题目数据保证
nums在预先未知的某个下标上进行了旋转 -104 <= target <= 104
因为旋转位数 k 是不定的，而 mid 必定在中间位置
- 当左侧有序时，nums[left] 是左侧有序部分的最小值，nums[mid] 是左侧有序部分的最大值。如果从左侧有序部分的最小值 nums[left] 开始向右查找，一直到左侧有序部分的最大值 nums[mid]，都不会大于 nums[left]，因此取小于等于符号。
- 当右侧有序时，nums[mid] 是右侧有序部分的最小值，nums[right] 是右侧有序部分的最大值。如果从右侧有序部分的最小值 nums[mid] 开始向左查找，一直到右侧有序部分的最大值 nums[right]，都不会小于 nums[mid]，因此取小于符号。
设旋转前数组：[1,2,3,4,5,6], n = 6, left = 0, right = 6 - 1 = 5, mid = 6 / 2 = 3
- k < n / 2 → [5,6,1,2,3,4] → nums[left] = 5 > nums[mid] = 2 mid 右侧升序
- k = n / 2 → [4,5,6,1,2,3] → nums[left] = 4 > nums[mid] = 1 mid 左侧升序
- k > n / 2 → [3,4,5,6,1,2] → nums[left] = 3 < nums[mid] = 6 mid 左侧升序
设旋转前数组：[1,2,3,4,5], n = 5, left = 0, right = 5 - 1 = 4, mid = 5 / 2 = 2
- k < n / 2 → [5,1,2,3,4] → nums[left] = 5 > nums[mid] = 2 mid 右侧升序
- k = n / 2 → [4,5,1,2,3] → nums[left] = 5 > nums[mid] = 1 mid 右侧升序
- k > n / 2 → [3,4,5,1,2] → nums[left] = 3 < nums[mid] = 5 mid 左侧升序
设旋转前数组：[1, 2], n = 2, left = 0, right = 1, mid = 2 / 2 = 1
- k < n / 2 → [1,2] → nums[left] = 1 < nums[mid] = 2 mid 左侧升序
- k = n / 2 → [2,1] → nums[left] = 2 > nums[mid] = 1 mid 右侧升序
- k > n / 2 → [1,2] → nums[left] = 1 < nums[mid] = 2 mid 左侧升序
设旋转前数组：[1], n = 1, left = 0, right = 0, mid = 1 / 2 = 0
- [1], nums[left] = nums[mid] mid 左侧升序 / mid 右侧升序
总结：
- 若 nums[left] <= nums[mid]，则 mid 左边有序
- 若 nums[left] > nums[mid]，则 mid 右边有序
class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size(); // 数组长度
if (n == 0) return -1; // 特殊情况，数组为空，直接返回-1
// 二分法固定结构，首尾双指针，左闭右闭
int left = 0, right = n - 1;
while (left <= right) { // 当左指针小于等于右指针时，执行循环
int mid = left + (right - left) / 2; // 计算中间指针的位置
if (nums[mid] == target) { // 如果中间的数等于目标值，直接返回结果
return mid;
}
// 判断 mid 左边是否有序
if (nums[left] <= nums[mid]) {
// 判断 target 是否在有序的一侧
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1; // 在有序一侧（左边），调整右指针
} else {
left = mid + 1; // 在无序一侧，调整左指针
}
} else {
// 判断 target 是否在有序的一侧
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1; // 在有序一侧（右边），调整左指针
} else {
right = mid - 1; // 在无序一侧，调整右指针
}
}
}
return -1; // 循环结束后仍然没有找到目标值，返回-1
}
};
153. 寻找旋转排序数组中的最小值
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
- 若旋转
4次，则可以得到[4,5,6,7,0,1,2] - 若旋转
7次，则可以得到[0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
示例 2：
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。
示例 3：
输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
提示：
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000nums中的所有整数 互不相同nums原来是一个升序排序的数组，并进行了1至n次旋转
class Solution {
public:
int findMin(vector<int>& nums) {
int left = 0; // 左边界
int right = nums.size() - 1; // 右边界
while (left < right) {
int mid = left + (right - left) / 2; // 中间元素的索引
if (nums[mid] < nums[right]) { // 中间元素比右边界元素小，说明最小值在左半边
right = mid;
}
else { // 中间元素比右边界元素大，说明最小值在右半边
left = mid + 1;
}
}
return nums[left];
}
};
4. 寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
提示：
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-106 <= nums1[i], nums2[i] <= 106
有点像归并排序 + 二分查找的混合物
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(); // 数组nums1的长度
int n = nums2.size(); // 数组nums2的长度
int total = m + n; // 合并后数组的长度
vector<int> merged(total); // 合并后的有序数组
int p1 = 0, p2 = 0; // 用于标记当前指针的位置
int p = 0; // 合并后数组的指针
while (p1 < m && p2 < n) { // 当两个数组都没有遍历完时
if (nums1[p1] <= nums2[p2]) { // 如果nums1当前位置的元素小于等于nums2当前位置的元素
merged[p++] = nums1[p1++]; // 将nums1当前位置的元素放入合并后的数组中，并将指针向后移动一位
} else { // 如果nums1当前位置的元素大于nums2当前位置的元素
merged[p++] = nums2[p2++]; // 将nums2当前位置的元素放入合并后的数组中，并将指针向后移动一位
}
}
while (p1 < m) { // 如果nums1还有未遍历的元素
merged[p++] = nums1[p1++]; // 将nums1剩余的元素放入合并后的数组中，并将指针向后移动一位
}
while (p2 < n) { // 如果nums2还有未遍历的元素
merged[p++] = nums2[p2++]; // 将nums2剩余的元素放入合并后的数组中，并将指针向后移动一位
}
if (total % 2 != 0) { // 如果合并后数组的长度为奇数
return merged[total / 2]; // 返回合并后数组中间位置的元素
} else { // 如果合并后数组的长度为偶数
return (merged[total / 2] + merged[total / 2 - 1]) * 0.5; // 返回合并后数组中间两个元素的平均值
}
}
};
栈
20. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
提示：
1 <= s.length <= 104s仅由括号'()[]{}'组成
class Node {
public:
int data;
Node* next;
Node(int val) {
data = val;
next = nullptr;
}
};
class Stack {
private:
Node* topNode;
public:
Stack() {
topNode = nullptr;
}
bool isEmpty() {
return topNode == nullptr;
}
void push(int val) {
Node* newNode = new Node(val);
if (isEmpty()) {
topNode = newNode;
}
else {
// topNode
// ↓
// 3 → 2 → 1
// topNode
// ↓
//newNode → 3 → 2 → 1
//topNode
// ↓
//newNode → 3 → 2 → 1
newNode->next = topNode;
topNode = newNode;
}
}
int pop() {
if (isEmpty()) {
cout << "Error:stack is empty!" << endl;
return -1;
}
else {
int val = topNode->data;
Node* tmp = topNode;
topNode = topNode->next;
delete tmp;
return val;
}
}
};
class Solution {
public:
bool isValid(string s) {
Stack stack;
for (char c : s) {
//遇见左括号，左括号入栈
if (c == '(' || c == '[' || c == '{') {
cout << c << " ";
stack.push(c);//左括号入栈
}
//遇见右括号，已入栈的左括号出栈
else if (c == ')' || c == ']' || c == '}') {
cout << c << " ";
//只有右括号，没有左括号 → 不匹配
if (stack.isEmpty()) {
return false;
}
char top = stack.pop();//左括号出栈
//判断是否匹配
if ((c == ')' && top != '(')
|| (c == ']' && top != '[')
|| (c == '}' && top != '{')) {
return false;
}
}
else {
cout << "Error: invalid char";
return false;
}
}
//栈为空，所有括号都匹配
return stack.isEmpty();
}
};
155. 最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack()初始化堆栈对象。void push(int val)将元素val推入堆栈。void pop()删除堆栈顶部的元素。int top()获取堆栈顶部的元素。int getMin()获取堆栈中的最小元素。
示例 1:
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
提示：
-231 <= val <= 231 - 1pop、top和getMin操作总是在 非空栈 上调用push,pop,top, andgetMin最多被调用3 * 104次
纯技巧题
class MinStack {
stack<int> s; // 声明一个普通的栈，用于存储所有的元素
stack<int> minStack; // 声明一个辅助栈，用于存储当前栈的最小值
public:
/** initialize your data structure here. */
MinStack() {
}
void push(int x) {
s.push(x); // 将元素x压入普通栈中
if (minStack.empty() || x <= minStack.top()) { // 如果辅助栈为空或者x小于等于辅助栈的栈顶，则将x压入辅助栈
minStack.push(x);
}
}
void pop() {
if (s.top() == minStack.top()) { // 如果普通栈的栈顶元素等于辅助栈的栈顶元素，则将辅助栈的栈顶元素弹出
minStack.pop();
}
s.pop(); // 弹出普通栈的栈顶元素
}
int top() {
return s.top(); // 返回普通栈的栈顶元素
}
int getMin() {
return minStack.top(); // 返回辅助栈的栈顶元素，即当前栈的最小值
}
};