chatgpt入口,网络seo推广培训,网站推广到海外怎么做,平阴县网站建设2578. 最小和分割 - 力扣#xff08;LeetCode#xff09;
给你一个正整数 num #xff0c;请你将它分割成两个非负整数 num1 和 num2 #xff0c;满足#xff1a;
num1 和 num2 直接连起来#xff0c;得到 num 各数位的一个排列。 换句话说#xff0c;num1 和 num2 中…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
时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn),主要在排序上空间复杂度 O ( 1 ) O(1) O(1)
class Solution {
public:int splitNum(int num) {string s to_string(num);sort(s.begin(), s.end());//687 678 68 7 75 2345 24 35int 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即可
时间复杂度 O ( 1 ) O(1) O(1)空间复杂度 O ( 1 ) O(1) O(1)
class Solution {
public:long long coloredCells(int n) {return (long long)2 * (n ) * (n) - (2 * n - 1);}
};2580. 统计将重叠区间合并成组的方案数 - 力扣LeetCode
给你一个二维整数数组 ranges 其中 ranges[i] [starti, endi] 表示 starti 到 endi 之间包括二者的所有整数都包含在第 i 个区间中。
你需要将 ranges 分成 两个 组可以为空满足
每个区间只属于一个组。两个有 交集 的区间必须在 同一个 组内。
如果两个区间有至少 一个 公共整数那么这两个区间是 有交集 的。
比方说区间 [1, 3] 和 [2, 5] 有交集因为 2 和 3 在两个区间中都被包含。
请你返回将 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 105ranges[i].length 20 starti endi 109
思路:
这道题实际上是区间合并问题和分组问题的缝合,我们先把能够合并的区间求出来记作cnt,然后组合,组合出答案是 2 c n t 2^{cnt} 2cnt次,不过好像cnt不是很多,虽然我写了个快速幂,用处不大,而且写的好像不够简洁,所以附上两个写法
时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn),主要是排序空间复杂度 O ( 1 ) O(1) O(1)
class Solution {
public:int countWays(vectorvectorint 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(vectorvectorint 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 个节点的树节点编号为 0 到 n - 1 。树用一个长度为 n - 1 的二维整数数组 edges 表示其中 edges[i] [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。
Alice 想要 Bob 找到这棵树的根。她允许 Bob 对这棵树进行若干次 猜测 。每一次猜测Bob 做如下事情
选择两个 不相等 的整数 u 和 v 且树中必须存在边 [u, v] 。Bob 猜测树中 u 是 v 的 父节点 。
Bob 的猜测用二维整数数组 guesses 表示其中 guesses[j] [uj, vj] 表示 Bob 猜 uj 是 vj 的父节点。
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 - 12 n 1051 guesses.length 1050 ai, bi, uj, vj n - 1ai ! biuj ! vjedges 表示一棵有效的树。guesses[j] 是树中的一条边。guesses 是唯一的。0 k guesses.length
思路:
换根dp,这道题可以用换根dp的思路来做,我们可以求出以 0 0 0号点位根的数,有多少询问是正确的即为 c n t 0 cnt0 cnt0,如果我们按照这个思路去枚举每个点,时间复杂度就爆炸了,所以我们考虑优化做法,注意到如果x和y之间有一条边相连,实际上对于非x,y和y,x的边,结果都不会有变化,因为他们的父节点还是那个,但是这两个的关系实际上就互换了,所以因此从 0 0 0出发再次 DFS 这棵树从节点 x x x 递归到节点 y y y时
如果有猜测 [ x , y ] [x, y] [x,y]那么猜对次数减一如果有猜测 [ y , x ] [y,x] [y,x]那么猜对次数加一。
除此之外,我们还需要记录一个 x 与 y x与y x与y的关系,我们可以用set来存储,但是set不能存储pair类型,所以我们可以用位运算来实现
时间复杂度 O ( n m ) O(n m) O(nm), n n n为边的长度, m m m为询问的长度空间复杂度 O ( n ) O(n) O(n)
class Solution {
public:int rootCount(vectorvectorint edges, vectorvectorint guesses, int k) {vectorvectorint g(edges.size() 1);unordered_setlong s;for(autoe : edges){int x e[0], y e[1];g[x].push_back(y);g[y].push_back(x);}for(autoe : guesses){s.insert((long)e[0] 32 | e[1]);}int ans 0, cnt0 0;functionvoid(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);functionvoid(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;}
};
