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

Next Permutation II
题意：动手实现next_permutation。
解法：这题其实是告诉你数组中可能有重复元素。不管有没有重复元素，做法都是一样的。
代码：

1. #include <algorithm>
   
2. using namespace std;
   
3. 
   
4. class Solution {
   
5. public:
   
6.     /**
   
7.      * @param nums: a vector of integers
   
8.      * @return: return nothing (void), do not return anything, modify nums in-place instead
   
9.      */
   
10.     void nextPermutation(vector<int> &nums) {
    
11.         int n = nums.size();
    
12.         if (n == 0) {
    
13.             return;
    
14.         }
    
15.         int i;
    
16.         for (i = n - 2; i >= 0; --i) {
    
17.             if (nums[i] < nums[i + 1]) {
    
18.                 break;
    
19.             }
    
20.         }
    
21.         if (i < 0) {
    
22.             reverse(nums.begin(), nums.end());
    
23.             return;
    
24.         }
    
25.         int j = i + 1;
    
26.         while (j < n && nums[j] > nums[i]) {
    
27.             ++j;
    
28.         }
    
29.         --j;
    
30.         swap(nums[i], nums[j]);
    
31.         reverse(nums.begin() + i + 1, nums.end());
    
32.     }
    
33. };

复制代码

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

Longest Palindromic Substring
题意：求字符串的最长回文子串。
解法1：暴力解法。
代码1：

1. // The brute-force solution
   
2. class Solution {
   
3. public:
   
4.     /**
   
5.      * @param s input string
   
6.      * @return the longest palindromic substring
   
7.      */
   
8.     string longestPalindrome(string &s) {
   
9.         string ans = "";
   
10.         int n = s.length();
    
11.         if (n == 0) {
    
12.             return ans;
    
13.         }
    
14.         ans.push_back(s[0]);
    
15.         
    
16.         int maxlen = 1;
    
17.         int i, j;
    
18.         for (i = 0; i <= n - 1; ++i) {
    
19.             j = 1;
    
20.             while (i - j >= 0 && i + j <= n - 1 && s[i - j] == s[i + j]) {
    
21.                 ++j;
    
22.             }
    
23.             --j;
    
24.             if (2 * j + 1 > maxlen) {
    
25.                 maxlen = 2 * j + 1;
    
26.                 ans = s.substr(i - j, 2 * j + 1);
    
27.             }
    
28.         }
    
29.         for (i = 0; i <= n - 1; ++i) {
    
30.             j = 0;
    
31.             while (i - j >= 0 && i + 1 + j <= n - 1 && s[i - j] == s[i + 1 + j]) {
    
32.                 ++j;
    
33.             }
    
34.             --j;
    
35.             if (2 * j + 2 > maxlen) {
    
36.                 maxlen = 2 * j + 2;
    
37.                 ans = s.substr(i - j, 2 * j + 2);
    
38.             }
    
39.         }
    
40.         return ans;
    
41.     }
    
42. };

复制代码

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

解法2：Manacher算法，这是第四次写了，依然无法写出bug-free的代码，最后还是参考了自己的旧代码才搞定。感觉真是挺难的。
代码2：

1. // The Manacher solution
   
2. // Man... that was really tough.
   
