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

这篇具有很好参考价值的文章主要介绍了【LeetCode算法系列题解】第36~40题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

LeetCode 36. 有效的数独(中等)

【题目描述】

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

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

注意:

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

【示例1】

【LeetCode算法系列题解】第36~40题,LeetCode,算法,leetcode,深度优先,c++,学习

输入: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 board.length == 9 board.length==9
b o a r d [ i ] . l e n g t h = = 9 board[i].length == 9 board[i].length==9
board[i][j] 是一位数字(1-9)或者 '.'

【分析】


直接按题意模拟即可。


【代码】文章来源地址https://www.toymoban.com/news/detail-688277.html

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】

【LeetCode算法系列题解】第36~40题,LeetCode,算法,leetcode,深度优先,c++,学习

输入: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 board.length == 9 board.length==9
b o a r d [ i ] . l e n g t h = = 9 board[i].length == 9 board[i].length==9
board[i][j] 是一位数字(1-9)或者 '.'
题目数据保证输入数独仅有一个解

【分析】


类似 N 皇后问题,爆搜每个位置可以填入的数,我们需要使用三个数组:row[i][x]col[i][x]cell[i][j][x],分别表示第 i i i 行(列)是否已经存在数字 x x x 以及第 i , j i,j i,j(左上角坐标)个3*3小方格是否已经存在数字 x x 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" 的描述如下图:

【LeetCode算法系列题解】第36~40题,LeetCode,算法,leetcode,深度优先,c++,学习

【示例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 ≤ n ≤ 30 1\le n\le 30 1n30

【分析】


直接按题意模拟即可。


【代码】

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 ≤ c a n d i d a t e s . l e n g t h ≤ 30 1\le candidates.length\le 30 1candidates.length30
2 ≤ c a n d i d a t e s [ i ] ≤ 40 2\le candidates[i]\le 40 2candidates[i]40
candidates 的所有元素互不相同
1 ≤ t a r g e t ≤ 40 1\le target\le 40 1target40

【分析】


本题要求出所有的方案,因此考虑可以使用爆搜。枚举每个数选不同的数量,若当前组合方案的和超过 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 ≤ c a n d i d a t e s . l e n g t h ≤ 100 1\le candidates.length\le 100 1candidates.length100
1 ≤ c a n d i d a t e s [ i ] ≤ 50 1\le candidates[i]\le 50 1candidates[i]50
1 ≤ t a r g e t ≤ 30 1\le target\le 30 1target30

【分析】


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


【代码】

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();  // 还原现场
    }
};

到了这里,关于【LeetCode算法系列题解】第36~40题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C语言 | Leetcode C语言题解之第36题有效的数独

    题目: 题解:

    2024年04月22日
    浏览(37)
  • 【深度优先】【广度优先】Leetcode 104 二叉树的最大深度 Leetcode 111 二叉树的最小深度 Leetcode 110 平衡二叉树

    二叉树节点的深度: 指从根节点到该节点的最长简单路径边的条数或者节点数 (取决于深度从0开始还是从1开始) 二叉树节点的高度: 指从该节点到叶子节点的最长简单路径边的条数后者节点数 (取决于高度从0开始还是从1开始) 【前序求的是深度,后序求的是高度】 -

    2024年02月19日
    浏览(52)
  • LeetCode-200. 岛屿数量【深度优先搜索 广度优先搜索 并查集 数组 矩阵】

    给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。 岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外,你可以假设该网格的四条边均被水包围。 示例 1: 输入:grid = [ [“1”,“1”,“1”,“

    2024年04月14日
    浏览(38)
  • 【快乐手撕LeetCode题解系列】——移除元素

        😎博客昵称:博客小梦 😊最喜欢的座右铭:全神贯注的上吧!!! 😊作者简介:一名热爱C/C++,算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主! 😘博主小留言:哈喽! 😄各位CSDN的uu们,我是你的博客好友小梦,希望我的文章可以给您带来一定的帮助,话不

    2023年04月15日
    浏览(35)
  • 【快乐手撕LeetCode题解系列】——消失的数字

        😎博客昵称:博客小梦 😊最喜欢的座右铭:全神贯注的上吧!!! 😊作者简介:一名热爱C/C++,算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主! 😘博主小留言:哈喽! 😄各位CSDN的uu们,我是你的博客好友小梦,希望我的文章可以给您带来一定的帮助,话不

    2024年02月01日
    浏览(33)
  • ※【回溯】【深度优先前序】Leetcode 257. 二叉树的所有路径

    ---------------🎈🎈257. 二叉树的所有路径 题目链接🎈🎈------------------- 时间复杂度O(N) 空间复杂度O(N) 深度优先遍历 添加了 StringBulider 替代字符串拼接提升效率 toString() 转化为String .append() 添加元素 时间复杂度O(N) 空间复杂度O(N)

    2024年02月20日
    浏览(37)
  • 每天一道leetcode:797. 所有可能的路径(图论&中等&深度优先遍历)

    给你一个有 n 个节点的 有向无环图(DAG) ,请你找出所有从节点 0 到节点 n-1 的路径并输出( 不要求按特定顺序 ) graph[i] 是一个从节点 i 可以访问的所有节点的列表(即从节点 i 到节点 graph[i][j] 存在一条有向边)。 n == graph.length 2 = n = 15 0 = graph[i][j] n graph[i][j] != i (即不存

    2024年02月12日
    浏览(60)
  • Leetcode题解-算法-动态规划(python版)

    1.1 爬楼梯 70. 爬楼梯(Easy) 走n阶楼梯的方法有两种,1、先走 1 级台阶,再走 n-1 级台阶;2、先走 2 级台阶,再走 n-2 级台阶 f(n) = f(n-1) + f(n-2) 1.2 强盗抢劫 198. 打家劫舍(Medium) 每个房间财产为 nums[0]……nums[n-1]。 假设 0 至 x 间房获得的最大财产为 f(x)。 f(x) = max(f(x-1),f(x-2)+nums[

    2024年02月03日
    浏览(47)
  • LeetCode算法题解(动态规划)|LeetCode343. 整数拆分、LeetCode96. 不同的二叉搜索树

    题目链接:343. 整数拆分 题目描述: 给定一个正整数  n  ,将其拆分为  k  个  正整数  的和(  k = 2  ),并使这些整数的乘积最大化。 返回  你可以获得的最大乘积  。 示例 1: 示例 2: 提示: 2 = n = 58 算法分析: 定义dp数组及下标含义: dp[i]表述正整数i拆分成k个正整数

    2024年02月04日
    浏览(39)
  • 【完全二叉树节点数!】【深度优先】【广度优先】Leetcode 222 完全二叉树的节点个数

    ---------------🎈🎈题目链接🎈🎈------------------- 完全二叉树只有两种情况: 情况一:就是满二叉树, 情况二:最后一层叶子节点没有满。 对于情况一,可以直接用 2 ^ 树深度 - 1 来计算,注意这里根节点深度为1。 对于情况二,分别递归左孩子,和右孩子,递归到某一深度一

    2024年02月19日
    浏览(34)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包