1. Max Points on a Line
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
用斜率slope和y截距来定义一条直线是通常的做法，那么n个线段里两两配对，然后把slope和截距记录到hashtable里。这样的算法比较复杂。另一种简单的做法是依次选取一个点 P， 然后考察其他点和他的斜率，如果线段AP和BP的斜率一样，那么ABP三个点是共线的，这样就省去了截距的计算。 当然每一次iteration hashtable要清空，因为AP 和BQ的斜率即便一样，也未必是同一条线。最后要注意重复点的问题。
2013年12月16日星期一
2013年10月10日星期四
常用排序算法
1. 选择排序
每次遍历从集合中选择出最小或最大的放入集合的开头或结尾的位置，下次循环从剩余的元素集合中遍历找出最小的并如上操作，最后直至所有原集合元素都遍历完毕，排序结束。 2. 冒泡排序
依次比较相邻两个元素，优先级高（或大或小）的元素向后移动，直至到达序列末尾，无序区间就会相应地缩小。下一次再从无序区间进行冒泡操作，依此循环直至无序区间为1，排序结束。 3. 插入排序
将前面的区间（初始区间为1，包含第一个元素）视作有序区间，然后将有序区间的后一元素插入到前面有序区间的适当位置。直至有有序区间扩展到原区间的大小，排序结束。 4. 快速排序
思想就是任取待排序序列中的某个元素（元素的选取方式在一定程序上会影响实现过程和排序效率）作为标杆，将待排序序列划分为左右两个子序列，左侧元素小于标杆元素，右侧元素大于标杆元素，标杆元素则排在这两个子序列的中间，然后再对这两个子序列重复上述的方法，直至排序结束。 方法2 5. 归并排序
归并排序的原理比较简单，也是基于分治思想的。它将待排序的元素序列分成两个长度相等的子序列，然后为每一个子序列排序，然后再将它们合并成一个序列。 6. 堆排序 堆排序的过程分为两个步骤，第一步是根据初始输入数据，建立一个初始堆；第二步是将堆顶元素与当前无序区间的最后一个元素进行交换，然后再从堆顶元素开始对堆进行调整。
每次遍历从集合中选择出最小或最大的放入集合的开头或结尾的位置，下次循环从剩余的元素集合中遍历找出最小的并如上操作，最后直至所有原集合元素都遍历完毕，排序结束。 2. 冒泡排序
依次比较相邻两个元素，优先级高（或大或小）的元素向后移动，直至到达序列末尾，无序区间就会相应地缩小。下一次再从无序区间进行冒泡操作，依此循环直至无序区间为1，排序结束。 3. 插入排序
将前面的区间（初始区间为1，包含第一个元素）视作有序区间，然后将有序区间的后一元素插入到前面有序区间的适当位置。直至有有序区间扩展到原区间的大小，排序结束。 4. 快速排序
思想就是任取待排序序列中的某个元素（元素的选取方式在一定程序上会影响实现过程和排序效率）作为标杆，将待排序序列划分为左右两个子序列，左侧元素小于标杆元素，右侧元素大于标杆元素，标杆元素则排在这两个子序列的中间，然后再对这两个子序列重复上述的方法，直至排序结束。 方法2 5. 归并排序
归并排序的原理比较简单，也是基于分治思想的。它将待排序的元素序列分成两个长度相等的子序列，然后为每一个子序列排序，然后再将它们合并成一个序列。 6. 堆排序 堆排序的过程分为两个步骤，第一步是根据初始输入数据，建立一个初始堆；第二步是将堆顶元素与当前无序区间的最后一个元素进行交换，然后再从堆顶元素开始对堆进行调整。
2013年10月2日星期三
LeetCode 中Tree的BFS
Tree 的BFS往往指的是层序遍历已经层序遍历的变型。最常见的做法是用两个queue，交替表示当前层和下一层。这种做法思路清晰简单，但是空间耗费是O（n）。 有些时候会要求更巧妙的空间耗费少的办法。
1. Binary Tree Level Order Traversal
也可以用递归的方法来做：
2. Binary Tree ZigZag Level Order Traversal
因为是zigzag顺序，因此用stack而不是queue，反序时先放left后放right，正序时先放right后放left。
3. Binary Tree Level Order Traversal II
题目由自顶向下改为了自底向上，只要把题1的结果reverse即可。这里代码略去
4. Populating Next Right Pointers in Each Node
此题是按层遍历的变种，用到双层 queue。注意此题的假设树是完全二叉树(perfect binary tree)
还有一种O（1）空间的解法，两个节点node负责换层(node=node->left), cross负责把左右子树连起来，以及右子树和corss->next的左子树连起来。
5. Populating Next Right Pointers in Each Node II
此题输入是任意的二叉树，因此并不是左右子树都存在，要分别考虑。代码很简单只需要改动两行
空间O（1）的解法，需要先把下一层链接好然后 用next来遍历下一层。 在开始遍历每一层前，next和pre都为0，这是位了发现正确的next（下层第一个非空孩子）和pre（下层第一个非空孩子）
1. Binary Tree Level Order Traversal
也可以用递归的方法来做：
2. Binary Tree ZigZag Level Order Traversal
因为是zigzag顺序，因此用stack而不是queue，反序时先放left后放right，正序时先放right后放left。
3. Binary Tree Level Order Traversal II
题目由自顶向下改为了自底向上，只要把题1的结果reverse即可。这里代码略去
4. Populating Next Right Pointers in Each Node
此题是按层遍历的变种，用到双层 queue。注意此题的假设树是完全二叉树(perfect binary tree)
还有一种O（1）空间的解法，两个节点node负责换层(node=node->left), cross负责把左右子树连起来，以及右子树和corss->next的左子树连起来。
5. Populating Next Right Pointers in Each Node II
此题输入是任意的二叉树，因此并不是左右子树都存在，要分别考虑。代码很简单只需要改动两行
空间O（1）的解法，需要先把下一层链接好然后 用next来遍历下一层。 在开始遍历每一层前，next和pre都为0，这是位了发现正确的next（下层第一个非空孩子）和pre（下层第一个非空孩子）
LeetCode 中 Tree的DFS
树是典型的可以用dfs算法的数据结构。 DFS往往都伴随着递归。但是与上一篇博客不同，这里的递归函数往往是help函数，难度也增加了，需要仔细分析
1. Path Sum I
检查是否有从root到leaf的path 使得他们的和等于sum，很典型的利用递归的DFS算法：
2. Path Sum II找到所有符合上题条件的路径
典型的DFS+回溯(pop_back)
3. Flatten Binary Tree to Linked List
思路是把每一个节点的left child置为空，right child挂在左子树最右子树（preorder right child的前驱）后面，right child放左子树（pre order 的next节点）。递归考虑右子树。
4. Binary Tree Maximum Path Sum
这题稍有难度。 三种情况需要考虑：1.左子树路径加当前根节点。2。右子树路径加当前根节点。 前两种情况都是以当前根节点为起始点。 3.如果path是穿过当前根节点的，那就需要左右子树路径加当前节点
5. Sum root to Leaf Numbers
思路是从root一直加下去，如果当前节点是叶子节点那么加到结果中去，否则最左右子数继续加。
6. Unique Binary Search Trees
Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
定义Count[i] 为以[0,i]能产生的Unique Binary Tree的数目， 如果数组为空，毫无疑问，只有一种BST，即空树， Count[0] =1
如果数组仅有一个元素{1}，只有一种BST，单个节点 Count[1] = 1
如果数组有两个元素{1,2}， 那么有如下两种可能
1 2
\ /
2 1
Count[2] = Count[0] * Count[1] (1为根的情况)
+ Count[1] * Count[0] (2为根的情况。
再看一遍三个元素的数组，可以发现BST的取值方式如下：
Count[3] = Count[0]*Count[2] (1为根的情况)
+ Count[1]*Count[1] (2为根的情况)
+ Count[2]*Count[0] (3为根的情况)
所以，由此观察，可以得出Count的递推公式为Count[i] = ∑ Count[0...k] * [ k+1....i] 0<=k<i-1
问题至此划归为一维动态规划。当数组为 1，2，3，4，.. i，.. n时，基于以下原则的BST建树具有唯一性：以i为根节点的树，其左子树由[0, i-1]构成， 其右子树由[i+1, n]构成。
7. Unique Binary Search Tree II
思路和上题类似，先定root然后把各种可能的左右子树分别组合。 8. Construct Binary Tree from Preorder and Inorder Traversal
9. Construct Binary Tree From PostOrder and InOrder TRaversal
定义Count[i] 为以[0,i]能产生的Unique Binary Tree的数目， 如果数组为空，毫无疑问，只有一种BST，即空树， Count[0] =1
如果数组仅有一个元素{1}，只有一种BST，单个节点 Count[1] = 1
如果数组有两个元素{1,2}， 那么有如下两种可能
1 2
\ /
2 1
Count[2] = Count[0] * Count[1] (1为根的情况)
+ Count[1] * Count[0] (2为根的情况。
再看一遍三个元素的数组，可以发现BST的取值方式如下：
Count[3] = Count[0]*Count[2] (1为根的情况)
+ Count[1]*Count[1] (2为根的情况)
+ Count[2]*Count[0] (3为根的情况)
所以，由此观察，可以得出Count的递推公式为Count[i] = ∑ Count[0...k] * [ k+1....i] 0<=k<i-1
问题至此划归为一维动态规划。当数组为 1，2，3，4，.. i，.. n时，基于以下原则的BST建树具有唯一性：以i为根节点的树，其左子树由[0, i-1]构成， 其右子树由[i+1, n]构成。
7. Unique Binary Search Tree II
思路和上题类似，先定root然后把各种可能的左右子树分别组合。 8. Construct Binary Tree from Preorder and Inorder Traversal
9. Construct Binary Tree From PostOrder and InOrder TRaversal
2013年10月1日星期二
LeetCode 中 Tree相关的Recursion
Tree是一个很重要的考点。其中recursion的题目占很大的比例。 在tree中， recursion往往和dfs相结合。 这里我们探讨一下那些用recursion解决的问题思路都很直观，代码比较容易写出来的题目。 注意相对应的iterative的题目也需要掌握。
1. Tree Pre-Order，InOrder,PostOrder遍历 这里首先给出中序遍历递归代码 iterative for InOrder Travesal iterative for InOrder Travesal with O(1) space (have parent ptr) Iterative for PreOrder Travesal
Iterative for PostOrder Travesal
2.Validate Binary Search Tree 递归检查左子树比root值小，又子树比root值大。 3. Recover Binary Search Tree 可以先用O（n）space 将树中序序列化，然后找出乱序的数字。这里要求O（1）的space 3.a 另一个利用iterative inorder的方法，不需要全局变量 以上方法都用到了extra space。下面的方法真正用到了O(1)space 4. Same Tree recursion 算法非常简单： 这里再给出iterative的方法 5. Symmetric Tree 思路和上一道题差不多。 Iterative: 6. Construct Binary Tree from Preorder and Inorder Tree 分段递归 7. Construct Binary Tree from Postorder and Inorder Tree 分段递归 8.Convert Sorted Array to Binary Search Tree 比较简单，每次取中间的数作为root，递归对左右两边的子数组进行操作。 9.Convert Sorted linkedList to Binary Search Tree 这题比上题复杂。 如果按照上题的思路每一层都需要遍历一次list 需要O（NlogN）。 如果采用从底向上的方法构建，可以充分利用list不能随机访问的性质，达到O（n） 10. Maximum Depth of Binary Tree 非常简单，递归调用 11. Minimum Depth of Binary Tree 思路和上题一样，但是不同的是，空！=零的关系，因此不能照搬上题的答案。 12， Balanced Search Tree 左右子数都是balance的而且两者maximum 高度差不超过1。
1. Tree Pre-Order，InOrder,PostOrder遍历 这里首先给出中序遍历递归代码 iterative for InOrder Travesal iterative for InOrder Travesal with O(1) space (have parent ptr) Iterative for PreOrder Travesal
Iterative for PostOrder Travesal
2.Validate Binary Search Tree 递归检查左子树比root值小，又子树比root值大。 3. Recover Binary Search Tree 可以先用O（n）space 将树中序序列化，然后找出乱序的数字。这里要求O（1）的space 3.a 另一个利用iterative inorder的方法，不需要全局变量 以上方法都用到了extra space。下面的方法真正用到了O(1)space 4. Same Tree recursion 算法非常简单： 这里再给出iterative的方法 5. Symmetric Tree 思路和上一道题差不多。 Iterative: 6. Construct Binary Tree from Preorder and Inorder Tree 分段递归 7. Construct Binary Tree from Postorder and Inorder Tree 分段递归 8.Convert Sorted Array to Binary Search Tree 比较简单，每次取中间的数作为root，递归对左右两边的子数组进行操作。 9.Convert Sorted linkedList to Binary Search Tree 这题比上题复杂。 如果按照上题的思路每一层都需要遍历一次list 需要O（NlogN）。 如果采用从底向上的方法构建，可以充分利用list不能随机访问的性质，达到O（n） 10. Maximum Depth of Binary Tree 非常简单，递归调用 11. Minimum Depth of Binary Tree 思路和上题一样，但是不同的是，空！=零的关系，因此不能照搬上题的答案。 12， Balanced Search Tree 左右子数都是balance的而且两者maximum 高度差不超过1。
2013年9月24日星期二
Leetcode 中stack在string处理中的应用
1. Valid Parentheses
这题思路较简单。用stack保存考察的char如果是右括号就对比和栈顶元素是否匹配，是则弹出否则插入。
2. Longest Valid Parentheses
这道题由于要求长度，因此压入栈的不是字符本身，而是index。遇到（直接压入，遇到）如果栈非空而且栈顶是（则update当前最大长度。 3. Simplify Path 预处理：去掉多余的"/"并在最后一位补上“/”。 设置状态位 flag==1 说明一层目录的开始，flag==2是一层目录的结尾。注意区别 "/."和“/..”. 前者直接舍弃，后者需要把栈顶元素弹出
4. Largest Rectangle in Histogram
最简单的方法就是依次遍历，取最大值 O（n^2）。比较巧妙的算法是用一个stack，存直方图的index，如果下一个直方图比栈顶直方图高，继续压栈，否则计算下一个直方图和当前直方图组成的面积。 5. Maximal Rectangle
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area. 此题第一步先纵向累计，i.e. 新建matrix (called mat), mat[i][j] 表示第j列上 以i结尾的最长连续1的个数。此步结束可以得到i组直方图然后用上题思路求解 6. Evaluate the value of an arithmetic expression in Reverse Polish Notation.
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
思路很简单， 读出来如果是操作数就压栈，如果是操作符，就把栈顶的两个元素拿出来计算，结果再次压栈
这题思路较简单。用stack保存考察的char如果是右括号就对比和栈顶元素是否匹配，是则弹出否则插入。
2. Longest Valid Parentheses
这道题由于要求长度，因此压入栈的不是字符本身，而是index。遇到（直接压入，遇到）如果栈非空而且栈顶是（则update当前最大长度。 3. Simplify Path 预处理：去掉多余的"/"并在最后一位补上“/”。 设置状态位 flag==1 说明一层目录的开始，flag==2是一层目录的结尾。注意区别 "/."和“/..”. 前者直接舍弃，后者需要把栈顶元素弹出
4. Largest Rectangle in Histogram
最简单的方法就是依次遍历，取最大值 O（n^2）。比较巧妙的算法是用一个stack，存直方图的index，如果下一个直方图比栈顶直方图高，继续压栈，否则计算下一个直方图和当前直方图组成的面积。 5. Maximal Rectangle
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area. 此题第一步先纵向累计，i.e. 新建matrix (called mat), mat[i][j] 表示第j列上 以i结尾的最长连续1的个数。此步结束可以得到i组直方图然后用上题思路求解 6. Evaluate the value of an arithmetic expression in Reverse Polish Notation.
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
思路很简单， 读出来如果是操作数就压栈，如果是操作符，就把栈顶的两个元素拿出来计算，结果再次压栈
2013年9月23日星期一
Leetcode 中 Array Matrix相关的题目
这类题目不算难题，仔细分析题目，第一次作对的概率还是很大的。 即便没有思路，看一下答案和讲解，再次见到也很容易写出。
1. Container With Most Water
两个指针，算面积。竖边长度小的指针往中间移动
2. Valid Sudoku
创建bool三个数据结构，row，col，block分别表示某行/列/块中某个数出现过没有。 3. Trapping Rain Water
每一个柱子，除去最后一个和第一个，都有可能积水。如果它左边和右边都有比他大的柱子，那么他积水的体积取决于那两者的最小值。否则不积水 6. Spiral Matrix
提出层的概念， 每一层的层号（从0开始从外向内），每遍历一层，就去掉外层，行列数分别减2，[k,k]相当于该层左上角元素坐标。这样就好理解了 8. Rotate Image
此题与上一题很相似，但不用递归而是迭代更好些。思路是把每一层的环形表示成四个等长数组（上右下左）依次赋值。也是要先定义层的概念，设为k， 从0到n/2.这样每一层的左上角就是[k][k],这一层top行待换的元素是[k][k]..[k][n-k-1];右侧待换元素是[k][n-k-1]...[n-k-1][n-k-1]... .用offset来表示当前元素到这一组数据首元素的距离 7. Spiral Matrix II
此题比上两题简单，只需一个指针依次遍历即可。注意四个while的用法，向右-向下-向左-向上的顺序访问。 9. Merge Intervals
先按照start排序，插入第一个interval然后依次遍历一遍即可。主要是判断当前interval的start是否比已有的最后一个interval的end小，如果是的话不插入当前intervel，而是把已有的最后一个interval的end值修改位较大的end值。
10. Insert Interval
Insert比Merge 要难。 首先要找到插入点，其次要看是否需要merge。 假设当前考察的Interval[s1,e1], 要插入的是[s2,e2]. 如果e1<s2 那么把[s1,e1]插入结果，考察下一个。否则如果e2<s1, 插入[s2,e2]. 剩下的一切情况都是要merge的 取s1 s2的最小值，e1，e2的最大值，插入。
11. Set Matrix Zeros
此题思路很简单。 遍历矩阵，若[i,j]==0那么 [i,0] 和 [0,j]都要设为0。 再遍历一遍 若[i,0]或者[0,j]为0，要把[i,j]置为0. 需要注意的事一开始要把[0,j][i,0]上有无0记录一下，否则会和后面的操作混淆。 12. Maximum Rectangle
找出面积最大的全是1的矩形。先把每一行上的1累积，这样只需要访问一个点[i][j]就可以知道第i行第j列左边有几个连续的1，然后在考察这一列从上到下的累积。 13. Pascal's Triangle
先手动定义第一行 第二行，剩下的每行第一个和最后一个都是1，中间元素A[i]=B[i-1]+B[1]B是上一行元素数组 14. Pascal's Triangle II
和上题思路一样只不过不要求所有的行，那么可以只用一个数组来完成，注意要从数组的后面加到前面 15. Unique path
从matrix的左上角到右下角，每次只能往下或者往右走一步，How many possible unique paths are there? 16. Unique path II
加入了障碍。1是有障碍，0是没有
17. Triangle Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. [ [2], [3,4], [6,5,7], [4,1,8,3] ] The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
两个指针，算面积。竖边长度小的指针往中间移动
2. Valid Sudoku
创建bool三个数据结构，row，col，block分别表示某行/列/块中某个数出现过没有。 3. Trapping Rain Water
每一个柱子，除去最后一个和第一个，都有可能积水。如果它左边和右边都有比他大的柱子，那么他积水的体积取决于那两者的最小值。否则不积水 6. Spiral Matrix
提出层的概念， 每一层的层号（从0开始从外向内），每遍历一层，就去掉外层，行列数分别减2，[k,k]相当于该层左上角元素坐标。这样就好理解了 8. Rotate Image
此题与上一题很相似，但不用递归而是迭代更好些。思路是把每一层的环形表示成四个等长数组（上右下左）依次赋值。也是要先定义层的概念，设为k， 从0到n/2.这样每一层的左上角就是[k][k],这一层top行待换的元素是[k][k]..[k][n-k-1];右侧待换元素是[k][n-k-1]...[n-k-1][n-k-1]... .用offset来表示当前元素到这一组数据首元素的距离 7. Spiral Matrix II
此题比上两题简单，只需一个指针依次遍历即可。注意四个while的用法，向右-向下-向左-向上的顺序访问。 9. Merge Intervals
先按照start排序，插入第一个interval然后依次遍历一遍即可。主要是判断当前interval的start是否比已有的最后一个interval的end小，如果是的话不插入当前intervel，而是把已有的最后一个interval的end值修改位较大的end值。
10. Insert Interval
Insert比Merge 要难。 首先要找到插入点，其次要看是否需要merge。 假设当前考察的Interval[s1,e1], 要插入的是[s2,e2]. 如果e1<s2 那么把[s1,e1]插入结果，考察下一个。否则如果e2<s1, 插入[s2,e2]. 剩下的一切情况都是要merge的 取s1 s2的最小值，e1，e2的最大值，插入。
11. Set Matrix Zeros
此题思路很简单。 遍历矩阵，若[i,j]==0那么 [i,0] 和 [0,j]都要设为0。 再遍历一遍 若[i,0]或者[0,j]为0，要把[i,j]置为0. 需要注意的事一开始要把[0,j][i,0]上有无0记录一下，否则会和后面的操作混淆。 12. Maximum Rectangle
找出面积最大的全是1的矩形。先把每一行上的1累积，这样只需要访问一个点[i][j]就可以知道第i行第j列左边有几个连续的1，然后在考察这一列从上到下的累积。 13. Pascal's Triangle
先手动定义第一行 第二行，剩下的每行第一个和最后一个都是1，中间元素A[i]=B[i-1]+B[1]B是上一行元素数组 14. Pascal's Triangle II
和上题思路一样只不过不要求所有的行，那么可以只用一个数组来完成，注意要从数组的后面加到前面 15. Unique path
从matrix的左上角到右下角，每次只能往下或者往右走一步，How many possible unique paths are there? 16. Unique path II
加入了障碍。1是有障碍，0是没有
17. Triangle Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. [ [2], [3,4], [6,5,7], [4,1,8,3] ] The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
2013年9月19日星期四
Leetcode 中 DFS 深度优先搜索
DFS常用在求permutation, combination, 找出所有解，Search等等，思想就是把解看做树的叶子然后遍历之。
1. Letter combination of a Phone Number
遇到一个数字，把所有可能的字符试一遍，以此为分叉，看下一个数字。遇到1或者0没有分叉，直接看下一个数字
2. Generate Parentheses
By default 加(直到(用完，当l>n的时候可以加）。 最后缺的）一并补上 3. Next Permutation
严格意义上 Next Permutation不算是DFS，但是他巧妙的利用了DSF不同branch的关系，来更有效的得出结果。
step 1: find largest k so that num[k]<num[k+1]; if no, this is the last one. the "next" one is the smallest one in lex order. sort the array.
step 2: find lasgest l so that num[l]>num[k]; and swap.
step 3: reverse (K+1, end)
3.a 此题的另一个变种是last permutation 思路相似
step 1: find largest k so that num[k]>num[k+1];
step 2: find lasgest l so that num[l]<num[k]; and swap. if l=0, this is the first one. the "last" one is the biggest one in lex order. sort the array.
step 3: reverse (K+1, end)
4. Sudoku Solver
遍历每个格子，看是否为空，不为空就依次试1-9，检查是否合法，包括行合法，列合法，block合法。不合法就返回，否则继续试下一个格子 5. Combination Sum
这题重点在思路。首先将数字集合排序，从最小的开始依次往后挑，直到sum等于target或者没得挑了退出。 用一个index数组来记录挑到的数字 不用index数组的解法： 6. Combination Sum II
这题思路和上题一样，只不过挑过的数字就不能再挑了，i=index[n]改为i=index[n]+1 不用index数组的做法也和上题一样，把foo的实参之一i改为i＋1.同时需要注意去重 比如［1，1］＝1 会有两个相同的结果。方法是在pop_back()之后加一句：
7. Permutation
重点也是思路，依次交换： e.g. ABC, 首先看第0位，A先和A交换->ABC; A和B交换->BAC, A和C交换，CBA。 然后看第1位 ABC->ABC和ACB， BAC->BAC和BCA, CBA->CBA和CAB 注意ABC 变成 BAC之后，要变回来ABC,才能变成CBA。 8. Permutation II
思路和上题一样，区别在于 for循环里交换的时候如果num[i]==num[n],i!=n,则跳过这次交换。
9. N-Queen
此题和数独问题类似，每试一个位子，去检查合法性，合法性包括行，列，对角线。 A[i]表示第i行 第A[i]列放置Q。 10. N-Queen II
此题只要求返回解的个数。可以用上题做法，也有更简单的做法，参见http://www.matrix67.com/blog/archives/266
11. Combinations
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n
此题和permutaion相似，只是k！=n,这里用index<=0和k==0来控制分支。 两次调用foo保证了每个n都可能出现在第i位，1<=i<=k. 而且每个数字后面出现的数字都比前面的数字大，这样避免了重复 另一种方法： 12. Subsets
Given a set of distinct integers, S, return all possible subsets.
此题也是典型的DFS， 是上题k=1,..n的扩展.更直观和简单的一个解题思路是用二进制数字来表示所有的subset. 每一个二进制数字对应一个unique subset, 1表示这个位的数字有，0表示这个位子上的数字无。当然前提先把数组排序（不排序也可以做，排过序答案更整齐） 12.b Subset II
如果有重复怎么做。我们先看没重复的 S=[1,2,3]. 可能的子集是 [], [1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]. 每一次遇到新元素，其实就是加到所有的已有的set里。比如当新元素是2， 那么就要加到[], [1]中，结果是[2],[1,2]。(上题的另一种解法) 如果有重复,那么就不能加入到已有的所有set里，而是只加入上一步生成的set里。比如如果不重复，当遇到新元素3，3要加入到所有已经生成的set中，也就是 [], [1],[2],[1,2]。 但是如果是重复的set S=[1,2,2],当遇到第二个2，就不能加所有的了因为[],[1]已经加过，只需要加上一步生成的,也就是[2],[1,2] 13. Word Search
典型的DFS。 先遍历找第一个字符，找到之后进入DFS搜索模式。注意每匹配一个要做记号，防止loop。返回要把记号去掉。 14. Surrounded Regions
此题先搜索不能被包围的区域，也就是和边界联通的O，先都找出来，标记位D。然后把剩下的O（被包围的）置换成#。 最后把标记位D的位（不能被包围的）还原成O。 15. Word Ladder 这道题是典型的BFS广度优先搜索，这里一并介绍。思路其实比较简单，就是把一个word从头到位依次用a-z替换，然后插入队列末尾。记住用空格来区分不同的层。 16. Palindrome Partitioning 返回所有的partitioning 情况。典型的DFS。 17. Palindrome Partitioning II res[i] 表示s[0..i]的最小cut。res(i) = min [ res(j)+1, j=0..i-1 and s[j:i] 是回文] 0, if s[0,i] 是回文. 我们用一个矩阵mp来记录s[i,j]是不是回文
1. Letter combination of a Phone Number
遇到一个数字，把所有可能的字符试一遍，以此为分叉，看下一个数字。遇到1或者0没有分叉，直接看下一个数字
2. Generate Parentheses
By default 加(直到(用完，当l>n的时候可以加）。 最后缺的）一并补上 3. Next Permutation
严格意义上 Next Permutation不算是DFS，但是他巧妙的利用了DSF不同branch的关系，来更有效的得出结果。
step 1: find largest k so that num[k]<num[k+1]; if no, this is the last one. the "next" one is the smallest one in lex order. sort the array.
step 2: find lasgest l so that num[l]>num[k]; and swap.
step 3: reverse (K+1, end)
3.a 此题的另一个变种是last permutation 思路相似
step 1: find largest k so that num[k]>num[k+1];
step 2: find lasgest l so that num[l]<num[k]; and swap. if l=0, this is the first one. the "last" one is the biggest one in lex order. sort the array.
step 3: reverse (K+1, end)
4. Sudoku Solver
遍历每个格子，看是否为空，不为空就依次试1-9，检查是否合法，包括行合法，列合法，block合法。不合法就返回，否则继续试下一个格子 5. Combination Sum
这题重点在思路。首先将数字集合排序，从最小的开始依次往后挑，直到sum等于target或者没得挑了退出。 用一个index数组来记录挑到的数字 不用index数组的解法： 6. Combination Sum II
这题思路和上题一样，只不过挑过的数字就不能再挑了，i=index[n]改为i=index[n]+1 不用index数组的做法也和上题一样，把foo的实参之一i改为i＋1.同时需要注意去重 比如［1，1］＝1 会有两个相同的结果。方法是在pop_back()之后加一句：
7. Permutation
重点也是思路，依次交换： e.g. ABC, 首先看第0位，A先和A交换->ABC; A和B交换->BAC, A和C交换，CBA。 然后看第1位 ABC->ABC和ACB， BAC->BAC和BCA, CBA->CBA和CAB 注意ABC 变成 BAC之后，要变回来ABC,才能变成CBA。 8. Permutation II
思路和上题一样，区别在于 for循环里交换的时候如果num[i]==num[n],i!=n,则跳过这次交换。
9. N-Queen
此题和数独问题类似，每试一个位子，去检查合法性，合法性包括行，列，对角线。 A[i]表示第i行 第A[i]列放置Q。 10. N-Queen II
此题只要求返回解的个数。可以用上题做法，也有更简单的做法，参见http://www.matrix67.com/blog/archives/266
11. Combinations
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n
此题和permutaion相似，只是k！=n,这里用index<=0和k==0来控制分支。 两次调用foo保证了每个n都可能出现在第i位，1<=i<=k. 而且每个数字后面出现的数字都比前面的数字大，这样避免了重复 另一种方法： 12. Subsets
Given a set of distinct integers, S, return all possible subsets.
此题也是典型的DFS， 是上题k=1,..n的扩展.更直观和简单的一个解题思路是用二进制数字来表示所有的subset. 每一个二进制数字对应一个unique subset, 1表示这个位的数字有，0表示这个位子上的数字无。当然前提先把数组排序（不排序也可以做，排过序答案更整齐） 12.b Subset II
如果有重复怎么做。我们先看没重复的 S=[1,2,3]. 可能的子集是 [], [1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]. 每一次遇到新元素，其实就是加到所有的已有的set里。比如当新元素是2， 那么就要加到[], [1]中，结果是[2],[1,2]。(上题的另一种解法) 如果有重复,那么就不能加入到已有的所有set里，而是只加入上一步生成的set里。比如如果不重复，当遇到新元素3，3要加入到所有已经生成的set中，也就是 [], [1],[2],[1,2]。 但是如果是重复的set S=[1,2,2],当遇到第二个2，就不能加所有的了因为[],[1]已经加过，只需要加上一步生成的,也就是[2],[1,2] 13. Word Search
典型的DFS。 先遍历找第一个字符，找到之后进入DFS搜索模式。注意每匹配一个要做记号，防止loop。返回要把记号去掉。 14. Surrounded Regions
此题先搜索不能被包围的区域，也就是和边界联通的O，先都找出来，标记位D。然后把剩下的O（被包围的）置换成#。 最后把标记位D的位（不能被包围的）还原成O。 15. Word Ladder 这道题是典型的BFS广度优先搜索，这里一并介绍。思路其实比较简单，就是把一个word从头到位依次用a-z替换，然后插入队列末尾。记住用空格来区分不同的层。 16. Palindrome Partitioning 返回所有的partitioning 情况。典型的DFS。 17. Palindrome Partitioning II res[i] 表示s[0..i]的最小cut。res(i) = min [ res(j)+1, j=0..i-1 and s[j:i] 是回文] 0, if s[0,i] 是回文. 我们用一个矩阵mp来记录s[i,j]是不是回文
2013年9月18日星期三
Leetcode String 中的有难度题目
字符串处理是面试中常见题型，较难的题目包括递归，动态规划，以及DFS等。
1，正则表达式匹配
‘.’ Matches any single character.
‘*’ Matches zero or more of the preceding element. * 号必须和前一个字符相关，这是和wildcard 匹配的区别。 这道题leetcode给出的解法用递归。下面来分析一下。
给定目标串S和模式串P，如果下一位上不是*，当前位的比较就很好办了：如果P当前位是*，返回错；如果S和P的当前位不相等返回错，否则这位匹配看下一位。
如果下一位是*，那就需要看当前位是否匹配：若是，1）P的当前位下一位*可以看做出现了0次，直接比较P下下位和S当前位；或者2)判断S的下一位和P当前位是否相等，若相等*可以看做P当前位出现了两次。若S和P当前位不匹配，那么S+2， P当前位和*视为出现了0次。
string 版本，加入^和$ Iterative 2.WildCard 匹配
*不需要和前一个字符挂钩，它可以是任意长度的任意字符串。因此直接比较当前位，如果当前位匹配则看下一位。否则，若当前位不是* 返回错。 若当前位是*，需要记录当前P的位置（*的位置）然后从P的下一位开始同S的当前位继续比较。直到有不匹配的，就返回来，从P的下一位和S的下一位开始比较。。。直到匹配成功。最后若S匹配完了，而且若P剩下的都是* 返回true，否则false
3. Text Justification
这道题思路并不难，但是非常难写，细节很多。总体思想是 依次读取word并加一个空格，直到下一个word超出行数L， 此时计算出现有的长度len，那么剩余的L-len用空格补齐而且要平均分配到各个word后面。
4. Edit Distance.
两个字符串str1 和str2，每一步只能有三个选择：增加一个元素，删除一个元素，转换一个元素。求转换的最小步数。 此题是典型的DP问题。dp[i][j] 表示str1[0,i)转换到str2[0,j) 需要的步数。显然dp[i][0]=i; dp[0][j]=j。 若str1[i]=str1[j], dp[i][j]==dp[i-1][j-1]; 否则有三种变化方法： str1[i]删掉，此时dp[i][j]=dp[i-1][j]+1;str2[j]删掉，此时dp[i][j]=dp[i][j-1]+1;str1[i]替换为str2[j],dp[i][j]=dp[i-1][j-1]+1。 这三个值取最小的。
5. Scramble String
两个字符串是Scramble String 的条件： 1. 两字符串相等。2，存在中间点i， str1中前i个字符组成的串和str2中前i个字符组成的串是scramble string而且 str1中i以后的字符组成的串和str2中i以后的字符组成的串是scramble string；3. 存在中间点i， str1中前i个字符组成的串和str2中后i个字符组成的串是scramble string而且str1中i以后的字符组成的串和str2中前n-i个字符组成串是scramble string。 先看DP解法： f[i][j][k] 代表了s1从i开始，s2从j开始，长度为k的两个substring是否为scramble string。
递归解法也很明了，注意substr(i)这个函数返回i以后一直到结尾的子字符串
6. Decode Ways.
主要是11-26这几个数有两重意义。 c[i] 表示decode ways of s[0,i-1]， 如果S[i-1]不等于0，c[i]=c[i-1]; 如果S[i-2]S[i-1] 是11-26这几个数，c[i] 还得加上c[i-2]
7.Restore IP Address
用DFS 思路比较简单， 每次取三个字符 abc, 分别看a, ab, abc是否是valid，如果是就保存下来，再取剩下的三个数，否则返回。注意如果不是最后一组字符串，要加上"."
8. Interleaving Strings
check s3 是不是s1 和s2的interleaving string. 这是一个典型的DP问题，需要二维DP。 f(i, j) == f(i, j-1) && s2[j-1] == s3[i+j-1) OR f(i-1, j) && s1[i-1] == s3[i+j-1],
i, j 代表 s1, s2 的长度，f(i, j) 表示 s1[0, i), s2[0, j) 是否可以interleaving 形成 s3[0, i+j) 解释一下这个公式： 如果s1的最后一个字符和s3最后一个字符相等，说明S3最后一个字符是S1最后一个字符做的贡献，因此把他俩去掉之后，若S1和S2能形成S3， 加上他俩也一定能，这就是f(i, j) == f(i-1, j) && s1[i-1] == s3[i+j-1]的意义。
9. Distinct Subsequences
也是一个典型的DP。 用 dp[i][j] 表示 the distinct seq number of T[0,i] in S[0,j]. 如果 T[i]!=S[j]. 说明S[j] 对结果没有贡献， dp[i][j]=dp[i][j-1] e.g ab a. S[1]!=T[0] hence dp[0][1]==dp[0][0]=1 如果 S[i]==T[j] 说明 S[i]对于结果做出来了贡献， dp[i][j]=dp[i][j-1]+dp[i-1][j-1] e.g abb ab S[2]==T[1] dp[1][2]=dp[1][1]+dp[0][1]=2 再更进一步，二维DP可以用一维DP取代
10. Count and Say
每一次从上一次的结果中计算求得，主要计算连续出现同一个数字的个数 11. Palindrome Partitioning I
此题求所有可能的切割方法使得每个字串都是palindrome 用DFS 详见 see here. No.16 11. Palindrome Partitioning II
此题是求最小的cut数，使得所有的substring是回文。 典型的DP问题： 设DP[i]: s[0..i] 最少切次数。 如果s[0..i]是回文就是0 否则： DP[i]=min{DP[j-1]+1} j 属于[1,i] 且s[j,i]是回文。 palin用来判断字串s[i..j]是否为回文。 12. word break I
给一个字符串和一个字典， 看能否把这个字符串分割为几个word，这几个word在字典中都能找到。 一维DP问题 F[j]表示S[0,j)是一个valid word， F[i]=true if F[j]=true and S[j,i)是valid word. 13. word break II
在上题基础上返回所有可能的word。典型的DFS问题，但是单纯DFS会超时。这里结合上一题用一个DP数组p保存结果 p[n+1]=true if s[0,n]可以被分割。
1，正则表达式匹配
‘.’ Matches any single character.
‘*’ Matches zero or more of the preceding element. * 号必须和前一个字符相关，这是和wildcard 匹配的区别。 这道题leetcode给出的解法用递归。下面来分析一下。
给定目标串S和模式串P，如果下一位上不是*，当前位的比较就很好办了：如果P当前位是*，返回错；如果S和P的当前位不相等返回错，否则这位匹配看下一位。
如果下一位是*，那就需要看当前位是否匹配：若是，1）P的当前位下一位*可以看做出现了0次，直接比较P下下位和S当前位；或者2)判断S的下一位和P当前位是否相等，若相等*可以看做P当前位出现了两次。若S和P当前位不匹配，那么S+2， P当前位和*视为出现了0次。
string 版本，加入^和$ Iterative 2.WildCard 匹配
*不需要和前一个字符挂钩，它可以是任意长度的任意字符串。因此直接比较当前位，如果当前位匹配则看下一位。否则，若当前位不是* 返回错。 若当前位是*，需要记录当前P的位置（*的位置）然后从P的下一位开始同S的当前位继续比较。直到有不匹配的，就返回来，从P的下一位和S的下一位开始比较。。。直到匹配成功。最后若S匹配完了，而且若P剩下的都是* 返回true，否则false
3. Text Justification
这道题思路并不难，但是非常难写，细节很多。总体思想是 依次读取word并加一个空格，直到下一个word超出行数L， 此时计算出现有的长度len，那么剩余的L-len用空格补齐而且要平均分配到各个word后面。
4. Edit Distance.
两个字符串str1 和str2，每一步只能有三个选择：增加一个元素，删除一个元素，转换一个元素。求转换的最小步数。 此题是典型的DP问题。dp[i][j] 表示str1[0,i)转换到str2[0,j) 需要的步数。显然dp[i][0]=i; dp[0][j]=j。 若str1[i]=str1[j], dp[i][j]==dp[i-1][j-1]; 否则有三种变化方法： str1[i]删掉，此时dp[i][j]=dp[i-1][j]+1;str2[j]删掉，此时dp[i][j]=dp[i][j-1]+1;str1[i]替换为str2[j],dp[i][j]=dp[i-1][j-1]+1。 这三个值取最小的。
5. Scramble String
两个字符串是Scramble String 的条件： 1. 两字符串相等。2，存在中间点i， str1中前i个字符组成的串和str2中前i个字符组成的串是scramble string而且 str1中i以后的字符组成的串和str2中i以后的字符组成的串是scramble string；3. 存在中间点i， str1中前i个字符组成的串和str2中后i个字符组成的串是scramble string而且str1中i以后的字符组成的串和str2中前n-i个字符组成串是scramble string。 先看DP解法： f[i][j][k] 代表了s1从i开始，s2从j开始，长度为k的两个substring是否为scramble string。
递归解法也很明了，注意substr(i)这个函数返回i以后一直到结尾的子字符串
6. Decode Ways.
主要是11-26这几个数有两重意义。 c[i] 表示decode ways of s[0,i-1]， 如果S[i-1]不等于0，c[i]=c[i-1]; 如果S[i-2]S[i-1] 是11-26这几个数，c[i] 还得加上c[i-2]
7.Restore IP Address
用DFS 思路比较简单， 每次取三个字符 abc, 分别看a, ab, abc是否是valid，如果是就保存下来，再取剩下的三个数，否则返回。注意如果不是最后一组字符串，要加上"."
8. Interleaving Strings
check s3 是不是s1 和s2的interleaving string. 这是一个典型的DP问题，需要二维DP。 f(i, j) == f(i, j-1) && s2[j-1] == s3[i+j-1) OR f(i-1, j) && s1[i-1] == s3[i+j-1],
i, j 代表 s1, s2 的长度，f(i, j) 表示 s1[0, i), s2[0, j) 是否可以interleaving 形成 s3[0, i+j) 解释一下这个公式： 如果s1的最后一个字符和s3最后一个字符相等，说明S3最后一个字符是S1最后一个字符做的贡献，因此把他俩去掉之后，若S1和S2能形成S3， 加上他俩也一定能，这就是f(i, j) == f(i-1, j) && s1[i-1] == s3[i+j-1]的意义。
9. Distinct Subsequences
也是一个典型的DP。 用 dp[i][j] 表示 the distinct seq number of T[0,i] in S[0,j]. 如果 T[i]!=S[j]. 说明S[j] 对结果没有贡献， dp[i][j]=dp[i][j-1] e.g ab a. S[1]!=T[0] hence dp[0][1]==dp[0][0]=1 如果 S[i]==T[j] 说明 S[i]对于结果做出来了贡献， dp[i][j]=dp[i][j-1]+dp[i-1][j-1] e.g abb ab S[2]==T[1] dp[1][2]=dp[1][1]+dp[0][1]=2 再更进一步，二维DP可以用一维DP取代
10. Count and Say
每一次从上一次的结果中计算求得，主要计算连续出现同一个数字的个数 11. Palindrome Partitioning I
此题求所有可能的切割方法使得每个字串都是palindrome 用DFS 详见 see here. No.16 11. Palindrome Partitioning II
此题是求最小的cut数，使得所有的substring是回文。 典型的DP问题： 设DP[i]: s[0..i] 最少切次数。 如果s[0..i]是回文就是0 否则： DP[i]=min{DP[j-1]+1} j 属于[1,i] 且s[j,i]是回文。 palin用来判断字串s[i..j]是否为回文。 12. word break I
给一个字符串和一个字典， 看能否把这个字符串分割为几个word，这几个word在字典中都能找到。 一维DP问题 F[j]表示S[0,j)是一个valid word， F[i]=true if F[j]=true and S[j,i)是valid word. 13. word break II
在上题基础上返回所有可能的word。典型的DFS问题，但是单纯DFS会超时。这里结合上一题用一个DP数组p保存结果 p[n+1]=true if s[0,n]可以被分割。
2013年9月17日星期二
Leetcode 中的数学类题目
这里不探讨涉及到二分法的数学题 （详见 Leetcode Array 中的 Binary Search II 一文）。 这里讲的题目大部分都和某些数学概念有关，只要搞清了这些数学概念，题目就迎刃而解了。
1. Reverse Integer
此题主要考/和%的用法。 /取高位，%取低位。注意整数越界判断
2. String to Integer
此题考点与上题类似， 多了些corner case： ' ', +/-. bigger than INT_MAX, smaller than INT_MIN
3. Palindrome Number
考点类似。/取高位，%取低位。 注意%10总是取到最低位，但%div 取最高位时，div是跟着当前数字变化的（依次缩小十倍）。 因此需要有一个变量div记录当前最高位。
4. Integer to Roman
此题考罗马数字原理。不懂的话肯定是写不出来，但看到面经这题概率还不小，因此需要记一下简单的罗马数字原理。（来自wiki） 羅馬數字共有7個，即I（1）、V（5）、X（10）、L（50）、C（100）、D（500）和M（1000）
在較大的羅馬數字的右邊記上較小的羅馬數字，表示大數字加小數字。
在較大的羅馬數字的左邊記上較小的羅馬數字，表示大數字减小數字。
左减的数字有限制，仅限于I、X、C。比如45不可以写成VL，只能是XLV
左減數字必須為一位，比如8寫成VIII，而非IIX。
右加數字不可連續超過三位，比如14寫成XIV，而非XIIII
这道题题目输入1-3999，简化了计算。通过观察，阿拉伯数字的各位可以由I V X 搞定，十位可以由XLC搞定，百位由CDM搞定。因此可以有一个变量base初始化为0，阿拉伯数字没增一位base增2. 剩下的部分每一个位上其实是一样的。比如 8=VIII, 80=LXXX, 800=DCCC. 这允许我们又一次利用/ %同样的方法来对待每一位。
6. Plus One
先判断最后一位是否是9，如果不是直接加一返回。否则从倒数第二位开始检查，如果当前位不是9，那么加一返回，否则置为零检查前一位。如果前面位都是9，则需要增加一位放到最前面
7.Add Binary
思路很简单，从最后一位开始加直到任意一个数组到头，继续加剩下一个数组其余部分。注意模取余都是以2为底。
8. Valid Number 这题是数学类题目中最难的，难不是因为算法，而是状态转化图。 我认为这题最重要的是和面试官讨论状态图，代码很简单。注意终止状态只能是数字或者空格。其他一律非法。 代码不贴了，参考http://discuss.leetcode.com/questions/241/valid-number
9. Multiply Strings
笔算乘法的方法。Str1的最后一位和Str2的每一位相成，记录下进位： 10. Permutation Sequence Example n=3, k=3. str="123",fac=[1,1,2,6]. 第一个数字是str[2/2]=2,str="13";第二个数字是str[0/1]=1, str="3";第三个数字是str[0/1]=3; 11. Gray Code The gray code is a binary numeral system where two successive values differ in only one bit. Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0. For example, given n = 2, return [0,1,3,2]. Its gray code sequence is: 00, 01, 11, 10 规律是 [0]+1->[1], [1,0]+2->[3,2]. [2,3,1,0]+4=[6,7,5,4] i.e. n=k时的Gray Code，相当于n=k-1时的Gray Code的逆序 加上 pow(2,k-1)。
1. Reverse Integer
此题主要考/和%的用法。 /取高位，%取低位。注意整数越界判断
2. String to Integer
此题考点与上题类似， 多了些corner case： ' ', +/-. bigger than INT_MAX, smaller than INT_MIN
3. Palindrome Number
考点类似。/取高位，%取低位。 注意%10总是取到最低位，但%div 取最高位时，div是跟着当前数字变化的（依次缩小十倍）。 因此需要有一个变量div记录当前最高位。
4. Integer to Roman
此题考罗马数字原理。不懂的话肯定是写不出来，但看到面经这题概率还不小，因此需要记一下简单的罗马数字原理。（来自wiki） 羅馬數字共有7個，即I（1）、V（5）、X（10）、L（50）、C（100）、D（500）和M（1000）
5. Roman to Integer
这题比上题要更简单一些，做法是从低位（string的末端）开始向前扫描，若当前位的罗马数字大于等于它后面的那一位，两者相加，否则两者相减6. Plus One
先判断最后一位是否是9，如果不是直接加一返回。否则从倒数第二位开始检查，如果当前位不是9，那么加一返回，否则置为零检查前一位。如果前面位都是9，则需要增加一位放到最前面
7.Add Binary
思路很简单，从最后一位开始加直到任意一个数组到头，继续加剩下一个数组其余部分。注意模取余都是以2为底。
8. Valid Number 这题是数学类题目中最难的，难不是因为算法，而是状态转化图。 我认为这题最重要的是和面试官讨论状态图，代码很简单。注意终止状态只能是数字或者空格。其他一律非法。 代码不贴了，参考http://discuss.leetcode.com/questions/241/valid-number
9. Multiply Strings
笔算乘法的方法。Str1的最后一位和Str2的每一位相成，记录下进位： 10. Permutation Sequence Example n=3, k=3. str="123",fac=[1,1,2,6]. 第一个数字是str[2/2]=2,str="13";第二个数字是str[0/1]=1, str="3";第三个数字是str[0/1]=3; 11. Gray Code The gray code is a binary numeral system where two successive values differ in only one bit. Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0. For example, given n = 2, return [0,1,3,2]. Its gray code sequence is: 00, 01, 11, 10 规律是 [0]+1->[1], [1,0]+2->[3,2]. [2,3,1,0]+4=[6,7,5,4] i.e. n=k时的Gray Code，相当于n=k-1时的Gray Code的逆序 加上 pow(2,k-1)。
订阅：
博文 (Atom)