l****c
发帖数: 782 | 1 So, I think that another BULL GUY is using recursive to push_back the lower
layer's values into container. And when it reaches the lowest level begin
to print, then the 2nd lowest layer's values printed.
I am trying to use non-recursive means. From the highest level, push the
node into a queue (for next level) and a stack for final printing. When the
level popped out from the queue increases to the lower level, check whether
it is the objective. If yes, stop and print everything in the stack. B... 阅读全帖 |
|
m*****n
发帖数: 204 | 2 严格地说，recursion + 中间结果记录应该叫memoization.
Bottom-up non-recursive的做法才叫dynamic programming. |
|
p*****2
发帖数: 21240 | 3 我记得在我没学过DP以前，Google一位大哥电面给我出了一道最简单的DP。那是我第一
次见DP，上来先晕了一下，用greedy来解的（当时也不知道greedy算法，只是思路自然
想的）。然后他说不对，给了我个反例，我突然发现需要用recursion来做。最后写了
一个recursion的过了。
后来才知道这种题就是DP。 |
|
p*****2
发帖数: 21240 | 4
我觉得DP题不能用recursion来解的话就能filter掉不合格的程序员了吧。recursion还
是基本的编程逻辑吧。 |
|
d**********x
发帖数: 4083 | 5 别的不说，浏览器代码里面全是recursion。要parse一棵dom tree，不用recursion写
出来的代码可以去shi了 |
|
p*****2
发帖数: 21240 | 6
标准dp不准recursion不准backtracing
有这么一说吗？
有些DP recursion更好吧。我记得这次GCJ一题就具备这个特点。 |
|
M*****a
发帖数: 2054 | 7 发信人: peking2 (myfacebook), 信区: JobHunting
标 题: Re: leetcode过的一代工程师
发信站: BBS 未名空间站 (Sun Aug 12 14:38:00 2012, 美东)
我觉得DP题不能用recursion来解的话就能filter掉不合格的程序员了吧。recursion还
是基本的编程逻辑吧。 |
|
a*******y
发帖数: 1040 | 8 how? if you mean recursion, I cannot think of a way to keep this in the
recursion. |
|
h*****n
发帖数: 188 | 9 I had a typo, the recursion should be multiplications
T(n) = \sum_i=0^(n-1) T(i)*T(n-1-i)
catalan numbers is correct, the recursions shows how "catalan numbers" are
calculated. |
|
b*****o
发帖数: 715 | 10 iteration != recursion.
Take a very simple example of computing Fibonacci array:
(1) This is recursion, but NOT DP:
int fib(int n) {
if (n <= 2) {
return 1;
}
return fib(n-1) + fib(n-2);
}
(2) This is DP:
int fib_dp(int n) {
int a = 1;
int b = 1;
int sum;
for (int i=0;i
sum = a + b;
a = b;
b = sum;
}
return sum;
}
stored |
|
j******2
发帖数: 362 | 11 那就是说，DP问题必须是最优化问题。像在有路障的格子中找有多少种路径，一个
boolean expression有几种打括号以得到true，8皇后，running up stairs...这样
count ways的题，就都不可能是DP了，只能算是有memoization的recursion
按照最优化子问题的标准，150这本书的第九章，Dynamic Programming and Recursion
里的11个问题没有一个是符合的。只有17、18章有两题算DP。 |
|
p*****2
发帖数: 21240 | 12
不对。这题我感觉recursion更快一些。过大数据比较容易。但是你要加DP才行。
DP分两种，recursion也可以DP。今天有人发了相关的帖子，你看看就明白了。 |
|
l****c
发帖数: 782 | 13 加DP的recursion是指 dp_table[m][n] = foo(...m-1,n|| ...m,n-1)吗？
我用的是不好的recursion。。。。 |
|
w*********0
发帖数: 48 | 14 如果我理解的对的话，dynamic programming有top down和bottom up两种，分别在
recursion和iteration中记录subproblem结果
很多情况下我只能做到top down的，bottom up的怎么想都不直观。但是效率的话，应
该是bottom up好一些吧。。。
发现150题里大部分这种问题都是用的top down。但是我们学校开的一门算法课，大部
分给的例子都是bottom up的。
大家觉得有必要一定写成bottom up么？或者换一个角度 是不是能iterative解的问题
最好不要recursive解呢？ |
|
|
|
a********x
发帖数: 1502 | 17 我觉得思路对头，可以用recursion来算
public static double log2(double x) {
if( x - 1 < epsilon ){
return (x-1)/ln2; //base case 泰勒级数
} else{
return log2( Math.sqrt(x) ) * 2; // recursion
}
printf( " %d ", x/2);
}
问题在于需要hard code 常数 ln2
好像见过
log2(n)=log2( (sqrt(n))^2 ) =2 log2(sqrt(n))
不过这样子只能算整数
比如8的根号是2.。。这样子= =“ |
|
a********x
发帖数: 1502 | 18 我觉得思路对头，可以用recursion来算
public static double log2(double x) {
if( x - 1 < epsilon ){
return (x-1)/ln2; //base case 泰勒级数
} else{
return log2( Math.sqrt(x) ) * 2; // recursion
}
printf( " %d ", x/2);
}
问题在于需要hard code 常数 ln2
好像见过
log2(n)=log2( (sqrt(n))^2 ) =2 log2(sqrt(n))
不过这样子只能算整数
比如8的根号是2.。。这样子= =“ |
|
f*****e
发帖数: 2992 | 19 我的答案是二分查找，判断
1)a[n/2-1]>a[n/2]>a[n/2+1]，则最大值在左边，recurse on left
2)a[n/2-1]
3)a[n/2-1]a[n/2+1]，con~! you have found the largest number |
|
S********t
发帖数: 3431 | 20 FYI, a good candidate, after solving this particular problem, should also
figure out how to convert any recursive code into non-recursive code (via
explicit stack) in general |
|
c********t
发帖数: 5706 | 21 建一个map, key是认识人数，value是人，就是认识i个人的所有人在一个value
当从list删除这个人的时候，更新他认识的人的list，如果他认识的人变的<5,
recursion 删除这个人，他不认识的人如果是认识总数=n-5的，从map中找到他们
recursion 删除，总人数n--。应该是n+m的复杂度吧 |
|
C***U
发帖数: 2406 | 22 code看这里
http://blog.sina.com.cn/s/blog_60b5450101019v71.html
思路是这样的
比如你有101和110
那么你要把都是1的那些位拿出来，因为这些为相加会进一位，需要用&
这个例子里面百位都是1，所以他们相加变成0，所以进以为。那么我们就取出100 然后
进以为得到1000
然后呢你需要把剩下那些没有加的拿出来，都是0的不用拿出来，因为相加是0，所以你
就用xor把对应位置不同的位拿出来
然后再把这两个相加就是需要求的和了，这里用到recursion。
然后很容易就能说明剩下的那个数总是越来越小，最后变成0的
所以你结束recursion的条件是小的那个是0的时候，那就返回大的那个数字 |
|
d*******d
发帖数: 2050 | 23 sigh,怎么会这样。好吧，详细说一下面试这些intern的过程吧。
这是个algorithm & coding section（也就是说还有其他section).
2个coding题，题目是公司指定的，顺序问法面试官自己掌握。
1个小时。
最开始5分钟，自我介绍，说说你上过的课，说说你最喜欢的课程（有一半人说的是算
法和数据结构），做过的project等等。
然后5-10分钟，问做过的project，看看是不是真参与了，弄懂了。到目前为止，大多
还不错，个别人很腼腆，问一句答一句。
然后10-15分钟，第一个coding题，10到20行。很简单，没有任何tricky,考察是否能用
简历上claim会的语言编程。版上的混2个星期都该没问题。但是，目前为止，没见过一
个bug free的。一半以上的人，完全不考虑任何edge case。
这个时候，因该已经过去大约25分钟了。
第二个coding题，也是版上反复出现过的经典入门级题目，是个人都该会。要用到
recursion。coding 10-15行。
为了引导candiate的思路到recursion上来，我会花10分钟问问他们学过的... 阅读全帖 |
|
l****c
发帖数: 782 | 24 我想用个recursion，string碰到最后或是碰到".",取之前的部分转成int比较，有大小
了就返回，没有大小了就recursion到下一部分。 |
|
l****c
发帖数: 782 | 25 recursion+stack?
1.从上往下读children，输入为root，只要不为空，将children存在vector里面，推入
stack
2.直到输入为空，跳出recursion，
4.读stack？ |
|
d*****y
发帖数: 1365 | 26 来自主题: JobHunting版 - 问一个问题 recursive 相对于iterative的算法都有啥优势啊?
我就回答了说recursive的code会简单点,可能会在内存里面体积比较小.
interviewer说还有其他优点,我踌躇半天,还是没任何clue... |
|
h****n
发帖数: 1093 | 27 举一反三，将来必定又是一个大牛啊
贴贴我的代码：
class Solution {
public:
int numDistinct(string S, string T) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
//return recursive(S,T);
return DP(S,T);
}
int DP(string S, string T)
{
int m = T.size();
int n = S.size();
vector >matrix(m+1, vector(n+1,0));
int i,j;
for(i=0;i<=n;i++)
matrix[0][i] = 1;
... 阅读全帖 |
|
h****n
发帖数: 1093 | 28 写了三个方法，一个是递归，一个是naive方法，一个是用指向指针的指针来构建
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
ListNode* res;
//Method using pointer to pointer
res = P2PMethod(l1,l2);
//res = recursive(l... 阅读全帖 |
|
l***i
发帖数: 1309 | 29 assume all nodes are distinct
1. recursively find maxL and minR, which are max element in root->left
subtree and min element in root->right subtree
2. if maxL > minR, then these two are swapped elements
3. if maxL > root value, then maxL is swapped with root
4. if root value > minR, then minR is swapped with root
5. the only case remain is maxL < root < minR, in this case recurse on both
root->left and root->right because the two swapped nodes must be in the same
subtree now. |
|
b*****s
发帖数: 36 | 30 一周前面的，今天收到HR邮件说onsite挂了，于是奉上完整的面经回报本版。
我自己是fresh master，9月份在他家官网的上投的New Grad的码工职位，一个月后收
到电面邀请。面过他家的朋友都知道，他家有一个非常奇葩的HR技术电面，就是HR给你
问十几个非常简单非常基础的技术问题，大部分问题都是一两句话可以回答。HR自己并
没有技术背景，所以不必罗嗦只需要给关键词即可。答完这十几道题之后，HR会告诉你
通过了，然后会给你安排正式的技术电面。HR问题的题库有前辈总结过，下面这个链接
可以找到这个pdf。我的经验是，我被问到的题95%都是题库，所以把题库看一遍就行了
。 http://ishare.iask.sina.com.cn/f/33739828.html
接下来是跟他们广告组的一个manager电面。上来问了几个behavior的问题，包括“你
最近做过什么有挑战的project”这类问题。然后问了一个“从浏览器输入一个url按回
车之后会发生什么事情”，这个问题也多次出现在之前的面经当中。最后在Collabedit
出了个“反转链表”的题，我向他询问是需要iterat... 阅读全帖 |
|
|
|
l*****a
发帖数: 14598 | 33 想想callstack.
递归调用就是一层层压栈 |
|
b***m
发帖数: 5987 | 34
嗯，比如binary tree的post order traversal用iterative就很麻烦。 |
|
|
|
|
|
b*2
发帖数: 94 | 39 来自主题: JobHunting版 - 亚麻电面！ 亚麻电面！
一面：给一个Set of word, 查找某一个词是否在这个set里。
追问set size，面试官说很大。我：用trie。
如果很小？我：hash
面试官：如果set 超大但是内存很小怎么办
追问other solution.. 我还有说sort string, 然后用Binary search.
再问，如果well sorted set, 让我找区域范围，比如找(inclusively) 包含cat到dog
的范围。得瑟。。问这么多。
然后就是传说中的deck of card. 聊得很开心。肯定是好评~撒花~
二面：接电话以后，从第一句就没听清对方说啥，印度哥哥……
从上学到上班，同学同事印度人不少，按理说已经培养出来了，这位口音之重实在是太
！坑！爹！了！他介绍了一大通他现在的工作，我除了知道他在warehouse那里弄什么
internal tool以外，完全的沟通障碍。。 他让我写 从大到小打印binary search
tree.. Are u kidding me?.. 我问要iterate还是 recursive.. 答：recursive… …
…… 这难... 阅读全帖 |
|
a*******6
发帖数: 520 | 40 如果是要maximize期望，下面这个DP（倒过来就是back track）就可以了
n : 假设总共最多扔n次
f(i, m) : 在第m次扔到i时，往下继续的最优解 (0 <= m <= n)
initialize: f(i, n) = i ( i = 1, 2, ..., 6 )
recursion : f(i, m) = max(i, (f(1, m+1) + f(2, m+1) + ... + f(6, m+1))/6)
--initialize的含义是：如果是最后一轮只能扔到什么算什么
--recursion的含义是：前面几轮可以在不继续扔（f(i, m) = i）或者继续扔间做个决策
第一次如果扔到x，就按以上DP的解f(x, 1)决定后面的策略
如果最优策略是继续且第二轮扔到y就参考f(y, 2)，依次类推 |
|
p*****2
发帖数: 21240 | 41 面试题总结(1) - 面试题的构成和分类
首先声明一下，这里的面试题主要所指数据结构和算法的题目，题目的分析集中在
Leetcode上面的题目上。
我认为一道面试题由以下几个方面组成的
Question
Data structure in question
Data structure in solution
Algorithm in solution
Coding
题目：非常关键，一个题目通常有一些相应的变形题目，同一个题目可能有不同的要求
。比如时间复杂度，空间复杂度的要求，比如recursive, iterative的要求。而根据题
目的变形与要求，可能会极大的影响到你能够采取的数据结构和算法。
问题中的数据机构：问题中有可能带数据结构，有可能没有数据结构，有可能是可以自
定义数据结构
解决方案中的数据结构：可以是in-place的，也就是利用已有的数据结构，也可能是创
建新的数据结构。新的数据结构跟已有的数据结构没有必然的联系，而很多问题都是一
题多解，可能采取不同的数据结构。
算法：一般来说，当解决方案中的数据结构确定以后，算法也就确定了。同样，一旦解
决方案的算法确定，相应... 阅读全帖 |
|
z*****e
发帖数: 231 | 42 some thoughts about the first question:
recursively determine if the left substree and right subtree is the same.
Also to avoid the recursive call on the same node multiple times, use the
hash table to store the visited node.
What is the exact question for the second one? |
|
c*****a
发帖数: 808 | 43 用recursion会不会被人看不起啊...很多题，recursion解法比较make sense |
|
b*****n
发帖数: 482 | 44 我其实最近才开始做leetcode，一周时间，到现在刚好50题。我先来抛块砖吧，讲讲自
己的体会：
1. 先看思路领会透不透。譬如说peranthese matching, largest rectangle, maximum
rectangle 这些题。还有kth largest, median of two sorted arrays。特别是
median of two sorted arrays，思路和细节吃透了， 再要写一遍的话，bug free并不
算特别难。当然我是指“再写一遍”。我知道peking2的目标可能是没见过面的5分题一
次写对:)，那可真得下功夫。
2. 再看固定模式熟不熟。tree的recursive，string matching的dp，math里用的移位
和二分法，数组的左右指针，单链表的双指针traverse/delete。这些基本的东西要有
敏感度。
3. corner case要cover够。空指针，0长度，integer记住有负数，unsigned包括0，
duplicate怎么处理，会不会overflow，out of range，loop能不能... 阅读全帖 |
|
b*****n
发帖数: 482 | 45 我其实最近才开始做leetcode，一周时间，到现在刚好50题。我先来抛块砖吧，讲讲自
己的体会：
1. 先看思路领会透不透。譬如说peranthese matching, largest rectangle, maximum
rectangle 这些题。还有kth largest, median of two sorted arrays。特别是
median of two sorted arrays，思路和细节吃透了， 再要写一遍的话，bug free并不
算特别难。当然我是指“再写一遍”。我知道peking2的目标可能是没见过面的5分题一
次写对:)，那可真得下功夫。
2. 再看固定模式熟不熟。tree的recursive，string matching的dp，math里用的移位
和二分法，数组的左右指针，单链表的双指针traverse/delete。这些基本的东西要有
敏感度。
3. corner case要cover够。空指针，0长度，integer记住有负数，unsigned包括0，
duplicate怎么处理，会不会overflow，out of range，loop能不能... 阅读全帖 |
|
G****A
发帖数: 4160 | 46 3. 判断这个二叉树是不是平衡树
recursive, top-down, O(n^2)
4. 优化3.
recursive, bottom-Up, O(n) |
|
c*****a
发帖数: 808 | 47 "Whenever the function calls itself recursively all local variables remain
on the stack and a new set of them are pushed to the stack for the new call.
This means that you care how many calls are there at most, in other words
what is the maximum depth of the recursion." |
|
b*******e
发帖数: 217 | 48 for (2): you are right.
recursive fucntion:
exist(i, a1, a2) = { exist(i-1, a1-xi, a2) ||
exist(i-1, a1, a2-xi)}
starting form i = 1 a1 = 1, a2 =1
end at i = n and a1 = a2 = sum/3.
complexity: n * (sum/3)^2.
don't quite understand (1). any example?
when start froming i = 1 to i = n, the recursive structure ... should be
able to gurantee that xi will only be used for once?
my solution: 3d np. |
|
e****e
发帖数: 418 | 49 我不明白。。。
首先，用你的odd/even two pointers从数组第一个元素遍历完，得到的结果应该是
A = {7,3,5,2,4,6,8,10}， 可以看出有些偶数位置也是错的。
其次，看不出为什么用stack，从例子可以看出，奇数的所在位置并不是正好和预期结
果是逆序。
最后，用了stack,并且存放奇数， 就是需要额外的O(n)空间了。
你这个用recursion作为可利用的额外空间的想法挺好，应该有些题可以借鉴，虽然我
没有在你的方法里看到recursion函数和函数调用。。。
positions |
|
r*******n
发帖数: 3020 | 50 可以，
result = []
1 left, right = partition // the elements in right > that of left
2 if sizeof(right) > k
drop the left, recursively call on the right.
else if sizeof(right) < k
k = k - sizeof(right)
append the right to the result.
recursively call on the left.
else
append the right to the result.
the end.
|
|
