m*****n
发帖数: 2152 | 1 写了一个程序，但是系统总是用它算160+阶的triangle，然后显示Time Limit
Exceeded。
反复修改了，实在没办法再省时间了，而且还要求内存空间O(n).
请问，有人的程序能通过吗？
这是第一次在上面练习，不知道怎么算通过。 | n******d
发帖数: 386 | 2 确定没有死循环？
【在 m*****n 的大作中提到】
: 写了一个程序，但是系统总是用它算160+阶的triangle，然后显示Time Limit
: Exceeded。
: 反复修改了，实在没办法再省时间了，而且还要求内存空间O(n).
: 请问，有人的程序能通过吗？
: 这是第一次在上面练习，不知道怎么算通过。
| m*****n
发帖数: 2152 | 3 应该没有，现在改了code，有出现runtime error，算了还是先在机器上调试一下吧。 | j******i
发帖数: 244 | 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*****J
发帖数: 18 | 5 int triangle(vector> &triangle)
{
for(int i=triangle.size()-2; i>=0; i--)
{
for(int j=0; j
triangle[i][j]+=std::min(triangle[i+1][j], triangle[i+1][j+1]);
}
return triangle.empty()? 0 : triangle[0][0];
} | m*****n
发帖数: 2152 | 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; i
if(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]();
|
|
