Leetcode数组章节

数组章节

二分查找

二分查找模板题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while(l <= r)
        {
            int mid = (l + r) / 2;
            if(nums[mid] < target)
                l = mid + 1;
            else if(nums[mid] > target)
                r = mid - 1;
            else
                return mid;
        }
        return -1;
    }
};

其中，变形题可根据不同的判断条件进行判断，如将三种情况重新分成两种等

lower_bound和upper_bound的实现

lower_bound—返回第一个 大于等于 的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        int ans = -1;
        while (l <= r)
        {
            int mid = (l + r) / 2;
            if (nums[mid] >= target)
            {
                r = mid - 1; // 可能左边还有值等于target的元素
                ans = mid;
            }
            else
                l = mid + 1;
        }
        return ans;
    }
};

upper_bound—返回第一个 大于 的元素

类似，第一个 大于 的元素则判断条件中 遇到 小于等于 的元素时执行l = mid + 1， 遇到大于的元素 记录ans的同时r = mid - 1，因为左边可能还有值 大于 的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        int ans = -1;
        while (l <= r)
        {
            int mid = (l + r) / 2;
            if (nums[mid] <= target)
                l = mid + 1;
            else
            {
            	r = mid - 1;
            	ans =mid;
            }
        }
        return ans;
    }
};

找到值等于target的区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int binary_search(vector<int>& nums, int target)
    {
        int l = 0, r = nums.size() - 1;
        int ans = -1;
        while (l <= r)
        {
            int mid = (l + r) / 2;
            if (nums[mid] >= target)
            {
                r = mid - 1; // 可能左边还有值等于target的元素
                ans = mid;
            }
            else
                l = mid + 1;
        }
        return ans;
    }
    vector<int> searchRange(vector<int>& nums, int target) {
        int n = nums.size() - 1;
        if(n < 0)   return {-1, -1};
        int st = -1, en = -1;
        st = binary_search(nums, target);
        en = binary_search(nums, target + 1);
        if(st == en) // 数组中找不到相等的元素
            return {-1, -1};
        else if(en == -1) // 找到相等的元素但没有比target更大的元素
            return {st, n};
        else
            return {st, en - 1};
    }
};

应用 lower_bound的实现（找到第一个 大于等于 的元素），通过寻找区间首元素和尾元素的位置判断，传入不同的target值， 即可实现；但不能用 upper_bound来实现，因为st = binary_search(nums, target - 1), en = binary_search(nums, target)中，想要得知数组中 是否存在与target值相等的元素 与 当en为尾后元素时 冲突，例如[5,7,7], target = 6和[2,2], target = 2

找到第一个(逆序排序) 小于等于 的元素

x的平方根

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int mySqrt(int x) {
        int l = 0, r = x, ans = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if ((long long)mid * mid <= x) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
};

(当从小到大排序时)与上述不同，这一题要求的是 小于等于 的元素，则判断条件中当遇到 小于等于 的元素时，记录该元素同时l = mid + 1，因为右边可能还有 小于等于 的元素；而当遇到大于的元素，则直接r = mid - 1不用记录

双指针——滑动窗口

移动元素

使用双指针在O(n)时间复杂度和O(1)空间复杂度下实现

同向遍历，即快慢指针实现，r指针遍历数组，不断的将r遍历到的不需要删除的元素赋值到l中，同时l++，当r遇到需要删除的元素则跳过，再次遇到不需要删除元素时，覆盖到l上，并逐一将后续需要的元素按顺序覆盖

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        // 同向遍历
        int l = 0, r = 0;
        for(r; r < nums.size(); r++)
        {
            if(nums[r] != val) // 需要删除的元素
            {
                nums[l] = nums[r];
                l++;
            }
        }
        return l;
    }
};

对向遍历，当l指针遇到需要删除的元素时与r指针交换，同时r–，此时，有可能r指针也指向需要删除的元素，因此这一轮中l指针不动，只移动r指针，也就在下一轮中再次判断l指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        // 对向遍历
        int l = 0, r = nums.size() - 1;
        while(l <= r)
        {
            if(nums[l] == val) // 需要删除的元素
            {
                swap(nums[l], nums[r--]);
            }
            else
                l++;
        }
        return l;
    }
};

