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

Reverse Linked List
题意：反转链表
解法：不用new额外的结点。
代码：

1. /**
   
2. * Definition of ListNode
   
3. *
   
4. * class ListNode {
   
5. * public:
   
6. *     int val;
   
7. *     ListNode *next;
   
8. *
   
9. *     ListNode(int val) {
   
10. *         this->val = val;
    
11. *         this->next = NULL;
    
12. *     }
    
13. * }
    
14. */
    
15. class Solution {
    
16. public:
    
17.     /**
    
18.      * @param head: The first node of linked list.
    
19.      * @return: The new head of reversed linked list.
    
20.      */
    
21.     ListNode *reverse(ListNode *head) {
    
22.         if (head == NULL) {
    
23.             return NULL;
    
24.         }
    
25.         ListNode *h = head;
    
26.         head = head->next;
    
27.         h->next = NULL;
    
28.         
    
29.         ListNode *p;
    
30.         while (head != NULL) {
    
31.             p = head;
    
32.             head = head->next;
    
33.             p->next = h;
    
34.             h = p;
    
35.         }
    
36.         return h;
    
37.     }
    
38. };

复制代码

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

Reverse Linked List II
题意：依然是反转链表，但这次规定了起点和终点
解法：因为起点终点可能是/不是头和尾，所以要分情况处理。虽然是medium题，但实战中如果遇到，其实很容易出错的，要多加小心。
代码：

1. /**
   
2. * Definition of singly-linked-list:
   
3. *
   
4. * class ListNode {
   
5. * public:
   
6. *     int val;
   
7. *     ListNode *next;
   
8. *     ListNode(int val) {
   
9. *        this->val = val;
   
10. *        this->next = NULL;
    
11. *     }
    
12. * }
    
13. */
    
14. class Solution {
    
15. public:
    
16.     /**
    
17.      * @param head: The head of linked list.
    
18.      * @param m: The start position need to reverse.
    
19.      * @param n: The end position need to reverse.
    
20.      * @return: The new head of partial reversed linked list.
    
21.      */
    
22.     ListNode *reverseBetween(ListNode *head, int m, int n) {
    
23.         if (head == NULL) {
    
24.             return head;
    
25.         }
    
26.         int len = 0;
    
27.         ListNode *p = head;
    
28.         while (p != NULL) {
    
29.             p = p->next;
    
30.             ++len;
    
31.         }
    
32.         ListNode *t1, *h2, *h3;
    
33.         
    
34.         int i;
    
35.         if (m == 1) {
    
36.             t1 = NULL;
    
37.         } else {
    
38.             t1 = head;
    
39.             for (i = 2; i < m; ++i) {
    
40.                 t1 = t1->next;
    
41.             }
    
42.         }
    
43.         
    
44.         p = head;
    
45.         for (i = 1; i < n; ++i) {
    
46.             p = p->next;
    
47.         }
    
48.         h3 = p->next;
    
49.         p->next = NULL;
    
50.         
    
51.         ListNode *t2;
    
52.         ListNode *tmp;
    
53.         
    
54.         p = t1 != NULL ? t1->next : head;
    
55.         h2 = t2 = p;
    
56.         p = p->next;
    
57.         t2->next = h3;
    
58.         while (p != NULL) {
    
59.             tmp = p->next;
    
60.             p->next = h2;
    
61.             h2 = p;
    
62.             p = tmp;
    
63.         }
    
64.         if (t1 != NULL) {
    
65.             t1->next = h2;
    
66.             return head;
    
67.         } else {
    
68.             return h2;
    
69.         }
    
70.     }
    
71. };

复制代码

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

Search a 2D Matrix II
题意：在杨氏矩阵中查找一个值出现的次数。
解法1：从右上角或者左下角出发，直到无路可走。中间根据访问到的值大于/小于/等于目标值，调整下一步应该走的位置。这题应该还可以用类似二分的四分法来做，以达到更优的复杂度。
代码1：

