分享我的Lintcode题解，目前进度244/248

Candy
题意：hard难度。发糖果。规定每个孩子至少一颗糖，而且分数比隔壁高的孩子，得到的糖果也要多于隔壁。
解法：这题比较有意思。第一次碰见时，我花了很久想O(1)空间的解法，始终没有找到简洁易懂的思路。后来还是用O(N)空间的方法解决了。不过O(N)空间的这个解法，倒是非常直观。
代码：

1. // O(n) time and space. How to reach O(1) space?
   
2. class Solution {
   
3. public:
   
4.     /**
   
5.      * @param ratings Children's ratings
   
6.      * @return the minimum candies you must give
   
7.      */
   
8.     int candy(vector<int> &ratings) {
   
9.         vector<int> &a = ratings;
   
10.         int n = a.size();
    
11.         vector<int> c(n, 1);
    
12.         int i;
    
13.         for (i = 1; i <= n - 1; ++i) {
    
14.             if (a[i] > a[i - 1]) {
    
15.                 c[i] = c[i - 1] + 1;
    
16.             }
    
17.         }
    
18.         for (i = n - 2; i >= 0; --i) {
    
19.             if (a[i] > a[i + 1] && c[i] <= c[i + 1]) {
    
20.                 c[i] = c[i + 1] + 1;
    
21.             }
    
22.         }
    
23.         int sum = 0;
    
24.         for (i = 0; i <= n - 1; ++i) {
    
25.             sum += c[i];
    
26.         }
    
27.         return sum;
    
28.     }
    
29. };

复制代码

复杂度：时间O(N)，空间O(N)。

House Robber
题意：给定一个数组，允许你从中选出一些元素，但选取的元素必须互不相邻。求能够得到的最大和。
解法：这是典型的动态规划问题，而且空间可以优化成O(1)。依然从局部最优，全局最优着手。
代码：

1. typedef long long int LL;
   
2. 
   
3. LL max(LL x, LL y)
   
4. {
   
5.     return x > y ? x : y;
   
6. }
   
7. 
   
8. class Solution {
   
9. public:
   
10.     /**
    
11.      * @param A: An array of non-negative integers.
    
12.      * return: The maximum amount of money you can rob tonight
    
13.      */
    
14.     LL houseRobber(vector<int> A) {
    
15.         int n = A.size();
    
16.         LL a1, a2, a3, a4;
    
17.         LL ans;
    
18.         
    
19.         if (n == 0) {
    
20.             return 0;
    
21.         } else if (n == 1) {
    
22.             return A[0];
    
23.         } else if (n == 2) {
    
24.             return max(A[0], A[1]);
    
25.         }
    
26.         A[2] += A[0];
    
27.         ans = max(A[0], A[1]);
    
28.         ans = max(ans, A[2]);
    
29.         
    
30.         int i;
    
31.         a1 = A[0];
    
32.         a2 = A[1];
    
33.         a3 = A[2];
    
34.         for (i = 3; i < n; ++i) {
    
35.             a4 = max(a1, a2) + A[i];
    
36.             ans = max(ans, a4);
    
37.             a1 = a2;
    
38.             a2 = a3;
    
39.             a3 = a4;
    
40.         }
    
41.         return ans;
    
42.     }
    
43. };

复制代码

复杂度：时间O(N)，空间O(1)。

Best Time to Buy and Sell Stock IV
题意：hard难度。给定股价，允许至多进行K次买卖，求最大收益。
解法：和最大K子字段和问题类似，动态规划的题目。请注意代码中的循环方向，如果反过来就会错。代码中前半部分是对于一种特殊情况的处理，即涨价的次数还不到K次，此时直接贪婪即可。
代码：

1. // O(n * k) DP, global and local optimal
   
