# 36. 有效的数独 





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

python
```python
from typing import List
class Solution:
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        # init data
        rows = [{} for i in range(9)] # 字典 哈希表 列表第一个字典：rows[0]这个字典是第一行的键值信息
        columns = [{} for i in range(9)] # 字典 哈希表
        boxes = [{} for i in range(9)] # 字典 哈希表
        # validate a board
        for i in range(9):
            for j in range(9):
                num = board[i][j]  # 第i行  第j列  的元素
                if num != '.':
                    num = int(num)
                    box_index = (i // 3) * 3 + j // 3    # 在一个3*3方格里的index
                    # keep the current cell value
                    rows[i][num] = rows[i].get(num, 0) + 1  # 第i行的rows字典里找这个元素，找不到就是0，加1后变成1. 找得到加上1后就会大于1
                    columns[j][num] = columns[j].get(num, 0) + 1
                    boxes[box_index][num] = boxes[box_index].get(num, 0) + 1
                    # check if this value has been already seen before
                    if rows[i][num] > 1 or columns[j][num] > 1 or boxes[box_index][num] > 1:
                        return False
        return True
print(Solution().isValidSudoku([
  ["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"]  ]))
```

运行完毕后：

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

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

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

按健寻值的字典：

```python
rows = [{} for i in range(9)]
print(rows)
rows[0][1]=1
rows[0][3]=1
rows[1][1]=1
print(rows)
```

结果
```python
C:\Users\xd_du\Anaconda3\envs\py37\python.exe C:/Users/xd_du/PycharmProjects/wave/gendata.py
[{}, {}, {}, {}, {}, {}, {}, {}, {}]
[{1: 1, 3: 1}, {1: 1}, {}, {}, {}, {}, {}, {}, {}]
Process finished with exit code 0
```

# 37. 解数独

https://leetcode-cn.com/problems/sudoku-solver/solution/jie-shu-du-by-leetcode-solution/

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

```python
from typing import List
class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        def dfs(pos: int):
            nonlocal valid
            if pos == len(spaces):
                valid = True
                return
            i, j = spaces[pos]
            for digit in range(9):
                if line[i][digit] == column[j][digit] == block[i // 3][j // 3][digit] == False:
                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = True
                    board[i][j] = str(digit + 1)
                    dfs(pos + 1)   #递归
                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = False
                if valid:
                    return
        line = [[False] * 9 for _ in range(9)]
        column = [[False] * 9 for _ in range(9)]
        block = [[[False] * 9 for _a in range(3)] for _b in range(3)]
        valid = False
        spaces = list()
        for i in range(9):
            for j in range(9):
                if board[i][j] == ".":
                    spaces.append((i, j))
                else:
                    digit = int(board[i][j]) - 1
                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = True
        dfs(0)
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"]]
Solution().solveSudoku(board)
for i in range(9):
    print(board[i])
```

```python
def check(matrix, row, col, value):
    """
    检测在(row,col)放value是否合适
    1.每行含1-9,不含重复值value
    2.每列含1-9,不含重复值value
    3.3*3区块含1-9,不含重复值value
    """
    # 检测每行
    for j in range(9):
        if matrix[row][j] == value:
            return False
    # 检测每列
    for i in range(9):
        if matrix[i][col] == value:
            return False
    # 检测元素所在3*3区域
    area_row = (row // 3) * 3
    area_col = (col // 3) * 3
    for i in range(area_row, area_row + 3):
        for j in range(area_col, area_col + 3):
            if matrix[i][j] == value:
                return False
    return True
def solveSudoku(matrix, count=0):
    """
    遍历每一个未填元素，遍历1-9替换为合适的数字
    """
    if (count == 81):  # 递归出口
        return True
    #行优先遍历
    row = count // 9  # 行标
    col = count % 9  # 列标
    if matrix[row][col] != 0:  # 已填充
        return solveSudoku(matrix, count=count + 1)
    else:  # 未填充
        for i in range(1, 10):
            if check(matrix, row, col, i):  # 找到可能的填充数
                matrix[row][col] = i
                if solveSudoku(matrix, count=count + 1):  # 是否可完成
                    return True  # 可完成
                # 不可完成
                matrix[row][col] = 0  # 回溯
        return False  # 不可完成
while True:
    try:
        matrix = []
        for i in range(9):
            matrix.append([int(i) for i in  input().split(' ')])#多维列表输入
        solveSudoku(matrix)
        for i in range(9):
            print( ' '.join(map(str, matrix[i])))
    except:
        break
```



# 生成一张标准数独地图

标准数独地图有17个数字提示，且是有唯一解的。

36. 有效的数独（遍历一次 9+9+9个字典 哈希） 37. 解数独

# 1 两数之和





https://leetcode-cn.com/problems/two-sum/

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

