AllenY's blog

🧑🏻‍💻🎮🍿🎹🗻

Home Archive Tags About

LeetCode刷题记录（数组篇）

2024-03-25 16 min read # LeetCode

LeetCode刷题记录（数组篇），个人向。
为了锻炼代码能力，会交替使用不同编程语言完成答案。

难度：Easy
语言：C++

题目描述。
确定好并保持区间一致性即可，例如是闭区间还是开区间，不变量贯彻到底即可。

  int search(vector<int>& nums, int target) {
    int size = nums.size();
    int lower = 0;
    int upper = size - 1;
    int index = 0;
    while (true) {
      if (upper < lower) {
        return -1;
      }
      index = (lower + upper) / 2;
      int now = nums[index];
      if (now == target) {
        return index;
      }
      if (target < now) {
        upper = index - 1;
      } else {
        lower = index + 1;
      }
    }
  }

[27] Remove Element

难度：Easy
语言：Python

题目描述。
利用元素顺序可以改变的特性，左右指针往中间靠拢即可。

    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        head_index = 0
        tail_index = len(nums) - 1
        while tail_index >= 0 and nums[tail_index] == val:
            tail_index -= 1
        while head_index < tail_index:
            if nums[head_index] == val:
                nums[head_index] = nums[tail_index]
                tail_index -= 1

            head_index += 1
            while head_index <= tail_index and nums[tail_index] == val:
                tail_index -= 1
        return tail_index + 1

[977] Squares of a Sorted Array

难度：Easy
语言：Rust

题目描述。
原数组是有序的，因此平方后最大值一定在两端。利用双指针往中间靠拢即可。

    pub fn sorted_squares(nums: Vec<i32>) -> Vec<i32> {
        let (mut left, mut right) = (0, nums.len() - 1);
        let mut cur_index = right;
        let mut res: Vec<i32> = vec![0; right + 1];
        while left <= right {
            let (left_squares, right_squares) =
                (nums[left] * nums[left], nums[right] * nums[right]);

            if left_squares < right_squares {
                right -= 1;
                res[cur_index] = right_squares;
            } else {
                left += 1;
                res[cur_index] = left_squares
            };

            cur_index -= 1;
        }
        res
    }

[209] Minimum Size Subarray Sum

难度：Medium
语言：C++

题目描述。
使用滑动窗口（其实也相当于快慢指针）即可。每次sum >= target了就开始注意更新left指针，最后返回min_len即可。复杂度O(n)。说是Medium但是是做起来最快的一道。

  int minSubArrayLen(int target, vector<int>& nums) {
    int sum = 0;
    int left = 0;
    int right = 0;
    int n = nums.size();
    int min_len = n + 1;
    while (right < n) {
      sum += nums[right];

      if (sum >= target) {
        while (sum - nums[left] >=
               target) {  // if target can be zero, the condition should be
                          // (left <= right && sum - nums[left] >= target
          sum -= nums[left];
          left++;
        }
        if (right - left + 1 < min_len) {
          min_len = right - left + 1;
        }
      }
      right++;
    }

    return min_len > n ? 0 : min_len;
  }

[59] Spiral Matrix II

难度：Medium
语言：Python

