当前位置： 首页 > article >正文

Leetcode 第 422 场周赛题解

article 2024/12/25 2:20:33

Leetcode 第 422 场周赛题解

  • Leetcode 第 422 场周赛题解
    • 题目1：3340. 检查平衡字符串
      • 思路
      • 代码
      • 复杂度分析
    • 题目2：3341. 到达最后一个房间的最少时间 I
      • 思路
      • 代码
      • 复杂度分析
    • 题目3：3342. 到达最后一个房间的最少时间 II
      • 思路
      • 代码
      • 复杂度分析
    • 题目4：3343. 统计平衡排列的数目
      • 思路
      • 代码
      • 复杂度分析

Leetcode 第 422 场周赛题解

题目1：3340. 检查平衡字符串

思路

模拟。

代码

/*
 * @lc app=leetcode.cn id=3340 lang=cpp
 *
 * [3340] 检查平衡字符串
 */

// @lc code=start
class Solution
{
public:
    bool isBalanced(string num)
    {
        int oddSum = 0, evenSum = 0;
        for (int i = 0; i < num.length(); i++)
            (i % 2 ? oddSum : evenSum) += (num[i] - '0');

        return oddSum == evenSum;
    }
};
// @lc code=end

复杂度分析

时间复杂度：O(n)，其中 n 是字符串 num 的长度。

空间复杂度：O(1)。

题目2：3341. 到达最后一个房间的最少时间 I

思路

广度优先搜索。

一个节点的最短路径可能来自于上下左右，单纯用BFS会导致重复访问节点，造成死循环问题。为此，使用一个distance[m][n]的数组来记录从(0,0)节点到当前节点(i,j)的最短路径，当重复访问节点时，只有在当前最小值被更新时，才将这个节点加入队列（相当于更新操作，重新从该点出发去找寻到达最终节点的最短路径），否则不加入队列，这样就不会造成死循环问题。

代码

/*
 * @lc app=leetcode.cn id=3341 lang=cpp
 *
 * [3341] 到达最后一个房间的最少时间 I
 */

// @lc code=start
class Solution
{
private:
    const int dx[4] = {0, 1, 0, -1};
    const int dy[4] = {1, 0, -1, 0};

public:
    int minTimeToReach(vector<vector<int>> &moveTime)
    {
        int m = moveTime.size(), n = m ? moveTime[0].size() : 0;

        // distance[i][j]记录从节点(0,0)到当前节点(i,j)的最短路径
        vector<vector<int>> distance(m, vector<int>(n, INT_MAX / 2));
        queue<pair<int, int>> q;
        int ans = INT_MAX;

        q.push({0, 0});
        distance[0][0] = 0;

        while (!q.empty())
        {
            auto t = q.front();
            q.pop();
            int x = t.first / n, y = t.first % n;

            if (x == m - 1 && y == n - 1)
                ans = min(ans, t.second);

            for (int i = 0; i < 4; i++)
            {
                int r = x + dx[i], c = y + dy[i];
                if (r >= 0 && r < m && c >= 0 && c < n)
                {
                    if (moveTime[r][c] >= distance[x][y])
                    {
                        if (distance[r][c] <= moveTime[r][c] + 1)
                            continue;
                        distance[r][c] = moveTime[r][c] + 1;
                        q.push({r * n + c, distance[r][c]});
                    }
                    else
                    {
                        if (distance[r][c] <= distance[x][y] + 1)
                            continue;
                        distance[r][c] = distance[x][y] + 1;
                        q.push({r * n + c, distance[r][c]});
                    }
                }
            }
        }

        return ans;
    }
};
// @lc code=end

复杂度分析

时间复杂度：O(m * n)，其中 m 和 n 分别表示二维数组 moveTime 的长度和宽度。

空间复杂度：O(m * n)，其中 m 和 n 分别表示二维数组 moveTime 的长度和宽度。

题目3：3342. 到达最后一个房间的最少时间 II

思路

题目要计算从左上角到右下角的最短路，这可以用 Dijkstra 算法解决。

设从起点走到 (i,j) 的最短路为 distance[i][j]。

那么从 (i,j) 走到相邻格子 (x,y)，到达 (x,y) 的时间为 max(dis[i][j],moveTime[x][y])+time。

对于本题，由于每走一步 time 都会在 1,2 之间变化，联系国际象棋棋盘，(i+j) 的奇偶性就决定了 time，即 time=(i+j)mod2+1。

由于一定可以从起点走到终点，我们可以在循环中判断，只要出堆的点是终点，就立刻返回 dis[m−1][n−1]。

代码

/*
 * @lc app=leetcode.cn id=3342 lang=cpp
 *
 * [3342] 到达最后一个房间的最少时间 II
 */