python

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

```python
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable = dict()
        for i, num in enumerate(nums):
            if target - num in hashtable:
                return [hashtable[target - num], i]
            hashtable[nums[i]] = i
        return []
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
```

# 2 三数之和

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

python
```python
from typing import List
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        nums.sort()
        ans = list()
        # 枚举 a
        for first in range(n):  # 遍历所有元素
            # 需要和上一次枚举的数不相同
            if first > 0 and nums[first] == nums[first - 1]:
                continue
            # c 对应的指针初始指向数组的最右端
            third = n - 1
            target = -nums[first]
            # 枚举 b
            for second in range(first + 1, n):
                # 需要和上一次枚举的数不相同
                if second > first + 1 and nums[second] == nums[second - 1]:
                    continue
                # 需要保证 b 的指针在 c 的指针的左侧
                while second < third and nums[second] + nums[third] > target:
                    third -= 1
                # 如果指针重合，随着 b 后续的增加
                # 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                if second == third:
                    break
                if nums[second] + nums[third] == target:
                    ans.append([nums[first], nums[second], nums[third]])
        return ans
print(Solution().threeSum([3, 5, 4, 4, -2, -2, -1, -3, -3]))
```

# 3 四数之和

https://leetcode-cn.com/problems/4sum/solution/si-shu-zhi-he-by-leetcode-solution/

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

1. 两数之和（哈希表） 15. 三数之和（双指针） 18. 四数之和

https://leetcode-cn.com/problems/container-with-most-water/





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

python

```python
class Solution:
    def maxArea(self, height) -> int:
        l, r = 0, len(height) - 1  # 左右指针
        ans = 0
        while l < r:  # 左右指针指向同一个元素的时候退出循环
            area = min(height[l], height[r]) * (r - l)  # 面积　＝　最短挡板　×　间距
            ans = max(ans, area)  # 答案只想要最大的面积
            if height[l] <= height[r]:  # 左挡板 小于 右挡板
                l += 1  # 左指针移动
            else:
                r -= 1  # 右指针移动
        return ans
print(Solution().maxArea([3, 5, 4]))
```

左右指针正确性：

（1）假设左指针指着height[0]不动；

（2）移动可行性：右指针指着height[-1]，此时面积假设为area1。如果右指针移动，指着height[-2]，此时面积假设为area2。间距的缩小，使得只有当height[-2]挡板大于之前的，才有可能找到更大的值。

（3）该移动哪一个指针？：左挡板 小于等于 右挡板，那么就移动左指针。

11. 盛最多水的容器 双指针

# 1 题目





