首页 > 其他 > 详细

LeetCode Triangle

时间:2014-03-21 09:33:51      阅读:337      评论:0      收藏:0      [点我收藏+]
bubuko.com,布布扣
class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
        if (!triangle.size() || !triangle[0].size()) return 0;
        
        int rows = triangle.size();
        int *ra = new int[rows];
        int *rb = new int[rows];
        int *tmp= NULL;
        int L, R;
        
        ra[0] = triangle[0][0];
        for (int i=1; i<rows; i++) {
            vector<int>& row = triangle[i];
            for (int j=0; j<=i; j++) {
                L = (j - 1) >= 0 ? ra[j-1] : INT_MAX;
                R = (j != i) ? ra[j] : INT_MAX;
                rb[j] = ((L < R) ? L : R) + row[j];
            }
            tmp = ra, ra = rb, rb = tmp;
        }
        
        int sum = INT_MAX;
        for (int i=0; i<rows; i++) {
            if (ra[i] < sum) sum = ra[i];
        }
        
        delete[] ra;
        delete[] rb;
        return sum;   
    }
};
bubuko.com,布布扣

这里使用了两个数组,如果入参允许改变的话可以直接在其上进行修改而不用其他额外空间,提交了一下也是可以。

LeetCode Triangle,布布扣,bubuko.com

LeetCode Triangle

原文:http://www.cnblogs.com/lailailai/p/3615032.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!