📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 1569| 回复: 3
跳转到指定楼层
上一主题 下一主题
收起左侧

问一个LeetCode Sudoku Solver这道题

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
本帖最后由 leeshell 于 2015-4-1 01:40 编辑

这道题我发现大部分的解决方法都是加一个isValid函数,来判断当前数字是否合法。
比如:
但是我想这样的话就得每次遍历当前列,当前行,当前3×3方格。所以还不如设置hashset数组来记录,然后就可以直接通过hashSet判断是否合法了。
而且他们都是每次递归只检查当前格,我想,如果可以一直前进,前进到是'.'的格,再进入下一次递归,就可以减少递归次数了呀。
但是,写出来代码之后一直不对。。。调了半天也没看出哪里不对。。。。。真是。。。。
而且错误情况也很奇葩,前面都对了,最后一行死活不对。。。。。。

Input:
["..9748...","7........",".2.1.9...","..7...24.",".64.1.59.",".98...3..","...8.3.2.","........6","...2759.."]
Output:
["519748632","783652419","426139875","357986241","264317598","198524367","975863124","832491756","...2759.3"]
Expected:
["519748632","783652419","426139875","357986241","264317598","198524367","975863124","832491756","641275983"]


调试之后发现,始终进入不到最后一行前面几个数,但是因为这个程序实在递归太多,到最后也没看出为啥会出现这种情况。。。。
大家能帮我看看哪里出问题了吗?
多谢!

public class Solution {

    public void solveSudoku(char[][] board) {
        HashSet<Integer>[] rows = new HashSet[9];
        for(int i=0; i<9; i++) rows = new HashSet<Integer>();

        HashSet<Integer>[] cols = new HashSet[9];
        for(int i=0; i<9; i++) cols[i] = new HashSet<Integer>();

        HashSet<Integer>[] squares = new HashSet[9];
        for(int i=0; i<9; i++) squares[i] = new HashSet<Integer>();

        for(int i=0; i<9; i++){
            for(int j=0; j<9; j++){
                if(Character.isDigit(board[i][j])){
                    rows[i].add(board[i][j]-'0');
                    cols[j].add(board[i][j]-'0');
                    squares[(i/3)*3+(j/3)].add(board[i][j] - '0');
                }
            }
        }

        helper(board,rows, cols, squares, 0, 0);

    }

    public boolean helper(char[][] board, HashSet<Integer>[] rows, HashSet<Integer>[] cols, HashSet<Integer>[] squares, int row, int col){
        if(row >= 9) return true;
        for(int i=row; i<9; i++){
            for(int j=col; j<9; j++){
                if(Character.isDigit(board[i][j])){
                    continue;
                }
                else{
                    for(int k=1; k<=9; k++){
                        if(rows[i].contains(k) || cols[j].contains(k) || squares[(i/3)*3+(j/3)].contains(k)) continue;
                        else{
                            rows[i].add(k);
                            cols[j].add(k);
                            squares[(i/3)*3+(j/3)].add(k);
                            board[i][j] = (char)('0'+k);
                            int nextrow;
                            int nextcol;
                            if(j>=8){
                                nextrow = i+1;
                                nextcol = 0;
                            }
                            else{
                                nextrow = i;
                                nextcol = j+1;
                            }
                            if(helper(board, rows, cols, squares, nextrow, nextcol)) return true;
                            rows[i].remove(k);
                            cols[j].remove(k);
                            squares[(i/3)*3+(j/3)].remove(k);
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
}
[i][i][i][i][i][i][i][i][i][i][i][i][i][i][i][i][i][i][i][i][i][i][i][i][i][i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]

上一篇:【第四轮】3.30 -4.5 Career Cup 1.7
下一篇:leetcode题解 有java 版本吗?
全局:
调试了一下终于知道你的问题出在哪里了

nextrow = 7,nextcol = 8的时候,会调用helper
"........6"这一行比较巧,刚好最后一个是digit,所以Character.isDigit返回了true,会continue到下一个循环
此时i = 7 j = 8, j++之后j = 9,内层循环结束,i++
那么i = 8,j=col,col=8,所以j也等于8,最后一行直接被跳过

这题用HashSet<Integer>思路是对的,但实在是有点浪费空间
可以参考我Github上用位操作的答案:https://github.com/FreeTymeKiyan ... d/SudokuSolver.java

这个repo是三刷之后总结的,其他题目也可以借鉴。
回复

使用道具 举报

🔗
 楼主| leeshell 2015-4-2 22:28:48 | 只看该作者
全局:
Freetymekiyan 发表于 2015-4-1 04:20
调试了一下终于知道你的问题出在哪里了

nextrow = 7,nextcol = 8的时候,会调用helper

太谢谢你啦!

用位操作确实很省空间 只是我位操作不是很熟练,以后我多练习下哈

谢谢你提供的repo!
回复

使用道具 举报

全局:
^_^不客气,有问题请尽管问!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表