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

zhuli19901106 发表于 2015-7-18 23:52
嗯，还剩4题。暂时不想做了，打算去干点别的~~这个跟leetcode是一样的，会不断添加新题目。感觉攒一段时 ...

我都没有刷什么hard题 刷完了medium之前的 这个确实难度比leetcode难一些

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

其实是有公式的。。

LeetCode上一道类似的题目 #233-Number-of-Digit-One (https://leetcode.com/problems/number-of-digit-one/)
只用六行py代码就AC了:

1. class Solution:
   
2.     # @param {integer} n
   
3.     # @return {integer}
   
4.     def countDigitOne(self, n):
   
5.         counter, i = 0, 1
   
6.         while i <= n:
   
7.             a, b = n/i, n%i
   
8.             counter += (a+8)/10*i + int(a%10==1)*(b+1)
   
9.             i *= 10
   
10.         return counter
    

复制代码

楼主你刷的好快啊我一天刷五题都不能保证啊，你这是第几遍刷啊

EroicaCMCS 发表于 2015-7-19 03:42
其实是有公式的。。

LeetCode上一道类似的题目 #233-Number-of-Digit-One (https://leetcode.com/prob ...

谢谢回复！我看了大概十分钟才看懂。
你的解法是算出每一位上1的个数，对吧。然后对于当前位就是1的，则加上后面的余数。
其中(a + 8) / 10 * i是算出当前位有多少个完整的i，每个完整的i对应了i个1。
比如100~199在第3位上总共有100个“1”。那么32222在第3位就有(322+ 8) / 10 * 100 = 3300个“1”。
看来我把这些东西累积起来算反而把问题搞复杂了，你和stellari都是单独考虑每一位上的1。
经过简单修改，已AC：

1. # This solution is credited to EroicaCMCS in 1point3acres
   
2. class Solution:
   
3.     # @param k & n  two integer
   
4.     # @return ans a integer
   
5.     def digitCounts(self, k, n):
   
6.         ans, b = 0, 1
   
7.         while b <= n:
   
8.             q, r = n / b, n % b
   
9.             ans += (q + 9 - k) / 10 * b
   
10.             if q % 10 == k:
    
11.                 ans += r + 1
    
12.             b *= 10
    
13.         return ans
    
14.         

复制代码

sevenwonder 发表于 2015-7-19 07:53
楼主你刷的好快啊我一天刷五题都不能保证啊，你这是第几遍刷啊

我是第一次刷，不过以前刷过其他的题，所以速度还行。不过你也看到了，刷题不在于快。关键是要简洁高效。
之后才是手速跟熟练度。

N-Queens
题意：著名的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 * N!)，空间O(N!)

N-Queens
题意：N huang hou wen ti
解法：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 * N!)，空间O(N!)。

N-Queens
题意：有敏感词吗
解法：DFS + 回溯
代码：

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 * N!)，空间O(N!)。

怎么一直被审核？下一题的题解一直发不出来。谁知道什么情况吗？

N-Queens II
题意：这次是求可行解的个数（N-Queens的题解一直被审核，不知什么原因。。）
解法：依然是DFS+回溯
代码：

1. class Solution {
   
2. public:
   
3.     /**
   
4.      * Calculate the total number of distinct N-Queen solutions.
   
5.      * @param n: The number of queens.
   
6.      * @return: The total number of distinct solutions.
   
7.      */
   
8.     int totalNQueens(int n) {
   
9.         ans = 0;
   
10.         if (n == 0) {
    
11.             return ans;
    
12.         }
    
13.         this->n = n;
    
14.         c.resize(n);
    
15.         d.resize(2 * n - 1);
    
16.         ad.resize(2 * n - 1);
    
17.         DFS(0);
    
18.         return ans;
    
19.     }
    
20. private:
    
21.     int ans;
    
22.     vector<bool> c, d, ad;
    
23.     int n;
    
24.    
    
25.     void DFS(int idx) {
    
26.         if (idx == n) {
    
27.             ++ans;
    
28.             return;
    
29.         }
    
30.         int i;
    
31.         for (i = 0; i < n; ++i) {
    
32.             if (c[i]) {
    
33.                 continue;
    
34.             }
    
35.             if (d[idx + i] || ad[n - 1 + idx - i]) {
    
36.                 continue;
    
37.             }
    
38.             
    
39.             c[i] = true;
    
40.             d[idx + i] = true;
    
41.             ad[n - 1 + idx - i] = true;
    
42.             
    
43.             DFS(idx + 1);
    
44.             
    
45.             ad[n - 1 + idx - i] = false;
    
46.             d[idx + i] = false;
    
47.             c[i] = false;
    
48.         }
    
49.     }
    
50. };

复制代码

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