leetcode 99场双周赛

2578. 最小和分割 – 力扣(LeetCode)

给你一个正整数 num ,请你将它分割成两个非负整数 num1 和 num2 ,满足:

num1 和 num2 直接连起来,得到 num 各数位的一个排列。
换句话说,num1 和 num2 中所有数字出现的次数之和等于 num 中所有数字出现的次数。
num1 和 num2 可以包含前导 0 。
请你返回 num1 和 num2 可以得到的和的 最小 值。

注意:

num 保证没有前导 0 。
num1 和 num2 中数位顺序可以与 num 中数位顺序不同。

示例 1:

输入:num = 4325
输出:59
解释:我们可以将 4325 分割成 num1 = 24 和 num2 = 35 ,和为 59 ,59 是最小和。
示例 2:

输入:num = 687
输出:75
解释:我们可以将 687 分割成 num1 = 68 和 num2 = 7 ,和为最优值 75 。

提示:

10 <= num <= 109

思路:

贪心排序即可,我们只需要将数字先转成字符串,然后排序后对奇数位偶数位分别累加,就行,唯一需要注意的是字符串需要-'0'

  • 时间复杂度leetcode 99场双周赛,主要在排序上
  • 空间复杂度leetcode 99场双周赛
class Solution {
public:
    int splitNum(int num) {
        string s = to_string(num);
        sort(s.begin(), s.end());
        //687 678 68 + 7 = 75 2345 24 + 35
        int n = s.size();
        int x = 0, y = 0;
        for(int i = 0; i < n; i += 2)
        {
            x = x * 10 + s[i] - '0';
        }
        for(int i = 1; i < n; i += 2)
        {
            y = y * 10 + s[i] - '0';
        }
        return x + y;
    }
};

2579. 统计染色格子数 – 力扣(LeetCode)

有一个无穷大的二维网格图,一开始所有格子都未染色。给你一个正整数 n ,表示你需要执行以下步骤 n 分钟:

  • 第一分钟,将 任一 格子染成蓝色。
  • 之后的每一分钟,将与蓝色格子相邻的 所有 未染色格子染成蓝色。

下图分别是 1、2、3 分钟后的网格图。

请你返回 n 分钟之后 被染色的格子 数目。

示例 1:

输入:n = 1
输出:1
解释:1 分钟后,只有 1 个蓝色的格子,所以返回 1 。

示例 2:

输入:n = 2
输出:5
解释:2 分钟后,有 4 个在边缘的蓝色格子和 1 个在中间的蓝色格子,所以返回 5 。

提示:

  • 1 <= n <= 105
思路:

这道题就是找规律写通项表达式的题目,我的思路是可以从中间往上和往下看到两个等差数列求和,最后减去中间那排就行,需要注意的是会爆int,直接转longlong即可

  • 时间复杂度leetcode 99场双周赛
  • 空间复杂度leetcode 99场双周赛
class Solution {
public:
    long long coloredCells(int n) {
        
        return (long long)2 * (n ) * (n) - (2 * n - 1);
    }
};

2580. 统计将重叠区间合并成组的方案数 – 力扣(LeetCode)

给你一个二维整数数组 ranges ,其中 ranges[i] = [starti, endi] 表示 startiendi 之间(包括二者)的所有整数都包含在第 i 个区间中。

你需要将 ranges 分成 两个 组(可以为空),满足:

  • 每个区间只属于一个组。
  • 两个有 交集 的区间必须在 同一个 组内。

如果两个区间有至少 一个 公共整数,那么这两个区间是 有交集 的。

  • 比方说,区间 [1, 3][2, 5] 有交集,因为 23 在两个区间中都被包含。

请你返回将 ranges 划分成两个组的 总方案数 。由于答案可能很大,将它对 109 + 7 取余 后返回。

示例 1:

输入:ranges = [[6,10],[5,15]]
输出:2
解释:
两个区间有交集,所以它们必须在同一个组内。
所以有两种方案:
- 将两个区间都放在第 1 个组中。
- 将两个区间都放在第 2 个组中。

