【LeetCode算法系列题解】第36~40题

- LeetCode 36. 有效的数独（中等）
- LeetCode 37. 解数独（困难）
- LeetCode 38. 外观数列（中等）
- LeetCode 39. 组合总和（中等）
- LeetCode 40. 组合总和 II（中等）

LeetCode 36. 有效的数独（中等）

【题目描述】

请你判断一个 9 x 9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次（请参考示例图）。

注意：

一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
空白格用 '.' 表示。

【示例1】

在这里插入图片描述

输入：board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：true

【示例2】

输入：board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

【提示】

$b o a r d . l e n g t h == 9$
$b o a r d [i] . l e n g t h == 9$
board[i][j] 是一位数字（1-9）或者 '.'

【分析】

直接按题意模拟即可。

【代码】

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        bool st[10];
        for (int i = 0; i < 9; i++)
        {
            memset(st, false, sizeof st);
            for (int j = 0; j < 9; j++)
                if (board[i][j] == '.') continue;
                else if (st[board[i][j] - '0']) return false;
                else st[board[i][j] - '0'] = true;
        }
        for (int i = 0; i < 9; i++)
        {
            memset(st, false, sizeof st);
            for (int j = 0; j < 9; j++)
                if (board[j][i] == '.') continue;
                else if (st[board[j][i] - '0']) return false;
                else st[board[j][i] - '0'] = true;
        }
        for (int i = 0; i < 9; i += 3)  // 枚举每个3*3方格的左上角坐标
            for (int j = 0; j < 9; j += 3)
            {
                memset(st, false, sizeof st);
                for (int x = i; x < i + 3; x++)  // 枚举每个3*3方格中每个点的坐标
                    for (int y = j; y < j + 3; y++)
                        if (board[x][y] == '.') continue;
                        else if (st[board[x][y] - '0']) return false;
                        else st[board[x][y] - '0'] = true;
            }
        return true;
    }
};

LeetCode 37. 解数独（困难）

【题目描述】

编写一个程序，通过填充空格来解决数独问题。
数独的解法需遵循如下规则：

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次（请参考示例图）。

数独部分空格内已填入了数字，空白格用 '.' 表示。

【示例1】

在这里插入图片描述

输入：board = 
输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]

【提示】

$b o a r d . l e n g t h == 9$
$b o a r d [i] . l e n g t h == 9$
board[i][j] 是一位数字（1-9）或者 '.'
题目数据保证输入数独仅有一个解

【分析】

类似 N 皇后问题，爆搜每个位置可以填入的数，我们需要使用三个数组：row[i][x]、col[i][x]、cell[i][j][x]，分别表示第 $i$ 行（列）是否已经存在数字 $x$ 以及第 $i, j$ （左上角坐标）个3*3小方格是否已经存在数字 $x$ 。

【代码】

class Solution {
public:
    bool row[9][9], col[9][9], cell[3][3][9];

    void solveSudoku(vector<vector<char>>& board) {
        memset(row, false, sizeof row);
        memset(col, false, sizeof col);
        memset(cell, false, sizeof cell);
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++)
                if (board[i][j] == '.') continue;
                else
                {
                    int t = board[i][j] - '1';  // 将'1'-'9'映射为0-8
                    row[i][t] = col[j][t] = cell[i / 3][j / 3][t] = true;
                }
        dfs(board, 0, 0);  // 从第0行第0列开始搜索
    }

    bool dfs(vector<vector<char>>& board, int x, int y)
    {
        if (x == 9) return true;  // 搜完了所有位置，找到解
        if (y == 9) return dfs(board, x + 1, 0);  // 搜完了一行，x加一y清零
        if (board[x][y] != '.') return dfs(board, x, y + 1);  // 该位置已经有数直接跳过
        for (int i = 0; i < 9; i++)
            if (!row[x][i] && !col[y][i] && !cell[x / 3][y / 3][i])
            {
                board[x][y] = i + '1';
                row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = true;
                if (dfs(board, x, y + 1)) return true;  // 注意不能写return dfs(board, x, y + 1);
                board[x][y] = '.';  // 还原现场
                row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = false;
            }
        return false;  // 该位置已经用完了所有数，返回false
    }
};

LeetCode 38. 外观数列（中等）

【题目描述】

给定一个正整数 n，输出外观数列的第 n 项。
外观数列是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。
你可以将其视作是由递归公式定义的数字字符串序列：

countAndSay(1) = "1"
countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。

前五项如下：

