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

Trailing Zeros
题意：给定N，求N的阶乘末尾有多少个0
解法：0的个数等于N！可以分解出多少个10，也就是多少个5，所以不断除以5并求和即可。
代码：

1. class Solution {
   
2. public:
   
3.     // param n : description of n
   
4.     // return: description of return
   
5.     long long trailingZeros(long long n) {
   
6.         long long int sum = 0;
   
7.         while (n > 0) {
   
8.             sum += n / 5;
   
9.             n /= 5;
   
10.         }
    
11.         return sum;
    
12.     }
    
13. };

复制代码

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

Digit Counts
题意：给定一个数字k，以及一个整数n，求0~n的所有整数中，数字k出现了多少次。k可以是0~9。
解法：典型的数位动归题目，这种题直接从0数到N肯定会被面试官鄙视的。这题头疼的是0的处理，我的代码中1~9可以用同一套解法，0单独处理。数组sum{i}表示i位数中总共出现了多少个1~9，sum0{i}表示数组中总共出现了多少个0。至于它们为什么不能归为同类，可以这么理解。最高位数字可以是1~9，而不能是0。所以0要单独处理，思路也不一样。这题我的实现很复杂，自己都觉得晕，请问有效率不差，而且更简洁易懂的思路吗？
代码：

1. typedef long long int LL;
   
2. 
   
3. class Solution {
   
4. public:
   
5.     Solution() {
   
6.         int i, j;
   
7.         LL b10;
   
8.         
   
9.         sum[0] = 0;
   
10.         sum[1] = 1;
    
11.         b10 = 1;
    
12.         for (i = 2; i < M; ++i) {
    
13.             b10 *= 10;
    
14.             sum[i] = 10 * sum[i - 1] + b10;
    
15.         }
    
16.         
    
17.         LL ss;
    
18. 
    
19.         sum0[0] = 0;
    
20.         sum0[1] = 0;
    
21.         b10 = 1;
    
22.         for (i = 2; i < M; ++i) {
    
23.             b10 *= 10;
    
24.             ss = 0;
    
25.             for (j = 1; j < i; ++j) {
    
26.                 ss += sum0[j];
    
27.             }
    
28.             sum0[i] = 9 * (leadingZero(b10 - 1, i - 1) + ss);
    
29.         }
    
30.     }
    
31.     /*
    
32.      * param k : As description.
    
33.      * param n : As description.
    
34.      * return: How many k's between 0 and n.
    
35.      */
    
36.     int digitCounts(int k, int n) {
    
37.         if (k == 0) {
    
38.             return countZero(n) + 1;
    
39.         }
    
40.         return countDigit(n, k);
    
41.     }
    
42. private:
    
43.     static const int M = 19;
    
44.     LL sum[M];
    
45.     LL sum0[M];
    
46.    
    
47.     LL countDigit(LL x, int d) {
    
48.         LL b10;
    
49.         int idx;
    
50. 
    
51.         if (x < d) {
    
52.             return 0;
    
53.         } else if (x < 10) {
    
54.             return 1;
    
55.         }
    
56. 
    
57.         b10 = 1;
    
58.         idx = 0;
    
59.         while (b10 * 10 <= x) {
    
60.             b10 *= 10;
    
61.             ++idx;
    
62.         }
    
63.         if (x / b10 > d) {
    
64.             return (x / b10) * sum[idx] + b10 + countDigit(x % b10, d);
    
65.         } else if (x / b10 == d) {
    
66.             return (x / b10) * sum[idx] + (x % b10 + 1) + countDigit(x % b10, d);
    
67.         } else {
    
68.             return (x / b10) * sum[idx] + countDigit(x % b10, d);
    
69.         }
    
70.     }
    
71.    
    
72.     LL leadingZero(LL x, int idx) {
    
73.         LL b10 = 1;
    
74.         LL sum = idx;
    
75.         int bi = 1;
    
76.         while (b10 * 10 <= x) {
    
77.             sum += 9 * b10 * (idx - bi);
    
78.             b10 *= 10;
    
79.             ++bi;
    
80.         }
    
81.         sum += (x - b10 + 1) * (idx - bi);
    
82.         return sum;
    
83.     }
    
84.    
    
85.     LL countZero(LL x) {
    
86.         LL b10;
    
87.         int idx;
    
88.         
    
89.         if (x < 10) {
    
90.             return 0;
    
91.         }
    
92. 
    
93.         b10 = 1;
    
94.         idx = 0;
    
95.         while (b10 * 10 <= x) {
    
96.             b10 *= 10;
    
97.             ++idx;
    
98.         }
    
99. 
    
100.         LL ans = 0;
     
101.         LL ss = 0;
     
102.         int i;
     
103. 
     
104.         for (i = 1; i <= idx; ++i) {
     
105.             ans += sum0[i];
     
106.             ss += sum0[i];
     
107.         }
     
108.         ans += (x / b10 - 1) * (ss + leadingZero(b10 - 1, idx));
     
109.         ans += leadingZero(x % b10, idx) + countZero(x % b10);
     
110. 
     
111.         return ans;
     
112.     }
     
113. };

