0602练习题目

06.02第 013 ~ 025 题（第 05 ~ 08 天）

搜索旋转排序数组

分析

把数组看成左右两部分，左边部分一定比右半部分值大。

• 如果nums[mid] == target，直接返回下标。
• 如果nums[mid] >= nums[left]，说明mid在左半部分，此时：
  • nums[mid] > target && target >= nums[left]，target在mid左侧，移动right = mid - 1。
  • nums[mid] < target，则target在mid右侧，left = mid + 1。
  • target < nums[left]，target在右半部分，left = mid + 1。
• 如果nums[mid] < nums[left]，说明mid在右半部分，此时：
  • nums[mid] < target && taret < nums[right]，则target在mid右侧，left = mid + 1。
  • nums[mid] > target，则target在右半部分，且在mid左侧，right = mid - 1。
  • target > nums[right]，target在左半部分，right = mid-1。

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

• 时间复杂度：O(logn)
• 空间复杂度：O(1)

寻找峰值

分析

使用两个指针left和right分别指向数组的第一个元素和最后一个元素。取中间值mid，如果nums[mid] < nums[mid + 1]，则峰值在右侧，left = mid + 1；否则峰值在左侧，right = mid。当left == right时跳出循环，返回结果。

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

• 时间复杂度：O(logn)
• 空间复杂度：O(1)

寻找两个正序数组中的中位数

分析

中位数把数组分割成了左右两部分，并且左右两部分元素个数相等。如果两个数组元素个数为偶数，单侧元素个数为$(n1+n2) / 2$个；否则是$(n1+n2)/2 + 1$个，可以总结为单侧元素个数： $\lfloor \frac{(n1 + n2 + 1)}{2} \rfloor$ 。现在的问题就变为了：如何在两个有序数组中找到前 k 小的元素位置？

1. 让left指向nums1的首个元素，right指向最后一个元素，m1为中间元素。
2. 则m2 = k - m1，然后判断m1和m2位置上元素的关系：
   • nums1[m1] < nums2[m2]，说明最多有m1 + m2 - 1 = k - 1个元素比nums[m1]小，所以左侧的m1个元素都不可能是第k个元素，因此可以将left右移，即left = m1 + 1。
   • 否则，说明m1取值过大，right = m1。
3. 当left == right，循环结束，找到正确的m1和m2.
4. 分奇偶情况讨论。

• 如果m1 <= 0，说明整个nums1都比nums2大，那第k个元素一定在m2中；反之亦然。
• 如果m1 >= n1，则说明整个nums1都小于第k个元素，即第k个元素在m2中；反之亦然。

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        // 设nums1为较短的数组
        int n1 = nums1.size();
        int n2 = nums2.size();
        if (n1 > n2) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int k = (n1 + n2 + 1) / 2;
        int left = 0;
        int right = n1;
        
        while (left <= right) {  // 修改终止条件
            int m1 = (left + right) / 2;
            int m2 = k - m1;

            // 检查 m1 和 m2 的边界，确保不会越界
            if (m1 < n1 && m2 > 0 && nums1[m1] < nums2[m2 - 1]) {
                left = m1 + 1;
            } else if (m1 > 0 && m2 < n2 && nums1[m1 - 1] > nums2[m2]) {
                right = m1 - 1;
            } else {
                // 满足条件，划分完成
                int c1;
                if (m1 == 0) {
                    c1 = nums2[m2 - 1];  // nums1 全部被划分到右侧
                } else if (m2 == 0) {
                    c1 = nums1[m1 - 1];  // nums2 全部被划分到右侧
                } else {
                    c1 = max(nums1[m1 - 1], nums2[m2 - 1]);  // 左侧最大值
                }

                // 如果总数为奇数，直接返回
                if ((n1 + n2) % 2 == 1) {
                    return c1;
                }

                // 否则，计算右半部分的最小值
                int c2;
                if (m1 == n1) {
                    c2 = nums2[m2];  // nums1 全部被划分到左侧
                } else if (m2 == n2) {
                    c2 = nums1[m1];  // nums2 全部被划分到左侧
                } else {
                    c2 = min(nums1[m1], nums2[m2]);  // 右侧最小值
                }

                // 返回中位数
                return (c1 + c2) / 2.0;
            }
        }

        return 0.0;  // 理论上不会到达此处
    }
};

