l*********8
发帖数: 4642 | 1 这个方法类似二叉树遍历， 二叉树遍历也有路径回溯，但还是O(n)的算法。 |
|
b***m
发帖数: 5987 | 2
这题我还真没接触过。你总要遍历一遍该链表吧？这跟图的遍历有什么区别？ |
|
|
d*********g
发帖数: 154 | 4
我感觉应该是你说的这样。遍历过的元素就标记为visited（或者直接把遍历过的1改成
0或者2，如果允许改动原矩阵的话）。这样每个元素最多访问2遍。不知道我说的对不
对。 |
|
j*****s
发帖数: 189 | 5 嗯，我也是在这里绊了好久，其实hash table的遍历是不讲究顺序的，只要能把所有元
素遍历一遍就行了。 |
|
j*****s
发帖数: 189 | 6 嗯，我也是在这里绊了好久，其实hash table的遍历是不讲究顺序的，只要能把所有元
素遍历一遍就行了。 |
|
S**I
发帖数: 15689 | 7 ☆─────────────────────────────────────☆
princekim (Prince Kim) 于 (Wed Apr 11 09:32:26 2012, 美东) 提到:
BT树结构, 中间节点是算数运算符(只有+ - * / 4种操作), 叶节点是数字, 要求给出
算数表达式 (要求没有冗余括号)
比如
*
/ \
+ *
/ \ / \
1 2 4 5
表达式 = (1 + 2) * 4 * 5, 不能是 (1+2)*(4*5)
+
/ \
* +
/ \ / \
1 2 4 5
表达式 = 1 * 2 + 4 + 5, 不能是 1 * 2 + (4 + 5)
总之, 这题的难点是 算数表达式不能有冗余括号
我当时的思路: in-order 递归遍历, 遇到 + - 给出左右括号 (但这样就有冗余括号).
面试官指出后, 我说我可以再扫描遍得到的表达式，去除冗余括号 (这也是我情急下
蒙的).
他说不行, ... 阅读全帖 |
|
y****n
发帖数: 743 | 8 思路：
1. 逆序遍历，凡是比后面最小值min大的元素，都需要swap。
并且记录其中最小值swapMin。
2. 再次逆序遍历，把第一次没数过的并且比swapMin大的都需要swap。
假设输入参数不为空：
public static int MinSwap(int[] arr)
{
int swapCount = 0;
int swapMin = int.MaxValue;
int min = int.MaxValue;
for (int i = arr.Length - 1; i >= 0; i--)
if (arr[i] > min)
{
swapCount++;
if (arr[i] < swapMin)
swapMin = arr[i];
}
else if (arr[i] < min)
min = arr[i];
min = int.MaxValue;
for (int i = arr.Length - 1; i >= 0; i--)
{
if ((arr[i] <= min) && (arr[i] > swapMin))
swapCount++;
if (arr[i] ... 阅读全帖 |
|
y****n
发帖数: 743 | 9 思路：
1. 逆序遍历，凡是比后面最小值min大的元素，都需要swap。
并且记录其中最小值swapMin。
2. 再次逆序遍历，把第一次没数过的并且比swapMin大的都需要swap。
假设输入参数不为空：
public static int MinSwap(int[] arr)
{
int swapCount = 0;
int swapMin = int.MaxValue;
int min = int.MaxValue;
for (int i = arr.Length - 1; i >= 0; i--)
if (arr[i] > min)
{
swapCount++;
if (arr[i] < swapMin)
swapMin = arr[i];
}
else if (arr[i] < min)
min = arr[i];
min = int.MaxValue;
for (int i = arr.Length - 1; i >= 0; i--)
{
if ((arr[i] <= min) && (arr[i] > swapMin))
swapCount++;
if (arr[i] ... 阅读全帖 |
|
M********5
发帖数: 715 | 10 除了用一个map的structure, 建立一个原来数组长度的bitset，在遍历原来的数组的时
候，如果发现有相同的string存在过，就把原来的那个bit set为0，把新的bit set为1
，然后最后从头到尾扫一遍bitset，就可以得到最后的结果。不过这个提法跟你的提法
可能会适用于不同的地方，如果原数组的重复的string很少，可能这个会更好，因为
sorting一般会nlogn的时间，这个是线性的；不过如果重复的多的话，sorting会更划
算，比如如果10000个数组最后可能只有100个unique的，显然遍历一遍也要花10000，
但是sorting比这个快。 |
|
b********s
发帖数: 1676 | 11 是比较2n次啊。你遍历一遍和遍历两遍不是都要比较2n次吗？如果是worst case的话。 |
|
u****u
发帖数: 229 | 12 本来一个很简单的问题，一看就知道应该用DP做的，结果想搞个小花招，弄一个遍历的
方法做对比，结果没想到遍历的算法特复杂，居然想不出来，折腾了半天也搞不定，整
的气势全无，最后DP也只能草草收场，太郁闷了！ |
|
r********g
发帖数: 14 | 13 基于你的算法，我稍作改变：
建立一个hashset 和一个linkedlist， linkedlist 不需要double single即可 有
header和tail两个指针
对于string， 在遍历时，先检验是存在于hashset之中 如果存在 检验下一个char
如果不存在，放到linkedlist的tail后面 tail指向这个node 同时放到hashset中
这样遍历string一边后，
从linkedlist的header 开始查找 如果存在于hashset中 header指向下一个， 如果不
存在于hashset
return header的value 如果header指向null return 不dupliate的char 不存在。 |
|
e****e
发帖数: 418 | 14 hashtable这里不好使吧, 原因好猫已经说了.
我觉得从小文件里建个tree.具体如下：
1. 对小文件里的每行的域名double reverse(老题...),
i.e. washington.usa -> usa.washington
2. 再建立prefix tree.
i.e (root)
|
|
usa
/ \
/ \
oregon washington
3. 遍历大文件里的域名, double reverse 之后和比较.
优化：
prefix tree只需要建立第一层就可以了. 至此，我觉得hashtable更好！
其实是个hashset,里面放小文件里域名反转之后的第一级域名.
i.e.
usa
china
canada
然后遍历大文件, 看hashset包含反转域名之后第一级域名.
i.e.
bjhmm.seattle.washington.usa --> usa.washin... 阅读全帖 |
|
m******s
发帖数: 165 | 15 来自主题: JobHunting版 - G 家面经 真要虐出翔了。。。
1:
边同时遍历两个树边建一个新的，最后有可能要再遍历一次，比如：
I1 =
01
10
I2 =
10
01
则I1 intersect I2 =
00
00
即I1 intersect I2 = 0
2A:
O(n)，由于array可以随机存取所以很好写。。。
2B:
好像前面有说，根据两个人的位置dp，greedy不太对
3A:
c++ stl lower_bound
3B:
应该不用上template吧orz，意思意思行了
4A:
trie (prefix tree)，根据用户输入习惯或者是流行搜索词进行缓存
4B:
range minimum query，做法很多，在线算法评判的标准有这么几个：
空间复杂度 预处理时间复杂度 每次查询时间复杂度
可以搜索一下各种算法的不同
另外还可以扩展到多线程/多台机器
的。 |
|
i**********e
发帖数: 1145 | 16 关于怎么测下一步是不是合法：
每一个字母'a'-'z'遍历，再看是否在字典里的复杂度 = 26 * n (n = 字的长度）
unordered_set 的查询是 O(1) 的。
遍历所有字典里的字然后一个一个比较是 n * dictionary_size，复杂度自然就上去
了。 |
|
i**********e
发帖数: 1145 | 17 你的算法每次从queue 里取出一个字出来，就要遍历hashtable 里所有的字。
这很不efficient，因为字典内可能含有很多字。还有就是，hashtable 遍历好像很不
efficient，只有查询最适合。
倒过来思考：
把queue 取出来的那个字的所有可能性枚举出来。
如果字的长度是6，那么所有可能性就是 26*6 = 156，远远小于字典内的个数。 |
|
i**********e
发帖数: 1145 | 18 关于怎么测下一步是不是合法：
每一个字母'a'-'z'遍历，再看是否在字典里的复杂度 = 26 * n (n = 字的长度）
unordered_set 的查询是 O(1) 的。
遍历所有字典里的字然后一个一个比较是 n * dictionary_size，复杂度自然就上去
了。 |
|
i**********e
发帖数: 1145 | 19 你的算法每次从queue 里取出一个字出来，就要遍历hashtable 里所有的字。
这很不efficient，因为字典内可能含有很多字。还有就是，hashtable 遍历好像很不
efficient，只有查询最适合。
倒过来思考：
把queue 取出来的那个字的所有可能性枚举出来。
如果字的长度是6，那么所有可能性就是 26*6 = 156，远远小于字典内的个数。 |
|
s******y
发帖数: 72 | 20 两轮店面 + Onsite, onsite面了8个人，四个人问coding，两个人问design，一个人问
project，还有一个senior manager问behavior。 题目都不难，自我感觉答得也还行，
但是还是悲剧了，anyway， move on了。 发一下记得的题目，
电面：
1. 给一个二叉树，返回它的镜像
实现一个 thread-safe blocking queue
2. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
似树遍历一样的方法
Onsite:
第一个: 给两个单词， 比如head, tail: 找到一个最短的转换，从head到tail，每
次只能变一个字母，path上的word都必须是有效的英文单词，我用的Graph shortest
path
第二个: memcpy: 源区域和目标区域可能有重叠
BST 插入和删除操作实现
BST iterator 实现
3: 实现两... 阅读全帖 |
|
f*********m
发帖数: 726 | 21 那位大俠能給個下面两题的解法？
2. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
似树遍历一样的方法
我的想法：
（1）HashMap里装的value type是一个class,这个class的member包括elementhe 和map。
（2）HashMap里装的value type是一个指针，这个指针的类型可以是elementhe 或map
。不过不太确定如何转化指针类型。
4: Given a social graph, find if there is a path between two persons with at
most 2 steps (3rd level connection), how to handle it in distributed way (
large graph stored at a large number of nodes, minimize cross-communication)... 阅读全帖 |
|
s******y
发帖数: 72 | 22 两轮店面 + Onsite, onsite面了8个人，四个人问coding，两个人问design，一个人问
project，还有一个senior manager问behavior。 题目都不难，自我感觉答得也还行，
但是还是悲剧了，anyway， move on了。 发一下记得的题目，
电面：
1. 给一个二叉树，返回它的镜像
实现一个 thread-safe blocking queue
2. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
似树遍历一样的方法
Onsite:
第一个: 给两个单词， 比如head, tail: 找到一个最短的转换，从head到tail，每
次只能变一个字母，path上的word都必须是有效的英文单词，我用的Graph shortest
path
第二个: memcpy: 源区域和目标区域可能有重叠
BST 插入和删除操作实现
BST iterator 实现
3: 实现两... 阅读全帖 |
|
f*********m
发帖数: 726 | 23 那位大俠能給個下面两题的解法？
2. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
似树遍历一样的方法
我的想法：
（1）HashMap里装的value type是一个class,这个class的member包括elementhe 和map。
（2）HashMap里装的value type是一个指针，这个指针的类型可以是elementhe 或map
。不过不太确定如何转化指针类型。
4: Given a social graph, find if there is a path between two persons with at
most 2 steps (3rd level connection), how to handle it in distributed way (
large graph stored at a large number of nodes, minimize cross-communication)... 阅读全帖 |
|
l*******b
发帖数: 2586 | 24 不知道,看大牛指导下
面的时候也是说搞个linked list就够了,回来想了下觉得那个需要多一些code,删除,插
入都不如hash table的写起来好写.
最早一直觉得搞一个数组存每个node就好了,发现删除节点会很麻烦,删除了数组就得动
,编号就要变.
要删除简单用链表,每个edge都会成为一个真正的link,可是这样又没有random access
一个node,而且创建一个graph貌似会比较繁琐,这个题倒无所谓,因为总是要遍历一遍,
而且编号都有,不关心具体连接结构,存个整数做标记就好了.
hash table貌似两个都能, 感觉适合需要动态变化的graph. hash table的iterator本
身就是一个linked list实现的吧,插入hash table的时候加到一个linked list里, 这
样. 还是遍历hash数组那样, 根据load factor动态更新hash table的size.
hashMap |
|
E*****D
发帖数: 3 | 25 可以看作是一个upside down的二叉树。从当前节点往上遍历所有parents,存到hashmap
. 然后遍历另外一节点的parents, 查看是否已在hashmap中。 |
|
n*******w
发帖数: 687 | 26 re
曾经面G，有个题第一步是遍历树都要用跌代写。那题还不是考树的遍历。 |
|
b******7
发帖数: 92 | 27 后序遍历非递归bug free就很难了，像这种遍历过程中还要进行复杂判断的就更麻烦了 |
|
z*******3
发帖数: 13709 | 28 没认真看代码，不过光看描述
是不是有一个小问题？
如果这样做的话，是不是假设只有一个装水的点？
比如
33333
30313
33333
这种其实可以装3＋2＝5unit的水
但是如果只从0那个点装水并找周边的边界的话
会忽略掉1那个装水点
所以第一步是不是先把所有相对低点给找出来
然后挨个弹出来，再寻找最低边界在哪里
同时储存所有遍历过的点
最后用最低边界高度来减去每一个遍历过的点计算units |
|
x*****0
发帖数: 452 | 29 嗯嗯，明白了。是这样的
因为对java不熟，所以都是用c做的。我的想法是这样：
(1) 遍历word one by one.
(2) 每遇到一个word，有三种情况
a. 这个word不是以 A E I O U 开头的, do nothing
b. 这个word如果是，例如以A开头。那么又分两种情况。
b1 如果这是第一个以A开头的word，用变量x记录其位置。
b2 如果这不是第一个以A开头的word，将其移到上个以A开头的word之后，并更新x。
算法时间复杂度O(N^2) N是string的长度。空间复杂度O（1）
移动一个word的算法：
http://stackoverflow.com/questions/15212749/move-a-word-in-a-st
还有另一个方法，时间复杂度要低一些。
(1) 对string中的每个word进行以比较首字母的方式排序。
(2) 然后遍历原始的string。当遇到word以A E I O U开头时，比如A。从排好序的
string中输出所有以A开头的word。
这个方法应该和你的java实现本质上差不多。 |
|
f*********m
发帖数: 726 | 30 从大牛的面经摘录的，为大家看着方便。哪位能给个code?不胜感激。
一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
似树遍历一样的方法 |
|
a*******3
发帖数: 27 | 31 第二题是找最长匹配的前缀码？还是说从某个特定位置的开始的数字串匹配到字典也算？
如果是第一种的话，可以把词典简称 trie数吧，不是以字母来建，而是以字母对应的
数字来建，这样查询数字串直接一遍遍历trie，找到最底层的，是合法word的节点就行
了。
第一题，2^40的数，如果没有重复的，那么分段计数应该是最好的方法。如果有重复的
，那么就分段写回硬盘。
比如16M内存，那么分为长度为16M为一个区间，读一遍，将每个区间单独为一个文件。
将数据写入对应的区间。
第二遍遍历每个文件，用16M做bitmap，只需要找到第一个置0的位就行了。
IO复杂度，2遍读，一遍写 |
|
d*******y
发帖数: 27 | 32 SDE for fresh grad, seattle onsite, 4 rounds.
第一轮，老印，abstract和interface的区别，我把Java语言里的区别说了半天，他不
满意。感觉他想听的是从面向对象角度出发有什么区别。coding题目：两数和，但是返
回下标最小的两个数。说了三种方法，最后让写hashmap的方法。这个题写的非常憋屈
。从一开始写函数声明的时候，老印就开始挑毛病。我返回的是一个长度为2的数组，
分别指示两个下标，老印不满意，问有没有别的方法，我说可以返回一个对象，老印还
不满意，no clue .. 瞬间感到阵脚完全被打乱了，后面的code写了一半，出bug了，老
印过来找bug，最后也没写完。
第二轮，老印，表达式求值。输入参数是一个后缀树。开始说可以后续遍历，将结果存
在栈里面，然后求值。老印说可以不需要申请栈。然后直接写了个后序遍历的方法，
code没问题。follow up，给一个反过来的后缀表达式，求值。很简单，逆序求值就好
了。
第三轮，美国人，是个新人，问的问题很水，问有关hashmap都知道什么。说了load
factor, col... 阅读全帖 |
|
n*******w
发帖数: 687 | 33 两数和
感觉是想用一个数组当做参数传进去，返回true false表示是否找到。
想到的办法
1 暴力解 n^2
2 用另一个数组存sort之后对应元素在原数组中的index，两指针头尾往中间遍历这个
index数组，直到相遇。空间 n，时间nlgn
3 建hashtable，将value map到index。遍历hashtable。 |
|
h*******0
发帖数: 270 | 34 为什么要把所以东西都写道一个函数里面呢？ 为什么不先找node，然后在打印该node
下的所有leaf呢？ 你这个drawback是每次都要遍历所有的点。 其实有些情况是不需要
遍历所有点的。 |
|
p*****9
发帖数: 20 | 35 Intern面试：
电面：
是阿三问的，不过人很好，我不会的一直在提示我，问了C++和Java的区别，C++中
virtual function，java当中的Garbage collection，更喜欢哪种语言，为什么等，又
问了两道题：
1. 两个sorted list，求相同的部分（值相同）
2. n！后面以多少个零结尾。
Onsite：
1面是两个人轮流问问题。第一个人问hashtable的实现，怎么实现hashcode（不会。。
），写个函数判断两个字符串是否是anagram，用了一个大小为256的数组，先遍历++,
后遍历--， 写完后又优化。第二个人让写quicksort，让比较mergesort和quicksort，
哪种情况用哪个最好。然后又问了leetcode的原题，sort colors，要求in place
2面第一个人问哪个数据结构比较熟，然后自己写一个函数，我说了bst，他让我写find
函数，然后又问delete如何delete。问malloc的时候需要size，free不需要size，为什
么。第二个人问travel tree by level。后面又有... 阅读全帖 |
|
J*****a
发帖数: 4262 | 36 不是啊 她还是按递归那个顺序算
比如背包问题 dp的矩阵应该一行一行的算 矩阵每个元素只要遍历一次
比如断字问题 就应该先算对角线 向左上方向遍历
而且DP都是先算小子问题 在算大子问题 顺序都是精心安排才能最大限度降复杂度
但是她还是按照递归算法访问那些子问题 所以先碰到的是大问题 因此就肯定有很多
mismatch （在hashtable里找不到） 所以复杂度肯定高了啊 |
|
t********e
发帖数: 1169 | 37 很幸运，全程没有遇到一个烙印，上周二onsite,现在还没回复，求分析。 fresh
phd, 手头有些offer.没有签任何协定，说题目应该没问题吧。。
Update: Onsite居然拖了一周回复，磕磕盼盼总算拿下了，具体package还没谈
——————————————————————————————————————
0.店面：台湾人 rsde还是applied researcher来着
0a. 一个数组里面找中位数， 复杂度
0b. 如果有m台机器，每个机器有n个数据，怎么找nm个数据的中位数，复杂度
就是个quickselect, 后面一问没怎么答好，我居然想到的是每台机器先排序，再找中
位数。。。
应该是答得很不好，在店面后两周才通知onsite.....还以为挂了呢
——————————————————————————————————————
上周2 onsite, 9:30am开始，先跟hr小聊了一下，然后等10:30的lunch interview
1. 老美，典型geek, 97年就到西雅图上班了，级别不知。 先做题目再到公司cafe吃饭
，吃饭时看窗外，从来不知怎... 阅读全帖 |
|
A**u
发帖数: 2458 | 38 别人的面经
一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
似树遍历一样的方法 |
|
c**********e
发帖数: 58 | 39 这样的话，如何判断最后一行和最后一列的每个元素是否为零呢？如果先遍历最后一行
和最后一列，只要行和列中各有一个元素为零，最后一行和列就全为零了。如果先遍历
其他的行和列，假设本来最后一行和最后一列全是1，但是被设置标记后最后一行和最
后一列有零了，无法判断这个零是否是本来就是零还是标记后才是零，也就无法得出最
后一行和最后一列元素的正确值。
因此，我觉得此方法不太对。。。
这道题不用extra space 真的有方法可以做吗？求指教 |
|
d**e
发帖数: 6098 | 40 ☆─────────────────────────────────────☆
FastOne (伤逝) 于 (Fri Jun 14 12:03:30 2013, 美东) 提到:
我是一名普通的亚马逊码农，那地方有50%的人整天干的事情就是谈最新的时髦的技术
和自己解决的多难多难的bug。我是个程序员，每天敲敲打打，哪天电脑崩溃了你会发
现我这辈子啥都没留下。
我那可爱的岳父岳母在向自己的亲戚朋友们介绍我的时候，总是轻描淡写的说，他在亚
马逊当程序员。而那帮亲戚就会说：哎呀怎么会这样呀，你家孩子从小到大成绩都好，
一直是同龄人中的佼佼者，没想到怎么最后就当了个程序员？？你们不是希望他以后从
政或是做个教授什么的吗，现在那谁谁谁可厉害了挣得老多了。。也有倒霉催的亲戚朋
友们会用一种既内行又套近乎的口气说，你能内部fake价格吗？...我想买那啥啥你能
搞到coupon吗？这时我父母通常都会脸色暗沉，应该是和父母的预期有很大落差吧。让
他们老人家失望了，自己心里也不太好受，想想自己从小到大确实一直是同龄人中的佼
佼者，高考，申请出国，一路都付出了很多的艰辛，
全家人也都对自己寄予... 阅读全帖 |
|
r*******e
发帖数: 7583 | 41 工具有很多，最常见的免费的valgrind和收费的IBM purify
不过面试应该不是问用什么工具，而是用什么思路
ref counting是一种，另一种是mark & sweep
在任意时候遍历所有的stack和global vars，看他们能reach到哪些objects，作上标记
然后遍历整个memory set，没标记而又显示in use的就是leak |
|
s*********n
发帖数: 191 | 42 这个题目的O(N)+O(1)解法太多了啊，哪需要递归和排序什么。
1，都给了数据范围那最直接的就是桶排序啊，就是leetcode那道题的所谓swap的解法。
2，再笨一点的方法可以在知道了x+y和x*y求取一元二次方程也很快啊，一次遍历完成
。缺点是容易溢出。
3，再或者用xor也可以啊，知道了x^y的值，再根据x^y中某个1的位置，对原数组分成
两类元
素分别进行xor，两遍遍历。也可以直接求出x和y啊。 |
|
R******1
发帖数: 58 | 43 我之前做的时候是【2500， 4000】，所以很快， 7s左右
刚试了试这个新的range，本来以为是线性增加，时间应该也不不大；
但是，很多target无法满足，就要遍历hash table一次。
【2500， 4000】 用时 7s 命中率1477/1500 绝大多数都很快break了
【0， 1000】 用时 1m56s 命中率445/1000 多于一半要遍历完
建议楼主试试先sort（O（NlogN)), 然后binary search （O（logN)).
2sum.txt ～4MB 所以建设1M个ints
range是【-10000， 10000】， 20000
用hashtable worst case 20000*1M
用sort然后binary search， worst case 1M*log（1M） + 20000*log（1M） ～ 20*1M |
|
s****n
发帖数: 70 | 44 Not for sure...
如果用>表示包含关系，那么如果是这种情况
i1 > i2 > i3 > ... > in
用interval tree的话查询i1要遍历所有n个叶节点，查询i2要遍历至少n-1个节点。。
。以此类推，一共要访问O(n^2)叶节点。 |
|
z****e
发帖数: 54598 | 45 dp我还没找到状态转移方程，不知道怎么个dp法
图论可解，跟leetcode上那道变态的字典题一样做
首先建图，建立所有的路径
然后从某一点开始走
广度优先的遍历
走到不能走为止，这样就是这个点出发开始走可以走的最长路径
记录下来，换下一个点
这样遍历过去，取最长点 |
|
l*n
发帖数: 529 | 46 只能遍历两个输入list一次，没说不能遍历新list多次。把新list逆序记录，有进位就
处理进位，最后再反转。 |
|
j******i
发帖数: 244 | 47 DP其实只是一种解题思路，把一个问题的最优解表达成最优子问题的解，这样其实就建
立了各个问题和其下子问题之间的依赖关系。你把每个问题想象成一个顶点，依赖关系
想象成顶点之间的有向线段，那么整个问题其实就是对一个DAG从某一个起点的遍历。
用recursion+memoization是更直观的DFS遍历，而将DAG做toposort以后确定了各个顶
点的前后关系，从后往前iterate，计算量是完全一样的，但是写起来比较难理解，不
过节省了stack空间。 |
|
l*n
发帖数: 529 | 48 呃，感觉思路超混乱啊。话说先遍历一遍建好新节点，再遍历一遍建立邻接关系，不是
很直观的吗？试图把二者搞在一起总觉得十分绕，难写更难懂。 |
|
z*********8
发帖数: 2070 | 49 没办法， 大家刷题把门槛都搞的很高， 两次遍历的人offer就被一次遍历的人给抢了
。。。 |
|
a********s
发帖数: 20 | 50 今天面Google Intern也面到了LZ说的continental divider的题。
感觉跟LZ理解的不一样，不知道我理解的对不对。 好像是找出continental divider
的点（题目中的括号）
这些点的特征是：从这些点出发，既可以连接到大西洋，也可以连接到太平洋。连接
的原则就是只能往海拔相等或更低的点流动。
这样理解好像也比较符合地理上的定义。
我当时只写出了brute force的方法，就是遍历所有点，然后DFS，看能不能即到太
平洋，又到大西洋。
面完了想想，好像可以遍历所有太平洋沿岸点，做DFS，将走到的点标记为true。然
后从大西洋沿岸DFS，将走到的点标记为true。 最后只需要找出两个都为true的即可，
好像能稍微efficient一点。不知道有没有更好的方法。 |
|
