Report: Interleaving String

标签（空格分隔）： Lintcode DP Ladder

题目

• 题目链接

思考

first trial: fail

• F[i][j]表示是否可以用S1, S2的前i,j个字符表示S3的前i+j个字符. 既然是M x N的DP, 自然要先init 第一行和第一列.
• 然后就是optimally equation. 就是每次看S3的i+j-1个字符是否等于S1的i-1或者S2的j-1. 如果是, 就沿用F[i-1][j]或F[i][j-1].
• 但是这样fail在第15/18个test case:

  1

  ["sdfjas;dfjoisdufzjkndfasdkfja;sdfa;dfa;dfaskdjhfasdhjdfakhdgfkajdfasdjfgajksdfgaksdhfasdkbfjkdsfbajksdfhakjsdfbajkdfbakdjsfgaksdhgfjkdsghfkdsfgadsjfgkajsdgfkjasdfh", "dfnakdjnfjkzghdufguweygfasjkdfgb2gf8asf7tgbgasjkdfgasodf7asdgfajksdfguayfgaogfsdkagfsdhfajksdvfbgkadsghfakdsfgasduyfgajsdkfgajkdghfaksdgfuyadgfasjkdvfjsdkvfakfgauyksgfajkefgjkdasgfdjksfgadjkghfajksdfgaskdjfgasjkdgfuyaegfasdjkfgajkdfygadjskfgjkadfg", "sdfjas;dfjoisdfnakdjnfjkzghdufguwdufzjkeygfasjkdfgb2gf8asf7ndtgbgasjkdfgasodf7asdfgfajkasdksdfguayfgaogfsdkagfsfjadhfajksdvfbgkadsghfa;sdkdsfgasduyfgajsdkfgafajkdghfaksdgfuyadgfas;dfjkdvfjsdkvfakfgauyksa;dgfajkefgjkdasgfdjksffaskdjhfasdhjdfakhdgadjkghfajgfkajdfksdfgaskdjfgasjkdgfuasdjfgajksdfgaksdhfasdkbfjkdsfbajksdfyaegfasdjkfgajkdfygadjskfgjkadfghakjsdfbajkdfbakdjsfgaksdhgfjkdsghfkdsfgadsjfgkajsdgfkjasdfh"]

应该return false, 但我return true.
找了好久, 终于发现问题了: 我的递推方程是:

1
2
3
4
5
6
7
8

if (s3.charAt(i + j - 1) == s1.charAt(i - 1)) {
  F[i][j] = F[i - 1][j];
} else if (s3.charAt(i + j - 1) == s2.charAt(j - 1)) {
  F[i][j] = F[i][j - 1];
}
else {
  F[i][j] = false;
}

注意这里: 如果s1.charAt(i - 1)和s3.charAt(i + j - 1)和s2.charAt(j - 1)相等的话, F[i][j]是给else if覆盖了. 所以有时候对有时候错. 所以是我的optimally equation写错了. 这里是or的关系.

2nd trial: AC

• 这次解决了这个bug. 使用OR来得到F[i][j].

3rd trial: fail

• 虽然刚才那样做是可以AC, 但是空间复杂度太大! 因为这个只和上一层跟左一列有关系. 所以可以用1d的rolling array来做. 那为什么这里和distinct subsequences的1d不同, 是自左向右循环呢? 分析如下:
• update的时候要看是否使用更新前还是更新后的上一层的信息.
  • 例如distinct subsequences就是使用更新前的上一层信息, 所以内循环是自后往前.
  • 而像Interleaving string的1d rolling array就是自前向后.
  • 这2个有什么区别呢: 区别在于optimally equation, 看到底需要上一层的哪个数, 如果是上一层的左边, 那么就不能覆盖的循环, 所以要自后向前. 而且若是同时需要上一层左侧和这一层左侧的话就不能用1d滚动数组了, 用mod rolling.
  • 总结见下图:
• Ganer就是这样写的. 但是我一开始先是像distinct substring那样写: 即内循环是从后向前来update State. 结果是错的.
  • 所以这里有个重要事情. 什么时候是自前向后, 什么时候自后向前. 这里并不是说Top-down, Bottom-up. 而是说1d rolling array里面是使用更新前还是更新后的值.

    每次迭代我们只保存了上一行的信息。接下来从前往后还是从后往前就取决于我们要用的是更新前还是更新后的信息，如果从前往后，我们会使用更新后的信息

4th trial : AC

• 这题和distinct substring 的 rolling array的内层循环不同的是: 这里是从前往后.

标签（空格分隔）： lintcode BFS BinaryTree

题目

