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

本文最后更新于:1 年前

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

回溯

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

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

分治

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

动态规划

  • 0-1 背包问题

  • 最小路径和

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

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

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

题目

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

思路

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

代码

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(最小路径和)

思路

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

代码

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),具体可参考官方题解

代码

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(买卖股票的最佳时机)

思路

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

代码

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进行交换再进行下一步计算
  • 参考链接

代码

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])

代码

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

本博客所有文章除特别声明外,均采用 CC BY-SA 3.0协议 。转载请注明出处!


欢迎关注我的公众号😘