Mind palace

some thoughts

0%

Posted on Edited on In Disqus:
Symbols count in article: 2.2k Reading time ≈ 2 mins.

O(n*n!) time

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        do {
            res.push_back(nums);
        } while (next(nums));
        return res;
    }

    bool next(vector<int> &A) {
        int n = A.size();
        int x = 0, y = 0;
        for (int i = n - 1; i > 0; --i) {
            if (A[i - 1] < A[i]) {
                x = i - 1;
                y = i;
                break; // 说明从i开始后边全降序
            }
        }
        if (y == 0) return false;
        for (int i = n - 1; i > x; --i) {
            if (A[i] > A[x]) {
                swap(A[i], A[x]); // 找到下一个比A[x]大的开始下一轮遍历
                break;
            }
        }
        reverse(A.begin() + y, A.end());
        return true;
    }
};

backtracking O(n*n!) time

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        n, res = len(nums), []
        def dfs(A, b):
            if b == n:
                res.append(A)
                return
            for i in range(b, n):
                A[i], A[b] = A[b], A[i]
                dfs(A[:], b + 1)
        dfs(nums, 0)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        n, res = len(nums), []
        def dfs(b):
            if b == n:
                res.append(nums[:])
                return
            for i in range(b, n):
                nums[i], nums[b] = nums[b], nums[i]
                dfs(b + 1)
                nums[i], nums[b] = nums[b], nums[i]
        dfs(0)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        sort(begin(nums), end(nums));
        dfs(nums, 0);
        return res;
    }

    void dfs(vector<int> nums, int b) { // 这里nums是深拷贝！！
        int n = nums.size();
        if (b == n) {
            res.push_back(nums);
        }
        for (int i = b; i < n; ++i) {
            swap(nums[i], nums[b]); // 每次把一个数放到最前边（可以保证剩下的序列还是升序），然后对剩下的序列全排列
            dfs(nums, b + 1);
        }
    }

    vector<vector<int>> res;
};

O(nn) time

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        n = nums.size();
        visited.resize(n);
        sort(begin(nums), end(nums));
        dfs(nums);
        return res;
    }

    void dfs(const vector<int> &nums) {
        if (v.size() == n) {
            res.push_back(v);
            return;
        }
        for (int i = 0; i < n; ++i) {
            if (visited[i]) continue;
            visited[i] = true;
            v.push_back(nums[i]); // 把当前剩下还没访问过的数分别尝试append到v后边
            dfs(nums);
            v.pop_back();
            visited[i] = false;
        }
    }

    int n;
    vector<bool> visited;
    vector<int> v;
    vector<vector<int>> res;
};

Posted on Edited on In Disqus:
Symbols count in article: 1.2k Reading time ≈ 1 mins.

greedy O(n) time O(1) space
相当于BFS一棵树
last就是当前层所能达到的最远位置（可以覆盖的地方）
curr_max是当前位置能达到的最远位置
题解比较清楚
0 1 2 3 4 i
2 3 1 1 4 nums[i]
2 4 3 4 8 i + nums[i]
0 2 2 4 4 last
2 4 4 4 8 curr_max
{0(2)} –> {1(4) 2(3)} –> {3(4) 4(8)}
意思是最开始在0，不跳的话只能到0，如果想跳到1以后需要跳一次，这一次最远跳到2，然后如果想再跳到3以后需要再跳一次，这一次至少跳到4（最远跳到8但是不需要了），因为4已经达到最远点，跳出循环

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def jump(self, nums: List[int]) -> int:
        possible = curr = res = 0
        n = len(nums)
        for i in range(n):
            if curr >= n - 1:
                break
            if curr < i:
                curr = possible
                res += 1
            possible = max(possible, i + nums[i])
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        int last = 0;
        int curr_max = 0;
        int cnt = 0;
        for (int i = 0; i < n && last < n - 1; ++i) { // last < n - 1是一个优化，因为last达到n - 1就说明cnt已经够了
            if (i > last) { // bfs应该先更新，表示必须要jump一次才能达到当前的i
                last = curr_max;
                ++cnt;
            }
            curr_max = max(curr_max, i + nums[i]); // bfs应该后『遍历』如果颠倒顺序last少更新一次
        }
        return cnt;
    }
};