1.     1
2.     11
3.     21
4.     1211
5.     111221
第一项是数字 1 
描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 "11"
描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 "21"
描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 "1211"
描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 "111221"

要描述一个数字字符串，首先要将字符串分割为最小数量的组，每个组都由连续的最多相同字符组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。

例如，数字字符串 "3322251" 的描述如下图：

在这里插入图片描述

【示例1】

输入：n = 1
输出："1"
解释：这是一个基本样例。

【示例2】

输入：n = 4
输出："1211"
解释：
countAndSay(1) = "1"
countAndSay(2) = 读 "1" = 一 个 1 = "11"
countAndSay(3) = 读 "11" = 二 个 1 = "21"
countAndSay(4) = 读 "21" = 一 个 2 + 一 个 1 = "12" + "11" = "1211"

【提示】

$1\le n\le 30$

【分析】

直接按题意模拟即可。

【代码】

class Solution {
public:
    string countAndSay(int n) {
        string s = "1";  // 初始化
        for (int i = 0; i < n - 1; i++)  // 需要变换n-1次
        {
            string t;
            for (int j = 0, k; j < s.size(); j = k)
            {
                k = j + 1;
                while (k < s.size() && s[k] == s[k - 1]) k++;  // 找到第一个不同的数
                t += to_string(k - j) + s[j];  // 一共k-j个s[j]
            }
            s = t;
        }
        return s;
    }
};

LeetCode 39. 组合总和（中等）

【题目描述】

给你一个无重复元素的整数数组 candidates 和一个目标整数 target，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。
candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。

【示例1】

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

【示例2】

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

【示例3】

输入: candidates = [2], target = 1
输出: []

【提示】

$1\le candidates.length\le 30$
$2\le candidates[i]\le 40$
candidates 的所有元素互不相同
$1\le target\le 40$

【分析】

本题要求出所有的方案，因此考虑可以使用爆搜。枚举每个数选不同的数量，若当前组合方案的和超过 target 了则直接剪枝。此外，由于相同的组合调换顺序不属于新的组合，因此爆搜的时候还需要保证顺序关系保证一种组合固定以一种顺序出现一次，而不会重复。

【代码】

class Solution {
public:
    vector<vector<int>> res;
    vector<int> v;

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        dfs(candidates, 0, target);
        return res;
    }

    // now表示从第几个数开始选，因为序列不能重复，例如[2,2,3]和[2,3,2]是一样的
    // target每次减去选中的数，减为0说明找到和恰好为target的序列
    void dfs(vector<int>& c, int now, int target)
    {
        if (target <= 0)  // 剪枝
        {
            if (target == 0) res.push_back(v);  // 找到一个合法序列
            return;
        }
        for (int i = now; i < c.size(); i++)  // 每次dfs都可以选一次now
        {
            v.push_back(c[i]);
            dfs(c, i, target - c[i]);
            v.pop_back();  // 还原现场
        }
    }
};

LeetCode 40. 组合总和 II（中等）

【题目描述】

给定一个候选人编号的集合 candidates 和一个目标数 target，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
注意：解集不能包含重复的组合。

【示例1】

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

【示例2】

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

【提示】

$1\le candidates.length\le 100$
$1\le candidates[i]\le 50$
$1\le target\le 30$

【分析】

与上一题基本一样，唯一区别在于每个元素只能选一次，因此每个数能选择的次数的上限是固定的，我们可以先将数组排好序，搜索的时候每次先求出每个数出现的次数，然后枚举每个数选择的次数即可。

【代码】

class Solution {
public:
    vector<vector<int>> res;
    vector<int> v;

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        dfs(candidates, 0, target);
        return res;
    }

    void dfs(vector<int>& c, int now, int target)
    {
        if (target == 0) { res.push_back(v); return; }
        if (now == c.size()) return;  // 已经遍历完所有数
        int k = now + 1;  // 找到第一个不相同数的下标
        while (k < c.size() && c[k] == c[now]) k++;
        int cnt = k - now;  // 一共有k-now个数相同
        for (int i = 0; i <= cnt && c[now] * i <= target; i++)  // 枚举c[now]选几个
        {
            dfs(c, k, target - c[now] * i);  // 下一个位置是下一个不同的数，也就是k
            v.push_back(c[now]);  // 注意刚开始是选0个，因此先搜索完才选c[now]
        }
        for (int i = 0; i <= cnt && c[now] * i <= target; i++)
            v.pop_back();  // 还原现场
    }
};