LeetCode刷题:贪心、分治、回溯和动态规划

几种算法思想必知必会的代码实现

回溯

  • 利用回溯算法求解八皇后问题

  • 利用回溯算法求解 0-1 背包问题

分治

  • 利用分治算法求一组数据的逆序对个数

动态规划

  • 0-1 背包问题

  • 最小路径和

  • 编程实现莱文斯坦最短编辑距离

  • 编程实现查找两个字符串的最长公共子序列

  • 编程实现一个数据序列的最长递增子序列

题目

Regular Expression Matching(正则表达式匹配)

思路

不容易想到,直接看官方题解

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean isMatch(String text, String pattern) {
boolean[][] dp = new boolean[text.length() + 1][pattern.length() + 1];
dp[text.length()][pattern.length()] = true;

for (int i = text.length(); i >= 0; i--){
for (int j = pattern.length() - 1; j >= 0; j--){
boolean first_match = (i < text.length() && (pattern.charAt(j) == text.charAt(i) || pattern.charAt(j) == '.'));
if (j + 1 < pattern.length() && pattern.charAt(j+1) == '*'){
dp[i][j] = dp[i][j+2] || first_match && dp[i+1][j];
} else {
dp[i][j] = first_match && dp[i+1][j+1];
}
}
}
return dp[0][0];
}

Minimum Path Sum(最小路径和)

思路

动态规划问题,往左往下选择最小即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int minPathSum(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[] dp = new int[n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0) {
dp[j] = j == 0? grid[i][j] : grid[i][j] + dp[j - 1];
} else if (j == 0) {
dp[j] = grid[i][j] + dp[j];
} else {
dp[j] = grid[i][j] + Math.min(dp[j], dp[j - 1]);
}
}
}
return dp[n - 1];
}

Coin Change(零钱兑换)

思路

找出动态转移方程 dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1),具体可参考官方题解

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int coinChange(int[] coins, int amount) {
int max = amount + 1;
int[] dp = new int[amount + 1];
Arrays.fill(dp, max);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}

Best Time to Buy and Sell Stock(买卖股票的最佳时机)

思路

由于只能交易一次,则从前到后找出最小值,并计算最大利润

代码

1
2
3
4
5
6
7
8
9
10
11
12
public int maxProfit(int[] prices) {
if (prices.length == 0)
return 0;
int maxProfit = 0, minValue = prices[0];
for (int i = 0; i < prices.length; i++){
if (minValue > prices[i])
minValue = prices[i];
else
maxProfit = Math.max(maxProfit, prices[i] - minValue);
}
return maxProfit;
}

Maximum Product Subarray(乘积最大子序列)

思路

  • 遍历数组时计算当前最大值,不断更新
  • imax为当前最大值,则当前最大值为 imax = max(imax * nums[i], nums[i])
  • 由于存在负数,那么会导致最大的变最小的,最小的变最大的。因此还需要维护当前最小值iminimin = min(imin * nums[i], nums[i])
  • 当负数出现时则imaximin进行交换再进行下一步计算
  • 参考链接

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int maxProduct(int[] nums) {
int max = Integer.MIN_VALUE, imax = 1, imin = 1;
for(int i=0; i<nums.length; i++){
if(nums[i] < 0){
int tmp = imax;
imax = imin;
imin = tmp;
}
imax = Math.max(imax*nums[i], nums[i]);
imin = Math.min(imin*nums[i], nums[i]);

max = Math.max(max, imax);
}
return max;
}

Triangle(三角形最小路径和)

思路

动态规划,自底向上进行, dp[j] = nums[i][j] + Math.min(dp[j], dp[j + 1])

代码

1
2
3
4
5
6
7
8
9
public int minimumTotal(List<List<Integer>> triangle) {
int[] dp = new int[triangle.get(triangle.size() - 1).size() + 1];
for (int i = triangle.size() - 1; i >= 0; i--) {
for (int j = 0; j < triangle.get(i).size(); j++) {
dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j + 1]);
}
}
return dp[0];
}

LeetCode刷题:贪心、分治、回溯和动态规划
https://muchen.fun/passages/leetcode-greedy-partition-backtracking-dynamic/
作者
沐晨
发布于
2019年9月9日
许可协议