leetcode 第 369 场算法比赛

零、背景

昨天晚上与旧同事和前同事聚餐，聊到半夜11点多，之后又随万圣节的岩友去烧烤，吃到两点多。

当然，这些不是理由。
今天比赛第三题状态转移方程没写就直接写代码了，结果被卡了。
最后老老实实的定义状态与写状态方程，最后才通过。

一、找出数组中的 K-or 值

题意：给一个数组，如果某个二进制位 1 出现的次数超过 K 次，答案的此二进制位才是 1，求最终答案。

思路：统计各二进制 1 出现的次数，判断是否大于 K 即可。

二、数组的最小相等和

题意：给两个数组，数组中的 0 需要替换为正整数，问替换后是否可以使得两个数组和相等。

思路：0 最小可以替换的正整数是 1，最大无限制。
所以 0 可以按 1 计算两个数组的最小数组和，根据是否出现 0 可以计算出两个数组和的区间。
分四种情况判断两个区间是否有交集即可。

三、使数组变美的最小增量运算数

题意：给一个数组，每次操作可以把一个位置的值加1，求最小操作把数组变为美丽数组。
美丽数组：如果数组中任何长度 大于或等于 3 的子数组，其 最大 元素都大于或等于 k ，则认为数组是一个 美丽数组 。

思路：动态规划。

状态定义：
f(i) 第 i 个元素进行加法操作，使得前缀变成美丽数组的最优答案。
F(i) 前 i 个元素进行加法操作，使得前缀变成美丽数组的最优答案。

状态转移方程：

f(i) = min(val(i)-k, 0) + F(i-1)  
F(i) = min(f(i), f(i-1), f(i-2));

解释：
f(i) 进行加法操作时，以位置 i 为后缀的子数组都满足要求。
其他子数组的答案可以上个位置的最优答案 F(i-1) 来计算。

F(i) 的最优答案是最近 3 个元素为修改位置时最小的那个。

四、收集所有金币可获得的最大积分

题意：给一个有根无向树，树的节点都有一定的积分，问如何选择才能得到最大积分。
选择1：折半选择，即当前子树的积分都减半，然后选择当前子树根节点的积分，之后进入子树选择。
选择2：比较选择，可以得到coins[i] - k分，如果分数是负的，就扣分。

思路：树形DP。

由于有子树扣分，可以增加一个维度，代表扣分的次数，最多不超过 32 次。

状态定义：f(i, lev) 代表祖先选择 lev 次折半选择后，当前子树的最优答案。

状态转移方程如下：

f(i, lev) = min(
    coins[i]>>lev - k + ChildSum(f(j, lev)),
    coins[i]>>(lev+1) + ChildSum(f(j, lev+1)),
)

五、最后

这次比赛其实不难，不过我差点就翻车了。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code