1. class Solution {
   
2. public:
   
3.     /**
   
4.      * @param matrix: A list of lists of integers
   
5.      * @param target: An integer you want to search in matrix
   
6.      * @return: An integer indicate the total occurrence of target in the given matrix
   
7.      */
   
8.     int searchMatrix(vector<vector<int> > &matrix, int target) {
   
9.         vector<vector<int> > &a = matrix;
   
10.         int n, m;
    
11.         n = a.size();
    
12.         if (n == 0) {
    
13.             return 0;
    
14.         }
    
15.         m = a[0].size();
    
16.         if (m == 0) {
    
17.             return 0;
    
18.         }
    
19.         
    
20.         int i, j;
    
21.         int ans = 0;
    
22.         i = 0;
    
23.         j = m - 1;
    
24.         while (i <= n - 1 && j >= 0) {
    
25.             if (a[i][j] < target) {
    
26.                 ++i;
    
27.             } else if (a[i][j] > target) {
    
28.                 --j;
    
29.             } else {
    
30.                 ++ans;
    
31.                 --j;
    
32.             }
    
33.         }
    
34.         return ans;
    
35.     }
    
36. };

复制代码

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

解法2：通过对二分的理解，可以对这题用类似的四分搜索。注意左上角和右下角的子矩阵至少有一个可以跳过，而左下角和右上角总得搜。
代码2：

1. // Solution using quaternary search
   
2. typedef vector<vector<int> > V2DI;
   
3. class Solution {
   
4. public:
   
5.     /**
   
6.      * @param matrix: A list of lists of integers
   
7.      * @param target: An integer you want to search in matrix
   
8.      * @return: An integer indicate the total occurrence of target in the given matrix
   
9.      */
   
10.     int searchMatrix(V2DI &matrix, int target) {
    
11.         V2DI &a = matrix;
    
12.         int n = a.size();
    
13.         int m = n ? a[0].size() : 0;
    
14.         this->ans = 0;
    
15.         this->target = target;
    
16.         if (n == 0 || m == 0) {
    
17.             return 0;
    
18.         }
    
19.         quadSearch(a, 0, n - 1, 0, m - 1);
    
20.         return ans;
    
21.     }
    
22. private:
    
23.     int ans;
    
24.     int target;
    
25.    
    
26.     void quadSearch(V2DI &a, int tt, int bb, int ll, int rr) {
    
27.         if (tt == bb && ll == rr) {
    
28.             ans += a[tt][ll] == target;
    
29.             return;
    
30.         }
    
31.         int mmr = tt + (bb - tt + 1 >> 1);
    
32.         int mmc = ll + (rr - ll + 1 >> 1);
    
33.         if (mmr > tt && mmc > ll && target < a[mmr][mmc]) {
    
34.             // Search the top left submatrix
    
35.             quadSearch(a, tt, mmr - 1, ll, mmc - 1);
    
36.         }
    
37.         if (mmr > tt) {
    
38.             // Search the top right submatrix
    
39.             quadSearch(a, tt, mmr - 1, mmc, rr);
    
40.         }
    
41.         if (mmc > ll) {
    
42.             // Search the bottom left submatrix
    
43.             quadSearch(a, mmr, bb, ll, mmc - 1);
    
44.         }
    
45.         if (target >= a[mmr][mmc]) {
    
46.             // Search the bottom right submatrix
    
47.             quadSearch(a, mmr, bb, mmc, rr);
    
48.         }
    
49.     }
    
50. };

复制代码

复杂度2：时间应该是O(log(4 / 3)(N * M))，空间也是，因为用的是递归。

Recover Rotated Sorted Array
题意：给定一个旋转过的有序数组，请把它转回去，变回有序数组。
解法：先找出旋转了多少位，再转回去。鉴于旋转的复杂度是O(N)，所以我就偷懒没写O(log N)的找出旋转位置的代码。
代码：

1. #include <algorithm>
   