3. class Solution {
   
4. public:
   
5.     /**
   
6.      * @param s input string
   
7.      * @return the longest palindromic substring
   
8.      */
   
9.     string longestPalindrome(string &s) {
   
10.         string ans = "";
    
11.         int n = s.length();
    
12.         if (n <= 1) {
    
13.             return s;
    
14.         }
    
15.         ans.push_back(s[0]);
    
16.         
    
17.         string ss;
    
18.         vector<int> r;
    
19.         alignStr(s, ss);
    
20.         r.resize(ss.length(), 1);
    
21.         
    
22.         int i, j;
    
23.         int mi, pos;
    
24.         
    
25.         mi = pos = r[0] = 0;
    
26.         for (i = 1; i < 2 * n; ++i) {
    
27.             r[i] = 1;
    
28.             if (pos > i) {
    
29.                 // Within the palindromic radius
    
30.                 // Possibly so
    
31.                 r[i] = r[2 * mi - i];
    
32.                 if (i + r[i] > pos) {
    
33.                     // Beyond the unknown
    
34.                     r[i] = pos - i;
    
35.                 }
    
36.             }
    
37.             while (ss[i - r[i]] == ss[i + r[i]]) {
    
38.                 ++r[i];
    
39.             }
    
40.             if (i + r[i] > pos) {
    
41.                 pos = i + r[i];
    
42.                 mi = i;
    
43.             }
    
44.         }
    
45.         
    
46.         int maxlen = 1;
    
47.         int len;
    
48.         string tmp;
    
49.         for (i = 1; i < 2 * n; ++i) {
    
50.             len = i % 2 ? (r[i] - 1) / 2 * 2 + 1 : r[i] / 2 * 2;
    
51.             if (len <= maxlen) {
    
52.                 continue;
    
53.             }
    
54.             maxlen = len;
    
55.             tmp = "";
    
56.             if (i % 2) {
    
57.                 for (j = i - (r[i] - 1) / 2 * 2; j <= i + (r[i] - 1) / 2 * 2; j += 2) {
    
58.                     tmp.push_back(ss[j]);
    
59.                 }
    
60.             } else {
    
61.                 for (j = i - r[i] / 2 * 2 + 1; j <= i + r[i] / 2 * 2 - 1; j += 2) {
    
62.                     tmp.push_back(ss[j]);
    
63.                 }
    
64.             }
    
65.             ans = tmp;
    
66.         }
    
67.         return ans;
    
68.     }
    
69. private:
    
70.     const char UNDEF1 = '\254';
    
71.     const char UNDEF2 = '\253';
    
72.    
    
73.     void alignStr(string &s, string &ss) {
    
74.         ss.clear();
    
75.         ss.push_back(UNDEF2);
    
76.         int n = s.length();
    
77.         int i;
    
78.         
    
79.         for (i = 0; i < n; ++i) {
    
80.             ss.push_back(s[i]);
    
81.             ss.push_back(UNDEF1);
    
82.         }
    
83.         ss[2 * n] = 0;
    
84.     }
    
85. };

复制代码

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

Partition Array by Odd and Even
题意：把数组中的奇数放左边，偶数放右边。
解法：来自快排。
代码：

1. #include <algorithm>
   
2. using namespace std;
   
3. 
   
4. class Solution {
   
5. public:
   
6.     /**
   
7.      * @param nums: a vector of integers
   
8.      * @return: nothing
   
9.      */
   
10.     void partitionArray(vector<int> &nums) {
    
11.         // Think about quick sort.
    
12.         vector<int> &a = nums;
    
13.         int n = a.size();
    
14.         if (n <= 1) {
    
15.             return;
    
16.         }
    
17.         int i = 0;
    
18.         int j = n - 1;
    
19.         while (true) {
    
20.             while (i <= j && a[i] % 2 == 1) {
    
21.                 ++i;
    
22.             }
    
23.             while (i <= j && a[j] % 2 == 0) {
    
24.                 --j;
    
25.             }
    
26.             if (i > j) {
    
27.                 break;
    
28.             }
    
29.             swap(a[i], a[j]);
    
30.         }
    
31.     }
    
32. };

复制代码

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

Longest Increasing Continuous subsequence II
题意：hard难度。给定一个二维数组，允许你从其中一点出发，上下左右走，要求每一步都走向数字更大的点，求路径最长能有多长。
解法：这题的样例给得不好，没有说清楚这个最长连续递增序列到底是什么意思。我一开始还以为是像{1,2,3}这样在数值上连续的数列，其实这题指的是位置上的连续。
解决这题可以用DFS+DP，也就是记忆化搜索。
代码：

1. class Solution {
   
2. public:
   
3.     Solution() {
   
4.         offset.resize(4, vector<int>(2));
   
5.         offset[0][0] = -1;
   
6.         offset[0][1] = 0;
   
7.         offset[1][0] = +1;
   
8.         offset[1][1] = 0;
   
9.         offset[2][0] = 0;
   
10.         offset[2][1] = -1;
    
11.         offset[3][0] = 0;
    
12.         offset[3][1] = +1;
    
13.     }
    
14.     /**
    
15.      * @param A an integer matrix
    
16.      * @return  an integer
    
17.      */
    
18.     int longestIncreasingContinuousSubsequenceII(vector<vector<int> > &A) {
    
19.         d.clear();
    
20.         vector<vector<int> > &a = A;
    
21.         n = a.size();
    
22.         m = n ? a[0].size() : 0;
    
23.         int i, j;
    
24.         if (n == 0 || m == 0) {
    
25.             return 0;
    
26.         }
    
27.         d.resize(n, vector<int>(m, 0));
    
28.         
    
29.         int ans = 0;
    
30.         for (i = 0; i < n; ++i) {
    
31.             for (j = 0; j < m; ++j) {
    
32.                 ans = max(ans, DFS(i, j, a));
    
33.             }
    
34.         }
    
35.         return ans;
    
36.     }
    
37. private:
    
38.     vector<vector<int> > offset;
    
39.     vector<vector<int> > d;
    
40.     int n, m;
    
41.    
    
42.     bool inbound(int x, int y) {
    
43.         return x >= 0 && x <= n - 1 && y >= 0 && y <= m - 1;
    
44.     }
    
45.    
    
46.     int DFS(int x, int y, vector<vector<int> > &a) {
    
47.         if (d[x][y] != 0) {
    
48.             // Use memorization to avoid redundant recursion
    
49.             return d[x][y];
    
50.         }
    
51.         d[x][y] = 1;
    
52.         
    
53.         int i;
    
54.         int x1, y1;
    
55.         for (i = 0; i < 4; ++i) {
    
56.             x1 = x + offset[i][0];
    
57.             y1 = y + offset[i][1];
    
58.             if (!inbound(x1, y1) || a[x1][y1] >= a[x][y]) {
    
59.                 continue;
    
60.             }
    
61.             d[x][y] = max(d[x][y], DFS(x1, y1, a) + 1);
    
62.         }
    
63.         return d[x][y];
    
64.     }
    
65. };