2. class Solution {
   
3. public:
   
4.     /**
   
5.      * @param k: An integer
   
6.      * @param prices: Given an integer array
   
7.      * @return: Maximum profit
   
8.      */
   
9.     int maxProfit(int k, vector<int> &prices) {
   
10.         vector<int> &a = prices;
    
11.         int i, j;
    
12.         int n = a.size();
    
13.         j = 0;
    
14.         int sum = 0;
    
15.         for (i = 0; i < n - 1; ++i) {
    
16.             if (a[i] < a[i + 1]) {
    
17.                 sum += a[i + 1] - a[i];
    
18.                 ++j;
    
19.             }
    
20.         }
    
21.         if (j <= k) {
    
22.             return sum;
    
23.         }
    
24.         
    
25.         vector<int> local(k + 1, 0), global(k + 1, 0);
    
26.         int diff;
    
27.         for (i = 1; i < n; ++i) {
    
28.             diff = a[i] - a[i - 1];
    
29.             // j from k to 1, why?
    
30.             for (j = k; j >= 1; --j) {
    
31.                 local[j] = max(global[j - 1] + max(diff, 0), local[j] + diff);
    
32.                 global[j] = max(global[j], local[j]);
    
33.             }
    
34.         }
    
35.         return global[k];
    
36.     }
    
37. };

复制代码

复杂度：时间O(K * N)，空间O(K)。

Coins in a Line
题意：巴什博弈。
解法：博弈问题一般都是很难的（只要稍微加些条件，就能让人吐血），巴什博弈估计是能碰见的最简单问题了。话说这方面有什么比较好的入门书籍吗？运筹学或者组合数学的？我想有针对性地学习一下，求推荐。
代码：

1. class Solution {
   
2. public:
   
3.     /**
   
4.      * @param n: an integer
   
5.      * @return: a boolean which equals to true if the first player will win
   
6.      */
   
7.     bool firstWillWin(int n) {
   
8.                 return n % 3 != 0;
   
9.     }
   
10. };

复制代码

复杂度：时间O(1)，空间O(1)。

Coins in a Line II
题意：有N枚价值不尽相同的硬币摆成一排，两个玩家轮流从左侧拿走硬币。规定每人每次只能拿一或两枚。最后得到价值大的人赢。请问先手玩家是赢是输？
解法：这题就不能直接公式解了，于是采取动态规划的办法。考虑的是用dp{i}{j}表示先手玩家在i~j这段里最多能拿到的最大价值。递推关系参加代码。
代码：

1. // Solution using DP
   
2. #include <algorithm>
   
3. using namespace std;
   
4. 
   
5. class Solution {
   
6. public:
   
7.     /**
   
8.      * @param values: a vector of integers
   
9.      * @return: a boolean which equals to true if the first player will win
   
10.      */
    
11.     bool firstWillWin(vector<int> &values) {
    
12.         int n = values.size();
    
13.         if (n <= 2) {
    
14.             return true;
    
15.         }
    
16.         
    
17.         vector<vector<int> > dp;
    
18.         dp.resize(n, vector<int>(n, 0));
    
19.         vector<int> sum;
    
20.         sum.resize(n + 1, 0);
    
21.         
    
22.         int i, j;
    
23.         for (i = 0; i < n; ++i) {
    
24.             dp[i][i] = values[i];
    
25.             sum[i + 1] = sum[i] + values[i];
    
26.         }
    
27.         for (i = 0; i < n - 1; ++i) {
    
28.             dp[i][i + 1] = values[i] + values[i + 1];
    
29.         }
    
30.         for (i = 2; i < n; ++i) {
    
31.             for (j = 0; j + i < n; ++j) {
    
32.                 // Think about why?
    
33.                 dp[j][j + i] = max(dp[j][j + i], sum[j + i + 1] - sum[j] - dp[j + 1][j + i]);
    
34.                 dp[j][j + i] = max(dp[j][j + i], sum[j + i + 1] - sum[j] - dp[j + 2][j + i]);
    
35.             }
    
36.         }
    
37.         return dp[0][n - 1] > sum[n] - dp[0][n - 1];
    
38.     }
    
39. };

复制代码

复杂度：时间O(N ^ 2)，空间O(N ^ 2)。

Subtree
题意：给定两棵二叉树T1和T2，判断T2是否为T1的子树。此处子树的定义是，可以找到某个T1的节点，如果以这节点为根的话，就和T2长得一模一样。
解法1：暴力递归解决，效率并不高。感觉这题很像字符串匹配里的text=”aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa“，pattern=”aaaab“这种情况。如果总是在结尾才发现匹配失败的话，效率会变得很低。所以这题的数据肯定是很宽容的，否则不可能AC。如果能像AC自动机那样计算出每个节点的回溯位置，是不是可以提高效率呢？
代码1：

1. /**
   
2. * Definition of TreeNode:
   
3. * class TreeNode {
   
4. * public:
   
5. *     int val;
   
6. *     TreeNode *left, *right;
   
7. *     TreeNode(int val) {
   
8. *         this->val = val;
   
9. *         this->left = this->right = NULL;
   
10. *     }
    
11. * }
    
12. */
    