dp O(n2) time O(n) space TLE
dp[i]表示达到i所需要的最少步数
求dp[i]需要查询dp[j] where 0 <= j < i，然后+1
dp[0]肯定为0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int jump(vector<int>& nums) {
        int n(nums.size());
        vector<int> dp(n, INT_MAX);
        dp[0] = 0;
        for (int i(1); i < n; ++i) {
            for (int j(0); j < i; ++j) {
                if (j + nums[j] >= i)
                    dp[i] = min(dp[i], dp[j] + 1);
            }
        }
        return dp.back();
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 2.4k Reading time ≈ 2 mins.

backtracking best case O(m+n) time O(1) space
worst case O(mn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.length(), n = p.length();
        int i = 0, j = 0, ist = -1, jst = -1;
        while (i < m) {
            if (j < n && (s[i] == p[j] || p[j] == '?')) {
                ++i;
                ++j;
            } else if (j < n && (p[j] == '*')) { // 保存*匹配到的i和j
                ist = i;
                jst = j++;
            } else if (ist >= 0) { // 如果之前匹配过*
                i = ++ist; // 这里重置到ist的下一个是因为*有可能匹配多个字符，方便重置i
                j = jst + 1; // backtracking假设*可以cover之前的ist那个字符，继续尝试匹配之后的字符
            } else return false;
        }
        while (j < n && p[j] == '*') { // 只有p后边全是*才说明完全匹配上了
            ++j;
        }
        return j == n;
    }
};

dp O(mn) time O(mn) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        f = [[False] * (n + 1) for _ in range(m + 1)]
        f[0][0] = True
        for i in range(1, n + 1):
            f[0][i] = p[i - 1] == '*' and f[0][i - 1]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == '*':
                    f[i][j] = f[i][j - 1] or f[i - 1][j]
                else:
                    f[i][j] = f[i - 1][j - 1] and (s[i - 1] == p[j - 1] or p[j - 1] == '?')
        return f[m][n]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.length(), m = p.length();
        vector<vector<int>> f(n + 1, vector<int>(m + 1));
        f[0][0] = true; // 两个空串肯定匹配
        for (int j = 1; j <= m; ++j) {
            f[0][j] = f[0][j - 1] && (p[j - 1] == '*'); // *可以匹配任意多个字符，所以直接继承前一个的结果
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (p[j - 1] == '*') {
                    f[i][j] = f[i][j - 1] || f[i - 1][j]; // s[i - 1]不去跟*匹配，看s[0:i-1]和p[0:j-2]是否匹配；s[i - 1]去跟*匹配，看s[0:i-2]和p[0:j-1]是否匹配
                } else {
                    f[i][j] = f[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '?'); // 两字符相同（或通配符是?）直接查看之前的匹配结果
                }
            }
        }
        return f[n][m];
    }
};

recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.length(), n = p.length();
        cache.resize(m + 1, vector<int>(n + 1, -1));
        return f(m, n, s, p);
    }

    bool f(int i, int j, const string &s, const string &p) {//cout<<i<<" "<<j<<endl;
        if (i == 0 && j == 0) return true;
        if (i > 0 && j < 1) return false;
        if (cache[i][j] != -1) return cache[i][j];
        if (i == 0) return cache[i][j] = p[j - 1] == '*' && f(i, j - 1, s, p);
        if (p[j - 1] == '*') return cache[i][j] = f(i, j - 1, s, p) || f(i - 1, j, s, p);
        return cache[i][j] = (s[i - 1] == p[j - 1] || p[j - 1] == '?') && f(i - 1, j - 1, s, p);
    }

    vector<vector<int>> cache;
};

Posted on Edited on In Disqus:
Symbols count in article: 826 Reading time ≈ 1 mins.

