leetcode 第 279 场算法比赛

零、背景

肠胃不舒服，本来不打算参加比赛的，睡一觉好了不少，便参加比赛了。

睡醒的时候，已经十点三十多了，便打开电脑。

作比赛的时候，已经十点四十多了。

题目还算简单，只是中间我有几个笔误，浪费不少时间。

一、对奇偶下标分别排序

题意：偶数位置的值升序排序，奇数位置的值偶数排序。

思路：按奇偶位置拆分为两个数组，分别排序，然后在组合起来。

注意事项：偶数位置的元素可能比奇数位置的元素多一个。

二、重排数字的最小值

题意：给一个整数，要求对整数数字重排列，使整数的值最小。

思路：分三种情况。

1、零直接返回零。
2、正数，从小到大排序，有前导零时需只要到第一个非0的位置，与第一个位置交换。
3、负数，从大到小排序。

三、设计位集

题意：要求设计一个 bitset 数据结构，支持修改、反转、查询等操作。

思路：由于存在翻转 和 查询整个 bitset 的值，暴力做不知道会不会超时，所以我直接选择了最优方法。

我使用双 Buf 的方法，把翻转前和翻转后的答案都维护起来。
每个数据结构中都储存 1 的个数，方便快速查询。

复杂度分别如下：

初始化：O(n) 申请内存。
fix ：O(1) 修改一位
unfix：O(1) 修改一位
flip：O(1) 修改双 buf 指针
all：O(1) 与 1 的个数比较
one：O(1) 与 1 的个数比较
count：O(1) 返回 1 的个数
toString：O(1) 返回数据结构中的字符串

四、移除所有载有违禁货物车厢所需的最少时间

题意：给一个 01 数组，现在需要把所有的 1 删除。
可以从两边依次删除一个数字，代价是 1。
也可以从中间删除删除一个数字，代价是 2。
求最小删除代价。

思路：枚举中间不删除的区间，暴力做的复杂度是O(n^2)。

写出方程后，如下

f(i, j) = befor(i) + center(i, j) * 2 + after(j)

假设 j 固定，则方程转化为

F(j) = min(befor(i) + center(i, j) * 2) + after(j)

再看 j + 1 的方程

F(j+1) = min(befor(i) + center(i, j+1) * 2) + after(j)

针对 第 j+1 位置的值，可以分情况讨论。

如果 V(j+1) 为 0，则放在中间时不需要删除，故答案可以更小 F(j) = F(j+1) + 1。

如果 V(j+1) 为 1，则放在中间时依旧需要删除，代价却加1，故答案是F(j+1) = F(j) + 1。
考虑到中间可能不存在，故也可能不需要加 1.

F(j+1) = min(F(j) + 1, allDel)

就这样，我们通过分情况就可以通过 F(j) 的答案计算出 F(j+1) 的答案来。

具体代码非常简单，大家可以看我 B 站的视频或者 github 上的源码。

五、最后

这次比赛题目还算简单，不过我每道题都出现了笔误，排名就比较靠后了。

第三题 Bitset 你是怎么做的呢？
第四题动态规划你又是怎么做的呢？

《完》

-EOF-

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