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-