p*****2
发帖数: 21240 | 1
我还没看答案呢。有时间再看。我感觉两个边很容易找，然后就是按顺序找叶子了。 |
|
|
w****x
发帖数: 2483 | 3
啊, 服了, 原来就是left-most bottom 和 right most 啊, 我还以为是那种edge, 想
了半天
_______________28_______________
/ \
4____ ____69
\ /
__8__ __56__
/ \ / \
__7 12__ __34 __27__
/ \ / / \
5_ _13 _2 _3 39
\ / / /
6 11 10 9
原来7, 5都不打印, 那也没什么难的 |
|
w****x
发帖数: 2483 | 4
这题他说的没错, 就是按search的路径找diff最小的, 你可以证明
如果当前节点比目标数字小, 你只需要search右子树, 因为左子树所有节点的diff肯定
更大,
如果当前节点比目标数字大, 你只需要search左子树, 因为右子树所有节点的diff肯定
更大,
相等的话那就是最小喽.
把上面3条想通了就可以了, 我想了7,8分钟, NND |
|
a********m
发帖数: 15480 | 5 是的，想通了狠容易，但是有些细节地方一开始没想到也狠正常。比如下面这个树目标
数字是4.
2
/ \
1 50
/ \
45 60 |
|
z****h
发帖数: 164 | 6 dijkestra的空间时间复杂度是O(n)??
求实现。。。 |
|
|
h**6
发帖数: 4160 | 8 两个指针，一个指向开始跳的位置，一个指向到达的位置。扫描到数组末尾结束。 |
|
a********m
发帖数: 15480 | 9 假设a->b这个区间可以最少用n步。用n+1步能达到的是：
c = max{array[i] + i, i = a->b}
现在是b->c这个区间可以用n+1步达到。
循环到c>目标就可以了。 |
|
t*****j
发帖数: 1105 | 10 我错了，貌似还是O(n^2)，哪怕递归。
O（n）的解法怎么弄啊？能私我么？
谢了！ |
|
|
t*****j
发帖数: 1105 | 12 OK，就是算最远能到达的范围，因为所有在最远能到达范围
内的所有地方都是可以到达的，因为这些范围是连续的。 |
|
|
a********m
发帖数: 15480 | 14 恩。每一步算一批。其实还是dp思路，区别在具体应用方法。 |
|
z****h
发帖数: 164 | 15 谢谢虫子。
不过好像这还是O(n2)的复杂度吧。
如有错误请更正。 |
|
|
a********m
发帖数: 15480 | 17 不会呀。每个点算一次,然后和当前的max比较一次。没别的计算了。 |
|
a********m
发帖数: 15480 | 18 纯greedy不对，比如下面这个：
2，100，1，1，1，1，1，1 |
|
Z*****Z
发帖数: 723 | 19 建议大家直接上LeetCode，Jump Game II，过了之后直接贴代码，呵呵。 |
|
a********m
发帖数: 15480 | 20 差不多这个意思吧。没运行过不保证没小错误。
int Steps(int* array, int n) {
int start = 0;
int end = 0;
int steps = 0;
while (end < n) {
steps++;
int next = end;
for (int i = start; i <= end; ++i) {
int reach = array[i] + i;
next = max(next, reach);
}
start = end + 1;
end = next;
assert(start <= end);
}
return steps;
} |
|
|
|
|
|
|
p*****2
发帖数: 21240 | 26 public int jump(int[] A)
{
int ans = 0;
int n = A.length;
int start = 0;
int end = 0;
while (end < n - 1)
{
int max = 0;
for (int i = start; i <= end; i++)
max = Math.max(max, i + A[i]);
ans++;
start = end + 1;
end = max;
}
return ans;
} |
|
w****x
发帖数: 2483 | 27
greedy 又不能保证最优, 这题就考个DP, 别折腾啦, 还没见过哪家面试考greedy的 |
|
|
p*****2
发帖数: 21240 | 29
本来就是尽量往远跳呀。这样才能有最小的步数呢。 |
|
|
|
|
a********m
发帖数: 15480 | 33 你的程序检查每个点，不算尽量往远跳的greedy。greedy是:
start = 0;
end = 0;
while (end < n) {
end = array[start];
} |
|
|
w****x
发帖数: 2483 | 35
太牛X了, 这都能想到, 能不能描述一下你是怎么一步步想到这个的?? |
|
|
a********m
发帖数: 15480 | 37 俺的例子里面:
2, 100, 1,1,1
第一步你没有前进2而是前进1就已经不是greedy了。解法里面有greedy的影子但不是真
正的greedy。 |
|
w****x
发帖数: 2483 | 38
算了, 遇到这种题直接投降, greedy出现概率太低了, 记得以前有个什么安排活动不让
时间冲突的题也是greedy, 还有一个数学方法证明greedy最优解的公式啥的, 直接放弃
了... |
|
p*****2
发帖数: 21240 | 39
我还真没学过算法。看来我对greedy的理解有误呀。 |
|
|
Z*****Z
发帖数: 723 | 41 赞美一下二爷的这个解。
但是我要+1这不是greedy. |
|
U*********y
发帖数: 54 | 42 我当时写的解法和你差不错, 只不过是用递归写的, 面试官又问怎么证明算法的正确性
, 没有证出来. 有没有想法如何证明? |
|
|
|
t******d
发帖数: 1383 | 45 first name D, last name is Z. seems like chinese. |
|
|
s*******e
发帖数: 1630 | 47 晕，跟facebook完全不同的公司好不好，面试之前稍微了解一下人家公司吧，用用又不
收费 |
|
t******d
发帖数: 1383 | 48 "差不多"，我们定义不一样吧。你要是觉得我不对，不回帖就ok |
|
n*******n
发帖数: 446 | 49 看了下 ，确实跟是跟facebook很不同的公司。别人的建议是好的，先了解下它们家公
司. |
|
c****e
发帖数: 57 | 50 经常版面潜水。现回馈大家。
A家要俺去seattle。标准package吧。
SDE II
125K base
65K sign on, 2 years
400 rsu。
4年工作经验，非牛人。
大家觉得如何。一个人工作，这个在西雅图能买的起房子么？
还有个M家offer，差的太远，就不说了。 |
|
