CodingTour —
ARTS #103

Algorithm

本周选择的算法题是：Valid Sudoku。

规则

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

  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 nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

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.

Example 1:

img

Input: board = 
[["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: board = 
[["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.

Constraints:

  • board.length == 9
  • board[i].length == 9
  • board[i][j] is a digit or '.'.

Solution

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        table = set()
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == '.': continue

                row_key = f'{i}_{board[i][j]}'
                column_key = f'{j}-{board[i][j]}'
                grid_key = f'{(i // 3) * 3 + (j // 3)}:{board[i][j]}'
                if row_key in table or column_key in table or grid_key in table:
                    return False

                table.add(row_key)
                table.add(column_key)
                table.add(grid_key)
        return True

Review

Web-Development is running into the wrong direction

这篇文章的作者是后端、客户端的背景，对前端的看法很激进，老实讲我不认为他说的是对的，因为几乎每一天都有对应的解决方案，如 - 1. 更新依赖 2. 阅读文档或源码 3. …，不过对于从客户端转向前端的同学来说确实容易面对相同的问题，从而产生偏见，或者和客户端的技术迭代相对“缓慢”有关系。

Tip

在本周的专场面试中，学到了一个考察 HTTP 知识的好问题：如何设计一个删除文章的接口。

Share

分享一份应聘建议。