企业案例网站,网站 图文混编,网站高端,网站需要数据库吗文章目录双周赛99[6312. 最小和分割](https://leetcode.cn/problems/split-with-minimum-sum/)贪心[6311. 统计染色格子数](https://leetcode.cn/problems/count-total-number-of-colored-cells/)找规律[6313. 统计将重叠区间合并成组的方案数](https://leetcode.cn/problems/c…
文章目录双周赛99[6312. 最小和分割](https://leetcode.cn/problems/split-with-minimum-sum/)贪心[6311. 统计染色格子数](https://leetcode.cn/problems/count-total-number-of-colored-cells/)找规律[6313. 统计将重叠区间合并成组的方案数](https://leetcode.cn/problems/count-ways-to-group-overlapping-ranges/)相似[56. 合并区间](https://leetcode.cn/problems/merge-intervals/)[6314. 统计可能的树根数目](https://leetcode.cn/problems/count-number-of-possible-root-nodes/)换根DP双周赛99
6312. 最小和分割
难度简单4
给你一个正整数 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
贪心
class Solution {// 思考 1越高位的数字对结果的影响越大所以优先排列最小的数字// 思考 2如果划分两个数字的长度不均会放大最终的值// 算法对数字排序从小到大分别排列到两个数字上。public int splitNum(int num) {char[] arr (num ).toCharArray();Arrays.sort(arr);int[] res new int[2];for(int i 0; i arr.length; i){res[i % 2] res[i % 2] * 10 (int)arr[i]-0;}return res[0] res[1];}
}6311. 统计染色格子数
难度中等2
有一个无穷大的二维网格图一开始所有格子都未染色。给你一个正整数 n 表示你需要执行以下步骤 n 分钟
第一分钟将 任一 格子染成蓝色。之后的每一分钟将与蓝色格子相邻的 所有 未染色格子染成蓝色。
下图分别是 1、2、3 分钟后的网格图。 请你返回 n 分钟之后 被染色的格子 数目。
示例 1
输入n 1
输出1
解释1 分钟后只有 1 个蓝色的格子所以返回 1 。示例 2
输入n 2
输出5
解释2 分钟后有 4 个在边缘的蓝色格子和 1 个在中间的蓝色格子所以返回 5 。提示
1 n 105
找规律
class Solution {// 斜着看其实就是n * n大小的方阵空隙里夹了一个 (n - 1) * (n - 1)的方阵public long coloredCells(int n) {// dp[1] 1 1x1// dp[2] 5 2x2 1// dp[3] 13 3x3 4// int[] dp new int[n1];// dp[1] 1;// for(int i 2; i n; i){// dp[i] i * i (i-1) * (i-1);// }// return dp[n];long a n;return a * a (a-1) * (a-1);}
}6313. 统计将重叠区间合并成组的方案数
难度中等8
给你一个二维整数数组 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
class Solution {//假设最后分成了 m 个集合那么每个集合都可以决定要在第一个组还是第二个组// 所以方案数为 2 ^ mprivate static final int MOD (int)1e9 7;public int countWays(int[][] ranges) {Arrays.sort(ranges, (a,b) - a[0] b[0] ? a[1]-b[1] : a[0] - b[0]);int ans 2;int maxR ranges[0][1];for(int[] p : ranges){if(p[0] maxR){ // 产生了新的集合 m加一ans ans * 2 % MOD;}maxR Math.max(maxR, p[1]);}return ans;}
}相似56. 合并区间
难度中等1815
以数组 intervals 表示若干个区间的集合其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间并返回 一个不重叠的区间数组该数组需恰好覆盖输入中的所有区间 。
示例 1
输入intervals [[1,3],[2,6],[8,10],[15,18]]
输出[[1,6],[8,10],[15,18]]
解释区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].示例 2
输入intervals [[1,4],[4,5]]
输出[[1,5]]
解释区间 [1,4] 和 [4,5] 可被视为重叠区间。提示
1 intervals.length 104intervals[i].length 20 starti endi 104
class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals, (a, b) - a[0] b[0] ? a[1]-b[1] : a[0]-b[0]);Listint[] list new ArrayList();int i 0;while(i intervals.length){int left intervals[i][0];int right intervals[i][1];while(i1 intervals.length right intervals[i1][0]){right Math.max(right, intervals[i1][1]);i;}list.add(new int[]{left, right});i;}int[][] res new int[list.size()][2];for(int k 0; k list.size(); k){res[k] list.get(k);}return res;}
}6314. 统计可能的树根数目
难度困难13
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] 是树中的一条边。0 k guesses.length
换根DP
题解https://leetcode.cn/problems/count-number-of-possible-root-nodes/solution/huan-gen-dppythonjavacgo-by-endlesscheng-ccwy/
class Solution {private ListInteger[] g;private SetLong s new HashSet();private int k, ans, cnt0;public int rootCount(int[][] edges, int[][] guesses, int k) {this.k k;g new ArrayList[edges.length1];Arrays.setAll(g, e - new ArrayList());for(int[] e : edges){int x e[0], y e[1];g[x].add(y);g[y].add(x); // 建图}for(int[] e : guesses){ // guesses 转换成哈希表加快查询速度s.add((long) e[0] 32 | e[1]); // 两个 4 字节数压缩成一个 8 字节数Long}dfs(0, -1);reroot(0,-1,cnt0);return ans;}private void dfs(int x, int fa){for(int y : g[x]){if(y ! fa){if(s.contains((long) x 32 | y)) // 以 0 为根时猜对了cnt0;dfs(y,x);}}}private void reroot(int x, int fa, int cnt){if(cnt k) ans;// 此时 cnt 就是以 x 为根时的猜对次数for(int y : g[x]){if(y ! fa){int c cnt;if(s.contains((long) x 32 | y)) c--;// 原来是对的现在错了if(s.contains((long) y 32 | x)) c;// 原来是对的现在错了reroot(y,x,c);}}}
}rivate void reroot(int x, int fa, int cnt){ if(cnt k) ans;// 此时 cnt 就是以 x 为根时的猜对次数 for(int y : g[x]){ if(y ! fa){ int c cnt; if(s.contains((long) x 32 | y)) c–;// 原来是对的现在错了 if(s.contains((long) y 32 | x)) c;// 原来是对的现在错了 reroot(y,x,c); } } } }
