首页 > 代码库 > Triangle

Triangle

2024-10-29 13:58:39   208人阅读

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

[java] view plaincopy
  1. <span style="font-size:18px;">public class Solution {  
  2.     public int minimumTotal(List<List<Integer>> triangle) {  
  3.         int num = (triangle.size()+1)*triangle.size()/2;//元素数  
  4.         int L = 1;//i节点所在的层数,i节点的左节点是i + L,右节点是i+L+1  
  5.         int[] train = new int[num];  
  6.         int k = 0;  
  7.         for(int i = 0 ; i < triangle.size() ; i++){  
  8.             for(int j = 0 ; j < triangle.get(i).size();j++){  
  9.                 train[k++] = triangle.get(i).get(j);//将列表转存到数组中，方便处理  
  10.             }  
  11.         }  
  12.         //接下来利用树的深度遍历思想寻找最小值  
  13.         //int min = 0;  
  14.         if(num < 1){//空  
  15.             return 0;  
  16.         }  
  17.         return inorder(train,0,1,0);  
  18.     }  
  19.     public int inorder(int train[],int index, int L,int min){//参数的意义，train为存储数据的数组,index为要访问数组的下标，L是访问数组的层数,min为从父节点传递下来的最小值  
  20.         if(index + L >= train.length){//叶子节点,这棵树是一棵完全二叉树  
  21.             return min + train[index];  
  22.         }else{//非叶子节点,继续向下传播，  
  23.             int left = inorder(train,index + L,L+1,min+train[index]);  
  24.             int right = inorder(train,index + L+1,L+1,min+train[index]);  
  25.             return left>right ? right : left;  
  26.         }  
  27.     }  
  28. }</span>  


时间超时。。。。

观察发现，其实最终这个三角形是一个完全二叉树的形式，所以最先想到使用树的DFS，遍历完之后就找到了。但是使用树遍历的方式时间超时，所以参考网上的思路，使用动态规划算法，有两种调整方式，自顶向下和自底向上。

我采用的是自顶向下的方式。

首先根据的左右节点的概念，我们发现在数组中第i个节点对应的树中的左右节点分别是i+L和i+L+1，L为i节点所在的层次（不是2i和2i+1，这点需要注意，虽说是完全二叉树的形式，但是不同于完全二叉树）。

那么，知道了上面的关系我们也就知道了迭代公式

d[k + i] = d[k + i ] > d[k]+trian[k + i]? d[k]+trian[k+i]: d[k + i ];// i 节点的左节点
d[k + i + 1] = d[k + i + 1] > d[k]+trian[k + i + 1]? d[k]+trian[k + i + 1]: d[k + i + 1];// i 节点的右节点

[java] view plaincopy
  1. <span style="font-size:14px;">public class Solution {  
  2.     public int minimumTotal(List<List<Integer>> triangle) {  
  3.         int num = (triangle.size()+1)*triangle.size()/2;//元素数  
  4.         int level = triangle.size();//层数  
  5.         int L = 1;//i节点所在的层数,i节点的左节点是i + L,右节点是i+L+1  
  6.         int[] trian = new int[num];  
  7.         int k = 0;  
  8.         for(int i = 0 ; i < triangle.size() ; i++){  
  9.             for(int j = 0 ; j < triangle.get(i).size();j++){  
  10.                 trian[k++] = triangle.get(i).get(j);//将列表转存到数组中，方便处理  
  11.             }  
  12.         }  
  13.         if(num < 1){  
  14.             return 0;  
  15.         }  
  16.         int[] d = new int[num];//记录每一个元素对应的最小路径长  
  17.         for(int i = 0; i < num ; i ++){  
  18.             d[i] = Integer.MAX_VALUE;  
  19.         }  
  20.         k = 0;  
  21.         d[0] = trian[k];  
  22.         for(int i = 1 ; i < level ; i ++){  
  23.             for(int j = 0 ; j < i ; j ++){  
  24.                 d[k + i] = d[k + i ] > d[k]+trian[k + i]? d[k]+trian[k+i]: d[k + i ];//左节点  
  25.                 d[k + i + 1] = d[k + i + 1] > d[k]+trian[k + i + 1]? d[k]+trian[k + i + 1]: d[k + i + 1];//右节点  
  26.                 k++;  
  27.             }  
  28.         }  
  29.         int min = d[num-1];  
  30.         for(int i = num - 2 ; i > num - 1 - level; i --){  
  31.             if(min > d[i]){  
  32.                 min = d[i];  
  33.             }  
  34.         }  
  35.         return min;  
  36.     }  
  37. }</span>  
Runtime: 239 ms

Triangle


联系
我们