前言
我不会再闷闷不乐了，那种像是紧紧揪着胸口的悲伤，甚至是快要夺眶而落的泪水，全都是塑造出如今的我的东西。
烦恼，焦躁，痛苦，喜悦，这些也全都不可或缺。
现在存在于这里的，不是别人，而是货真价实的「我 珂朵莉」
没错 唯有现在...
整体评价
说真的，挺难的，没有一题是水题，而且每一题都可以一题多解。
真的是一场值得纪念和回味的比赛。
非常推荐.
1. 有效时间的数目
第一时间想的对？进行枚举+检验。
然后就用dfs全枚举了， 感觉对于t1而言，码量有点大，但是安全踏实。
说真的，这题在写的过程，闪过位数DP的影子，还好总方案不大，dfs深度也小。
Java
class Solution {
// 合法性校验
boolean valid(char[] buf) {
int hour = (buf[0] - '0') * 10 + buf[1] - '0';
if (hour < 0 || hour >= 24) return false;
int min = (buf[3] - '0') * 10 + buf[4] - '0';
if (min < 0 || min >= 60) return false;
return true;
}
// dfs 全枚举
int dfs(char[] buf, int s) {
if (buf.length == s) {
return valid(buf) ? 1 : 0;
}
if (s == 2) {
return dfs(buf, s + 1);
}
if (buf[s] == '?') {
int res = 0;
for (int i = 0; i <= 9; i++) {
buf[s] = (char)('0' + i);
res += dfs(buf, s + 1);
}
buf[s] = '?';
return res;
} else {
return dfs(buf, s + 1);
}
}
public int countTime(String time) {
char[] buf = time.toCharArray();
return dfs(buf, 0);
}
}其实小时和分钟是独立，同时这边通过分类讨论+枚举，来计数，不过这个超级容易错，T_T.
go
func countTime(time string) int {
stime := []byte(time)
countHour := func() int {
if stime[0] == '?' && stime[1] == '?' {
return 24
} else if stime[0] == '?' && stime[1] != '?' {
if stime[1] <= '3' {
return 3
}
return 2
} else if stime[0] != '?' && stime[1] == '?' {
if stime[0] == '2' {
return 4
}
return 10
}
return 1
}
countMinute := func() int {
if stime[3] == '?' && stime[4] == '?' {
return 60
} else if stime[3] == '?' && stime[4] != '?' {
return 6
} else if stime[3] != '?' && stime[4] == '?' {
return 10
}
return 1
}
return countHour() * countMinute()
}2. 二的幂数组中查询范围内的乘积
差点想 前缀乘积 + 逆元，幸好转念一想，一个数字的二进制表示最多才几个，直接莽就行.
Java
class Solution {
public int[] productQueries(int n, int[][] queries) {
List<Integer> arr = new ArrayList<>();
// 二进制拆解
int cnt = 0;
while (n > 0) {
int v = n % 2;
if (v == 1) {
arr.add(1 << cnt);
}
n /= 2;
cnt++;
}
int m = queries.length;
int[] res = new int[m];
for (int i = 0; i < m; i++) {
int[] q = queries[i];
long tx = 1l;
for (int j = q[0]; j <= q[1]; j++) {
tx = tx * arr.get(j);
tx = tx % 10_0000_0007l;
}
res[i] = (int)tx;
}
return res;
}
}3. 最小化数组中的最大值
这类题，典型的二分题，哈哈。
现在聚焦的焦点在于，check函数如何实现？
珂朵莉MM在比赛用的正向贪心，实际上逆向贪心更好。
实际上，正向+逆向贪心，都是可以的。
Java
class Solution {
// *) 正向验证
boolean check(int[] nums, int k) {
long[] arr = new long[nums.length];
for (int i = 0; i < nums.length; i++) {
arr[i] = nums[i];
}
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] > k) return false;
if (arr[i] < k) {
long d = k - arr[i];
arr[i] += d;
arr[i + 1] -= d;
}
}
return arr[arr.length - 1] <= k;
}
public int minimizeArrayValue(int[] nums) {
// 二分吗？
int min = nums[0], max = nums[0];
for (int i = 0; i < nums.length; i++) {
min = Math.min(min, nums[i]);
max = Math.max(max, nums[i]);
}
int ans = 0;
int l = min, r = max;
while (l <= r) {
int m = l + (r - l) / 2;
if (check(nums, m)) {
ans = m;
r = m - 1;
} else {
l = m + 1;
}
}
return ans;
}
}
4. 创建价值相同的连通块
因子枚举+树形DP
其实因子枚举，相对容易想到，为啥这么说呢？ 因为总和确定S，每个连通块和相等s，则s必定是S的因子，且s并不多，起一定要节点最大值.
由于树结构的特殊性， 要连通块拆分，最好的思路从叶节点出发。
从叶节点出发，有两类思路，一种是树形DP，一种是拓扑排序（从叶节点往内节点逐步构建）。
还有一种思路，就是前几周的并查集+逆序构建。
不过这题，因子枚举+树形DP可行。
Java
class Solution {
int[] nums;
List<List<Integer>> adj = new ArrayList<>();
// *) 树形DP，总和 < k, 则继续传递，刚好=k, 则自成一个连通量，> k, 则失败
int dfs(int root, int fa, int k) {
int dv = nums[root];
List<Integer> es = adj.get(root);
for (int v: es) {
if (v == fa) continue;
int t = dfs(v, root, k);
if (t == -1) return -1;
dv += t;
if (dv > k) return -1;
}
if (dv > k) return -1;
return dv % k;
}
public int componentValue(int[] nums, int[][] edges) {
int n = nums.length;
this.nums = nums;
int tsum = 0, maxV = 0;
for (int i = 0; i < n; i++) {
adj.add(new ArrayList<>());
tsum += nums[i];
maxV = Math.max(maxV, nums[i]);
}
for (int[] e: edges) {
adj.get(e[0]).add(e[1]);
adj.get(e[1]).add(e[0]);
}
// *) 枚举因子
for (int i= maxV; i <= tsum; i++) {
if (tsum % i == 0) {
if (dfs(0, -1, i) == 0) {
return (tsum / i) - 1;
}
}
}
return 0;
}
}
珂朵莉MM 在比赛中，尝试用了并查集，借助优先队列(延迟删除)，对边（点和点，点和连通分量）进行贪心合并。
最后的结果是WA，基本上一看错误case，就宣告了这个算法思路是错误的。
评论 (2)
