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

Count and Say
题意：给定一个序列，把它”读出来“。比如1123读作211213，看出规律了吧？就是数个数。如果按照起始序列为”1“，每次都进行这种变换，求第N个序列。
解法：因为结果是固定的，所以算完就保存下来，免得下次又算。所谓动态打表嘛。
代码：

1. #include <unordered_map>
   
2. using namespace std;
   
3. 
   
4. class Solution {
   
5. public:
   
6.     /**
   
7.      * @param n the nth
   
8.      * @return the nth sequence
   
9.      */
   
10.     Solution() {
    
11.         ans[1] = "1";
    
12.         max_n = 1;
    
13.     }
    
14.    
    
15.     string countAndSay(int n) {
    
16.         if (ans.find(n) != ans.end()) {
    
17.             return ans[n];
    
18.         }
    
19.         int i;
    
20.         for (i = max_n; i < n; ++i) {
    
21.             ans[i + 1] = next(ans[i]);
    
22.         }
    
23.         max_n = n;
    
24.         return ans[n];
    
25.     }
    
26.    
    
27.     ~Solution() {
    
28.         ans.clear();
    
29.     }
    
30. private:
    
31.     unordered_map<int, string> ans;
    
32.     int max_n;
    
33.    
    
34.     string next(string s) {
    
35.         string s1;
    
36.         int n, i, j;
    
37.         
    
38.         n = s.length();
    
39.         i = 0;
    
40.         s1 = "";
    
41.         while (i < n) {
    
42.             j = i;
    
43.             while (j < n && s[i] == s[j]) {
    
44.                 ++j;
    
45.             }
    
46.             s1 += to_string(j - i);
    
47.             s1.push_back(s[i]);
    
48.             i = j;
    
49.         }
    
50.         return s1;
    
51.     }
    
52. };

复制代码

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

Kth Smallest Number in Sorted Matrix
题意：给定一个杨氏矩阵，求第K小的数。
解法：用小顶堆。把N行当成N个有序链表，这题就等效于Merge K Sorted List。上次在一个讨论贴里看到有位老兄说这题可以做到O(K)时间，好像是mgccl说的。
代码：

1. #include <queue>
   
2. using namespace std;
   
3. 
   
4. vector<vector<int> > *pa;
   
5. int n, m;
   
6. 
   
7. typedef struct Comp {
   
8.     bool operator () (const int &i1, const int &i2) const {
   
9.         return (*pa)[i1 / m][i1 % m] > (*pa)[i2 / m][i2 % m];
   
10.     }
    
11. } Comp;
    
12. priority_queue<int, vector<int>, Comp> pq;
    
13. 
    
14. class Solution {
    
15. public:
    
16.     /**
    
17.      * @param matrix: a matrix of integers
    
18.      * @param k: an integer
    
19.      * @return: the kth smallest number in the matrix
    
20.      */
    
21.     int kthSmallest(vector<vector<int> > &matrix, int k) {
    
22.         vector<vector<int> > &a = matrix;
    
23.         n = a.size();
    
24.         m = a[0].size();
    
25.         
    
26.         pa = &matrix;
    
27.         int i, j;
    
28.         for (i = 0; i < n; ++i) {
    
29.             pq.push(i * m);
    
30.         }
    
31.         
    
32.         int x, y, c;
    
33.         int ans;
    
34.         for (i = 0; i < k; ++i) {
    
35.             c = pq.top();
    
36.             pq.pop();
    
37.             x = c / m;
    
38.             y = c % m;
    
39.             ans = a[x][y];
    
40.             if (y < m - 1) {
    
41.                 ++y;
    
42.                 pq.push(x * m + y);
    
43.             }
    
44.         }
    
45.         
    
46.         while (!pq.empty()) {
    
47.             pq.pop();
    
48.         }
    
49.         return ans;
    
50.     }
    
51. };

复制代码

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

Maximum Gap
题意：hard难度。给定一个无序的数组，如果把它排序，请求出排好序以后相邻元素的最大差值。
解法1：排序。
代码1：

1. // The straight-forward solution
   
