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
思路很简单， 读出来如果是操作数就压栈，如果是操作符，就把栈顶的两个元素拿出来计算，结果再次压栈

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).

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]是不是回文

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]可以被分割。

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. 这允许我们又一次利用/ %同样的方法来对待每一位。

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)。

Leetcode string 类的简单题目

这类题目重点是思路，而且思路也都不难。 这类题目算是面试当中频率不低，应该拿下。
1. Longest Palindromic Substring
这道题思路是设定pivot i, 从0到n-1 对每一个i ，以i为中心，向两侧扩展直到不是回文。注意回文的两种可能，单数个字符和双数个字符。

2. ZigZag Conversion
这道题的思路是，为每一行设置一个字符序列，一个指针按之字型从上到下到上的周期性扫描。每次到达的位置和行数一一对应起来，并把这个位置的字符插入到该行的字符串（序列）中即可。 首先看这个周期，假设给定行是nRows, 那么指针从开始竖值走下来到底，行号递增一；然后变换方向，斜向上走到顶，也是行好递减一，至此一个周期走完。这个周期是竖直下来的nRows和斜向上的nRows-2 （去掉斜线的首位两个，因为已经分别算在了上半个周期和下个周期内），因此周期是2*nRows-2. 第二我们看行号，前半个周期行号递增一，后半个周期行号递减一，我们只需要把前半个周期和后半个周期的转折点找到即可，显然它是最后一行，nRows-1.

3. Longest Common Prefix
思路很简单，从每个字符串首字符开始检查当前字符串的首字符是否和下一个字符串的首字符相等。是则继续，否则退出，找到了答案。

4. length of Last Word
这道题思路简单，但是要特别注意corner case。 "a  ", "  " 等等。 一言以蔽之， 就是one pass 字符串，遇到非空格字符，当前字符长度就自增一，直到遇到空格字符长度就清零。但清零是需注意这个空格后还有没有非空格字符串，如果有则可以清零，否则不可以，因为当前求得字符串就是last word 另一种方法，用一个变量tmp记录前一个非负的count数。这样可以处理“a ”的情况
5. Valid Palindrome 这道题思路简单。首尾两个指针，遇到非字母数字的字符，无条件的向中间靠拢。遇到字符数字，比较两个指针的指向的值是否相同。不同的话就返回false
6. Implement strStr() 字符串匹配
这道题如果用brute force的方法，思路也比较简单。从匹配串的首字符开始依次比较是否与模式串相对应的字符相等。 KMP 和 rolling hash可以提高算法的效率。大部分面试不要求能写出来。
KMP 7. Reverse Words in a String
这道题要注意空字符串和首尾有空格的情况。思路就是从最后一位开始向前遍历，忽略空格。把遇到的非空格字符串拿出来加入到新字符串中（注意单个word不需要reverse或者reverse两遍）。 8. Anagrams
Given an array of strings, return all groups of strings that are anagrams.
下面这个答案在网上流传很多，实际上是错的。如果input是 vector a; a.push_back("abcd"); a.push_back("bcde"); a.push_back("cdef"); a.push_back("bcda"); a.push_back("decb"); a.push_back("edfc"); a.push_back("adcb"); a.push_back("acdb"); 结果是 abcd,bcda.bcde,decb,cdef,edfc,adcb,acdb leetcode 的test case应该没有考虑多个anagram group的情况 正确的做法应该是：

LeetCode string with visited table

这一类型的string相关的题目需要记录某个区间内字符出现的次数，需要用到hashtable。

1. Longest substring without repeating characters

i, j 来记录字字符串窗口，用exist table 记录当前字符是否在substring窗口内出现过，j++直到S[j]在当前字窗口内出现过。然后i++如果 S[i]和S[j]不一样，i++, S[i]重置为没有出现过。


2. Minimum Window Substring

两个表 一个needtofind 需要找的元素的个数，根据模式串计算得来；一个hastofind 已经找到的元素个数，根据当前window里的字符数算出。两个指针 begin end分别是窗口的起止点。 当已经找到的有效元素等于模式串的长度时，一个解已经形成，记录下来。如果begin的元素对结果没作出贡献(属于模式串而且has>needed) begin要++


3. substring of all concatenations of all words
在S中找到T中所有words的concatenation， 假设word的长度是k，可以将S切成以k为单位长度的段, 例如”barfoothefoobarman”, ["foo","bar"], 第一次从第0个开始bar foo the foo bar man, 第二次从第1个字符开始arf oot hef oob arm, 第三次rfo oth efo oba rma, 这样只需要k次循环。 同上一道题一样，也许要两个table来记录当前字符串被访问的次数和期望被访问的次数。不同的是，这道题不需要最大窗口，而是有一个固定的窗口大小（T中word的个数）。

Leetcode LinkedList II

第二类的linkedlist 比较复杂，复杂主要是在多种指针的交替赋值变换。要做好这一类题，需要对各个指针的变换有很清晰的概念。比如说删除类交换类的题目，都需要pre指针，往往会构建一个dummy node。

