LeetCode 27.移除元素

题目描述

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

  • 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
  • 返回 k。

示例 1:

输入: nums = [3,2,2,3], val = 3
输出: 2，nums = [2,2,_,_]
解释: 你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

示例 2:

输入: nums = [0,1,2,2,3,0,4,2], val = 2
输出: 5，nums = [0,1,4,0,3,_,_,_]
解释: 你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。注意这五个元素可以任意顺序返回。

提示：

  • $0 \le {nums.length} \le 100$
  • $0 \le {nums[i]} \le 50$
  • $0 \le {val} \le 100$

思路

题目要求删除数组中等于 val 的元素，因此输出数组的长度一定小于等于输入数组的长度，我们可以把输出的数组直接写在输入数组上。数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。

最容易想到的就是暴力解法，使用两个 for 循环，第一个 for 循环遍历数组元素 ，第二个 for 循环更新数组。

可以使用双指针进行优化：使用快指针和慢指针在一个 for 循环下完成两个 for 循环的工作

快慢指针的定义：

  • 快指针：指向当前需要处理的元素
  • 慢指针：指向下一个将要赋值的位置

如果快指针指向的元素不等于 val ，它一定是输出数组的一个元素，就将快指针指向的元素复制到慢指针的位置，快慢指针同时后移。

如果快指针指向的元素等于 val ，它不能在输出数组里，此时慢指针不动，快指针右移一位。

整个过程保持不变的性质是：区间 [0, slow) 中的元素都不等于 val。

当快指针遍历完输入数组以后，slow 的值就是输出数组的长度。

二分查找

C++代码

c++
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 slow = 0, fast = 0;
        while (fast < nums.size()) {
            if (nums[fast] != val) {
                // 当前要处理的元素的值不等于 val, 将其保存到新数组中（放到原数组slow的位置）
                swap(nums[slow], nums[fast]);
                // 此时 slow 后移，指向下一个可以赋值的位置，保证 [0, slow)区间的元素一定不等于 val
                ++slow;
            }
            ++fast;
        }
        return slow;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

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

题目描述

给你一个 非严格递增排列 的数组 nums ，请你原地删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

  • 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
  • 返回 k 。

示例 1:

输入: nums = [1,1,2]
输出: 2，nums = [1,2,_]
解释: 函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2:

输入: nums = [0,0,1,1,1,2,2,3,3,4]
输出: 5，nums = [0,1,2,3,4]
解释: 函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0，1，2，3，4。不需要考虑数组中超出新长度后面的元素。

提示：

  • $1 \le {nums.length} \le 3*10^{4}$
  • $-10^4 \le {nums[i]} \le 10^4$
  • $nums$ 已按 非严格递增 排列

思路

nums 已按 非严格递增 排列，说明重复元素一定是彼此相邻的，只需要保留一个即可。那么我们可以理解为每个非空数组的第一个元素一定的需要保留的，可以考虑一种极端情况 nums = [1,1,1,1,1] ，只需要保留数组中第一个即可。

同样可以使用双指针，只需要遍历一边数组即可：

  • 快指针：指向当前需要处理的元素
  • 慢指针：指向已经处理好的非重复元素的最后一个，这里与上一题有所不同，这里的有效区间是 [0, slow] ,这里是闭区间，所以最后需要返回的是 slow + 1

如果快指针指向的元素不等于慢指针指向的元素 ，它一定是输出数组的一个元素，就将快指针指向的元素复制到慢指针的后一个位置，快慢指针同时后移。

如果快指针指向的元素等于慢指针指向的元素，说明该元素重复了，慢指针不动，快指针右移一位。

整个过程保持不变的性质是：区间 [0, slow] 中的元素都不重复。

当快指针遍历完输入数组以后，slow + 1 的值就是输出数组的长度。

C++代码

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int slow = 0, fast = 1;
        while (fast < nums.size()) {
            if (nums[slow] != nums[fast]) {
                // 当前要处理的元素的值不等于 val, 将其保存到新数组中（放到原数组slow + 1的位置）
                nums[slow + 1] = nums[fast];
                // 此时 slow 后移，指向新数组的末尾，保证 [0, slow] 区间的元素一定不等于 val
                ++slow;
            }
            ++fast;
        }
        return slow + 1;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

LeetCode 283.移动零

题目描述

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

提示：

  • $1 \le {nums.length} \le 10^{4}$
  • $-2^{31} \le {nums[i]} \le 2^{31} - 1$

思路

使用双指针，左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部。

