题解 | #数独#

数独

https://www.nowcoder.com/practice/5e6c424b82224b85b64f28fd85761280

import java.util.* ;

public class Solution {
    static class Position {
        int x;
        int y;

        Position(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public void solveSudoku(char[][] board) {
        valid(0, getPositionList(board), board);
    }

    // 从待填列表的index位置开始,填充待填列表,如果数独有解,返回true
    private boolean valid(int index, List<Position> positionList, char[][] board) {
        Position curPosition = positionList.get(index);
        int x = curPosition.x;
        int y = curPosition.y;
        List<Character> candinateList = getCandinateList(board, x, y);
        if (candinateList.size() == 0) {
            return false;
        }
        if (index == positionList.size() - 1) {
            if (candinateList.size() == 1) {
                board[x][y] = candinateList.get(0);
                return true;
            } else {
                return false;
            }
        }
        for (Character candinate : candinateList) {
            board[x][y] = candinate;
            boolean valid = valid(index + 1, positionList, board);
            if (valid) {
                return true;
            }
        }
        board[x][y] = '.';
        return false;
    }

    // 获取待填值的坐标列表
    private List<Position> getPositionList(char[][] board) {
        List<Position> positionList = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == '.') {
                    positionList.add(new Position(i, j));
                }
            }
        }
        return positionList;
    }

    // 获取当前坐标的候选值
    private List<Character> getCandinateList(char[][] board, int x, int y) {
        // 横向检查、纵向检查
        Set<Character> candinateSet = new HashSet(Arrays.asList('1', '2', '3', '4', '5', '6', '7', '8', '9'));
        for (int i = 0; i < board[0].length; i++) {
            candinateSet.remove(board[x][i]);
            candinateSet.remove(board[i][y]);
        }
        //九宫格检查
        int leftStart = y / 3 * 3;
        int upStart = x / 3 * 3;
        for (int i = upStart; i < upStart + 3; i++) {
            for (int j = leftStart; j < leftStart + 3; j++) {
                candinateSet.remove(board[i][j]);
            }
        }
        return new ArrayList<>(candinateSet);
    }

}

全部评论

相关推荐

小浪_Coding:找硬件测试,也可兼顾软测欧, 简历还可以的 ,注意排版,项目写的有条理一点, 然后个人技能多加点, 润色好简历之后就开始沟通海投了,深圳,东莞这边做硬件相关的公司还不少, 医疗类,仪器类的都可以尝试
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 12:04
毕业生招你惹你了,问一个发薪日来一句别看网上乱七八糟的你看哪个工作没有固定发薪日扭头就取消了面试就问了一句公司都是这个态度吗还搞上人身攻击了...
程序员小白条:呃呃呃,都还没面试,我都不会问这么细,何况通不通过,去不去都另说,你没实力和学历的话,在外面就这样,说实话没直接已读不回就不错了,浪费时间基本上
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务