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

Partition Array
题意：给定一个数组和一个值K，请把所有小于K的放到左边，大于等于的放右边。
解法：理解快速排序的代码。
代码：

1. #include <algorithm>
   
2. #include <climits>
   
3. using namespace std;
   
4. 
   
5. class Solution {
   
6. public:
   
7.     int partitionArray(vector<int> &nums, int k) {
   
8.         int n = nums.size();
   
9.         int i, j;
   
10.         int piv = INT_MAX;
    
11.         int mi = -1;
    
12.         for (i = 0; i < n; ++i) {
    
13.             if (nums[i] >= k) {
    
14.                 piv = min(piv, nums[i]);
    
15.                 mi = i;
    
16.             }
    
17.         }
    
18.         if (mi == -1) {
    
19.             return n;
    
20.         }
    
21.         swap(nums[0], nums[mi]);
    
22.         
    
23.         i = 1;
    
24.         j = n - 1;
    
25.         while (true) {
    
26.             while (i <= j && nums[i] < piv) {
    
27.                 ++i;
    
28.             }
    
29.             while (i <= j && nums[j] >= piv) {
    
30.                 --j;
    
31.             }
    
32.             if (i > j) {
    
33.                 break;
    
34.             }
    
35.             swap(nums[i++], nums[j--]);
    
36.         }
    
37.         swap(nums[0], nums[j]);
    
38.         while (j > 0 && nums[j - 1] >= k) {
    
39.             --j;
    
40.         }
    
41.         return j;
    
42.     }
    
43. };

复制代码

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

zhuli19901106 发表于 2015-7-18 16:11
Digit Counts
题意：给定一个数字k，以及一个整数n，求0~n的所有整数中，数字k出现了多少次。k可以是0~9。 ...

这道题可以这样。比如现在n = 4123, k = 2。我们可以依次决定在每位数字上，k出现了多少次。比如现在要找第3位，也就是4(1)23的括号标注的这位上出现的2的个数，那么我们可以先把4123切成3部分：
4 / 1 /  23
(hi/cur/rem)
这一位上的2有400个，也就是最高位的 x 10^(最高位base-1)
如果n是4523，则
这位上的2有500个，就是(4+1) x 10^(最高位base-1)
但如果n是4223, 则
这位上的2有424个，就是4 x 10^(base-1) + 23 +1 (+1是因为4100~4123总共是24种情况，4100也要算进来)

因此可以有规则：如果cur < k, result += hi * 10^(base-1); 如果cur > k, result += (hi+1) * 10^(base -1);
如果cur==k, result += (hi) * 10^(base-1) + rem + 1;

所以可以有下面的代码。一个小细节是，我在网上看到的大部分基于这种思路的实现都是需要把base定义成long long，我的这种实现方式的好处是base定义成int即可。虽然base同样可能会溢出，但是循环能够保证在溢出的base参与任何运算之前就退出循环，所以不会影响结果。

1.    
   
2.     int digitCounts(int k, int n) {
   
3.         // write your code here
   
4.         int base = 1;
   
5.         int result = 0;
   
6.         int rem = 0;
   
7.         while (n > 0) {
   
8.             int cur = n % 10;       // 得到当前位
   
9.             n /= 10;                // 和高于当前位的部分
   
10.             
    
11.             // 当前位上的k的个数至少是n*base，但根据cur的具体取值
    
12.             // 可能有以下三条规则：
    
13.             if (cur < k) result += n * base;
    
14.             else if (cur > k) result += (n + 1) * base;
    
15.             else result += n * base + rem +1;
    
16. 
    
17.             rem += base*cur;        // 得到低于当前位的部分
    
18.             base*=10;               // 更新base
    
19.         }
    
20.         return result;
    
21.     }

复制代码

354886 发表于 2015-7-18 23:14
medium我一天最多十道已经是极限了。佩服

共勉~~希望持续的付出能换来offer~

stellari 发表于 2015-7-18 23:19
这道题可以这样。比如现在n = 4123, k = 2。我们可以依次决定在每位数字上，k出现了多少次。比如现在要找 ...

真是大道至简。。
同样一题我写完了自己都看不懂，你的版本20行就搞定。学习了~
有了stellari，天黑都不怕~~

zhuli19901106 发表于 2015-7-18 23:27
真是大道至简。。
同样一题我写完了自己都看不懂，你的版本20行就搞定。学习了~
有了stellari，天黑都 ...

不敢不敢，这个算法我也是从网上看来的。只是在实现上稍微做了点加工而已。

其实我的经验是，Lintcode敢标记为Medium的题，一定存在有比较简洁的实现。否则如果必须写许多行的话，一般就会升格为Hard了。遇到Medium题不妨多想想看，说不定能找到比自己现在方法简单得多的实现呢。

Minimum Window Substring
题意：给定一个字符串source，和一个字符串target。你要找出长度最短的，而且包含了所有target中字符的source的子串。
解法：也就是说，首先要包含target中的所有字符，而且允许再包含些多余的字符。于是我的想法就是要随时统计各字符个数，使用一前一后两个指针逐步往前移。随时看是否找到了更短的window substring，更新最终结果。
代码：

