[LeetCode]数组部分记录

跟随《代码随想录》刷题，12.11~12.14 小记录。

下面我按照做题顺序，梳理一下目前做的题目。既是一个算法做题的分享，也是自己回顾知识，增强记忆点的方式。最近题目的特点是，基本最优解都是「双指针」解法。

前言—关于双指针算法

双指针算法是一种常用于数组（或链表）操作的算法技巧，它通过维护两个指针，分别指向序列中的不同位置，以解决一些特定问题。这两个指针可以是同方向移动，也可以是相反方向移动。

常见的双指针算法有三种类型：

  1. 快慢指针： 主要用于解决链表中的问题，例如判断链表是否有环，找到链表的中间节点等。一个指针移动速度快（快指针），另一个指针移动速度慢（慢指针），从而在链表中实现一种追赶的效果。

  2. 左右指针： 主要用于数组或字符串的问题，例如在有序数组中找到两个数使它们的和等于目标值。左指针指向序列的开头，右指针指向序列的末尾，根据题目的要求，移动左右指针来达到特定的条件。

  3. 滑动窗口： 通常用于解决子数组或子串的问题，例如找到最小覆盖子串、最长无重复字符的子串等。通过维护一个区间（窗口），其中的元素满足一定的条件，然后根据条件移动窗口的起始位置或结束位置。

这些双指针算法的核心思想是通过控制指针的移动，有效地减小问题的规模，从而提高算法的效率。在解决一些数组、链表或字符串相关的问题时，双指针算法是一个非常有用的工具。

一、快慢指针

1. 典型题目

26. 删除有序数组中的重复项

输入: [0,0,1,1,1,2,2,3,3,4] or [1,2,3,4,4,4,5,5,6]
输出: [0,1,2,3,4] or [1,2,3,4,5,6]

下面是我的题解，核心是初始化：i = 0, j = i + 1，这样方便比较相邻数字是否重复。如果没重复，i 和 j都往右移，否则，i 不动，移动 j，直到 j 找到一个不相同的数，覆盖掉 i 的右侧重复数据。这样遍历下去，就能把重复项去除，返回 i + 1 表示新数组长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int i = 0, sz = nums.size();
        for (int j = i + 1; j < sz; j++)
        {
            if (nums[j] != nums[i])
            {
                nums[i+1] = nums[j];
                i++;
            }
        }
        return i + 1;
    }
};
27.移除元素

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]

题解如下，这里还是用到了快慢指针，也是用快指针 j 遍历，慢指针 i 标记有效元素最后的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int i = 0;
        int sz = nums.size();

        for (int j = 0; j < sz; ++j) {
            if (nums[j] != val) {
                nums[i++] = nums[j];
            }
        }

        cout << i << ", nums = [";
        for (int ct = 0; ct < i; ++ct) {
            cout << nums[ct];
            if (ct != i - 1) {
                cout << ",";
            }
        }
        std::cout << "]" << std::endl;
        return i;
    }
};
283. 移动零

输入：[0,1,0,3,12]
输出：[1,3,12,0,0]

题解如下，j 用于遍历数组找非 0 元素，找到了就和 i 做交换，让 i 始终指向非 0 元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int i = 0, sz = nums.size();
        for(int j = 0; j < sz; j++) {
			if (nums[j] != 0) {
                int temp = nums[i];
                nums[i++] = nums[j];
                nums[j] = temp;
            }
        }
    }
};
844. 比较含退格的字符串

输入：s = “ab#c”, t = “ad#c”
输出：true
解释：s 和 t 都会变成 “ac”。

虽然这个题目的难度给的是简单的，但是实际我觉得按照时间复杂度，空间复杂度 $$O(1)$$来做的话，苦思冥想还是想不出来。后面参考了 chatGPT 的双指针解法才解决。开始我是用的栈，创建两个栈分别处理两个字符串。

一、栈处理

代码如下，核心就是创建一个栈stk，便利字符串，如果字符是#，则不入栈且将栈顶元素出栈；如果是非#的字符，则入栈。处理完两个字符串后，比较两个栈即可得出是否相等。时间复杂度：$$O(n)$$，空间复杂度：$$O(n)$$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool backspaceCompare(string s, string t) {
        	stack<char> stk1, stk2;
            for (auto c : s) {
            	if (c != '#')
                	stk1.push(c);
            	else
                    if (!stk1.empty())
                		stk1.pop();
            }
        	for (auto c : t) {
            	if (c != '#')
                	stk2.push(c);
            	else
                    if (!stk2.empty())
                		stk2.pop();
            }
        
			return stk1 == stk2;
    }
};

二、双指针