// @lc code=start
class Solution
{
private:
    const int dx[4] = {0, 1, 0, -1};
    const int dy[4] = {1, 0, -1, 0};

public:
    int minTimeToReach(vector<vector<int>> &moveTime)
    {
        int m = moveTime.size(), n = m ? moveTime[0].size() : 0;

        // distance[i][j]记录从节点(0,0)到当前节点(i,j)的最短路径
        vector<vector<int>> distance(m, vector<int>(n, INT_MAX));
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;

        pq.emplace(0, 0, 0);
        distance[0][0] = 0;

        while (1)
        {
            auto [dis, x, y] = pq.top();
            pq.pop();

            if (x == m - 1 && y == n - 1)
                return dis;

            if (dis > distance[x][y])
                continue;

            for (int i = 0; i < 4; i++)
            {
                int r = x + dx[i], c = y + dy[i];
                if (r >= 0 && r < m && c >= 0 && c < n)
                {
                    int new_dis = max(dis, moveTime[r][c]) + (x + y) % 2 + 1;
                    if (new_dis < distance[r][c])
                    {
                        distance[r][c] = new_dis;
                        pq.emplace(new_dis, r, c);
                    }
                }
            }
        }
    }
};
// @lc code=end

复杂度分析

时间复杂度：O(m * n * log(m * n))，其中 m 和 n 分别表示二维数组 moveTime 的长度和宽度。

空间复杂度：O(m * n)，其中 m 和 n 分别表示二维数组 moveTime 的长度和宽度。

题目4：3343. 统计平衡排列的数目

思路

多重集排列数 + 计数 DP。

题解：https://leetcode.cn/problems/count-number-of-balanced-permutations/solutions/2975507/duo-zhong-ji-pai-lie-shu-ji-shu-dppython-42ky/

代码

/*
 * @lc app=leetcode.cn id=3343 lang=cpp
 *
 * [3343] 统计平衡排列的数目
 */

// @lc code=start
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];
        int total = 0;
        for (char c : num)
        {
            cnt[c - '0']++;
            total += c - '0';
        }

        if (total % 2)
            return 0;

        // 原地求前缀和
        partial_sum(cnt, cnt + 10, cnt);

        int n = num.size(), n1 = n / 2;
        vector<vector<vector<int>>> memo(10, vector(n1 + 1, vector<int>(total / 2 + 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;
            int c = cnt[i] - (i ? cnt[i - 1] : 0);
            int left2 = cnt[i] - left1;
            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[n1] * F[n - n1] % MOD * dfs(dfs, 9, n1, total / 2) % MOD;
    }
};
// @lc code=end

复杂度分析

时间复杂度：O(n2S)，其中 n 为字符串 num 的长度，S 为字符串 num 的数字和的一半，这不超过 9n/2。注意本题要把状态 i 和枚举 k 结合起来看，这二者一起是 O(n) 的。

空间复杂度：O(DnS)，其中 D=10。保存多少状态，就需要多少空间。


http://www.kler.cn/a/382060.html

相关文章：

  • 链接数据Linked Data的深层解读
  • docker 容器的基本使用
  • 自动驾驶控制算法-横向误差微分方程LQR前馈控制
  • ChatGPT之父：奥尔特曼
  • ubuntu22.04.5本地apt源部署
  • C++ 杨辉三角 - 力扣（LeetCode）
  • Flutter中有趣的级联语法
  • 蓝桥杯真题——三角回文数（C语言）
  • PCL 点云配准 精度评价指标均方根误差（RMSE）
  • ASP .NET CORE 6 在项目中集成WatchDog开源项目
  • 社区养老服务小程序ssm+论文源码调试讲解
  • Mac M1 Docker创建Rocketmq集群并接入Springboot项目
  • 《Keras3 深度学习初探：开启Keras3 深度学习之旅》
  • 关注AI技术的应用前景，抓住未来科技发展的机遇！
  • 闪存学习_2：Flash-Aware Computing from Jihong Kim
  • 蓝桥杯练习笔记（二十-日期问题）
  • Docker篇（数据卷）
  • GaussDB的向量化处理技术
  • uniapp推送配置流程
  • 高科技行业知识库搭建：驱动创新与效率的双引擎
  • 【大咖云集，院士出席 | ACM独立出版】第四届大数据、人工智能与风险管理国际学术会议 (ICBAR 2024，11月15-17日)--冬季主会场
  • AWTK-WEB 新版改动细节
  • 一篇文章理解CSS垂直布局方法
  • 【nlp】USAD异常检测
  • RabbitMQ 七种工作模式介绍
  • SpringBoot旋律：打造现代Web音乐平台