79. 单词搜索

遍历所有起点进行回溯判断。

回溯中,如果不等于或者超过边界返回 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;
}
}

131. 分割回文串

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;
}
}

51. N 皇后

生成棋盘数组,全部填充。然后回溯判断,每次横向遍历放置的位置,如果当前位置可以放,就回溯向下一行判断。当最后一行结束后,收集结果。判断是不是可以放,就判断对角线和列。

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;
}
}

35. 搜索插入位置

左闭右闭区间需要有等于号

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;
}
}

20. 有效的括号

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;
}
}

55. 跳跃游戏

每次计算最大覆盖范围,要么是现在的覆盖范围,要么是自己的覆盖范围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;
}
}

121. 买卖股票的最佳时机

记录历史最低点,每次比较收益。

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;
}
}

153. 寻找旋转排序数组中的最小值

二分查找,第一种情况是中间小于右侧。这说明中间是最小值右侧的元素,因此我们可以忽略二分查找区间的右半部分。如果大于右侧,最小值是说明是最小值左侧的元素,移动左边。

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];
}
}

45. 跳跃游戏 II

不断计算最大的覆盖范围,然后每次当旧的覆盖走完了,再去用新的范围,每次加一,就是把旧的走完再走新的,实现最小更新。

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;
}
}

763. 划分字母区间

  • 统计每一个字符最后出现的位置
  • 从头遍历字符,并更新字符的最远出现下标,如果找到字符最远出现位置下标和当前下标相等了,则找到了分割点
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;
}
}

118. 杨辉三角

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;
}
}

198. 打家劫舍

动态规划记录每天的最大收益,要么是前一天偷了,那就是前一天的收益;要么前一天没偷,偷今天就是前前天 + 今天的收益,每次更新最大值。

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;
}
}

279. 完全平方数

完全背包物品和背包先后都一样,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];
}
}

322. 零钱兑换

完全背包问题,如果背包还是最大值,就返回-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];
}
}

139. 单词拆分

用一个布尔数组 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()];
}
}

300. 最长递增子序列

定义 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;
}
}

152. 乘积最大子数组

它通过维护两个变量 maxEndminEnd,分别表示以当前位置结尾的最大乘积和最小乘积(考虑负数翻转),并在遇到负数时交换两者。每一步更新当前最大乘积,并维护全局最大值 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;
}
}

416. 分割等和子集

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;
}
}

32. 最长有效括号

这道题通过动态规划求解最长有效括号子串。我们定义 dp[i] 表示以第 i 个字符结尾的最长有效括号长度。遍历字符串时,只有遇到 ')' 才可能构成有效括号。两种情况需要处理:

  1. 当前 ')' 前面是 '(':直接构成 '()',则 dp[i] = dp[i - 2] + 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;
}
}

62. 不同路径

使用动态规划 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];
}
}

64. 最小路径和

使用动态规划 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];
}
}

5. 最长回文子串

中心扩展法

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;
}
}

1143. 最长公共子序列

定义 dp[i][j] 表示 text1i 个字符 和 text2j 个字符 的最长公共子序列长度。

  • 如果当前字符相等(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()];
}
}

72. 编辑距离

状态转移:

  1. 初始化边界:
    • dp[i][0] = i:把 word1[0..i-1] 变成空串,需要删掉 i 个字符。
    • dp[0][j] = j:把空串变成 word2[0..j-1],需要插入 j 个字符。
  2. 递推逻辑:
    • 如果当前字符相等: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];
}
}

136. 只出现一次的数字

任何数和 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;
}
}

169. 多数元素

它的核心思想是:
“多数元素的出现次数比其他所有元素出现次数之和还多”

所以我们可以用一个 计数器(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;
}
}

73. 矩阵置零

  1. 先扫描第一行和第一列,判断它们自己是否包含 0,分别用两个布尔变量 flagRow0flagCol0 记录。
  2. 从第二行第二列开始遍历矩阵,如果某个元素是 0,就把它所在的行的第一个元素和列的第一个元素设为 0(即在第一行和第一列打标记)。
  3. 再从第二行第二列开始遍历矩阵,根据第一行或第一列的标记来置 0
  4. 最后,根据第一步记录的两个布尔变量,如果第一行或第一列原本就有 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;
}
}
}
}

155. 最小栈

用一个额外的辅助栈,入栈时候辅助栈入栈一个新元素和栈顶元素的最小值,出栈两个栈都要出。

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();
}
}

/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(val);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
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;
}
}

/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(val);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/

394. 字符串解码

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 可能会是n位数,为了方便后续统一x10处理,必须归零
num = 0;
res = new StringBuilder(); // res 也要重置
} 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();
}
}

394. 字符串解码

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 可能会是n位数,为了方便后续统一x10处理,必须归零
num = 0;
res = new StringBuilder(); // res 也要重置
} 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();
}
}

739. 每日温度

用一个最小栈,储存对应的索引,如果发现有比栈顶元素大的,就计算索引,然后出栈,直到比栈顶小了为止。完成后新元素入栈。

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;
}
}

84. 柱状图中最大的矩形

单调栈,递增,遇到比栈顶小的时候开始处理。

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;
}
}

215. 数组中的第K个最大元素

想保大,用小堆;想保小,用大堆
✅ 判断条件是:新元素比堆顶“更优”时就替换

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();
}
}

347. 前 K 个高频元素

想保大,就用小堆;想保小,就用大堆。

小顶堆,维护 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);
}

// int[] 的第一个元素代表数组的值,第二个元素代表了该值出现的次数
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;
}
}

74. 搜索二维矩阵

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;
}
}