作者 | 梁唐
出品 | 公众号: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
难度: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];
}
};
总的来说,这一场的赛题难度不算很大,梯度做得不错,并且很值得我们反复琢磨和思考。非常建议大家亲自上手练练,一定会很有收获的。
感谢大家的阅读,祝大家日拱一卒.
喜欢本文的话不要忘记三连~