示例 2:

输入:ranges = [[1,3],[10,20],[2,5],[4,8]]
输出:4
解释:
区间 [1,3] 和 [2,5] 有交集,所以它们必须在同一个组中。
同理,区间 [2,5] 和 [4,8] 也有交集,所以它们也必须在同一个组中。
所以总共有 4 种分组方案:
- 所有区间都在第 1 组。
- 所有区间都在第 2 组。
- 区间 [1,3] ,[2,5] 和 [4,8] 在第 1 个组中,[10,20] 在第 2 个组中。
- 区间 [1,3] ,[2,5] 和 [4,8] 在第 2 个组中,[10,20] 在第 1 个组中。

提示:

  • 1 <= ranges.length <= 105
  • ranges[i].length == 2
  • 0 <= starti <= endi <= 109
思路:

这道题实际上是区间合并问题分组问题的缝合,我们先把能够合并的区间求出来记作cnt,然后组合,组合出答案是leetcode 99场双周赛次,不过好像cnt不是很多,虽然我写了个快速幂,用处不大,而且写的好像不够简洁,所以附上两个写法

  • 时间复杂度leetcode 99场双周赛,主要是排序
  • 空间复杂度leetcode 99场双周赛
class Solution {
public:
    int countWays(vector<vector<int>>& ranges) {
        int n = ranges.size();
        int cnt = 0;
        sort(ranges.begin(), ranges.end());
        int l = ranges[0][0], r = ranges[0][1];
        const int MOD = 1e9 + 7;
        for(int i = 1; i < n; i ++)
        {
            if(ranges[i][0] > r)
            {
                cnt ++;
                l = ranges[i][0], r = ranges[i][1];
            }
            else
            {
                r = max(r, ranges[i][1]);
            }
        }
        cnt += 1;
        cout << cnt << endl;
       long long res = 1;
        long long a = 2;
        while(cnt)
        {
            if(cnt & 1) res = (res * a) % MOD;
            a = (a * a) % MOD; // 对 a 取模
            cnt >>= 1;
        }
        return res;

    }
};
//简化版本
class Solution {
public:
    int countWays(vector<vector<int>>& ranges) {
        sort(ranges.begin(), ranges.end());
        int n = ranges.size();
        int maxr = ranges[0][1];
        const int MOD = 1e9 + 7;
        long long ans = 2;
        for(int i = 1; i < n; i ++)
        {
            if(ranges[i][0] > maxr)
                ans = ans * 2 % MOD;
            maxr = max(maxr, ranges[i][1]);
        }
        return ans;

    }
};

2581. 统计可能的树根数目 – 力扣(LeetCode)

Alice 有一棵 n 个节点的树,节点编号为 0n - 1 。树用一个长度为 n - 1 的二维整数数组 edges 表示,其中 edges[i] = [ai, bi] ,表示树中节点 aibi 之间有一条边。

Alice 想要 Bob 找到这棵树的根。她允许 Bob 对这棵树进行若干次 猜测 。每一次猜测,Bob 做如下事情:

  • 选择两个 不相等 的整数 uv ,且树中必须存在边 [u, v]
  • Bob 猜测树中 uv父节点

Bob 的猜测用二维整数数组 guesses 表示,其中 guesses[j] = [uj, vj] 表示 Bob 猜 ujvj 的父节点。

Alice 非常懒,她不想逐个回答 Bob 的猜测,只告诉 Bob 这些猜测里面 至少k 个猜测的结果为 true

给你二维整数数组 edges ,Bob 的所有猜测和整数 k ,请你返回可能成为树根的 节点数目 。如果没有这样的树,则返回 0

示例 1:

输入:edges = [[0,1],[1,2],[1,3],[4,2]], guesses = [[1,3],[0,1],[1,0],[2,4]], k = 3
输出:3
解释:
根为节点 0 ,正确的猜测为 [1,3], [0,1], [2,4]
根为节点 1 ,正确的猜测为 [1,3], [1,0], [2,4]
根为节点 2 ,正确的猜测为 [1,3], [1,0], [2,4]
根为节点 3 ,正确的猜测为 [1,0], [2,4]
根为节点 4 ,正确的猜测为 [1,3], [1,0]
节点 0 ,1 或 2 为根时,可以得到 3 个正确的猜测。

