首页 > 编程语言 >#yyds干货盘点# LeetCode程序员面试金典:解数独

#yyds干货盘点# LeetCode程序员面试金典:解数独

时间:2023-04-26 22:06:11浏览次数:42  
标签:yyds digit int 金典 private column boolean board LeetCode

题目:

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

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

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

输出:[["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"]]

解释:输入的数独如上图所示,唯一有效的解决方案如下所示:

代码实现:

class Solution {
    private boolean[][] line = new boolean[9][9];
    private boolean[][] column = new boolean[9][9];
    private boolean[][][] block = new boolean[3][3][9];
    private boolean valid = false;
    private List<int[]> spaces = new ArrayList<int[]>();

    public void solveSudoku(char[][] board) {
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') {
                    spaces.add(new int[]{i, j});
                } else {
                    int digit = board[i][j] - '0' - 1;
                    line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;
                }
            }
        }

        dfs(board, 0);
    }

    public void dfs(char[][] board, int pos) {
        if (pos == spaces.size()) {
            valid = true;
            return;
        }

        int[] space = spaces.get(pos);
        int i = space[0], j = space[1];
        for (int digit = 0; digit < 9 && !valid; ++digit) {
            if (!line[i][digit] && !column[j][digit] && !block[i / 3][j / 3][digit]) {
                line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;
                board[i][j] = (char) (digit + '0' + 1);
                dfs(board, pos + 1);
                line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = false;
            }
        }
    }
}

标签:yyds,digit,int,金典,private,column,boolean,board,LeetCode
From: https://blog.51cto.com/u_13321676/6228986

相关文章

  • #yyds干货盘点# LeetCode面试题:合并两个有序数组
    1.简述:给你两个按非递减顺序排列的整数数组 nums1和nums2,另有两个整数m和n,分别表示nums1和nums2中的元素数目。请你合并nums2到nums1中,使合并后的数组同样按非递减顺序排列。注意:最终,合并后数组不应由函数返回,而是存储在数组nums1中。为了应对这种情况,nums1......
  • # yyds干货盘点 # 我要提取text4文本中的邮箱号 正则应该怎么写?
    大家好,我是皮皮。一、前言前几天在Python白银交流群【膨胀西瓜汁】问了一个Python正则表达式的问题,这里拿出来给大家分享下。代码如下:二、实现过程这里【甯同学】给了一个思路,如下图所示:直接使用字符串+列表推导式搞定了,太强了!不过粉丝正好在学习正则表达式,所以还是希望能够用正则......
  • 【哈希表】LeetCode 767. 重构字符串
    题目链接767.重构字符串思路先用哈希表统计出出现次数最多的字符,如果这个次数大于一半,说明这个字符总会挨在一起,直接返回""。如果不超过一半,则先把字符填在偶数位置(先填出现次数最多的字符),偶数位置填满了再填奇数位置。代码classSolution{publicStringreorganize......
  • 【DP】LeetCode 740. 删除并获得点数
    题目链接740.删除并获得点数思路分析动态规划题目的时候只需要考虑最后一个阶段,因为所有的阶段转化都是相同的,考虑最后一个阶段容易发现规律在数组的动态规划问题中,一般dp[i]都是表示以nums以前i个元素组成(即nums[i-1])的状态;dp[i][j]分别表示以nums1前i个元素(......
  • LeetCode 152. 乘积最大子数组
    20230426顺利通过原题解题目约束题解classSolution{public:intmaxProduct(vector<int>&nums){intmaxF=nums[0],minF=nums[0],ans=nums[0];for(inti=1;i<nums.size();++i){intmx=maxF,mn=minF;......
  • [LeetCode] 2418. Sort the People
    Youaregivenanarrayofstrings names,andanarray heights thatconsistsof distinct positiveintegers.Botharraysareoflength n.Foreachindex i, names[i] and heights[i] denotethenameandheightofthe ith person.Return names sorted......
  • 【LeetCode动态规划#13】买卖股票含冷冻期(状态众多,比较繁琐)、含手续费
    最佳买卖股票时机含冷冻期力扣题目链接(opensnewwindow)给定一个整数数组,其中第i个元素代表了第i天的股票价格。设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):你不能同时参与多笔交易(你必须在再次购买前出售掉之前......
  • LeetCode 1643. 第 K 条最小指令
    康托展开一开始无脑枚举全排列,果断超时,还是得看看如果降低计算量。题目destination=[2,3],相当于2个V,3个H,输出全排列去重后的对应位置字典序列内容。忽略去重则问题为全排列,所有可能为:\[(\sumdestination)!=(2+3)!=5!\]k恰好为康托展开结果+1,直接逆向......
  • leetcode调研version0
     这是我第一次发博客,所以许多功能还不太会使用。前几次的随笔既当作记录,也当作自己的练习。 最近想要刷leetcode,纠结用哪种语言(我自己学过c/c++,python,fortran,Java),所以前期做了一些调研,在此记录一下。 c语言: 网址:https://github.com/begeekmyfriend/leetcode ......
  • leetcode 607 銷售員
    銷售員 selects.`name`fromsalespersonsleftjoinordersoons.sales_id=o.sales_idleftjoincompanycono.com_id=c.com_idandc.name='RED'groupbys.sales_idhavingcount(c.`name`)=0 ===selects.`name`fromsalespersonswheres.sa......