m*n
2 楼
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]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
public class Solution {
int min=Integer.MAX_VALUE;
public int minimumTotal(ArrayList> triangle) {
// Start typing your Java solution below
// DO NOT write main() function
if(triangle.size()==0) return 0;
return dfs(triangle,1,triangle.get(0).get(0),0);
}
public int dfs(ArrayList> t,int l,int sum,int i) {
if(l==t.size()) return sum;
int left=dfs(t,l+1,sum+t.get(l).get(i),i);
min=left int right=dfs(t,l+1,sum+t.get(l).get(i+1),i+1);
min=right return min;
//return left }
}
刚开始我是想用一个global min去记录最小值然后最后返回。可是这个一直没通过一个
test case:[[-1],[2,3],[1,-1,-3]]
它说我输出-4,应该是-1。然后我就查了半天,不知道怎么会输出-4,然后我自己run了
一下给的相同的test input,结果输出的是-1.。。。。搞不懂怎么oj说我输出-4
后来发现根本没必要这个min变量,可以直接return left和right中最小的,然后通过
了小test case.
我没发现有min和没min本质上的不同。
请教各位大神。谢谢
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]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
public class Solution {
int min=Integer.MAX_VALUE;
public int minimumTotal(ArrayList
// Start typing your Java solution below
// DO NOT write main() function
if(triangle.size()==0) return 0;
return dfs(triangle,1,triangle.get(0).get(0),0);
}
public int dfs(ArrayList
if(l==t.size()) return sum;
int left=dfs(t,l+1,sum+t.get(l).get(i),i);
min=left
min=right
//return left
}
刚开始我是想用一个global min去记录最小值然后最后返回。可是这个一直没通过一个
test case:[[-1],[2,3],[1,-1,-3]]
它说我输出-4,应该是-1。然后我就查了半天,不知道怎么会输出-4,然后我自己run了
一下给的相同的test input,结果输出的是-1.。。。。搞不懂怎么oj说我输出-4
后来发现根本没必要这个min变量,可以直接return left和right中最小的,然后通过
了小test case.
我没发现有min和没min本质上的不同。
请教各位大神。谢谢
m*0
3 楼
我的EB2 PD:1/11/2013, 485 Received Date: July 2015.
现在EB3 current了。我有必要降级么?还是继续等?
谢谢
现在EB3 current了。我有必要降级么?还是继续等?
谢谢
g*o
5 楼
leetcode不是每次都重新创建对象
public class Solution {
int min=Integer.MAX_VALUE;
public int minimumTotal(ArrayList> triangle) {
// Start typing your Java solution below
// DO NOT write main() function
min=Integer.MAX_VALUE;//add this line
if(triangle.size()==0) return 0;
return dfs(triangle,1,triangle.get(0).get(0),0);
}
public int dfs(ArrayList> t,int l,int sum,int i) {
if(l==t.size()) return sum;
int left=dfs(t,l+1,sum+t.get(l).get(i),i);
min=left int right=dfs(t,l+1,sum+t.get(l).get(i+1),i+1);
min=right return min;
//return left }
}
public class Solution {
int min=Integer.MAX_VALUE;
public int minimumTotal(ArrayList
// Start typing your Java solution below
// DO NOT write main() function
min=Integer.MAX_VALUE;//add this line
if(triangle.size()==0) return 0;
return dfs(triangle,1,triangle.get(0).get(0),0);
}
public int dfs(ArrayList
if(l==t.size()) return sum;
int left=dfs(t,l+1,sum+t.get(l).get(i),i);
min=left
min=right
//return left
}
S*o
6 楼
看你的具体情况,如果工作稳定,也不急着用卡,等等也无所谓。要是想早拿卡将级应
该会快很多。
该会快很多。
l*d
7 楼
漏了各个学校的bookstore,大多有ipad,但货一般不多。
E*m
8 楼
你這個時間會超過, 必須用 DP 才行。
【在 g****o 的大作中提到】
: leetcode不是每次都重新创建对象
: public class Solution {
: int min=Integer.MAX_VALUE;
: public int minimumTotal(ArrayList> triangle) {
: // Start typing your Java solution below
: // DO NOT write main() function
: min=Integer.MAX_VALUE;//add this line
: if(triangle.size()==0) return 0;
: return dfs(triangle,1,triangle.get(0).get(0),0);
: }
【在 g****o 的大作中提到】
: leetcode不是每次都重新创建对象
: public class Solution {
: int min=Integer.MAX_VALUE;
: public int minimumTotal(ArrayList
: // Start typing your Java solution below
: // DO NOT write main() function
: min=Integer.MAX_VALUE;//add this line
: if(triangle.size()==0) return 0;
: return dfs(triangle,1,triangle.get(0).get(0),0);
: }
E*m
10 楼
DP 很容易寫
public class Solution {
public int minimumTotal(ArrayList> triangle) {
// Start typing your Java solution below
// DO NOT write main() function
int[] sum=new int[triangle.size()];
for (int i=0;i sum[i]=triangle.get(triangle.size()-1).get(i);
for (int i=triangle.size()-2;i>=0;i--){
ArrayList cur=triangle.get(i);
for (int j=0;j<=i;j++)
sum[j]=cur.get(j)+Math.min(sum[j], sum[j+1]);
}
return sum[0];
}
}
public class Solution {
public int minimumTotal(ArrayList
// Start typing your Java solution below
// DO NOT write main() function
int[] sum=new int[triangle.size()];
for (int i=0;i
for (int i=triangle.size()-2;i>=0;i--){
ArrayList
for (int j=0;j<=i;j++)
sum[j]=cur.get(j)+Math.min(sum[j], sum[j+1]);
}
return sum[0];
}
}
p*6
11 楼
果断降级马上绿
c*d
12 楼
把 min=Integer.MAX_VALUE;加到minimumTotal开头。
我一般不用instance variable.
【在 m***n 的大作中提到】
: 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]
: ]
: The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
我一般不用instance variable.
【在 m***n 的大作中提到】
: 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]
: ]
: The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
相关阅读
[包子大派送]PD刚到第一天绿了【梦里征文】奉献比较顺利的十年 (转载)找到新的similar job, 但是part-time的,可以transfer h1b吗? 还是只能用ead卡啦?现在I-140多长时间批准?EAD renew, I-765问题巴马要赢了哪儿有数据估算下PD08年2月之前的还有多少demand?LD是什么身份?新国会,基本上移民改革不会有任何变化2012年8月PD的PERM批到哪儿了?J1豁免了,I140今天批了,还需要办H1B吗?EB3 PD 2010年11月,什么时候可以交485呢?反对版主连任! (转载)EAD/AP 过期以后再renew可行吗?吾也绿了求个NIW的模版吧12月,1月排期猜对的给10个包子Green Card Tracker (I-485 Tracker) (转载)FYI: VSC H1-B ext approved yesterday想要跳槽,问一下关于priority date的保留问题