leetcode中学习recursion

leetcode

---

• N00t大神的recursion出神入化
• LC中大量的recursion解法
• recursion的关键在于代码结构, 以及param/return.

recursion的种类

简单的分有

1个rec. 以及简单三明治关系.

void rec(){
    codeTD;
    rec();
    codeBU;
    }

• 这里面的codeTD可以看作是walk DOWN the tree, codeBU理解为walk UP the tree.

1个rec. 但是在for loop里面的话, 会更有意思.

void rec(){
    if (lastRow)
        res.add(path + s);
    for(i = 1; i < path.size(); i++){
        rec(path.append, res);
        path.delete;
    }
}

• 这在restore IP的N00t的第一个解法中遇到.

1个recursion, 这次是在for each() 括号里面. 更有意思啦

List<List<?> segmentRec(String s) {
    // do something
    for ( i ) {
        rest = s.substring(i)
        for (List<?> seg : segmentRec(rest)) {
            // do something
        }
    }
    return result;
}

• 这个是在word segment里面用到.

2个连续rec call. 有param, 有return

int DFS(a, sum, minSum) {
  sum += a;  // walking down the tree.
  if (lastRow && sum < minSum)  return sum;
  else {
    minSum = DFS(a, sum, minSum);  // 注意这里的赋值是minSum, 而不是其他var name. 所以跟着的第二条recursion中的minSum才会update.
    minSum = DFS(a, sum, minSum);  // 这里的minSum用于DFS的return.
  }
  return minSum; // walking up the tree.
}

• 这个在triangle Path Sum中的N00t的第一个解法.

  • 注意这里的minSum既是recursion method的param, 又是param的返回值. 这在recursion中很常用. 可以记录在触底反弹的时候不断update这个值.
  • 因为rec有返回值, 而且复制给同一个var(minSum). 因为2个recursion的话, 第二个rec中的param会在第一个rec算完后update. 所以这一套组合拳就能在Traversal tree中不断update. 也就相当于brute force的找所有组合的极值.
  • 这就体现出recursion的意义: 有目的, 有结构的遍历符合规则的结构的所有path. 例如triangle Path Sum就是想要找DFS path的最小路径. 而不是随便一个乱序的路径.

• 还有个很好的例子就是flatten Binary Tree的九章算法模版.

  • recursion中有param不一定必须return. 主要修改就OK了.
  • 关键在于2个recursion的时候, 第二个recursion计算的root
  +

2个不连续的rec call. 中间有code. 注意N00t和programCreek的一点区别

Node rec(l, h) {
  mid = lo + (hi-lo)/2;
  leftNode = rec(lo, mid-1);
  middleCode;
  rightNode = rec(mid+1, hi);
  return root;
}

• 这在Sorted list to Binary Tree里面用到了.

3个rec call, 中间有code, 有param, 有返回.

DFS(tri, row, col, HashMap){
    // base condition
    return min;
    if(Map.contains())
        min+= Math.min(DFS(Hashmap), DFS(Hashmap));
    else 
        min+= Math.min(map.get(), DFS(HashMap));
    map.put(row, min);
    return min;
}

• 在Triangle Path Sum的DFS recursion解法里面用到. 注意这里的Math.min()里面的第二个DFS的map已经在在第一个DFS中改变了.
• 记住: java永远是call by value.
  
  • 所以primitive 的话不会改变. 于是必须return. 所以在Triangle Path Sum中的第一个解法必须return, 然后第二个recursion的minSum才是改动过的.
  • 如果是object, call-by-value的是地址. 所以可以改动. 于是不需要return. 就如Triangle Path Sum里面的DFS解法的map. 这里的map是重复使用(update)的.
  • 其实这里就是段公子说的用HashMap来代替array保存DP结果更有通用性. array其实是最简单的HashMap, 即key是index, value则是a[i].