右指针不断向右移动，若右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。

注意到以下性质：

  • 左指针左边均为非零数；
  • 右指针左边直到左指针处均为零（左指针指向的可能是非零数也可能是零）

因此每次交换，都是将左指针的零与右指针的非零数交换，且非零数的相对顺序并未改变。

（极端情况，若数组中没有零，则每次交换的都是自己，相当于位置不变）

C++代码

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
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)

LeetCode 844.比较含退格的字符串

题目描述

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

**注意：**如果对空文本输入退格字符，文本继续为空。

示例 1:

输入: s = "ab#c", t = "ad#c"
输出: true

示例 2:

输入: s = "ab##", t = "c#d#"
输出: true

示例 3:

输入: s = "a#c", t = "b"
输出: false

提示：

  • $1 \le {s.length, t.length} \le 200$
  • s 和 t 只含有小写字母以及字符 '#'

思路

**一个字符是否会被删掉，只取决于该字符后面的退格符，而与该字符前面的退格符无关。**因此当我们逆序地遍历字符串，就可以立即确定当前字符是否会被删掉。

定义 skip 表示当前待删除的字符的数量。每次我们遍历到一个字符：

  • 若该字符为退格符，则我们需要多删除一个普通字符，让 skip 加 1
  • 若该字符为普通字符：
    • 若 skip 为 0，则说明当前字符不需要删去；
    • 若 skip 不为 0，则说明当前字符需要删去，我们让 skip 减 1。

定义两个指针，分别指向两字符串的末尾。每次我们让两指针逆序地遍历两字符串，直到两字符串能够各自确定一个字符，然后将这两个字符进行比较。重复这一过程直到找到的两个字符不相等，或遍历完字符串为止。

C++代码

c++
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
class Solution {
public:
    bool backspaceCompare(string s, string t) {
        // 从后往前遍历------方便退格（相当于遇到 # 跳过前面的）
        int i = s.size() - 1, j = t.size() - 1;
        // 分别记录当前字符串需要跳过的字符串个数
        int skipS = 0, skipT = 0;
        while (i >= 0 || j >= 0) {
            while (i >= 0) {
                if (s[i] == '#') {  
                    // 如果当前位置是 # 就进行记录
                    ++skipS;
                    --i;
                } else if (skipS > 0) {  
                    // 如果当前位置是字符，并且skipS大于零说明，他的后面有退格#，就跳过
                    --skipS;
                    --i;
                } else {
                    // 此时skipS == 0，不需要跳过当前字符，跳出循环，将该字符与字符串t的进行比较
                    break;
                }
            }
            // 与上面同理
            while (j >= 0) {
                if (t[j] == '#') {
                    ++skipT;
                    --j;
                } else if (skipT > 0) {
                    --skipT;
                    --j;
                } else {
                    break;
                }
            }
            if (i >= 0 && j >= 0) {  // 保证不会越界
                if (s[i] != t[j]) {
                    return false;
                } 
            } else if (i >= 0 || j >= 0) {  // 进入这里面，说明有一个字符串的索引已经小于0了
                    return false;
            }
            --i;
            --j;
        }
        return true;
    }
};
  • 时间复杂度：O(N + M) , 其中 N 和 M 分别为字符串 S 和 T 的长度。我们需要遍历两字符串各一次。
  • 空间复杂度：O(1)

LeetCode 977.有序数的平方

题目描述

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1:

输入: nums = [-4,-1,0,3,10]
输出: [0,1,9,16,100]

示例 2:

输入: nums = [-7,-3,2,3,11]
输出: [4,9,9,49,121]

提示：

  • $1 \le {nums.length} \le 10^4$
  • $-10^4 \le {nums[i]} \le 10^4$
  • nums 已按 非递减顺序 排序

思路

使用两个指针分别指向位置 0 和 n−1 ，每次比较两个指针对应的数，选择较大的那个逆序放入答案并移动指针。逆序插入

C++代码

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n);
        int index = n - 1;
        int left = 0, right = n - 1;
        while (left <= right) {
            if (nums[right] * nums[right] >= nums[left] * nums[left]) {
                ans[index--] = nums[right] * nums[right];
                --right;
            } else {
                ans[index--] = nums[left] * nums[left];
                ++left;
            }
        }
        return ans;
    }
};
  • 时间复杂度：O(n) , 其中 n 是数组 nums 的长度。
  • 空间复杂度：O(1) , 除了存储答案的数组以外，我们只需要维护常量空间。