难度可以控制，且解法唯一，时间复杂度看运气。







首先，我们定义了一个 SudokuGenerator 类。然后，我们定义了 generate 方法来生成数独游戏。该方法生成了一个 9 × 9 的矩阵，初始值为 '.'。接着，使用 solveSudoku 方法来解决数独游戏，并将解决后的结果存放在生成的矩阵中。

在求解数独游戏时，我们使用深度优先搜索算法来实现。对于每个单元格，首先检查它是否有预设值（即是否为 '.'），如果有，直接跳过。如果没有，我们随机生成1~9的数字，并检查该数字是否符合数独规则，如果不符合规则，就换一个数字再次尝试，直到找到符合规则的数字。将符合规则的数字填入该单元格，并继续向后搜索，直到搜索完成整个数独游戏。

然后，我们定义了 removeNumbers 方法来删除数独游戏，使难度符合所选根据。在此方法中，我们使用深度优先搜索算法来逐步删除数独游戏中的数字。我们找到所有预设数字的单元格，并随机打乱它们的顺序。然后尝试删除单元格中的数字，并确保解法唯一，如果解法唯一，继续删除数字，否则回退上一个状态。

最后，我们定义了 isUnique 和 solve 方法来解决数独游戏。isUnique 方法用于确定给定的游戏是否具有唯一解。该方法使用深度优先搜索算法，在填写数字的过程中判断是否出现多个解决方案。 solve 方法解决数独游戏，将字符串表示为数独板，并返回解决结果的一个布尔值。

```python
import random
class SudokuGenerator:
    def __init__(self, difficulty):
        # 限制在30和60之间
        if difficulty < 30:
            self.difficulty = 30
        elif difficulty > 60:
            self.difficulty = 60
        else:
            self.difficulty = difficulty
    def generate(self):
        board = [['.' for _ in range(9)] for _ in range(9)]
        self.solveSudoku(board)
        self.removeNumbers(board, self.difficulty)
        return board
    def solveSudoku(self, board):
        def dfs(board, row, col):
            if col == 9:
                return dfs(board, row + 1, 0)
            if row == 9:
                return True
            if board[row][col] != '.':
                return dfs(board, row, col + 1)
            nums = list(range(1, 10))
            random.shuffle(nums)
            for i in nums:
                if not isValid(board, row, col, str(i)):
                    continue
                board[row][col] = str(i)
                if dfs(board, row, col + 1):
                    return True
                board[row][col] = '.'
            return False
        def isValid(board, row, col, c):
            for i in range(9):
                if board[i][col] == c:
                    return False
                if board[row][i] == c:
                    return False
                if board[(row // 3) * 3 + i // 3][(col // 3) * 3 + i % 3] == c:
                    return False
            return True
        dfs(board, 0, 0)
    def removeNumbers(self, board, difficulty):
        def dfs(board, num):
            if num == 0:
                return True
            lst = [(i, j) for i in range(9) for j in range(9) if board[i][j] != '.']
            lst = sorted(lst, key=lambda x: random.random())
            for i, j in lst:
                c = board[i][j]
                board[i][j] = '.'
                if not self.isUnique(board):
                    board[i][j] = c
                elif dfs(board, num - 1):
                    return True
                else:
                    board[i][j] = c
            return False
        dfs(board, difficulty)
    def isUnique(self, board):
        s = ''.join([''.join(row) for row in board])
        solver = SudokuSolver()
        return solver.solve(s)
class SudokuSolver:
    def solve(self, s):
        board = [[s[i * 9 + j] for j in range(9)] for i in range(9)]
        return self.solveSudoku(board)
    def solveSudoku(self, board):
        def dfs(board, row, col):
            if col == 9:
                return dfs(board, row + 1, 0)
            if row == 9:
                return True
            if board[row][col] != '.':
                return dfs(board, row, col + 1)
            for i in range(1, 10):
                if not isValid(board, row, col, str(i)):
                    continue
                board[row][col] = str(i)
                if dfs(board, row, col + 1):
                    return True
                board[row][col] = '.'
            return False
        def isValid(board, row, col, c):
            for i in range(9):
                if board[i][col] == c:
                    return False
                if board[row][i] == c:
                    return False
                if board[(row // 3) * 3 + i // 3][(col // 3) * 3 + i % 3] == c:
                    return False
            return True
        return dfs(board, 0, 0)
generator = SudokuGenerator(50)  # 挖空多少个格子
board = generator.generate()
for row in board:
    print(row)
print(str(board).count("."))
```