[https://leetcode-cn.com/problems/water-and-jug-problem/](https://leetcode-cn.com/problems/water-and-jug-problem/)

有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？

如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升 水。

你允许：

装满任意一个水壶

清空任意一个水壶

从一个水壶向另外一个水壶倒水，直到装满或者倒空


输入: x = 3, y = 5, z = 4

输出: True

示例 2:

输入: x = 2, y = 6, z = 5

输出: False

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/water-and-jug-problem

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

# 2 题目解析与数学解法

题目没说清楚，看了解答才知道，我们把题目做一个等价。

题目想表达的是这样：有3个壶编号，容量如下表。

| 水壶编号| 水壶1 |   水壶2  |  水壶3  |

|:--------:|:--------:| :----------:| :----------:|

| 容量 | x| y |x+y |

最开始水壶3全是水，是满的。不管我们怎么倒腾，最终要得到z升水在水壶3（目标）。

因此必须有 z <= x+y 了。

一个数学解答是，找到2个整数a和b，让其满足 ax+by=z 。（整数=正整数+0+负整数）

>    贝祖定理：ax+by=z 有解当且仅当 z 是 x,y 的最大公约数的倍数。

所以判断有没有这样的2个整数a和b，就去判断x+y最大公约数的倍数是不是可以等于z。（3和5的最大公约数是1）

python

```python
import math
class Solution:
    def canMeasureWater(self, x: int, y: int, z: int) -> bool:
        if x + y < z:  # 一共都没那么多水
            return False
        if x == 0 or y == 0:  #
            return z == 0 or x + y == z  # z是0显然True  x和y有一个是0就必须x+y=z才是True
        return (z % math.gcd(x, y)) == 0
print(Solution().canMeasureWater(3, 5, 4))
```

# 3 DFS

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

```python
class Solution:
    def canMeasureWater(self, x: int, y: int, z: int) -> bool:
        stack = [(0, 0)]
        self.seen = set()
        while stack:
            remain_x, remain_y = stack.pop()
            if remain_x == z or remain_y == z or remain_x + remain_y == z:
                return True
            if (remain_x, remain_y) in self.seen:
                continue
            self.seen.add((remain_x, remain_y))
            # 把 X 壶灌满。
            stack.append((x, remain_y))
            # 把 Y 壶灌满。
            stack.append((remain_x, y))
            # 把 X 壶倒空。
            stack.append((0, remain_y))
            # 把 Y 壶倒空。
            stack.append((remain_x, 0))
            # 把 X 壶的水灌进 Y 壶，直至灌满或倒空。
            stack.append((remain_x - min(remain_x, y - remain_y), remain_y + min(remain_x, y - remain_y)))
            # 把 Y 壶的水灌进 X 壶，直至灌满或倒空。
            stack.append((remain_x + min(remain_y, x - remain_x), remain_y - min(remain_y, x - remain_x)))
        return False
print(Solution().canMeasureWater(3, 5, 4))
```

水壶问题

要在Android中实现震动50ms，并将震动等级设置为低，你可以使用`Vibrator`类。下面是一个简单的代码示例，展示如何实现这个功能：





```java
import android.content.Context;
import android.os.VibrationEffect;
import android.os.Vibrator;
public void vibratePhone(Context context) {
    Vibrator vibrator = (Vibrator) context.getSystemService(Context.VIBRATOR_SERVICE);
    if (vibrator != null && vibrator.hasVibrator()) {
        // 设置震动等级低一点，使用VibrationEffect.DEFAULT_AMPLITUDE的一半
        int vibrationAmplitude = VibrationEffect.DEFAULT_AMPLITUDE / 2;
        VibrationEffect vibrationEffect = VibrationEffect.createOneShot(50, vibrationAmplitude);
        vibrator.vibrate(vibrationEffect);
    }
}
```

### 代码说明：

- `Vibrator`：获取系统的震动服务。

- `VibrationEffect.createOneShot(50, vibrationAmplitude)`：创建一个持续50ms的震动效果，并将震动等级设置为默认等级的一半。

- `vibrator.vibrate(vibrationEffect)`：让设备执行震动。

这个代码可以放在你的活动或服务中，只要传入`Context`即可。这样可以实现设备震动50ms，并且震动等级相对较低。


要调用上面提供的震动功能代码，你需要在合适的地方使用 `vibratePhone` 方法。以下是如何在一个 Android 活动（Activity）中调用这个方法的示例。

### 示例代码：

```java
import android.os.Bundle;
import androidx.appcompat.app.AppCompatActivity;
public class MainActivity extends AppCompatActivity {
    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);
        // 调用震动方法
        vibratePhone(this);
    }
    // 震动方法的定义
    private void vibratePhone(Context context) {
        Vibrator vibrator = (Vibrator) context.getSystemService(Context.VIBRATOR_SERVICE);
        if (vibrator != null && vibrator.hasVibrator()) {
            // 设置震动等级低一点，使用VibrationEffect.DEFAULT_AMPLITUDE的一半
            int vibrationAmplitude = VibrationEffect.DEFAULT_AMPLITUDE / 2;
            VibrationEffect vibrationEffect = VibrationEffect.createOneShot(50, vibrationAmplitude);
            vibrator.vibrate(vibrationEffect);
        }
    }
}
```

### 调用说明：

- 在 `MainActivity` 的 `onCreate` 方法中，调用了 `vibratePhone(this)`，并将当前活动的 `Context` 传递给方法。

- `vibratePhone` 方法会在活动创建时执行设备震动50ms。

你可以在任何需要的地方调用这个方法，例如按钮点击事件、某个特定条件触发时等。

### 示例：在按钮点击时触发震动
```java
import android.os.Bundle;
import android.view.View;
import android.widget.Button;
import androidx.appcompat.app.AppCompatActivity;
public class MainActivity extends AppCompatActivity {
    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);
        // 查找按钮
        Button vibrateButton = findViewById(R.id.vibrateButton);
        // 设置按钮点击监听器
        vibrateButton.setOnClickListener(new View.OnClickListener() {
            @Override
            public void onClick(View v) {
                // 按钮点击时调用震动方法
                vibratePhone(MainActivity.this);
            }
        });
    }
    // 震动方法的定义
    private void vibratePhone(Context context) {
        Vibrator vibrator = (Vibrator) context.getSystemService(Context.VIBRATOR_SERVICE);
        if (vibrator != null && vibrator.hasVibrator()) {
            int vibrationAmplitude = VibrationEffect.DEFAULT_AMPLITUDE / 2;
            VibrationEffect vibrationEffect = VibrationEffect.createOneShot(50, vibrationAmplitude);
            vibrator.vibrate(vibrationEffect);
        }
    }
}
```

在这个示例中，`vibrateButton` 是一个按钮的ID，当用户点击按钮时，会触发震动。

【Android】android，震动一下，50ms，震动等级设置低一点

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