i******t
发帖数: 22541 | 1 自己编辑可以通过啊 放在leetcode 说time error。。。
咋回事啊
class Solution {
public:
int minimumTotal(vector > &triangle) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int minV = INT_MAX;
int m = triangle.size();
vector > vecV;
vecV.resize(m);
if(m==0) return 0;
if(m==1) return triangle[0][0];
vecV[0][0]=triangle[0][0];
for(int i=1;i
{
int n = triangle[i].size();
vecV[i].resize(n);
for(int j=0;j
{
vecV[i][j] =INT_MAX;
int leftIdx = j-1;
int middleIdx = j;
int rightIdx = j+1;
if(leftIdx>=0 && leftIdx
{
vecV[i][j]=min(vecV[i][j], vecV[i-1][leftIdx]+triangle[i
][j] );
}
if(middleIdx>=0 && middleIdx
{
vecV[i][j]= min( vecV[i][j], vecV[i-1][middleIdx]+
triangle[i][j] ) ;
}
if(rightIdx>=0 && rightIdx
{
vecV[i][j]= min( vecV[i][j], vecV[i-1][rightIdx]+
triangle[i][j] ) ;
}
}
}
vector v;
for(int j=0;j
{
v.push_back( vecV[m-1][j]);
}
std::sort(v.begin(),v.end());
return v[0];
}
}; | l*****a
发帖数: 14598 | 2 前面的没看
最后面你明明扫一遍最后一行，找到最小的就得了
你还非要弄个额外的vector,再sort...
【在 i******t 的大作中提到】
: 自己编辑可以通过啊 放在leetcode 说time error。。。
: 咋回事啊
: class Solution {
: public:
: int minimumTotal(vector > &triangle) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: int minV = INT_MAX;
: int m = triangle.size();
: vector > vecV;
|
|