检查时间复杂度：

```python
import time
ties = []
for _ in range(100):
    t0 = time.time()
    generator = SudokuGenerator(60)  # 挖空多少个格子
    board = generator.generate()
    # for row in board:
    #     print(row)
    ties.append(time.time() - t0)
print(max(ties))
print(min(ties))
print(sum(ties) / len(ties))
```

得到的生成游戏所消耗的时间是：

254.41049194335938

0.02700185775756836

7.814508402347565

最大时间居然需要254秒，需要改进。

【算法题目】使用Python生成一个数独游戏的棋盘

【算法题目】【Python】彻底刷遍DFS与回溯的算法题目

参考：[https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-48c1d/wo-xie-le--9c7a4/](https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-48c1d/wo-xie-le--9c7a4/)






#  1 基本介绍

二分查找法（Binary Search）是一种在**有序数组**中查找某一特定元素的搜索算法。其基本思想是，首先将整个有序数列分成前后两部分，判断在哪个部分中可能会找到要查找的数，然后递归地在那个部分中查找。

具体来说，首先选择数列的中间元素。如果要查找的数比中间元素小，则在数列的左半部分继续查找；如果要查找的数比中间元素大，则在数列的右半部分继续查找；如果相等，则找到了要查找的数。这样一直递归进行，直到找到要查找的数或者整个数列被查找完。

二分查找法的时间复杂度为 O(log n)，其中 n 是数列中的元素个数。由于其在有序数列中查找元素的时间复杂度较低，因此常用于大规模有序数列的查找。

> 二分查找并不简单，Knuth 大佬（发明 KMP 算法的那位）都说二分查找：思路很简单，细节是魔鬼。

- 有哪些细节：

> while循环中使用 low <= high 还是 low < high ？ 

> if条件里写<还是<=? 是low = mid +1？

> 还是low = mid ？



# 2 基本的二分查找

基本的二分查找中有序数组里的元素没有重复数值，而二分查找的目的就是找到符合条件的下标。

比如想在有序数组 arr = [1, 2, 3, 4, 5, 6, 7, 8, 9] 中找到元素5的index，该如何写python代码呢：

```python
def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    while low <= high:  # 结束条件是 low > high， 为什么不用<符号呢：因为当low=high时，还需要判断一次，不然[low,high]就会被漏掉
        mid = (low + high) // 2  # 和mid=low+(high-low)//2是一样的结果，low+(high-low)//2可以防止大数溢出
        if arr[mid] < x:
            low = mid + 1  # 在区间 [mid+1, high] 中查找
        elif arr[mid] > x:
            high = mid - 1  # 在区间 [low, mid-1] 中查找
        elif arr[mid] == x:
            return mid
    return -1
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
x = 5
result = binary_search(arr, x)
if result != -1:
    print(f"Element is present at index {result}")
else:
    print("Element is not present in array")
```

# 3 左边界 vs 右边界，查找相等的元素

当有序数组中存在重复值，即是由多个元素可以满足条件，返回哪一个下标更合适呢？

比如 arr = [1, 2, 3, 4, 5, 5, 5, 6, 7, 8, 9]， 找数值5，那么左边界index是4，右边界index是6。 

如果有序数组中有重复值，并且你想找到左边界的下标，你可以在二分查找的基础上，做一些改变来实现这个功能。

下面的代码展示了左边界和右边界的代码：

