第422场周赛：检查平衡字符串、到达最后一个房间的最少时间 Ⅰ、到达最后一个房间的最少时间 Ⅱ、统计平衡排列的数目

Q1、检查平衡字符串

1、题目描述

给你一个仅由数字 0 - 9 组成的字符串 num。如果偶数下标处的数字之和等于奇数下标处的数字之和，则认为该数字字符串是一个 平衡字符串。

如果 num 是一个 平衡字符串，则返回 true；否则，返回 false。

2、解题思路

1. 遍历字符串：我们可以遍历字符串，分别计算偶数下标位置和奇数下标位置上的数字之和。
2. 计算差值：我们用一个 diff 变量来计算差值：
   • 对于偶数下标的数字，累加到 diff。
   • 对于奇数下标的数字，累减从 diff。
3. 判断平衡：如果遍历结束后 diff 等于 0，那么该字符串就是平衡字符串，否则不是。

这个方法只需要遍历一次字符串，因此时间复杂度为 O(n)，其中 n 是字符串的长度。

3、代码实现

class Solution {
public:bool isBalanced(string num) {// 初始化差值为 0int diff = 0;// 用 flag 标记是否是偶数下标, 偶数下标加, 奇数下标减bool flag = true;// 遍历字符串中的每个字符for (const auto& ch : num) {if (flag) {// 偶数下标, 累加数字diff += ch - '0';} else {// 奇数下标, 减去数字diff -= ch - '0';}// 切换标记, 确保偶数下标和奇数下标交替flag = !flag;}// 如果差值为 0, 说明偶数下标和奇数下标的数字和相等return diff == 0;}
};

4、复杂度分析

1. 时间复杂度：

   • 我们只遍历一次字符串，因此时间复杂度为 O(n)，其中 n 是字符串的长度。

2. 空间复杂度：

   • 我们只使用了常数空间来保存 diff 和 flag，因此空间复杂度为 O(1)。

Q2、到达最后一个房间的最少时间 Ⅰ

1、题目描述

有一个地窖，地窖中有 n x m 个房间，它们呈网格状排布。

给你一个大小为 n x m 的二维数组 moveTime ，其中 moveTime[i][j] 表示在这个时刻 以后 你才可以 开始 往这个房间 移动 。你在时刻 t = 0 时从房间 (0, 0) 出发，每次可以移动到 相邻 的一个房间。在 相邻 房间之间移动需要的时间为 1 秒。

请你返回到达房间 (n - 1, m - 1) 所需要的 最少 时间。

如果两个房间有一条公共边（可以是水平的也可以是竖直的），那么我们称这两个房间是 相邻 的。

2、解题思路

我们可以将这个问题看作是一个图搜索问题，其中每个房间可以看作是图中的一个节点。每次移动到相邻房间的时间为 1 秒，同时，房间的访问时间受 moveTime[i][j] 的影响。我们的目标是从 (0, 0) 房间出发，找到到达 (n-1, m-1) 房间的最短时间。

由于每个房间的移动时间是动态的（即不能提前进入某个房间，必须等到 moveTime 所指定的时刻），这就类似于一个加权图中的最短路径问题。考虑到这是一个 最短路径 问题，可以使用 Dijkstra 算法 来解决。

Dijkstra 算法

Dijkstra 算法通常用于找最短路径问题，尤其是图中的边权为非负值时。通过优先队列（最小堆）来高效地实现。

算法步骤：

1. 初始化：设置 dis 数组，其中 dis[i][j] 表示从 (0, 0) 到房间 (i, j) 的最短时间。初始时，dis[0][0] = 0，其他房间的时间为无穷大。
2. 优先队列：使用优先队列来维护当前访问的节点（即房间），每次都选择最小时间的房间进行处理。
3. 更新邻居房间的时间：每次从当前房间 (i, j) 移动到相邻的房间 (x, y)，计算从 (i, j) 到 (x, y) 的时间。我们需要等待到 moveTime[x][y] 时刻才能进入房间 (x, y)，并且每次移动需要 1 秒。即 new_dis = max(d, moveTime[x][y]) + 1。
4. 更新最短时间：如果通过当前房间到达相邻房间 (x, y) 的时间比原来存储的时间小，则更新该房间的最短时间，并将其加入优先队列。
5. 终止条件：当队列中的最小时间到达房间 (n-1, m-1) 时，我们找到了从 (0, 0) 到 (n-1, m-1) 的最短时间。

3、代码实现

class Solution {
private:// 定义上下左右四个方向static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};public:int minTimeToReach(vector<vector<int>>& moveTime) {int n = moveTime.size();int m = moveTime[0].size();// dis 数组用于存储到每个房间的最短时间, 初始化为最大值vector<vector<int>> dis(n, vector<int>(m, INT_MAX));// 从(0, 0)开始, 时间为0dis[0][0] = 0;// 优先队列用于 Dijkstra 算法, 元素为 (当前时间, 当前房间的x坐标,// 当前房间的y坐标)priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;pq.emplace(0, 0, 0); // 从(0, 0)出发, 时间为 0while (true) {// 获取当前最短时间的房间auto [d, i, j] = pq.top();pq.pop();// 如果已经到达目标房间 (即(n-1, m-1)), 直接返回结果if (i == n - 1 && j == m - 1) {return d;}// 如果当前房间的时间已经大于之前的最短时间, 说明是一个冗余节点, 跳过if (d > dis[i][j]) {continue;}// 遍历当前房间的四个相邻房间for (auto& q : dirs) {int x = i + q[0]; // 相邻房间的 x 坐标int y = j + q[1]; // 相邻房间的 y 坐标// 如果相邻房间在合法范围内if (0 <= x && x < n && 0 <= y && y < m) {// 计算到达该相邻房间的时间int new_dis = max(d, moveTime[x][y]) + 1; // 等待 moveTime[x][y] 的时间, 再加上 1 秒移动时间// 如果通过当前房间到达相邻房间的时间比之前记录的时间小, 则更新if (new_dis < dis[x][y]) {dis[x][y] = new_dis;pq.emplace(new_dis, x, y); // 将新的房间加入优先队列}}}}}
};

4、复杂度分析

1. 时间复杂度：