2. #include <algorithm>
   
3. using namespace std;
   
4. 
   
5. class Solution {
   
6. public:
   
7.     /**
   
8.      * @param nums: a vector of integers
   
9.      * @return: the maximum difference
   
10.      */
    
11.     int maximumGap(vector<int> nums) {
    
12.         sort(nums.begin(), nums.end());
    
13.         int ans = 0;
    
14.         int n = nums.size();
    
15.         int i;
    
16.         for (i = 1; i < n; ++i) {
    
17.             ans = max(ans, nums[i] - nums[i - 1]);
    
18.         }
    
19.         return ans;
    
20.     }
    
21. };

复制代码

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

解法2：这题确实挺难想的。排序的做法就不提了，说说不排序的。我独立想了四十分钟没有思路，然后上网搜，结果看到了”桶排序“后就大概明白了，然后搞出了下面这个解法。在这儿就不细讲了，要写清楚篇幅太大。桶排序这个点子我是真没想到。
代码2：

1. // O(n) solution, yet tricky and slow...
   
2. #include <climits>
   
3. #include <unordered_set>
   
4. using namespace std;
   
5. 
   
6. class Solution {
   
7. public:
   
8.     /**
   
9.      * @param nums: a vector of integers
   
10.      * @return: the maximum difference
    
11.      */
    
12.     int maximumGap(vector<int> nums) {
    
13.         vector<int> a;
    
14.         unordered_set<int> us;
    
15.         int n = nums.size();
    
16.         int i;
    
17.         for (i = 0; i < n; ++i) {
    
18.             us.insert(nums[i]);
    
19.         }
    
20.         for (auto it = us.begin(); it != us.end(); ++it) {
    
21.             a.push_back(*it);
    
22.         }
    
23.         
    
24.         n = a.size();
    
25.         if (n < 2) {
    
26.             return 0;
    
27.         }
    
28.         int minVal = INT_MAX;
    
29.         for (i = 0; i < n; ++i) {
    
30.             minVal = min(minVal, a[i]);
    
31.         }
    
32.         int maxVal = INT_MIN;
    
33.         for (i = 0; i < n; ++i) {
    
34.             a[i] -= minVal;
    
35.             maxVal = max(maxVal, a[i]);
    
36.         }
    
37.         int d = maxVal / (n - 1);
    
38.         vector<vector<int> > b(n);
    
39.         for (i = 0; i < n; ++i) {
    
40.             if (b[a[i] / d].empty()) {
    
41.                 b[a[i] / d].push_back(a[i]);
    
42.                 b[a[i] / d].push_back(a[i]);
    
43.             } else {
    
44.                 b[a[i] / d][0] = min(b[a[i] / d][0], a[i]);
    
45.                 b[a[i] / d][1] = max(b[a[i] / d][1], a[i]);
    
46.             }
    
47.         }
    
48.         i = 0;
    
49.         int j;
    
50.         int ans = 0;
    
51.         while (i < n) {
    
52.             j = i + 1;
    
53.             while (j < n && b[j].empty()) {
    
54.                 ++j;
    
55.             }
    
56.             if (j == n) {
    
57.                 break;
    
58.             }
    
59.             ans = max(ans, b[j][0] - b[i][1]);
    
60.             i = j;
    
61.         }
    
62.         return ans;
    
63.     }
    
64. };

复制代码

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

Simplify Path
题意：给定UNIX风格的路径，把其中存在"."、”..“和”///“之类的给简化掉，给出最简路径。
解法：正则处理字符串。用栈记录路径。
代码：

1. import re
   
2. 
   
3. class Solution:
   
4.     # @param {string} path the original path
   
5.     # @return {string} the simplified path
   
6.     def simplifyPath(self, path):
   
7.         path = re.split('/+', path.strip('/ \n\t'))
   
8.         st = []
   
9.         for token in path:
   
10.             if token == '.':
    
11.                 continue
    
12.             elif token == '..':
    
13.                 if len(st) > 0:
    
14.                     st.pop()
    
15.             else:
    
16.                 st.append(token)
    