```python
def binary_search_leftright(arr, x):
    low = 0
    high = len(arr) - 1
    result = -1
    while low <= high:  # 结束条件是 low > high， 为什么不用<符号呢：因为当low=high时，还需要判断一次，不然[low,high]就会被漏掉
        mid = (low + high) // 2  # 和mid=low+(high-low)//2是一样的结果，low+(high-low)//2可以防止大数溢出
        if arr[mid] < x:
            low = mid + 1  # 在区间 [mid+1, high] 中查找
        elif arr[mid] > x:
            high = mid - 1  # 在区间 [low, mid-1] 中查找
        elif arr[mid] == x:
            result = mid  # 记录符合条件的下标
            # high = mid - 1  # 在区间 [low, mid-1] 中查找，这就很灵性，意味着找到了，但是还要继续找，而且趋势是往左找. 即找左边界。
            low = mid + 1  # 在区间 [mid+1, high] 中查找，这就很灵性，意味着找到了，但是还要继续找，而且趋势是往右找. 即找右边界。
    return result
arr = [1, 2, 3, 4, 5, 5, 5, 6, 7, 8, 9]
x = 5
result = binary_search_left(arr, x)
if result != -1:
    print(f"Element is present at index {result}")
else:
    print("Element is not present in array")
```

# 4 难度升级，找到 x<6 的右边界

在 arr = [4, 4, 5, 5, 6, 6, 7, 8, 9] 中找到一个元素x，满足x<6，且x是右边界元素：
```python
def binary_search_right(arr, x):
    low = 0
    high = len(arr) - 1
    while low < high:
        mid = (low + high) // 2
        if arr[mid] < x:
            low = mid + 1  # 继续在[mid+1, high]中查找，因为想找右边界
        else:
            high = mid  # 为什么不是mid-1呢?
    if arr[high] >= x:
        return high - 1
    else:
        return high
arr = [4, 4, 5, 5, 6, 6, 7, 8, 9]
x = 6
result = binary_search_right(arr, x)
print(result)
```

函数返回 high - 1 或者返回high。


- 如果将条件改为while low <= high呢，这样不可以吗？

> 如果你将循环的条件改为 while low <= high，在数组中查找小于目标值的右边界的时候是会有问题的。

> 

> 当low==high时，如果arr[high] >= x 那么最终返回值就是high -1,而实际上并不是小于目标值的右边界。

> 

> 因此，在二分查找中查找右边界时，循环条件应该是 low < high.

> 

> 这样当循环结束时，high指向的就是第一个大于等于目标值的位置，而high - 1就是小于目标值的右边界

> 

> 所以，在二分查找中查找右边界时，循环条件应该是 low < high 而非 low <= high,这是为了确保查找的正确性

> 

> 除此之外，还可能发生死循环。


- 那为什么是high = mid ，而不是high = mid -1？

> 在查找小于目标值的右边界时，如果循环条件是 low < high, 当 arr[mid] >= x 时,如果 high = mid -1 会使得 high 不满足循环条件,从而导致循环终止，而不是移动到小于目标值的右边界。

> 

> 而赋值high = mid会使得high = mid或者 high =

> mid-1,这样high总是满足循环条件且正确地找到了第一个大于等于目标值的位置,而high-1就是小于目标值的右边界。

> 

> 所以如果你想在查找小于目标值的右边界时，应该让 high = mid。这样可以保证查找的正确性。


# 5 找到 x>5 的左边界

在 arr = [4, 4, 5, 5, 6, 6, 7, 8, 9] 中找到一个元素x，满足x>5，且x是左边界元素：

```python
def binary_search_left(arr, x):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] <= x:
            low = mid + 1
        else:
            high = mid - 1
    return low
arr = [4, 4, 5, 5, 6, 6, 7, 8, 9]
x = 5
result = binary_search_left(arr, x)
print(result)
```

或者：

```python
def binary_search_left(arr, x):
    low = 0
    high = len(arr)
    while low < high:
        mid = (low + high) // 2
        if arr[mid] <= x:
            low = mid + 1
        else:
            high = mid 
    return low
```


# 6 总结模板

