一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 441|回复: 3
收起左侧

[编程题] 问一个LeetCode Sudoku Solver这道题

[复制链接] |试试Instant~ |关注本帖
leeshell 发表于 2015-4-1 01:38:38 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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 = new HashSet<Integer>();

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

        for(int i=0; i<9; i++){
            for(int j=0; j<9; j++){
                if(Character.isDigit(board[j])){
                    rows.add(board[j]-'0');
                    cols[j].add(board[j]-'0');
                    squares[(i/3)*3+(j/3)].add(board[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[j])){
                    continue;
                }
                else{
                    for(int k=1; k<=9; k++){
                        if(rows.contains(k) || cols[j].contains(k) || squares[(i/3)*3+(j/3)].contains(k)) continue;
                        else{
                            rows.add(k);
                            cols[j].add(k);
                            squares[(i/3)*3+(j/3)].add(k);
                            board[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.remove(k);
                            cols[j].remove(k);
                            squares[(i/3)*3+(j/3)].remove(k);
                            board[j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
}
Freetymekiyan 发表于 2015-4-1 04:20:29 | 显示全部楼层
调试了一下终于知道你的问题出在哪里了

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!
回复 支持 反对

使用道具 举报

Freetymekiyan 发表于 2015-4-3 08:37:54 | 显示全部楼层
^_^不客气,有问题请尽管问!
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 10:44

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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