题目描述。
没什么算法可言，就是锻炼代码能力，难点在于边界条件的判断。
一般来说坚持循环不变量即可，例如每次循环坚持左闭右开。但是有特殊情况，那就是n如果是奇数就会有一个中心点，如果都坚持左闭右开的话就会导致中心点永远填不到。网上一些解法是特殊处理，单独最后填中心点的值。
本人的解法则是牺牲了一定的循环不变量，即每个round第一个循环（矩阵上方从左到右）采用了左闭右闭，第二、三个循环采用左开右闭，第四个循环（矩阵左边从下到上）采用左开右开（右开与第一个循环的左闭相对应），避免了中心点的单独处理（第一个循环是左闭右闭，所以能够处理中心点）。这种解法与前面那种各有利弊，见仁见智。

    def generateMatrix(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        ret = [[0] * n for _ in range(n)]
        round_index = 0
        cur_num = 1
        while cur_num <= n * n:
            for i in range(0 + round_index, n - round_index):
                ret[0 + round_index][i] = cur_num
                cur_num += 1
            for i in range(0 + round_index + 1, n - round_index):
                ret[i][n - round_index - 1] = cur_num
                cur_num += 1
            for i in range(n - round_index - 2, 0 + round_index - 1, -1):
                ret[n - round_index - 1][i] = cur_num
                cur_num += 1
            for i in range(n - round_index - 2, 0 + round_index, -1):
                ret[i][0 + round_index] = cur_num
                cur_num += 1
            round_index += 1
        return ret

总结

数组作为最基础的数据结构之一，内容也很简单。就做的几道经典题而言，要掌握的就是两个内容：

  • 循环不变量
    无论是二分法还是最后的螺旋矩阵模拟，防止边界条件出错的方法都是保持循环不变量，即按照区间的定义来操作。
  • 双指针
    两个指针可以是同向的（快慢指针、滑动窗口），也可以是相向的。不少题目都是用该套路来解（例如27，977，209）。

补充

[283] Move Zeroes

难度：Easy
语言：C++

题目描述。
题目要求保留非0元素相对顺序顺序。我们考虑把非0元素挨个挪到前面，然后把后面没被挪到的位置全部补0即可。
使用快慢指针即可。fast用来扫描非0元素，slow指向非0元素要被挪到的位置。fast扫描完以后再给slow及后面的位置补0。

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

[42] Trapping Rain Water

难度：Hard
语言：C++

题目描述。
双指针从左右往中间靠拢，同时记录左右指针各自扫到过的最大值leftMax和rightMax。
如果height[left] < height[right]，则++left，否则--right。
由于我们每次移动的都是left和right较矮的那一个，保留较高的那一个，因此left和right一定其中有一个是当前扫过的所有元素的最高值（高的指针等待矮的那个移动，直到另一个指针扫到更高的了才轮到这个指针移动）。
因此，当height[left] < height[right]，height[right]就是扫过的所有元素的最高值（同时也是rightMax）。对于左指针left，其left左边最高值（即leftMax）≤left右边最高值left左边最高值（即leftMax） \le left右边最高值，这是由于left左边最高值=leftMax<=所有遇到过的最高值=rightMax<=left右边最高值left左边最高值 = leftMax <= 所有遇到过的最高值 = rightMax <= left右边最高值。因此此时使用leftMax计算left所在柱子水量即可，即ans += leftMax - height[left]。
height[left] >= height[right]的情况反过来即可。

class Solution {
  public:
    int trap(vector<int> &height) {
        int n = height.size();
        int left = 0, right = n - 1;
        int leftMax = 0, rightMax = 0;
        int ans = 0;
        while (left < right) {
            leftMax = max(leftMax, height[left]);
            rightMax = max(rightMax, height[right]);
            if (height[left] < height[right]) {
                // leftMax < rightMax
                ans += leftMax - height[left];
                ++left;
            } else {
                // leftMax >= rightMax
                ans += rightMax - height[right];
                --right;
            }
        }

        return ans;
    }
};

[189] Rotate Array

难度：Medium
语言：C++

题目描述。
我们的目标是O(1)O(1)的空间复杂度。
三步反转即可：

  • 反转整个数组
  • 反转数组[0,k)[0, k)的部分
  • 反转数组[k,n)[k, n)的部分
class Solution {
  public:
    void rotate(vector<int> &nums, int k) {
        k %= nums.size();
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
    }
};

[238] Product of Array Except Self

难度：Medium
语言：C++

题目描述。
计算前缀乘积left[i] = left[i-1] * nums[i-1]，再计算后缀乘积right[i] = right[i+1] * nums[i+1]，然后每个数除自身以外数组的乘积就是left[i] + right[i]。这个方法的时间和空间复杂度均为O(n)O(n)。
我们可以再基于以上方法把空间复杂度降到O(1)O(1)（不考虑output的空间复杂度）。我们直接使用res先作为left，然后再用一个变量来存储right。我们在计算最终结果的过程中同时更新right变量，便可把这部分的空间复杂度降下来。最终得到如下代码。

class Solution {
  public:
    vector<int> productExceptSelf(vector<int> &nums) {
        int n = nums.size();
        vector<int> res(n, 1);
        for (int i = 1; i < n; ++i) {
            res[i] = res[i - 1] * nums[i - 1];
        }
        int right = 1;
        for (int i = n - 2; i >= 0; --i) {
            right *= nums[i + 1];
            res[i] *= right;
        }
        return res;
    }
};

[41] First Missing Positive

难度：Hard
语言：C++

题目描述。
题目难点在于同时需要O(n)O(n)的时间复杂度和O(1)O(1)的空间复杂度。
实际上这道题不存在真正O(1)O(1)空间复杂度的方法，最终我们也是使用并修改了原数组nums，不过不能修改nums的话可能就无解了。
思路就是，我们将nums[i]放回（交换）到nums[nums[i] - 1]的地方，尝试将数组构造成[1, 2, ..., N]的形式。最终，再看这种形式中数字缺失不满足的地方（即nums[i] != i+1），然后返回i即可。若都满足，说明结果应该是n + 1。

class Solution {
  public:
    int firstMissingPositive(vector<int> &nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            while (nums[i] != i + 1) {
                if (nums[i] < 1 || nums[i] > n ||
                    nums[i] == nums[nums[i] - 1]) {
                    break;
                }
                int idx = nums[i] - 1;
                nums[i] = nums[idx];
                nums[idx] = idx + 1;
            }
        }

        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
};

[73] Set Matrix Zeroes

难度：Medium
语言：C++

题目描述。
很容易想到，我们可以分别使用两个数组，一个记录每一行是否存在0，一个记录每一列是否存在0。先遍历一遍矩阵，填完这两个数组，然后再根据数组更新一遍矩阵即可。但是难点在于我们要使用O(1)O(1)的空间复杂度完成。
LeetCode上很多这种优化空间复杂度的解其实并没有换成什么多新颖的算法，只是借用了输入（或输出）里原本的空间而已。这里我们借用了矩阵里第一行和第一列的空间分别用来做那两个标记的数组。我们再使用一个额外变量flag_col0来记录第一列原本是否存在0（第一行原本是否存在0用matrix[0][0]就可以了）。于是我们先扫描一遍矩阵，更新flag_col0的同时把第一行和第一列填上，然后再根据第一行和第一列的元素更新矩阵即可。这里我们从最后一行填到第一行，防止第一行的值被提前覆盖掉（其他行要参考第一行的值）。最后，再根据falg_col0更新第一列。

class Solution {
  public:
    void setZeroes(vector<vector<int>> &matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        int flag_col0 = false;
        for (int i = 0; i < m; ++i) {
            if (matrix[i][0] == 0) {
                flag_col0 = true;
            }
            for (int j = 1; j < n; ++j) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = matrix[i][0] = 0;
                }
            }
        }

        for (int i = m - 1; i >= 0; --i) {
            for (int j = 1; j < n; ++j) {
                if (matrix[0][j] == 0 || matrix[i][0] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (flag_col0) {
            for (int i = 0; i < m; ++i) {
                matrix[i][0] = 0;
            }
        }
    }
};

[54] Spiral Matrix

难度：Medium
语言：C++

题目描述。
和[59] Spiral Matrix II类似，按层遍历矩阵。这里我们使用四个不同的变量来模拟4个边界，并在每次模拟完一边时更新该方向边界。

class Solution {
  public:
    vector<int> spiralOrder(vector<vector<int>> &matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<int> res;
        int u = 0, d = m - 1, l = 0, r = n - 1;
        while (true) {
            for (int j = l; j <= r; ++j) {
                res.emplace_back(matrix[u][j]);
            }
            if (++u > d) {
                break;
            }
            for (int i = u; i <= d; ++i) {
                res.emplace_back(matrix[i][r]);
            }
            if (--r < l) {
                break;
            }
            for (int j = r; j >= l; --j) {
                res.emplace_back(matrix[d][j]);
            }
            if (--d < u) {
                break;
            }
            for (int i = d; i >= u; --i) {
                res.emplace_back(matrix[i][l]);
            }
            if (++l > r) {
                break;
            }
        }
        return res;
    }
};

[48] Rotate Image

难度：Medium
语言：C++

题目描述。
利用公式newRow=oldCol,newCol=n−oldRow−1newRow = oldCol, newCol = n - oldRow - 1反复推四遍回到原点，然后把公式套进去即可。循环范围是n2∗n+12\frac{n}{2} * \frac{n+1}{2}，其中n为偶数则+1+1没影响，奇数+1+1则后面会进一个数字，例如5∗55*5的矩阵会得到2∗32*3，最后会留下中间的中心点。

class Solution {
  public:
    void rotate(vector<vector<int>> &matrix) {
        int n = matrix.size();
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < (n + 1) / 2; ++j) {
                int tmp = matrix[i][j];
                // newRow = oldCol, newCol = n - oldRow - 1
                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = tmp;
            }
        }
    }
};