1. swap nodes in pairs.

p作为pre指针，q1, 和q2是要交换的节点。这个清楚了，指针赋值会很容易。最后p=p1，下一个pair的pre指针，

2. reverse nodes in K groups

这道题是非常典型的reverse类型的题。思想是两个指针 pre 和next 中间夹着k个要reverse的nodes。 初始情况下 pre的next 是last， 这个元素最终next指向next。初始情况下last的next是cur，通过不断把新元素加进来，cur不断的后移。cur最终是pre的next。

3.a. Reverse Linked List
Iterative: note the head pointer is passed by reference Recursive: 3.  Reverse Linked List II

Reverse linked list from position m to n.  我们需要找到m-1 和n+1 node 作为 pre 和next，重复2的方法即可

4. Rotate List

重点是找到倒数第k+1个元素。就可以了。需要dummy辅助node

5. Remove duplicated element in sorted Linked List I

思路比较简单，两个指针 pre=NULL 和p=head。 如果两个都不为空且值相等，删除p的节点，p重新指向下一个。否则两个一起前进。

5.1 Remove duplicated element in sorted Linked List II

上题中重复数字需要保留一个因此不需要重复数字之前的pre指针。这道题要求把所有的重复数字都删掉，因此重复数字之前的pre是需要的。

6. Remove element in Linked List 这道题需要将head和其他元素分开考虑

7. Copy List with Random Pointer
这道题需要一个巧妙的解法。 1.把每个node复制一遍，然后把copy插到这个node后面去（A->B 变成 A->A->B->B）然后node->random->next 赋给node->next->random. thats it!

8. LinkList Cycle
思路很简单，一快一慢两个指针，快的每次走两步，慢的走一步。初始他们都指向head。如果他们未来再次相遇，那么就是有cycle

8. LinkList Cycle II
思路不太好想。 需要利用上题结果。当快慢指针相遇的时候，把其中一个重新指向head，然后两个指针同时同速前进，第二次相遇的地方就是cycle起点。 思路的正确性证明参加cc150 2.5. 知道思路之后代码就很容易了

9. Reorder List
用一快一慢指针找到list的中点。把后半部分list reverse。 然后再把前后两部分list merge. 11. LRU Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
为数不多的需要用到双链表的题目。 两个数据结构，一个是hashtable，key是 key， value是key在双链表中的地址。 一个是双链表，用于快速查找key， 快速把最近更新的key放到头部。 双链表需要维护一个tail指针，当满了的时候，需要把tail的元素(least updated)删除。 12. Insertion Sort List: Sort a linked list using insertion sort.
首先一个指针b遍历list，然后一个指针a从头节点遍历到b.如果a>b那么就把b插到a前面。然后b回到原来的位置的后一个。循环。
注意b插a前面需要a的pre指针，记做p.a就是p->next. 把b从原来位置删除也许要前继指针，我们记做pre。 13. Sort List. Sort a linked list in O(n log n) time using constant space complexity.
用归并排序。把list一分为二(用slow和fast指针)，直到子list只有一个或者两个元素。 对他们排序后把两个排好序的子list和在一起。

Leetcode LinkedList I

Linked List 是比较难的数据结构。不断的变化指针非常容易出错。需要理清思路，切勿硬背。第一类的linkedlist 复杂度稍低，基本都是顺序操作，思路简单，不容易写错。

1. Remove nth node from end  in linkedlist

这道题目思路很简单，主要是定位从后往前数第n个元素，然后把他的前一个的next赋值为他的next即可。注意第一个for循环后 fast-slow=n. 然后两者一起前进直到fast是最后一个元素 此时slow是倒数第n+1个元素 (fast-slow=n) 也就是要删除元素的前一个。

2. Merge two sorted List

这道题并不需要创建新的节点空间，只需要把原有节点next修改即可。辅助dummy node，比较p1 和p2 的第一个元素那个大，地址赋给dummy node的next 然后递增。最后把剩下的接上即可。注意判断空指针


3. Merge K sorted List

这道题List的部分很简单。这道题的主要考点在于heap的用法。思路并不难：把K sorted List想象成k个柱子，最顶上的是最小值。然后从空中俯瞰，是k个最小值。把这k个最小值排入heap，并作以下一些处理： heap的第一个元素（k个最小值里的最小值，也就是全局最小值）加入新建list；pop_heap, 把heap第一个元素所在的柱子放到heap的末尾；再把这根柱子第一个元素弹出，剩下的元素重新组成这个柱子；再把这根柱子push_back回heap。这样每次能保证没跟柱子的最小值中的最小值可以被选走。


4. Partition List

这题如果用对付array的方法做，会很麻烦。比较好的方法是新建一个list，用来存原list中小于x的节点，同时原list将这个节点删去，最后把原list接在新建list上即可。


5. Add two numbers:Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8