有序数组的平方

首先利用有序性，找到负数与非负数的分界线，从分界线开始向左右两边使用双指针遍历，其中，寻找分界线时可以使用二分法进行加速查找；或者从数组两端开始遍历并比较，最后则需要将数组逆序输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
// 从分界线开始遍历
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        if(nums.size()==1)
            return {nums[0]*nums[0]};
        // 先找零 或者最小的正数
        int l = 0, r = nums.size() - 1;
        int ind = nums.size() - 1;
        while(l <= r)
        {
            int mid = (l + r) / 2;
            if(nums[mid] >= 0)
            {
                ind = mid;
                r = mid - 1;
            }
            else
                l = mid + 1;
        }
        l = ind - 1, r = ind;
        vector<int> res;

        while(l >= 0 && r < nums.size())
        {
            if(nums[l]*nums[l] < nums[r]*nums[r])
            {
                res.push_back(nums[l]*nums[l]);
                l--;
            }
            else
            {
                res.push_back(nums[r]*nums[r]);
                r++;
            }
        }
        while(l >= 0)
        {
            res.push_back(nums[l]*nums[l]);
            l--;
        }
        while(r < nums.size())
        {
            res.push_back(nums[r]*nums[r]);
            r++;
        }
        return res;
    }
};



// 从两端开始遍历
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> res;
        int n = nums.size();
        int i = 0, j = n - 1;
        while(i < j)
        {
            if(abs(nums[i]) > nums[j])
            {
                res.push_back(nums[i] * nums[i]);
                i++;
            }
            else
            {
                res.push_back(nums[j] * nums[j]);
                j--;
            }
        }
        res.push_back(nums[i]*nums[i]);
        reverse(res.begin(), res.end());
        return res;
    }
};

总结1

通常，在使用快慢指针时，用快指针遍历数组并判断是否符合条件，而不是用慢指针，因此是判断if(nums[r] != val)而不是if(val == nums[l]，否则会miss掉一些值

删除有序数组中的重复项

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size() == 1)    return 1;
        int l = 1;
        for(int r = 1; r < nums.size(); r++)
        {
            if(nums[r] > nums[r - 1])
                nums[l++] = nums[r];
        }
        return l;
    }
};

删除有序数组中的重复项 II

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int l = 2;
        if(nums.size() < 3) return nums.size();
        for(int r = 2; r < nums.size(); r++)
        {
            if(nums[r] != nums[l - 2])
                nums[l++] = nums[r];
        }
        return l;
    }
};

总结2

都使用快慢指针，但当允许有两个重复值时，应该比较的是 快指针和慢指针-2，而不是 快指针和快指针-2，因为快慢指针都被初始化为2，当相等时，则快指针（=慢指针）当前值多余，快指针继续遍历；遍历至当快指针遇到与慢指针-2不相等时，则可以将快指针的值赋值到慢指针，此时慢指针 = 慢指针 - 1 = 慢指针 - 2，需要删除的是慢指针而不是快指针。

同理，I中也可以将判断条件改为if(nums[r] != nums[l - 1])，也可以延伸到重复项数量为k

长度最小的子数组

右指针遍历整个数组，并不断扩大窗口，直至满足条件后，while循环中不断缩小窗口并更新结果，维持动态窗口满足条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        long long sum = 0;
        int i = 0;
        int res = nums.size() + 1;
        for(int j = 0; j < nums.size(); j++)
        {
            sum += nums[j];
            while(sum >= target)
            {
                res = min(res, j - i + 1);
                sum -= nums[i];
                i++;
            }
        }
        return res == nums.size() + 1? 0 : res;
    }
};

最小覆盖子串