17.         return '/' + '/'.join(st)

复制代码

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

Length of Last Word
题意：给定一个字符串，求最后一个单词的长度。
解法：注意处理空格即可。
代码：

1. class Solution {
   
2. public:
   
3.     /**
   
4.      * @param s A string
   
5.      * @return the length of last word
   
6.      */
   
7.     int lengthOfLastWord(string &s) {
   
8.         int i, j;
   
9.         
   
10.         j = s.length() - 1;
    
11.         while (j >= 0 && s[j] == ' ') {
    
12.             --j;
    
13.         }
    
14.         i = j;
    
15.         while (i >= 0 && s[i] != ' ') {
    
16.             --i;
    
17.         }
    
18.         return j - i;
    
19.     }
    
20. };

复制代码

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

Valid Parentheses
题意：括号序列匹配，可能包含大中小括号。
解法：用栈。
代码：

1. #include <map>
   
2. #include <stack>
   
3. using namespace std;
   
4. 
   
5. class Solution {
   
6. public:
   
7.     Solution() {
   
8.         m[')'] = '(';
   
9.         m[']'] = '[';
   
10.         m['}'] = '{';
    
11.     }
    
12.     /**
    
13.      * @param s A string
    
14.      * @return whether the string is a valid parentheses
    
15.      */
    
16.     bool isValidParentheses(string& s) {
    
17.         int n = s.length();
    
18.         stack<char> st;
    
19.         
    
20.         int i;
    
21.         for (i = 0; i < n; ++i) {
    
22.             switch (s[i]) {
    
23.             case '(':
    
24.             case '[':
    
25.             case '{':
    
26.                 st.push(s[i]);
    
27.                 break;
    
28.             case ')':
    
29.             case ']':
    
30.             case '}':
    
31.                 if (st.empty() || st.top() != m[s[i]]) {
    
32.                     return false;
    
33.                 }
    
34.                 st.pop();
    
35.                 break;
    
36.             }
    
37.         }
    
38.         return st.empty();
    
39.     }
    
40. private:
    
41.     map<char, char> m;
    
42. };

复制代码

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

Evaluate Reverse Polish Notation
题意：逆波兰表达式求值。
解法：无需考虑优先级问题，直接用栈处理即可。
代码：

1. import re
   
2. 
   
3. class Solution:
   
4.     op = {}
   
5.    
   
6.     def sign(self, x):
   
7.         return 0 if x == 0 else 1 if x > 0 else -1
   
8.         
   
9.     def __init__(self):
   
10.         self.op['+'] = lambda x, y: x + y
    
11.         self.op['-'] = lambda x, y: x - y
    
12.         self.op['*'] = lambda x, y: x * y
    
13.         self.op['/'] = lambda x, y: abs(x) / abs(y) * self.sign(x * y)
    
14.         
    
15.     # @param {string[]} tokens The Reverse Polish Notation
    
16.     # @return {int} the value
    
17.     def evalRPN(self, tokens):
    
18.         st = []
    
19.         for token in tokens:
    
20.             if re.match(r'[\+\-]?\d+', token):
    
21.                 st.append(int(token))
    
22.             else:
    
23.                 n2 = st.pop()
    
24.                 n1 = st.pop()
    
25.                 st.append(self.op[token](n1, n2))
    
26.         return st.pop()
    
27.         

复制代码

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

Continuous Subarray Sum
题意：最大子数组和。求出起点和终点。
解法：对O(N)的算法进行适当修改，就可以记录下起点和终点。
代码：