1. #include <cstring>
   
2. using namespace std;
   
3. 
   
4. class Solution {
   
5. public:   
   
6.     /**
   
7.      * @param source: A string
   
8.      * @param target: A string
   
9.      * @return: A string denote the minimum window
   
10.      *          Return "" if there is no such a string
    
11.      */
    
12.     string minWindow(string &source, string &target) {
    
13.         string &s = source;
    
14.         string &t = target;
    
15.         int tc[256];
    
16.         int c[256];
    
17.         int cc;
    
18.         int ls = s.length();
    
19.         int lt = t.length();
    
20.         int i, j;
    
21.         int mi, mj;
    
22.         
    
23.         memset(tc, 0, sizeof(tc));
    
24.         cc = 0;
    
25.         for (i = 0; i < lt; ++i) {
    
26.             ++tc[t[i]];
    
27.             ++cc;
    
28.         }
    
29.         
    
30.         memset(c, 0, sizeof(c));
    
31.         mi = 0;
    
32.         mj = ls;
    
33.         i = j = 0;
    
34.         while (j < ls) {
    
35.             if (c[s[j]] < tc[s[j]]) {
    
36.                 --cc;
    
37.             }
    
38.             ++c[s[j]];
    
39.             if (cc == 0) {
    
40.                 while (cc == 0) {
    
41.                     if (j - i < mj - mi) {
    
42.                         mi = i;
    
43.                         mj = j;
    
44.                     }
    
45.                     --c[s[i]];
    
46.                     if (c[s[i]] < tc[s[i]]) {
    
47.                         ++cc;
    
48.                     }
    
49.                     ++i;
    
50.                 }
    
51.             }
    
52.             ++j;
    
53.         }
    
54.         
    
55.         if (mj == ls) {
    
56.             return "";
    
57.         } else {
    
58.             return s.substr(mi, mj - mi + 1);
    
59.         }
    
60.     }
    
61. };

复制代码

复杂度：时间O(N)，空间O(1)。用于统计字符个数的空间不知道算不算O(1)。

楼主 你的hard题也都刷的差不多了吗？

N-Queens
题意：著名的N皇后问题。在NxN的棋盘上放置N个皇后，不能同行、同列、同对角线、同反对角线
解法：逐行DFS，同时记录列、对角线、反对角线的占用情况，以便能在O(1)时间内检查一个位置是否可放置。
代码：

1. class Solution {
   
2. public:
   
3.     /**
   
4.      * Get all distinct N-Queen solutions
   
5.      * @param n: The number of queens
   
6.      * @return: All distinct solutions
   
7.      * For example, A string '...Q' shows a queen on forth position
   
8.      */
   
9.     vector<vector<string> > solveNQueens(int n) {
   
10.         ans.clear();
    
11.         if (n == 0) {
    
12.             return ans;
    
13.         }
    
14.         this->n = n;
    
15.         c.resize(n);
    
16.         d.resize(2 * n - 1);
    
17.         ad.resize(2 * n - 1);
    
18.         DFS(0);
    
19.         return ans;
    
20.     }
    
21. private:
    
22.     vector<vector<string> > ans;
    
23.     vector<bool> c, d, ad;
    
24.     int n;
    
25.     vector<string> s;
    
26.     vector<int> b;
    
27.    
    
28.     void DFS(int idx) {
    
29.         if (idx == n) {
    
30.             convertBoard();
    
31.             ans.push_back(s);
    
32.             return;
    
33.         }
    
34.         int i;
    
35.         for (i = 0; i < n; ++i) {
    
36.             if (c[i]) {
    
37.                 continue;
    
38.             }
    
39.             if (d[idx + i] || ad[n - 1 + idx - i]) {
    
40.                 continue;
    
41.             }
    
42.             
    
43.             b.push_back(i);
    
44.             c[i] = true;
    
45.             d[idx + i] = true;
    
46.             ad[n - 1 + idx - i] = true;
    
47.             
    
48.             DFS(idx + 1);
    
49.             
    
50.             ad[n - 1 + idx - i] = false;
    
51.             d[idx + i] = false;
    
52.             c[i] = false;
    
53.             b.pop_back();
    
54.         }
    
55.     }
    
56.    
    
57.     void convertBoard() {
    
58.         int i;
    
59.         string line;
    
60.         s.clear();
    
61.         line.resize(n, '.');
    
62.         for (i = 0; i < n; ++i) {
    
63.             line[b[i]] = 'Q';
    
64.             s.push_back(line);
    
65.             line[b[i]] = '.';
    
66.         }
    
67.     }
    
68. };

复制代码

复杂度：时间空间均为O(N!)。

julia1006 发表于 2015-7-18 23:49
楼主 你的hard题也都刷的差不多了吗？

嗯，还剩4题。暂时不想做了，打算去干点别的~~这个跟leetcode是一样的，会不断添加新题目。感觉攒一段时间再回来刷也可以。

刚才发了一题被审核了？莫非碰到敏感词了？
算了，可能是一次发太多了。明后天我接着来写吧。