没参加。
https://leetcode.cn/problems/number-of-valid-clock-times/solution/
这里灵佬使用 go 的 continue label 是否漂亮。
func count(time string, limit int) (ans int) {
next:
for i := 0; i < limit; i++ {
for j, c := range fmt.Sprintf("%02d", i) { // 检验是否匹配
if time[j] != '?' && byte(c) != time[j] {
continue next
}
}
ans++
}
return
}
func countTime(time string) int {
return count(time[:2], 24) * count(time[3:], 60)
}注意：
- go 的
continue label会触发循环的增量条件并且做判断
https://leetcode.cn/problems/minimize-maximum-of-array/
见到“最大最小值”，我都想不到二分了。
class Solution {
public:
int minimizeArrayValue(vector<int>& nums) {
int n = nums.size();
int maxv = *max_element(nums.begin(), nums.end());
int l = 0, r = maxv;
auto check = [&](int x) -> bool {
long extra = 0;
for (int i = n - 1; i > 0; -- i)
extra = max(nums[i] - x + extra, 0L);
return nums[0] + extra <= x;
};
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
};灵佬还有另一种贪心思路。
// nums[0] 决定下限
// nums[1] 若大于 nums[0] ，则可以匀一匀
// nums[2] 与 nums[1] 同理，前三个匀一匀
func minimizeArrayValue(nums []int) (ans int) {
s := 0
for i, x := range nums {
s += x
ans = max(ans, (s+i)/(i+1)) // 上取整
}
return
}
func max(a, b int) int { if b > a { return b }; return a }https://leetcode.cn/problems/create-components-with-same-value/
// 见到本题我想的是“如何切”
// 实际上，重点在于“能不能切为 x 块”，如何切不重要
// 于是我把自己局限在了如何搜索，切哪里，其实这不是重点
class Solution {
public:
int componentValue(vector<int> &nums, vector<vector<int>> &edges) {
vector<vector<int>> g(nums.size());
for (auto &e : edges) {
int x = e[0], y = e[1];
g[x].push_back(y);
g[y].push_back(x);
}
// 这个 dfs 讨论得很精妙
// 如果子树恰好切成 target ，则返回 0 ，不参与子树之上的 sum
int target;
function<int(int, int)> dfs = [&](int x, int fa) {
int sum = nums[x]; // 价值
for (int y : g[x])
if (y != fa) {
int res = dfs(y, x);
if (res < 0) return -1; // 子树不能切成比 target 小
sum += res;
}
if (sum > target) return -1;
return sum < target ? sum : 0; // 恰好切成 target 则返回 0
};
int total = accumulate(nums.begin(), nums.end(), 0);
int mx = *max_element(nums.begin(), nums.end());
for (int i = total / mx;; --i) // 尝试切成 i 块
if (total % i == 0) {
target = total / i;
if (dfs(0, -1) == 0) return i - 1; // 切成 i 则需要去掉 i-1 条边
}
}
};