   • 对于每个房间，我们最多会将其加入一次优先队列，且每次操作的时间是 O(log(n * m))。因此，时间复杂度为 O((n * m) * log(n * m))。

2. 空间复杂度：

   • 使用了 dis 数组和优先队列，空间复杂度为 O(n * m)。

Q3、到达最后一个房间的最少时间 Ⅱ

1、题目描述

有一个地窖，地窖中有 n x m 个房间，它们呈网格状排布。

给你一个大小为 n x m 的二维数组 moveTime ，其中 moveTime[i][j] 表示在这个时刻 以后 你才可以 开始 往这个房间 移动 。你在时刻 t = 0 时从房间 (0, 0) 出发，每次可以移动到 相邻 的一个房间。在 相邻 房间之间移动需要的时间为：第一次花费 1 秒，第二次花费 2 秒，第三次花费 1 秒，第四次花费 2 秒……如此 往复 。

请你返回到达房间 (n - 1, m - 1) 所需要的 最少 时间。

如果两个房间有一条公共边（可以是水平的也可以是竖直的），那么我们称这两个房间是 相邻 的。

2、解题思路

我们需要求解一个动态加权图中的最短路径问题，关键点在于每次移动的代价根据奇偶次序变化，以及需要等到指定时间才能进入某个房间。

为了解决这个问题，可以使用 Dijkstra 算法，结合以下优化：

1. 动态移动代价计算

在 Dijkstra 中，动态更新到达某个房间的时间时，需要计算移动代价：

• 假设当前时刻是 t，根据 (i+j) % 2 确定奇偶次序：
  • 如果当前是奇数次移动，则代价为 1 秒。
  • 如果当前是偶数次移动，则代价为 2 秒。

2. 优先队列优化搜索

Dijkstra 算法的核心是通过最小堆维护当前到达房间的最短时间，优先访问时间较短的节点，确保以最小代价到达目标。

3. 状态更新

对于每个房间 (x, y)，计算新的时间 new_dis，更新条件：

• 等待时间必须大于等于 moveTime[x][y]。
• 如果 new_dis < dis[x][y]，则更新 dis[x][y] 并将其加入优先队列。

4. 终止条件

一旦到达目标房间 (n-1, m-1)，直接返回当前时间作为结果。

3、代码实现

class Solution {
private:// 定义上下左右四个方向static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};public:int minTimeToReach(vector<vector<int>>& moveTime) {int n = moveTime.size();    // 地窖的行数int m = moveTime[0].size(); // 地窖的列数// 初始化最短时间数组, 所有房间的初始时间设为无穷大vector<vector<int>> dis(n, vector<int>(m, INT_MAX));dis[0][0] = 0; // 起点房间的时间为 0// 优先队列 (最小堆), 存储 (当前时间, 房间 x 坐标, 房间 y 坐标)priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;pq.emplace(0, 0, 0); // 起点房间入队// 使用 Dijkstra 算法while (!pq.empty()) {auto [d, i, j] = pq.top(); // 获取当前时间最短的房间pq.pop();// 如果已经到达目标房间, 返回当前时间if (i == n - 1 && j == m - 1) {return d;}// 如果当前时间已经不是最短时间, 跳过该房间if (d > dis[i][j]) {continue;}// 遍历相邻的四个房间for (auto& q : dirs) {int x = i + q[0]; // 相邻房间的 x 坐标int y = j + q[1]; // 相邻房间的 y 坐标// 检查房间是否在有效范围内if (0 <= x && x < n && 0 <= y && y < m) {// 计算移动到相邻房间的时间代价int new_dis = max(d, moveTime[x][y]) + (i + j) % 2 + 1; // 总时间为等待时间加移动时间// 如果新的时间更短, 则更新该房间的最短时间并加入队列if (new_dis < dis[x][y]) {dis[x][y] = new_dis;pq.emplace(new_dis, x, y);}}}}return -1; // 无法到达目标房间}
};

4、复杂度分析

1. 时间复杂度：

