遍历所有起点进行回溯判断。
回溯中，如果不等于或者超过边界返回 false；当长度等于要求长度，返回 true。回溯每层向四个方向判断，回溯先把当前位置给标记为已访问。
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 class Solution { public boolean exist (char [][] board, String word) { for (int i = 0 ; i < board.length; i++) { for (int j = 0 ; j < board[0 ].length; j++) { if (board[i][j] == word.charAt(0 )) { if (backtracing(0 , i, j, board, word)) { return true ; } } } } return false ; } public boolean backtracing (int index, int row, int col, char [][] board, String word) { if (row < 0 || row >= board.length || col < 0 || col >= board[0 ].length || board[row][col] != word.charAt(index)) { return false ; } if (index == word.length() - 1 ) { return true ; } char tmp = board[row][col]; board[row][col] = '#' ; boolean res = backtracing(index + 1 , row - 1 , col, board, word) || backtracing(index + 1 , row + 1 , col, board, word) || backtracing(index + 1 , row, col - 1 , board, word) || backtracing(index + 1 , row, col + 1 , board, word); board[row][col] = tmp; return res; } }
startIndex 用来分割串，然后判断子串是不是回文，是的话就继续搜索。当切割线到末尾就收集结果。
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 class Solution { private List<List<String>> res = new ArrayList <>(); private LinkedList<String> path = new LinkedList <>(); public List<List<String>> partition (String s) { backtracing(0 , s); return res; } public void backtracing (int startIndex, String s) { if (startIndex == s.length()) { res.add(new ArrayList <>(path)); return ; } for (int i = startIndex; i < s.length(); i++) { String str = s.substring(startIndex, i + 1 ); if (check(str.toCharArray())) { path.addLast(str); backtracing(i + 1 , s); path.removeLast(); } } } public boolean check (char [] str) { int i = 0 ; int j = str.length - 1 ; while (i < j) { if (str[i] != str[j]) { return false ; } i++; j--; } return true ; } }
生成棋盘数组，全部填充。然后回溯判断，每次横向遍历放置的位置，如果当前位置可以放，就回溯向下一行判断。当最后一行结束后，收集结果。判断是不是可以放，就判断对角线和列。
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 48 49 50 51 52 53 54 55 56 57 class Solution { private List<List<String>> res = new ArrayList <>(); public List<List<String>> solveNQueens (int n) { char [][] board = new char [n][n]; for (char [] c : board) { Arrays.fill(c, '.' ); } backtracing(0 , board); return res; } public void backtracing (int row, char [][] board) { if (row == board.length) { add2Res(board); return ; } for (int i = 0 ; i < board.length; i++) { if (isValid(row, i,board)) { board[row][i] = 'Q' ; backtracing(row + 1 , board); board[row][i] = '.' ; } } } public List<String> add2Res (char [][] board) { List<String> list = new ArrayList <>(); for (char [] c : board) { list.add(String.valueOf(c)); } res.add(list); return list; } public boolean isValid (int row, int col, char [][] board) { int n = board.length; for (int i = 0 ; i < row; i++) { if (board[i][col] == 'Q' ) { return false ; } } for (int i = row - 1 , j = col - 1 ; i >= 0 && j >= 0 ; i--, j--) { if (board[i][j] == 'Q' ) { return false ; } } for (int i = row - 1 , j = col + 1 ; i >= 0 && j <= n - 1 ; i--, j++) { if (board[i][j] == 'Q' ) { return false ; } } return true ; } }
左闭右闭区间需要有等于号
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public int searchInsert (int [] nums, int target) { int left = 0 , right = nums.length - 1 ; while (left <= right) { int mid = left + ((right - left) >> 1 ); if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { left = mid + 1 ; } else { right = mid - 1 ; } } return right + 1 ; } }
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 class Solution { public boolean isValid (String s) { if (s.length() < 2 ) { return false ; } char [] stack = new char [s.length()]; int index = -1 ; for (char c : s.toCharArray()) { if (c == '(' || c == '{' || c == '[' ) { index++; stack[index] = c; } else { if (index == -1 ) return false ; char top = stack[index]; index--; if (c == ')' && top != '(' ) return false ; if (c == '}' && top != '{' ) return false ; if (c == ']' && top != '[' ) return false ; } } return index == -1 ; } }
每次计算最大覆盖范围，要么是现在的覆盖范围，要么是自己的覆盖范围i + nums[i]，看哪个大。注意 for 的终点是 max。
1 2 3 4 5 6 7 8 9 10 11 12 class Solution { public boolean canJump (int [] nums) { int max = 0 ; for (int i = 0 ; i <= max; i++) { max = Math.max(max, i + nums[i]); if (max >= nums.length - 1 ) { return true ; } } return false ; } }
记录历史最低点，每次比较收益。
1 2 3 4 5 6 7 8 9 10 11 class Solution { public int maxProfit (int [] prices) { int max = 0 ; int min = Integer.MAX_VALUE; for (int price : prices) { min = Math.min(min, price); max = Math.max(max, price - min); } return max; } }
二分查找，第一种情况是中间小于右侧。这说明中间是最小值右侧的元素，因此我们可以忽略二分查找区间的右半部分。如果大于右侧，最小值是说明是最小值左侧的元素，移动左边。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public int findMin (int [] nums) { int left = 0 ; int right = nums.length - 1 ; while (left < right) { int mid = left + (right - left) / 2 ; if (nums[mid] < nums[right]) { right = mid; } else { left = mid + 1 ; } } return nums[right]; } }
不断计算最大的覆盖范围，然后每次当旧的覆盖走完了，再去用新的范围，每次加一，就是把旧的走完再走新的，实现最小更新。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public int jump (int [] nums) { if (nums.length < 2 ) { return 0 ; } int currDistance = 0 ; int res = 0 ; int nextDistance = 0 ; for (int i = 0 ; i < nums.length; i++) { nextDistance = Math.max(nextDistance, i + nums[i]); if (i == currDistance) { res++; currDistance = nextDistance; if (currDistance >= nums.length - 1 ) { break ; } } } return res; } }
统计每一个字符最后出现的位置
从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public List<Integer> partitionLabels (String s) { int [] edge = new int [26 ]; for (int i = 0 ; i < s.length(); i++) { edge[s.charAt(i) - 'a' ] = i; } int index = 0 ; int prev = -1 ; List<Integer> res = new ArrayList <>(); for (int i = 0 ; i < s.length(); i++) { index = Math.max(index, edge[s.charAt(i) - 'a' ]); if (i == index) { res.add(i - prev); prev = i; } } return res; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public List<List<Integer>> generate (int numRows) { List<List<Integer>> dp = new ArrayList <>(); dp.add(Arrays.asList(1 )); for (int i = 1 ; i < numRows; i++) { List<Integer> row = new ArrayList <>(); row.add(1 ); List<Integer> prev = dp.get(i - 1 ); for (int j = 1 ; j < i; j++) { row.add(prev.get(j - 1 ) + prev.get(j)); } row.add(1 ); dp.add(row); } return dp; } }
动态规划记录每天的最大收益，要么是前一天偷了，那就是前一天的收益；要么前一天没偷，偷今天就是前前天 + 今天的收益，每次更新最大值。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public int rob (int [] nums) { if (nums.length <= 1 ) { return nums[0 ]; } int [] dp = new int [nums.length]; dp[0 ] = nums[0 ]; dp[1 ] = Math.max(nums[1 ], dp[0 ]); int res = Math.max(dp[0 ], dp[1 ]); for (int i = 2 ; i < nums.length; i++) { dp[i] = Math.max(dp[i - 2 ] + nums[i], dp[i - 1 ]); res = Math.max(res, dp[i]); } return res; } }
完全背包物品和背包先后都一样，01背包先物品再背包，而且背包倒序遍历。
如果求组合数就是外层for循环遍历物品，内层for遍历背包 。
如果求排列数就是外层for遍历背包，内层for循环遍历物品 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public int numSquares (int n) { int [] dp = new int [n + 1 ]; Arrays.fill(dp, Integer.MAX_VALUE); dp[0 ] = 0 ; for (int i = 1 ; i * i <= n; i++) { for (int j = i * i; j <= n; j++) { dp[j] = Math.min(dp[j - i * i] + 1 , dp[j]); } } return dp[n]; } }
完全背包问题，如果背包还是最大值，就返回-1，不然就返回背包最少的硬币个数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public int coinChange (int [] coins, int amount) { int [] dp = new int [amount + 1 ]; Arrays.fill(dp, Integer.MAX_VALUE); dp[0 ] = 0 ; for (int i = 0 ; i < coins.length; i++) { for (int j = coins[i]; j <= amount; j++) { if (dp[j - coins[i]] != Integer.MAX_VALUE) { dp[j] = Math.min(dp[j - coins[i]] + 1 , dp[j]); } } } return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount]; } }
用一个布尔数组 dp[i] 表示字符串前 i 个字符是否可以被字典中的单词拆分。初始时 dp[0] = true（空字符串可以被拆分）。然后对每个位置 i，遍历字典中的单词，判断当前结尾是否可以匹配某个单词，且前面部分也可以被拆分（dp[i - word.length()] == true）。如果是，就设 dp[i] = true。
最终返回 dp[s.length()]，表示整个字符串是否可以被拆分。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public boolean wordBreak (String s, List<String> wordDict) { boolean [] dp = new boolean [s.length() + 1 ]; dp[0 ] = true ; for (int i = 1 ; i <= s.length(); i++) { for (String word : wordDict) { if (i >= word.length() && dp[i - word.length()] && word.equals(s.substring(i - word.length(), i))){ dp[i] = true ; break ; } } } return dp[s.length()]; } }
定义 dp[i] 表示以第 i 个元素结尾的最长递增子序列的长度。
初始化每个位置的 dp[i] = 1，表示每个元素本身就可以构成一个长度为 1 的递增子序列。
然后对每个元素 nums[i]，向前查找所有比它小的元素 nums[j]（j < i），如果 nums[i] > nums[j]，说明 nums[i] 可以接在以 nums[j] 结尾的子序列后面，更新：dp[i] = Math.max(dp[i], dp[j] + 1);
最终结果是所有 dp[i] 中的最大值，即最长递增子序列的长度。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public int lengthOfLIS (int [] nums) { int [] dp = new int [nums.length + 1 ]; Arrays.fill(dp, 1 ); int res = 1 ; for (int i = 1 ; i < nums.length; i++) { for (int j = 0 ; j < i; j++) { if (nums[i] > nums[j]) { dp[i] = Math.max(dp[i], dp[j] + 1 ); } } res = Math.max(res, dp[i]); } return res; } }
它通过维护两个变量 maxEnd 和 minEnd，分别表示以当前位置结尾的最大乘积和最小乘积（考虑负数翻转），并在遇到负数时交换两者。每一步更新当前最大乘积，并维护全局最大值 res。最终返回的就是所有连续子数组中乘积的最大值。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public int maxProduct (int [] nums) { int res = nums[0 ]; int maxEnd = nums[0 ]; int minEnd = nums[0 ]; for (int i = 1 ; i < nums.length; i++) { int num = nums[i]; if (num < 0 ) { int tmp = maxEnd; maxEnd = minEnd; minEnd = tmp; } maxEnd = Math.max(num, num * maxEnd); minEnd = Math.min(num, num * minEnd); res = Math.max(res, maxEnd); } return res; } }
01背包问题，先计算总和，然后分成一半做为背包的容量。
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 class Solution { public boolean canPartition (int [] nums) { int n = nums.length; int sum = 0 ; for (int num : nums) { sum += num; } if (sum % 2 != 0 ) { return false ; } int amount = sum / 2 ; int [] dp = new int [amount + 1 ]; for (int i = 0 ; i < nums.length; i++) { for (int j = amount; j >= nums[i]; j--) { dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]); } if (dp[amount] == amount) { return true ; } } return dp[amount] == amount; } }
这道题通过动态规划求解最长有效括号子串。我们定义 dp[i] 表示以第 i 个字符结尾的最长有效括号长度。遍历字符串时，只有遇到 ')' 才可能构成有效括号。两种情况需要处理：
当前 ')' 前面是 '('：直接构成 '()'，则 dp[i] = dp[i - 2] + 2。
当前 ')' 前面是 ')'：检查前一段有效子串的前一个字符是否为 '('，若是，则形成嵌套或连接结构，更新为 dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public int longestValidParentheses (String s) { int n = s.length(); if (n < 2 ) return 0 ; int [] dp = new int [n]; int maxLen = 0 ; for (int i = 1 ; i < n; i++) { if (s.charAt(i) == ')' ) { if (s.charAt(i - 1 ) == '(' ) { dp[i] = (i >= 2 ? dp[i - 2 ]: 0 ) + 2 ; } else if (i - dp[i - 1 ] > 0 && s.charAt(i - dp[i - 1 ] - 1 ) == '(' ) { dp[i] = dp[i - 1 ] + 2 + (i - dp[i - 1 ] >= 2 ? dp[i - dp[i - 1 ] - 2 ] : 0 ); } maxLen = Math.max(maxLen, dp[i]); } } return maxLen; } }
使用动态规划 dp[i][j] 表示从起点到位置 (i, j) 的路径数。
初始化第一行和第一列为 1，因为从起点到这些位置只有一条路径。
对于其他位置，路径数等于它上方和左方路径数之和（即只能从上或左走过来）。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public int uniquePaths (int m, int n) { int [][] dp = new int [m][n]; for (int i = 0 ; i < m; i++) { dp[i][0 ] = 1 ; } for (int i = 0 ; i < n; i++) { dp[0 ][i] = 1 ; } for (int i = 1 ; i < m; i++) { for (int j = 1 ; j < n; j++) { dp[i][j] = dp[i - 1 ][j] + dp[i][j - 1 ]; } } return dp[m - 1 ][n - 1 ]; } }
使用动态规划 dp[i][j] 表示从起点到位置 (i, j) 的路径数。
初始化第一行和第一列为 1，因为从起点到这些位置只有一条路径。
对于其他位置，路径数等于它上方和左方路径数之和（即只能从上或左走过来）。
上方和左方的最小路径和加当前的数值就是当前的最小路径和。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public int minPathSum (int [][] grid) { int m = grid.length; int n = grid[0 ].length; int [][] dp = new int [m][n]; dp[0 ][0 ] = grid[0 ][0 ]; for (int i = 1 ; i < m; i++) { dp[i][0 ] = dp[i - 1 ][0 ] + grid[i][0 ]; } for (int i = 1 ; i < n; i++) { dp[0 ][i] = dp[0 ][i - 1 ] + grid[0 ][i]; } for (int i = 1 ; i < m; i++) { for (int j = 1 ; j < n; j++) { dp[i][j] = Math.min(dp[i - 1 ][j], dp[i][j - 1 ]) + grid[i][j]; } } return dp[m - 1 ][n - 1 ]; } }
中心扩展法
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 class Solution { public String longestPalindrome (String s) { int start = 0 , end = 0 ; for (int i = 0 ; i < s.length(); i++) { int len1 = expandAroundCenter(s, i, i); int len2 = expandAroundCenter(s, i, i + 1 ); int len = Math.max(len1, len2); if (len > end - start) { start = i - (len - 1 ) / 2 ; end = i + len / 2 ; } } return s.substring(start, end + 1 ); } public int expandAroundCenter (String s, int left, int right) { while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) { left--; right++; } return right - left - 1 ; } }
定义 dp[i][j] 表示 text1 前 i 个字符 和 text2 前 j 个字符 的最长公共子序列长度。
如果当前字符相等（text1[i-1] == text2[j-1]），说明这个字符可以作为公共子序列的一部分，dp[i][j] = dp[i-1][j-1] + 1。
如果不相等，那就从两个方向找最大值：dp[i][j] = max(dp[i-1][j], dp[i][j-1])，表示跳过一个字符继续匹配。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public int longestCommonSubsequence (String text1, String text2) { int [][] dp = new int [text1.length() + 1 ][text2.length() + 1 ]; for (int i = 1 ; i <= text1.length(); i++) { char char1 = text1.charAt(i - 1 ); for (int j = 1 ; j <= text2.length(); j++) { char char2 = text2.charAt(j - 1 ); if (char1 == char2) { dp[i][j] = dp[i - 1 ][j - 1 ] + 1 ; } else { dp[i][j] = Math.max(dp[i - 1 ][j], dp[i][j - 1 ]); } } } return dp[text1.length()][text2.length()]; } }
✅ 状态转移：
初始化边界：
dp[i][0] = i：把 word1[0..i-1] 变成空串，需要删掉 i 个字符。dp[0][j] = j：把空串变成 word2[0..j-1]，需要插入 j 个字符。
递推逻辑：
如果当前字符相等：word1[i-1] == word2[j-1]dp[i][j] = dp[i-1][j-1]
否则，三种操作取最小：
替换：dp[i-1][j-1] + 1
word2 增加一个元素：dp[i][j-1] + 1
word1 增加一个元素：dp[i-1][j] + 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public int minDistance (String word1, String word2) { int m = word1.length();136. 只出现一次的数字 int n = word2.length(); int [][] dp = new int [m + 1 ][n + 1 ]; for (int i = 1 ; i <= m; i++) { dp[i][0 ] = i; } for (int j = 1 ; j <= n; j++) { dp[0 ][j] = j; } for (int i = 1 ; i <= word1.length(); i++) { for (int j = 1 ; j <= word2.length(); j++) { if (word1.charAt(i - 1 ) == word2.charAt(j - 1 )) { dp[i][j] = dp[i - 1 ][j - 1 ]; } else { dp[i][j] = Math.min(Math.min(dp[i - 1 ][j - 1 ], dp[i][j - 1 ]), dp[i - 1 ][j]) + 1 ; } } } return dp[m][n]; } }
任何数和 0 异或，结果都是本身；任何数和自己异或，结果是 0。
1 2 3 4 5 6 7 8 9 class Solution { public int singleNumber (int [] nums) { int res = 0 ; for (int num : nums) { res ^= num; } return res; } }
它的核心思想是：“多数元素的出现次数比其他所有元素出现次数之和还多” 。
所以我们可以用一个 计数器（count） 去“对抗”其他元素。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public int majorityElement (int [] nums) { int count = 0 ; int majority = 0 ; for (int num : nums) { if (count == 0 ) { majority = num; } if (majority == num) { count++; } else { count--; } } return majority; } }
先扫描第一行和第一列 ，判断它们自己是否包含 0，分别用两个布尔变量 flagRow0 和 flagCol0 记录。从第二行第二列开始遍历矩阵 ，如果某个元素是 0，就把它所在的行的第一个元素和列的第一个元素设为 0（即在第一行和第一列打标记）。再从第二行第二列开始遍历矩阵，根据第一行或第一列的标记来置 0 。
最后，根据第一步记录的两个布尔变量 ，如果第一行或第一列原本就有 0，就将整行或整列全部置 0。
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 48 class Solution { public void setZeroes (int [][] matrix) { int m = matrix.length; int n = matrix[0 ].length; boolean flagCol0 = false ; boolean flagRow0 = false ; for (int i = 0 ; i < m; i++) { if (matrix[i][0 ] == 0 ) { flagCol0 = true ; } } for (int j = 0 ; j < n; j++) { if (matrix[0 ][j] == 0 ) { flagRow0 = true ; } } for (int i = 1 ; i < m; i++) { for (int j = 1 ; j < n; j++) { if (matrix[i][j] == 0 ) { matrix[i][0 ] = 0 ; matrix[0 ][j] = 0 ; } } } for (int i = 1 ; i < m; i++) { for (int j = 1 ; j < n; j++) { if (matrix[i][0 ] == 0 || matrix[0 ][j] == 0 ) { matrix[i][j] = 0 ; } } } if (flagCol0) { for (int i = 0 ; i < m; i++) { matrix[i][0 ] = 0 ; } } if (flagRow0) { for (int j = 0 ; j < n; j++) { matrix[0 ][j] = 0 ; } } } }
用一个额外的辅助栈，入栈时候辅助栈入栈一个新元素和栈顶元素的最小值，出栈两个栈都要出。
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 class MinStack { private Deque<Integer> stack; private Deque<Integer> minStack; public MinStack () { this .stack = new LinkedList <>(); this .minStack = new LinkedList <>(); this .minStack.push(Integer.MAX_VALUE); } public void push (int val) { stack.push(val); minStack.push(Math.min(minStack.peek(), val)); } public void pop () { stack.pop(); minStack.pop(); } public int top () { return stack.peek(); } public int getMin () { return minStack.peek(); } }
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 48 49 50 51 52 class Node { int val, min; Node next; public Node () {} public Node (int val, int min, Node next) { this .val = val; this .min = min; this .next = next; } } class MinStack { Node root; public MinStack () { root = new Node (); root.min = Integer.MAX_VALUE; } public void push (int val) { Node cur = new Node (val, root.min, root.next); root.min = Math.min(root.min, val); root.next = cur; } public void pop () { Node cur = root.next; if (cur.val == root.min){ root.min = cur.min; } root.next = cur.next; } public int top () { return root.next.val; } public int getMin () { return root.min; } }
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 class Solution { public String decodeString (String s) { Deque<Integer> stack_num = new LinkedList <>(); Deque<String> stack_res = new LinkedList <>(); StringBuilder res = new StringBuilder (); int num = 0 ; for (Character x : s.toCharArray()) { if (x == '[' ) { stack_num.push(num); stack_res.push(res.toString()); num = 0 ; res = new StringBuilder (); } else if (x == ']' ) { int cur_num = stack_num.pop(); String last_res = stack_res.pop(); StringBuilder tmp = new StringBuilder (); for (int i = 0 ; i < cur_num; i++) tmp.append(res); res = new StringBuilder (last_res + tmp); } else if (x >= '0' && x <= '9' ) num = num * 10 + (x - '0' ); else res.append(x); } return res.toString(); } }
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 class Solution { public String decodeString (String s) { Deque<Integer> stack_num = new LinkedList <>(); Deque<String> stack_res = new LinkedList <>(); StringBuilder res = new StringBuilder (); int num = 0 ; for (Character x : s.toCharArray()) { if (x == '[' ) { stack_num.push(num); stack_res.push(res.toString()); num = 0 ; res = new StringBuilder (); } else if (x == ']' ) { int cur_num = stack_num.pop(); String last_res = stack_res.pop(); StringBuilder tmp = new StringBuilder (); for (int i = 0 ; i < cur_num; i++) tmp.append(res); res = new StringBuilder (last_res + tmp); } else if (x >= '0' && x <= '9' ) num = num * 10 + (x - '0' ); else res.append(x); } return res.toString(); } }
用一个最小栈，储存对应的索引，如果发现有比栈顶元素大的，就计算索引，然后出栈，直到比栈顶小了为止。完成后新元素入栈。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public int [] dailyTemperatures(int [] temperatures) { int lens = temperatures.length; int [] res = new int [lens]; Deque<Integer> stack = new LinkedList <>(); for (int i = 0 ; i < lens; i++) { while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) { res[stack.peek()] = i - stack.peek(); stack.pop(); } stack.push(i); } return res; } }
单调栈，递增，遇到比栈顶小的时候开始处理。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public int largestRectangleArea (int [] heights) { int [] newHeight = new int [heights.length + 2 ]; System.arraycopy(heights, 0 , newHeight, 1 , heights.length); newHeight[heights.length + 1 ] = 0 ; newHeight[0 ] = 0 ; Stack<Integer> stack = new Stack <>(); stack.push(0 ); int res = 0 ; for (int i = 1 ; i < newHeight.length; i++) { while (newHeight[i] < newHeight[stack.peek()]) { int mid = stack.pop(); int w = i - stack.peek() - 1 ; int h = newHeight[mid]; res = Math.max(res, w * h); } stack.push(i); } return res; } }
✅ 想保大，用小堆；想保小，用大堆 新元素比堆顶“更优”时就替换
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public int findKthLargest (int [] nums, int k) { Queue<Integer> queue = new PriorityQueue <>((a, b) -> a - b); for (int num : nums) { if (queue.size() == k) { if (queue.peek() < num) { queue.poll(); queue.offer(num); } } else { queue.offer(num); } } return queue.poll(); } }
想保大，就用小堆；想保小，就用大堆。
小顶堆，维护 K 个频率大的元素。
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 class Solution { public int [] topKFrequent(int [] nums, int k) { Map<Integer, Integer> map = new HashMap <Integer, Integer>(); for (int num : nums) { map.put(num, map.getOrDefault(num, 0 ) + 1 ); } PriorityQueue<int []> queue = new PriorityQueue <int []>((a, b) -> a[1 ] - b[1 ]); for (Map.Entry<Integer, Integer> entry : map.entrySet()) { int num = entry.getKey(), count = entry.getValue(); if (queue.size() == k) { if (queue.peek()[1 ] < count) { queue.poll(); queue.offer(new int []{num, count}); } } else { queue.offer(new int []{num, count}); } } int [] res = new int [k]; for (int i = 0 ; i < k; ++i) { res[i] = queue.poll()[0 ]; } return res; } }
int x = matrix[mid / n][mid % n];
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public boolean searchMatrix (int [][] matrix, int target) { int m = matrix.length, n = matrix[0 ].length; int low = 0 , high = m * n - 1 ; while (low <= high) { int mid = (high - low) / 2 + low; int x = matrix[mid / n][mid % n]; if (x < target) { low = mid + 1 ; } else if (x > target) { high = mid - 1 ; } else { return true ; } } return false ; } }
