几种算法思想必知必会的代码实现
回溯
利用回溯算法求解八皇后问题
利用回溯算法求解 0-1
背包问题
分治
动态规划
0-1
背包问题
最小路径和
编程实现莱文斯坦最短编辑距离
编程实现查找两个字符串的最长公共子序列
编程实现一个数据序列的最长递增子序列
题目
思路
不容易想到,直接看官方题解
代码
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]; }
|
思路
动态规划问题,往左往下选择最小即可
代码
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]; }
|
思路
找出动态转移方程 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]; }
|
思路
由于只能交易一次,则从前到后找出最小值,并计算最大利润
代码
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; }
|
思路
- 遍历数组时计算当前最大值,不断更新
- 令
imax
为当前最大值,则当前最大值为 imax = max(imax * nums[i], nums[i])
- 由于存在负数,那么会导致最大的变最小的,最小的变最大的。因此还需要维护当前最小值
imin
,imin = min(imin * nums[i], nums[i])
- 当负数出现时则
imax
与imin
进行交换再进行下一步计算 - 参考链接
代码
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; }
|
思路
动态规划,自底向上进行, 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]; }
|