1. class Solution {
   
2. public:
   
3.     /**
   
4.      * @param A an integer array
   
5.      * @return  A list of integers includes the index of
   
6.      *          the first number and the index of the last number
   
7.      */
   
8.     vector<int> continuousSubarraySum(vector<int>& A) {
   
9.         int n = A.size();
   
10.         int ll;
    
11.         int sum;
    
12.         int msum;
    
13.         
    
14.         ll = 0;
    
15.         msum = A[0];
    
16.         int i;
    
17.         for (i = 1; i < n; ++i) {
    
18.             if (A[i] > msum) {
    
19.                 msum = A[i];
    
20.                 ll = i;
    
21.             }
    
22.         }
    
23.         vector<int> ans;
    
24.         if (msum <= 0) {
    
25.             ans.push_back(ll);
    
26.             ans.push_back(ll);
    
27.             return ans;
    
28.         }
    
29.         
    
30.         int mll, mrr;
    
31.         ll = 0;
    
32.         msum = sum = 0;
    
33.         for (i = 0; i < n; ++i) {
    
34.             sum += A[i];
    
35.             if (sum < 0) {
    
36.                 sum = 0;
    
37.                 ll = i + 1;
    
38.             }
    
39.             if (sum > msum) {
    
40.                 msum = sum;
    
41.                 mll = ll;
    
42.                 mrr = i;
    
43.             }
    
44.         }
    
45.         ans.push_back(mll);
    
46.         ans.push_back(mrr);
    
47.         return ans;
    
48.     }
    
49. };

复制代码

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

Continuous Subarray Sum II
题意：最大子数组和，求出起点和终点。不过这次允许”循环子数组“，也就是从尾到头的子数组。
解法1：分情况处理，一种是连续子数组，一种是两段子数组。代码写得很繁琐，思路不清晰。
代码1：

1. class Solution {
   
2. public:
   
3.     /**
   
4.      * @param A an integer array
   
5.      * @return  A list of integers includes the index of
   
6.      *          the first number and the index of the last number
   
7.      */
   
8.     vector<int> continuousSubarraySumII(vector<int>& A) {
   
9.         int msum1;
   
10.         vector<int> ans1;
    
11.         ans1 = continuousSubarraySum(A, msum1);
    
12.         if (ans1[0] == ans1[1]) {
    
13.             return ans1;
    
14.         }
    
15.         
    
16.         vector<int> s1;
    
17.         vector<int> i1;
    
18.         vector<int> s2;
    
19.         vector<int> i2;
    
20.         
    
21.         int n = A.size();
    
22.         int i;
    
23.         int sum;
    
24.         
    
25.         s1.resize(n);
    
26.         i1.resize(n);
    
27.         s2.resize(n);
    
28.         i2.resize(n);
    
29.         
    
30.         sum = A[0];
    
31.         s1[0] = A[0];
    
32.         i1[0] = 0;
    
33.         for (i = 1; i <= n - 1; ++i) {
    
34.             sum += A[i];
    
35.             if (sum > s1[i - 1]) {
    
36.                 s1[i] = sum;
    
37.                 i1[i] = i;
    
38.             } else {
    
39.                 s1[i] = s1[i - 1];
    
40.                 i1[i] = i1[i - 1];
    
41.             }
    
42.         }
    
43.         
    
44.         sum = A[n - 1];
    
45.         s2[n - 1] = A[n - 1];
    
46.         i2[n - 1] = n - 1;
    
47.         for (i = n - 2; i >= 0; --i) {
    
48.             sum += A[i];
    
49.             if (sum > s2[i + 1]) {
    
50.                 s2[i] = sum;
    
51.                 i2[i] = i;
    
52.             } else {
    
53.                 s2[i] = s2[i + 1];
    
54.                 i2[i] = i2[i + 1];
    
55.             }
    
56.         }
    
57.         
    
58.         int msum2 = 0;
    
59.         vector<int> ans2;
    
60.         ans2.resize(2);
    
61.         for (i = 0; i < n - 1; ++i) {
    
62.             if (s1[i] + s2[i + 1] > msum2) {
    
63.                 msum2 = s1[i] + s2[i + 1];
    
64.                 ans2[0] = i2[i + 1];
    
65.                 ans2[1] = i1[i];
    
66.             }
    
67.         }
    
68.         return msum1 > msum2 ? ans1 : ans2;
    
69.     }
    
70. private:
    
71.     vector<int> continuousSubarraySum(vector<int>& A, int &msum) {
    
72.         int n = A.size();
    
73.         int ll;
    
74.         int sum;
    
75.         
    
76.         ll = 0;
    
77.         msum = A[0];
    
78.         int i;
    
79.         for (i = 1; i < n; ++i) {
    
80.             if (A[i] > msum) {
    
81.                 msum = A[i];
    
82.                 ll = i;
    
83.             }
    
84.         }
    
85.         vector<int> ans;
    
86.         if (msum <= 0) {
    
87.             ans.push_back(ll);
    
88.             ans.push_back(ll);
    
89.             return ans;
    
90.         }
    
91.         
    
92.         int mll, mrr;
    
93.         ll = 0;
    
94.         msum = sum = 0;
    
95.         for (i = 0; i < n; ++i) {
    
96.             sum += A[i];
    
97.             if (sum < 0) {
    
98.                 sum = 0;
    
99.                 ll = i + 1;
    
100.             }
     
101.             if (sum > msum) {
     
102.                 msum = sum;
     
103.                 mll = ll;
     
104.                 mrr = i;
     
105.             }
     
106.         }
     
107.         ans.push_back(mll);
     
108.         ans.push_back(mrr);
     
109.         return ans;
     
110.     }
     
111. };

