Study Plan For Algorithms - Part18

1. 搜索插入位置
题目链接：https://leetcode.cn/problems/search-insert-position/
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1

        while left <= right:
            mid = (left + right) // 2

            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return left

2. 有效的数独
题目链接：https://leetcode.cn/problems/valid-sudoku/
请判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：

• 一个有效的数独（部分已被填充）不一定是可解的。
• 只需要根据以上规则，验证已经填入的数字是否有效即可。
• 空白格用 '.' 表示。

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        def is_valid_row(row):
            seen = set()
            for num in row:
                if num!= '.':
                    if num in seen:
                        return False
                    seen.add(num)
            return True

        def is_valid_col(col):
            seen = set()
            for row in board:
                num = row[col]
                if num!= '.':
                    if num in seen:
                        return False
                    seen.add(num)
            return True

        def is_valid_box(r_start, c_start):
            seen = set()
            for r in range(r_start, r_start + 3):
                for c in range(c_start, c_start + 3):
                    num = board[r][c]
                    if num!= '.':
                        if num in seen:
                            return False
                        seen.add(num)
            return True

        for i in range(9):
            if not is_valid_row(board[i]) or not is_valid_col(i):
                return False

        for r in range(0, 9, 3):
            for c in range(0, 9, 3):
                if not is_valid_box(r, c):
                    return False

        return True