示例 2:

输入:edges = [[0,1],[1,2],[2,3],[3,4]], guesses = [[1,0],[3,4],[2,1],[3,2]], k = 1
输出:5
解释:
根为节点 0 ,正确的猜测为 [3,4]
根为节点 1 ,正确的猜测为 [1,0], [3,4]
根为节点 2 ,正确的猜测为 [1,0], [2,1], [3,4]
根为节点 3 ,正确的猜测为 [1,0], [2,1], [3,2], [3,4]
根为节点 4 ,正确的猜测为 [1,0], [2,1], [3,2]
任何节点为根,都至少有 1 个正确的猜测。

提示:

  • edges.length == n - 1
  • 2 <= n <= 105
  • 1 <= guesses.length <= 105
  • 0 <= ai, bi, uj, vj <= n - 1
  • ai != bi
  • uj != vj
  • edges 表示一棵有效的树。
  • guesses[j] 是树中的一条边。
  • guesses 是唯一的。
  • 0 <= k <= guesses.length
思路:

换根dp,这道题可以用换根dp的思路来做,我们可以求出以leetcode 99场双周赛号点位根的数,有多少询问是正确的即为leetcode 99场双周赛,如果我们按照这个思路去枚举每个点,时间复杂度就爆炸了,所以我们考虑优化做法,注意到如果xy之间有一条边相连,实际上对于非x,yy,x的边,结果都不会有变化,因为他们的父节点还是那个,但是这两个的关系实际上就互换了,所以因此,从leetcode 99场双周赛出发,再次 DFS 这棵树,从节点leetcode 99场双周赛 递归到节点 leetcode 99场双周赛时:

  • 如果有猜测leetcode 99场双周赛,那么猜对次数减一;
  • 如果有猜测leetcode 99场双周赛,那么猜对次数加一。

除此之外,我们还需要记录一个leetcode 99场双周赛的关系,我们可以用set来存储,但是set不能存储pair类型,所以我们可以用位运算来实现

  • 时间复杂度leetcode 99场双周赛,leetcode 99场双周赛为边的长度,leetcode 99场双周赛为询问的长度
  • 空间复杂度leetcode 99场双周赛
class Solution {
public:
    int rootCount(vector<vector<int>>& edges, vector<vector<int>>& guesses, int k) {
        vector<vector<int>> g(edges.size() + 1);
        unordered_set<long> s;
        for(auto&e : edges)
        {
            int x = e[0], y = e[1];
            g[x].push_back(y);
            g[y].push_back(x);
        }
        for(auto&e : guesses)
        {
            s.insert((long)e[0] << 32 | e[1]);
        }
        int ans = 0, cnt0 = 0;
        function<void(int, int)> dfs = [&](int x, int fa){
            for(int y : g[x])
            {
                if(y != fa)
                {
                    cnt0 += s.count((long)x << 32 | y);
                    dfs(y, x);
                }
            }
        };
        dfs(0, -1);
        function<void(int, int, int)> reroot = [&](int x, int fa, int cnt)
        {
            ans += cnt >= k;
            for(int y : g[x])
            {
                if(y != fa)
                {
                    reroot(y, x, cnt - s.count((long) x << 32 | y) + s.count((long) y << 32 | x));
                }
            }
        };
        reroot(0, -1, cnt0);
        return ans;
    }
};

版权声明:本文为博主作者:echo-su原创文章,版权归属原作者,如果侵权,请联系我们删除!

原文链接:https://blog.csdn.net/m0_53201842/article/details/136122866

共计人评分,平均

到目前为止还没有投票!成为第一位评论此文章。

(0)
社会演员多的头像社会演员多普通用户
上一篇 2024年2月19日
下一篇 2024年2月19日

相关推荐

此站出售,如需请站内私信或者邮箱!