2. using namespace std;
   
3. 
   
4. class Solution {
   
5. public:
   
6.     void recoverRotatedSortedArray(vector<int> &nums) {
   
7.         int n = nums.size();
   
8.         if (n < 2) {
   
9.             return;
   
10.         }
    
11.         
    
12.         int i;
    
13.         for (i = 0; i < n - 1; ++i) {
    
14.             if (nums[i] > nums[i + 1]) {
    
15.                 break;
    
16.             }
    
17.         }
    
18.         if (i == n - 1) {
    
19.             return;
    
20.         }
    
21.         reverse(nums.begin(), nums.begin() + i + 1);
    
22.         reverse(nums.begin() + i + 1, nums.end());
    
23.         reverse(nums.begin(), nums.end());
    
24.     }
    
25. };

复制代码

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

Implement Queue by Two Stacks
题意：请用两个栈实现一个队列。
解法：可以这么理解，队列是正的，栈是反的，所以反反得正，非常科学。
代码：

1. #include <stack>
   
2. using namespace std;
   
3. 
   
4. class Queue {
   
5. public:
   
6.     Queue() {}
   
7. 
   
8.     void push(int element) {
   
9.         s1.push(element);
   
10.     }
    
11.    
    
12.     int pop() {
    
13.         if (s2.empty()) {
    
14.             pour();
    
15.         }
    
16.         int val = s2.top();
    
17.         s2.pop();
    
18.         return val;
    
19.     }
    
20. 
    
21.     int top() {
    
22.         if (s2.empty()) {
    
23.             pour();
    
24.         }
    
25.         return s2.top();
    
26.     }
    
27. private:
    
28.     stack<int> s1;
    
29.     stack<int> s2;
    
30.    
    
31.     void pour() {
    
32.         while (!s1.empty()) {
    
33.             s2.push(s1.top());
    
34.             s1.pop();
    
35.         }
    
36.     }
    
37. };

复制代码

复杂度：基本操作的均摊复杂度都是O(1)，单次操作可能会有O(N)的情况。（要理解均摊复杂度，请思考并查集的路径压缩算法。一次操作可能是O(N)，但连续N次操作依然只花O(N)时间，所以均摊下来就是O(1)。）

Maximum Subarray
题意：求一个数组中和最大的子数组（而不是子序列）。第一次感受算法的神奇，就是在这个题目。
解法：略
代码：

1. class Solution {
   
2. public:   
   
3.     /**
   
4.      * @param nums: A list of integers
   
5.      * @return: A integer indicate the sum of max subarray
   
6.      */
   
7.     int maxSubArray(vector<int> nums) {
   
8.         vector<int> &a = nums;
   
9.         int n = a.size();
   
10.         int msum, sum;
    
11.         int i;
    
12.         
    
13.         msum = a[0];
    
14.         for (i = 1; i < n; ++i) {
    
15.             msum = max(msum, a[i]);
    
16.         }
    
17.         if (msum < 0) {
    
18.             return msum;
    
19.         }
    
20.         
    
21.         sum = 0;
    
22.         for (i = 0; i < n; ++i) {
    
23.             sum += a[i];
    
24.             if (sum < 0) {
    
25.                 sum = 0;
    
26.             }
    
27.             msum = max(msum, sum);
    
28.         }
    
29.         return msum;
    
30.     }
    
31. };

复制代码

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

Maximum Subarray II
题意：从给定数组中选取两段子数组，使得它们的和最大。
解法：首先两段都不能为空，两段既可以相邻，也可以不相邻。我的做法是不考虑是否相邻，只求左右两段能拼出的最大值是多少即可，免得把代码搞复杂。
代码：