当使用 "while low <= high" 时，要想结束循环，就需要更严格的判断，从而就不需要再单独对low 和high 进行特判。

如果要查找左边界（x>5的左边界）：

```python
def binary_search_left(arr, x):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] <= x: # 如果是x>=5，这里就需要改变查找区间
            low = mid + 1
        else:
            high = mid - 1
    return low
```

如果要查找右边界（x<6的右边界）：

```python
def binary_search_right(arr, x):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] < x: # 如果是x<=6，这里就需要改变查找区间
            low = mid + 1
        else:
            high = mid - 1
    return high
```

【算法题目】一文搞懂二分查找法

![在这里插入图片描述](/static/img/images/04904.png)





普通二叉树，每个节点的数值不相同。写一个函数，输入是树的根节点和要删除的节点的集合，删除某个节点意味着去除掉和这个节点的关联，剩下的都是子树，函数返回剩余子树数量。

input：root，｛1｝

output：2

input：root，｛1,,2,5｝

output：2

input：root，｛1,,2｝

output：3

input：root，｛4｝

output：3

input：root，｛4,9｝

output：2


程序还有点问题：
```python
import copy
from typing import Set
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
def getSubTree(root: Node, elements: Set, node_del=False) -> int:
"""
    if not elements or root is None:
        return 0
    if root.val in elements:
        elements = copy.deepcopy(elements)
        elements.remove(root.val)
        left_num = 1 + getSubTree(root.left, elements, True) if root.left is not None else 0
        right_num = 1 + getSubTree(root.right, elements, True) if root.right is not None else 0
        if node_del:
            return left_num + right_num - 1
        return left_num + right_num
    else:
        left_num = getSubTree(root.left, elements, False) if root.left is not None else 0
        right_num = getSubTree(root.right, elements, False) if root.right is not None else 0
        return left_num + right_num
        """
root = Node(1)
root.left = tree2 = Node(2)
root.right = tree3 = Node(3)
tree2.left = tree4 = Node(4)
tree2.right = tree5 = Node(5)
tree3.left = tree6 = Node(6)
tree3.right = tree7 = Node(7)
tree4.left = tree8 = Node(8)
tree4.right = tree9 = Node(9)
print(getSubTree(root, {1, 2, 5}))
```

【算法题目】【DFS】【一点资讯面试题】二叉树删除节点剩余子树数量

浮点数的 n次方根：





牛顿迭代法：
```python
class Solution:
    def sqrt_n(self, y, n) -> int:
        # f(x)=x**n-y=0
        # f`(x)=n*x^(n-1)
        # x=x-(x**n-y)/(n*2^(n-1))
        if n == 0:
            return 1
        # x1 的 n1 次方
        def pow1(x1, n1):
            if n1 == 0:
                return 1
            y1 = pow1(x1, n1 // 2)
            return y1 * y1 if n1 % 2 == 0 else y1 * y1 * x1
        x = 1  # 牛顿不动点迭代法
        while True:
            x2 = x - (pow1(x, n) - y) / (n * pow1(x, n - 1))
            if abs(x2 - x) < 1e-6:
                break
            x = x2
        return x2
```

二分查找：
```python
class Solution:
    def sqrt_n(self, y, n) -> int:
        assert n > 0
        # x1 的 n1 次方
        def pow1(x1, n1):
            if n1 == 0:
                return 1
            y1 = pow1(x1, n1 // 2)
            return y1 * y1 if n1 % 2 == 0 else y1 * y1 * x1
        # 二分查找，在0到y之间查找
        b1, b2 = 0, y
        while True:
            x = (b1 + b2) / 2
            if pow1(x, n) < y - 1e-2:
                b1 = x
            elif pow1(x, n) > y + 1e-2:
                b2 = x
            else:
                break
        return [x,-x]
```

【算法题目】浮点数的 n次方根 n次方 ，牛顿迭代法

我是一个专注技术分享的博主,尤其爱搞深度学习和单片机电子。你现在看到的是我的个人博客网站。

参考资料