O(mn) time O(m+n) space

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        m, n = len(num1), len(num2)
        num = [0] * (m + n)
        for i in range(m - 1, -1, -1):
            c = 0
            for j in range(n - 1, -1, -1):
                s = num[i + j + 1] + int(num1[i]) * int(num2[j]) + c
                c, num[i + j + 1] = divmod(s, 10)
            num[i] = c
        res = ''.join(map(str, num)).lstrip('0')
        return res if res else '0'
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    string multiply(string num1, string num2) {
        int m = num1.length(), n = num2.length();
        string res(m + n, '0');
        for (int i = m - 1, j; i >= 0; --i) {
            int c = 0;
            for (j = n - 1; j >= 0; --j) {
                int s = (res[i + j + 1] - '0') + (num1[i] - '0') * (num2[j] - '0') + c;
                res[i + j + 1] = s % 10 + '0';
                c = s / 10;
            }
            res[i] = c + '0';
        }
        int p = res.find_first_not_of("0");
        return p == string::npos ? "0" : res.substr(p);
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1.1k Reading time ≈ 1 mins.

O(n)
跟11. Container With Most Water方法几乎一样

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        l, r, res = 0, n - 1, 0
        while l < r:
            mn = min(height[l], height[r])
            while l < r and height[l] <= mn:
                res += mn - height[l]
                l += 1
            while l < r and height[r] <= mn:
                res += mn - height[r]
                r -= 1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int l = 0, r = n - 1;
        int res = 0;
        while (l < r) {
            int mn = min(height[l], height[r]);
            while (l < r && height[l] <= mn) {
                res += mn - height[l];
                ++l;
            }
            while (l < r && height[r] <= mn) {
                res += mn - height[r];
                --r;
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int trap(vector<int>& height) {
        int left(0), right(height.size() - 1), ret(0);
        while (left < right) {
            auto min(std::min(height[left], height[right]));
            if (min == height[left])
                while (++left < right && height[left] < min)
                    ret += min - height[left];
            else
                while (left < --right && height[right] < min)
                    ret += min - height[right];
        }
        return ret;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1.5k Reading time ≈ 1 mins.

O(n) time O(1) space
负号法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i, x in enumerate(nums):
            if x < 1 or x > n:
                nums[i] = n + 1
        for x in nums:
            x = abs(x)
            if 0 < x <= n:
                nums[x - 1] = -abs(nums[x - 1]);
        for i, x in enumerate(nums):
            if x > 0:
                return i + 1
        return n + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int &x : nums) {
            if (x < 1 || x > n) {
                x = n + 1;
            }
        }
        for (int x : nums) {
            x = abs(x);
            if (0 < x && x <= n) {
                nums[x - 1] = -abs(nums[x - 1]);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) return i + 1;
        }
        return n + 1;
    }
};

类似桶排序，每个数都应该放在对应的位置，即 nums[i] == nums[nums[i] - 1]，所以不停交换数，尽可能把每个数挪到对应的位置

1
2
3
4
5
6
7
8
9
10
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            while 0 < nums[i] <= n and nums[i] != nums[nums[i] - 1]:
                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1] # 注意不能写成nums[i], nums[nums[i] - 1] = nums[nums[i] - 1], nums[i]因为从左到右赋值，nums[i]先被修改，nums[nums[i] - 1]的新值是错的！！必要时可以考虑加一个中间变量t来swap
        for i, x in enumerate(nums):
            if x != i + 1:
                return i + 1
        return n + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) { // 交换的条件，nums[i]必须在(0, n]之间，而且被交换的数不能等于nums[i]，否则会造成死循环
                swap(nums[i], nums[nums[i] - 1]);
            }
        }
        for (int i = 0; i < n; ++i) { // 查找第一个不在对应位置的数
            if (nums[i] != i + 1) return i + 1;
        }
        return n + 1;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1.4k Reading time ≈ 1 mins.

backtracking
对比39. Combination Sum这道题candidates可能有dup且每个candidate只能用一次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        res, A = [], []
        candidates.sort()
        def dfs(b, s):
            if s == 0:
                res.append(A[:])
                return
            for i in range(b, len(candidates)):
                x = candidates[i]
                if x > s:
                    break
                if i > b and x == candidates[i - 1]:
                    continue
                A.append(x)
                dfs(i + 1, s - x)
                A.pop()
        dfs(0, target)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        candidates.sort()
        def dfs(b, s, A):
            if s == 0:
                res.append(A)
                return
            for i in range(b, len(candidates)):
                x = candidates[i]
                if x > s:
                    break
                if i > b and x == candidates[i - 1]:
                    continue
                dfs(i + 1, s - x, A + [x])
        dfs(0, target, [])
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(begin(candidates), end(candidates));
        dfs(candidates, 0, target);
        return res;
    }

    void dfs(const vector<int> &candidates, int b, int target) {
        if (target == 0) {
            res.push_back(v);
            return;
        }
        for (int i = b; i < candidates.size() && candidates[i] <= target; ++i) {
            if (i > b && candidates[i] == candidates[i - 1]) continue; // 去重
            v.push_back(candidates[i]);
            dfs(candidates, i + 1, target - candidates[i]); // 从下一个开始
            v.pop_back();
        }
    }

    vector<int> v;
    vector<vector<int>> res;
};

