很多时候不懂事

📝 题目描述 题目链接：螺旋矩阵 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。 示例： 示例 1： 12输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]输出：[1,2,3,6,9,8,7,4,5] 示例 2： 12输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]输出：[1,2,3,4,8,12,11,10,9,5,6,7] 提示： m == matrix.length n == matrix[i].length 1 <= m, n <= 10 -100 <= matrix[i][j] <= 100 💡 解题思路 方法一：模拟 最容易想到的方法就是模拟螺旋矩阵的路径。 初始位置是矩阵的左上角，初始方向是向右。 需要注意一下改变方向的边界条件，当路径超出界限或者进入之前访问过的位置时，顺时针旋转，进入下一个方向。 判断路径是否进入之前访问过的位置需要使用一个与输入矩阵大小相同的辅助矩阵 visited，其中的每个元素表示该位置是...

📝 题目描述 题目链接：矩阵置零 给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。 示例： 示例 1： 12输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]输出：[[1,0,1],[0,0,0],[1,0,1]] 示例 2： 12输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]] 提示： m == matrix.length n == matrix[0].length 1 <= m, n <= 200 -2^31 <= matrix[i][j] <= 2^31 - 1 💡 解题思路 方法一：标记数组 首先我们创建两个bool数组zero_row(m), zero_col(n)，分别代表矩阵的m行和n列。 该bool数组的含义是：如果zero_row[i] = true，那么代表矩阵的第i行需要全置为0；同理如果zero_col[j] = true，那么代...

📝 题目描述 题目链接：缺失的第一个正数 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n)O(n)O(n) 并且只使用常数级别额外空间的解决方案。 示例： 12345678910111213141516171819示例 1：输入：nums = [1,2,0]输出：3解释：范围 [1,2] 中的数字都在数组中。示例 2：输入：nums = [3,4,-1,1]输出：2解释：1 在数组中，但 2 没有。示例 3：输入：nums = [7,8,9,11,12]输出：1解释：最小的正数 1 没有出现。 提示： 1 <= nums.length <= 10^5 -2^31 <= nums[i] <= 2^31 - 1 💡 解题思路 方法一：标记法 如果题目没有空间复杂度要求，那么很容易想到的一个解法就是将数组所有的数放入哈希表（set），随后从 1 开始依次枚举正整数，并判断其是否在哈希表中，这种做法的时间复杂度为 O(N)O(N)O(N)，空间复杂度为 O(N)O(N)O(N)。 上面做法中，耗费空...

📝 题目描述 题目链接：除了自身以外数组的乘积 给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除了 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32位整数 范围内。 请 不要使用除法，且在 O(n)O(n)O(n) 时间复杂度内完成此题。 示例： 1234567891011示例 1:输入: nums = [1,2,3,4]输出: [24,12,8,6]示例 2:输入: nums = [-1,1,0,-3,3]输出: [0,0,9,0,0] 提示： 2 <= nums.length <= 10^5 -30 <= nums[i] <= 30 输入 保证 数组 answer[i] 在 32 位 整数范围内 💡 解题思路 方法一：左右乘积列表 最容易想到的方法，首先构建两个数组 prefix 和 suffix。 其中 prefix[i] 代表 输入数组中 nums[i] 前面所有数字的乘积（不含nums[i]自己）；同理，suffi...

📝 题目描述 题目链接：轮转数组 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。 示例： 123456789101112131415161718示例 1:输入: nums = [1,2,3,4,5,6,7], k = 3输出: [5,6,7,1,2,3,4]解释:向右轮转 1 步: [7,1,2,3,4,5,6]向右轮转 2 步: [6,7,1,2,3,4,5]向右轮转 3 步: [5,6,7,1,2,3,4]示例 2:输入：nums = [-1,-100,3,99], k = 2输出：[3,99,-1,-100]解释: 向右轮转 1 步: [99,-1,-100,3]向右轮转 2 步: [3,99,-1,-100] 提示： 1 <= nums.length <= 10^5 -2^31 <= nums[i] <= 2^31 - 1 0 <= k <= 10^5 💡 解题思路 方法一：使用额外的数组 我们可以使用额外的数组来将每个元素放至正确的位置。用 n 表示数组的长度，我们遍历原数组，将原数组下标...

📝 题目描述 题目链接：合并区间 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start_i, end_i] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。 示例： 12345678910111213141516171819示例 1：输入：intervals = [[1,3],[2,6],[8,10],[15,18]]输出：[[1,6],[8,10],[15,18]]解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].示例 2：输入：intervals = [[1,4],[4,5]]输出：[[1,5]]解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。示例 3：输入：intervals = [[4,7],[1,4]]输出：[[1,7]]解释：区间 [1,4] 和 [4,7] 可被视为重叠区间。 提示： 1 <= intervals.length <= 10^4 intervals[i].length == 2 0 <= start_...

📝 题目描述 题目链接：最大子数组和 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 子数组是数组中的一个连续部分。 子数组：子数组是数组中连续的 非空 元素序列。 示例： 12345678910111213141516示例 1：输入：nums = [-2,1,-3,4,-1,2,1,-5,4]输出：6解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。示例 2：输入：nums = [1]输出：1示例 3：输入：nums = [5,4,-1,7,8]输出：23 提示： 1 <= nums.length <= 10^5 -10^4 <= nums[i] <= 10^4 💡 解题思路 方法一：动态规划 假设数组 nums 的长度为 n，下标是 0 到 n - 1。 我们使用 f(i)f(i)f(i) 表示以第 i 个数结尾的“连续子数组的最大和”，那么很显然我们要求的答案就是： max0≤i≤n−1​f(i)max_{0≤i≤n−1​}{f(i)} max0≤i≤n−1​​f(i)...

📝 题目描述 题目链接：最小覆盖子串 给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的最短窗口子串，使得该子串包含 t 中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串 ""。 测试用例保证答案唯一。 子串：子字符串 是字符串中连续的 非空 字符序列。 示例： 1234567891011121314151617181920示例 1：输入：s = "ADOBECODEBANC", t = "ABC"输出："BANC"解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。示例 2：输入：s = "a", t = "a"输出："a"解释：整个字符串 s 是最小覆盖子串。示例 3:输入: s = "a", t = "aa"输出: ""解释: ...

📝 题目描述 题目链接：滑动窗口最大值 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。 示例： 1234567891011121314151617181920示例 1：输入：nums = [1,3,-1,-3,5,3,6,7], k = 3输出：[3,3,5,5,6,7]解释：滑动窗口的位置 最大值--------------- -----[1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7示例 2：输入：nums = [1], k = 1输出...

📝 题目描述 题目链接：和为 K 的子数组 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。 子数组是数组中元素的连续非空序列。 示例： 1234567891011示例 1：输入：nums = [1,1,1], k = 2输出：2示例 2：输入：nums = [1,2,3], k = 3输出：2 提示： 1 <= nums.length <= 2 * 10^4 -1000 <= nums[i] <= 1000 -10^7 <= k <= 10^7 💡 解题思路 方法一：暴力解法 最容易想到的朴素解法，使用一个二重循环，列举出所有可能的开头i和结尾j，然后计算它们代表的子数组的和，在计算和时，由于我们的内层循环（代表结尾的j）是逐个往后列举的，因此可以令sum += nums[j]而不必重新遍历来计算和，稍微降低了一下复杂度。 方法二：前缀和 + 哈希表优化 方法一中，对于每个开头i，我们要遍历i后的每一个元素来找结尾j。 对于这种：知道最终和k，知道其中一个元素i，求另一个元素j的问题，...