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

Majority Number
题意：给定一个数组，找到出现次数超过数组长度一半的那个数。
解法：这题尽管已经人尽皆知，但我相信第一次遇见都会觉得神奇。请搜索Boyer-Moore，两个大神的杰作。（我还不会BM算法，等学会了我再去strStr那题补充一种解法。）
代码：

1. class Solution {
   
2. public:
   
3.     /**
   
4.      * @param nums: A list of integers
   
5.      * @return: The majority number
   
6.      */
   
7.     int majorityNumber(vector<int> nums) {
   
8.                 int c;
   
9.                 int val;
   
10.                 int n = nums.size();
    
11.                 int i;
    
12.                
    
13.                 val = nums[0];
    
14.                 c = 1;
    
15.                 for (i = 1; i < n; ++i) {
    
16.                         if (nums[i] == val) {
    
17.                                 ++c;
    
18.                         } else {
    
19.                                 --c;
    
20.                         }
    
21.                         if (c == 0) {
    
22.                                 val = nums[i];
    
23.                                 c = 1;
    
24.                         }
    
25.                 }
    
26.                
    
27.                 return val;
    
28.     }
    
29. };

复制代码

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

话说KMP算法中的K是算法大帝Knuth，M是不是Morris遍历的那个Morris？
查了下发现不是同一人。好奇当年这些算法的发明者是经过了多少学习和实践才能走到发明这步~~

Majority Number II
题意：给定一个数组，有个数出现的次数超过了数组的1 / 3，请找出。
解法：这就是把问题升级到两个众数了，其中至少有一个是有效的。
代码：

1. class Solution {
   
2. public:
   
3.     /**
   
4.      * @param nums: A list of integers
   
5.      * @return: The majority number occurs more than 1/3.
   
6.      */
   
7.     int majorityNumber(vector<int> nums) {
   
8.         vector<int> &a = nums;
   
9.         int n = a.size();
   
10.         int i;
    
11.         int a1, a2;
    
12.         int c1, c2;
    
13.         
    
14.         a1 = a2 = 0;
    
15.         c1 = c2 = 0;
    
16.         for (i = 0; i < n; ++i) {
    
17.             if (a1 == a[i]) {
    
18.                 ++c1;
    
19.             } else if (a2 == a[i]) {
    
20.                 ++c2;
    
21.             } else if (c1 == 0) {
    
22.                 a1 = a[i];
    
23.                 c1 = 1;
    
24.             } else if (c2 == 0) {
    
25.                 a2 = a[i];
    
26.                 c2 = 1;
    
27.             } else {
    
28.                 --c1;
    
29.                 --c2;
    
30.             }
    
31.         }
    
32.         c1 = c2 = 0;
    
33.         for (i = 0; i < n; ++i) {
    
34.             if (a1 == a[i]) {
    
35.                 ++c1;
    
36.             } else if (a2 == a[i]) {
    
37.                 ++c2;
    
38.             }
    
39.         }
    
40.         if (c1 > n / 3) {
    
41.             return a1;
    
42.         }
    
43.         if (c2 > n / 3) {
    
44.             return a2;
    
45.         }
    
46.     }
    
47. };

复制代码

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

Majority Number III
题意：给定一个数组，其中某数出现次数超过数组的1 / K，请找出。
解法：把问题一般化到了K - 1个众数，其中至少有一个是有效的。
代码：