   • 每个房间最多处理一次，每次操作的时间为 $O(log(n\ast m))$（优先队列的插入与删除）。

   • 总体时间复杂度为 $O((n\times m)\cdot \log (n\times m))$。

2. 空间复杂度：

   • 需要存储 dis 数组和优先队列，空间复杂度为 $O(n\times m)$。

Q4、统计平衡排列的数目

1、题目描述

给你一个字符串 num 。如果一个数字字符串的奇数位下标的数字之和与偶数位下标的数字之和相等，那么我们称这个数字字符串是 平衡的 。

请你返回 num 不同排列 中，平衡 字符串的数目。

由于答案可能很大，请你将答案对 109 + 7 取余 后返回。

一个字符串的 排列 指的是将字符串中的字符打乱顺序后连接得到的字符串。

2、解题思路

本问题涉及排列组合和动态规划，主要难点在于：

1. 如何高效地统计排列中满足平衡条件的个数。
2. 如何避免重复计算和排列冗余。

通过以下步骤，我们可以解决问题：

1. 初步分析

1.1 字符串的排列

给定一个数字字符串 num，计算其所有可能的排列中，哪些是平衡的：

• 个数字在 num 中的出现次数是固定的。

• 字符串中数字的总数位和分为两部分（左部分和右部分），要求这两部分的数位和相等。

1.2 性质分析

• 如果字符串的 总数位和 不是偶数，则不可能将其分成两个相等的部分，直接返回 0。

• 如果字符串长度为 n，一部分包含 $n/2$ 个数字，另一部分包含 $n/2$ 个数字（假设 n 是偶数）。

2. 数学工具：排列组合与逆元

为了高效地处理排列中的重复情况，需要使用组合数学。
假设字符串中某个数字 $x$ 出现 $c_x$​ 次：

• 全排列公式为：

  ​ $\text{排列数}=\frac{n!}{c_0!\times c_1!\times \cdots \times c_9!}$

• 逆元：通过快速幂法计算阶乘的模逆元，用于高效求解组合数。

代码中定义了两个辅助数组：

• F[i]：表示 $i!$。
• INV_F[i]：表示 $i!$ 的逆元。

通过预处理，这些数组可以在 $O(MX)$ 时间内完成初始化，其中 $MX=41$（假设字符串长度不超过 40）。

3. 状态表示与递归搜索

我们将问题转化为一个动态规划问题，定义如下：

3.1 状态定义

1. 状态变量：

