37. 解数独 - 力扣(LeetCode)

这篇具有很好参考价值的文章主要介绍了37. 解数独 - 力扣(LeetCode)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述
编写一个程序,通过填充空格来解决数独问题。

数独的解法需 遵循如下规则:

  • 数字 1-9 在每一行只能出现一次。
  • 数字 1-9 在每一列只能出现一次。
  • 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

数独部分空格内已填入了数字,空白格用 ‘.’ 表示。
37. 解数独 - 力扣(LeetCode),leetcode,算法,职场和发展

输入示例

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"]]

解题思路
37. 解数独 - 力扣(LeetCode),leetcode,算法,职场和发展

解题代码文章来源地址https://www.toymoban.com/news/detail-820484.html

class Solution {
    public void solveSudoku(char[][] board) {
        backtrack(board);
    }
    
    public boolean backtrack(char[][] board) {
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                // 跳过原始数字
                if(board[i][j] != '.') {
                    continue;
                }
                // 只处理空白格,填写1-9
                for(char k = '1'; k <= '9'; k++) {
                    if(isValid(i, j, k, board)) {
                        board[i][j] = k;
                        boolean result = backtrack(board);
                        if(result) {
                            return true;
                        }
                        board[i][j] = '.';
                    }
                }
                // 九个是尝试完了还是不行,就返回 false
                return false;
            }
        }
        // 遍历完没有返回 false,说明找到合适棋盘位置了
        return true;
    }

    public boolean isValid(int row, int col, char k, char[][] board) {
        // 判断行是否重复
        for(int i = 0; i < 9; i++) {
            if(board[row][i] == k) {
                return false;
            }
        }
        // 判断列是否重复
        for(int j = 0; j < 9; j++) {
            if(board[j][col] == k) {
                return false;
            }
        }
        // 判断九宫格是否重复
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++) { // 判断9方格里是否重复
            for (int j = startCol; j < startCol + 3; j++) {
                if (board[i][j] == k) {
                    return false;
                }
            }
        }
        return true;
    }
}

到了这里,关于37. 解数独 - 力扣(LeetCode)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 算法训练day37|贪心算法 part06(LeetCode738.单调递增的数字)

    题目链接🔥🔥 给定一个非负整数 N,找出小于或等于 N 的最大的整数,同时这个整数需要满足其各个位数上的数字是单调递增。 (当且仅当每个相邻位数上的数字 x 和 y 满足 x = y 时,我们称这个整数是单调递增的。) 示例 1: 输入: N = 10 输出: 9 示例 2: 输入: N = 1234 输出:

    2024年02月09日
    浏览(35)
  • LeetCode037之解数独(相关话题:回溯法)

    编写一个程序,通过填充空格来解决数独问题。 数独的解法需  遵循如下规则 : 数字  1-9  在每一行只能出现一次。 数字  1-9  在每一列只能出现一次。 数字  1-9  在每一个以粗实线分隔的  3x3  宫内只能出现一次。(请参考示例图) 数独部分空格内已填入了数字,空白

    2023年04月17日
    浏览(28)
  • 力扣(LeetCode)算法_C++—— 快乐数

    编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」 定义为: 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。 如果这个过程 结果为 1,那么这个数就是快乐数。 如果 n 是

    2024年02月09日
    浏览(40)
  • 算法学习——LeetCode力扣回溯篇2

    40. 组合总和 II - 力扣(LeetCode) 描述 给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意:解集不能包含重复的组合。 示例 示例 1: 输入: candidates = [10,1,2,7

    2024年02月20日
    浏览(36)
  • 算法学习——LeetCode力扣字符串篇

    344. 反转字符串 - 力扣(LeetCode) 描述 编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。 不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。 示例 示例 1: 输入:s = [“h”,“e”,“l”

    2024年02月20日
    浏览(44)
  • 刷力扣 LeetCode 算法题需要充值会员吗?

    大家好,我是『负雪明烛』。 在过去的这些年里,我的一项业余爱好就是写作算法题解。如今写了上千篇题解了! 在 CSDN 上,我的博客获得了 200 多万的阅读。 在力扣中国题解区,我也获得了180 万的阅读。 当然,这些多归功于粉丝们的关注与支持!!谢谢各位!! 我一直

    2024年02月09日
    浏览(51)
  • 力扣(LeetCode)算法_C++—— 存在重复元素

    给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ,返回 true ;如果数组中每个元素互不相同,返回 false 。 示例 1: 输入:nums = [1,2,3,1] 输出:true 示例 2: 输入:nums = [1,2,3,4] 输出:false 示例 3: 输入:nums = [1,1,1,3,3,4,3,2,4,2] 输出:true 提示: 1 = nums.length = 105 -1

    2024年02月09日
    浏览(46)
  • LeetCode面试算法-力扣 88. 合并两个有序数组

    88. 合并两个有序数组 题目描述     给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。 注意: 最终,合并后数组不应由函数返回,而是存储

    2024年02月10日
    浏览(49)
  • 【LeetCode题目详解】第八章 贪心算法 part06 738.单调递增的数字 968.监控二叉树 (day37补)

    当且仅当每个相邻位数上的数字  x  和  y  满足  x = y  时,我们称这个整数是 单调递增 的。 给定一个整数 n ,返回 小于或等于 n 的最大数字,且数字呈 单调递增 。 示例 1: 示例 2: 示例 3: 提示: 0 = n = 109 # 暴力解法 题意很简单,那么首先想的就是暴力解法了,来我替大家

    2024年02月10日
    浏览(41)
  • 力扣(LeetCode)算法_C++—— 两个数组的交集

    给定两个数组 nums1 和 nums2 ,返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。 示例 1: 输入:nums1 = [1,2,2,1], nums2 = [2,2] 输出:[2] 示例 2: 输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出:[9,4] 解释:[4,9] 也是可通过的

    2024年02月09日
    浏览(35)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包