Posted on Edited on In Disqus:
Symbols count in article: 1.3k Reading time ≈ 1 mins.

backtracking
如果问个数就是背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res, A = [], []
        candidates.sort()
        def dfs(b, s):
            if s == 0:
                res.append(A[:]) # 注意要copy!!!
                return
            for i in range(b, len(candidates)):
                x = candidates[i]
                if x > s:
                    break
                A.append(x)
                dfs(i, s - x)
                A.pop()
        dfs(0, target)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        candidates.sort()
        def dfs(b, s, A):
            if s == 0:
                res.append(A)
                return
            for i in range(b, len(candidates)):
                x = candidates[i]
                if x > s:
                    break
                dfs(i, s - x, A + [x]) # 会触发copy
        dfs(0, target, [])
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(begin(candidates), end(candidates)); // 用来加速和去重
        dfs(candidates, 0, target);
        return res;
    }

    void dfs(const vector<int> &candidates, int b, int target) {
        if (target == 0) {
            res.push_back(v);
            return;
        }
        for (int i = b; i < candidates.size() && candidates[i] <= target; ++i) { // 注意candidates <= target
            v.push_back(candidates[i]); // 尝试寻找以candidates[i]开头的可行解
            dfs(candidates, i, target - candidates[i]);
            v.pop_back();
        }
    }

    vector<int> v;
    vector<vector<int>> res;
};

Posted on Edited on In Disqus:
Symbols count in article: 2.5k Reading time ≈ 2 mins.