13. class Solution {
    
14. public:
    
15.     /**
    
16.      * @param T1, T2: The roots of binary tree.
    
17.      * @return: True if T2 is a subtree of T1, or false.
    
18.      */
    
19.     bool isSubtree(TreeNode *T1, TreeNode *T2) {
    
20.         if (sameTree(T1, T2)) {
    
21.             return true;
    
22.         }
    
23.         if (T1 == NULL) {
    
24.             return false;
    
25.         }
    
26.         return isSubtree(T1->left, T2) || isSubtree(T1->right, T2);
    
27.     }
    
28. private:
    
29.     bool sameTree(TreeNode *r1, TreeNode *r2) {
    
30.         if (r1 == NULL) {
    
31.             if (r2 == NULL) {
    
32.                 return true;
    
33.             }
    
34.             return false;
    
35.         }
    
36.         if (r2 == NULL) {
    
37.             return false;
    
38.         }
    
39.         if (r1->val != r2->val) {
    
40.             return false;
    
41.         }
    
42.         return sameTree(r1->left, r2->left) && sameTree(r1->right, r2->right);
    
43.     }
    
44. };

复制代码

复杂度1：时间O(N1 * N2)，空间一样。

解法2：依然是暴力搜索，但加上判断高度的条件。如果两棵树高度不一样，肯定不可能相同。没想到运行时间比第一种还慢，不解。
代码2：

1. #include <unordered_map>
   
2. using namespace std;
   
3. /**
   
4. * Definition of TreeNode:
   
5. * class TreeNode {
   
6. * public:
   
7. *     int val;
   
8. *     TreeNode *left, *right;
   
9. *     TreeNode(int val) {
   
10. *         this->val = val;
    
11. *         this->left = this->right = NULL;
    
12. *     }
    
13. * }
    
14. */
    
15. class Solution {
    
16. public:
    
17.     /**
    
18.      * @param T1, T2: The roots of binary tree.
    
19.      * @return: True if T2 is a subtree of T1, or false.
    
20.      */
    
21.     bool isSubtree(TreeNode *T1, TreeNode *T2) {
    
22.         height.clear();
    
23.         height[NULL] = 0;
    
24.         calcHeight(T1);
    
25.         calcHeight(T2);
    
26.         return subtree(T1, T2);
    
27.     }
    
28. private:
    
29.     unordered_map<TreeNode *, int> height;
    
30.    
    
31.     bool subtree(TreeNode *T1, TreeNode *T2) {
    
32.         if (sameTree(T1, T2)) {
    
33.             return true;
    
34.         }
    
35.         if (T1 == NULL) {
    
36.             return false;
    
37.         }
    
38.         return subtree(T1->left, T2) || subtree(T1->right, T2);
    
39.     }
    
40.    
    
41.     void calcHeight(TreeNode *root) {
    
42.         if (root == NULL) {
    
43.             return;
    
44.         }
    
45.         calcHeight(root->left);
    
46.         calcHeight(root->right);
    
47.         height[root] = max(height[root->left], height[root->right]) + 1;
    
48.     }
    
49.    
    
50.     bool sameTree(TreeNode *r1, TreeNode *r2) {
    
51.         if (height[r1] != height[r2]) {
    
52.             // No need to go further
    
53.             return false;
    
54.         }
    
55.         if (r1 == NULL) {
    
56.             if (r2 == NULL) {
    
57.                 return true;
    
58.             }
    
59.             return false;
    
60.         }
    
61.         if (r2 == NULL) {
    
62.             return false;
    
63.         }
    
64.         if (r1->val != r2->val) {
    
65.             return false;
    
66.         }
    
67.         return sameTree(r1->left, r2->left) && sameTree(r1->right, r2->right);
    
68.     }
    
69. };

复制代码

复杂度2：时间O(N1 * N2)，空间一样。

