Leetcode 第93场比赛回顾

零、背景

Leetcode 第 93 场比赛的题相对来说比较简单，前三道是简单计算、第四题贪心或动态规划。

我是使用动态规划过得，周围同事使用贪心过得。

下面来看看这四道题吧。

一、二进制间距

题意：给一个数字，求这个数字的二进制里面，相邻 1 的最大间距。

思路：这道题理解起来比较麻烦。

相邻 1 的意思是，有些 1 是挨着的，那么他们的间距是 1 。有些 1 之间有若干个 0 ，那么间距就是 0 的个数加一。

理解了题意，总结一下就是相邻 1 之间 0 的个数。

如果只有一个 1 ，则答案是 0 。

二、重新 排序 得到 2 的幂

题意：给一个数字，问这个数字的十进制进行排列组合，是否可以组成 2 的幂。

思路：最简单的方法是对这个数字进行递归排列组合，然后判断对应的数字是不是答案，找到则结束递归。 但是这种方法理论上会超时。

看一下数据范围，这个数字是 32 整数范围内的。

所以另一个方法是求出 32 位范围内所有 2 的整幂数字，顶多 32 个。

然后判断这个数字是不是给的数字的一个排列组合。

那怎么判断两个数字的排列组合是否相同呢？

一种方法是对数字各位进行排序，另一种是对数字各位进行统计，从 0~9 分别有多少个，然后对比是否一致。

三、优势洗牌

题意：给两个大小相等的数组 A 和 B ，数组 A 的相对优势是 A[i] > B[i] 的个数。

在数组 A 的排列中，求最大优势。

思路：这个其实就是田忌赛马。

基本思路是，自己最强的马与对方最强的马比较，如果可以打败则打，如果不能打败，则使自己最弱的马与对方最强的马打。

对应的代码实现就是，对两个数组排序，然后按照上面的规则计算出每个位置应该和谁打。

四、最低加油次数

题意：在一条直线公路上有一些加油站，每个加油站有一定量的油。

我们起初位置在原点 0 ，有一定的油量，然后要开车去目标点 target 。

问开车是否可以到达目标点，如果可以，求最少加油的次数。

注意：假设车的邮箱是无限大的。

思路：我看到这道题，首先想到的是动态规划。

定义状态： dp[i][j] 代表加了 j 次油到达第 i 个加油站时，剩余的最大油量。

这样我们就可以使用两层循环来求出所有状态。

每次判断当前 dp[i][j] 是否可以看到下一个加油站，可以了就状态转移。

转移的时候有两个选择。

一种是不加油，需要更新 dp[i+1][j] 这个状态。

一种是加油，则需要更新 dp[i+1][j+1] 这个状态。

这里有个注意事项，我们需要把起点和重点都当做加油站，不过没有油而已。

具体的可以参考代码。

赛后，问其他同事，有人贪心做的。

说每次只要有油，就一直向前开，没有了，然后再在前面的加油站里选择油最多的加。

这个确实很有道理。

由于是无限油箱，遇到加油站时可以先记着。需要加油了，选择油最多的加油站，就可以使得加油次数最少了。

代码需要使用一个最大堆，这个直接使用 STL 里面的优先队列就行了。

五、最后

这次比赛题目相对比较简单，但是还是比较考验敲代码的能力的。

就像做项目一样，我们设计了一个复杂的架构，代码还是需要能够按照所想的敲出来的才行。

做 leetcode 上的算法算是一种训练，将所想的东西，使用代码实现，并通过验证。

-EOF-