sliding window

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def countAndSay(self, n: int) -> str:
        res = '1'
        for x in range(1, n):
            s, i, j, n = '', 0, 1, len(res)
            while i < n:
                while j < n and res[j] == res[i]:
                    j += 1
                s += str(j - i) + res[i]
                i = j
            res = s
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def countAndSay(self, n: int) -> str:
        def cas(s):
            res = ''
            i, j, n = 0, 1, len(s)
            while i < n:
                while j < n and s[j] == s[i]:
                    j += 1
                res += str(j - i) + s[i]
                i = j
            return res
        res = '1'
        for x in range(1, n):
            res = cas(res)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    string countAndSay(int n) {
        string res = "1";
        for (int i = 1; i < n; ++i) {
            res = helper(res);
        }
        return res;
    }

    string helper(const string &s) {
        int n = s.length(), cnt = 0;
        string res;
        for (int i = 0; i < n; ++i) {
            char c = s[i];
            int cnt = 0, j = i;
            for (; j < n && s[j] == c; ++j) {
                ++cnt;
            }
            res += to_string(cnt);
            res += c;
            i = j - 1;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    string countAndSay(int n) {
        string res = "1";
        for (int i = 1; i < n; ++i) {
            res = helper(res);
        }
        return res;
    }

    string helper(string &s) {
        s += "#";
        char prev = '#';
        int b = 0;
        int n = s.length();
        string res;
        for (int i = 0; i < n; ++i) {
            if (s[i] != prev) {
                if (i - b > 0) {
                    res += to_string(i - b);
                    res += prev;
                }
                prev = s[i];
                b = i;
            }
        }
        return res;
    }
};

iterative

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    string countAndSay(int n) {
        string res = "1";
        while (n-- > 1) {
            string s;
            int l = 0, r = 1, len = size(res);
            while (l < len) {
                while (r < len && res[r] == res[l]) ++r;
                s += to_string(r - l) + res[l];
                l = r;
            }
            swap(res, s);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    string countAndSay(int n) {
        string res = "1";
        while (n-- > 1) { // 要从1开始，因为0已经数过了
            int len = size(res);
            res += "#"; // padding以防最后越界
            string s;
            int cnt = 1; // cnt要从1开始，因为每次res[i] != res[i + 1]的时候会少做一次cnt++
            for (int i = 0; i < len; ++i) {
                if (res[i] == res[i + 1]) {
                    ++cnt;
                } else {
                    s += to_string(cnt) + res[i];
                    cnt = 1;
                }
            }
            swap(res, s);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    string countAndSay(int n) {
        string res = "1";
        for (int i = 1; i < n; ++i) {
            res += "#";
            char prev = '#';
            int b = 0;
            int len = res.length();
            string s;
            for (int i = 0; i < len; ++i) {
                if (res[i] != prev) {
                    if (i - b > 0) {
                        s += to_string(i - b);
                        s += prev;
                    }
                    prev = res[i];
                    b = i;
                }
            }
            swap(res, s);
        }
        return res;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 3k Reading time ≈ 3 mins.

backtracking
预处理board把每个cell能算出来的都填上，再跑backtracking试数
先写backtracking，再写预处理优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        row.resize(9);
        col.resize(9);
        sub.resize(9);
        s.resize(81);
        for (int r = 0; r < 9; ++r) {
            for (int c = 0; c < 9; ++c) {
                if (board[r][c] != '.') {
                    int i = board[r][c] - '0';
                    row[r][i] = col[c][i] = sub[r / 3 * 3 + c / 3][i] = true;
                }
            }
        }
        int change = 0;
        do {
            change = 0;
            for (int r = 0; r < 9; ++r) {
                for (int c = 0; c < 9; ++c) {
                    if (board[r][c] == '.') {
                        for (int i = 1; i <= 9; ++i) {
                            if (!row[r][i] && !col[c][i] && !sub[r / 3 * 3 + c / 3][i]) {
                                s[r * 9 + c].insert(i);
                            }
                        }
                        if (s[r * 9 + c].size() == 1) {
                            int i = *s[r * 9 + c].begin();
                            board[r][c] = '0' + i;
                            ++change;
                            row[r][i] = col[c][i] = sub[r / 3 * 3 + c / 3][i] = true;
                        }
                    }
                }
            }
        } while (change > 0);
        dfs(board, 0);
    }

    bool dfs(vector<vector<char>> &b, int idx) {
        if (idx == 81) return true;
        int r = idx / 9, c = idx % 9;
        if (b[r][c] != '.') return dfs(b, idx + 1);
        for (int i : s[idx]) {
            if (row[r][i] || col[c][i] || sub[r / 3 * 3 + c / 3][i]) continue;
            b[r][c] = '0' + i;
            row[r][i] = col[c][i] = sub[r / 3 * 3 + c / 3][i] = true;
            if (dfs(b, idx + 1)) return true;
            row[r][i] = col[c][i] = sub[r / 3 * 3 + c / 3][i] = false;
        }
        b[r][c] = '.'; // revert
        return false;
    }

    vector<bitset<10>> row, col, sub;
    vector<unordered_set<int>> s; // 对每个位置来说所有可能的数
};

没有预处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        h = [[False] * 10 for _ in range(9)]
        v = [[False] * 10 for _ in range(9)]
        s = [[False] * 10 for _ in range(9)]
        for r in range(9):
            for c in range(9):
                x = board[r][c]
                if x != '.':
                    x = int(x)
                    h[r][x] = v[c][x] = s[r // 3 * 3 + c // 3][x] = True
        def dfs(idx):
            if idx == 81: return True
            r, c = divmod(idx, 9)
            if board[r][c] != '.': return dfs(idx + 1)
            for x in range(1, 10):
                if h[r][x] or v[c][x] or s[r // 3 * 3 + c // 3][x]: continue
                board[r][c] = str(x)
                h[r][x] = v[c][x] = s[r // 3 * 3 + c // 3][x] = True
                if dfs(idx + 1): return True
                h[r][x] = v[c][x] = s[r // 3 * 3 + c // 3][x] = False
                board[r][c] = '.'
            return False
        dfs(0)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        row.resize(9);
        col.resize(9);
        sub.resize(9);
        for (int r = 0; r < 9; ++r) {
            for (int c = 0; c < 9; ++c) {
                if (board[r][c] != '.') {
                    int i = board[r][c] - '0';
                    row[r][i] = col[c][i] = sub[r / 3 * 3 + c / 3][i] = true;
                }
            }
        }
        dfs(board, 0);
    }

    bool dfs(vector<vector<char>> &b, int idx) {
        if (idx == 81) return true;
        int r = idx / 9, c = idx % 9;
        if (b[r][c] != '.') return dfs(b, idx + 1);
        for (int i = 1; i <= 9; ++i) {
            if (row[r][i] || col[c][i] || sub[r / 3 * 3 + c / 3][i]) continue;
            b[r][c] = '0' + i;
            row[r][i] = col[c][i] = sub[r / 3 * 3 + c / 3][i] = true;
            if (dfs(b, idx + 1)) return true;
            row[r][i] = col[c][i] = sub[r / 3 * 3 + c / 3][i] = false;
		    b[r][c] = '.';
        }
        return false;
    }

    vector<bitset<10>> row, col, sub;
};