1. class Solution {
   
2. public:
   
3.     /**
   
4.      * @param nums: A list of integers
   
5.      * @return: An integer denotes the sum of max two non-overlapping subarrays
   
6.      */
   
7.     int maxTwoSubArrays(vector<int> nums) {
   
8.         vector<int> &a = nums;
   
9.         int n = a.size();
   
10.         vector<int> dl, dr;
    
11.         dl.resize(n);
    
12.         dr.resize(n);
    
13.         
    
14.         int sum;
    
15.         int i;
    
16.         
    
17.         dl[0] = sum = a[0];
    
18.         for (i = 1; i <= n - 1; ++i) {
    
19.             sum = max(sum, 0);
    
20.             sum += a[i];
    
21.             dl[i] = max(dl[i - 1], sum);
    
22.         }
    
23.         
    
24.         dr[n - 1] = sum = a[n - 1];
    
25.         for (i = n - 2; i >= 0; --i) {
    
26.             sum = max(sum, 0);
    
27.             sum += a[i];
    
28.             dr[i] = max(dr[i + 1], sum);
    
29.         }
    
30.         
    
31.         sum = dl[0] + dr[1];
    
32.         for (i = 1; i < n - 1; ++i) {
    
33.             sum = max(sum, dl[i] + dr[i + 1]);
    
34.         }
    
35.         return sum;
    
36.     }
    
37. };

复制代码

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

Maximum Subarray III
题意：hard难度。给定一个数组，从其中选取不重叠的K个子数组，使得和最大。
解法：这题我开始想了俩钟头都没思路，就是因为对前面两题的DP没有仔细想。这题的关键在于理解“局部最优”和“全局最优”。比如从前i个元素选出j个子数组，那么什么是全局和局部？区别就在于是否包含了第i个元素。不包含，那就是全局的，包含了就是局部的。局部和全局相互依赖于彼此，而且交替更新，才有了O(K * N)的DP。
我的代码直接用空间优化了，所以空间是O(N)的。
代码：

1. // O(k * n) DP with O(n) space, yes!
   
2. #include <algorithm>
   
3. #include <climits>
   
4. using namespace std;
   
5. 
   
6. class Solution {
   
7. public:
   
8.     /**
   
9.      * @param nums: A list of integers
   
10.      * @param k: An integer denote to find k non-overlapping subarrays
    
11.      * @return: An integer denote the sum of max k non-overlapping subarrays
    
12.      */
    
13.     int maxSubArray(vector<int> nums, int k) {
    
14.         vector<int> &a = nums;
    
15.         int n = a.size();
    
16.         if (k <= 0 || k > n) {
    
17.             return 0;
    
18.         }
    
19.         vector<vector<int> > dp(2, vector<int>(n, 0));
    
20.         vector<int> mx(n, 0);
    
21.         int i, j;
    
22.         int f, nf;
    
23.         
    
24.         mx[0] = dp[0][0] = a[0];
    
25.         for (i = 1; i < n; ++i) {
    
26.             dp[0][i] = max(dp[0][i - 1], 0) + a[i];
    
27.         }
    
28.         mx[0] = dp[0][0];
    
29.         for (i = 1; i < n; ++i) {
    
30.             mx[i] = max(mx[i - 1], dp[0][i]);
    
31.         }
    
32.         
    
33.         f = 1;
    
34.         nf = !f;
    
35.         for (i = 1; i < k; ++i) {
    
36.             dp[f][i] = dp[nf][i - 1] + a[i];
    
37.             for (j = i + 1; j < n; ++j) {
    
38.                 dp[f][j] = max(dp[f][j - 1], mx[j - 1]) + a[j];
    
39.             }
    
40.             mx[i] = dp[f][i];
    
41.             for (j = i + 1; j < n; ++j) {
    
42.                 mx[j] = max(mx[j - 1], dp[f][j]);
    
43.             }
    
44.             f = !f;
    
45.             nf = !f;
    
46.         }
    
47.         return mx[n - 1];
    
48.     }
    
49. };

复制代码

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

Minimum Subarray
题意：给定一个数组，求出和最小的子数组。
解法：就是把最大和子数组反过来。
代码：

1. #include <algorithm>
   