复制代码

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

解法2：对于两段子数组，其实可以转而关注中间的那段没被选取的子数组。于是，求出了中间那段的最小值，也就求出了两段的最大和，于是有了下面解法。代码相对来说好写多了。
代码2：

1. #include <algorithm>
   
2. using namespace std;
   
3. 
   
4. class Solution {
   
5. public:
   
6.     /**
   
7.      * @param A an integer array
   
8.      * @return  A list of integers includes the index of
   
9.      *          the first number and the index of the last number
   
10.      */
    
11.     vector<int> continuousSubarraySumII(vector<int> &A) {
    
12.         vector<int> pos1(2), pos2(2);
    
13.         int msum1, msum2;
    
14.         int n = A.size();
    
15.         int i;
    
16.         
    
17.         pos1 = continuousSubarraySum(A, msum1);
    
18.         if (msum1 <= 0) {
    
19.             return pos1;
    
20.         }
    
21.         
    
22.         int sum = 0;
    
23.         for (i = 0; i < n; ++i) {
    
24.             sum += A[i];
    
25.             A[i] = -A[i];
    
26.         }
    
27.         pos2 = continuousSubarraySum(A, msum2);
    
28.         msum2 = sum + msum2;
    
29.         
    
30.         pos2[0] = (pos2[0] + n - 1) % n;
    
31.         pos2[1] = (pos2[1] + 1) % n;
    
32.         swap(pos2[0], pos2[1]);
    
33.         
    
34.         return msum1 >= msum2 ? pos1 : pos2;
    
35.     }
    
36. private:
    
37.     vector<int> continuousSubarraySum(vector<int>& A, int &msum) {
    
38.         int n = A.size();
    
39.         int ll;
    
40.         int sum;
    
41.         
    
42.         ll = 0;
    
43.         msum = A[0];
    
44.         int i;
    
45.         for (i = 1; i < n; ++i) {
    
46.             if (A[i] > msum) {
    
47.                 msum = A[i];
    
48.                 ll = i;
    
49.             }
    
50.         }
    
51.         vector<int> ans;
    
52.         if (msum <= 0) {
    
53.             ans.push_back(ll);
    
54.             ans.push_back(ll);
    
55.             return ans;
    
56.         }
    
57.         
    
58.         int mll, mrr;
    
59.         ll = 0;
    
60.         msum = sum = 0;
    
61.         for (i = 0; i < n; ++i) {
    
62.             sum += A[i];
    
63.             if (sum < 0) {
    
64.                 sum = 0;
    
65.                 ll = i + 1;
    
66.             }
    
67.             if (sum > msum) {
    
68.                 msum = sum;
    
69.                 mll = ll;
    
70.                 mrr = i;
    
71.             }
    
72.         }
    
73.         ans.push_back(mll);
    
74.         ans.push_back(mrr);
    
75.         return ans;
    
76.     }
    
77. };

复制代码

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