[240] Search a 2D Matrix II

难度：Meidum
语言：C++

题目描述。
这道题的关键是要想到可以从右上角开始搜索，搜索范围是当前元素matrix[x][y]到原矩阵左下角的矩阵。

  • 若matrix[x][y] == target，说明找到值，返回true。
  • 若matrix[x][y] > target，则当前列（matrix[x][y]以及其下面的）值都大于target，y减小。
  • 若matrix[x][y] < target，则当前行（matrix[x][y]以及其左边的）值都小于target，x增大。

如此下去，若x或y碰到边界则说明值不存在，返回false。

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

[88] Merge Sorted Array

难度：Easy
语言：C++

题目描述。
题目要求把结果放在nums1里面，这就要求在排序的时候不覆盖nums1里面还未排序的值，同时我们又想要追求使用O(1)O(1)的空间复杂度来完成。
结果就是，我们可以反过来从最后开始排序。可以证明nums1的后面总是有足够的空间的（m+n−p1−1≥m−p1−1+n−p2−1m+n-p_1-1≥m-p_1-1+n-p_2-1）来让nums1的未排序元素不被覆盖。

class Solution {
  public:
    void merge(vector<int> &nums1, int m, vector<int> &nums2, int n) {
        int i = m - 1, j = n - 1, cur = m + n - 1;
        while (i >= 0 && j >= 0) {
            nums1[cur--] = nums1[i] >= nums2[j] ? nums1[i--] : nums2[j--];
        }
        while (i >= 0) {
            nums1[cur--] = nums1[i--];
        }
        while (j >= 0) {
            nums1[cur--] = nums2[j--];
        }
    }
};
Copyright © 2023-2024 Allen Yuan. All rights reserved. RSS