LeetCode周赛286场，高质量题目，不容错过
LeetCode周赛286场，高质量题目，不容错过
作者 | 梁唐
出品 | 公众号：Coder梁（ID：Coder_LT）
大家好，我是梁唐。
老规矩，我们一起来看下LeetCode周赛。
这一次的周赛是六方云赞助的，前500名可以获得内推码，还有按摩仪、定制水杯等奖品。
本场比赛题目的质量很不错，梯度很明显。没有出一些比较小众的算法，更加看重常规算法的理解和思维能力。
好了，我们废话不多说了，来看题吧。
找出两数组的不同
难度：0星
给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，请你返回一个长度为 2 的列表 answer ，其中：
answer[0]是nums1中所有 不 存在于nums2中的 不同 整数组成的列表。answer[1]是nums2中所有 不 存在于nums1中的 不同 整数组成的列表。
注意：列表中的整数可以按 任意 顺序返回。
解法
看一下范围，两个数组元素最多只有1000，那就随便怎么玩都行了。
所以我选择用Python水过去……
不过题目当中有一个trick，最后返回的结果当中只能包含互不相同的元素，所以返回之前需要用set做去重。
class Solution:
def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]:
st1, st2 = set(nums1), set(nums2)
rt1, rt2 = [], []
for x in nums1:
if x not in st2:
rt1.append(x)
for x in nums2:
if x not in st1:
rt2.append(x)
return [list(set(rt1)), list(set(rt2))]
比赛的时候没有想那么多，赛后看了大佬的题解，发现这题用Python只需要三行：
class Solution:
def findDifference(self, s1: List[int], s2: List[int]) -> List[List[int]]:
return [[*(set(s1) - set(s2))], [*(set(s2) - set(s1))]]
不禁有些羞愧，看来对于Python的用法还是不够熟悉啊……
美化数组的最少删除数
难度：2星
给你一个下标从 0 开始的整数数组 nums ，如果满足下述条件，则认为数组 nums 是一个 美丽数组 ：
nums.length为偶数- 对所有满足
i % 2 == 0的下标i，nums[i] != nums[i + 1]均成立
注意，空数组同样认为是美丽数组。
你可以从 nums 中删除任意数量的元素。当你删除一个元素时，被删除元素右侧的所有元素将会向左移动一个单位以填补空缺，而左侧的元素将会保持 不变 。
返回使 nums 变为美丽数组所需删除的 最少 元素数目。
解法
首先观察一下数据范围，数组的长度最大有1e5，所以我们肯定不能用复杂度大于等于的算法。
确定了复杂度范围之后，结合题意要求最优的情况，基本上摆在面前的只有两条路：贪心或者动态规划。
我们首先来说动态规划，出现冲突的情况只有一种，就是当i是偶数时，nums[i] == nums[i+1]。可以想到，我们可以维护每一个数分别在奇数位和在偶数位时的结果。我们用dp[i][0]表示nums[i]在偶数位时最少要删除的元素数量，用dp[i][1]表示nums[i]在奇数位时最少要删除的数量。
怎么进行状态转移呢？
首先，只有一种情况会出现冲突，就是当nums[i] == nums[i-1]时。这个时候根据i在不同的位置，又有不同的情况。
对于dp[i][0]来说，它有两种选择，第一种是接在dp[i-1][1]后面，因为题目只要求了偶数位不能和下一位奇数位相等，但没有要求不能与之前一位相等，所以这是一种策略。第二种策略是替换掉在偶数位的i-1，这会需要删除i-1，所以会产生1的开销。所以我们在这两种情况里选最优：dp[i][0] = min(dp[i-1][0]+1, dp[i-1][1])。
对于dp[i][1]来说，它只有一种选择，就替换掉在奇数位的i-1。因为它不能接在dp[i-1][0]后面，这不符合题目要求。
对于nums[i] != nums[i-1]的情况而言就很好办了，我们无非两种选择，0成本接在前一位后面，或者是花费1成本替换掉前一位。代码如下：
class Solution {
public:
int minDeletion(vector<int>& nums) {
int n = nums.size();
int dp[n+2][2];
memset(dp, 0, sizeof dp);
dp[0][1] = 1;
for (int i = 1; i < n; i++) {
if (nums[i] == nums[i-1]) {
dp[i][0] = min(dp[i-1][1], dp[i-1][0]+1);
dp[i][1] = dp[i-1][1]+1;
}
else {
dp[i][0] = min(dp[i-1][1], dp[i-1][0]+1);
dp[i][1] = min(dp[i-1][0], dp[i-1][1]+1);
}
}
return dp[n-1][1];
}
};
这道题并不只有这一种动态规划的方式，这里再给出另外一种动态规划的思路。
我们可以考虑使用dp[i]存储以i位置开头的子串需要删除的最少元素个数，从右往左进行遍历状态进行动态规划。
显然dp[n-1] = 1，因为最后只剩下一个元素不满足要求，必须要删除。
当nums[i] == nums[i+1]时，有两种选择，第一种选择是顶替i+1位置，代价是dp[i+1]+1，第二种是和i+1位置一起删除，代价是dp[i+2]+2。
如果nums[i] != nums[i+1]，直接dp[i] = dp[i+2]即可。
代码如下：
class Solution {
public:
int minDeletion(vector<int>& nums) {
int n = nums.size();
int dp[n+2];
memset(dp, 0, sizeof dp);
dp[n-1] = 1;
for (int i = n-2; i > -1; i--) {
if (nums[i] == nums[i+1]) {
dp[i] = min(dp[i+1]+1, dp[i+2]+2);
}else dp[i] = dp[i+2];
}
return dp[0];
}
};
其实，这道题也可以使用贪心搞定……
在阐述算法之前，我们先来简单证明一下，为什么贪心可以有解。我们可以把数组看成是m段相同元素拼接而成的。不同的元素不论是奇数位还是在偶数位都是可以拼接的，唯一要考虑的就是相同元素内部如何组合达到最优。
我们假设数组当中某一个片段是这样的：[..., x, y, y, ... y]。
即若干个y跟在一个x后面，这时有两种可能，第一种可能x在偶数位，在这种情况下，最多可以放下两个y：[x, y, y]。
第二种可能是x在奇数位，此时只能放下一个y：[x, y]。此时我们可以选择干掉x，让第一个y出现在奇数位，这样可以放下两个y：[y, y]，但很容易发现，对于整体的贡献是一样的，都是贡献了长度2。
经过了简单的证明之后，就可以发现，其实不论前面怎么放，我们使用贪心的方法能放就放得到的结果都是一样的。所以只需要维护一下之前最后一个摆放的元素，以及当前已经摆放的总数即可：
class Solution {
public:
int minDeletion(vector<int>& nums) {
int ret = 0;
int n = nums.size();
int last = nums[0];
int cnt = 1;
for (int i = 1; i < n; i++) {
// 在奇数位判断一下是否和last冲突
if (cnt % 2) {
if (nums[i] != last) {
last = nums[i];
cnt++;
}
// 如果在偶数位，直接放
}else {
last = nums[i];
cnt++;
}
}
if (cnt % 2) cnt--;
return n - cnt;
}
};
在比赛的时候我本来是打算仔细推导动态规划算法的，但感觉状态之间表示和转移有点乱，后来分析了一下，发现贪心可行，就果断放弃推导直接贪心搞定了。这道题本身不算难，但推理各种解法的过程非常有意思。
找到指定长度的回文数
难度：2.5星
给你一个整数数组 queries 和一个 正 整数 intLength ，请你返回一个数组 answer ，其中 answer[i] 是长度为 intLength 的 正回文数 中第 queries[i] 小的数字，如果不存在这样的回文数，则为 -1 。
回文数 指的是从前往后和从后往前读一模一样的数字。回文数不能有前导 0 。
解法
还是老规矩，先来看数据范围。发现里面query的最大范围是1e9，也就是说最多可能要序号1e9的回文数。这么大的范围看着是很吓人，但也侧面说明了，按顺序一个一个生成是不可能的。大概率有的方法可以直接计算。
接着分析一下回文串大小排列的规律，很容易发现窍门。
长度为1的回文串有10种：0-9，长度为2的回文串也是10种00-99。估计有同学会说00不能算吧，不是有前导零吗？先别急，暂时先不考虑前导零，就先当做是10种。那么问题来了，长度是3的有几种？100种，怎么算的？
很简单，长度为1的有10种，我们任选一种有10种可能。接着我们在长度为1的回文串外侧包裹上0-9，所以就是10x10=100种，其中00包裹的有10种，所以去掉前导零的情况有90种。
那么，我再问你，长度为k的回文串有多少种？很简单，递推一下可以知道：不考虑前导零就是种，考虑前导零的情况有种。
我们接着来思考另外一个问题，假设我们知道回文串的长度是5，我们要求第x小的回文串，怎么求呢？
其实也很简单，我们先把最小的回文串写出来，是什么？是10001，第二小的呢？是10101，为什么是这个？因为先动里面的数字可以尽量保证高位尽量小，所以先动内侧的数字再动外侧的数字。到这里你会发现，10001的下一位是10101，如果我们去掉一半的数字，只看左侧，是什么？是100变成了101。
101的下一个数字是什么？当然是102，所以我们要求x小怎么求？很简单，100+x，然后再回文一下就是答案，是的，花里胡哨一大堆，其实就这么简单。
我比赛的时候脑子没转过弯来，用C++写的可丑了……
class Solution {
public:
long long generate(vector<long long>& cnt, int lth, long long x) {
// 存储回文串左侧部分
vector<int> bits;
for (int i = lth; i > 0; i -= 2) {
long long dec = (i > 1 ? cnt[i-2]: 1);
int b = x / dec + (i == lth);
if (b > 9) return -1;
bits.push_back(b);
x = x % dec;
}
// 将回文串拼接完整
if (lth % 2) {
for (int i = bits.size() - 2; i > -1; i--) bits.push_back(bits[i]);
}else {
for (int i = bits.size() - 1; i > -1; i--) bits.push_back(bits[i]);
}
long long ret = 0;
for (int i = bits.size()-1; i > -1; i--) {
ret = ret * 10 + bits[i];
}
return ret;
}
vector<long long> kthPalindrome(vector<int>& queries, int lth) {
vector<long long> cnt;
cnt.push_back(1);
cnt.push_back(10);
cnt.push_back(10);
// 计算lth长度的回文串有多少种
for (int i = 3; i <= lth; i++) {
cnt.push_back(10ll * cnt[i-2]);
}
vector<long long> ret;
for (auto x: queries) {
ret.push_back(generate(cnt, lth, x-1));
}
return ret;
}
};
其实用Python很简单就能实现。
class Solution:
def kthPalindrome(self, queries: List[int], lth: int) -> List[int]:
base = 10 ** ((lth - 1) // 2)
maxi = 9 * base
ans = []
def func(x):
if lth % 2 == 0:
return str(x) + str(x)[::-1]
return str(x) + str(x)[-2::-1]
for q in queries:
if q > maxi:
ans.append(-1)
else:
x = base + q - 1
ans.append(int(func(x)))
return ans
从栈中取出K个硬币的最大面值和
难度：4星
一张桌子上总共有 n 个硬币 栈 。每个栈有 正整数 个带面值的硬币。
每一次操作中，你可以从任意一个栈的 顶部 取出 1 个硬币，从栈中移除它，并放入你的钱包里。
给你一个列表 piles ，其中 piles[i] 是一个整数数组，分别表示第 i 个栈里 从顶到底 的硬币面值。同时给你一个正整数 k ，请你返回在 恰好 进行 k 次操作的前提下，你钱包里硬币面值之和 最大为多少 。
解法
老规矩，首先看范围。n和k的范围都不大，限制不大，提示性也不强。
其次分析题意，我们要从n堆硬币当中拿若干枚。由于每一枚硬币的价值都大于0，并且k小于硬币的总数，所以k一定是要拿满的。其次硬币是罗列的，这意味着我们在同一列硬币当中拿取若干次，可以合并成拿取一次。
所以题意可以进行简化：有n列硬币，我们每次可以从任意一列当中拿取若干枚，保证最多拿取k枚的情况下，最多可以拿多少价值？
如果我们把硬币转化成商品，其实已经很明显了，这就是一个多重背包的问题。只不过多重背包当中，同样物品的价值是一样的，这里做了一点改变，同一列的硬币价格不一定一样。但不管一样不一样都没关系，因为硬币排列在栈中，我们只能从上往下拿，拿取x枚的方法只有一种，我们只要计算总和就行。
熟悉背包问题，应该可以秒切。
class Solution {
public:
int maxValueOfCoins(vector<vector<int>>& piles, int k) {
int n = piles.size();
vector<vector<int>> dp(n+1, vector<int>(k+2, 0));
for (int i = 1; i <= n; i++) {
int m = piles[i-1].size();
vector<int> val;
val.push_back(0);
int tot = 0;
// 遍历从1枚到全部拿完的情况
for (int j = 0; j < m; j++) {
tot += piles[i-1][j];
val.push_back(tot);
}
// 跳过这一列的情况
for (int l = 0; l <= k; l++) dp[i][l] = dp[i-1][l];
for (int j = 1; j <= m; j++) {
for (int l = k-j; l > -1; l--)
dp[i][l+j] = max(dp[i][l+j], dp[i-1][l] + val[j]);
}
}
return dp[n][k];
}
};
总的来说，这一场的赛题难度不算很大，梯度做得不错，并且很值得我们反复琢磨和思考。非常建议大家亲自上手练练，一定会很有收获的。
感谢大家的阅读，祝大家日拱一卒.
喜欢本文的话不要忘记三连~