重写的代码怎么也通不过，只能再看之前写的代码。

• 时间复杂度：时间复杂度：O(log min(m,n))
• 空间复杂度：O(1)

搜索二维矩阵II

分析

z字形查找方法，从矩阵右上角进行搜索:

• matrix[i][j] == target，搜索完成。
• matrix[i][j] > target，j--。
• matrix[i][j] < target，i++。

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

• 时间复杂度：O(m + n)，操作过程中，要么i+1，要么j-1，i最多加m次，j最多减n次。
• 空间复杂度：O(1)

x的平方根

分析

可以从0~x的范围，用二分法进行查找。

class Solution {
public:
    int mySqrt(int x) {
        int left = 0;
        int right = x;
        int res = -1;
        while(left <= right){
            int mid = (left + right) / 2;
            if((long long)mid * (long long)mid <= x){
                res = mid;
                left = mid + 1;
            }
            else{
                right = mid - 1;
            }
        }
        return res;
    }
};

• 时间复杂度：O(logx)
• 空间复杂度：O(1)

移动零

分析

使用两个指针，slow指向指向处理好的非0数字的尾部，fast指向当前待处理元素。不断向右移动fast，每次移动到非零数，则将左右指针对应的数交换，交换同时将slow右移。最后，slow指针左侧均为处理好的非零数。

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int slow = 0, fast = 0;
        while(fast < nums.size()){
            if(nums[fast] != 0){
                swap(nums[slow], nums[fast]);
                slow++;
            }
            fast++;
        }   
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(1)

字符串相加

分析

class Solution {
public:
    string addStrings(string num1, string num2) {
        int n1 = num1.length();
        int n2 = num2.length();
        if(n1 < n2){
            return addStrings(num2, num1);
        }
        string res;
        int carry = 0;
        int i = n1-1, j = n2-1;
        while(i >= 0 && j >= 0){
            int t1 = num1[i--] - '0';
            int t2 = num2[j--] - '0';
            res = to_string((t1 + t2 + carry) % 10 ) + res;
            carry = (t1 + t2 + carry) / 10;
        }
        while(i >= 0){
            int t = num1[i--] - '0';
            res = to_string((t + carry) % 10) + res;
            carry = (t + carry) / 10;
        }
        if(carry == 1){
            res = '1' + res;
        }
        return res;
    }
};

• 时间复杂度：O(max(len1, len2))
• 空间复杂度：O(1)

滑动窗口最大值

优先队列

初始时将前k个元素加入优先队列的二叉堆中。存入优先队列的是数组值与索引构成的元组。优先队列将数组值作为优先级。每当我们向右移动窗口时，我们就可以把一个新的元素放入优先队列中，此时堆顶的元素就是堆中所有元素的最大值。然而这个最大值可能并不在滑动窗口中，在这种情况下，这个值在数组 nums 中的位置出现在滑动窗口左边界的左侧。可以将其永久地从优先队列中移除。不断地移除堆顶的元素，直到其确实出现在滑动窗口中。此时，堆顶元素就是滑动窗口中的最大值。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        // 定义优先队列并初始化
        priority_queue<pair<int, int>> q;
        for(int i = 0; i < k; i++){
            q.push({nums[i], i});
        }
        vector<int> res;
        res.push_back(q.top().first);
        // 逐渐向右移动窗口
        for(int i = k; i < n; i++){
            q.push({nums[i], i});
            while(q.top().second <= i-k){
                q.pop();
            }
            res.push_back(q.top().first);
        }
        return res;
    }
};

• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)