1. class Solution {
   
2. public:
   
3.     /**
   
4.      * @param nums: A list of integers
   
5.      * @param k: As described
   
6.      * @return: The majority number
   
7.      */
   
8.     int majorityNumber(vector<int> nums, int k) {
   
9.         vector<int> &a = nums;
   
10.         int n = a.size();
    
11.         int i, j;
    
12.         vector<int> m, c;
    
13.         
    
14.         m.resize(k - 1, 0);
    
15.         c.resize(k - 1, 0);
    
16.         for (i = 0; i < n; ++i) {
    
17.             for (j = 0; j < k - 1; ++j) {
    
18.                 if (m[j] == a[i]) {
    
19.                     ++c[j];
    
20.                     break;
    
21.                 }
    
22.             }
    
23.             if (j < k - 1) {
    
24.                 continue;
    
25.             }
    
26.             
    
27.             for (j = 0; j < k - 1; ++j) {
    
28.                 if (c[j] == 0) {
    
29.                     m[j] = a[i];
    
30.                     c[j] = 1;
    
31.                     break;
    
32.                 }
    
33.             }
    
34.             if (j < k - 1) {
    
35.                 continue;
    
36.             }
    
37.             
    
38.             for (j = 0; j < k - 1; ++j) {
    
39.                 --c[j];
    
40.             }
    
41.         }
    
42.         
    
43.         for (i = 0; i < k - 1; ++i) {
    
44.             c[i] = 0;
    
45.         }
    
46.         for (i = 0; i < n; ++i) {
    
47.             for (j = 0; j < k - 1; ++j) {
    
48.                 if (a[i] == m[j]) {
    
49.                     ++c[j];
    
50.                     break;
    
51.                 }
    
52.             }
    
53.         }
    
54.         for (i = 0; i < k - 1; ++i) {
    
55.             if (c[i] > n / k) {
    
56.                 return m[i];
    
57.             }
    
58.         }
    
59.     }
    
60. };

复制代码

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

Product of Array Exclude Itself
题意：在不使用除法的情况下，算出对应每个位置的除了此位置外其他元素的乘积。
解法：如果允许使用除法，那就可以O(1)空间了。但因为不让用除法，所以需要记录左边的连乘积，然后从右边往左扫描即可。
代码：

1. typedef long long int LL;
   
2. 
   
3. class Solution {
   
4. public:
   
5.     /**
   
6.      * @param A: Given an integers array A
   
7.      * @return: A long long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]
   
8.      */
   
9.     vector<LL> productExcludeItself(vector<int> &nums) {
   
10.         vector<LL> sum;
    
11.         int n = nums.size();
    
12.         if (n == 0) {
    
13.             return sum;
    
14.         }
    
15.         sum.resize(n);
    
16.         
    
17.         int i;
    
18.         LL p = 1;
    
19.         for (i = 0; i <= n - 1; ++i) {
    
20.             sum[i] = p;
    
21.             p *= nums[i];
    
22.         }
    
23.         p = 1;
    
24.         for (i = n - 1; i >= 0; --i) {
    
25.             sum[i] *= p;
    
26.             p *= nums[i];
    
27.         }
    
28.         return sum;
    
29.     }
    
30. };

复制代码

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

Previous Permuation
题意：给定一个排列，求字典序中的上一个排列。
解法：就是next_permutation的逆过程。所以思路完全反过来即可。
代码：

1. #include <algorithm>
   
2. using namespace std;
   
3. 
   
4. class Solution {
   
5. public:
   
6.     /**
   
7.      * @param nums: An array of integers
   
8.      * @return: An array of integers that's previous permuation
   
9.      */
   
10.     vector<int> previousPermuation(vector<int> &nums) {
    
11.         vector<int> &a = nums;
    
12.         int n = a.size();
    
13.         
    
14.         if (n == 0) {
    
15.             return a;
    
16.         }
    
17.         int i, j;
    
18.         
    
19.         for (i = n - 2; i >= 0; --i) {
    
20.             if (a[i] > a[i + 1]) {
    
21.                 break;
    
22.             }
    
23.         }
    
24.         if (i < 0) {
    
25.             reverse(a.begin(), a.end());
    
26.             return a;
    
27.         }
    
28.         for (j = n - 1; j > i; --j) {
    
29.             if (a[j] < a[i]) {
    
30.                 break;
    
31.             }
    
32.         }
    
33.         swap(a[i], a[j]);
    
34.         reverse(a.begin() + i + 1, a.end());
    
35.         return a;
    
36.     }
    
37. };

复制代码

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

Next Permutation
题意：给定一个排列，求字典序中的下一个排列。
解法：从后往前找出第一个a{i} < a{i + 1}的位置。然后从后往前找到大于a{i}的第一个a{j}并交换。最后反转a{i + 1} ~ a{n - 1}。
代码：

