l********7 发帖数: 40 | 1 刚面过G,从9月份电面到现在一共两个月把所有事情弄完。
电面只有一轮,出了一个之前版上出现过的题,一个string由0,1和?组成,并且?可
以被替换成0或者1,让输出所有的把?替换之后不同的string,比如1?0把?替换之后
能够生成110和100
之后过了三周才接到onsite的通知
onsite一共有4轮,中间午餐
第一轮一上来告诉我一个function的定义和它的功能,然后问了很多test的东西,我也
不懂,就瞎扯,之后让我实现这个function以及它的一个变种,类似就是一个array of
integer,以及一个int,这个int表示一个window的宽度,这个window从array的一开
始滑动到最后,找出来在滑动的过程中每次window中int的和,比如一个array是[1,2,3
,4,5],然后window的宽度是2,那么就输出[3,5,7,9]
第二轮是给一个int N,让输出所有的长度为N的valid string的个数,valid string的
定义是由A,B,C三种字母组成,并且在这个string中任意连续的三个字母不能包括A,B,C
三个字母,比如BACCA就不是valid string,因为前三个字母B,A,C包含了这三个字母。
我用了一个三维的DP做,但是边界条件没有写好
第三轮特别简单,问了买卖stock那道题,以及在这上面又问了其它一些边边角角的东西
第四轮问了两个题,给一个array of int,以及一个range (low, high),找出array中
所有的continuos subsequence使得这个subsequence的和在range之中。第二个问题是
grid的题,假设你是harry potter,在grid的左上角,你现在要走到右下角,grid中有
正数也有负数,遇到正数表示你的strength增加那么多,遇到负数表示strength减少那
么多,在任何时刻如果你的strength小于等于0,那么你就挂了。在一开始你有一定的
初始的strength,现在问这个初始的strength最少是多少,才能保证你能够找到一条路
走到右下角
这周hr说送到HC了,求blessing啊!!!!! |
A*********c 发帖数: 430 | 2 Bless lz拿到大offer
of
,3
【在 l********7 的大作中提到】 : 刚面过G,从9月份电面到现在一共两个月把所有事情弄完。 : 电面只有一轮,出了一个之前版上出现过的题,一个string由0,1和?组成,并且?可 : 以被替换成0或者1,让输出所有的把?替换之后不同的string,比如1?0把?替换之后 : 能够生成110和100 : 之后过了三周才接到onsite的通知 : onsite一共有4轮,中间午餐 : 第一轮一上来告诉我一个function的定义和它的功能,然后问了很多test的东西,我也 : 不懂,就瞎扯,之后让我实现这个function以及它的一个变种,类似就是一个array of : integer,以及一个int,这个int表示一个window的宽度,这个window从array的一开 : 始滑动到最后,找出来在滑动的过程中每次window中int的和,比如一个array是[1,2,3
|
f********e 发帖数: 91 | 3 bless 搞定Google!
of
,3
【在 l********7 的大作中提到】 : 刚面过G,从9月份电面到现在一共两个月把所有事情弄完。 : 电面只有一轮,出了一个之前版上出现过的题,一个string由0,1和?组成,并且?可 : 以被替换成0或者1,让输出所有的把?替换之后不同的string,比如1?0把?替换之后 : 能够生成110和100 : 之后过了三周才接到onsite的通知 : onsite一共有4轮,中间午餐 : 第一轮一上来告诉我一个function的定义和它的功能,然后问了很多test的东西,我也 : 不懂,就瞎扯,之后让我实现这个function以及它的一个变种,类似就是一个array of : integer,以及一个int,这个int表示一个window的宽度,这个window从array的一开 : 始滑动到最后,找出来在滑动的过程中每次window中int的和,比如一个array是[1,2,3
|
d***n 发帖数: 832 | 4 Bless
HR还不错,说送了HC
我面完后HR只说一周内出消息 |
P*******r 发帖数: 210 | 5 Google 题目还是难啊。
第四个的第一题是用dp算 V[i][j] (i->j continues subsequence sum),然后比较
range吗? |
d*k 发帖数: 207 | 6 好久没在线练习了,写个valid string,欢迎斧正
// assume n >= 3 for simplicity
int valid_string(int n) {
int rec[2][3][3];
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
rec[2&1][i][j] = 1;
}
}
for (int i = 3; i <= n; ++i) {
for (int x = 0; x < 3; ++x) {
rec[i&1][x][x] = sum(rec[(i-1)&1][x], rec[(i-1)&1][x] + 3);
int y = (x+1) % 3;
int z = (x+2) % 3;
rec[i&1][x][y] = sum(rec[(i-1)&1][y], rec[(i-1)&1][y] + 3) - rec
[(i-1)&1][y][z];
rec[i&1][x][z] = sum(rec[(i-1)&1][z], rec[(i-1)&1][z] + 3) - rec
[(i-1)&1][z][y];
}
}
return sum(*rec[n&1], *rec[n&1] + 9);
} |
A*****o 发帖数: 284 | 7 valid string这题蛮有意思的, 也许可以简化为二维的dp, 写个思路供大家拍砖:
dp[i][x] 表示了下标位置为i 以字符 x (x = A B C) 结尾的valid string个数
有递推式
dp[i]['A'] = (dp[i-1]['B'] - dp[i-2]['C']) + (dp[i-1]['C'] - dp[i-2]['B'])
+ dp[i-1]['A']
上式的原理不难理解,类似容斥原理吧
初始条件可以为
dp[0]['A'] = dp[0]['B'] = dp[0]['C'] = 1;
dp[1]['A'] = dp[1]['B'] = dp[1]['C'] = 3;
最终答案取 dp[n]['A'] + dp[n]['B'] + dp[n]['C']
实现上我觉得直接开 dp[N][255]数组好了,省得计算下标,面试实现比较容易
本质上可能跟楼上的牛牛解法是一样的, 不过确实没读懂....
Bless lz 成功:) |
c********p 发帖数: 1969 | |
j*******r 发帖数: 201 | |
c********e 发帖数: 186 | |
|
|
z****s 发帖数: 409 | 11 bless,顺便问一句,怎么你面的全是算法题?和面的组有关系吗? |
j*********6 发帖数: 407 | 12 bless
下下周面 (蛋疼的thanksgiving 下周面不了) 同求bless
lz 是 new grad 吗? 好像new grad 都是算法题?
你每一轮多长时间? 我是 9:45 - 2:00 也能是四轮吗? 还是三轮? |
k*********6 发帖数: 738 | 13 第四轮的那个一个array of int,以及一个range (low, high),什么解法比较好呢?
我想先把array sort了再两头2 pointers往中间走,选出within range 的subsequence
, 靠谱吗? |
d*k 发帖数: 207 | 14 第四轮的两道题求澄清:
1. array里面是否可能出现负数?
2. Harry potter是否只能向右或向下走?
祝楼主好运 |
m*******m 发帖数: 80 | |
t*****y 发帖数: 25 | 16 同迷惑:什么叫continuous subsequence sum? 是两个index之前所有元素的和吗?
我的解法是两个pointer, 一个st 一个en,
int st = 0;
int en = -1;
int count = 0;
while(en < A.length){
// move en forward
while(count < low){
en++;
count += A[en];
}
while(count <= high){
addSequence(A,st,en);
en++;
count += A[en];
}
// move st forward
while(count > high){
count -= A[st];
st++;
}
while(count >= low){
addSequence(A,st,en);
st++;
count -= A[st];
}
}
subsequence
【在 k*********6 的大作中提到】 : 第四轮的那个一个array of int,以及一个range (low, high),什么解法比较好呢? : 我想先把array sort了再两头2 pointers往中间走,选出within range 的subsequence : , 靠谱吗?
|
l****y 发帖数: 1461 | |
z****s 发帖数: 409 | 18 好心人给说一下吧。。。现在就算法还行,TC有1700。但其他设计,OO什么的都基本上
就没认真学,现在也忘光了,不知道有没有面试只考算法的?
【在 z****s 的大作中提到】 : bless,顺便问一句,怎么你面的全是算法题?和面的组有关系吗?
|
l********7 发帖数: 40 | 19 我是new grad general招的,面的时候没有具体组,面我的人也来自不同的组
【在 z****s 的大作中提到】 : bless,顺便问一句,怎么你面的全是算法题?和面的组有关系吗?
|
l********7 发帖数: 40 | 20 面试官说不能sort,因为要输出range,如果sort了那index就乱掉了
最好的方法是用一个prefix sum array吧
subsequence
【在 k*********6 的大作中提到】 : 第四轮的那个一个array of int,以及一个range (low, high),什么解法比较好呢? : 我想先把array sort了再两头2 pointers往中间走,选出within range 的subsequence : , 靠谱吗?
|
|
|
l********7 发帖数: 40 | 21 1.可以出现负数
2.只能往右或者往下走
【在 d*k 的大作中提到】 : 第四轮的两道题求澄清: : 1. array里面是否可能出现负数? : 2. Harry potter是否只能向右或向下走? : 祝楼主好运
|
d********e 发帖数: 239 | 22 不明白valid string为啥要dp
直接用两个数记录前一个位置上,相同两个字母结尾的为a,不同字母结尾的为b
这样迭代一下
a = a +b;
b = 2*a+b;
初始值为长度为2,所以a=3,b=6,不就可以了吗
of
,3
【在 l********7 的大作中提到】 : 刚面过G,从9月份电面到现在一共两个月把所有事情弄完。 : 电面只有一轮,出了一个之前版上出现过的题,一个string由0,1和?组成,并且?可 : 以被替换成0或者1,让输出所有的把?替换之后不同的string,比如1?0把?替换之后 : 能够生成110和100 : 之后过了三周才接到onsite的通知 : onsite一共有4轮,中间午餐 : 第一轮一上来告诉我一个function的定义和它的功能,然后问了很多test的东西,我也 : 不懂,就瞎扯,之后让我实现这个function以及它的一个变种,类似就是一个array of : integer,以及一个int,这个int表示一个window的宽度,这个window从array的一开 : 始滑动到最后,找出来在滑动的过程中每次window中int的和,比如一个array是[1,2,3
|
z****s 发帖数: 409 | 23 谢啦,我是算法还行,其他设计,OO什么的就一塌糊涂了,如果只面算法和coding就太
好了。bless~
【在 l********7 的大作中提到】 : 我是new grad general招的,面的时候没有具体组,面我的人也来自不同的组
|
P*******r 发帖数: 210 | 24 赞一个,简单明了。
原则上也算一维dp吧。
【在 d********e 的大作中提到】 : 不明白valid string为啥要dp : 直接用两个数记录前一个位置上,相同两个字母结尾的为a,不同字母结尾的为b : 这样迭代一下 : a = a +b; : b = 2*a+b; : 初始值为长度为2,所以a=3,b=6,不就可以了吗 : : of : ,3
|
H*********a 发帖数: 34 | 25 valid string是否是每增加一位,多出来的个数为3*3(末两位相同的情况*可以添加的
char的种类)+6*2(末两位不同的情况*可以添加的char的种类) |
w**7 发帖数: 22 | 26 did anyone solve the harry potter question? please post your thoughts. |
b*****6 发帖数: 179 | 27 n(i, j) = max(0, min(n(i+1,j), n(i,j+1)) - input(i,j))
min(n(i+1,j), n(i,j+1)) 这步一个出界的话直接取另一个。两个都出界(右下角)这
项取0。
最后返回n(0,0)
【在 w**7 的大作中提到】 : did anyone solve the harry potter question? please post your thoughts.
|
w**7 发帖数: 22 | 28 it does not look right. If every value in the matrix is negative, your
answer would be 0 which is apprently not correct.
I am struggling with how we can keep track of a path with least negative
values. Greedy algorithm here is not going to give us the right answer.
【在 b*****6 的大作中提到】 : n(i, j) = max(0, min(n(i+1,j), n(i,j+1)) - input(i,j)) : min(n(i+1,j), n(i,j+1)) 这步一个出界的话直接取另一个。两个都出界(右下角)这 : 项取0。 : 最后返回n(0,0)
|
g*********e 发帖数: 14401 | 29
不错
有时候题目刷多了基本的数学反而忘了
【在 d********e 的大作中提到】 : 不明白valid string为啥要dp : 直接用两个数记录前一个位置上,相同两个字母结尾的为a,不同字母结尾的为b : 这样迭代一下 : a = a +b; : b = 2*a+b; : 初始值为长度为2,所以a=3,b=6,不就可以了吗 : : of : ,3
|
l*n 发帖数: 529 | 30 应该是
n(i,j) = input(i, j) + max(n(i-1, j), n(i, j-1)), -infinite if out of range
每个位置表示到当前位置的最多剩余。
给出n matrix之后从右下角开始找,每次都选bigger predecessor,一直走到左上角。
过程当中的最小值就是初始时要持有的strength。
比如
00 -3 -6 -1
-5 -2 -5 -9
-4 -1 -4 -1
-1 -2 -6 -1
要得到的是
00 -3 -9 -10
-5 -5 -10 -19
-9 -6 -10 -11
-10 -8 -14 -12
走法就是-12>>-11>>-10>>-6>>-5>>-3>>00
【在 b*****6 的大作中提到】 : n(i, j) = max(0, min(n(i+1,j), n(i,j+1)) - input(i,j)) : min(n(i+1,j), n(i,j+1)) 这步一个出界的话直接取另一个。两个都出界(右下角)这 : 项取0。 : 最后返回n(0,0)
|
|
|
w**7 发帖数: 22 | 31 what you proposed is a greedy algorithm - at every step, you choose a better
move, but overall, the path may not be the best. The best path is the one
has least amount of negative value through the whole path.
range
【在 l*n 的大作中提到】 : 应该是 : n(i,j) = input(i, j) + max(n(i-1, j), n(i, j-1)), -infinite if out of range : 每个位置表示到当前位置的最多剩余。 : 给出n matrix之后从右下角开始找,每次都选bigger predecessor,一直走到左上角。 : 过程当中的最小值就是初始时要持有的strength。 : 比如 : 00 -3 -6 -1 : -5 -2 -5 -9 : -4 -1 -4 -1 : -1 -2 -6 -1
|
z*****5 发帖数: 38 | 32
能不能先从index 0开始,把后面的element一个个加起来,sum在range内就记录,不然
就继续,直加到array结尾。然后从index 1开始,重复以上步骤。总共时间是O(n^2),
貌似和prefix sum array一样,而且不用额外space啊。或者说prefix sum array能做
出优于O(n^2)的解法?
不过既然是找出所有subarray,感觉遍历一遍所有subarray还是必要的,这样下限是不
是就只能是O(n^2)了?
【在 l********7 的大作中提到】 : 面试官说不能sort,因为要输出range,如果sort了那index就乱掉了 : 最好的方法是用一个prefix sum array吧 : : subsequence
|
l*n 发帖数: 529 | 33 确实,greedy思路走岔了,不过在考虑greedy accu怎么着路径的时候发现必须要有两
个matrix来dp,一个是accu, 一个是pathmin。
accu(i, j)=pathmin(i-1, j)>pathmin(i, j-1)?
accu(i-1, j)+input(i, j):
accu(i, j-1)+input(i, j);
pathmin(i, j)=pathmin(i-1, j)>pathmin(i, j-1)?
min(pathmin(i-1, j), accu(i, j)):
min(pathmin(i, j-1), accu(i, j));
better
【在 w**7 的大作中提到】 : what you proposed is a greedy algorithm - at every step, you choose a better : move, but overall, the path may not be the best. The best path is the one : has least amount of negative value through the whole path. : : range
|
w**7 发帖数: 22 | 34 Every path has a min and it is path dependent. I doubt you can dp the path
min as you proposed.
The brutal force solution:
1. In an m x n matrix, we know how many unique path exits. Easy
2. Iterate each path, find its path min, pm. Easy.
3. Find min of all pm[0, ... N], minpm. Easy.
4. If minpm is less than zero, abs(minpm) is the answer, otherwise, zero is
the answer.
The real challenge is: how can we do it faster?? Localized optimization (
greedy) is not a solution.
【在 l*n 的大作中提到】 : 确实,greedy思路走岔了,不过在考虑greedy accu怎么着路径的时候发现必须要有两 : 个matrix来dp,一个是accu, 一个是pathmin。 : accu(i, j)=pathmin(i-1, j)>pathmin(i, j-1)? : accu(i-1, j)+input(i, j): : accu(i, j-1)+input(i, j); : pathmin(i, j)=pathmin(i-1, j)>pathmin(i, j-1)? : min(pathmin(i-1, j), accu(i, j)): : min(pathmin(i, j-1), accu(i, j)); : : better
|
l*n 发帖数: 529 | 35 这样来分析吧。假设我们用brutal force方法解了问题,那么我们能够知道走到最右下
角时符合题设的路径中的最低strength。能对最右下角做,也就能对任何坐标点做。假
设现在知道了pathmin(i, j-1)和pathmin(i-1,j),也就是当坐标的左边和上边,那为
了走到当前坐标会如何走?进当前坐标格只有两个入口,或者左或者上,显然选的是
pathmin高的那个。一旦入口选定了,当前坐标的累计值accu就决定了,然后当前坐标
格的pathmin也就决定了。
这里pathmin不是记录的某个path的最低streng,而是所有能走到当前坐标格的路径中
最优路径的最低accu值。
is
【在 w**7 的大作中提到】 : Every path has a min and it is path dependent. I doubt you can dp the path : min as you proposed. : The brutal force solution: : 1. In an m x n matrix, we know how many unique path exits. Easy : 2. Iterate each path, find its path min, pm. Easy. : 3. Find min of all pm[0, ... N], minpm. Easy. : 4. If minpm is less than zero, abs(minpm) is the answer, otherwise, zero is : the answer. : The real challenge is: how can we do it faster?? Localized optimization ( : greedy) is not a solution.
|
w**7 发帖数: 22 | 36 Sorry I am not convinced even though I feel what you said have merit. Can
you post your code?
By the way, I feel this is like a directed graph. The starting point from
top left is important. For example, if you have a path such as 1->1->1->1->(
-5)->0
the required initial strength is 2. Your solution seems overlooked the
contribution of cell value to a path min, if I am not mistaken.
【在 l*n 的大作中提到】 : 这样来分析吧。假设我们用brutal force方法解了问题,那么我们能够知道走到最右下 : 角时符合题设的路径中的最低strength。能对最右下角做,也就能对任何坐标点做。假 : 设现在知道了pathmin(i, j-1)和pathmin(i-1,j),也就是当坐标的左边和上边,那为 : 了走到当前坐标会如何走?进当前坐标格只有两个入口,或者左或者上,显然选的是 : pathmin高的那个。一旦入口选定了,当前坐标的累计值accu就决定了,然后当前坐标 : 格的pathmin也就决定了。 : 这里pathmin不是记录的某个path的最低streng,而是所有能走到当前坐标格的路径中 : 最优路径的最低accu值。 : : is
|
l*n 发帖数: 529 | 37 我在调试,一会儿post。
你这个1>>1>>1>>1>>-5>>0的情况,对应的accu是1>>2>>3>>4>>-1>>-1,
而pathmin是1>>1>>1>>1>>-1>>-1,应该是对的。
>(
【在 w**7 的大作中提到】 : Sorry I am not convinced even though I feel what you said have merit. Can : you post your code? : By the way, I feel this is like a directed graph. The starting point from : top left is important. For example, if you have a path such as 1->1->1->1->( : -5)->0 : the required initial strength is 2. Your solution seems overlooked the : contribution of cell value to a path min, if I am not mistaken.
|
l*n 发帖数: 529 | 38 前面的递归还少了左方和上方pathmin相等时的处理。
下面的code我还用brutal force的比较过,用http://stackoverflow.com/questions/5498130/bit-manipulationprint-the-next-smallest-and-largest-numbers-with-same-no-of-1-b的nexthi_same_count_ones生成每个路径的01表示,两者能够match上。左方和上方pathmin相等时的情况就是用brutal force发现的。
int initStr(int[][] mat) {
assert (mat != null && mat.length > 0 && mat[0].length > 0);
int m = mat.length;
int n = mat[0].length;
int[][] accu = new int[m][n]; //cumulative
int[][] pathmin = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 && j == 0) { //boundary part 1: [0, 0]
accu[i][j] = 0;
pathmin[i][j] = 0;
continue;
}
//boundary part 2: left or up predecessor out of bound
int lefmin = j - 1 >= 0 ? pathmin[i][j - 1] : Integer.MIN_VALUE;
int upmin = i - 1 >= 0 ? pathmin[i - 1][j] : Integer.MIN_VALUE;
if (lefmin > upmin) {
accu[i][j] = accu[i][j - 1] + mat[i][j];
} else if (lefmin < upmin) {
accu[i][j] = accu[i - 1][j] + mat[i][j];
} else {
//greedy when paths to left and up have the same min
accu[i][j] = Math.max(accu[i][j - 1], accu[i - 1][j])
+ mat[i][j];
}
//update pathmin at [i, j]
pathmin[i][j] = lefmin > upmin ? Math.min(lefmin, accu[i][j])
: Math.min(upmin, accu[i][j]);
}
}
//return 0 if pathmin is always positive
return pathmin[m - 1][n - 1] <= 0 ? -pathmin[m - 1][n - 1] +1 : 0;
}
>(
【在 w**7 的大作中提到】 : Sorry I am not convinced even though I feel what you said have merit. Can : you post your code? : By the way, I feel this is like a directed graph. The starting point from : top left is important. For example, if you have a path such as 1->1->1->1->( : -5)->0 : the required initial strength is 2. Your solution seems overlooked the : contribution of cell value to a path min, if I am not mistaken.
|
w**7 发帖数: 22 | 39 Now I can comprehend your solution and I am with you 100%.
Using 2D array to dp is very easy to understand, but to use 1D array with
one extra element (m+1 or n+1) is much easy to write code as you don't need
boundary condition check.
Thanks a bunch!
【在 l*n 的大作中提到】 : 前面的递归还少了左方和上方pathmin相等时的处理。 : 下面的code我还用brutal force的比较过,用http://stackoverflow.com/questions/5498130/bit-manipulationprint-the-next-smallest-and-largest-numbers-with-same-no-of-1-b的nexthi_same_count_ones生成每个路径的01表示,两者能够match上。左方和上方pathmin相等时的情况就是用brutal force发现的。 : int initStr(int[][] mat) { : assert (mat != null && mat.length > 0 && mat[0].length > 0); : int m = mat.length; : int n = mat[0].length; : : int[][] accu = new int[m][n]; //cumulative : int[][] pathmin = new int[m][n]; : for (int i = 0; i < m; i++) {
|
l*********b 发帖数: 1541 | 40 if (lefmin > upmin) {
accu[i][j] = accu[i][j - 1] + mat[i][j];
} else if (lefmin < upmin) {
accu[i][j] = accu[i - 1][j] + mat[i][j];
}
上面两个if/else不是很明白, 感觉不能推出上面两个吧。。 请问你这个pathmin和
accu分别代表啥?
【在 l*n 的大作中提到】 : 前面的递归还少了左方和上方pathmin相等时的处理。 : 下面的code我还用brutal force的比较过,用http://stackoverflow.com/questions/5498130/bit-manipulationprint-the-next-smallest-and-largest-numbers-with-same-no-of-1-b的nexthi_same_count_ones生成每个路径的01表示,两者能够match上。左方和上方pathmin相等时的情况就是用brutal force发现的。 : int initStr(int[][] mat) { : assert (mat != null && mat.length > 0 && mat[0].length > 0); : int m = mat.length; : int n = mat[0].length; : : int[][] accu = new int[m][n]; //cumulative : int[][] pathmin = new int[m][n]; : for (int i = 0; i < m; i++) {
|
|
|
l*n 发帖数: 529 | 41 accu(accumulate)如其名字,是记录最优的path走到当前位置的累计值。
pathmin是走到当前位置的最优路径的最小accu值,假设路径上input矩阵的值是2>>5>>
-3>>-2>>4>>2的话,accu就是2>>7>>4>>2>>6>>8,而一路上pathmin的值是2>>2>>2>>2>
>2>>2。
这里ifelse的逻辑就是,进入某一个位置只能是从左边或者上边的cell,左边cell的
pathmin值比上边的pathmin要高的话,初始需要的strength就更低,所以从左边进入当
前cell。
【在 l*********b 的大作中提到】 : if (lefmin > upmin) { : accu[i][j] = accu[i][j - 1] + mat[i][j]; : } else if (lefmin < upmin) { : accu[i][j] = accu[i - 1][j] + mat[i][j]; : } : 上面两个if/else不是很明白, 感觉不能推出上面两个吧。。 请问你这个pathmin和 : accu分别代表啥?
|
l*********b 发帖数: 1541 | 42 虽然左边的pathmin比较高,但是上边的accu可能比较大。比如:左边的pathmin比较大
,但是accu是10,上边的accu是20, 当前cell的stength是-15,这时候要选上边的吧?
>>
2>
【在 l*n 的大作中提到】 : accu(accumulate)如其名字,是记录最优的path走到当前位置的累计值。 : pathmin是走到当前位置的最优路径的最小accu值,假设路径上input矩阵的值是2>>5>> : -3>>-2>>4>>2的话,accu就是2>>7>>4>>2>>6>>8,而一路上pathmin的值是2>>2>>2>>2> : >2>>2。 : 这里ifelse的逻辑就是,进入某一个位置只能是从左边或者上边的cell,左边cell的 : pathmin值比上边的pathmin要高的话,初始需要的strength就更低,所以从左边进入当 : 前cell。
|
G*****m 发帖数: 5395 | 43 min大但是accu小不能保证superior, 应该都保留吧
0 -5 10
0 0 0
0 0 -6
和
0 -5 10
0 0 0
0 0 -4
的解是不一样的
>>
2>
【在 l*n 的大作中提到】 : accu(accumulate)如其名字,是记录最优的path走到当前位置的累计值。 : pathmin是走到当前位置的最优路径的最小accu值,假设路径上input矩阵的值是2>>5>> : -3>>-2>>4>>2的话,accu就是2>>7>>4>>2>>6>>8,而一路上pathmin的值是2>>2>>2>>2> : >2>>2。 : 这里ifelse的逻辑就是,进入某一个位置只能是从左边或者上边的cell,左边cell的 : pathmin值比上边的pathmin要高的话,初始需要的strength就更低,所以从左边进入当 : 前cell。
|
m******s 发帖数: 1469 | 44 Bless
of
,3
【在 l********7 的大作中提到】 : 刚面过G,从9月份电面到现在一共两个月把所有事情弄完。 : 电面只有一轮,出了一个之前版上出现过的题,一个string由0,1和?组成,并且?可 : 以被替换成0或者1,让输出所有的把?替换之后不同的string,比如1?0把?替换之后 : 能够生成110和100 : 之后过了三周才接到onsite的通知 : onsite一共有4轮,中间午餐 : 第一轮一上来告诉我一个function的定义和它的功能,然后问了很多test的东西,我也 : 不懂,就瞎扯,之后让我实现这个function以及它的一个变种,类似就是一个array of : integer,以及一个int,这个int表示一个window的宽度,这个window从array的一开 : 始滑动到最后,找出来在滑动的过程中每次window中int的和,比如一个array是[1,2,3
|
j*********6 发帖数: 407 | 45 求大牛讲解一下 第四题 substring range 的解法
再贴一个 第四题 第二问 哈利波特 的 2D dp 解法 求大神看看 有什么问题
public static int smallestStrengthValue(int[][] grid){
if( grid == null || grid.length == 0 ||
grid[0] == null || grid[0].length == 0){
throw new IllegalArgumentException("State of grid is illegal!");
}
int row = grid.length;
int col = grid[0].length;
int[][] max = new int[row][col];
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
int left = j > 0 ? max[i][j - 1] : Integer.MIN_VALUE;
int upper = i > 0 ? max[i - 1][j] : Integer.MIN_VALUE;
if(left == Integer.MIN_VALUE && upper == Integer.MIN_VALUE){
max[i][j] = grid[i][j];
}else{
max[i][j] = grid[i][j] + Math.max(left, upper);
}
}
}
if(max[row - 1][col - 1] >= 0){
return 0;
}else{
return -max[row - 1][col - 1];
}
} |
w*******s 发帖数: 96 | 46 能举例子展开讲讲? 没看明白
【在 d********e 的大作中提到】 : 不明白valid string为啥要dp : 直接用两个数记录前一个位置上,相同两个字母结尾的为a,不同字母结尾的为b : 这样迭代一下 : a = a +b; : b = 2*a+b; : 初始值为长度为2,所以a=3,b=6,不就可以了吗 : : of : ,3
|
l*n 发帖数: 529 | 47 你是对的,楼上楼也提到pathmin跟accu的冲突,我原来想的错误比较是用pathmin[i,
j-1]跟pathmin[i-1, j],即便修正为比较"考虑了accu的"从上面和左边进入的两个假
想pathmin,也无法解决局部和全局的问题。每次比较进入[i,j]的两个假想的pathmin
,也可能会错过全局的最优,因为可能存在的情况是某个在中途不是给出最优pathmin
的路径反而能给出全局最优。
一个反例就是
6 -12 4 13
-1 -9 5 -3
-5 -11 -16 -17
-8 -13 5 -8
每次都要求进入当前位置的pathmin为最优导致选择-1 -9 5 ...的路径,其pathmin是-
1 -10 -10,但是在5的位置accu是-5,而brutal force给出的路径是-12 4 5...,在5
位置的accu是-3,而其pathmin是-12 -12 -12...。
这种局部最优策略跟全局最优的冲突,极端起来怕是每一处都需要走两条线。看来这个
harry potter的题目只能brutal force了。
【在 G*****m 的大作中提到】 : min大但是accu小不能保证superior, 应该都保留吧 : 0 -5 10 : 0 0 0 : 0 0 -6 : 和 : 0 -5 10 : 0 0 0 : 0 0 -4 : 的解是不一样的 :
|
p*****e 发帖数: 537 | 48 Potter那道题我的解法是这样的:
Keep一个neededStrength array,NS[N][N], NS[N-1][N-1] = 0,
NS[i][j] = min(NS[i+1][j], NS[i][j+1]) - strength[i][j]. If NS[i][j] < 0, NS
[i][j] = 0
return: NS[0][0] + 1, if NS[0][0] > 0, otherwise return 0. |
p*****e 发帖数: 537 | 49 Subarray sum那道题,我觉得如果O(n^2)可以的话,有至少2种解法,prefix sum
array,或是一个2D DP, 其实本质都一样。
有没有大牛说说优于O(n^2)的解法? |
l*******u 发帖数: 35 | |
|
|
S********e 发帖数: 74 | |
r**********o 发帖数: 50 | 52
大牛,这答案是不是有个小小问题?
因为以A结尾的dp[i]['A']还包括 substring(0,[i-1])不是valid string的情况。
比如0, i-1 只包含b,c 这两个字符。所以是不是还是要3维dp?
【在 A*****o 的大作中提到】 : valid string这题蛮有意思的, 也许可以简化为二维的dp, 写个思路供大家拍砖: : dp[i][x] 表示了下标位置为i 以字符 x (x = A B C) 结尾的valid string个数 : 有递推式 : dp[i]['A'] = (dp[i-1]['B'] - dp[i-2]['C']) + (dp[i-1]['C'] - dp[i-2]['B']) : + dp[i-1]['A'] : 上式的原理不难理解,类似容斥原理吧 : 初始条件可以为 : dp[0]['A'] = dp[0]['B'] = dp[0]['C'] = 1; : dp[1]['A'] = dp[1]['B'] = dp[1]['C'] = 3; : 最终答案取 dp[n]['A'] + dp[n]['B'] + dp[n]['C']
|
P****9 发帖数: 177 | |
w*******s 发帖数: 138 | 54 Harry Potter是二分搜索答案,对于每个答案,用DP判断是否可行。
一开始随便找一条路设初始值。
,
pathmin
pathmin
【在 l*n 的大作中提到】 : 你是对的,楼上楼也提到pathmin跟accu的冲突,我原来想的错误比较是用pathmin[i, : j-1]跟pathmin[i-1, j],即便修正为比较"考虑了accu的"从上面和左边进入的两个假 : 想pathmin,也无法解决局部和全局的问题。每次比较进入[i,j]的两个假想的pathmin : ,也可能会错过全局的最优,因为可能存在的情况是某个在中途不是给出最优pathmin : 的路径反而能给出全局最优。 : 一个反例就是 : 6 -12 4 13 : -1 -9 5 -3 : -5 -11 -16 -17 : -8 -13 5 -8
|
p*********y 发帖数: 17 | 55 没看懂,能否详细讲讲?
【在 w*******s 的大作中提到】 : Harry Potter是二分搜索答案,对于每个答案,用DP判断是否可行。 : 一开始随便找一条路设初始值。 : : , : pathmin : pathmin
|
w*******s 发帖数: 138 | 56 给定初始strength,用DP算出能否到达右下角,DP的状态是到达每一个点的strength的
最大值,此算法输入是strength,输出是yes or no。
随便找一条路就能得到一个可以走到右下角的strength(S),在0 - S范围里二分搜索
,反复调用DP算法,找到最小的返回yes的strength就可以了。
【在 p*********y 的大作中提到】 : 没看懂,能否详细讲讲?
|
e********r 发帖数: 24 | 57 最后一个题意不明,如果是“保证”,是不是应该求负得最多的那条路?
of
,3
【在 l********7 的大作中提到】 : 刚面过G,从9月份电面到现在一共两个月把所有事情弄完。 : 电面只有一轮,出了一个之前版上出现过的题,一个string由0,1和?组成,并且?可 : 以被替换成0或者1,让输出所有的把?替换之后不同的string,比如1?0把?替换之后 : 能够生成110和100 : 之后过了三周才接到onsite的通知 : onsite一共有4轮,中间午餐 : 第一轮一上来告诉我一个function的定义和它的功能,然后问了很多test的东西,我也 : 不懂,就瞎扯,之后让我实现这个function以及它的一个变种,类似就是一个array of : integer,以及一个int,这个int表示一个window的宽度,这个window从array的一开 : 始滑动到最后,找出来在滑动的过程中每次window中int的和,比如一个array是[1,2,3
|
m******n 发帖数: 187 | 58 把prefix sum sort 一下,找到大的减小的在规定范围内,就是线性问题了。
当然要检查大的是更多的数的和。这样是O(nlogn)。
【在 p*****e 的大作中提到】 : Subarray sum那道题,我觉得如果O(n^2)可以的话,有至少2种解法,prefix sum : array,或是一个2D DP, 其实本质都一样。 : 有没有大牛说说优于O(n^2)的解法?
|
g*****g 发帖数: 212 | 59 dek问到点子了。
我觉得应该需要这个条件。
1)假设没有负数
先构建一个数组 sum
sum[i] = Sigma(A[0]+...+A[i])
求此序列
foreach(A[i])
{
lower index sum[j] >= lowerbond - sum[i]
upper index sum[k] <= upperbond - sum[i]
(j,k)为所求
}
NlogN
2)假设只能右或者下
先把(0,0)设置为0
相当于找到一条左上到又下的最大和路径,可DP
路径中abs(最小值) 就是所求
m*n + (m+n)
【在 d*k 的大作中提到】 : 第四轮的两道题求澄清: : 1. array里面是否可能出现负数? : 2. Harry potter是否只能向右或向下走? : 祝楼主好运
|
A*********c 发帖数: 430 | 60 大家有没有试过,第二题用dfs+剪枝可以写出很简练的代码。同时可以方便得生成合法
的字符串。
of
,3
【在 l********7 的大作中提到】 : 刚面过G,从9月份电面到现在一共两个月把所有事情弄完。 : 电面只有一轮,出了一个之前版上出现过的题,一个string由0,1和?组成,并且?可 : 以被替换成0或者1,让输出所有的把?替换之后不同的string,比如1?0把?替换之后 : 能够生成110和100 : 之后过了三周才接到onsite的通知 : onsite一共有4轮,中间午餐 : 第一轮一上来告诉我一个function的定义和它的功能,然后问了很多test的东西,我也 : 不懂,就瞎扯,之后让我实现这个function以及它的一个变种,类似就是一个array of : integer,以及一个int,这个int表示一个window的宽度,这个window从array的一开 : 始滑动到最后,找出来在滑动的过程中每次window中int的和,比如一个array是[1,2,3
|
|
|
A*********c 发帖数: 430 | 61 为什么我觉得第二题就是一个dp,从(M-1,N-1)往(0,0)规划如下
dp[i][j] = max(dp[i+1][j], dp[i][j+1]) + A[i][j];
结果就是
return dp[0][0] < 0 ? -dp[0][0] : 0;
和Leetcode里边的unique path没区别,就是方向反了而已,
Did I miss anything?
of
,3
【在 l********7 的大作中提到】 : 刚面过G,从9月份电面到现在一共两个月把所有事情弄完。 : 电面只有一轮,出了一个之前版上出现过的题,一个string由0,1和?组成,并且?可 : 以被替换成0或者1,让输出所有的把?替换之后不同的string,比如1?0把?替换之后 : 能够生成110和100 : 之后过了三周才接到onsite的通知 : onsite一共有4轮,中间午餐 : 第一轮一上来告诉我一个function的定义和它的功能,然后问了很多test的东西,我也 : 不懂,就瞎扯,之后让我实现这个function以及它的一个变种,类似就是一个array of : integer,以及一个int,这个int表示一个window的宽度,这个window从array的一开 : 始滑动到最后,找出来在滑动的过程中每次window中int的和,比如一个array是[1,2,3
|
A*********c 发帖数: 430 | 62 “才能保证你能够找到一条路走到右下角”
这不是说了找到一条路就行吗,没说要求任意一条路,对吧。
【在 e********r 的大作中提到】 : 最后一个题意不明,如果是“保证”,是不是应该求负得最多的那条路? : : of : ,3
|
n*******s 发帖数: 482 | 63 validation string DP (2d)
M[CurrentLength, Last2Index]
Last2Index:
0: AA
1: AB
..
8: CC
M[i+1, 0 - 9] is depends on M[i, 0 - 9]
也可以用两个数组pre, current来简化
pre=[1,1,1,1,1,1,1,1,1]
for(j = 3 to n)
cur= [0]*9
for i = 0 to 8
tmp = pre[i] +1
switch(i)
case 0 :
cur[0]+= tmp // AA -> AAA
cur[1]+= tmp // AA => AAB
cur[2]+= tmp // AA => AAC
break;
case 1:
cur[4]+=tmp //AB -> ABA
cur[3]+=tmp //AB => ABB
...
pre = cur
final_result = sumup (pre[i])
|
l******6 发帖数: 340 | 64 Re
【在 w*******s 的大作中提到】 : 给定初始strength,用DP算出能否到达右下角,DP的状态是到达每一个点的strength的 : 最大值,此算法输入是strength,输出是yes or no。 : 随便找一条路就能得到一个可以走到右下角的strength(S),在0 - S范围里二分搜索 : ,反复调用DP算法,找到最小的返回yes的strength就可以了。
|
A*********c 发帖数: 430 | 65 This dumb solution is blatantly wrong.
Thanks for Jc2013 and lcheng to point out.
【在 A*********c 的大作中提到】 : 为什么我觉得第二题就是一个dp,从(M-1,N-1)往(0,0)规划如下 : dp[i][j] = max(dp[i+1][j], dp[i][j+1]) + A[i][j]; : 结果就是 : return dp[0][0] < 0 ? -dp[0][0] : 0; : 和Leetcode里边的unique path没区别,就是方向反了而已, : Did I miss anything? : : of : ,3
|
i*****t 发帖数: 68 | 66 第二题能不能化简为一维DP.
因为DP[i][A] == DP[i][B] == DP[i][C]
设DP[i]为以index i为结尾的变体个数
所以DP[i] = dp[i - 1] + 2(dp[i - 1] - dp[i - 2]);
最后返回3DP[N - 1] |
j****u 发帖数: 12 | 67 mark
of
,3
【在 l********7 的大作中提到】 : 刚面过G,从9月份电面到现在一共两个月把所有事情弄完。 : 电面只有一轮,出了一个之前版上出现过的题,一个string由0,1和?组成,并且?可 : 以被替换成0或者1,让输出所有的把?替换之后不同的string,比如1?0把?替换之后 : 能够生成110和100 : 之后过了三周才接到onsite的通知 : onsite一共有4轮,中间午餐 : 第一轮一上来告诉我一个function的定义和它的功能,然后问了很多test的东西,我也 : 不懂,就瞎扯,之后让我实现这个function以及它的一个变种,类似就是一个array of : integer,以及一个int,这个int表示一个window的宽度,这个window从array的一开 : 始滑动到最后,找出来在滑动的过程中每次window中int的和,比如一个array是[1,2,3
|
n*******5 发帖数: 37 | |
l******a 发帖数: 64 | 69 4.2. 第四轮第二个, Harry Potter那道题试写了一下伪代码
memo[m+1][n+1]
For i in [0, m]
For j in [0, n]
Memo[i][j] = 0
For i in [0, m-1]
For j in [0, n-1]
Memo[i+1][j+1] = Memo[i][j+1] + grid[i][j]
Memo[i+1][j+1] = max(Memo[i+1][j+1] ,Memo[i][j+1] + grid[i][j])
val = Memo[m][n]-grid[m-1][n-1]
If val < 0
return -val
Else
Return 0 |
b*******d 发帖数: 750 | 70 1. 那个ABC的题,如此可以么?
先算N-1, 得到一个list of string,然后,算N的情况:iterate N-1的那个list,
每个string的每个位置,都拿ABC分别test一下,如果可以,就insert进去,算作一个N
的情况的解。
2. harry potter,难道不是 nxm的DP么?
构建个Nxm的矩阵,每个cell,纪录两个值:到达此处的strength 和最小需要的初始携
带strength。对个每个cell,看其两个来源cell,取各自的strength,加上cell本身的
strength,如果小于0,那么说明从这个cell来到当前cell的话,还需要再加一部分初
始携带strength,update这个初始strengh,取小的那个assign到当前cell。
一直到右下结束。 |