复制代码

复杂度：时间上对DP数组的预处理O(log N)，函数调用过程也是O(log N)。空间也是O(log N)。

Ugly Number
题意：这题和Humble Number一样，数论里名字有好几个，下面这个应该是一般化的定义。就是求所有质因数只有3， 5， 7的数里，从小到大排第k的那个。
https://en.wikipedia.org/wiki/Smooth_number
解法：3个指针逐步向前移，每次选取最小值。
代码：

1. #include <algorithm>
   
2. using namespace std;
   
3. 
   
4. typedef long long int LL;
   
5. 
   
6. class Solution {
   
7. public:
   
8.     /*
   
9.      * @param k: The number k.
   
10.      * @return: The kth prime number as description.
    
11.      */
    
12.     LL kthPrimeNumber(int k) {
    
13.         vector<LL> v;
    
14.         int p1, p2, p3;
    
15.         LL a1, a2, a3;
    
16.         LL val;
    
17.         
    
18.         p1 = p2 = p3 = 0;
    
19.         v.push_back(1);
    
20.         while (v.size() <= k) {
    
21.             a1 = v[p1] * 3;
    
22.             a2 = v[p2] * 5;
    
23.             a3 = v[p3] * 7;
    
24.             val = min(a1, min(a2, a3));
    
25.             if (val == a1) {
    
26.                 ++p1;
    
27.             }
    
28.             if (val == a2) {
    
29.                 ++p2;
    
30.             }
    
31.             if (val == a3) {
    
32.                 ++p3;
    
33.             }
    
34.             v.push_back(val);
    
35.         }
    
36.         return v[k];
    
37.     }
    
38. };

复制代码

复杂度：时间空间都是O(K)

Kth Largest Element
题意：求一个数组中，第K大的数。允许交换数组中的元素。
解法1：根据快排改造得到快速选择算法。注意题目要求的是第K大，不是第K小。
代码1：

1. #include <algorithm>
   
2. using namespace std;
   
3. 
   
4. class Solution {
   
5. public:
   
6.     /*
   
7.      * param k : description of k
   
8.      * param nums : description of array and index 0 ~ n-1
   
9.      * return: description of return
   
10.      */
    
11.     int kthLargestElement(int k, vector<int> nums) {
    
12.         int n = nums.size();
    
13.         return quickSelect(nums, 0, n - 1, n - k);
    
14.     }
    
15. private:
    
16.     int quickSelect(vector<int> &a, int ll, int rr, int k) {
    
17.         if (ll == rr) {
    
18.             return a[k];
    
19.         }
    
20.         int i = ll + 1;
    
21.         int j = rr;
    
22.         int piv = a[ll];
    
23.         while (true) {
    
24.             while (i <= j && a[i] < piv) {
    
25.                 ++i;
    
26.             }
    
27.             while (i <= j && a[j] > piv) {
    
28.                 --j;
    
29.             }
    
30.             if (i > j) {
    
31.                 break;
    
32.             }
    
33.             swap(a[i++], a[j--]);
    
34.         }
    
35.         swap(a[ll], a[j]);
    
36.         if (k < j) {
    
37.             return quickSelect(a, ll, j - 1, k);
    
38.         } else if (k > j) {
    
39.             return quickSelect(a, j + 1, rr, k);
    
40.         } else {
    
41.             return a[k];
    
42.         }
    
43.     }
    
44. };

复制代码

复杂度1：时间可以做到O(N)，但由于是递归，理论上空间复杂度介于O(log N)和O(N)之间。不知道O(1)空间的算法应该怎么做？

解法2：感谢stellari的提醒，递归经过简单的改造就变成了迭代。我居然没看出自己写的是尾递归(-_-)||
代码2：

1. // The iterative version
   
2. #include <algorithm>
   
3. using namespace std;
   
4. 
   