Subarray Sum II
题意：hard难度。给定一个整数，和两个值start和end。求出和介于这两者之间的所有的子数组的个数。
解法1：暴力枚举。这题没有负数。
代码1：

1. // O(n ^ 2) solution
   
2. // There is no negative number?
   
3. #include <algorithm>
   
4. using namespace std;
   
5. 
   
6. class Solution {
   
7. public:
   
8.     /**
   
9.      * @param A an integer array
   
10.      * @param start an integer
    
11.      * @param end an integer
    
12.      * @return the number of possible answer
    
13.      */
    
14.     int subarraySumII(vector<int> &A, int start, int end) {
    
15.         if (start == end) {
    
16.             return 0;
    
17.             return 0;
    
18.         }
    
19.         
    
20.         vector<int> &a = A;
    
21.         int n = a.size();
    
22.         vector<int> s(n + 1, 0);
    
23.         int i;
    
24.         for (i = 0; i < n; ++i) {
    
25.             s[i + 1] = s[i] + a[i];
    
26.         }
    
27.         // sort(s.begin(), s.end());
    
28.         int ans = 0;
    
29.         int j;
    
30.         for (i = 0; i < n; ++i) {
    
31.             for (j = i + 1; j <= n; ++j) {
    
32.                 if (s[j] - s[i] >= start && s[j] - s[i] <= end) {
    
33.                     ++ans;
    
34.                 }
    
35.             }
    
36.         }
    
37.         return ans;
    
38.     }
    
39. };

复制代码

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

解法2：第一维枚举，第二维二分。
代码2：

1. // O(n * log(n)) solution
   
2. // So, there is no negative number.
   
3. #include <algorithm>
   
4. using namespace std;
   
5. 
   
6. class Solution {
   
7. public:
   
8.     /**
   
9.      * @param A an integer array
   
10.      * @param start an integer
    
11.      * @param end an integer
    
12.      * @return the number of possible answer
    
13.      */
    
14.     int subarraySumII(vector<int> &A, int start, int end) {
    
15.         if (start == end) {
    
16.             return 0;
    
17.             return 0;
    
18.         }
    
19.         
    
20.         vector<int> &a = A;
    
21.         int n = a.size();
    
22.         vector<int> s(n + 1, 0);
    
23.         int i;
    
24.         for (i = 0; i < n; ++i) {
    
25.             s[i + 1] = s[i] + a[i];
    
26.         }
    
27.         sort(s.begin(), s.end());
    
28.         int ans = 0;
    
29.         int j1, j2;
    
30.         for (i = 0; i < n; ++i) {
    
31.             j1 = lower_bound(s.begin() + i, s.end(), start + s[i]) - s.begin();
    
32.             j2 = upper_bound(s.begin() + i, s.end(), end + s[i]) - s.begin();
    
33.             ans += j2 - j1;
    
34.         }
    
35.         return ans;
    
36.     }
    
37. };

复制代码

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

解法3：可以做到线性时间。
代码3：

1. // O(n) solution
   
2. class Solution {
   
3. public:
   
4.     /**
   
5.      * @param A an integer array
   
6.      * @param start an integer
   
7.      * @param end an integer
   
8.      * @return the number of possible answer
   
9.      */
   
10.     int subarraySumII(vector<int> &A, int start, int end) {
    
11.         int n = A.size();
    
12.         if (n == 0) {
    
13.             return 0;
    
14.         }
    
15.         int i, j, k;
    
16.         j = k = 0;
    
17.         vector<int> S(n + 1, 0);
    
18.         for (i = 0; i < n; ++i) {
    
19.             S[i + 1] = S[i] + A[i];
    
20.         }
    
21.         
    
22.         int ans = 0;
    
23.         j = k = 1;
    
24.         for (i = 0; i < n; ++i) {
    
25.             while (j <= n && S[j] - S[i] < start) {
    
26.                 ++j;
    
27.             }
    
28.             while (k <= n && S[k] - S[i] <= end) {
    
29.                 ++k;
    
30.             }
    
31.             ans += k - j;
    
32.         }
    
33.         return ans;
    
34.     }
    
35. };

复制代码

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