   • i：当前正在处理的数字（从 9 到 0）。
   • $left1$：左部分剩余的数字数量。
   • $lef{t}_s$：左部分剩余的数位和。

2. 转移方程：

   • 考虑将当前数字 iii 的 k 个分配到左部分：

     ​ $$\text{res}+=\text{dfs}(i-1,left1-k,lef{t}_s-k\times i)\times \text{组合数}(c,k)$$

     其中，c 是数字 i 的总出现次数， $\text{组合数}(c,k)$ 表示从 c 中选择 k 个数字的排列方式。

3.2 递归基

• 如果 i < 0（已经处理完所有数字），则检查是否满足条件：left_s == 0。

3.3 记忆化

为了避免重复计算，用三维数组 memo[i][left1][left_s] 记录已计算过的状态。

3、代码实现

const int MOD = 1'000'000'007;
const int MX = 41;long long F[MX];     // 阶乘数组 F[i] = i!
long long INV_F[MX]; // 阶乘的逆元 INV_F[i] = i!^-1// 快速幂, 用于计算逆元
long long pow(long long x, int n) {long long res = 1;for (; n; n /= 2) {if (n % 2) {res = res * x % MOD;}x = x * x % MOD;}return res;
}// 初始化阶乘和逆元数组
auto init = [] {F[0] = 1;for (int i = 1; i < MX; i++) {F[i] = F[i - 1] * i % MOD;}INV_F[MX - 1] = pow(F[MX - 1], MOD - 2);for (int i = MX - 1; i; i--) {INV_F[i - 1] = INV_F[i] * i % MOD;}return 0;
}();class Solution {
public:int countBalancedPermutations(string num) {// 统计每个数字的出现次数和总数位和int cnt[10];   // 表示数字 i 出现的次数int total = 0; // 数字的总和for (char c : num) {cnt[c - '0']++;total += c - '0';}// 如果总数位和不能被 2 整除, 则无法分成平衡的排列if (total % 2) {return 0;}// 计算数字的前缀和 (方便后续处理)partial_sum(cnt, cnt + 10, cnt);int n = num.size();      // 字符串的总长度int halfLength = n / 2;  // 平衡排列需要的数字数量int halfSum = total / 2; // 每半部分的数位和// 记忆化数组 memo[i][left1][left_s]vector<vector<vector<int>>> memo(10, vector(halfLength + 1, vector<int>(halfSum + 1, -1))); // -1 表示没有计算过// 深度优先搜索 + 动态规划auto dfs = [&](auto& dfs, int i, int left1, int left_s) -> int {// 递归基: 当所有数字已经分配完时if (i < 0) {return left_s == 0;}// 读取记忆化数组int& res = memo[i][left1][left_s]; // 注意这里是引用// 之前计算过if (res != -1) {return res;}res = 0; // 初始化结果为 0int c = cnt[i] - (i ? cnt[i - 1] : 0);int left2 = cnt[i] - left1;// 尝试分配 k 个数字到左半部分for (int k = max(c - left2, 0); k <= min(c, left1) && k * i <= left_s; k++) {int r = dfs(dfs, i - 1, left1 - k, left_s - k * i);res = (res + r * INV_F[k] % MOD * INV_F[c - k]) % MOD;}return res;};// 最终结果: 将所有可能的平衡排列数进行组合return F[halfLength] * F[n - halfLength] % MOD * dfs(dfs, 9, halfLength, total / 2) % MOD;}
};

4、复杂度分析

时间复杂度：

• 动态规划的状态个数为 $10\times n/2\times \text{halfSum}$，其中 halfSum 的上限为字符串数位和的一半。
• 假设字符串长度为 $n$，时间复杂度为 $O(10\times n\times \text{halfSum})$。

空间复杂度：

• 需要存储三维数组 memo，空间复杂度为 $O(10\times n/2\times \text{halfSum})$​。