5. class Solution {
   
6. public:
   
7.     /*
   
8.      * param k : description of k
   
9.      * param nums : description of array and index 0 ~ n-1
   
10.      * return: description of return
    
11.      */
    
12.     int kthLargestElement(int k, vector<int> nums) {
    
13.         int n = nums.size();
    
14.         return quickSelect(nums, 0, n - 1, n - k);
    
15.     }
    
16. private:
    
17.     int quickSelect(vector<int> &a, int ll, int rr, int k) {
    
18.         int i;
    
19.         int j;
    
20.         int piv;
    
21.         
    
22.         while (true) {
    
23.             if (ll == rr) {
    
24.                 return a[k];
    
25.             }
    
26.             i = ll + 1;
    
27.             j = rr;
    
28.             piv = a[ll];
    
29.             while (true) {
    
30.                 while (i <= j && a[i] < piv) {
    
31.                     ++i;
    
32.                 }
    
33.                 while (i <= j && a[j] > piv) {
    
34.                     --j;
    
35.                 }
    
36.                 if (i > j) {
    
37.                     break;
    
38.                 }
    
39.                 swap(a[i++], a[j--]);
    
40.             }
    
41.             swap(a[ll], a[j]);
    
42.             if (k < j) {
    
43.                 rr = j - 1;
    
44.             } else if (k > j) {
    
45.                 ll = j + 1;
    
46.             } else {
    
47.                 return a[k];
    
48.             }
    
49.         }
    
50.     }
    
51. };

复制代码

复杂度2：由于是迭代，所以空间变成O(1)了，时间是O(N)。

Merge Sorted Array II
题意：归并两个有序数组，存在新数组里。
解法：略
代码：

1. class Solution {
   
2. public:
   
3.     /**
   
4.      * @param A and B: sorted integer array A and B.
   
5.      * @return: A new sorted integer array
   
6.      */
   
7.     vector<int> mergeSortedArray(vector<int> &A, vector<int> &B) {
   
8.         vector<int> C;
   
9.         int i, j;
   
10.         int na, nb;
    
11.         
    
12.         na = A.size();
    
13.         nb = B.size();
    
14.         i = j = 0;
    
15.         while (i < na && j < nb) {
    
16.             if (A[i] < B[j]) {
    
17.                 C.push_back(A[i++]);
    
18.             } else {
    
19.                 C.push_back(B[j++]);
    
20.             }
    
21.         }
    
22.         while (i < na) {
    
23.             C.push_back(A[i++]);
    
24.         }
    
25.         while (j < nb) {
    
26.             C.push_back(B[j++]);
    
27.         }
    
28.         return C;
    
29.     }
    
30. };

复制代码

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

Binary Tree Serialization
题意：序列化和反序列化一棵二叉树。
解法：这题其实考察的是对二叉树遍历的理解，不论前序、后序、中序、层次遍历都可以。我倾向于选前序或者层次遍历。序列化的表示方法则可以自有选择。
代码：

1. #include <vector>
   
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.     string serialize(TreeNode *root) {
    
18.         serializePreorder(root);
    
19.         
    
20.         string ans = "";
    
21.         int n = v.size();
    
22.         int i;
    
23.         for (i = 0; i < n; ++i) {
    
24.             ans += v[i];
    
25.             ans.push_back(' ');
    
26.         }
    
27.         ans.pop_back();
    
28.         v.clear();
    
29.         
    
30.         return ans;
    
31.     }
    
32. 
    
33.     TreeNode *deserialize(string data) {
    
34.         int n = data.length();
    
35.         int i, j;
    
36.         string s;
    
37.         
    
38.         while (i < n) {
    
39.             s = "";
    
40.             j = i;
    
41.             while (j < n && data[j] != ' ') {
    
42.                 s.push_back(data[j++]);
    
43.             }
    
44.             v.push_back(s);
    
45.             ++j;
    
46.             i = j;
    
47.         }
    
48.         
    
49.         idx = 0;
    
50.         TreeNode *root;
    
51.         deserializePreorder(root);
    
52.         v.clear();
    
53.         
    
54.         return root;
    
55.     }
    
56. private:
    
57.     vector<string> v;
    
58.     int idx;
    
59.    
    
60.     void serializePreorder(TreeNode *root) {
    
61.         if (root == NULL) {
    
62.             v.push_back("#");
    
63.             return;
    
64.         }
    
65.         v.push_back(to_string(root->val));
    
66.         serializePreorder(root->left);
    
67.         serializePreorder(root->right);
    
68.     }
    
69.    
    
70.     void deserializePreorder(TreeNode *&root) {
    
71.         if (v[idx] == "#") {
    
72.             root = NULL;
    
73.             ++idx;
    
74.         } else {
    
75.             root = new TreeNode(atoi(v[idx].data()));
    
76.             ++idx;
    
77.             deserializePreorder(root->left);
    
78.             deserializePreorder(root->right);
    
79.         }
    
80.     }
    