同样地，右指针遍历整个数组，而左指针不断缩小窗口，同时更新结果。此外，需要用哈希表记录窗口的访问记录并判断是否符合条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    unordered_map<char, int> store, vis;

    bool check()
    {
        for (const auto & it : store)
        {
            if ((vis.find(it.first) == vis.end()) || (vis.find(it.first) != vis.end() && vis[it.first] < it.second))
                return false;
        }
        return true;
    }
    string minWindow(string s, string t) {

        for (auto c : t)
        {
            store[c]++;
        }
        int i = 0, j = 0;
        int res = s.size() + 1;
        int ind = i;
        while (j < s.size())
        {
            vis[s[j]]++;
            while (check()) // 已覆盖t字符串，则尝试缩小左边范围
            {
                if(res > j - i + 1)
                {
                    res = j - i + 1;
                    ind = i;
                }
                vis[s[i++]]--;
            }
            j++;
        }
        return res == s.size() + 1 ? "" : s.substr(ind, res);
    }
};

水果成篮

同样，右指针遍历数组，并扩大窗口，在不满足条件后，左指针不断缩小窗口，直至满足条件后更新结果。另外，还需要用哈希表来判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int res = 0;
        unordered_map<int, int> vis;
        int i = 0;
        for(int j = 0; j < fruits.size(); j++)
        {
            vis[fruits[j]]++;
            while(vis.size() > 2)
            {
                vis[fruits[i]]--;
                if(vis[fruits[i]] == 0)
                    vis.erase(fruits[i]);
                i++;
            }
            res = max(res, j - i + 1);
        }
        return res;
    }
};

无重复字符的最长子串

同样地思路，右指针不断扩大窗口，为了在扩大的时候不重复包含已有的元素，在添加元素到窗口之前把窗口中已有的对应元素删除掉，即左指针缩小窗口的过程，然后再更新结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int j = 0 , i = 0;
        int res = 0;
        unordered_set<char> store;
        for(j; j < s.size(); j++)
        {
            while(store.find(s[j]) != store.end())// 如果出现重复则先删除
            {
                store.erase(s[i++]);
            }
            if(store.find(s[j]) == store.end()) // 没有重复则加入
                store.insert(s[j]);
            res = max(res, j - i + 1);
        }
        return res;
    }
};

总结3

水果成篮和无重复字符的最长子串所求的是最大窗口长度，而长度最小的子数组和最小覆盖子串求的是最小窗口长度，因此同样的遍历循环下，要在不同位置对结果进行更新，即求最大窗口长度时要在左指针遍历结束后更新，求最小窗口长度则是在右指针遍历过程中更新

双指针——固定窗口

模拟

螺旋矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        int m = matrix.size(), n = matrix[0].size();
        int up = 0, down = m-1, left = 0, right = n-1;
        while (up <= down && left <= right)
        {
            for (int j = left; j <= right; j++)
            {
                res.push_back(matrix[up][j]);
            }
            up++;
            for (int i = up; i <= down; i++)
            {
                res.push_back(matrix[i][right]);
            }
            right--;
            if(up > down || left > right)
                break;
            for (int j = right; j >= left; j--)
            {
                res.push_back(matrix[down][j]);
            }
            down--;
            for (int i = down; i >= up; i--)
            {
                res.push_back(matrix[i][left]);
            }
            left++;
        }
        return res;
    }
};

螺旋矩阵 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        int cnt = n * n;
        int tmp = 1;
        int up = 0, down = n - 1, left = 0, right = n - 1;
        vector<vector<int>> res(n, vector<int>(n));
        while (tmp <= cnt)
        {
            for (int j = left; j <= right; j++)
            {
                res[up][j] = tmp++;
            }
            up++;
            for (int i = up; i <= down; i++)
            {
                res[i][right] = tmp++;
            }
            right--;
            if (tmp > cnt)
                break;
            for (int j = right; j >= left; j--)
            {
                res[down][j] = tmp++;
            }
            down--;
            for (int i = down; i >= up; i--)
            {
                res[i][left] = tmp++;
            }
            left++;
        }
        return res;
    }
};
Leetcode数组章节
https://kevin346-sc.github.io/2023/04/24/Leetcode数组章节/
作者
Kevin Huang
发布于
2023年4月24日
许可协议