复制代码

复杂度：时间O(N * M)，空间一样。

Longest Increasing Continuous subsequence
题意：给定一个数组，求严格单调的子数组的最大长度。
解法：单调递增，单调递减都可以。
代码：

1. #include <algorithm>
   
2. using namespace std;
   
3. 
   
4. static bool lt(const int &x, const int &y) {
   
5.     return x < y;
   
6. }
   
7. 
   
8. static bool gt(const int &x, const int &y) {
   
9.     return x > y;
   
10. }
    
11. 
    
12. class Solution {
    
13. public:
    
14.     /**
    
15.      * @param A an array of Integer
    
16.      * @return  an integer
    
17.      */
    
18.     int longestIncreasingContinuousSubsequence(vector<int>& A) {
    
19.         return max(solve(A, lt), solve(A, gt));
    
20.     }
    
21. private:
    
22.     int solve(vector<int> &a, bool (*comp)(const int &, const int &)) {
    
23.         int n = a.size();
    
24.         int ans = 0;
    
25.         int i, j;
    
26.         i = 0;
    
27.         while (i < n) {
    
28.             j = i + 1;
    
29.             while (j < n && comp(a[j - 1], a[j])) {
    
30.                 ++j;
    
31.             }
    
32.             ans = max(ans, j - i);
    
33.             i = j;
    
34.         }
    
35.         return ans;
    
36.     }
    
37. };

复制代码

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

Minimum Size Subarray Sum
题意：给定一个数组A，和一个值S。求出加起来不小于S的子数组的最短长度。
解法：两个指针，逐步向前移，并随时更新答案。可以在线性时间内求出结果。
代码：

1. #include <algorithm>
   
2. using namespace std;
   
3. 
   
4. class Solution {
   
5. public:
   
6.     /**
   
7.      * @param nums: a vector of integers
   
8.      * @param s: an integer
   
9.      * @return: an integer representing the minimum size of subarray
   
10.      */
    
11.     int minimumSize(vector<int> &nums, int s) {
    
12.         int n = nums.size();
    
13.         if (n == 0) {
    
14.             return -1;
    
15.         }
    
16.         
    
17.         int ll, rr;
    
18.         int sum;
    
19.         int ans = n + 1;
    
20.         
    
21.         sum = 0;
    
22.         ll = 0;
    
23.         rr = 0;
    
24.         while (rr < n) {
    
25.             sum += nums[rr];
    
26.             if (sum >= s) {
    
27.                 ans = min(ans, rr - ll + 1);
    
28.                 while (ll <= rr && sum - nums[ll] >= s) {
    
29.                     sum -= nums[ll];
    
30.                     ++ll;
    
31.                     ans = min(ans, rr - ll + 1);
    
32.                 }
    
33.             }
    
34.             ++rr;
    
35.         }
    
36.         return ans <= n ? ans : -1;
    
37.     }
    
38. };

复制代码

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

Valid Palindrome
题意：检查一个字符串是否是回文串，不过要忽略大小写。
解法：实现即可。
代码：

1. #include <cctype>
   
2. using namespace std;
   
3. 
   
