LeetCode题解整理版（一）

左手的ㄟ右手 2022-07-12 11:38 184阅读 0赞

LeetCode OJ is a platform for preparing technical coding interviews.

LeetCode OJ 是为与写代码有关的技术工作面试者设计的训练平台。

LeetCode OJ:[http://oj.leetcode.com/][http_oj.leetcode.com]

按照Leetcode上的顺序从上向下。可以用CTRL+F查找，如果没有的话就在题解二中。

## d ##

逆波兰表达式求值，经典问题。  
遇到数字入栈，遇到符号取栈顶的两个出来运算，再将结果入栈，最后栈里剩下的一个元素就是结果了。

题目：

**Evaluate the value of an arithmetic expression in [  
Reverse Polish Notation][Reverse Polish Notation].**

**Valid operators are**`+`**,**`-`**,**`*`**,**`/`**. Each operand may be an integer or another expression.**

**Some examples:**

["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9 ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

**另一个解法**

class Solution { public: int evalRPN(vector<string> &tokens) { stack<int> numeric; for(auto& t : tokens) { if (isdigit(t[0]) || t.size()>1) numeric.push(atoi(t.c_str())); else { int o1, o2; o2 = numeric.top(); numeric.pop(); o1 = numeric.top(); numeric.pop(); switch(t[0]) { case '+': numeric.push(o1 + o2); break; case '-': numeric.push(o1 - o2); break; case '*': numeric.push(o1 * o2); break; case '/': numeric.push(o1 / o2); break; } } } return numeric.top(); } };

温馨提示：ANSI C 规范定义了 [stof()][stof]、[atoi()][atoi]、[atol()][atol]、[strtod()][strtod]、[strtol()][strtol]、[strtoul()][strtoul] 共6个可以将字符串转换为数字的函数，大家可以对比学习。另外在 C99 / C++11 规范中又新增了5个函数，分别是 atoll()、strtof()、strtold()、strtoll()、strtoull()，在此不做介绍，请大家自行学习。

## Max Points on a Line ##

思路，暴力枚举，以每个“点”为中心，然后遍历剩余点，求出以i为起点j为终点的斜率（j>i），斜率相同的点一定共线。

对每个i，初始化一个哈希表，key 为斜率，value 为该直线上的点数。遍历结束后得到和当前i点共线的点的最大值，再和全局最大值比较，最后就是结果。

时间复杂度O(n2)，空间复杂度O(n)。

其中有几点要注意的是： 存在坐标一样的点；存在斜率不存在的点（与x轴平行的直线）

没想到什么好算法，枚举每个点，其它点以它为原点按斜率排序（我这里直接用MAP了，复杂度是一样的），复杂度O(n^2\*logn)。这道题trick比较多，注意无斜率以及点重合的情况。

另**外一个解法**

1. **public static int maxPoints(Point\[\] points) \{  **
2. **      **
3. **    if(points.length<=2) \{  **
4. **        return points.length;  **
5. **    \}  **
6. **    //斜率  **
7. **    double k = 0.0;  **
8. **    int maxPointNum      = 0;  **
9. **    int tempMaxPointNum  = 0;  **
10. **    //坐标完全相同点的个数  **
11. **    int samePointNum     = 0;  **
12. **    //与x轴平行  **
13. **    int parallelPointNum = 0;   **
14. **    HashMap<Double,Integer> slopeMap = new HashMap<Double,Integer>();  **
15. **    for(int i=0;i<points.length-1;i++) \{  **
16. **        //代表起始点，会被累加上  **
17. **        samePointNum     = 1;  **
18. **        parallelPointNum = 0;   **
19. **        tempMaxPointNum  = 0;  **
20. **        slopeMap.clear();  **
21. **        for(int j=i+1;j<points.length;j++) \{  **
22. **            //坐标完全相同  **
23. **            if((points\[i\].x == points\[j\].x)&&((points\[i\].y == points\[j\].y))) \{  **
24. **                samePointNum++;  **
25. **                continue;  **
26. **            \}  **
27. **            //与y轴平行  **
28. **            if(points\[i\].x == points\[j\].x) \{  **
29. **                parallelPointNum++;  **
30. **            \} else \{  **
31. **                if(points\[i\].y == points\[j\].y) \{  **
32. **                    k = 0;  **
33. **                \} else \{  **
34. **                    k = ((double)(points\[i\].y - points\[j\].y))/(points\[i\].x - points\[j\].x);  **
35. **                \}  **
36. **                //斜率不存在  **
37. **                if(slopeMap.get(k)==null) \{  **
38. **                    slopeMap.put(k, new Integer(1));  **
39. **                    if(1>tempMaxPointNum) \{  **
40. **                        tempMaxPointNum = 1;  **
41. **                    \}  **
42. **                \}else \{  **
43. **                    //斜率已存在  **
44. **                    int number = slopeMap.get(k);  **
45. **                    number++;  **
46. **                    slopeMap.put(k, new Integer(number));  **
47. **                    if(number>tempMaxPointNum) \{  **
48. **                        tempMaxPointNum = number;  **
49. **                    \}  **
50. **                \}  **
51. **            \}  **
52. **        \} //end of for  **
53. **          **
54. **        if(parallelPointNum>1) \{  **
55. **            if(parallelPointNum>tempMaxPointNum) \{  **
56. **                tempMaxPointNum = parallelPointNum;  **
57. **            \}  **
58. **        \}  **
59. **        //加上起始点和具有相同坐标的点  **
60. **        tempMaxPointNum += samePointNum;  **
61. **        if(tempMaxPointNum>maxPointNum) \{  **
62. **            maxPointNum = tempMaxPointNum;  **
63. **        \}  **
64. **    \}  **
65. **    return maxPointNum;  **
66. **\}  **

**![save_snippets.png][]**

第二种方法：

COPY FROM：http://blog.csdn.net/doc\_sgl/article/details/17103427

分析：

任意一条直线都可以表述为

y = ax + b

假设，有两个点(x1,y1), (x2,y2)，如果他们都在这条直线上则有

y1 = kx1 +b

y2 = kx2 +b

由此可以得到关系，k = (y2-y1)/(x2-x1)。即如果点c和点a的斜率为k, 而点b和点a的斜率也为k，可以知道点c和点b也在一条线上。

取定一个点points\[i\], 遍历其他所有节点, 然后统计斜率相同的点数，并求取最大值即可

**\[cpp\]**  [view  
plain][view plain] [copy][view plain] [print][view plain] [?][view plain] [![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1. /\*\* 
2.  \* Definition for a point. 
3.  \* struct Point \{  
4.  \*     int x; 
5.  \*     int y; 
6.  \*     Point() : x(0), y(0) \{\} 
7.  \*     Point(int a, int b) : x(a), y(b) \{\} 
8.  \* \}; 
9.  \*/  
10. **class** Solution \{  
11. **public**:  
12.     **int** maxPoints(vector<Point> &points) \{  
13.         // IMPORTANT: Please reset any member data you declared, as  
14.         // the same Solution instance will be reused for each test case.  
15.         unordered\_map<**float**,**int**> mp;  
16.         **int** maxNum = 0;  
17.         **for**(**int** i = 0; i < points.size(); i++)  
18.         \{  
19.             mp.clear();  
20.             mp\[INT\_MIN\] = 0;  
21.             **int** duplicate = 1;  
22.             **for**(**int** j = 0; j < points.size(); j++)  
23.             \{  
24.                 **if**(j == i) **continue**;  
25.                 **if**(points\[i\].x == points\[j\].x && points\[i\].y == points\[j\].y)  
26.                 \{  
27.                     duplicate++;  
28.                     **continue**;  
29.                 \}  
30.                 **float** k = points\[i\].x == points\[j\].x ? INT\_MAX : (**float**)(points\[j\].y - points\[i\].y)/(points\[j\].x - points\[i\].x);  
31.                 mp\[k\]++;  
32.             \}  
33.             unordered\_map<**float**, **int**>::iterator it = mp.begin();  
34.             **for**(; it != mp.end(); it++)  
35.                 **if**(it->second + duplicate > maxNum)  
36.                     maxNum = it->second + duplicate;  
37.         \}  
38.         **return** maxNum;  
39.     \}  
40. \};

注意：

0、points中重复出现的点。

1、int maxNum = 0;

初始化，以防points.size() ==0的情况。

2、mp\[INT\_MIN\] = 0;

保证poins中只有一个结点，还有points中只有重复元素时，mp中没有元素。这两种极端情况。

3、int duplicate = 1;

duplicate记录重复点的数量，初始化为1，是因为要把当前的点points\[i\]加进去。

4、float k = points\[i\].x == points\[j\].x ? INT\_MAX : (float)(points\[j\].y - points\[i\].y)/(points\[j\].x - points\[i\].x);

计算斜率，如果直线和y轴平行，就取INT\_MAX,否则就取(float)(points\[j\].y - points\[i\].y)/(points\[j\].x - points\[i\].x)

一开始把(float)(points\[j\].y - points\[i\].y)/(points\[j\].x - points\[i\].x)写做(float)((points\[j\].y - points\[i\].y)/(points\[j\].x - points\[i\].x))一直就不对，后来才想明白，注意注意！

## Sort List ##

在常数空间内使用O(nlogn)时间复杂度算法对链表排序。  
这题写了蛮久的，首先选择排序方法，因为链表不能够随机访问，可以想到使用归并排序，由此问题简化为如何对两个有序链表进行合并。常规的归并排序需要额外的空间来存排序好的数组，而这里因为是指针，我们只要将上一个排序好的节点的next指针指到当前两个链表中较小的节点即可，这样就不在需要额外空间了。这里有一个问题，递归中我们分别处理两段的时候，这两段链表中间的指针的next可以随便改，但是头尾指针的位置是不能改的，否则在左右两段递归出来后就可能不是一个完整的链表了。我这里的处理方法比较笨拙，强制左链表第一个端点是最小的值，而后面只处理到右端点的前一个（左递归处理的是l~m-1，右递归处理的是m~r-1，一开始传进去的r是NULL）。

## Insertion Sort List ##

不使用值交换实现插入排序  
插入排序就是不断将值插入到一个有序数组中，我这里新建了一个链表作为有序链表，插入的节点依次比较到下一个节点比它大即可插入。

## LRU Cache ##

LRU缓存算法实现，这个算法就是在缓存已满时，将最久未使用的元素移出缓存。  
经典实现就是双向链表加哈希，每次使用(get or set)都使用哈希值找到这个元素在双链表中的位置，然后将它移到最前面，如果缓存已满就删除队尾的元素。哈希中放的是元素的地址，在新增、移动和删除元素的时候都要在Hash表中作对应修改，而双向链表主要是为了方便删除。

<table style="margin:20px 0px; padding:0px; border:none; outline:0px; font-weight:inherit; font-style:inherit; font-family:inherit; font-size:16px; vertical-align:middle; border-collapse:collapse; border-spacing:0px; width:auto; color:rgb(255,255,255)"> 
 <tbody style="margin:0px; padding:0px; border:0px; outline:0px; font-weight:inherit; font-style:inherit; font-family:inherit; vertical-align:baseline"> 
 <tr style="margin:0px; padding:0px; border:0px; outline:0px; font-weight:inherit; font-style:inherit; font-family:inherit; vertical-align:baseline; height:35px"> 
 <td style="margin:0px; padding:0px; border:none; outline:0px; font-style:inherit; font-family:inherit; font-size:16px; vertical-align:middle; height:35px"> <pre style="margin-top:0px; margin-bottom:0px; padding:0px 20px 0px 0px; border:none; outline:0px; font-weight:inherit; font-style:inherit; font-family:Menlo,Consolas,'Source Code Pro',Inconsolata,Monaco,monospace; font-size:10px; vertical-align:baseline; line-height:22.4px; overflow:auto; color:rgb(153,153,153); text-align:right; background:rgb(0,43,54)">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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
</pre> </td> 
 <td style="margin:0px; padding:0px; border:none; outline:0px; font-style:inherit; font-family:inherit; font-size:16px; vertical-align:middle; height:35px"> <pre style="margin-top:0px; margin-bottom:0px; padding:0px; border:none; outline:0px; font-weight:inherit; font-style:inherit; font-family:Menlo,Consolas,'Source Code Pro',Inconsolata,Monaco,monospace; font-size:10px; vertical-align:baseline; line-height:22.4px; overflow:auto; background:rgb(0,43,54)">class Node{
 
public:
 int key, val;
 Node *pre, *next;
 Node(int k, int v): key(k), val(v), pre(NULL), next(NULL) {}
};
class LRUCache{
 
 map&lt;int, Node*&gt; mp;
 map&lt;int, Node*&gt;::iterator iter;
 int used, cap;
 Node *head, *tail;
public:
 LRUCache(int capacity) {
 
 mp.clear();
 used = 0, cap = capacity;
 head = new Node(0, 0);
 tail = new Node(0, 0);
 head-&gt;next = tail, tail-&gt;pre = head;
 }
 ~LRUCache(){
 
 for (Node *n = head, *nnext; n; n = nnext) {
 
 nnext = n-&gt;next;
 delete n;
 }
 }

 int get(int key) {
 
 if ((iter = mp.find(key)) != mp.end()) {
 
 movetoFirst(iter-&gt;second);
 return iter-&gt;second-&gt;val;
 }else
 return -1;
 }

 void set(int key, int value) {
 
 if ((iter = mp.find(key)) != mp.end()) {
 
 iter-&gt;second-&gt;val = value;
 movetoFirst(iter-&gt;second);
 } else {
 
 Node *node;
 if (used == cap) {
 
 mp.erase(tail-&gt;pre-&gt;key);
 node = tail-&gt;pre;
 node-&gt;key = key, node-&gt;val = value;
 } else {
 
 node = new Node(key, value);
 used++;
 }
 mp[node-&gt;key] = node;
 movetoFirst(node);
 }
 }
 void movetoFirst(Node *node) {
 
 if (node-&gt;pre &amp;&amp; node-&gt;next) {
 
 node-&gt;pre-&gt;next = node-&gt;next;
 node-&gt;next-&gt;pre = node-&gt;pre;
 }
 node-&gt;pre = head, node-&gt;next = head-&gt;next;
 head-&gt;next-&gt;pre = node, head-&gt;next = node;
 }

};
</pre> </td> 
 </tr> 
 </tbody> 
</table>

## Binary Tree Postorder Traversal ##

## Binary Tree Preorder Traversal ##

二叉树的非递归遍历  
这两道题见博文[另一种二叉树非递归遍历的实现][Link 1]，里面对我自己的算法和传统非递归算法都进行了实现。

## Reorder List ##

将链表L0→L1→…→Ln-1→Ln转变成L0→Ln→L1→Ln-1→L2→Ln-2，不能使用额外空间。  
将后半部分链表倒置，然后轮流合并即可。

## Linked List Cycle ##

判断一个链表是否有环(Q形，圈圈拖个尾巴)。  
两个指针，一个一次走一步，一个一次走两步，如果有圈必然会相遇。（都进圈后相当于追及问题，一次追一步，必然会追上而且不会错过）。

## Linked List Cycle II ##

找到入环指针，就是Q形链表从尾巴进入O之后的第一个指针。  
首先按照前一题的做法走到重合，这时再让其中一个指针回到起点，两者重新开始每次走一步，最后相遇的地方就是交点。为什么呢？假设尾巴长度为x，慢指针进入圈后走了一段弧长y，则第一次重合时，慢指针走了x+y。而快指针除了走了x+y外，还多绕了几个圈（假设多走了长度z），设圈的长度为k，则必有z=nk。快指针走的路程是慢指针的两倍，所以x+y+nk=2(x+y)，即nk=x+y。这时都回到起点，起点指针走了x步后到达交点，而这时另一个指针走了x=nk-y后也必然在交点。

## Word Break ##

判断一个字符串是否可以拆成字典里的词。 
DP，假设原串为`s[1..n]`，用`d[i][j]`表示`s[i..j]`是否可以有字典里的词组成，有DP方程 `d[i][j] = true if (d[i][k]&&d[k+1][j] == true,i<=k<j)` 
我写的是记忆化搜索，复杂度O（n^3）。

## Word Break II ##

上一题的加强版，需要给出所有可能的拆词方法。  
要找出所有的拆词方法，DFS是避免不了的，但是需要剪枝来优化。  
剪枝一：假设原串是`s[1...n]`，我们用`dp[i][j]=k,k>0`表示`s[i..j]`是字典中的第k个串，这里暴力就可以了，复杂度是`O(∑(n+m[k]))`，`m[k]`表示第字典中第k个串的长度，这样在搜索的时候，可以快速判断`s[i..j]`是否在字典中，以及是字典中的哪一个词。  
剪枝二：在搜索的时候，如果知道`s[i...n]`不能由字典中的词组成，就没必要往下搜了，这里可以用上一题的方法来DP，`dp[i][j]=0`表示不可以。

PS：其实这一题可以构造出有`2^(n-1)`个解的数据，令`s="a..a",dict={"a","aa","aaa",...,"a..a"}`即可，这组数据无法在多项式时间内求解。

<table style="margin:20px 0px; padding:0px; border:none; outline:0px; font-weight:inherit; font-style:inherit; font-family:inherit; font-size:16px; vertical-align:middle; border-collapse:collapse; border-spacing:0px; width:auto; color:rgb(255,255,255)"> 
 <tbody style="margin:0px; padding:0px; border:0px; outline:0px; font-weight:inherit; font-style:inherit; font-family:inherit; vertical-align:baseline"> 
 <tr style="margin:0px; padding:0px; border:0px; outline:0px; font-weight:inherit; font-style:inherit; font-family:inherit; vertical-align:baseline; height:35px"> 
 <td style="margin:0px; padding:0px; border:none; outline:0px; font-style:inherit; font-family:inherit; font-size:16px; vertical-align:middle; height:35px"> <pre style="margin-top:0px; margin-bottom:0px; padding:0px 20px 0px 0px; border:none; outline:0px; font-weight:inherit; font-style:inherit; font-family:Menlo,Consolas,'Source Code Pro',Inconsolata,Monaco,monospace; font-size:10px; vertical-align:baseline; line-height:22.4px; overflow:auto; color:rgb(153,153,153); text-align:right; background:rgb(0,43,54)">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
38
39
40
41
42
43
44
45
46
47
48
49
50
</pre> </td> 
 <td style="margin:0px; padding:0px; border:none; outline:0px; font-style:inherit; font-family:inherit; font-size:16px; vertical-align:middle; height:35px"> <pre style="margin-top:0px; margin-bottom:0px; padding:0px; border:none; outline:0px; font-weight:inherit; font-style:inherit; font-family:Menlo,Consolas,'Source Code Pro',Inconsolata,Monaco,monospace; font-size:10px; vertical-align:baseline; line-height:22.4px; overflow:auto; background:rgb(0,43,54)">class Solution {
 
public:
 vector&lt;string&gt; strRes;
 vector&lt;int&gt; seqRes;
 vector&lt;string&gt; setVec;
 vector&lt;string&gt; wordBreak(string s, unordered_set&lt;string&gt; &amp;dict) {
 
 // IMPORTANT: Please reset any member data you declared, as
 // the same Solution instance will be reused for each test case.
 unordered_set&lt;string&gt;::iterator iter;
 vector&lt;vector&lt;int&gt; &gt; dp(s.length(), vector&lt;int&gt;(s.length(), -1));
 setVec.clear();
 strRes.clear();
 seqRes.clear();
 for (string ds: dict) {
 
 setVec.push_back(ds);
 int pos = 0;
 while ((pos = s.find(ds, pos)) != string::npos)
 dp[pos][pos+ds.length()-1] = setVec.size(), pos ++;
 }
 dfs_result(dp, 0, s.length()-1);
 return strRes;
 }
 void dfs_result(vector&lt;vector&lt;int&gt; &gt; &amp;dp, int s, int e) {
 
 if (s &gt; e) {
 
 string s;
 for (int i = 0; i &lt; seqRes.size(); i++) {
 
 s.append(setVec[seqRes[i] - 1]);
 if (i != seqRes.size() - 1) s.append(" ");
 }
 strRes.push_back(s);
 return;
 }
 if (dpit(dp, s, e) == 0) return;
 for (int i = s; i &lt;= e; i++) {
 
 if (dp[s][i] &gt; 0) {
 
 seqRes.push_back(dp[s][i]);
 dfs_result(dp, i + 1, e);
 seqRes.pop_back();
 }
 }
 }
 int dpit(vector&lt;vector&lt;int&gt; &gt; &amp;dp, int l, int r) {
 
 if (dp[l][r] != -1) return dp[l][r];
 for (int i = l; i &lt; r; i++) {
 
 if (dpit(dp, l, i) &amp;&amp; dpit(dp, i+1, r))
 return dp[l][r] = -2;
 }
 return dp[l][r] = 0;
 }
};
</pre> </td> 
 </tr> 
 </tbody> 
</table>

## Copy List with Random Pointer ##

深拷贝一个链表，这个链表中除了next指针外，还有一个random指针指向链表中的某个节点。  
当然，可以Hash原链表和新链表的地址来做，这样没有什么难度，我想到了一种不使用额外空间的做法。  
用a表示原链表，b表示拷贝链表，a\[i\],b\[i\]分别表示a和b中的第i个节点。下面这段话可能比较绕，但是自己画一下应该很容易明白。  
首先第一遍遍历new出`b[1]`\->`b[n]`，并将`b[i]`放在`a[i]->random`中,`a[i]->random`放在`b[i]->next`中。然后第二遍遍历将`b[i]->random`指向`b[i]->next->random`（`b[i]->next`放的实际是`a[i]->random`，假设`a[j]=a[i]->random`，那`b[i]->next->random`中放的正是`b[j]`的地址！），这样就完成了`b[i]->random=b[j]`。最后，现在`a[i]->nex`t和`b[i]->random`都是正确的，而`a[i]->random`存在`b[i]->next`中，`b[i]->next`也可以通过`a[i]->next->random`得到，所以遍历一遍就可以将a和b都修复了。

## Single Number ##

找出只出现了一次的数，其它数都出现两次  
根据`x^x=0`以及`x^y=y^x`（交换律）,只要将所有数异或就完了。

## Single Number II ##

找出只出现了一次的数，其它数都出现三次  
上一题的扩展，其实上一题也可以这么想，将每个数看做一个32位的二进制数，统计每一位出现1的个数，假设某个数出现两次，那就为它为1的位每个位贡献了两次。如果每个数都是两个，那每位出现1的个数必然是偶数个，假设有一个位上的1出现了奇数次，那必然有一个只出现了一次的数贡献了一个1，所以只要找到哪些位1出现了奇数次就可以找到这个数了。也是基于这种思想才用异或操作来实现的。  
这一题虽然不能用异或操作来实现，但是还是可以根据上面这种思想来解。找出哪些位出现了`3n+1`次即可。我这里用位运算来实现的，`x[0]`表示出现`3n+1 or 3n+2`次的，`x[1]`表示出现`3n+2`次的，`x[2]`表示出现了`3n`次的。

## Candy ##

已知`a[1..n]`，给`b[1..n]`分配值，需满足若`a[i]>a[j]`则`b[i]>b[j]>0`。求`min∑b`。 
很简单，找到所有满足`a[i]<=a[i+1]`且`a[i]<=a[i-1]`的点，都取`b[i]=1`，然后沿着两边递增加1直到波峰即可。需要注意波峰可能会被两边上来的更新，要取较大的。 
总的复杂度O(n)。

## Gas Station ##

n个点围成一个圈，`1->2..->n->1`，到达i点可以加油`gas[i]`，i到i+1点需要花费`cost[i]`，求是否能找到一个起点保证有油转一整圈。  
这题还真的想了很久，想的比较复杂，其实正确的解法非常简单，我们可以依次推出以下两个结论。  
结论一：我们用d\[i\]\[j\]表示从i出发到j后剩余的油量，也就是`sum(gas[i]..gas[j-1])-sum(cost[i]..cost[j-1])`，假设依次有i,j,k三个点，如果`i->k`可以保持油量一直为正，并且`j->k`也可以保持油量一直为正，那么选择j做起点一定不如选择i做起点好，因为`d[i][k]= d[i][j]+d[j][k]>d[j][k]`。

根据结论一，我们假如从i点出发，到达j点后无法到达j+1点，那么i~j点都不可能作为起点，因为从这之间的任一一点出发到达j点后剩的油都不会比从i出发剩的多。  
而下一个最佳起点必然选j+1，因为假设j+1之后有点k，那么选j+2到~k之间的任一一点都不会比j+1好，原因同上。

结论二：如果总的gas大于总的cost，则必然有解。根据以上方法我们会不断更新最佳起点，假设这个序列是k1,k2..kn，有`d[k1][k2]<0`,`d[k2][k3]<0`…最后到达kn，我们知道kn必然是可以到达k1的，根据总gas大于总cost，有`d[kn][k1]+d[k1][k2]+..+d[k(n-1)][kn]>0`，于是`d[kn][k1-1]>-(d[k1][k2-1]+..+d[kn-1][kn])`，也就是说从kn走到k1后多的油量足够经过之前那些不能经过的点最终回到kn了。 
根据以上两个结论，我们可以知道当总gas大于总cost时，kn必然是一个可行解。

## Clone Graph ##

clone一张图  
将原图NODE和新图NODE之间的地址MAP映射一下，然后就是遍历原图邻接表建新图就可以了。

## Palindrome Partitioning ##

划分一个字符串为，使每个子串都是回文串，返回所有划分  
这种所有划分的必然要DFS了，只是要进行适当的剪枝。  
预处理字符串，找出所有回文串，枚举对称轴，O(n^2)的算法。我这里用vector\[i\]存了所有以第i个字符开头的回文串，然后DFS到第i位的时候，只要枚举vector\[i\]中的字符串就可以了。

## Palindrome Partitioning II ##

划分一个字符串，使每个子串都是回文串，要求划分次数最少 
DP，用`minC[i]`表示`s[1..i]`需要几刀，显然`minC[i]`最大是i。DP方程 
`minC[i] = min(i, minC[j]+1)(1<=j<=i&&isPar[j+1][i])`，`isPar[i][j]`在DP的过程中可以顺便求出来，`isPar[i][j] = true if (isPar[i+1][j-1]&&s[i]==s[j])`。 
总的复杂度O(n^2)。

## Surrounded Regions ##

给一个n\*m的由X和O组成的矩阵，要求把那些被X包围的O变成X。  
如果有一块O其中的一个或多个接触到了外边界，就不用变成X，所以从接触边缘的O开始BFS即可，BFS到的点都不用变X。我这里用Y表示一个点原本是O并且所在块没有被X全包围。最后除了Y点其它点都变成X即可。

## Sum Root to Leaf Numbers ##

从根到叶的每条路径构成一个数，求这些数的和。  
直接DFS，每次到叶子时加就可以了。其实随便一条路径长度超过9结果就超int了，想LeetCode OJ上还不至于要写BigInteger，随便用int写下果然过了。。

## Longest Consecutive Sequence ##

再一个数组中挑出一些连续的数，求最多能挑出多少  
想来想去也只能Hash了，把所有数都放到Hash里，重复的算一个就行。然后随意拿出一个数，以它为中心依次找比它大一的数以及小一的数，找到就擦除，然后记录它所在序列的长度。重复操作直到set为空为止。  
感谢unordered\_set，要不然还得自己写Hash。(直接用原来的set是O(nlogn)。)

## Word Ladder ##

给出字符串S，T以及一个词典，这些字符串长度均为N，每次可以修改S中的一个字母让它变为词典中的某个词，求从S到T最少要几步。  
边权为一的最短路，显然是BFS，我一开始使用N^2枚举建图超时了，这样复杂度是O(N^2\*len)。后来想一下如果N很大的话，不如枚举改变每个字母是否可以变成字典中的某个词，复杂读是O(N\*len\*26)。

## Word Ladder II ##

同上，只是要打印出所有最短路径。  
打印所有结果必然要DFS，重点是剪枝。  
我们称在最短路径中第N次转化后得到的字符串在第N层，可以证明，如果一个字符串在最短转化A中处于第N层，那么它在最短转化B中也处于第N层，否则A和B必然有一个不是最短转化，另外，如果第N层的a节点，可以转化为N+1层的b和c节点，那么a无论走b和c，只要最后能到目标字符串，都必然是最短路。也就是说，在BFS出的树形结构中，我们可以加一些树枝表示其它最短转化的路径，但这些树枝肯定只会连接第N～N+1层的点。所以我们先BFS一遍，用邻接表的形式存从图，每次第一次扫描到一个点时记录这个点的所在层次。这样构造了图并记录了每个点的所在层次。  
之后再从起点开始DFS,但是在相邻的点中，只走层次比自己大一的点，最后每次走到终点时将路径存入结果集即可。

<table style="margin:20px 0px; padding:0px; border:none; outline:0px; font-weight:inherit; font-style:inherit; font-family:inherit; font-size:16px; vertical-align:middle; border-collapse:collapse; border-spacing:0px; width:auto; color:rgb(255,255,255)"> 
 <tbody style="margin:0px; padding:0px; border:0px; outline:0px; font-weight:inherit; font-style:inherit; font-family:inherit; vertical-align:baseline"> 
 <tr style="margin:0px; padding:0px; border:0px; outline:0px; font-weight:inherit; font-style:inherit; font-family:inherit; vertical-align:baseline; height:35px"> 
 <td style="margin:0px; padding:0px; border:none; outline:0px; font-style:inherit; font-family:inherit; font-size:16px; vertical-align:middle; height:35px"> <pre style="margin-top:0px; margin-bottom:0px; padding:0px 20px 0px 0px; border:none; outline:0px; font-weight:inherit; font-style:inherit; font-family:Menlo,Consolas,'Source Code Pro',Inconsolata,Monaco,monospace; font-size:10px; vertical-align:baseline; line-height:22.4px; overflow:auto; color:rgb(153,153,153); text-align:right; background:rgb(0,43,54)">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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
</pre> </td> 
 <td style="margin:0px; padding:0px; border:none; outline:0px; font-style:inherit; font-family:inherit; font-size:16px; vertical-align:middle; height:35px"> <pre style="margin-top:0px; margin-bottom:0px; padding:0px; border:none; outline:0px; font-weight:inherit; font-style:inherit; font-family:Menlo,Consolas,'Source Code Pro',Inconsolata,Monaco,monospace; font-size:10px; vertical-align:baseline; line-height:22.4px; overflow:auto; background:rgb(0,43,54)">class Solution {
 
public:
 vector&lt;vector&lt;string&gt; &gt; ans;
 vector&lt;vector&lt;string&gt; &gt; findLadders(string start, string end, unordered_set&lt;string&gt; &amp;dict) {
 
 // IMPORTANT: Please reset any member data you declared, as
 // the same Solution instance will be reused for each test case.
 dict.insert(end);
 int dsize = dict.size(), len = start.length();
 unordered_map&lt;string, vector&lt;string&gt; &gt; next;
 unordered_map&lt;string, int&gt; vis;
 queue&lt;string&gt; q;
 vector&lt;string&gt; path;
 ans.clear();
 q.push(start);
 vis[start] = 0;
 while (!q.empty()) {
 
 string s = q.front(); q.pop();
 if (s == end) break;
 int step = vis[s];
 vector&lt;string&gt; snext;
 for (int i = 0; i &lt; len; i++) {
 
 string news = s;
 for (char c = 'a'; c &lt;= 'z'; c++) {
 
 news[i] = c;
 if (c == s[i] || dict.find(news) == dict.end()) continue;
 auto it = vis.find(news);
 if (it == vis.end()) {
 
 q.push(news);
 vis[news] = step + 1;
 }
 snext.push_back(news);
 }
 }
 next[s] = snext;
 }
 path.push_back(start);
 dfspath(path, next, vis, start, end);
 return ans;
 }
 void dfspath(vector&lt;string&gt; &amp;path, unordered_map&lt;string, vector&lt;string&gt; &gt; &amp;next, unordered_map&lt;string, int&gt; &amp;vis, string now, string end){
 
 //cout &lt;&lt; now &lt;&lt; endl;
 if (now == end) ans.push_back(path);
 else {
 
 auto vec = next[now];
 int visn = vis[now];
 for (int i = 0; i &lt; vec.size(); i++) {
 
 if (vis[vec[i]] != visn + 1) continue;
 path.push_back(vec[i]);
 dfspath(path, next, vis, vec[i], end);
 path.pop_back();
 }
 }
 }
};
</pre> </td> 
 </tr> 
 </tbody> 
</table>

## Valid Palindrome ##

判断是否是回文串。  
注意只有大小写字母和数字才算作串的内容，其它字符都跳过。左右两个指针逐渐往中间逼近就可以了。

## Binary Tree Maximum Path Sum ##

在二叉树中找一条路径，路径上点和加起来最大，求最大值。  
树形DP。首先应该知道最近公共祖先的概念，所谓最近公共祖先，就是从两个点(u,v)分别向根走，相遇的第一个点(s)，记为`LCA(u,v)=s`，那么最大权路径可以记为`u~s~v`，其中`u~s`从s的左子树上来，`v~s`从v的右子树上来，当然s可能等于u或者v。  
然后我们用dp\[x\]记录以x为一个端点向下走，最大能走多少。为了公式写起来方便，先假设节点的权值都大于0。当我们走到某个点x时，有可能x就是最大权路径中的s点，那么构造出来的最长路径就是`dp[x[left]->val]+dp[x[right]->val]+x->val`，之后求出dp\[x\]并往上传，`dp[x]=x->val+max(dp[x[left]->val],dp[x[right]->val])`。当DP回根节点的时候，我们已经枚举了每个节点作为s时的最大权路径，取其中最大的作为结果。  
注意如果有节点权值为负值，那么某个dp\[x\]可能为负，就是说宁愿不走，算做0就可以了。

## Best Time to Buy and Sell Stock ##

石头的价格每天不同，可以选择一天买进，在之后某一天卖出，求最大收益。全程只能交易一次。  
记录到i为止最低的价格，算出当天卖出的最大收益，然后取最大的就可以了。

## Best Time to Buy and Sell Stock II ##

与上面题面相同，只是不限买卖次数，但同一时刻只能持有一个石头。  
贪心，记录之前最低的价格，遇到比最低价格高就卖。并从当前开始继续记录最低价格。  
这题我并没有证明，只是想了几种情况，觉的是正确的（贪心题往往都是这样。。）。

## Best Time to Buy and Sell Stock III ##

题面与上题一样，买卖次数最多为两次，同一时刻只能持有一个石头。 
Stock1里，我们从前向后依次能求出当天卖出一颗石头的最大收益`pre[i]`，同理，我们也能从后向前依次求出当天买入一颗石头能得到的最大收益`last[i]`，再用`maxlast[i]=max(last[k](i<=k<=n))`表示从i~n天内买入一颗石头的最大收益，所以，`ans=max(pre[i]+maxlast[i])(1<=i<=n)`，就是说再第i天完成第一笔交易，并在第i天之后的某一天完成第二笔交易。 
总的复杂度O(n)（程序中第二次for循环的minv实际上是指从后面到当前的最大值）。

## Triangle ##

给一个三角形数组，从顶端开始向下走，每次可以走到旁边的两个，直到底端为止，使路径上的数的和最小。  
很经典的DP了，从下向上，每次可以从左下或右下上来，记录到当前点的最大值即可。

## Pascal’s Triangle ##

生成杨辉三角,`ans[i][j] = ans[i-1][j-1] + ans[i-1][j]`。

## Pascal’s Triangle II ##

生成杨辉三角第N行，第N行第i项就是二项展开式系数`C(N,i)`。  
而`C(N, i)=C(N, i-1)*(N-i+1)/i`，递推即可。

## Populating Next Right Pointers in Each Node ##

一棵完全二叉树，找到每个节点在这一层右边的点。  
直接DFS，将每个点左儿子向右全部指向右儿子向左上对应的节点。比如下图DFS到1时会将2的next指向3，5指向6。

## Populating Next Right Pointers in Each Node II ##

与上题一样，但不是完全二叉树，并且不能用额外空间。  
既然不能用额外空间，递归堆栈这些就直接不能用了。只能用上一层已经生成的next指针来逐层生成，代码还是有很多问题要注意的。

## Distinct Subsequences ##

求T作为S的子串出现了多少次(不一定连续出现)  
基础DP，`dp[i][j]`表示T\[1..i\]作为S\[1..j\]的子串出现了多少次。

## Flatten Binary Tree to Linked List ##

树转链表  
前序遍历，顺便把点链到链表上去。

## Path Sum ##

求树上有没有一条从根到叶子的路节点的值加起来为N  
DFS，到叶子判断累加值是否等于Sum

## Path Sum II ##

同上，只是要打印所有路径  
一样DFS，用一个vector存路径即可

## Minimum Depth of Binary Tree ##

求最近的叶子深度  
跟最大长度没什么不一样，注意处理下只有一个儿子的情况即可

## Balanced Binary Tree ##

判断一棵树是否是平衡树，所谓平衡树，是指每个节点的左右孩子最大深度之差不超过1  
DFS返回该节点的最大深度，过程中比较左孩子和右孩子为根的子树的最大深度即可。

## Convert Sorted List to Binary Search Tree ##

有序链表转平衡二叉树。  
要求平衡，一半放左边，一半放右边即可，递归生成。

## Convert Sorted Array to Binary Search Tree ##

有序数组转平衡二叉树。  
和上面一样，而且还不用找中点了，更简单一些

## Binary Tree Level Order Traversal II ##

记录树的每一层  
BFS当然可以，我是直接DFS然后每一层一个vector存该层的数。。

## Construct Binary Tree from Inorder and Postorder Traversal ##

根据中序和后序序列遍历构造树  
数据结构题，后序结构为`[left of x][right of x][x]`，中序结构为`[left of x][x][right of x]`，根据这样的结构递归构造即可

## Construct Binary Tree from Preorder and Inorder Traversal ##

根据前序中序遍历序列构造树  
数据结构题，前序结构为`[x][left of x][right of x]`，中序结构为`[left of x][x][right of x]`，根据这样的结构递归构造即可

## Maximum Depth of Binary Tree ##

树的最大深度  
直接DFS返回当前节点最大深度

## Binary Tree Zigzag Level Order Traversal ##

记录树的每一层，跟上面某题一样，就要前后输出顺序依次交替  
也是DFS然后vector记录每一层，奇数层reverse一下

## Binary Tree Level Order Traversal ##

还是记录树的每一层，换个输出顺序。。  
解法一样，vector记录每一层。。

## Symmetric Tree ##

判断一棵树是不是以根为对称轴中心对称的  
我是用vector保存下一层的节点，然后从两边向中间依次对比

## Same Tree ##

判断两棵树是否相同  
递归比较左子树和右子树了

## Unique Binary Search Trees ##

计算N个节点的树有多少种  
经典的DP了，dp\[n\]表示n个节点的树有dp\[n\]种，dp方程见代码

## Binary Tree Inorder Traversal ##

树的中序遍历，数据结构题，简单的遍历其实不容易写好

## Restore IP Addresses ##

将一个数字串转化成合法IP  
DFS，注意一些细节

## Simplify Path ##

对Linux系统下的绝对路径进行简化  
以`/`为分界，以栈来保存每一段，`/`和`/.`都没有意义，不用管，`/..`需要退栈，最后记得栈为空要加上根目录`/`

<table style="color:rgb(255,255,255); line-height:22.4px; margin:20px 0px; padding:0px; border:none; outline:0px; font-weight:inherit; font-style:inherit; font-family:inherit; font-size:16px; vertical-align:middle; border-collapse:collapse; border-spacing:0px; width:auto"> 
 <tbody style="margin:0px; padding:0px; border:0px; outline:0px; font-weight:inherit; font-style:inherit; font-family:inherit; vertical-align:baseline"> 
 <tr style="margin:0px; padding:0px; border:0px; outline:0px; font-weight:inherit; font-style:inherit; font-family:inherit; vertical-align:baseline; height:35px"> 
 <td style="margin:0px; padding:0px; border:none; outline:0px; font-style:inherit; font-family:inherit; font-size:16px; vertical-align:middle; height:35px"> <pre style="margin-top:0px; margin-bottom:0px; padding:0px 20px 0px 0px; border:none; outline:0px; font-weight:inherit; font-style:inherit; font-family:Menlo,Consolas,'Source Code Pro',Inconsolata,Monaco,monospace; font-size:10px; vertical-align:baseline; line-height:22.4px; overflow:auto; color:rgb(153,153,153); text-align:right; background:rgb(0,43,54)">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
</pre> </td> 
 <td style="margin:0px; padding:0px; border:none; outline:0px; font-style:inherit; font-family:inherit; font-size:16px; vertical-align:middle; height:35px"> <pre style="margin-top:0px; margin-bottom:0px; padding:0px; border:none; outline:0px; font-weight:inherit; font-style:inherit; font-family:Menlo,Consolas,'Source Code Pro',Inconsolata,Monaco,monospace; font-size:10px; vertical-align:baseline; line-height:22.4px; overflow:auto; background:rgb(0,43,54)">class Solution {
 
public:
 string simplifyPath(string path) {
 
 //cout &lt;&lt; "here" &lt;&lt; endl;
 vector&lt;string&gt; resVec;
 string ans = "";
 int pos = 0, rpos;
 while ((rpos = path.find("/", pos+1)) != string::npos) {
 
 resVec.push_back(path.substr(pos, rpos-pos));
 cal(resVec);
 pos = rpos;
 }
 resVec.push_back(path.substr(pos));
 cal(resVec);
 if (resVec.size() == 0) resVec.push_back("/");
 for (auto &amp;s: resVec) ans.append(s);
 return ans;
 }
 void cal(vector&lt;string&gt; &amp;vec) {
 
 string s = vec[vec.size() - 1];
 if (s == "/" || s == "/.") {
 
 vec.pop_back();
 } else if (s == "/..") {
 
 vec.pop_back();
 if (vec.size()) vec.pop_back();
 }
 }
};
</pre> </td> 
 </tr> 
 </tbody> 
</table>

[http_oj.leetcode.com]: http://oj.leetcode.com/
[Reverse Polish Notation]: http://en.wikipedia.org/wiki/Reverse_Polish_notation
[stof]: http://c.biancheng.net/cpp/html/124.html
[atoi]: http://c.biancheng.net/cpp/html/125.html
[atol]: http://c.biancheng.net/cpp/html/126.html
[strtod]: http://c.biancheng.net/cpp/html/128.html
[strtol]: http://c.biancheng.net/cpp/html/129.html
[strtoul]: http://c.biancheng.net/cpp/html/130.html
[save_snippets.png]: /images/20220710/00ae7fc0853748278ed4ece62eeeddb9.png
[view plain]: http://blog.csdn.net/doc_sgl/article/details/17103427#
[CODE]: https://code.csdn.net/assets/CODE_ico.png
[CODE_CODE]: https://code.csdn.net/snippets/95407
[ico_fork.svg]: https://code.csdn.net/assets/ico_fork.svg
[ico_fork.svg 1]: https://code.csdn.net/snippets/95407/fork
[Link 1]: http://c4fun.cn/blog/2013/11/21/binary-tree-nonrecursive-traversal/