专栏首页米扑专栏【leetcode】Triangle

【leetcode】Triangle

Question:

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

Anwser 1:

class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int rows = triangle.size();
        if(0 == rows) return 0;
        
        int *minSums = new int[rows];
        int *temp = new int[rows];
        
        for(int r = 0; r < rows; r++) {
            vector<int> vec = triangle[r];
            temp[0] = vec[0] + (r > 0 ? minSums[0] : 0);
            for(int i = 1; i < r; i++) {
                temp[i] = vec[i] + min(minSums[i-1], minSums[i]);
            }
            
            if(r > 0) {
                temp[r] = vec[r] + minSums[r-1];
            }
                
            int *tswap = temp;
            temp = minSums;
            minSums = tswap;
        }
        
        int m = minSums[0];
        for(int i = 1; i < rows; i++) 
        {
            if(minSums[i] < m){
                m = minSums[i];
            } 
        }
        
        delete temp;
        delete minSums;
        return m;
    }
};

Anwser 2:  

class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int line = triangle.size();

        for(int i = line -2 ; i >= 0; i--) 
        {
            for(int j = 0; j < triangle[i].size(); j++)
            {
                triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1]);
            }
        }

        return triangle[0][0];
    }
};

Anwser 3:

class Solution {
public:
    
    void run(vector<vector<int> > &triangle, int row, int idx, int curSum, int &minPath)
    {
        if (row == triangle.size())
        {
            minPath = min(minPath, curSum);
            return;
        }
        
        run(triangle, row + 1, idx, curSum + triangle[row][idx], minPath);
        run(triangle, row + 1, idx + 1, curSum + triangle[row][idx], minPath);
    }

    int minimumTotal(vector<vector<int> > &triangle) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int minPath = INT_MAX;
        
        if (triangle.size() == 0) {
            return 0;
        }
        
        run(triangle, 0, 0, 0, minPath);
        
        return minPath;
    }
};

注意点:

1) Judge Small is ok, but Judge Large is error

2) 如果迭代很深的话,容易造成压栈占用内存很高,超出段后会溢出

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【leetcode】Palindrome Partitioning II

    Given a string s, partition s such that every substring of the partition is a pa...

    阳光岛主
  • 【leetcode】Longest Consecutive Sequence

    Given an unsorted array of integers, find the length of the longest consecutive ...

    阳光岛主
  • 【leetcode】Valid Palindrome

    Given a string, determine if it is a palindrome, considering only alphanumeric c...

    阳光岛主
  • 1365 浴火银河星际跳跃

    1365 浴火银河星际跳跃 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 小...

    attack
  • 十种排序算法总结(冒泡、插入、选择、希尔、归并、堆、快速,计数,桶,基数)

    首先声明一下,本文只对十种排序算法做简单总结,并参照一些资料给出自己的代码实现,并没有对某种算法理论讲解,更详细的 了解可以参考以下资料(本人参考): 1、《d...

    s1mba
  • 十种排序算法总结(冒泡、插入、选择、希尔、归并、堆、快速,计数,桶,基数)

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/...

    s1mba
  • 并查集

    ​ 在我们需要判断某一些事物之间是否存在一定的关系的时候,我们最好的办法不是使用图而是使用并查集。因为我们关心的是他们之间是否有关系,而不是关心的他们到底...

    lwen
  • Codeforces Round #542 [Alex Lopashev Thanks-Round] (Div. 2) C. Connect(bfs)

    题目链接:http://codeforces.com/contest/1130/problem/C

    Ch_Zaqdt
  • leetcode 周赛155 | 项目管理之拓扑排序算法

    今天看了下leetcode周赛的题目,没怎么做,第四题是一道Hard题目,看了下题意感觉要用拓扑排序,但是这道题除了依赖关系,还有一个分组的变量,导致这道题处理...

    ACM算法日常
  • 牛客小白月赛11D(分治、RMQ)

    定义一个玄学节点叫做 R,每次操作读入 val ,执行 Insert(R,val)。

    ACM算法日常

扫码关注云+社区

领取腾讯云代金券