526互联

20天 hot 100 速通计划-day14

发布时间 2023-08-22 20:09:29作者: Ba11ooner

二分查找

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] <= 104
  • nums 中的每个值都 独一无二
  • 题目数据保证 nums 在预先未知的某个下标上进行了旋转
  • -104 <= target <= 104

因为旋转位数 k 是不定的，而 mid 必定在中间位置

  1. 当左侧有序时，nums[left] 是左侧有序部分的最小值，nums[mid] 是左侧有序部分的最大值。如果从左侧有序部分的最小值 nums[left] 开始向右查找，一直到左侧有序部分的最大值 nums[mid]，都不会大于 nums[left]，因此取小于等于符号。
  2. 当右侧有序时，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.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • nums 中的所有整数 互不相同
  • 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 == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= 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. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

提示：

  • 1 <= s.length <= 104
  • s 仅由括号 '()[]{}' 组成
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 - 1
  • pop、top 和 getMin 操作总是在 非空栈 上调用
  • push, pop, top, and getMin最多被调用 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(); // 返回辅助栈的栈顶元素，即当前栈的最小值
    }
};