LeetCode Hot 100 第8天
1. 73 矩阵置零（记录标识）
链接：题目链接
题解：
题解
时间复杂度O(n*m)：
- 方案1
(空间复杂度O(n + m))：matrix[i][j] = 0，意味着 第i行、第j列所有元素都要置为0；维护能置为0行、列的集合rowSet、columnSet；最后再遍历置0既可- 方案2
(空间复杂度O(1))：能否把上述rowSet、columnSet记录在matrix数组中？- 如果matrix[i][j] = 0，记录在matrix[0][j] = 0、matrix[i][0] = 0（这两个值本身就要置为0），会导致不知道第0行、0列是否需要置为0
- 那么单独用两个变量记录第0列、第0行是否需要 置为0就行了
- 注意：在根据matrix[i][0]、matrix[0][j] = 0 将当前列、当前行置为0的时候，不需要处理第0列、第0行（会影响接下来的遍历），且第0行第0列有单独的变量标识处理
代码：
// 方案1public void setZeroes(int[][] matrix) {// 行 x... 用常数来记录下来// 列 y... 用常数来记录下来int rowLen = matrix.length;int columnLen = matrix[0].length;Set<Integer> rowZeroSet = new HashSet<>(rowLen);Set<Integer> columnZeroSet = new HashSet<>(columnLen);for (int i = 0; i < rowLen; ++ i) {for (int j = 0; j < columnLen; ++ j) {if (matrix[i][j] == 0) {rowZeroSet.add(i);columnZeroSet.add(j);}}}for (Integer index: rowZeroSet) {Arrays.fill(matrix[index], 0);}for (Integer index: columnZeroSet) {for (int i = 0; i < rowLen; ++ i) {matrix[i][index] = 0;}}}// 方案2
class Solution {public void setZeroes(int[][] matrix) {int rowLen = matrix.length;int columnLen = matrix[0].length;boolean rowZeroFlag = false, columnZeroFlag = false;for (int[] value : matrix) {if (value[0] == 0) {columnZeroFlag = true;break;}}for (int i = 0; i < columnLen; ++ i) {if (matrix[0][i] == 0) {rowZeroFlag = true;break;}}for (int i = 1; i < rowLen; ++ i) {for (int j = 1; j < columnLen; ++ j) {if (matrix[i][j] == 0) {matrix[0][j] = 0;matrix[i][0] = 0;}}}for (int i = 1; i < rowLen; ++ i) {if (matrix[i][0] == 0) {Arrays.fill(matrix[i], 0);}}for (int i = 1; i < columnLen; ++ i) {if (matrix[0][i] == 0) {for (int j = 0; j < rowLen; ++ j) {matrix[j][i] = 0;}}}if (columnZeroFlag) {for (int i = 0; i < rowLen; ++ i) {matrix[i][0] = 0;}}if (rowZeroFlag) {for (int i = 0; i < columnLen; ++ i) {matrix[0][i] = 0;}}}
}
2. 54 螺旋矩阵（模拟 + 边界判断）
链接：题目链接
题解：
题解
时间复杂度O(n*m)：
- 按照逆时针转动（左 -> 下 -> 右 -> 上）
- 记录左 -> 下 -> 右 -> 上的边界，维护边界既可
- 注意：如果左 -> 下 -> 右 -> 上，其中一条路走不通的话，就终止循环（例如左 -> 右 -> 上（少了下），往左走完，没办法往下走，往如果直接往右走，那么就会重复记录，如果往上走，也会走不通）
代码：
class Solution {public List<Integer> spiralOrder(int[][] matrix) {int l = 0, r = matrix[0].length - 1, low = 0, hight = matrix.length - 1;List<Integer> ans = new ArrayList<>();while (true) {// 往右走if (l > r) {break;}for (int i = l; i <= r; ++ i) {ans.add(matrix[low][i]);}low ++;// 往下走if (low > hight) {break;}for (int i = low; i <= hight; ++ i) {ans.add(matrix[i][r]);}r --;// 往左走if (l > r) {break;}for (int i = r; i >= l; -- i) {ans.add(matrix[hight][i]);}hight --;// 往上走if (low > hight) {break;}for (int i = hight; i >= low; -- i) {ans.add(matrix[i][l]);}l ++;}return ans;}
}
3. 2461 长度为 K 子数组中的最大和（双指针）
链接：题目链接
题解：
题解
时间复杂度O(n)：
- 维护一个左右指针[l, r]，保证 [l, r]区间内没有重复数字
- 向右移动r指针，如果[l, r]区间内出现过nums[r + 1]数字，那么向右移动l指针，直至[l, r+1]没有重复数字
- 如果[l, r]区间大小 > k，需要向右移动l指针
- 需要维护一个区间和，方便取最大值
代码：
class Solution {public long maximumSubarraySum(int[] nums, int k) {int len = nums.length;Set<Integer> numSet = new HashSet<>();long sum = 0;long ans = 0;for (int i = 0, j = 0; i < len; ++ i) {while (numSet.contains(nums[i])) {sum -= nums[j];numSet.remove(nums[j]);j ++;}numSet.add(nums[i]);sum += nums[i];if (i - j + 1 == k) {ans = Math.max(ans, sum);sum -= nums[j];numSet.remove(nums[j]);j++;}}return ans;}
}
如果对你有帮助，辛苦点个赞，谢谢啦，朋友！！！