单调栈

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        // 定义双端队列并初始化
        deque<int> q;
        for(int i = 0; i < k; i++){
            while(!q.empty() && nums[i] >= nums[q.back()]){
                q.pop_back();
            }
            q.push_back(i);
        }
        // 向右移动窗口
        vector<int> res = {nums[q.front()]};
        for(int i = k; i < n; i++){
            while(!q.empty() && nums[i] >= nums[q.back()]){
                q.pop_back();
            }
            q.push_back(i);
            while(q.front() <= i - k){
                q.pop_front();
            }
            res.push_back(nums[q.front()]);
        }
        return res;
    }
};

• 时间复杂度：O(n)，每一个下标恰好被放入队列一次，并且最多被弹出队列一次。
• 空间复杂度：O(k)，因此「不断从队首弹出元素」保证了队列中最多不会有超过k+1个元素。

分块 + 预处理

将数组所有元素每k个分为一组，最后一组中元素的数量可能会不足 k 个。如果我们希望求出 nums[i] 到 nums[i+k−1] 的最大值，就会有两种情况：

• 如果i是k的倍数，那么此区间恰好是一个分组，只需要预处理出每个分组的最大值即可；
• 如果i不是k的倍数，那么存在一个j，i<j≤i+k−1，那么 nums[i] 到 nums[j−1] 就是第一个分组的后缀，nums[j] 到 nums[i+k−1] 就是第二个分组的前缀。如果我们能够预处理出每个分组中的前缀最大值以及后缀最大值，同样可以在 O(1) 的时间得到答案。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        // 定义前后缀数组
        int n = nums.size();
        vector<int> prefixMax(n), suffixMax(n);
        // 处理前缀
        for(int i = 0; i < n; i++){
            if(i % k == 0){
                prefixMax[i] = nums[i];
            }
            else{
                prefixMax[i] = max(prefixMax[i-1], nums[i]);
            }
        }
        // 处理后缀
        for(int i = n-1; i >= 0; i--){
            if(i == n-1 || (i + 1) % k == 0){
                suffixMax[i] = nums[i];
            }
            else{
                suffixMax[i] = max(suffixMax[i+1], nums[i]);
            }
        }
        // 返回结果
        vector<int> res;
        for(int i = 0; i <= n-k; i++){
            res.push_back(max(suffixMax[i], prefixMax[i+k-1]));
        }
        return res;
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(n)

无重复字符的最长子串

分析

双指针，维护一个left和一个right，用哈希表记录两个指针的窗口内字符的个数，用一个变量维护不含重复字符的最长子串长度。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // 定义双指针
        int n = s.length();
        int left = 0, right = 0;
        unordered_map<char, int> hash;
        int res = 0;
        // 枚举右指针
        while(right < n){
            if(hash.find(s[right]) == hash.end()){
                hash[s[right]] = 1;
            }
            else{
                hash[s[right]]++;
            }
            // 消除重复字符
            while(hash[s[right]] > 1){
                hash[s[left]]--;
                left++;
            }
            res = max(res, right - left + 1);
            right++;
        }
        return res;
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(1)

最小覆盖子串

分析

用一个变量 less 维护目前子串中有 less 种字母的出现次数小于 t 中字母的出现次数。

1. 初始化左右指针，ansLeft = -1, ansRight = m，m为s子串的长度。
2. 用哈希表或数组记录t中的字符情况，由于也要记录s中的情况，因此可以用一个数组cnt[] = cntT[] - cntS来代替，节省空间。
3. 初始化less为t中不同字母的个数。
4. 枚举右指针，即将右指针所指字符移入窗口内，cnt[s[right]]--，如果此时cnt[s[right]] == 0，说明在当前字符移入窗口后该字符的数量等于t中的数量，因此less可以减1.
5. 当less=0时，即s涵盖t，可以不断移动左指针，直到s又无法涵盖t。如果left所指字符在移出窗口前的cnt=0，那么在移出后，s无法涵盖t，所以less要+1.移出字符即cnt[s[left++]]++。

