代码如诗

864. 获取所有钥匙的最短路径

给定一个二维网格 grid ，其中：

• '.' 代表一个空房间

• '#' 代表一堵墙

• '@' 是起点

• 小写字母代表钥匙

• 大写字母代表锁

我们从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间。我们不能在网格外面行走，也无法穿过一堵墙。如果途经一个钥匙，我们就把它捡起来。除非我们手里有对应的钥匙，否则无法通过锁。

假设 k 为 钥匙/锁 的个数，且满足 1 <= k <= 6，字母表中的前 k 个字母在网格中都有自己对应的一个小写和一个大写字母。换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁。另外，代表钥匙和锁的字母互为大小写并按字母顺序排列。

返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙，返回 -1 。

示例 1：

```txt

输入：grid = ["@.a.#","###.#","b.A.B"]

输出：8

解释：目标是获得所有钥匙，而不是打开所有锁。

```

示例 2：

```txt

输入：grid = ["@..aA","..B#.","....b"]

输出：6

```

示例 3:

```txt

输入: grid = ["@Aa"]

输出: -1

```

提示：

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 30

• grid[i][j] 只含有 '.', '#', '@', 'a'-``'f``' 以及 'A'-'F'

• 钥匙的数目范围是 [1, 6] 

• 每个钥匙都对应一个 不同 的字母

• 每个钥匙正好打开一个对应的锁

2867. 统计树中的合法路径数目

给你一棵 n 个节点的无向树，节点编号为 1 到 n 。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ui, vi] 表示节点 ui 和 vi 在树中有一条边。

请你返回树中的 合法路径数目 。

如果在节点 a 到节点 b 之间 恰好有一个 节点的编号是质数，那么我们称路径 (a, b) 是 合法的 。

注意：

• 路径 (a, b) 指的是一条从节点 a 开始到节点 b 结束的一个节点序列，序列中的节点 互不相同 ，且相邻节点之间在树上有一条边。

• 路径 (a, b) 和路径 (b, a) 视为 同一条 路径，且只计入答案 一次 。

示例 1：

```txt

输入：n = 5, edges = [[1,2],[1,3],[2,4],[2,5]]

输出：4

解释：恰好有一个质数编号的节点路径有：

• (1, 2) 因为路径 1 到 2 只包含一个质数 2 。

• (1, 3) 因为路径 1 到 3 只包含一个质数 3 。

• (1, 4) 因为路径 1 到 4 只包含一个质数 2 。

• (2, 4) 因为路径 2 到 4 只包含一个质数 2 。

只有 4 条合法路径。

```

示例 2：

```txt

输入：n = 6, edges = [[1,2],[1,3],[2,4],[3,5],[3,6]]

输出：6

解释：恰好有一个质数编号的节点路径有：

• (1, 2) 因为路径 1 到 2 只包含一个质数 2 。

• (1, 3) 因为路径 1 到 3 只包含一个质数 3 。

• (1, 4) 因为路径 1 到 4 只包含一个质数 2 。

• (1, 6) 因为路径 1 到 6 只包含一个质数 3 。

• (2, 4) 因为路径 2 到 4 只包含一个质数 2 。

• (3, 6) 因为路径 3 到 6 只包含一个质数 3 。

只有 6 条合法路径。

```

提示：

• 1 <= n <= 10^5

• edges.length == n - 1

• edges[i].length == 2

• 1 <= ui, vi <= n

• 输入保证 edges 形成一棵合法的树。

1240. 铺瓷砖

你是一位施工队的工长，根据设计师的要求准备为一套设计风格独特的房子进行室内装修。

房子的客厅大小为 n x m，为保持极简的风格，需要使用尽可能少的 正方形 瓷砖来铺盖地面。

假设正方形瓷砖的规格不限，边长都是整数。

请你帮设计师计算一下，最少需要用到多少块方形瓷砖？

示例 1：

```txt

输入：n = 2, m = 3

输出：3

解释：3 块地砖就可以铺满卧室。

 2 块 1x1 地砖 1 块 2x2 地砖

```

示例 2：

```txt

输入：n = 5, m = 8

输出：5

```

示例 3：

```txt

输入：n = 11, m = 13

输出：6

```

提示：

• 1 <= n <= 13

• 1 <= m <= 13

2851. 字符串转换

You are given two strings s and t of equal length n. You can perform the following operation on the string s:

• Remove a suffix of s of length l where 0 < l < n and append it at the start of s.

  For example, let s = 'abcd' then in one operation you can remove the suffix 'cd' and append it in front of s making s = 'cdab'.

You are also given an integer k. Return the number of ways in which s can be transformed into t in exactly k operations.

Since the answer can be large, return it modulo 10^9 + 7.

Example 1:

```txt

Input: s = "abcd", t = "cdab", k = 2

Output: 2

Explanation:

First way:

In first operation, choose suffix from index = 3, so resulting s = "dabc".

In second operation, choose suffix from index = 3, so resulting s = "cdab".

Second way:

In first operation, choose suffix from index = 1, so resulting s = "bcda".

In second operation, choose suffix from index = 1, so resulting s = "cdab".

```

Example 2:

```txt

Input: s = "ababab", t = "ababab", k = 1

Output: 2

Explanation:

First way:

Choose suffix from index = 2, so resulting s = "ababab".

Second way:

Choose suffix from index = 4, so resulting s = "ababab".

```

Constraints:

• 2 <= s.length <= 5 * 10^5

• 1 <= k <= 10^15

• s.length == t.length

• s and t consist of only lowercase English alphabets.

6456. 矩阵中严格递增的单元格数

给你一个下标从 1 开始、大小为 m x n 的整数矩阵 mat，你可以选择任一单元格作为 起始单元格 。

从起始单元格出发，你可以移动到 同一行或同一列 中的任何其他单元格，但前提是目标单元格的值 严格大于 当前单元格的值。

你可以多次重复这一过程，从一个单元格移动到另一个单元格，直到无法再进行任何移动。

请你找出从某个单元开始访问矩阵所能访问的 单元格的最大数量 。

返回一个表示可访问单元格最大数量的整数。

示例 1：

```txt

输入：mat = [[3,1],[3,4]]

输出：2

解释：上图展示了从第 1 行、第 2 列的单元格开始，可以访问 2 个单元格。可以证明，无论从哪个单元格开始，最多只能访问 2 个单元格，因此答案是 2 。

```

示例 2：

```txt

输入：mat = [[1,1],[1,1]]

输出：1

解释：由于目标单元格必须严格大于当前单元格，在本示例中只能访问 1 个单元格。

```

示例 3：

```txt

输入：mat = [[3,1,6],[-9,5,7]]

输出：4

解释：上图展示了从第 2 行、第 1 列的单元格开始，可以访问 4 个单元格。可以证明，无论从哪个单元格开始，最多只能访问 4 个单元格，因此答案是 4 。

```

提示：

• m == mat.length 

• n == mat[i].length 

• 1 <= m, n <= 10^5

• 1 <= m * n <= 10^5

• -10^5 <= mat[i][j] <= 10^5

1201. 丑数 III

给你四个整数：n 、a 、b 、c ，请你设计一个算法来找出第 n 个丑数。

丑数是可以被 a 或 b 或 c 整除的 正整数 。

示例 1：

```txt

输入：n = 3, a = 2, b = 3, c = 5

输出：4

解释：丑数序列为 2, 3, 4, 5, 6, 8, 9, 10... 其中第 3 个是 4。

```

示例 2：

```txt

输入：n = 4, a = 2, b = 3, c = 4

输出：6

解释：丑数序列为 2, 3, 4, 6, 8, 9, 10, 12... 其中第 4 个是 6。

```

示例 3：

```txt

输入：n = 5, a = 2, b = 11, c = 13

输出：10

解释：丑数序列为 2, 4, 6, 8, 10, 11, 12, 13... 其中第 5 个是 10。

```

示例 4：

```txt

输入：n = 1000000000, a = 2, b = 217983653, c = 336916467

输出：1999999984

```

提示：

• 1 <= n, a, b, c <= 10^9

• 1 <= a * b * c <= 10^18

• 本题结果在 [1, 2 * 10^9] 的范围内

2009. 使数组连续的最少操作数

给你一个整数数组 nums 。每一次操作中，你可以将 nums 中 任意 一个元素替换成 任意 整数。

如果 nums 满足以下条件，那么它是 连续的 ：

• nums 中所有元素都是 互不相同 的。

• nums 中 最大 元素与 最小 元素的差等于 nums.length - 1 。

比方说，nums = [4, 2, 5, 3] 是 连续的 ，但是 nums = [1, 2, 3, 5, 6] 不是连续的 。

请你返回使 nums 连续 的 最少 操作次数。

示例 1：

```txt

输入：nums = [4,2,5,3]

输出：0

解释：nums 已经是连续的了。

```

示例 2：

```txt

输入：nums = [1,2,3,5,6]

输出：1

解释：一个可能的解是将最后一个元素变为 4 。

结果数组为 [1,2,3,5,4] ，是连续数组。

```

示例 3：

```txt

输入：nums = [1,10,100,1000]

输出：3

解释：一个可能的解是：

• 将第二个元素变为 2 。

• 将第三个元素变为 3 。

• 将第四个元素变为 4 。

结果数组为 [1,2,3,4] ，是连续数组。

```

提示：

• 1 <= nums.length <= 10^5

• 1 <= nums[i] <= 10^9