代码如下，当字符串中存在退格符 # 时，我们可以使用两个指针从字符串末尾向前遍历，跳过相应的退格符，并比较字符是否相等。这种方法的思想是通过逐个字符的比较，并在遇到退格符时调整指针位置，最终确定两个经过退格操作后的字符串是否相等。这样可以在一次遍历中完成比较，避免使用额外的空间。

  1. 定义两个指针 i 和 j 分别指向字符串 s 和 t 的末尾。

  2. 使用循环，条件为 i >= 0 || j >= 0，即两个字符串至少有一个还没有遍历完。

  3. 在循环前，使用 sBackspaceCount 记录遇到的退格符的数量，对字符串 s 执行退格操作，这里又使用了一个 while循环，循环继续的条件有两个：

    （1）字符串没遍历完且当前遍历到的字符是’#’，则需要回退的字符个数+1：i >= 0 && (s[i] == '#'；

    （2）退格符还没处理完：sBackspaceCount > 0。

    进入到 while 循环后，如果当前字符是 #，则增加 sBackspaceCount，否则减少，通过回退字符抵消掉一个#。通过这个循环，i 移动到有效字符或字符串的开头。

  4. 类似地，对字符串 t执行相同的退格操作，将 j 移动到有效字符或字符串的开头。

  5. 比较 s[i] 和 t[j]，先判断不想等的情况：

    • 存在且不相等，返回 false；
    • 一个字符串遍历完而另一个没有，也返回 false。

  6. 比较之后，两个字符相等，则将 i 和 j 减一，继续下一轮循环。

  7. 循环结束，说明两个字符串经过退格操作后相等，返回 true。

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
class Solution {
public:
    bool backspaceCompare(string s, string t) {
        int i = s.length() - 1, j = t.length() - 1;

        while (i >= 0 || j >= 0) {
            int sBackspaceCount = 0;
            while (i >= 0 && (s[i] == '#' || sBackspaceCount > 0)) {
                sBackspaceCount += (s[i] == '#') ? 1 : -1;
                --i;
            }

            int tBackspaceCount = 0;
            while (j >= 0 && (t[j] == '#' || tBackspaceCount > 0)) {
                tBackspaceCount += (t[j] == '#') ? 1 : -1;
                --j;
            }

            if (i >= 0 && j >= 0 && s[i] != t[j]) {
                return false;
            }

            if ((i >= 0) != (j >= 0)) {
                return 0;
            }
            --i;
            --j;
        }
        return true;
    }
};
977. 有序数组的平方

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

一、直接快速排序

最简单的就是先遍历数组做平方，然后对平方后的数组做快速排序。时间复杂度：$$O(nlogn)$$, 没使用额外空间，因此空间复杂度是 $$O(1)$$。

二、使用双指针

代码如下，这里用到双指针是因为有序数组平方之后，其实还是可以确定最大值不是在最左边就是在最右边，那么就可以用 i 指针从左向右移动，用 j 从右向左移动，逐一比较两个值，更大的那个就是整个数组最大的。创建大小相同的数组 res 来存储两端比较之后的较大值，取哪个之后，就移动哪个指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int sz = nums.size();
        vector<int> res(sz, 0);
        int i = 0, j = sz - 1, k = sz - 1;
        // 遍历条件是左指针i不超过右指针j
        while (i <= j) {
            int head = nums[i] * nums[i], tail = nums[j] * nums[j];
            if (head >= tail) {
                // 这里左边的值更大，则左指针右移一格
                res[k--] = head;
                i++;
            } else {
                // 这里右边的值更大，则右指针左移一格
                res[k--] = tail;
                j--;
            }
        }
        // 遍历结束，说明数值都已经填
        return res;
    }
};

类似的： LCR 008. 长度最小的子数组

二、左右指针

1. 典型题目

167. 两数之和 II - 输入有序数组

三、滑动窗口

1. 典型题目

904. 水果成篮

我是先看过 labuladong 大神的文章：我写了首诗，把滑动窗口算法变成了默写题。其中的第 76 题「最小覆盖子串」难度 Hard，我似懂非懂地看完了，觉得还是理解不够透彻。于是参考着做了另一道难度中等的题目，就是904. 水果成篮。

我首先自己做了一遍，不看参考，自己尝试按照滑动窗口的理解写了如下代码：

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
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        // 大小为 2 的哈希表，表示水果种类和数量
        unordered_map<int, int> basket;
        int sz = fruits.size();
        int left = 0, right = 0, res = 0;

        while (right < sz) {
            // 表示种类为fruits[right]的水果个数+1
            basket[fruits[right]]++;
			
            // 更新当前水果数目
            res = (right - left + 1) > res ? (right - left + 1) : res;

            // 当篮子满了
            while (basket.size() > 2) {
                // 左边界移动
                if (basket.count(fruits[left]) == 1) {
                    basket.erase(fruits[left]);
                } else {
                    basket[fruits[left]]--;
                }
                left++;
            }            

            right++;
        }

        return res;
    }
};

但是结果始终不对。咨询 GPT 老师，得出结论是，我要两处地方有问题：

  1. 逻辑错误

    在 basket[fruits[right]]++; 之后，计算 res 的语句应该放在 while (basket.size() > 2) 循环之外，以确保 res 在每次循环的开始时都被更新；

  2. 不恰当的左边界移动

    在 basket.count(fruits[left]) == 1 分支中，只检查了水果种类是否在篮子中，而没有检查数量是否为1。应该修改为 basket[fruits[left]] == 1 才删除对应水果。

总结：GPT 老师很厉害啊，以后刷题更方便了！后续再刷一些题目，巩固滑动窗口的算法！应当集中在中等难度的题目，困难的题目浪费人生！