leetcode 第 329 场算法比赛 未参赛

零、背景

除夕夜，我和另外两个同事在值班到了半夜 1 点，所以睡的有点晚。

回家后我的闹钟就关闭了，大年初一睡到了 11 点才醒来，发现比赛已经开始半个小时了，便没有参加。

PS1：旧历新的一年到了，祝大家新年快乐，比赛排名越来越靠前。

PS2：大年初一，leetcode 的每日一题竟然是最难的题，难度竟然有 2559 分。

一、交替数字和

题意：给一个数字，各位数字从最高位起交叉分配正负符号，求各位数字之和。

思路：根据数字长度计算出奇偶位的符号，求和即可。

二、根据第 K 场考试的分数排序

题意：给一个矩阵，对各行排序，要求按第 k 列的值排序。

思路：sort 即可。

三、执行逐位运算使字符串相等

题意：给一个二进制字符串，可以执行任意次规则，问是否可以得到目标字符串。
规则：选两个位置，第一个位置的新值为 OR 后的值，第二个位置的新值为 XOR 后的值。

思路：画出两个位置所有值的结果，可以得到几个结论。

0 0 => 0 0
0 1 => 1 1
1 0 => 1 1
1 1 => 1 0

结论1：有 1 个 1 后，另一个位置的值可以反转。
推论：原始值和目标值都有至少一个 1 时，就可以得到目标字符串。

结论2：两个 0 的结果还都是0。
推论：如果原始值都是0，则不能得到目标字符串。

结论2：有至少一个 1 时，结果也至少有一个1。
推论：如果目标值都是0，则不能得到目标字符串。

有了上的推论，总的结论是直接判断两个原始值和目标值是否都有 1 即可。

四、拆分数组的最小代价

题意：给一个数组，问拆分为几个子数组，才能使得子数组的积分之和最小。
数组积分：数组的大小减去数组中值出现一次的个数。

思路：数据范围只有 1000，直接动态规划做即可。

状态定义：f(n) 前 n 个数字进行拆分的最优值。
转移方程：f(n) = f(i-1) + Score(i, n)

计算 Score 需要进行集合计算，这里需要复用前一个状态的结果。
状态转移方程需要调整一下，然后两层循环即可求出结果。

f(n+i) = f(n-1) + Score(n, n+i)

五、最后

这次比赛最后一题不难，但是也不简单。

大家参加比赛了吗？做出了几道题？

加油，算法人。

《完》

-EOF-

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