1. class Solution {
   
2. public:
   
3.     /**
   
4.      * @param nums: An array of integers
   
5.      * @return: An array of integers that's next permuation
   
6.      */
   
7.     vector<int> nextPermutation(vector<int> &nums) {
   
8.         vector<int> &a = nums;
   
9.         int n = a.size();
   
10.         
    
11.         if (n == 0) {
    
12.             return a;
    
13.         }
    
14.         int i, j;
    
15.         
    
16.         for (i = n - 2; i >= 0; --i) {
    
17.             if (a[i] < a[i + 1]) {
    
18.                 break;
    
19.             }
    
20.         }
    
21.         if (i < 0) {
    
22.             reverse(a.begin(), a.end());
    
23.             return a;
    
24.         }
    
25.         for (j = n - 1; j > i; --j) {
    
26.             if (a[j] > a[i]) {
    
27.                 break;
    
28.             }
    
29.         }
    
30.         swap(a[i], a[j]);
    
31.         reverse(a.begin() + i + 1, a.end());
    
32.         return a;
    
33.     }
    
34. };

复制代码

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

Reverse Words in a String
题意：给定一个话，把句子里的单词顺序反过来，但单词中的字母不能反。
解法：python大法好
代码：

1. import re
   
2. 
   
3. class Solution:
   
4.     # @param s : A string
   
5.     # @return : A string
   
6.     def reverseWords(self, s):
   
7.         return (' '.join([val[::-1] for val in re.split('\s+', s.strip())]))[::-1]
   
8.         

复制代码

复杂度：时间O(N)，空间O(N)，因为中间运算需要临时空间。

String to Integer(atoi)
题意：hard难度。实现字符串转整数的atoi函数
解法：确定符号，诸位转换即可，要注意溢出。这题我偷懒用了long long，其实不用LL也可以检测溢出，考察是否发生了变号就可以做到。
这题被定为hard难度，其实是因为坑爹case很多，所以需要踩坑才行。
代码：

1. // You gotta ask before you code, all about the edge cases.
   
2. #include <climits>
   
3. using namespace std;
   
4. 
   
5. typedef long long int LL;
   
6. class Solution {
   
7. public:
   
8.     /**
   
9.      * @param str: A string
   
10.      * @return An integer
    
11.      */
    
12.     int atoi(string str) {
    
13.         int n = str.length();
    
14.         LL val = 0;
    
15.         int f = 1;
    
16.         bool sign = false;
    
17.         bool digit = false;
    
18.         int i = 0;
    
19.         i = 0;
    
20.         while (i < n) {
    
21.             if (str[i] == '-') {
    
22.                 if (digit || sign) {
    
23.                     break;
    
24.                 }
    
25.                 sign = true;
    
26.                 f = -1;
    
27.             } else if (str[i] == '+') {
    
28.                 if (digit || sign) {
    
29.                     break;
    
30.                 }
    
31.                 sign = true;
    
32.                 f = 1;
    
33.             } else if (isdigit(str[i])) {
    
34.                 digit = true;
    
35.                 val = val * 10 + (str[i] - '0');
    
36.                 if (f * val < INT_MIN) {
    
37.                     return INT_MIN;
    
38.                 }
    
39.                 if (f * val > INT_MAX) {
    
40.                     return INT_MAX;
    
41.                 }
    
42.             } else if (str[i] != ' ') {
    
43.                 break;
    
44.             }
    
45.             ++i;
    
46.         }
    
47.         return f * val;
    
48.     }
    
49. };

复制代码

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

Compare Strings
题意：给定字符串A和B，判断A是否包含了B中所有字符。无所谓是否按顺序或者连续。
解法：数数。
代码：

1. #include <cstring>
   
2. using namespace std;
   
3. 
   
4. class Solution {
   
5. public:
   
6.     /**
   
7.      * @param A: A string includes Upper Case letters
   
8.      * @param B: A string includes Upper Case letter
   
9.      * @return:  if string A contains all of the characters in B return true
   
10.      *           else return false
    
11.      */
    
12.     bool compareStrings(string A, string B) {
    
13.         int c[256];
    
14.         
    
15.         memset(c, 0, sizeof(c));
    
16.         int len = A.length();
    
17.         int i;
    
18.         for (i = 0; i < len; ++i) {
    
19.             ++c[A[i]];
    
20.         }
    
21.         len = B.length();
    
22.         for (i = 0; i < len; ++i) {
    
23.             --c[B[i]];
    
24.             if (c[B[i]] < 0) {
    
25.                 return false;
    
26.             }
    
27.         }
    
28.         return true;
    
29.     }
    
30. };

复制代码

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