• link点我
• Example
  An example of testdata: Binary tree {3,9,20,#,#,15,7}, denote the following structure, Our data serialization use bfs traversal:

  1	使用code block可以保留格式 3 / \ 9 20 / \ 15 7

分析

Serialize

• 注意这个是Lintcode的Serialize, 和Leetcode的区别在于他使用的是BFS. 而后者则是使用的pre-order DFS.
• null object 和 null的区别.
• flag的设计: 要有初始值, 在进入循环的时候update, 对于每一个节点再次update. 那么当这一层结束后就是有效的flag.

De-serialize

• 还是使用BFS解决. 和Pre-order的de-serialize一样, 和各自的Serialize有一个一一对应的关系.
• 第一次写的时候出现idx超出array size的问题. 这是为什么呢? 因为我在判断token[idx]的时候居然判断了4次. 因为每一次判断都要idx++. 然后我把4个if并成2个if…else就OK了.
• 注意这个时候的while loop判断不是parents queue是否为空, 而是判断token[] array走完没有. 我一开始这里搞错了, 居然去判断string走完没有. 注意string就是char Array. 例如{3, 9, 20, #, #, 15, 7}, 这个string的length是21. 而token[]则是7.
• 还有注意这里update parents queue的时候要注意. 这里的做法是对于”#”, 则不加入null到queue. 不然queue的size()就不对了. 因为这里不用traverse null node.

code

1. Serialize Binary Tree : BFS遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

public static String serializeBFS(TreeNode root) {
    if (root == null)
        return "#";
    String ans = "";
    Queue<TreeNode> parents = new LinkedList<>();
    parents.offer(root);
    boolean end = false;
    while (!parents.isEmpty() && !end) {
        end = true;
        int size = parents.size();
        for (int i = 0; i < size; ++i) {
            TreeNode head = parents.poll();
            // update result
            String thisnode = "";
            if (head == null) {
                thisnode = "#";
            }
            else {
                thisnode = head.value + "";
            }
            if (ans.length() == 0) {
                ans = ans + thisnode;
            }
            else {
                ans = ans + ", " + thisnode;
            }
            // update queue
            if (head != null) {
                if (!head.isLeaf())
                    end = false;
                parents.offer(head.left);
                parents.offer(head.right);
            }
        }
    }
    return ans;
}

1. De-serialize binary tree
   还是直接link github代码好了.
   试了几个方法. 最后还是觉得使用gist-it方便. 但是前提是代码不能有中文. 否则python解析不了.

• 今天开始讲Dynamic Programming.
  • 先讲的前2个常见的DP类型题: Matrix DP和Sequence DP.
  • 下一节课再讲后2个DP类型题: 2 Sequencee DP和Backpack.

DP的实现方式:

1. top-down的recursion: memorization search
2. bottom-up的iteration或者recursion.

如何想到使用DP

• 虽然和recursion都是使用了子问题解决大问题. 不过动归是一种算法思想, 而递归则如同Algs4书本所说: 是一种organize代码的方式.
• 我感觉段老师这里所说的动归是指严格的动归, 他将memorization search作为广义的动归, 到底还是search.
• 如何想到使用动归
  • 满足其中一个条件:
    1. 求极值
    2. 判断是否存在
    3. Count(*)
  • can not sort/swap. 参考LCS(subsequence vs substring)

动归4要素

1. 状态 : 关键的关键. 这个靠经验(参见: 100个动规方程) 相当于几何题目的辅助线. 往往不是一次成功, 要反复的实验. 经典的例子是: LIS.
2. 递推式 : 表述state之间的联系: 如何使用小state来算大state. 这里的大小是段老师定义的. 例如unique path, 小state就是距离起点近的, 大state就是举例起点近, 或者说举例终点近的.
3. 初始条件 : 最极限的小状态. 例如2D DP表就是初始化第一行/第一列.
4. 答案 : 最大的状态.

面试最常见的4种类型

1. Matrix DP(10%)
2. Sequence (40%)
3. 2 Sequence (40%) —- 全都可以用rolling DP!
4. Backpack (10%) —- 可以参考背包九讲2.0

Binary Tree的2个重点: DFS和BFS.

Traverse

必须会iteration. 可以先背下来.

• Pre
• in -> Iterator题目
• Post

Divide and Conquer

Binary Tree里面的DC和Traverse都是recursion, 本质的区别是D&C的recursion有return, 而Traverse里面的recursion仅仅是用来走Tree, 并不需要return.

p1. Binary Tree Maximum Path Sum

• 3721 先用D&C.

p2. LCA I/II. (区别是有没有parent pointer)

2分法模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

while (start + 1 < end) {
    mid = start + (end - start) / 2;
    if (A[mid] == target) {
        end = mid;  // key
    } else if (A[mid] < target) {
        start = mid;
    } else if (A[mid] > target) {
        end = mid;
    }
}
if (A[start] >= target) {
    return start;
} else if (A[end] >= target) {
    return end;
} else {
    return end + 1;
}

• while退出条件: lo+1<hi
• 中间处理通用: 都是lo=mid, hi=mid. 不用mid+1/mid-1.
• while循环结束后, 只要处理2个数就可以了: start和end. 可以很容易分析.
  • 这里的start/end的意义是什么呢? 并不一定是target的范围就已经确定了, 例如有dup的时候, 就要看你是求first, any, 还是last了.
  • 或者说target不再A[]里面的情况呢? 那么target < A[lo] 或者 A[hi] < target.

从复杂度->算法

• 一般的复杂度有O(n), 比他好的就是O(lgn). 那就只有二分了. 所以看到这种复杂度要求的题目, 就是用二分模版.

p1. search insert position

• 其实根据题意了解到, 就是找first position i, that A[i] >= target. 所以对于这种sorted array的search first/last position就是用二分法.
• 模版是要灵活运用的, 只是说这样写不太容易出错. 但是也要在适当范围内根据问题来做. 譬如insert的target不再A[]内会怎么样呢? 实际还是只要根据lo/hi这2个数分析就好, 但是这里学到了有了range, 有了lo/hi, 并不一定就是分3段: 左中右. 这里的分法有意思. <= low, <= hi, 和大于hi.

Sorted Array 问题

重要的2题: Search in rotated sorted array

• binary search
  • 重要做题概念: 做题先画图, 容易直观分析.
  • 如果有duplicate, 就没得2分. 因为lo=mid=hi = 1的话, 所以2分无意义.
• 不用二分做
  • find minimum in rotated sorted array. 也是2分.
  • recover rotatted sorted array.
  • 然后用min来search, 或者recover在search.

p1. Find minimum in Rotated sorted array I/II

重要的2题: Median of two sorted arrays

• 这题的算法思想很重要. 能提升自己的能力.
• 先做: find kth int of two sorted arrays
  • 其实就等于做出来median这题了.
• 注意 k-k/2!=k/2. 因为有奇数偶数的情况. 所以统一用k-k/2.

kth of two sorted arrays

其他简单

• merge sorted array/list.
  • 小技巧: 从末尾开始插入.
    +
• 三步反转法

• 这节课我miss了, 所以只是放上对PPT的理解.
  • 参考的blog是Shuatiblog.com: link

strStr说开去

• 先看到这种substring match的问题就想到是不是有现成的算法啊: 有啊:
  • KMP -> O(n)
  • RB hash
  • BM 首尾搜索
• 不过这里是很简单的情况, 最好先写个简单的看出我基本功的可以用的code
  • 为了不失一般性, 先判断base case. 即太短, sub过长, etc.
  • 然后就可以假定我们的needle是远小于haystack的长度. 然后就是Ganker在substring concatenation那种, 在Haystack里面traverse所有长度为needle.length()的substring, 然后另一个指针对比needle和substring.

NP搜索模版: 从Permutation说开去

• code monkey说: “Permutation problem provides you a list of items, your task is to build, validate and return a somewhat combination of these items. The template is to sort the input first, and add qualified item 1 by 1”
  • 一般这个helper method (或者叫dfs), 都有个控制进入下一步的控制方式, 例如Subset的helper用pos, Permutation用boolean[] used, 等等.
  • 先写一下这个模版:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

public List<List<Integer>> Search(int[] A) {
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    if (A==null || A.length()==0)
        return ans;
    Arrays.sort(A);
    dfs(A, new boolean[A.length()], new List<Integer>(), ans);
    return ans;
}

private static void dfs(int[] A, boolean[] used, List<Integer> path, List<List<Integer>>res) {
    if (path.length() == A.length()) {
        res.add(new ArrayList<Integer>(path))
    }
    for (int i = 0; i < A.length(); i++) {
        if (i > 0 && !used[i-1] && A[i]==A[i-1])  continue;
        if (used[i])  continue;
        path.add(A[i]);
        dfs(A, used, path, res);
        path.remove(path.size()-1);
        used[i] = false;  // 记得recursion一定要恢复现场. 即call stack回退之后的状态要和进入之前一样. 可以看看Ganker的解释.
    }
}

Subset

Permutation

• 这里通过boolean[] used, 来处理duplicate.
• 例子：[1 2 3 4 4 4 5 6 7 8]. 这个例子via CMUyu
  • 444这个的选法只能:4, 44, 444连续这三种选法. 即是说: 只对第一个4做递归调用. 然后对于后面2个4就不用递归了, 因为第一个4已经将这3种选法保存到result里面了.
• 当然, Permutation在工作中的代码时尽量要避免的, 所以follow up很有可能是要求用iteration来解. 见Code ganker. 或者下面这个Next Permutation.

Combination

• 典型的模版套用

Combination Sum

Letter Combination of a Phone number

Palindrome Partitioning

Restore IP Address

8 queen

• 如何选取valid subproblem.

Coin

• 这一篇想整理一下在LC中学到的DP. 一是学习如何推DP公式, 一是学如何优化.
• 另外2篇是:
  • Leetcode中学习Recursion.
  • Leetcode中学习贪心

学习

CLRS

• rod cut

  Stanford

• WIS

ACM 资料

• DP的3个特性
  • 这个豆瓣文章不错, 讲了基本上面试会用的所有基本数据结构和算法.
  • 其中是3个特性:
    1. 最优子结构
    2. 无后效性
    3. 空间需求度

最简单的DP: Unique Path

2D DP经典: distinct subsequences

2D DP优化为1D DP的经典: Distinct Subsequences/Coin changes

分析来自CSDN

• 2D DP经典: LCS

  Naive recursion

  2D DP

• DP打表有个关键: 先构造好表, 理解并初始化边界, 然后找规律填几行.

  1D DP (真1层)

• 我昨天就是想当然的直接像coin change那样直接改成1D, 其实是不对的, 因为不是opt[i][j] ~ opt[i+1][j], 而是opt[i+1][j+1]. 因为我们的opt[i][j]的定义是x[i…M] vs y[j…N]. 所以必须从后往前/从下往上扫. 所以j+1在被j使用之前就改了. 因为这里打表是想使用修改前的值. 而且不能从反过来(前向后扫), 因为这里和ganker distinct subsequence不同???

  O(1)D的DP, 也就是1,2,3, … 的常数层

• 其实我使用的[0..1/2/3][0..N]这样一个滚动数组
• 如果是3层的滚动数组, 如POJ 1159 Palindrome的话, 可以用取mod来找到正确的行, 如ACM女神 也就是常用的方法(见Valid sudoku). 如果是2层的滚动数组, 可以用我在LCS里面的双buffer. 或者可以直接使用2层的数组做(可以mod, 或者^1), 见dp[k][j] = dp[k^1][j-1] + 1
• 参考资料: 这个分了DP类: 斜率, 压缩
• ACM分类, KMP7题

LCS经典变形: POJ 1159 Palindrome

• 实际上LCS这里的subsequence是不连续的顺序子串. 所以可以利用这一点来解决Palindrome问题.
• 只要将给的String 反转, 比较LCS, 然后加入len-LCS即可.
• 如果要返回得到的Palindrome怎么弄?

2D vs 1D

• 关键就在于可不可以recover. 例如

Leetcode freq 3

标签（空格分隔）： leetcode

Frequency 3题解

[TOC]

20141218

Combination - N00t

• 标准的recursion DFS模版. 牢记于心.
• 而且有topdown和buttomup2个写法. 其中BU更简练.
• 还有iteration的写法.

Letter Combinations of a Phone Number

• 然后再来看这道题, 可以用Simple&Stupid的做法, 和N00t的Combination差不多.
• 或者N00t的iteration解法.

Combination Sum I/II

• N00t和Ganker结合. 注意2个的区别: I是可以reuse自己. 即可以用2(0), 2(0). 这里的2(0)表示在位置0的2. eg: {2, 2, 3, 7} 求sum=7. 而II是不能reuse自己. 所以答案是2(0), 2(1).

Maximum Subarray I/II

• N00t的I是用的简单的一次过. 里面的sum初始化的条件是sum<0. 但是看了Ganker的方法才知道原来这道题目是典型的DP.
• 其实LC的要求是不用DP做来达到O(n). 而是用Divide and Conquer来做. 看水中的鱼(C++). 或者一天一学(Java): 链接
• 其实II并不能用N00t的做法. 因为有可能出现有多个subarray的值都一样! 可以看LintCode的解法: 链接

Jump Game

• Ganker在Maximum Subarray里面提到了DP里面常用的一个方法: 称为”局部最优和全局最优解法”. 在Jump game里面也用到了.

20141217

Trapping Rain Water

• Ganker CSDN大神的DP解法
• 当然还是N00t的解法作为入口开始理解.

Largest Rectangle in Histogram

• N00t: 双Stack, 一个stack
• CSDN/abcbc: 双Stack
• GeekForGeek: sliding window, segment tree. 这2个做法很重要!要认真理解.

Search a 2D Matrix

• 简单题: 用2次binary search. 或者当作1个sorted array只要一次binary search就行了.

Partition List

• 参考的Ganker的答案, 但是有点混乱了. Java里面不是copy的handle吗? 那walk, runner一直改变, 不是也同时改变了helper吗?
• ANS: NONONONONO. 双指针大法: walker/runner只是copy了pointer. 而每次walker = walker.next. 就assign了walker到下一个pointer. 这和C/C++一样.

Number of Islands

• 简单题. ProgramCreek使用的recursion解法.

20141208

Populating Next Right Pointers in Each Node

Divide Two Integers

Search in Rotated Sorted Array I/II

Deep Iterator : LinkedIn老题目

• C++的解法: fgdsd的解法 以及Iterator pattern
• Rosetta算法大全里面也有解法 这只是print Flatten, 不是iterator: Java解法link
• 还是包子铺好, 有Java的解法(是iteration, 使用Stack来替代recursion, 上面讲recursion简单些): iteration解法
• 其实这是一个常见的模式: Iterator and Composite Pattern. 见Head First Design Pattern. 这是最好的解法. 设计+代码

20141206

Search In Sorted Array

• 同类题目: Search Insert Position
• 同类题目: Search for a range

Multiply Strings

• 初看之下, 就是一道简单题目啊, str2num然后乘起来不就行了? 其实不行, 因为会太大(??)
• 第一种解法初看之下也是平淡无奇, 但其实分析的时候发现居然把array和charAt的顺序搞混了. 45->num1 = [4,5]. 这里的num1[0] = 4! 所以45*123的res要做成5位, 并将第一位留为0. 因为最终可能进位.

N-Queens I/II

• Matrix67/N00t用的是位运算解决问题.
• Ganker用的是传统的循环递归解决这种NP问题.
• 又听了段公子的DP+Recursion讲座. 讲了用遍历+backtracking这种都是NP, 即是NP问题. 里面也提到了像Word Break这种可以Top-Down(memorize)和Button-Up(DP)的区别. 以及求CSP的个数和所有解空间的区别.
• Quora上面讲了top-down跟button-up的DP都不一定需要用recursion.

20141205

Restore IP Addresses

• 太好了, 又深入的理解了recursion. 这里虽然只有一次显式的recursion, 但他是位于loop里面, 后面还有个results.add(). 以及共用(?和谁)一个results. 所以这种是一个今天学到的recursion: loop内的recursion用于循环遍历一层.
• N00t果然是recursion很厉害. 佩服. 这里是DFS还是BFS? 是不是子解树? 之前看的那个CSDN 链接在哪?

Triangle Path Sum

• 很好的DP问题. 简单, 也分为top-down, 和button-up的2种思维方式.
• 初始化List>费了些心思, 觉得还是anonymous inner class比较简洁. link. 其中programinterview的讲解很清晰
• N00t的top-down又让我深入理解了recursion中的param是primitive/object的区别. 以及call stack的new和clr的过程(Eclipse).
• 暂时还没看N00t的top-down的BFS解法………………………………….

Surrounded Regions

• 极度经典的图形学算法题目: flood fill. 同时关于DFS/BFS的取舍. 以及Queue的API: offer/poll. (这和stack的push/pull对应)
• 参考Ganker/N00t的解法.
• Palindrome Partitioning I/II

• N00t大神的DP+DP/DP+, 还有美丽的partitionHelper()

  1 2 3 4 5 6 7 8 9 10 11 12 13

  private static void recur(String s, int left, List<List<String>> result) { if (left == s.length()) { result.add(new ArrayList<String>()); } for (int i = left; i < s.length(); ++i) { List<List<String>> temp = new ArrayList<List<String>>(); recur(s, i + 1, temp); for (List<String> partitions : temp) { partitions.add(0, s.substring(left, i + 1)); } result.addAll(temp); // add()和addAll()的区别. } }

• 想到了word segment, word spell out, Matrix Chain multiplication

  • 也是一道经典recursion题目. 而且还看到了在for each里面的recursion call. 怎么展开呢? 太美了的recursion!
  • word spell out 链接
  • Matrix Chain Multiplication链接
  • Word Split: SOF链接
  • 20150423: subsequence+matching的题目首先想到的应该是DP: 见sophieJ的解法

Word Segment I/II

• Naive做法是N00t的好
• DP做法有2D和1D, 可以是aray或者arrayList, N00t的做法和ProgramCreek的不同.
• Word Break II的主要参照programCreek的做法. 很完美经典的DFS+DP解法. 漂亮!!! ProgramCreek还赔了图, 其中的words即dp[].显而可见index为什么是s.length()+1了.

20141129

Find the k-th Smallest Element in the Union of Two Sorted Arrays

• 先理解这道题再做median of two array.
• 这里关键的问题可以转化为: 找B[j-1] <A[i] < B[j] 或者 A[i-1] < B[j] < A[i]. 如果不成立就recursion. 注意这里因为Java不能用指针, 所以要稍微站换一下1337的写法.

Median of Two Sorted Arrays

• 这题有很多思考, 值得说道说道. 这题是源自于CLRS. 而且里面还简化了: m=n. 而LC这道题是generic的.
• 要做这题先要理解这道题: Find the k-th Smallest Element in the Union of Two Sorted Arrays. 见上.
  +

Regular Expression Matching

• 如何保证考虑详细?
• N00t的解法很好
  • 不知道怎样才能像他那样那么有逻辑. 不会有错漏. 这个if/else设计的太美了
  • redundant分析我觉得不对. 因为到了2nd iteration中. “b” vs “aab”是不会有3个substructure的. 因为不match.
  • backtracking做法中, 一个用substring, 一个就是用2个指针i,j. 避免了substring()来copy浪费空间. 不过之所以这里可以用”char array”是因为这里只是比对. 而不需要修改. 所以直接reference即可. 但是像之前的partitionHelper里面可以用吗??? 或者是更之前的:

Wildcard Matching

+

20141118

Construct Binary Tree from Inorder and Postorder traversal

• 首先通过pre, post, in加深了对recursion的理解.
• 还是老话, 思考问题的方式. 先是找规律. 发现pre order的头的root, 然后可以在In order里面找到左右子树的大小, 再回到pre order里面找到左右子树的root. 如此recursion.

construct binary tree from preorder and inorder traversal

• 举一反三. 找规律看到了post-order反着读的话就正好是pre order的mirror. 所以这次从post order的尾巴开始读. 发现尾巴就是root, 然后回到inorder里面找左右子树的大小. 从而回到post-order里面找左右子树的root. 要注意的是不能点到mid < end和mid > start! 一开始就这样, 发现有错误, 进行到一半就停了.
• Flatten Binary Tree to Linked List
• 太好了, 终于完全理解复杂recursion了

Path Sum

• root-to-leaf Path sum: ProgramCreek的解法
• Binary Tree Maximum Path Sum
• Find ALL Path Sum

Reverse Integer

• 要注意overflow, 跟负号

Unique Paths I/II

• 经典的DP问题
• 也是path问题, 可以找规律, 变成排列组合题.
• 如果有obstacle呢?
• 觉得还是N00t的解法比较好. 相对于1337的2D opt, 这个只要1D. 而且可以解出来.

Longest Consecutive Sequence

• 还是觉得N00t的方法. 还是一样, 学会抽象, 不要以为tree型就一定要用tree实现, 或者range就必须要知道左右和长度. 要有了整体把握才设计API. HashMap的关键在于key/value的设计.
• 还是N00t的”simple”(不觉得simple, 然而很多技巧在里面). 好聪明的做法. 果然是精通API和recursion的N00t.

20141115

Edit Distance

• 这个是个经典的DP问题. 是Stanford Algs 2 DP问题DNA Sequence Alignment的扩展, 因为不只是ACGT, 也不只是Gap, 而是有3种操作. 注意n00tc0d3r的DP的优化! (用的空间是O(min(l1, l2) 而不是通常的O(l1*l2)) 我觉得这个是一个通用的optimize方法. 是不是four Russian(不是)?

One Edit Distance

• 这个看起来就是直接用Edit Distance就行了. 其实会超时间! 注意是one distance. 所以直接1 pass.

Binary Tree Inorder Traversal

• 很喜欢N00tc03的post-order=pre-order的mirror.

Binary Tree ZigZag level order Traversal

• 这个属于BFS. 注意看题意: 输出是要按照parent来加上括号. 而不是只要按照顺序就行的. 所以有2中方法:
• 法1: 用flag
• 法2: SRAM的双buffer. 这里使我真正的理解了github_addtion.bellmanFord()! 原来reachableNode, 和nextreachableNodes就和queue, queueBuffer的关系一样. 都是用来update到下一个layer的.
• 注意要用2个loop, out-loop创建reslist来保存currLevel的值, 创建childLevel来保存下一层. in-loop用来填充res和childLevel

20141112

Convert Sorted list to BST (in-order, Button-up)

• 这个和array的区别是array可以O(1) search, LinkedList要O(n). 所以不行. 但是想到BST是in-order. 可以直接从leaf开始. 也就是Buttom-up recursive. 但是要注意的是recursion的写法. 真正理解: 位于recursive call之前和之后的code的意义是什么. 这在Algs4的BST讲过. 在Stanford的SCC的DFS_loop讲过.

Convert Sorted Array to BST

• 简单. 因为BST是按顺序的, 所以recursive拿middle并左右路.

Remove duplicates from sorted Array

• 这个可以看N00tc0d3r的解法. 先学会remove element from array
• 而且用Nth-to-end里面的双指针, 距离n+1个node!

Median of Two Sorted Arrays

• 比较难. 而且大部分答案都不对. 还是得看1337c0d3r的答案分析. 正统. 他让先看: Find the k-th Smallest Element in the Union of Two Sorted Arrays. 他说这个是这道题的基础.

Remove duplicates from sorted List

• 关键在于list的删除要给出这个node的前一个node, 然后用pre.next = pre.next.next.

题目

20150306

Short URL

• 参考N00t的设计

Battlefield

Game of Life

• 参考Holub书中的介绍以及UML

Chess

• 参考Github的UML

Collaberative Editor (Google doc)

• 参考isnowfy的设计Blog链接
  

Google 自动补全搜索

*

20141228

Populating Next Right Pointers in Each Node II

*

Lowest Common Ancestors I/II:

I: 即没有parent的pointer怎么做?

• 这题不仅在九章算法课第二课里面讲了, 而且在1337文章link也详细的解释了Bottom-up的意义. 我认为那个是设计思路.

• 先复习一下: top-down/bottom-up approach: TD/BU的区别-米群讨论, 但是里面大牛的回答也不准确, DP的top-down/bottom-up和recursion没什么关系. 例如这里的LCA的Bottom-up就是recursion. 但是Scramble String的3D Bottom-up DP就是iteration. 那么在Bottom-up有什么好处呢? 在Binary Tree的BU解法中, 相对于Top-Down是

  avoiding traversing the same nodes over and over again. —- 1337

  • 就树来说: 最准确的解释就是: 自底向上=post order traversal, 以及这篇Bottom-up解题报告
  • 其次javayu的解释: 树的bottom-up方式和top-down方式的主要差别就在于：先处理当前节点还是先处理子树

• 而且这里很有意思的是Top down的LCA是recursion, 里面还调用countMatches这个小recursion.
  • 这还是见得比较少的, 一般就是client调用helper recursion.
  • 照Tree总结所总结的万金油方法, 不过这个表述没看明白, 原来是在cnblog symetric Tree里面的分析的思路:

    1. top-down 还是 bottom-up. 选择top-down. O(n^2)
    2. 用递归. 是否需要内嵌小递归. 需要. 其实就是判定root的是否一样的小递归.
    3. 逻辑运用小递归.

这道题的follow up: parent pointer

• 如果每个node有parent pointer的话呢? 可以怎么改进: LCA II
• 在九章算法的第二课就讲了, 90% Tree的题目可以用Divide & Conquer做. 注意D&C和Traverse的recursion区别在于前者有return value. 因为在治的阶段需要对分的结果进行合并处理.

Minimum Adjustment Cost: Lintcode动态规划题目

• 参考的是主页君的cnblog和github分析的很详细, 有4种解法:

  其实就是NP问题的backtracking解法. 但还是老问题, 怎么找到解集合?

Binary Tree Maximum Path Sum

• 这题是diameter/height的扩展题. 因为题目还包含了不经过root的情况. 其实都是dfs recursion. 只是要同时保存single path和sum. 即
  • single path是经过当前node的一边的max: Math.max(l.path, r.path)+root.v -> 经过当前node的边的最大值. 0->即经过此node的边为负.
  • sum则是左右sum的最大值, 或者左右边最大值加上当前node.

• 由嘻唰唰blog题解里面分析的: 对于每一个node的Maximum Path Sum分2类:

  1. single path是指由该node出发向leaf的第一类path中最大的path sum
  2. 以x为LCA的第二类path中的最大path sum

• 正是因为看到嘻唰唰提到的LCA, 所以去看了1337的LCA文章, 受益良多. 加深对top-down/bottom-up的理解.

Diameter and Height of Binary Tree

• 做Binary Tree Maximum Path Sum之前先做一下类似理解的题目: Diameter of Binary Tree: N00t帖子

  树没有被看成有向图，而是被当成无向图来寻找路径 — Ganker

• 标准的DFS. 注意base case一定要return来终止.
• 注意Height必须是进过root, 但是Diameter并不一定. 参见N00t的配图. 而N00t的公式则按照(SOF解释](http://stackoverflow.com/a/11897490). 很好理解了.

Next Permutation

• 先理解什么意思: 见Nayuyi.io的解释. 正如水中鱼所说: 这道题目就是一个观察题, 以及基本的array操作. 比如交换, index, loop的break. 复杂度只能是O(3*n)
• 我还是参考的水中的鱼的思路. 找到partitionNum, partitionIdx, changeNum. 然后交换partionNum, changeNum. 接着再reverse num.substring(partitionIdx+1).
• Ganker和水中的鱼对于changeNum的找法有一点微小区别.

First Missing Positive

1. 其实这就是bucket sorting. 是最快的排序法, 比qsort还快. 是O(n), 但是是用空间换时间.

   可以generalize为更实用的radix sort.

   A type of bucket sort called the counting sort —- IBM link

• bucket sort, radix sort, bubble sort, counting sort —- University of Washington CSE 373
  • 注意这里的最后一步就是Concatenation bucket到原array的时候有3个var, 不要搞混了.
• 注意ganker的内循环判定的条件是A[i] != A[A[i]-1]. 而且最后要i--. 为什么不能换成A[i] != i+1.
  • 因为若是换成直接判断A[i]!=i+1的话, 则会导致在重复字符的情况下出现死循环.
  • 之所以i—. 是因为交换完之后不一定是正确的. 例如{3,1,2}一开始的3,2交换为2,3后, 2并不是正确位置. 所以再判断2,1并交换才对.
  • 所以Ganker说这道题目很简单, 但其中包含的算法思想和编程基础很适合面试!

Largest Rectangle in Histogram

Scramble String: 3D 动态规划经典

• Google考过, 见MITBBS 2012年帖子
• 先理解这个Scramble是什么意思: s1 = "great", s2 = "rtgae";就不是有效的. 注意要求是
• 这道题目可以用recursion, 更可以用DP. 是一道经典的3D DP. 但正如段公子所说: DP table可以用array也可以用HashMap, 可见武大csdn的hashmap解法. 但是觉得这个和N00t的backtracking差不多? 看看九章算法主页君的就搞懂了, 其实不一样.

• 参考的:

  • fightforyourdream的recursion+DP.
  • 武大CSDN的Hashmap动态规划,
  • Unieagele解题博客的3D动归

  • 九章算法主页君—CMUyu

    • 分析的答案很适合面试的顺序: recursion->剪枝->Top-down DP(memorize)->Bottom-up DP(iteration).
    • 而且时间空间复杂度分析的很详细.

  • Ganker的3D动归, 和N00t的意思差不多. 不过Ganker的分析不错.

    • 难点在于for loop的顺序. 最外层应该是len. 因为是bottom-up. 从小问题推大问题. 或者说大问题的解可以使用小问题的解得到, 而不用反复求解同一个小问题.

      对于判断这些左右部分是不是scramble我们是有历史信息的，因为长度小于n的所有情况我们都在前面求解过了（也就是长度是最外层循环）。

    • 有点没搞明白: 为什么Ganker说:

      如果以上两种情况有一种成立，说明s1[i…i+len-1]和s2[j…j+len-1]是scramble的。

  • 水中的鱼的recursion, 他的剪枝很好, 可以AC. 而N00t的原始的recursion(即brute-force的剪枝仅仅比较s1,s2的长度, 是很低效率的, 所以过不了).
  • N00t的递归, DP (bottom-up) 就是iteration, 而LCA的DP (bottom-up)则是recursion. 那么这个是怎么想出来的呢:

    • 先理解递归是怎么做的: 从大到小substr判断. 即切割成substructure/subproblem.
    • For each pair of (n-1)-char-long substrings of the two strings, are they scramble to each other?
    • For each pair of (n-2)-char-long substrings, are they scramble?
    • … …
    • For each pair of 2-char-long substrings, are they scramble?
    • For each pair of char in the two strings, are they scramble (i.e. do they equal)?
    • That is saying, we can build up a table and solve the problem in a bottom-up fashion.
    • 然后还有就是这里的递推式一开始没有理解. 看了fight for your dream懂了: 还是recursion的想法,2种情况: 前前&&后后||前后&&后前. **注意: 这种var(i,j,k,p)变多了之后不要搞混了. 最好的方法就是写一个例子出来.

Interleaving String: 2D/1D 动态规划

凡是substring的题目, 都是自动脑补动态规划, 正如Tree的题目自动脑补分治法.

方法1: recursion

• 当然, 最好先从简单的做法入手, 先有个做对的方法: recursion是DP的前提. 或者说有了递归的思路就好想出来DP了.
  • 对于在recursion call里面处理下一个substring的话, 即修改index, 有2种方法.
    1. 例如remove duplicate from string, 因为简单的赋值. 所以res[j++] = s[i++];
    2. 在N00t的recursive call里面, 因为一句话里面有2个地方用到i,k. eg: s1[i] == s3[k] && isInterleave(s1, s2, s3, i+1, j, k+1). 我一开始是用++i, j++. 这样很容易弄混. 直接干脆用i+1.
    3. 总结一下: 如果是简单的method call, 可以使用++i; j++. 不过长一点的statement还是不要弄晕自己, 代码最好不要依赖于statement的顺序, 所以还是原始的i+1.

方法2: 2D 递归

• 既然recursion已经想出来了, 也就弄明白了? (not yet! 想法出来还要写代码实现, 里面很多门道和细节的设计)
• 首先是边界条件, 或者说base case的设计: 有个trick, 每次遇到string的DP, 都要增加一个空位. 表示s1, s2都不取的情况. 所以Opt[0][0] = true. 这里参考的popfish的算法路blog画的2D 打表图示. 我一开始做的时候, 在打1st row和1st col的时候直接就是比较substring了. 但是结果不对. 为什么呢: 因为substring没用对.
  • 有2点关于substring要注意
    1. substring上界是开区间. 所以substring(0,0)是"", (0,1)才相当于charAt(0).
    2. 刚发现: "n"=="n"是true, 但是"ni".substring(0,1)=="no".substring(0,1)居然是false! 刚查了SOF: how to compare string, 以及SOF: string object vs string literal, 才知道:

       Java的==比较string的时候比较的是reference, 而不是value!. 应该说: Java 的 “==”比较object的时候, 是看是否为同一个reference.
       所以2个substring的reference不同, 当然就是false!

方法3: 1D 递归. 参考Ganker的解法.

• 注意到2D的递推式只和上一层和左边的有关: opt[i][j] ~ {opt[i-1][j], opt[i][j-1]}. 所以可以只用一个1D 的 dp表就可以了. 当然这个时候就要小心了. 有几点:
  1. 长度多少? 意义已经改变了.
     • 对于处理2个string的问题, 有个trick: 一般都最好选择短的那个处理, 可以节省空间或者时间.当然opt[minWord.length()+1], 而且因为是需要update 短的opt长度. 所以将opt update放在内层短循环可以更加优化. 因为opt[0]的意义, 有2个含义:
       • 一个意义是到外层循环到i的时候, opt[0]表示第一列的第i个时候, 表示原本2d中的opt[0][j]. 即看s3[0…j]是否可以用MaxWord[0…j], 而没有MinWord. 来interleave.
       • 第二个意义是: 内层循环到j的时候, s3[0…i+j+1]是否可以由maxWord[0…i]minWord[0…j]来interleave.
  2. 因为外层循环maxWord, 内层循环minWord. 所以1st row可以单独初始化. 而1st col, 即maxWord的interleave的base caseze’y则要在外层循环中初始化. 而将minWord放在内层循环upodate可以节省DP表空间.
  3. 最关键的在于递推式现在怎么样勒?
     • 我一开始就搞错了. 一定要注意: 1D其实就是2D压缩而来的. 所以就是2D的简化版. 所以要和2D的递推式紧密联合起来想.
     • 2D的递推式: opt[i+1][j+1] = opt[i][j+1] && s1[i] 或者 opt[i+1][j] && s2[j]. 所以opt[j+1]和上一层或者左边有关: opt[j+1] = opt[j+1] && maxWord[i] 或者 opt[j] && minWord[j]. 关键在于搞清楚现在上一层和左边需要的char是哪一个. 注意这里的j是横轴啊!
       • 所以2d里面的左边, 即opt[i][j+1]则相当于1d里面的(opt[j])就是由2d里面的s1(横着的string).
       • 而j+1, 就是相当于2D里面的上一层, 即相当于opt[i+1][j]. 所以是和2d里面的s2(竖着的string), 所以是maxWord的char.

20141226

Reverse Nodes in k-Group

• 先做Swap Nodes in Pairs. 注意Ganker提到的, list常用的技巧就是遇到需要修改root的题目一般都是接一个空的node到root, 这样就把root退化为一般的中间node.
• 这题主要参考N00t的解法. 即Invariant是2个node, keep track这2个node. 头脑要清晰. 在写之前想好算法.
• N00t里面这个reverse list的时候的思路超级清晰. 想想为什么是这样写. 关键在于

  pre, cur是不变的[以N00t的例子为例, 到结束的时候, 实际上pre还是指向1, cur还是指向2], 只改变pre.next, cur.next. 以及这2个next之间的link.

  1 2 3 4 5 6 7 8

  // 定位好之后就可以开始交换了. 这里是这个method的关键. while (pos < end && cur != null) { ListNode tmp = cur.next.next; // N00t用的是nt: node temp. cur.next.next = pre.next; // cur; pre.next = cur.next; cur.next = tmp; // pre.next.next = tmp; pos++; }

Trapping Rain Water

Permutations I/II

• NP问题的做法基本都是用Backtracking. 想象这里和Combination有什么区别呢?
  • Ans: 这里子问题的条件变化了. Combination里面是helper(,i+1,). 这里是每次在loop里面使能used[i] = true, helper(used[i]). 这样就能缩小到下一个子问题.
  • 这很重要. 因为recursion就是要一步步进入子问题, 解决, 跳出递归, 到保存到stack的以前的现场. 所以ganker也强调了这里要在helper()后面恢复现场, 即list.remove(list.size()-1), 以及初始化used[i]. 即used[i] = false.
• II就是加入了一个条件: 如果是{1,2,1} 呢? 要避免112, 112出现2次的情况, 就要在dfs之前先判断是否和上一个num重复(**因为num已经sort过了).
• 评论的一个follow up: link. 其实很简单, 也是加入一个判断是否和上一个item里面最后一个数相等, 若是就continue.

Rotate Image

Text Justification

• 考察基本功的好题目, 注意题目的各个细节. 参考的ganker的解.
  1. 什么是last呢? 即本行的开头, 什么是i呢?下行的开头. 什么是i-last-1呢? 就是该行的间隔个数. 例如该行如果可以放5个单词, 开头的last是4, 下一行开头是9. 那么9-1就是该行的结尾, 9-1-4既是该行有4个间隔.
  2. 为什么下一步循环的时候判断if(j<i-1)呢? 这很好理解, 因为分配\b只跟间隔有关, end的词在一行只有一个词的时候才要pad空格.
  3. 上面2这个if语句里面最后的extraNum—是什么意思呢? 注意题目要求是尽量平均分配. 所以多余的就从start开始的间隔每个+1. 注意这里的extraNum是%间隔数. 所以最多的情况是每一个间隔的空格都加1个. 否则就是靠左的间隔s分到一个extra的空格.

     “Extra spaces between words should be distributed as evenly as possible.”

Sort Colors

• 其实就是counting sort. 拓展题就是如何压缩, 如何返回最长连续char及其个数.
• follow up: 如何使用O(1)的空间来做? 而且O(n)的time? N00t和Ganker都是用的双指针. 好聪明, 怎么想到的?
  • 最主要还是和reverse Nodes k-group的思想一样, 想好invarient. 可以这样想. 如果sort的colors只有0,1. 那么就只要一个pointer0, 然后i一个一个往下走, 如果遇到了0, 就赋值, pionter0++. 相当于swap的操作.
  • 现在可以看看有3个colors: 0,1,2的话怎么用pointers呢? ans: 就用2个pointers: p0, p1. 遇到0就赋值, p0++, p1++. 遇到1就赋值, p1++. 为什么这个时候p0不改变呢? 因为??????

Minimum Window Substring

• 先去复习longest non-repeated substring和Concatenation (freq1), 因为方法都一样:

  建立一个字典，然后维护一个窗口

• 都是substring match 字典. 这一点类似的还有Word break(Ganker的DP解)
• 看了N00t的Concatenation里面讲了原来双指针窗口法原来就是KMP(并不是KMP).不过KMP, BM, KR都很重要.
  -

Gray Code

• 使用的方法就是ASIC里面介绍的方法. 有意思. 感觉KMP也是FSM.
• 原来Gray code就是汉诺塔的解… N00t的一行解法太cool, 没看明白啥意思.

Subsets I/II

• 还是Permutation/Combination这种NP问题的解法: backtracking. 只是有一点点区别: 在处理加入的元素时要去掉一些不符合条件的.
• 很好的题目, 再次加深理解Recursion, 不仅仅是像我在LC中学习Recursion那样还停留在Recursion代码之前, 之后的代码的意义. 而是要深入理解Recursion思维的想法和设计.
  • recursion里面, subset加入的顺序是怎么样的? 如何保证 non-descending order? Ans: 其实就是对自己设计的recursion要理解, 只到recursion的顺序就ok了. 因为Ganker的rec是从3,2,1,0,-1 递减的call. 而N00t则是0,1,2,4递增的call. 所以顺序不同. 具体的trace可以参考P533-Algs4-DFS.
  • 还有就是为什么N00t的输出是从[3], [2]开始, 而Ganker的则是从[1], [1,2]开始. 这是因为base case 的判断的区别, 以及recur进入下一层子问题的顺序是递增还是递减. 这很有意思. 要thinking in recursion.

20141225

Path Sum I/II

• 树的题目很常见, 但是方法都类似: recursion.
• 问题也很常见: I一般就是问是否存在解. II一般是求所有解的集合.
• 正是这道题目, N00t讲了Java的call by value对于object来说是copy他的handler, 即reference, 所以将来的改变会对之前add的reference改变, 也就改变了最终的结果:

  • Notice that we make a copy of the path before we added it to our result set. The reason is that when we add an Object (here, an ArrayList), Java add a copy of the pointer (i.e. a reference) of the Object, rather than a deep copy. So, any changes to content of the original Object will reflect into our final result set.

• 同样的Ganker也是res.add(new ArrayList<Integer>(item));. 否则必然是错误的.
• 为什么N00t的if (root.value==sum)里面放path到res之后不能return, 否则会出现错误的path? 因为这个里面加上return是完全错误的! 这里并不是base case, 不应该return. 但是Ganker的为什么又应该加上return呢? 因为这个是base case. 注意Ganker的顺序.

Longest Substring Without Repeating Characters

• N00t的方法是hashmap+start/end2个pointer的移动, 注意N00t只要判断当前的char是不是在当前substring中, 才update. 考虑到返回所有这种substring的问题. 我的思路是记录longest的start, 这样因为maxlength是返回值. 所以substring就可以解决. 但是有点小问题.
• Ganker则是使用的walker/runner 双指针法. 或者说: 窗口法来处理这一类的string问题. 还归了类. 一开始没理解为什么是while(charAt(w)!=charAt(r)). 想到了一个好例子: “xyb12b02”. 走了一遍理解了. 本来给的例子: “abcabcbb”并不好. 因为W=R都是连续的, 没看到while不等的情况. 所以有时候要多举几个case. 但不是随便举. 而是想上面那个case那样第一个重复的’b’并不是第一个字母.
  • 扩展的题目有Substring with Concatenation of All Words，Minimum Window Substring，思路是非常接近的，只是操作上会更加繁琐一些。
• case很重要, 一是在开始做题之前用来理解, 考虑算法之用. 二来是作为test case. 但是case也要设计得好才行, 不然还是会错. 所以要建立在完全理解题意, 想好算法之后写有用的case, 来改正算法. 有点鸡生蛋, 但实际上是要懂了再下笔. 面试不是调代码.

Longest Consecutive int string

• 这道题在GoPro onsite面到. 其实很简单的recursion. 题目意思是给一个排好序的string: “abccdeeeeef”, 则’e’是重复次数最多, 有5次. 所以返回: e和5. 其实这个和compression很相同, 之前见过: 将这个string输出为”a1b1c2d1e5f1”
• 思路参考的SOF上面的recursion.

Container With Most Water

Jump Game

• 经典的DP和Greedy问题. 段公子在DP/recursion里面讲了.
• 第二题的想法在N00t和Ganker之间有区别. 可以加深理解. 也确实想了好久才明白他们的code.
• Ganker的评论里面又一个记录path的方法, 这样可以返回最少jump的path. 总而言之, 也是一个DP的方法. DP还是Greedy? 傻傻分不清. 还要回头复习一下贪新算法: MST.

3Sum/4Sum

• 主要参考N00t和Ganker的解法. 但其实可以结合HashSet来做4Sum. 更简单.
• 注意这里面的设计, 如何避免重复. 所以要sort. 通常的解法是夹逼法则. for loop循环3-2或者4-2个头, 然后剩下2个index可以用left/right来夹逼.
• 注意这里正确的使用了do…while.
• Binary search的合理使用. 一般不会直接写一个binary search. 但是这里夹逼自然是binary search好用. O(n)->O(lgn)

Spiral Matrix I/II

• N00t的这张图真是经典, 也确实是复杂题目想好psuedo code才写!
• Hello WOrld

Recover Binary Search Tree

• 再次加深了对Recursion的理解. 2个不连续的recursion. 而且param还不对称, N00t的recursion写的真好. N00t的方法也很好.

  Distinct Subsequences

  +When you see string problem that is about subsequence or matching, dynamic programming method should come to your mind naturally. —-by link

  • DP的经典题目. N00t的做法也是可以的. 但我倾向于Ganker/SophieJ. 但是要理解DP公式的含义. 不然连边界条件或者初始条件都搞不出来. Ganker的2D分析, 然后code则是优化为1D dp的解法一开始没看懂, 然后Ganker在回复里面解释了为什么j是从T的从后向前扫. 这是因为这里的DP是想使用update之前的值, 所以这样. 如果以后有个DP问题是要使用更新后的1D dp, 则是从头往后扫.
  • 还是的加深理解为什么1D的逆向填的DP是对的? 会不会导致比较出来的subsequence没按顺序? 或者反过来了? 见csdn link 有点乱: 下标, 如何保证是in-order? 看Coin Change—-段公子.

20141223

Plus One

• 这是一道简单题. N00t给出了他的扩展题: plus int.
• Ganker说他在Google店面的时候就问了这题. 因为适合扩展和OOD的设计.

  Symmetric Tree

• Ganker是简单的recursion和iteration. 注意这里判断是否对称的条件: 空的情况, 有值的情况. 注意不用判断值相等. 为什么? 因为helper是recursion, 要找到结束得点. 而值相等可以继续走下去. 而都为空就可以直接返回true. 因为走不下去了. 这里也明显的看出iteration为什么会繁琐.
• N00t使用的一种stl数据结构: ArrayDeque. 其他思路和Ganker是一样的.

Balanced Binary Tree

Palindrome Number

• 和Freq3的PalindromeDPDP类似.
• 这里的比较2end不能用pointer了. 因为不是string. 这里有2个方法. 用一个div(不断变化). 本质还是loop里面update为指向对称的end points.
• 或者是1337里面的第三个方法: 用一个stack.

Search Insert Position

• 在freq3里面已经做过

Valid Sudoku

• 巧妙使用i/3*3和i%3*3. 以及API的设计

SOlve Sudoku

• 加深理解循环递归. 觉得比NP的N-Queens更重要. 这里的设计是很重要的模版.

Count and Say

• String的小题目. 一定要bug free.
• 题目居然没看懂. 还是看了CSDN上面FightForDream的帖子才搞明白什么意思.

  Remove Duplicates from Sorted Array I/II

• 好在我回顾了这道题目. 发现N00t的思路太不好了, 很容易错, 而且扩展不了. 实际上有string, 有比较的时候就用pointer就好了. 而且这里还是in-place. 就算是II, 也只要多加一个变量cnt来看当前有几次重复元素.
• 所以Ganker的方法远胜于N00t. 也保证了这种简单题目的清晰思路和bug-free. 就是通过

题目