ARTS 打卡第 14 周

关注
发布于: 2020 年 08 月 30 日
ARTS简介Algorithm 是一道算法题，Review 是读一篇英文文章，Technique/Tips 是分享一个小技术，Share 是分享一个观点。
Algorithm力扣（LeetCode）37. 解数独
编写一个程序，通过已填充的空格来解决数独问题。。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 ‘.’ 表示。
解题思路：
解数独比验证数据复杂，第一想法是使用回溯法，在每次测试之前保留之前的状态
那么首先对每个单元格进行统计，统计是否是固定的数字
对统计好的每个单元格统计候选值：
找到第一个空的单元格，保存状态
当单元格数字全部找到就是解决
public class SudokuSolver {
    private static final char DOT = '.';
    static List<Integer> raw = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9);
    static final int SKD_ROW_LIMIT = 9;
    static final int SKD_COL_LIMIT = 9;
    static final int SKD_BLOCK_ROW_LIMIT = 3;
    static final int SKD_BLOCK_COL_LIMIT = 3;
    static final int SKD_BLOCK_LIMIT = 9;
    static final int SKD_CELL_COUNT = SKD_ROW_LIMIT * SKD_COL_LIMIT;
    static final int SKD_BLOCK_COUNT = SKD_BLOCK_ROW_LIMIT * SKD_BLOCK_COL_LIMIT;
    static class SoduCell implements Cloneable {
        int num;
        boolean fixed;
        Set<Integer> candidators;
        @Override
        protected Object clone() throws CloneNotSupportedException {
            SoduCell newCell = new SoduCell();
            newCell.num = num;
            newCell.fixed = fixed;
            newCell.candidators = new HashSet<>(candidators);
            return newCell;
        }
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append("number:");
            sb.append(num);
            sb.append(",fixed:");
            sb.append(fixed);
            sb.append(",candidators:");
            sb.append(candidators);
            return sb.toString();
        }
    }
    static class SoduGame {
        SoduCell[][] cells = new SoduCell[SKD_ROW_LIMIT][SKD_ROW_LIMIT];
        int fixedCount;
    }
    static void initSoduGame(SoduGame soduGame, char[][] board) {
        //初始化每个单元格
        for (int i = 0; i < SKD_ROW_LIMIT; i++) {
            for (int j = 0; j < SKD_COL_LIMIT; j++) {
                char c = board[i][j];
                SoduCell soduCell = new SoduCell();
                if (DOT != c) {
                    soduCell.num = c - '0';
                    soduCell.fixed = true;
                    soduCell.candidators = new HashSet<Integer>();
                } else {
                    soduCell.candidators = new HashSet<Integer>(raw);
                }
                if (soduCell.fixed) {
                    soduGame.fixedCount++;
                }
                soduGame.cells[i][j] = soduCell;
            }
        }
        //根据初始化的数字设置每个单元格候选数字
        for (int row = 0; row < SKD_ROW_LIMIT; row++) {
            for (int col = 0; col < SKD_COL_LIMIT; col++) {
                SoduCell soduCell = soduGame.cells[row][col];
                if (soduCell.fixed) {
                    //在对应的行排除数字
                    singleRowExclusive(soduGame, row, soduGame.cells[row][col].num);
                    //在对应的列排除数字
                    singleColumnExclusive(soduGame, col, soduGame.cells[row][col].num);
                    //在对应的3x3九宫格排除数字
                    int block = roundBlockNumber(row, col);
                    singleBlockExclusive(soduGame, block, soduGame.cells[row][col].num);
                }
            }
        }
        //printSoduDetail(soduGame);
    }
    private static boolean singleRowExclusive(SoduGame soduGame, int row, int num) {
        for (int i = 0; i < SKD_COL_LIMIT; i++) {
            if (isCellHasCandidator(soduGame.cells[row][i], num)) {
                if (!removeCellCandidator(soduGame, row, i, num)) {
                    return false;
                }
            }
        }
        return true;
    }
    static boolean singleColumnExclusive(SoduGame soduGame, int col, int num) {
        for (int i = 0; i < SKD_ROW_LIMIT; i++) {
            if (isCellHasCandidator(soduGame.cells[i][col], num)) {
                if (!removeCellCandidator(soduGame, i, col, num)) {
                    return false;
                }
            }
        }
        return true;
    }
    /**
     * 计算行列所在的3x3九宫格序号
     *
     * @param row
     * @param col
     * @return
     */
    static int roundBlockNumber(int row, int col) {
        return (row / SKD_BLOCK_COL_LIMIT) * SKD_BLOCK_ROW_LIMIT + (col / SKD_BLOCK_COL_LIMIT);
    }
    static boolean singleBlockExclusive(SoduGame soduGame, int block, int num) {
        int r = (block / SKD_BLOCK_ROW_LIMIT) * SKD_BLOCK_COL_LIMIT;
        int c = (block % SKD_BLOCK_ROW_LIMIT) * SKD_BLOCK_ROW_LIMIT;
        for (int i = 0; i < SKD_BLOCK_LIMIT; ++i) {
            int row = r + i / SKD_BLOCK_ROW_LIMIT;
            int col = c + i % SKD_BLOCK_ROW_LIMIT;
            if (isCellHasCandidator(soduGame.cells[row][col], num)) {
                if (!removeCellCandidator(soduGame, row, col, num)) {
                    return false;
                }
            }
        }
        return true;
    }
    private static boolean removeCellCandidator(SoduGame soduGame, int row, int col, int num) {
        if (!soduGame.cells[row][col].fixed) {
            soduGame.cells[row][col].candidators.remove(num);
            if (soduGame.cells[row][col].candidators.size() == 1) {
                if (!singlesCandidature(soduGame, row, col)) {
                    return false;
                }
            }
        }
        return true;
    }
    /**
     * 该位置只有一个候选者
     *
     * @param soduGame
     * @param row
     * @param col
     * @return
     */
    private static boolean singlesCandidature(SoduGame soduGame, int row, int col) {
        if (!switchCellToFixedSC(soduGame, row, col)) {
            return false;
        }
        if (!singleRowExclusive(soduGame, row, soduGame.cells[row][col].num)) {
            return false;
        }
        if (!singleColumnExclusive(soduGame, col, soduGame.cells[row][col].num)) {
            return false;
        }
        int block = roundBlockNumber(row, col);
        if (!singleBlockExclusive(soduGame, block, soduGame.cells[row][col].num)) {
            return false;
        }
        soduGame.fixedCount++;
        return true;
    }
    private static boolean switchCellToFixedSC(SoduGame soduGame, int row, int col) {
        SoduCell cell = soduGame.cells[row][col];
        int num = cell.candidators.iterator().next();
        if (checkValidCandidator(soduGame, row, col, num)) {
            cell.num = num;
            cell.fixed = true;
            cell.candidators.clear();
            return true;
        }
        return false;
    }
    private static boolean isCellHasCandidator(SoduCell soduCell, int num) {
        // 没有被选中然后判断候选者中是否有该数字
        return !soduCell.fixed && soduCell.candidators.contains(num);
    }
    static void printSodu(SoduGame soduGame) {
        for (int row = 0; row < SKD_ROW_LIMIT; row++) {
            for (int col = 0; col < SKD_COL_LIMIT; col++) {
                System.out.print(soduGame.cells[row][col].num + " ");
            }
            System.out.println();
        }
    }
    static void printSoduDetail(SoduGame soduGame) {
        for (int row = 0; row < SKD_ROW_LIMIT; row++) {
            for (int col = 0; col < SKD_COL_LIMIT; col++) {
                System.out.print(soduGame.cells[row][col] + " ");
            }
            System.out.println();
        }
    }
    /**
     *
     * @param soduGame
     *            sodu游戏
     * @param sp
     *            要查找的单元格
     */
    static void findSolution(SoduGame soduGame, int sp, char[][] board) {
        if (SKD_CELL_COUNT == soduGame.fixedCount) {
            for (int i = 0; i < SKD_ROW_LIMIT; i++) {
                for (int j = 0; j < SKD_COL_LIMIT; j++) {
                    SoduCell soduCell = soduGame.cells[i][j];
                    board[i][j] = (char) (soduCell.num + '0');
                }
            }
            return;
        }
        int row = sp / SKD_COL_LIMIT;
        int col = sp % SKD_COL_LIMIT;
        // 跳过已经找到的单元格
        while ((sp < SKD_CELL_COUNT) && soduGame.cells[row][col].fixed) {
            sp++;
            row = sp / SKD_COL_LIMIT;
            col = sp % SKD_COL_LIMIT;
        }
        if (sp < SKD_CELL_COUNT) {
            SoduCell curCell = soduGame.cells[row][col];
            SoduGame newState = new SoduGame();
            Iterator<Integer> itr = curCell.candidators.iterator();
            while (itr.hasNext()) {
                if (switchToNextState(soduGame, row, col, itr.next(), newState)) {
                    findSolution(newState, sp++, board);
                }
            }
        }
    }
    /**
     * 选择一个数字进行尝试
     *
     * @param soduGame
     * @param row
     * @param col
     * @param num
     * @param newState
     * @return true 该数字满足条件 false 该数字不满足条件
     */
    private static boolean switchToNextState(SoduGame soduGame, int row, int col, Integer num,
            SoduGame newState) {
        //保存状态
        copyState(soduGame, newState);
        return setCandidatorTofixed(newState, row, col, num);
    }
    /**
     * 对该数字进行尝试
     *
     * @param soduGame
     * @param row
     * @param col
     * @param num
     * @return
     */
    private static boolean setCandidatorTofixed(SoduGame soduGame, int row, int col, Integer num) {
        // 将其设置为选中的状态
        if (!switchCellToFixed(soduGame, row, col, num)) {
            return false;
        }
        // 排除行
        if (!singleRowExclusive(soduGame, row, soduGame.cells[row][col].num)) {
            return false;
        }
        // 排除列
        if (!singleColumnExclusive(soduGame, col, soduGame.cells[row][col].num)) {
            return false;
        }
        // 排除九宫格
        int block = roundBlockNumber(row, col);
        if (!singleBlockExclusive(soduGame, block, soduGame.cells[row][col].num)) {
            return false;
        }
        soduGame.fixedCount++;
        return true;
    }
    private static boolean switchCellToFixed(SoduGame soduGame, int row, int col, Integer num) {
        SoduCell cell = soduGame.cells[row][col];
        if (checkValidCandidator(soduGame, row, col, num)) {
            cell.num = num;
            cell.fixed = true;
            cell.candidators.clear();
            return true;
        }
        return false;
    }
    /**
     * 判断是否已经有相同的数字
     *
     * @param soduGame
     * @param row
     * @param col
     * @param num
     * @return
     */
    private static boolean checkValidCandidator(SoduGame soduGame, int row, int col, Integer num) {
        for (int i = 0; i < SKD_COL_LIMIT; i++) {
            if ((i != col) && (soduGame.cells[row][i].num == num)) {
                return false;
            }
        }
        for (int j = 0; j < SKD_ROW_LIMIT; j++) {
            if ((j != row) && (soduGame.cells[j][col].num == num)) {
                return false;
            }
        }
        int rs = (row / SKD_BLOCK_ROW_LIMIT) * SKD_BLOCK_ROW_LIMIT;
        int cs = (col / SKD_BLOCK_COL_LIMIT) * SKD_BLOCK_COL_LIMIT;
        for (int r = rs; r < SKD_BLOCK_COL_LIMIT; r++) {
            for (int c = cs; c < SKD_BLOCK_ROW_LIMIT; c++) {
                if (!((r == row) && (c == col)) && (soduGame.cells[r][c].num == num)) {
                    return false;
                }
            }
        }
        return true;
    }
    static void copyState(SoduGame soduGame, SoduGame newState) {
        newState.fixedCount = soduGame.fixedCount;
        try {
            for (int i = 0; i < SKD_CELL_COUNT; i++) {
                int row = i / SKD_COL_LIMIT;
                int col = i % SKD_COL_LIMIT;
                newState.cells[row][col] = (SoduCell) soduGame.cells[row][col].clone();
            }
        } catch (CloneNotSupportedException e) {
        }
    }
    public void solveSudoku(char[][] board) {
        SoduGame soduGame = new SoduGame();
        initSoduGame(soduGame, board);
        findSolution(soduGame, 0, board);
    }
}
ps:参考资料《算法的乐趣》
Review学习-微服务架构模式系列，网站地址是：https://microservices.io
微服务架构-Pattern: Pattern: Transactional outbox
这篇文章的主要介绍了微服务架构下如何进行发布数据更新：应用程序事件
问题：如何可靠/自动地更新数据库并发布消息/事件？
要求：不能使用2段式提交
解决方法，应用程序在本地事务中将时间插入到事件表，另一个独立进程拉取事件信息并发送到消息代理
好处：
服务发布高层次的领域事件
不需要2段式提交
不足
可能忘记发布事件
ps:《微服务架构设计模式》
Tips记录我对于Linux的学习，文件相关的命令：
ps:”~” 表示为 home 目录，”.” 则是表示目前所在的目录，”..” 则表示当前目录的上一层目录
-h 用人类可读的格式展示(G（千兆字节），M（兆字节）,K（千字节）)，大部分命令有这个参数
统计文件中信息wc 用于计算字数，如果没有给出文件名，则从标准输入读取。wc同时也给出所有指定文件的总统计数。字是由空格字符区分开的最大字符串。
格式： wc [选项]… [文件列表]
选项：
-c, –bytes 输出字节统计数
-m, –chars 输出字符统计数
-l, –lines 输出换行符统计数
-w, –words 输出单词统计数
1.
2.wc add.c
3.11  23 149 add.c # 行数为11、单词数23、字节数149
4.
5.wc add.c add.s
6.  11   23  149 add.c
7.  56  122  895 add.s
8.  67  145 1044 总用量
9.
Share分享最近对计算机基础的复习，这次分享的是程序的机器级表示 - 控制，可能会有不足之处，之后会根据理解继续修改。
﻿
发布于: 2020 年 08 月 30 日阅读数: 48
原文链接:【http://xie.infoq.cn/article/dab8e48e8fbc26ded4b0c53a6】。
引花眠

关注
还未添加个人签名 2018.06.11 加入
还未添加个人简介
发布
暂无评论
创作场景

ARTS 打卡 第 14 周

ARTS简介

Algorithm

Review

Tips

统计文件中信息

Share

引花眠

评论

ARTS 打卡第 14 周