解法3：刚才在解法1中提到了AC自动机里那种建立回溯指针的思路，实际写了之后，发现比较难，搞不定。于是我又从KMP的角度去入手。想出了这么个思路：如果T1的前序和中序遍历中都包含了T2的前序和中序遍历，那么T2就是T1的子树。此处的遍历序列还要把空指针也表示进去，否则就会出现二义性。比如前序{1,1,1}，中序{1,1,1}，这样你无法确定这棵树长什么样，如果变成{1,#,1,#,1,#,#}和{#,1#,1,#,1,#}，就没有二义性了。得到两棵树的前序、中序序列之后，按照T1作为文本，T2作为模式，进行KMP匹配。就可以在线性时间求出结果了。
当然，这么做写起来是很麻烦的，我的KMP代码都是copy自己以前写的。
代码3：

1. // This is my idea :)
   
2. #include <climits>
   
3. #include <vector>
   
4. using std::vector;
   
5. /**
   
6. * Definition of TreeNode:
   
7. * class TreeNode {
   
8. * public:
   
9. *     int val;
   
10. *     TreeNode *left, *right;
    
11. *     TreeNode(int val) {
    
12. *         this->val = val;
    
13. *         this->left = this->right = NULL;
    
14. *     }
    
15. * }
    
16. */
    
17. typedef long long int LL;
    
18. class Solution {
    
19. public:
    
20.     /**
    
21.      * @param T1, T2: The roots of binary tree.
    
22.      * @return: True if T2 is a subtree of T1, or false.
    
23.      */
    
24.     bool isSubtree(TreeNode *T1, TreeNode *T2) {
    
25.         if (T1 == NULL) {
    
26.             return T2 == NULL;
    
27.         }
    
28.         if (T2 == NULL) {
    
29.             return true;
    
30.         }
    
31.         pre1.clear();
    
32.         pre2.clear();
    
33.         in1.clear();
    
34.         in2.clear();
    
35.         
    
36.         preorder(T1, pre1);
    
37.         preorder(T2, pre2);
    
38.         inorder(T1, in1);
    
39.         inorder(T2, in2);
    
40.         
    
41.         return KMPMatch(pre1, pre2) && KMPMatch(in1, in2);
    
42.     }
    
43. private:
    
44.     vector<LL> pre1, in1, pre2, in2;
    
45.     vector<int> next;
    
46.     int ls, lt;
    
47.    
    
48.     void preorder(TreeNode *r, vector<LL> &v) {
    
49.         if (r == NULL) {
    
50.             v.push_back(LONG_LONG_MAX);
    
51.             return;
    
52.         }
    
53.         v.push_back(r->val);
    
54.         preorder(r->left, v);
    
55.         preorder(r->right, v);
    
56.     }
    
57.    
    
58.     void inorder(TreeNode *r, vector<LL> &v) {
    
59.         if (r == NULL) {
    
60.             v.push_back(LONG_LONG_MAX);
    
61.             return;
    
62.         }
    
63.         inorder(r->left, v);
    
64.         v.push_back(r->val);
    
65.         inorder(r->right, v);
    
66.     }
    
67.    
    
68.     void getNext(vector<LL> &t) {
    
69.         int i, j;
    
70.         i = 0;
    
71.         j = -1;
    
72.         
    
73.         next.clear();
    
74.         next.resize(lt + 1);
    
75.         next[0] = -1;
    
76.         while (i < lt) {
    
77.             if (j == -1 || t[i] == t[j]) {
    
78.                 ++i;
    
79.                 ++j;
    
80.                 next[i] = j;
    
81.             } else {
    
82.                 j = next[j];
    
83.             }
    
84.         }
    
85.     }
    
86.    
    
87.     bool KMPMatch(vector<LL> &s, vector<LL> &t) {
    
88.         ls = s.size();
    
89.         lt = t.size();
    
90.         getNext(t);
    
91.         
    
92.         int i, j;
    
93.         i = j = 0;
    
94.         while (i < ls) {
    
95.             if (j == -1 || s[i] == t[j]) {
    
96.                 ++i;
    
97.                 ++j;
    
98.             } else {
    
99.                 j = next[j];
    
100.             }
     
101.             if (j == lt) {
     
102.                 return true;
     
103.             }
     
104.         }
     
105.         return false;
     
106.     }
     
107. };

复制代码

复杂度3：时间O(N1 + N2)，空间一样。

Delete Node in the Middle of Singly Linked List
题意：给你一个单链表中的节点，请把它删掉。
解法：把下一个点的值拷过来，然后删除下一个节点即可。如果是尾巴，就没办法了。
代码：

1. /**
   
2. * Definition of ListNode
   
3. * class ListNode {
   
4. * public:
   
5. *     int val;
   
6. *     ListNode *next;
   
7. *     ListNode(int val) {
   
8. *         this->val = val;
   
9. *         this->next = NULL;
   
10. *     }
    
11. * }
    
12. */
    
13. class Solution {
    
14. public:
    
15.     /**
    
16.      * @param node: a node in the list should be deleted
    
17.      * @return: nothing
    
18.      */
    
19.     void deleteNode(ListNode *node) {
    
20.         ListNode *p = node->next;
    
21.         node->val = p->val;
    
22.         node->next = p->next;
    
23.         delete p;
    
24.     }
    
25. };

复制代码

复杂度：时间O(1)，空间O(1)。

Fibonacci
题意：求斐波那契数。
解法：这么小的数据范围，就别折腾对数解法了。顺便提一句，斐波那契数可以用指数、线性、对数、常数时间算出。四种解法的应用场景各不一样，其中第一种用于找抽，第二种用于小数据，第三种用于大数据，第四种用于允许一定误差的浮点数相关问题。
代码：

1. class Solution{
   
2. public:
   
3.     /**
   
4.      * @param n: an integer
   
5.      * @return an integer f(n)
   
6.      */
   
7.     int fibonacci(int n) {
   
8.         if (n == 1) {
   
9.             return 0;
   
10.         }
    
11.         if (n == 2) {
    
12.             return 1;
    
13.         }
    
14.         int a1 = 0;
    
15.         int a2 = 1;
    
16.         int a3;
    
17.         int i;
    
18.         for (i = 3; i <= n; ++i) {
    
19.             a3 = a1 + a2;
    
20.             a1 = a2;
    
21.             a2 = a3;
    
22.         }
    
23.         return a3;
    
24.     }
    
25. };

复制代码

复杂度：时间O(N)，空间O(1)。

Count 1 in Binary
题意：求一个整数的二进制表示中有多少个1。
解法：lowbit，第一次看见这题是在《编程之美》上。
代码：

1. class Solution {
   
2. public:
   
3.     /**
   
4.      * @param num: an integer
   
5.      * @return: an integer, the number of ones in num
   
6.      */
   
7.     int countOnes(int num) {
   
8.         int c;
   
9.         while (num > 0) {
   
10.             num = num & num - 1;
    
11.             ++c;
    
12.         }
    
13.         return c;
    
14.     }
    
15. };

复制代码

复杂度：O(log(N))，空间O(1)。

Merge Intervals
题意：给定一些区间，把它们合并成为互不相交的区间。
解法：首先自然要排序，按照两个维度依次升序。然后计算每个区间能够合并掉它前面的多少个区间，整个扫一遍就行了，时间O(N)。
代码：

1. #include <algorithm>
   
2. using namespace std;
   
3. /**
   
4. * Definition of Interval:
   
5. * classs Interval {
   
6. *     int start, end;
   
7. *     Interval(int start, int end) {
   
8. *         this->start = start;
   
9. *         this->end = end;
   
10. *     }
    
11. */
    
12. bool comp(const Interval &i1, const Interval &i2)
    
13. {
    
14.     if (i1.start != i2.start) {
    
15.         return i1.start < i2.start;
    
16.     } else {
    
17.         return i1.end < i2.end;
    
18.     }
    
19. }
    
20. 
    
21. class Solution {
    
22. public:
    
23.     /**
    
24.      * @param intervals: interval list.
    
25.      * @return: A new interval list.
    
26.      */
    
27.     vector<Interval> merge(vector<Interval> &intervals) {
    
28.         vector<Interval> &a = intervals;
    
29.         sort(a.begin(), a.end(), comp);
    
30.         
    
31.         int n = a.size();
    
32.         if (n == 0) {
    
33.             return vector<Interval>();
    
34.         }
    
35.         int i, j;
    
36.         vector<Interval> ans;
    
37.         
    
38.         j = 0;
    
39.         ans.push_back(a[0]);
    
40.         for (i = 1; i < n; ++i) {
    
41.             if (a[i].start > ans[j].end) {
    
42.                 ++j;
    
43.                 ans.push_back(a[i]);
    
44.                 continue;
    
45.             }
    
46.             ans[j].end = max(ans[j].end, a[i].end);
    
47.         }
    
48.         return ans;
    
49.     }
    
50. };

复制代码

复杂度：时间O(N * log(N))，空间O(1)。