LC120—三角形最小路径和

LC120---三角形最小路径和
强烈推介IDEA2020.2破解激活,IntelliJ IDEA 注册码,2020.2 IDEA 激活码

120. 三角形最小路径和

难度中等701

给定一个三角形 triangle ,找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标 i ,那么下一步可以移动到下一行的下标 ii + 1

示例 1:

输入:triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出:11
解释:如下面简图所示:
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。

方法一:利用二叉树的递归的进行比遍历

时间复杂度的高超时

/**
 * 递归 二叉树
 * 超时
 */
class Solution1 {
    int row;

    public int minimumTotal(List<List<Integer>> triangle) {
        row = triangle.size();
        return helper(0, 0, triangle);

    }

    private int helper(int level, int c, List<List<Integer>> triangle) {
        if (level == row - 1) {
            return triangle.get(level).get(c);
        }
        int left = helper(level + 1, c, triangle);
        int right = helper(level + 1, c + 1, triangle);
        return Math.min(right, left) + triangle.get(level).get(c);
    }
}

方法2:在方法1上进行优化,将每次遍历到的数据存储下来,避免多次遍历

  int row;

    /**
     * 递归
     *
     * @param triangle
     * @return
     */
    public int minimumTotal(List<List<Integer>> triangle) {
        row = triangle.size();
        return helper(0, 0, triangle, new HashMap());
    }

    private int helper(int level, int c, List<List<Integer>> triangle, Map<String, Integer> map) {
        if (level == row - 1) {
            return triangle.get(level).get(c);
        }
        String key = level + "-" + c;
        if (map.containsKey(key)) {
            return map.get(key);
        }
        int left = helper(level + 1, c, triangle, map);
        int right = helper(level + 1, c + 1, triangle, map);
        int sum = Math.min(right, left) + triangle.get(level).get(c);
        map.put(key, sum);
        return sum;
    }

方法3:二维数组进行动态规划

注意: 第一开始时利用倒数第二行开始遍历的也即是第一个循环歪为:for (int i = triangle.size() - 1; i >= 0; i++) {

    /**
     * 二维数组 动态规划
     *
     * @param triangle
     * @return
     */
    public int minimumTotal1(List<List<Integer>> triangle) {
        //定义一个二维数组
        int[][] dp = new int[triangle.size() + 1][triangle.size() + 1];
        //从最后一行也就是     倒数第二行开始计算
        // dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle.get(i).get(j);
        for (int i = triangle.size() - 1; i >= 0; i++) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                //递归公式
                dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle.get(i).get(j);
            }
        }
        return dp[0][0];
    }

方法4:在方法3的基础上进行优化改为一维数组,将缩减空间复杂度的应用

    /** * 一维数组 动态规划 * * @param triangle * @return */
    public int minimumTotal2(List<List<Integer>> triangle) {
   
        //定义一个二维数组
        int[] dp = new int[triangle.size() + 1];
        //从最后一行
        for (int i = triangle.size() - 1; i >= 0; i--) {
   
            for (int j = 0; j < triangle.get(i).size(); j++) {
   
                //递归公式
                dp[j] = Math.min(dp[j],dp[j+1]) + triangle.get(i).get(j);
            }
        }
        return dp[0];
    }

package com.nie.o2;/* * *@auth wenzhao *@date 2021/2/21 16:41 */

import com.sun.crypto.provider.HmacPKCS12PBESHA1;

import java.util.HashMap;
import java.util.List;
import java.util.Map;


public class LEE120 {
   


    int row;

    /** * 递归 * * @param triangle * @return */
    public int minimumTotal(List<List<Integer>> triangle) {
   
        row = triangle.size();
        return helper(0, 0, triangle, new HashMap());
    }

    private int helper(int level, int c, List<List<Integer>> triangle, Map<String, Integer> map) {
   
        if (level == row - 1) {
   
            return triangle.get(level).get(c);
        }
        String key = level + "-" + c;
        if (map.containsKey(key)) {
   
            return map.get(key);
        }
        int left = helper(level + 1, c, triangle, map);
        int right = helper(level + 1, c + 1, triangle, map);
        int sum = Math.min(right, left) + triangle.get(level).get(c);
        map.put(key, sum);
        return sum;
    }


    /** * 二维数组 动态规划 * * @param triangle * @return */
    public int minimumTotal1(List<List<Integer>> triangle) {
   
        //定义一个二维数组
        int[][] dp = new int[triangle.size() + 1][triangle.size() + 1];
        //从最后一行也就是 倒数第二行开始计算
        // dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle.get(i).get(j);
        for (int i = triangle.size() - 1; i >= 0; i++) {
   
            for (int j = 0; j < triangle.get(i).size(); j++) {
   
                //递归公式
                dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle.get(i).get(j);
            }
        }
        return dp[0][0];
    }

    /** * 一维数组 动态规划 * * @param triangle * @return */
    public int minimumTotal2(List<List<Integer>> triangle) {
   
        //定义一个二维数组
        int[] dp = new int[triangle.size() + 1];
        //从最后一行
        for (int i = triangle.size() - 1; i >= 0; i--) {
   
            for (int j = 0; j < triangle.get(i).size(); j++) {
   
                //递归公式
                dp[j] = Math.min(dp[j],dp[j+1]) + triangle.get(i).get(j);
            }
        }
        return dp[0];
    }
}

/** * 递归 二叉树 * 超时 */
class Solution1 {
   
    int row;

    public int minimumTotal(List<List<Integer>> triangle) {
   
        row = triangle.size();
        return helper(0, 0, triangle);

    }

    private int helper(int level, int c, List<List<Integer>> triangle) {
   
        if (level == row - 1) {
   
            return triangle.get(level).get(c);
        }
        int left = helper(level + 1, c, triangle);
        int right = helper(level + 1, c + 1, triangle);
        return Math.min(right, left) + triangle.get(level).get(c);
    }
}
本文来源面相薪水编程,由javajgs_com转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/8175

发表评论