2. using namespace std;
   
3. 
   
4. class Solution {
   
5. public:
   
6.     /**
   
7.      * @param nums: a list of integers
   
8.      * @return: A integer denote the sum of minimum subarray
   
9.      */
   
10.     int minSubArray(vector<int> nums) {
    
11.         vector<int> &a = nums;
    
12.         int n = a.size();
    
13.         int msum, sum;
    
14.         int i;
    
15.         
    
16.         msum = a[0];
    
17.         for (i = 1; i < n; ++i) {
    
18.             msum = min(msum, a[i]);
    
19.         }
    
20.         if (msum > 0) {
    
21.             return msum;
    
22.         }
    
23.         
    
24.         sum = 0;
    
25.         for (i = 0; i < n; ++i) {
    
26.             sum += a[i];
    
27.             if (sum > 0) {
    
28.                 sum = 0;
    
29.             }
    
30.             msum = min(msum, sum);
    
31.         }
    
32.         return msum;
    
33.     }
    
34. };

复制代码

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

Maximum Subarray Difference
题意：给定一个数组，从中选取两个不重叠的子数组，使得它俩的差（绝对值）最大。
解法：这题有意思。我起初动了番脑子，看能不能想出O(1)空间的解，最后还是没搞出来。O(N)时间空间的解倒是有。根据最大和子数组的思路，我们可以从左往右、从右往左依次找出当前位置能得到的最大、最小子数组和，全部给记录下来。然后用最大减去最小，看哪个差值最大即可。
代码：

1. #include <algorithm>
   
2. #include <climits>
   
3. using namespace std;
   
4. 
   
5. class Solution {
   
6. public:
   
7.     /**
   
8.      * @param nums: A list of integers
   
9.      * @return: An integer indicate the value of maximum difference between two
   
10.      *          Subarrays
    
11.      */
    
12.     int maxDiffSubArrays(vector<int> nums) {
    
13.         vector<int> &a = nums;
    
14.         int n = nums.size();
    
15.         vector<int> minl, minr, maxl, maxr;
    
16.         int sum;
    
17.         int i;
    
18.         
    
19.         minl.resize(n);
    
20.         minr.resize(n);
    
21.         maxl.resize(n);
    
22.         maxr.resize(n);
    
23.         
    
24.         minl[0] = sum = a[0];
    
25.         for (i = 1; i <= n - 1; ++i) {
    
26.             sum = min(sum, 0);
    
27.             sum += a[i];
    
28.             minl[i] = min(minl[i - 1], sum);
    
29.         }
    
30.         
    
31.         maxl[0] = sum = a[0];
    
32.         for (i = 1; i <= n - 1; ++i) {
    
33.             sum = max(sum, 0);
    
34.             sum += a[i];
    
35.             maxl[i] = max(maxl[i - 1], sum);
    
36.         }
    
37.         
    
38.         minr[n - 1] = sum = a[n - 1];
    
39.         for (i = n - 2; i >= 0; --i) {
    
40.             sum = min(sum, 0);
    
41.             sum += a[i];
    
42.             minr[i] = min(minr[i + 1], sum);
    
43.         }
    
44.         
    
45.         maxr[n - 1] = sum = a[n - 1];
    
46.         for (i = n - 2; i >= 0; --i) {
    
47.             sum = max(sum, 0);
    
48.             sum += a[i];
    
49.             maxr[i] = max(maxr[i + 1], sum);
    
50.         }
    
51.         
    
52.         int ans = INT_MIN;
    
53.         for (i = 0; i < n - 1; ++i) {
    
54.             ans = max(ans, myabs(maxl[i] - minr[i + 1]));
    
55.             ans = max(ans, myabs(maxr[i + 1] - minl[i]));
    
56.         }
    
57.         return ans;
    
58.     }
    
59. private:
    
60.     int myabs(int x) {
    
61.         return x >= 0 ? x : -x;
    
62.     }
    
63. };

复制代码

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