class Solution {
public:
    string minWindow(string s, string t) {
        int m = s.length();
        // 初始化左右指针、less、哈希表
        int ansLeft = -1, ansRight = m;
        int less = 0;
        int cnt[123];
        for(char c : t){
            // 统计less
            if(cnt[c] == 0){
                less++;
            }
            cnt[c]++;
        }
        // 滑动窗口
        int left = 0;
        for(int right = 0; right < m; right++){
            // 将右端点移入窗口内
            char c = s[right];
            cnt[c]--;
            // 更新less
            if(cnt[c] == 0){
                less--;
            }
            // 涵盖t，移动左指针
            while(less == 0){
                // 找到更短子串
                if(right - left < ansRight - ansLeft){
                    ansLeft = left;
                    ansRight = right;
                }
                // 移动左指针，更新less
                char x = s[left];
                if(cnt[x] == 0){    // 移动之后无法涵盖
                    less++;
                }
                cnt[x]++;
                left++;
            }
        }
        // 返回结果
        return ansLeft < 0 ? "" : s.substr(ansLeft, ansRight - ansLeft + 1);
    }
};

• 时间复杂度：O(m+n+∣Σ∣)
• 空间复杂度：O(∣Σ∣)

最长重复子数组

分析

1. 划分阶段：按照子数组结尾位置进行阶段划分。
2. 定义状态：dp[i][j]表示nums1前i个数字和nums2的前j个数字的最长公共子数组长度。
3. 状态转移方程：
   • 如果nums1[i-1] == nums2[j-1]，那么dp[i][j] = dp[i-1][j-1]+1；
   • 否则，dp[i][j] = 0。
4. 初始条件：dp[0][j] = dp[i][0] = 0
5. dp[i][j]中的最大值，可以在循环中用一个变量保存。

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        int res = 0;
        // 定义状态
        vector<vector<int>> dp(m+1, vector<int>(n+1));
        // 遍历
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(nums1[i-1] == nums2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    res = max(res, dp[i][j]);
                }                
            }
        }
        return res;
    }
};

• 时间复杂度：O(mn)
• 空间复杂度：O(mn)

删除排序链表中的重复元素

分析

用两个指针，pre和cur，当cur->val == pre->val时，删除当前节点，即pre->next = cur->next。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        // 处理边界
        if(!head || !head->next){
            return head;
        }
        // 定义两个指针
        ListNode* pre = head;
        ListNode* cur = pre->next;
        // 遍历链表
        while(cur){
            // 删除当前节点
            if(pre->val == cur->val){
                pre->next = cur->next;
            }
            else{
                pre = cur;
            }
            cur = cur->next;
        }
        return head;
    }
};

或者只用一个指针：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        // 处理边界
        if(!head){
            return head;
        }
        // 定义指针
        ListNode* cur = head;
        // 遍历链表
        while(cur->next){
            // 删除当前节点
            if(cur->val == cur->next->val){
                cur->next = cur->next->next;
            }
            else{
                cur = cur->next;
            }
        }
        return head;
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(1)

删除排序链表中的重复元素II

分析

与上一题的不同之处是，上一题会保留重复元素中的一个，而这道题要把重复的元素全部删除。在循环中用一个循环，把所有重复的节点删除，然后删除第一个节点，但是可能会把头节点删除，所以加一个dummy。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        // 处理边界
        if(!head){
            return head;
        }
        // 定义哑节点
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* cur = dummy;
        // 遍历
        while(cur->next && cur->next->next){
            // 如果相等
            if(cur->next->val == cur->next->next->val){
                // 暂时保存这个值
                int x = cur->next->val;
                while(cur->next && cur->next->val == x){
                    cur->next = cur->next->next;
                }
            }
            // 否则
            else{
                cur = cur->next;
            }
        }
        return dummy->next;
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(1)

总结

第二部分的题目主要涉及二分查找、滑动窗口、双指针等，注意二分查找的变形题目，主要是分析每次计算mid后，如何更新左右指针。滑动窗口的关键在于更新右指针后的操作以及如何更新左指针。在遍历链表时，要注意快慢指针所指向的节点，在有可能更改头节点的时候，要申请一个哑节点。