ARTS打卡：第十二周

每周完成一个ARTS：

Algorithm：每周至少做一个 leetcode 的算法题

Review：阅读并点评至少一篇英文技术文章

Tip：学习至少一个技术技巧

Share：分享一篇有观点和思考的技术文章

Algorithm

36. Valid Sudoku(Medium)

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition.

Each column must contain the digits 1-9 without repetition.

Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

A partially filled sudoku which is valid.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

Example 1:
Input:
[
[“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”]
]
Output: true

Example 2:
Input:
[
[“8”,”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”]
]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8’s in the top left 3x3 sub-box, it is invalid.

Note:

A Sudoku board (partially filled) could be valid but is not necessarily solvable.

Only the filled cells need to be validated according to the mentioned rules.

The given board contain only digits 1-9 and the character ‘.’.

The given board size is always 9x9.

@DevDocsleetcode.com/problems/valid-sudoku

题意如下：
判断 9×9 的数独板是否有效，只需要根据以下规则验证已填充的单元格即可：

每行必须包含数字1-9而不重复。
每列必须包含数字1-9而不重复。
网格的9个3x3子框中的每一个必须包含数字1-9而不重复。
数独板可以部分填充，其中空单元格填充字符'.'。

注意：

数独板(部分填充)可能是有效的，但不一定是可解的。
只需要根据上述规则验证填充的单元格。
给定的数独板只包含数字1-9和字符'.'。
给定的数独板大小一直都是 9×9 的。

解题思路：
按照题目说的规则和注意事项来看，解题的核心思路在于如何快速的判断出一个字符在当前行且当前列且当前所处的 3×3 小格内有无重复。
那么我们可以联想到借助哈希表的特性，来快速判断字符有无重复。

代码实现如下：

/**
 * 数独的特性：
 * 1. Each row must contain the digits 1-9 without repetition.
 * 2. Each column must contain the digits 1-9 without repetition.
 * 3. Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.
 * <p>
 * 所以解决这道题的核心思路在于：如何快速的判断出一个字符在当前行且当前列且当前所处的 3×3 小格内有无重复
 * <p>
 * 方法：借助哈希表（Set）的特性，快速判断字符有无重复
 *
 * @param board
 * @return
 */
public boolean isValidSudoku(char[][] board) {
    // 这里采用 Set 集合，
    // 利用 Set 集合的特性：
    // 1. 集合内元素不重复
    // 2. Set.add(a)：如果元素 a 不存在，加入到集合中，并返回 true，反之，则返回 false 且不加入到集合中
    Set<String> seen = new HashSet<>();
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            char number = board[i][j];
            // 依照题意，数独的空单元格可以用 '.' 来填充，所以这里要忽略 '.'
            if (number != '.') {
                // 这里为了便于阅读与理解，我们可以将 board[i][j] 的值进行处理
                // 假设 board[0][0] = 1，那么 "1 in row 0" 这个字符串值就可以表示 board[0][0] 在当前行的值；
                // "1 in column 0" 这个字符串值就可以表示 board[0][0] 在当前列的值；
                // "1 in block 0-0" 这个字符串值就可以表示 board[0][0] 在当前 3×3 小格内的值。
                // 这样就不需要借助额外的 set 集合来区分 行、列以及 3×3 的小格了。
                // 当然也可以使用三个 set 集合，分别进行区分，不过我觉得现在的实现方法，可读性更高，代码更简短。
                if (!seen.add(number + " in row " + i)
                        || !seen.add(number + " in column " + j)
                        || !seen.add(number + " in block " + i / 3 + "-" + j / 3)) {
                    return false;
                }
            }
        }
    }
    return true;
}

结果：
Runtime: 4 ms, faster than 59.98% of Java online submissions for Valid Sudoku.
Memory Usage: 43.3 MB, less than 94.33% of Java online submissions for Valid Sudoku.

复杂度分析：
时间复杂度：O(1)，数独的总格数固定是81格，也就是循环遍历次数是81次，是常数阶。
空间复杂度：O(1)，额外使用的空间也是81，是常数阶。

Review

本周阅读的是：6 Science-Backed Strategies to Avoid Choking Under Pressure（6个有科学依据的策略来避免在压力下窒息）。

作者在文中说明了在压力下，会产生焦虑，这个过程既是生理上的，也是心理上的，在高风险的情况下，会引起神经反应，例如注意力分散、记忆力丧失和运动功能丧失，所有这些都会影响自身表现。

为此，作者在文中列举了5个有科学依据的策略来避免在压力下窒息：

Don’t think too hard.（别想的太难）
Practice under pressure.（在压力下练习）
Pretend like you’ve already won.（假装你已经赢了）
Tell yourself that you’re in control.（告诉自己一切尽在掌握中）
Give yourself a pep talk.（自我激励）

感兴趣的小伙伴们，可以查看原文获取更多详情哟~（前提是要有梯子(:з」∠)）。

ps: 虽然作者的标题写的是有6个策略，但我反复数了下，就只有5个策略(:з」∠)。

Tip

本周分享：Jenkins 子节点构建配置

本周分享梁大在知识星球发的一个帖子，写的真好！
服务端思维
星球是付费，感兴趣的小伙伴们自行斟酌哈~