p*****2
发帖数: 21240 | 1 来自主题: JobHunting版 - 关于尾递归
大牛谦虚了。我也是刚学。看看到底尾递归都能做什么。 |
|
p*****2
发帖数: 21240 | 2 来自主题: JobHunting版 - 关于尾递归
尾递归
def C(m:Int, n:Int):Int={
recursion(m, 0, None)(n)
}
def recursion(m:Int, i:Int, arr:Option[Array[Int]]):Array[Int]= i match{
case _ if i==m+1 => arr.get
case 0 => recursion(m, 1, Option(Array[Int](0)))
case _ => val ret=process(i,arr.get); recursion(m, i+1, Option(ret))
}
def process(i:Int, arr:Array[Int]):Array[Int]={
val ar=new Array[Int](i+1)
ar(0)=1
ar(i)=1
1 until i foreach(j=>ar(j)=arr... 阅读全帖 |
|
p*****2
发帖数: 21240 | 3 来自主题: JobHunting版 - 关于尾递归 今天问了scala group的人了，确实所有的recursion都可以转换成尾递归。这个貌似没
什么悬念了。 |
|
y****n
发帖数: 743 | 4 来自主题: JobHunting版 - 关于尾递归 加一点难度。两个函数相互递归
public static double H(double val, int n)
{
if (n == 0)
return val;
else
{
double left = V(val - 1, n - 1);
double right = V(val + 1, n - 1);
return Math.Sqrt(Math.Abs(left * right));
}
}
public static double V(double val, int n)
{
if (n == 0)
return val;
else
{
double up = H(val * 2, n - 1);
double down = H(val / 2, n - 1);
return Math.Sqrt(Math.Abs(up + down));
}
} |
|
p*****2
发帖数: 21240 | 5 来自主题: JobHunting版 - 关于尾递归
那怎么对尾递归这么熟？ |
|
p*****2
发帖数: 21240 | 6 来自主题: JobHunting版 - 关于尾递归
好呀。一起学习呀。今天准备总结一下尾递归，大牛帮助点评一下。 |
|
|
p*****2
发帖数: 21240 | 8 来自主题: JobHunting版 - 关于尾递归
这个应该比yishan那个容易很多。memoization与尾递归并不矛盾吧？ |
|
b******7
发帖数: 92 | 9 后序遍历非递归bug free就很难了，像这种遍历过程中还要进行复杂判断的就更麻烦了 |
|
|
g***9
发帖数: 159 | 11 RT. 只看最后递归的call是不是原函数吗..
有么有可以debug之类或其他方法来确认? 谢谢! |
|
p*****2
发帖数: 21240 | 12
好久没研究了。当时稍微研究了一下尾递归，感觉还是挺麻烦的。 |
|
|
|
|
|
|
f********4
发帖数: 988 | 18 刷题的时候总是忍不住看答案。。结果面试时候一遇到没写过的递归，就紧张。。哎。
。。智商真令人捉急。 |
|
s*****e
发帖数: 1679 | 19 对递归还是了解不透彻啊，感觉似懂非懂，有谁给指导下？ |
|
j*****n
发帖数: 1545 | 20 很多 算法 递归写出来 实在是漂亮。就是 debug 太难了。。。 |
|
|
|
m******s
发帖数: 204 | 23 最差情况分析：
参见http://leetcode.com/2011/09/regular-expression-matching.html：
zhong zhang提到运算时间较长的情况：
s[] = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
p[] = "a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*b"
注意这个例子没法early out,假设s的长度是n，不考虑p的长度，那么递归的时间函数
表达式近似是：
T（n） ＝ T（n－1） ＋ T（n－2） ＋。。。
所以T（n）是2^n.
请指正。 |
|
|
s********u
发帖数: 1109 | 25 哦我大致明白了，就是通过space cost来换取time cost的，就是dp？
比如这个题：
给一个bool IsWord(string)的API, 判断能否把一个string分割成单词， 并给出所有
的答案。
如果要求用dp的话，递归还是要比循环好写很多吧。。 |
|
z****e
发帖数: 54598 | 26 dp就是数学归纳法，从前面已知的结果推导出当前的结果
循环一般比递归节省时间和空间 |
|
s*****h
发帖数: 155 | 27 你说的cache的这种属于自顶向下的DP，应该算是递归，需要一个global var
CLRS专门有一章讲DP的，有背包，编辑距离以及折棍子几个例子，讲得很清楚 |
|
s*****r
发帖数: 108 | 28 DAG 是有向无环图
有了 toposort 才知道应该怎样从前往后递推
否则的话得写记忆话搜索
所以进行 DP 通常这两种实现；知道了自底向上的顺序用递推
不知道又不想拓扑排序后再推就用递归 用这种形式感觉不怎么动脑子把转移方程放那
开头判断个边界就好了 好像显得没有递推实现高端
上面的回复大多不准确或者错误的
直到 jianglai 说到了本质 引入了拓扑排序好像蒙了一下 但把模型转化为 DAG 是
必要的 只是我们刚开始碰到的 DP 大都划分阶段显然 知道了推的顺序 其实在一些树
或图上的 DP 不容易递推实现 因为要么得先拓扑排序从边界开始向后推 要么用了巧妙
的实现方式那是非常值得一读的程序 |
|
s***e
发帖数: 403 | 29 DP是剑法
递归是内功
相同的剑法可以用不同的内功驱动
就是这个意思。 |
|
s********u
发帖数: 1109 | 30 之前有人放过这个题，就是提供一个bool isWord(string s)的函数，要求得到一个
string拆成若干个word的所有组合，word之间用空格隔开。
自己写了下，用递归 + memoization，想问问这个题有iteration的做法么？如果是每
个string有唯一解（只有一种拆法）呢？
vector wordBreak( string str, map >& cache){
vector vs;
if( str.empty() ){
vs.push_back(str);
return vs;
}
if(cache.count(str) > 0)
return cache[str];
string prefix;
string suffix;
vector segSuffix;
for( int len = 1;len <= str.s... 阅读全帖 |
|
|
s********u
发帖数: 1109 | 32 如果compiler如此智能的话，可以随便用递归而不用考虑效率了吧。。反正overlap会
自动解决
n |
|
s********u
发帖数: 1109 | 33 嗯，在理论上我是这么总结的：
**Divide and conquer :** 将问题分成几个部分，每一部分问题互相不重叠，假定每
个部分都可以得到解决进行递归调用，合并每一部分的结果。例如Merge Sort,Quick
Sort。
**Dynamic Programming**：对于具备最优子结构以及子问题重叠特性的问题，尽可能
不重复计算每个subproblem，将计算结果存储下来，以确定后驱问题的结果。与贪心算
法的区别是，在计算后驱问题时，可能会reconsider前驱问题的解，从而改变全局path
。
**Greedy Algorithm** : 当前问题的最优解只取决于前驱问题的最优解，即局部最
优解推广至全局最优解。如Dijkstra算法。
**Backtracking**： 一种暴力（穷举）的深度优先搜索法，直至检索到节点空间的尽
头。Tree或Graph的DFS，是backtracking的special case。
但实际上很多问题就算满足dp的条件，用dp却非常繁琐，比如8皇后问题，或path sum
问题。是可以用dp做，但实际上没必要。用b... 阅读全帖 |
|
s******y
发帖数: 416 | 34 DP和递归不是一个层面的概念，不能比较适用范围… |
|
j******o
发帖数: 4219 | 35 很长的一段时间以来，大家普遍认为都认为迭代好于递归 |
|
d**e
发帖数: 6098 | 36 我觉得是先写递归，除非要求写迭代。
因为首先是需要说服人家你的算法是对的，所以先用比较简单直观的做法令人容易理解
来说服他／她。
又除非那个算法迭代就已经很简单易懂，比如fibonacci。 |
|
a**********0
发帖数: 422 | 37 原因找到了 递归method之中有一个线性的操作 这样会导致整体的n平方复杂度 |
|
a**********0
发帖数: 422 | 38 你的递归中没有O（n）的操作 我的有 所以用 length不好 应该直接给出最后一个节点
的指针 |
|
w********s
发帖数: 1570 | 39 为啥湾区的面试都搞那么复杂的?
国内面试就问问语言知识，过去项目，哪来那么多递归，dp？你干活的时候用过么？ |
|
|
g*********e
发帖数: 14401 | 41
毫不扯淡。
比如你有个有向图，图里每个node都可以是一个小图，你要给这个大图做优化，递归最
好写。
还是这个图，求它的topo order算dependency，就得dfs。
电路里面做静态时序分析，那都是dp。
用位来存储一些数据结构，或者做查找表，节约空间。更抠的还有把flag存到指针低位
的 |
|
a*******m
发帖数: 626 | 42 哪这么简单，只能说你面过的国内公司太少。
国内问项目实践多，感觉还是湾区这边简单，靠刷题就可以。在国内只靠刷题基本没戏
，更看重有没有真的做过东西。
为啥湾区的面试都搞那么复杂的?
国内面试就问问语言知识，过去项目，哪来那么多递归，dp？你干活的时候用过么？ |
|
z**a
发帖数: 69 | 43 好角度，写了个，过了LC，差不多是非递归中序遍历二叉树的思路。
class Solution {
public:
class stack
{
public:
char c;
int flag;
stack(char c, int flag)
{
this->c = c;
this->flag = flag;
}
};
vector generateParenthesis(int n) {
int left = 0;
int right = 0;
vectorrecord;
vectorresult;
stack temp(0,0);
record.push_back(stack('(', 0));
le... 阅读全帖 |
|
|
C********e
发帖数: 492 | 45 也算吧，
比如inorder遍历tree，不论是用stack还是递归，其实都是logN的space复杂度
真正的O（1）space解法，需要靠morris算法来 |
|
a*****a
发帖数: 46 | 46 如果递归算空间的话，怎么O(1)判断一个链表是不是palindrome? |
|
|
s**********5
发帖数: 19 | 48 递归转iterative用stack
public int depthSum2 (List input){
Stack> nstack = new Stack<>();
Stack dstack = new Stack<>();
nstack.add(input);
dstack.add(1);
int total = 0;
while(nstack!=null){
int depth = dstack.pop();
for(NestedInteger i: nstack.pop()){
if(i.isInteger()){
total += i.getInteger()*depth;
} else{
dst... 阅读全帖 |
|
t******4
发帖数: 134 | 49 加一个parent指针？ or
加一个域标识root？
如果不能修改数据结构
送进函数之前特殊处理root，处理完进去递归
：目的是对根的处理和其他层不一样，需要保留判断条件。
：送之前存一个当然是搞笑了。
：多一个参数可行，就是看起来怪怪的，调用的时候传递两个相同参数。如果只允许一
个参数，有没有别的办法？ |
|
s****a
发帖数: 794 | 50 用到递归 dp的时候公司再去招个会写的？
要是用平时工作做标准的话，招个高中生就够了 |
|
