为什么oj.leetcode上面的triangle那道题总是超时 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

为什么oj.leetcode上面的triangle那道题总是超时

为什么oj.leetcode上面的triangle那道题总是超时# JobHunting - 待字闺中

m*n2013-09-26 07:09

1 楼

写了一个程序，但是系统总是用它算160+阶的triangle，然后显示Time Limit
Exceeded。
反复修改了，实在没办法再省时间了，而且还要求内存空间O(n).
请问，有人的程序能通过吗？
这是第一次在上面练习，不知道怎么算通过。

n*d2013-09-26 07:09

2 楼

确定没有死循环？

【在 m*****n 的大作中提到】

: 写了一个程序，但是系统总是用它算160+阶的triangle，然后显示Time Limit
: Exceeded。
: 反复修改了，实在没办法再省时间了，而且还要求内存空间O(n).
: 请问，有人的程序能通过吗？
: 这是第一次在上面练习，不知道怎么算通过。

m*n2013-09-26 07:09

3 楼

应该没有，现在改了code，有出现runtime error，算了还是先在机器上调试一下吧。

j*i2013-09-26 07:09

4 楼

设从(0, 0)到(i, j)的最小和为P(i, j)
P(i, j) = min(P(i - 1, j), P(i - 1, j - 1)) + triangle[i][j] （除了边界上的
点）
这样知道上一行的P值，就可以推出下一行的P值，找出最后一行P值的最小值返回即可。
时间O(n^2),空间O(n)
class Solution {
public:
int minimumTotal(vector > &triangle) {
int n = triangle.size();
int * p = new int[n]();
int * q = new int[n]();
for (int i = 0; i < n; ++i) {
p[0] = q[0] + triangle[i][0];
for (int j = 1; j < i + 1; ++j) {
if (j == i)
p[j] = q[j - 1] + triangle[i][j];
else
p[j] = min(q[j -1], q[j]) + triangle[i][j];
}
{int * t = p; p = q; q = t;}
}
int r = INT_MAX;
for (int i = 0; i < n; ++i)
r = min(r, q[i]);
delete[] p, q;
return r;
}
};

S*J2013-09-26 07:09

5 楼

int triangle(vector> &triangle)
{
for(int i=triangle.size()-2; i>=0; i--)
{
for(int j=0; jtriangle[i][j]+=std::min(triangle[i+1][j], triangle[i+1][j+1]);
}

return triangle.empty()? 0 : triangle[0][0];
}

m*n2013-09-26 07:09

6 楼

3x，受到启发，已经通过了，为了省时间，把你的循环里的不必要的if去掉了。
class Solution {
public:
int minimumTotal(vector > &triangle) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int depth = triangle.size();
if(!depth) return 0;
else if(depth==1) return triangle[0][0];
vector curr_min(depth, 0), pre_min(depth,0);
pre_min[0] = triangle[0][0];
for(int i=1; i{
curr_min[0] = pre_min[0]+triangle[i][0];
curr_min[i] = pre_min[i-1]+triangle[i][i];
for(int j=1; j]) + triangle[i][j];
pre_min = curr_min;
}

int min=999999;
for(int i=0; iif(min>curr_min[i]) min = curr_min[i];

return min;
}//minimumTotal
};

可。

【在 j******i 的大作中提到】

: 设从(0, 0)到(i, j)的最小和为P(i, j)
: P(i, j) = min(P(i - 1, j), P(i - 1, j - 1)) + triangle[i][j] （除了边界上的
: 点）
: 这样知道上一行的P值，就可以推出下一行的P值，找出最后一行P值的最小值返回即可。
: 时间O(n^2),空间O(n)
: class Solution {
: public:
: int minimumTotal(vector > &triangle) {
: int n = triangle.size();
: int * p = new int[n]();