网站建设和维护采购协议,网络seo排名,宜春企业网站的建设,在58做网站推广有效果吗目录 三、滑动窗口
30. 长度最小的子数组 ②
31. 无重复字符的最长子串 ②
32. 串联所有单词的子串 ③
33. 最小覆盖子串 ③
四、矩阵
34. 有效的数独 ②
35. 螺旋矩阵 ②
36. 旋转图像 ②
37. 矩阵置零 ②
38. 生命游戏 ② 三、滑动窗口
30. 长度最小的子数组 ② 给…目录 三、滑动窗口
30. 长度最小的子数组 ②
31. 无重复字符的最长子串 ②
32. 串联所有单词的子串 ③
33. 最小覆盖子串 ③
四、矩阵
34. 有效的数独 ②
35. 螺旋矩阵 ②
36. 旋转图像 ②
37. 矩阵置零 ②
38. 生命游戏 ② 三、滑动窗口
30. 长度最小的子数组 ② 给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl1, ..., numsr-1, numsr] 并返回其长度。如果不存在符合条件的子数组返回 0 。 示例 1
输入target 7, nums [2,3,1,2,4,3]
输出2
解释子数组 [4,3]是该条件下的长度最小的子数组。示例 2
输入target 4, nums [1,4,4]
输出1示例 3
输入target 11, nums [1,1,1,1,1,1,1,1]
输出0提示
1 target 1091 nums.length 1051 nums[i] 105 力扣题解. - 力扣LeetCode
方法1时间超时通过15/18 public int minSubArrayLen(int target, int[] nums) {int min nums.length 1;for (int i 0; i nums.length; i) {int sum 0;int left i;sum nums[left];int right i 1;while (right nums.length sum target){sum nums[right];right;}if (sum target min right - left){min right - left;}}return min nums.length 1? 0 : min;}
方法2(0ms) public int minSubArrayLen(int target, int[] nums) {int l 0, r 0;int n nums.length;int sum 0;while(r n sum target)sum nums[r];if(r n)if (sum target)return 0;else{while(sum target)sum - nums[l];}while(r n){if(sum target) sum nums[r];sum - nums[l];}if(sum target) return r-l1;return r -l;}
方法3 public int minSubArrayLen(int target, int[] nums) {int lo 0, hi 0, sum 0, min Integer.MAX_VALUE;while (hi nums.length) {sum nums[hi];while (sum target) {min Math.min(min, hi - lo);sum - nums[lo];}}return min Integer.MAX_VALUE ? 0 : min;} 方法42ms public int minSubArrayLen(int target, int[] nums) {int left 0;int res Integer.MAX_VALUE;int add 0;for (int right 0; right nums.length; right) {add nums[right];while (add target) {res Math.min(res, right - left 1);add - nums[left];left;}}return res nums.length ? 0 : res;} 31. 无重复字符的最长子串 ② 给定一个字符串 s 请你找出其中不含有重复字符的 最长子串 的长度。 示例 1:
输入: s abcabcbb
输出: 3
解释: 因为无重复字符的最长子串是 abc所以其长度为 3。示例 2:
输入: s bbbbb
输出: 1
解释: 因为无重复字符的最长子串是 b所以其长度为 1。示例 3:
输入: s pwwkew
输出: 3
解释: 因为无重复字符的最长子串是 wke所以其长度为 3。请注意你的答案必须是 子串 的长度pwke 是一个子序列不是子串。提示
0 s.length 5 * 104s 由英文字母、数字、符号和空格组成 方法17ms public static int lengthOfLongestSubstring(String s) {TreeSetInteger set new TreeSet();if (s.length() 0){return 0;}else if (s.length() 1){return 1;}else {int left 0;int right 1;while (right s.length()){String substring s.substring(left, right);if (substring.contains(s.charAt(right) )){set.add(right - left);left s.indexOf(s.charAt(right), left) 1;}else {if (right s.length() - 1) {set.add(right - left 1);break;}}right;}return set.last();}}方法2滑动窗口 5ms public int lengthOfLongestSubstring(String s) {if (s.length()0) return 0;HashMapCharacter, Integer map new HashMapCharacter, Integer();int max 0;int left 0;for(int i 0; i s.length(); i ){if(map.containsKey(s.charAt(i))){left Math.max(left,map.get(s.charAt(i)) 1);}map.put(s.charAt(i),i);max Math.max(max,i-left1);}return max;}作者powcai
链接https://leetcode.cn/problems/longest-substring-without-repeating-characters/solutions/3982/hua-dong-chuang-kou-by-powcai/32. 串联所有单词的子串 ③
33. 最小覆盖子串 ③
四、矩阵
34. 有效的数独 ② 请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。请参考示例图 注意
一个有效的数独部分已被填充不一定是可解的。只需要根据以上规则验证已经填入的数字是否有效即可。空白格用 . 表示。 示例 1 输入board
[[5,3,.,.,7,.,.,.,.]
,[6,.,.,1,9,5,.,.,.]
,[.,9,8,.,.,.,.,6,.]
,[8,.,.,.,6,.,.,.,3]
,[4,.,.,8,.,3,.,.,1]
,[7,.,.,.,2,.,.,.,6]
,[.,6,.,.,.,.,2,8,.]
,[.,.,.,4,1,9,.,.,5]
,[.,.,.,.,8,.,.,7,9]]
输出true示例 2
输入board
[[8,3,.,.,7,.,.,.,.]
,[6,.,.,1,9,5,.,.,.]
,[.,9,8,.,.,.,.,6,.]
,[8,.,.,.,6,.,.,.,3]
,[4,.,.,8,.,3,.,.,1]
,[7,.,.,.,2,.,.,.,6]
,[.,6,.,.,.,.,2,8,.]
,[.,.,.,4,1,9,.,.,5]
,[.,.,.,.,8,.,.,7,9]]
输出false
解释除了第一行的第一个数字从 5 改为 8 以外空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。 提示
board.length 9board[i].length 9board[i][j] 是一位数字1-9或者 . 方法1 public static boolean isValidSudoku(char[][] board) {String[] rows new String[9];String[] columns new String[9];String[] areas new String[9];for (int i 0; i 9; i) {if (rows[i] null){rows[i] a;}for (int j 0; j 9; j) {if (columns[j] null){columns[j] a;}if (rows[i].contains(board[i][j] )){return false;}else if (board[i][j] ! . !rows[i].contains(board[i][j] )){rows[i] board[i][j];}if (columns[j].contains(board[i][j] )){return false;}else if (board[i][j] ! . !columns[j].contains(board[i][j] )){columns[j] board[i][j];}int row i / 3; // 0 1 2int column j / 3; //0 1 2int area row * 3 column;if (areas[area] null){areas[area] a;}if (areas[area].contains(board[i][j] )){return false;}else if (board[i][j] ! . !areas[area].contains(board[i][j] )){areas[area] board[i][j];}}}return true;}
方法20ms public boolean isValidSudoku(char[][] board) {short[] rows new short[9];short[] cols new short[9];short[] squares new short[9];for (int i 0; i 9; i) {for (int j 0; j 9; j) {if (board[i][j] ! .) {short value (short)(1 (board[i][j] - 0));int boxNum i / 3 * 3 j / 3;if ((rows[i] value) ! 0 || (cols[j] value) ! 0 || (squares[boxNum] value) ! 0) {return false;}rows[i] | value;cols[j] | value;squares[boxNum] | value;}}}return true;}
方法31ms public boolean isValidSudoku(char[][] board) {int[] rows new int[9];int[] cols new int[9];int[] subboxes new int[9];for (int i 0; i 9; i) {for (int j 0; j 9; j) {char c board[i][j];if (c ! .) {int x (1 (c - 1));if ((rows[i] x) ! 0) {return false;} else {rows[i] | x;}if ((cols[j] x) ! 0) {return false;} else {cols[j] | x;}if ((subboxes[i / 3 * 3 j / 3] x) ! 0) {return false;} else {subboxes[i / 3 * 3 j / 3] | x;}}}}return true;}
方法42ms public boolean isValidSudoku(char[][] board) { int[][] row new int[9][9]; // 行int[][] columns new int[9][9]; // 列int[][][] a new int[3][3][9];for (int i 0; i 9; i) {SetCharacter set new HashSet();for (int j 0; j 9; j) {char c board[i][j];if (c ! .) {row[i][c - 49];columns[j][c - 49];a[i / 3][j / 3][c - 49];if (row[i][c - 49] 1 || columns[j][c - 49] 1 || a[i / 3][j / 3][c - 49] 1) {return false;}}}}return true;} 35. 螺旋矩阵 ② 给你一个 m 行 n 列的矩阵 matrix 请按照 顺时针螺旋顺序 返回矩阵中的所有元素。 示例 1 输入matrix [[1,2,3],[4,5,6],[7,8,9]]
输出[1,2,3,6,9,8,7,4,5]示例 2 输入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.lengthn matrix[i].length1 m, n 10-100 matrix[i][j] 100 方法10ms public static ListInteger spiralOrder(int[][] matrix) {int[][] path new int[matrix.length][matrix[0].length];int step 0;ArrayListInteger list new ArrayList();int row 0;int col 0;int direct 0;while (step matrix.length * matrix[0].length){list.add(matrix[row][col]);path[row][col] 1;if (direct 0){col;if (col matrix[0].length || path[row][col] 1){direct 1;col--;row;}}else if (direct 1){row;if (row matrix.length || path[row][col] 1){direct 2;row--;col--;}}else if (direct 2){col--;if (col -1 || path[row][col] 1){direct 3;col;row--;}}else {row--;if (row 0 || path[row][col] 1){direct 0;row;col;}}step;}return list;}
方法20ms public ListInteger spiralOrder(int[][] matrix) {int m matrix.length, n matrix[0].length;ListInteger res new ArrayList();int u 0, d m - 1, l 0, r n - 1;while (true) {for (int i l; i r; i ) res.add(matrix[u][i]);if (u d) break;for (int i u; i d; i ) res.add(matrix[i][r]);if (--r l) break;for (int i r; i l; i --) res.add(matrix[d][i]);if (--d u) break;for (int i d; i u; i --) res.add(matrix[i][l]);if (l r) break;}return res; } 36. 旋转图像 ② 给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。 示例 1 输入matrix [[1,2,3],[4,5,6],[7,8,9]]
输出[[7,4,1],[8,5,2],[9,6,3]]示例 2 输入matrix [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]提示
n matrix.length matrix[i].length1 n 20-1000 matrix[i][j] 1000
方法10ms public static void rotate(int[][] matrix) {int n matrix.length;int row 0;int col n - 1;int index 0;while (row col){while (row index col) {int leftUp matrix[row][row index];int rightUp matrix[row index][col];int rightDown matrix[col][col - index];int leftDown matrix[col - index][row];matrix[row][row index] leftDown;matrix[row index][col] leftUp;matrix[col][col - index] rightUp;matrix[col - index][row] rightDown;index;}index 0;row;col--;}}37. 矩阵置零 ② 给定一个 m x n 的矩阵如果一个元素为 0 则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。 示例 1 输入matrix [[1,1,1],[1,0,1],[1,1,1]]
输出[[1,0,1],[0,0,0],[1,0,1]]示例 2 输入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.lengthn matrix[0].length1 m, n 200-231 matrix[i][j] 231 - 1 进阶
一个直观的解决方案是使用 O(mn) 的额外空间但这并不是一个好的解决方案。一个简单的改进方案是使用 O(m n) 的额外空间但这仍然不是最好的解决方案。你能想出一个仅使用常量空间的解决方案吗 方法1 public void setZeroes(int[][] matrix) {TreeSetInteger rowSet new TreeSet();TreeSetInteger columnSet new TreeSet();for (int i 0; i matrix.length; i) {for (int j 0; j matrix[0].length; j) {if (matrix[i][j] 0){rowSet.add(i);columnSet.add(j);}}}for (int i 0; i matrix.length; i) {if (rowSet.contains(i)){Arrays.fill(matrix[i], 0);}}for (int i 0; i matrix[0].length; i) {if (columnSet.contains(i)){for (int j 0; j matrix.length; j) {matrix[j][i] 0;}}}}
方法2 public void setZeroes(int[][] matrix) {int m matrix.length;int n matrix[0].length;// 统计行列是否需要置为0 空间复杂度 O(mn)boolean[] zeroRow new boolean[m];boolean[] zeroCol new boolean[n];for(int i 0; i m; i) {for(int j 0; j n; j) {if(matrix[i][j] 0){zeroRow[i] true;zeroCol[j] true;}}}for(int i 0; i m; i) {for(int j 0; j n; j) {if(zeroRow[i] || zeroCol[j]) {matrix[i][j] 0;}}}} 38. 生命游戏 ② 根据 百度百科 生命游戏 简称为 生命 是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。
给定一个包含 m × n 个格子的面板每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态 1 即为 活细胞 live或 0 即为 死细胞 dead。每个细胞与其八个相邻位置水平垂直对角线的细胞都遵循以下四条生存定律
如果活细胞周围八个位置的活细胞数少于两个则该位置活细胞死亡如果活细胞周围八个位置有两个或三个活细胞则该位置活细胞仍然存活如果活细胞周围八个位置有超过三个活细胞则该位置活细胞死亡如果死细胞周围正好有三个活细胞则该位置死细胞复活
下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 board 的当前状态返回下一个状态。 示例 1 输入board [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
输出[[0,0,0],[1,0,1],[0,1,1],[0,1,0]]示例 2 输入board [[1,1],[1,0]]
输出[[1,1],[1,1]]提示
m board.lengthn board[i].length1 m, n 25board[i][j] 为 0 或 1 进阶
你可以使用原地算法解决本题吗请注意面板上所有格子需要同时被更新你不能先更新某些格子然后使用它们的更新后的值再更新其他格子。本题中我们使用二维数组来表示面板。原则上面板是无限的但当活细胞侵占了面板边界时会造成问题。你将如何解决这些问题 方法10ms public static void gameOfLife(int[][] board) {int[][] map new int[board.length][board[0].length];for (int i 0; i board.length; i) {for (int j 0; j board[0].length; j) {int row Math.max(i - 1, 0);int col Math.max(j - 1, 0);int src board[i][j];int count 0;while (row board.length col board[0].length){count board[row][col];col;if (col j 2 || col board[0].length){row;col Math.max(j - 1, 0);}if (row i 2 || row board.length){break;}}count - src;if (src 1 count 1) {map[i][j] 0;}else if (src 1 (count 2 || count 3)){map[i][j] 1;}else if (src 1 count 3){map[i][j] 0;}else if (src 0 count 3){map[i][j] 1;}}}
// board map;
// for (int[] ints : board) {
// System.out.println(Arrays.toString(ints));
// }for (int i 0; i board.length; i) {for (int j 0; j board[0].length; j) {board[i][j] map[i][j];}}}