4. class Solution {
   
5. public:
   
6.     /**
   
7.      * @param s A string
   
8.      * @return Whether the string is a valid palindrome
   
9.      */
   
10.     bool isPalindrome(string& s) {
    
11.         int i = 0;
    
12.         int j = s.length() - 1;
    
13.         
    
14.         while (i < j) {
    
15.             if (!isalnum(s[i])) {
    
16.                 ++i;
    
17.             } else if (!isalnum(s[j])) {
    
18.                 --j;
    
19.             } else if (s[i] == s[j]) {
    
20.                 ++i;
    
21.                 --j;
    
22.             } else if (isalpha(s[i]) && isalpha(s[j]) &&
    
23.                        tolower(s[i]) == tolower(s[j])) {
    
24.                 ++i;
    
25.                 --j;
    
26.             } else {
    
27.                 return false;
    
28.             }
    
29.         }
    
30.         return true;
    
31.     }
    
32. };

复制代码

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

Valid Number
题意：hard难度。判断一个给定字符串能否表示一个有效的数，不论整数还是浮点数都可以。
解法：用字符处理太麻烦，所以改用正则了。当然，用正则肯定是绕过了这题的难点。
代码：

1. import re
   
2. 
   
3. class Solution:
   
4.     # @param {string} s the string that represents a number
   
5.     # @return {boolean} whether the string is a valid number
   
6.     def isNumber(self, s):
   
7.         p = r'[+\-]?((\d+(\.\d*)?)|(\.\d+))([eE][+\-]?\d+)?'
   
8.         return re.match(p, s.strip()) != None
   
9.         

复制代码

复杂度：因为python的正则内部是由NFA驱动，所以理论复杂度是对数级，实际效率当然要根据模式的复杂程度和文本特征来看。空间不敢下结论。正则这东西一本书都讲不完，我还是有更深入了解以后再来分析时空复杂度吧。

Integer to Roman
题意：整数转换为罗马数字。
解法：按规则实现。
代码：

1. class Solution:
   
2.     # @param {int} n The integer
   
3.     # @return {string} Roman representation
   
4.     def intToRoman(self, n):
   
5.         # Write your code here
   
6.         m = {}
   
7.         m[1] = 'I'
   
8.         m[5] = 'V'
   
9.         m[10] = 'X'
   
10.         m[50] = 'L'
    
11.         m[100] = 'C'
    
12.         m[500] = 'D'
    
13.         m[1000] = 'M'
    
14.         b = 1
    
15.         while b < 1000:
    
16.             for i in xrange(2, 4):
    
17.                 m[i * b] = m[(i - 1) * b] + m[b]
    
18.             m[4 * b] = m[b] + m[5 * b]
    
19.             for i in xrange(6, 9):
    
20.                 m[i * b] = m[(i - 1) * b] + m[b]
    
21.             m[9 * b] = m[b] + m[10 * b]
    
22.             b *= 10
    
23.         for i in xrange(2, 3):
    
24.             m[i * b] = m[(i - 1) * b] + m[b]
    
25.         ans = ''
    
26.         while b > 0:
    
27.             if n / b % 10 == 0:
    
28.                 b /= 10
    
29.                 continue
    
30.             ans += m[n / b % 10 * b]
    
31.             b /= 10
    
32.         return ans

复制代码

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

Roman to Integer
题意：给定一个罗马数字，转换为整数。
解法：按规则实现。
代码：

1. #include <unordered_map>
   
2. using namespace std;
   
3. 
   
4. unordered_map<char, int> val;
   
5. unordered_map<char, char> nextchar;
   
6. 
   
7. class Solution {
   
8. public:
   
9.     Solution() {
   
10.         val['I'] = 1;
    
11.         val['V'] = 5;
    
12.         val['X'] = 10;
    
13.         val['L'] = 50;
    
14.         val['C'] = 100;
    
15.         val['D'] = 500;
    
16.         val['M'] = 1000;
    
17.         nextchar['V'] = 'I';
    
18.         nextchar['X'] = 'I';
    
19.         nextchar['L'] = 'X';
    
20.         nextchar['C'] = 'X';
    
21.         nextchar['D'] = 'C';
    
22.         nextchar['M'] = 'C';
    
23.     }
    
24.     /**
    
25.      * @param s Roman representation
    
26.      * @return an integer
    
27.      */
    
28.     int romanToInt(string& s) {
    
29.         int n = s.length();
    
30.         int i;
    
31.         int ans;
    
32.         
    
33.         ans = 0;
    
34.         i = 0;
    
35.         while (i < n) {
    
36.             if (i < n - 1 && nextchar[s[i + 1]] == s[i]) {
    
37.                 ans += val[s[i + 1]] - val[s[i]];
    
38.                 i += 2;
    
39.             } else {
    
40.                 ans += val[s[i]];
    
41.                 i += 1;
    
42.             }
    
43.         }
    
44.         return ans;
    
45.     }
    
46. };

复制代码

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