81. };

复制代码

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

Rotate String
题意：给定一个字符串，把它循环右移K位。
解法：使用神奇的reverse函数，注意处理边界情况。
代码：

1. #include <algorithm>
   
2. using namespace std;
   
3. 
   
4. class Solution {
   
5. public:
   
6.   /**
   
7.      * param A: A string
   
8.      * param offset: Rotate string with offset.
   
9.      * return: Rotated string.
   
10.      */
    
11.     string rotateString(string A, int offset) {
    
12.         if (A == "") {
    
13.             return A;
    
14.         }
    
15.         offset %= A.length();
    
16.         if (offset == 0) {
    
17.             return A;
    
18.         }
    
19.         reverse(A.begin(), A.begin() + A.length() - offset);
    
20.         reverse(A.begin() + A.length() - offset, A.end());
    
21.         reverse(A.begin(), A.end());
    
22.         return A;
    
23.     }
    
24. };

复制代码

复杂度：O(N)

Fizz Buzz
题意：纯水题，在面试里能碰见也算是人品爆发了。
解法：水过
代码：

1. class Solution {
   
2. public:
   
3.     /**
   
4.      * param n: As description.
   
5.      * return: A list of strings.
   
6.      */
   
7.     vector<string> fizzBuzz(int n) {
   
8.         vector<string> results;
   
9.         for (int i = 1; i <= n; i++) {
   
10.             if (i % 15 == 0) {
    
11.                 results.push_back("fizz buzz");
    
12.             } else if (i % 5 == 0) {
    
13.                 results.push_back("buzz");
    
14.             } else if (i % 3 == 0) {
    
15.                 results.push_back("fizz");
    
16.             } else {
    
17.                 results.push_back(to_string(i));
    
18.             }
    
19.         }
    
20.         return results;
    
21.     }
    
22. };

复制代码

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

Search Range in Binary Search Tree
题意：在一个BST中，给定K1个K2两个值，输出BST中所有介于两者之间的值，要求升序输出。
解法：对中序遍历进行修改，超出K1~K2的范围就不用继续递归了，可以理解为剪枝。
代码：

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 root: The root of the binary search tree.
    
17.      * @param k1 and k2: range k1 to k2.
    
18.      * @return: Return all keys that k1<=key<=k2 in ascending order.
    
19.      */
    
20.     vector<int> searchRange(TreeNode* root, int k1, int k2) {
    
21.         ans.clear();
    
22.         ll = k1;
    
23.         rr = k2;
    
24.         
    
25.         inorder(root);
    
26.         return ans;
    
27.     }
    
28. private:
    
29.     vector<int> ans;
    
30.     int ll;
    
31.     int rr;
    
32.    
    
33.     void inorder(TreeNode *root) {
    
34.         if (root == NULL) {
    
35.             return;
    
36.         }
    
37.         if (root->val > ll) {
    
38.             inorder(root->left);
    
39.         }
    
40.         if (root->val >= ll && root->val <= rr) {
    
41.             ans.push_back(root->val);
    
42.         }
    
43.         if (root->val < rr) {
    
44.             inorder(root->right);
    
45.         }
    
46.     }
    
47. };

复制代码

复杂度：时间基本还是O(N)，对递归进行剪枝并不降低理论复杂度。空间也是O(N)。

Min Stack
题意：实现一个栈，除了普通栈的功能外，还能随时返回栈中的最小值。
解法：经典题目，用一个额外的栈维护最小值。每当遇到小于等于当前最小值的，就压入栈中。这个最小栈始终是单调的。
代码：

1. #include <stack>
   
2. using namespace std;
   
3. 
   
4. class MinStack {
   
5. public:
   
6.     MinStack() {}
   
7. 
   
8.     void push(int number) {
   
9.         if (st.empty() || number <= mst.top()) {
   
10.             mst.push(number);
    
11.         }
    
12.         st.push(number);
    
13.     }
    
14. 
    
15.     int pop() {
    
16.         int val = st.top();
    
17.         if (mst.top() == st.top()) {
    
18.             mst.pop();
    
19.         }
    
20.         st.pop();
    
21.         return val;
    
22.     }
    
23. 
    
24.     int min() {
    
25.         return mst.top();
    
26.     }
    
27. private:
    
28.     stack<int> st, mst;
    
29. };

复制代码

复杂度：每个基本操作都是O(1)时间，维护一个最小栈需要额外O(N)空间。