作者 | 梁唐
出品 | 公众号:Coder梁(ID:Coder_LT)
大家好,我是老梁。
这次的赛题难度稍大,多花了点时间……照惯例咱们来聊一聊上周的LeetCode周赛,这一次是第333场。由佳期投资赞助,并且前100名的同学可以获得简历直通的机会。这已经好久没有出现了,算是市场行情的一个参照物吧。
这一场的题目质量不低,很多同学表示不小心成了一题选手。。。
废话不多说,来看题吧。
给你两个 二维 整数数组 nums1
和 nums2.
nums1[i] = [idi, vali]
表示编号为 idi
的数字对应的值等于 vali
。nums2[i] = [idi, vali]
表示编号为 idi
的数字对应的值等于 vali
。每个数组都包含 互不相同 的 id ,并按 id 以 递增 顺序排列。
请你将两个数组合并为一个按 id 以递增顺序排列的数组,并符合下述条件:
0
。返回结果数组。返回的数组需要按 id 以递增顺序排列。
签到题,比较直观,我们可以利用map
的天然有序性直接搞定。
class Solution {
public:
vector<vector<int>> mergeArrays(vector<vector<int>>& nums1, vector<vector<int>>& nums2) {
map<int, int> mp;
for (auto & vt: nums1) {
mp[vt[0]] += vt[1];
}
for (auto & vt: nums2) {
mp[vt[0]] += vt[1];
}
vector<vector<int>> ret;
for (auto it : mp) {
ret.push_back({it.first, it.second});
}
return ret;
}
};
给你一个正整数 n
,你可以执行下述操作 任意 次:
n
加上或减去 2
的某个 幂返回使 n
等于 0
需要执行的 最少 操作数。
如果 x == 2i
且其中 i >= 0
,则数字 x
是 2
的幂。
这题题意看着不难,但是真的深入去思考很容易被题目和样例误导。样例当中故意放了一个54的例子,54先加上了两个数字凑到了64,然后再一举删除。会很自然地引导我们思考可以故意将一些二进制0转化成1,方便凑成进位将一大片二进制1转成0。这样反而可能比直接删除更优。
但我们怎么知道,什么时候要凑进位,什么时候直接减呢?这个时候可能会本能地往动态规划上思考,然而也是行不通的。因为进位之后,很可能会改变我们求解之后的二进制位。即产生后效性,我们知道动态规划的必要条件之一就是无后效性。
老梁就在做题的时候一度卡死在了这里,后来冷静下来想了很久,决定回到题意,重新分析。这一次我发现,其实没有必要故意将0凑成1。我们假设这种情况11..11011...11
,中间有一个0,之前有若干个1,之后有若干个1。我们可以把中间两个0先变成1,方便凑成进位,然后再删除。这样操作的代价是0变1的代价1,加上产生进位的代价1,再加上进位之后清零的代价1,总的代价是3。但我们其实可以先把左边的一坨1先进位,这样中间的0就会变成1,再来一次进位,最后清零,总代价依然是3。
中间有两个零时的结果也是一样的,如果超过两个零,再把0变成1凑进位就不划算了。所以到这里就会发现其实这种情况不存在,我们只用管1怎么删除最优即可。剩下的就是一个简单的宽度优先搜索问题,我们从低位的二进制位开始操作即可。
class Solution {
public:
int minOperations(int n) {
typedef pair<int, int> pii;
queue<pii> que;
que.push(make_pair(n, 0));
while (!que.empty()) {
auto f = que.front();
que.pop();
if (f.first == 0) return f.second;
for (int i = 0; i < 31; i++) {
if (f.first & (1 << i)) {
int cur = f.first - (1 << i);
que.push(make_pair(f.first - (1 << i), f.second + 1));
st.insert(cur);
cur = f.first + (1 << i);
// 防止进位之后超过int范围,实际上去掉也可以,因为在此之前即可找到答案
if (cur < 1e6) {
que.push(make_pair(cur, f.second + 1));
st.insert(cur);
}
break;
}
}
}
return 0;
}
};
这里插一句,求解一个整数最后一个二进制1可以直接通过位运算得到,整个计算过程非常秀,只有一行。
int x = n - (n & n - 1);
做题的时候给忘了,赛后看了大佬的博客才想起来。
给你一个正整数数组 nums
。
如果数组 nums
的子集中的元素乘积是一个 无平方因子数 ,则认为该子集是一个 无平方 子集。
无平方因子数 是无法被除 1
之外任何平方数整除的数字。
返回数组 nums
中 无平方 且 非空 的子集数目。因为答案可能很大,返回对
取余的结果。
nums
的 非空子集 是可以由删除 nums
中一些元素(可以不删除,但不能全部删除)得到的一个数组。如果构成两个子集时选择删除的下标不同,则认为这两个子集不同。
这题也很秀,我个人觉得难度算是很高了。整场比赛也只有三百多人AC,要知道之前很多场第四题通过上千人是家常便饭……
这题的关键在于数据范围,题目中明确说了,每个数字小于等于30。30以内的完全平方数除了1以外只有4、9、16、25。质因数也只有11个:2, 3, 5, 7, 11, 13, 17, 19, 23, 27, 29。
只要质因数在子集中出现一次以上,就不成立。所以我们要维护所有这些质因子在子集当中出现的次数,我们要维护的是一个集合的状态。对于老手来说这已经是一个强提示了,集合的状态不方便直接维护,常用的方法是状态压缩。即用一个整数的二进制位来表示集合中某个元素的状态,由于质因数只有11个。我们使用11个二进制位,对应的整数范围是0到2047。
状态压缩之后,我们就可以套用动态规划了。dp[i][s]
表示以第i
个元素结尾,子集中质因数状态是s
的答案数量。当我们从i
转移到i+1
时,会遇到nums[i+1]
元素。我们将它转化成二进制的状态,我们称为p
。如果s
和p
没有一位同为1,那么我们就认为策略p
是可取的,那么dp[i+1][s|p] += dp[i][s]
,这个式子有了,状态转移方程也就有了。
只要再注意一些细节,不难写出代码:
class Solution {
public:
int squareFreeSubsets(vector<int>& nums) {
vector<vector<int>> dp(1010, vector<int>(2050, 0));
int n = nums.size();
// 判断是不是完全平方数的倍数,是的话单个元素就能导致子集失效
auto forbid = [](int x) -> bool {
return x % 4 == 0 || x % 9 == 0 || x % 25 == 0;
};
// 30以下质数
int pri[12]{2, 3, 5, 7, 11, 13, 17, 19, 23, 27, 29};
// 将整数转化成二进制状态,第i位二进制表示是否是第i个质数的倍数
auto get_status = [&](int x) -> int {
int cur = 0;
for (int i = 0; i < 11; i++) {
if (x % pri[i] == 0) {
cur |= (1 << i);
}
}
return cur;
};
// 特殊处理第0位
if (!forbid(nums[0])) {
int s = get_status(nums[0]);
dp[0][s] = 1;
}
int Mod = 1e9 + 7;
for (int i = 1; i < n; i++) {
dp[i] = dp[i-1];
int v = nums[i];
// 如果是完全平方数的倍数,那么v构不成策略
if (forbid(v)) continue;
int s = get_status(v);
dp[i][s]++;
// 枚举状态
for (int j = 0; j < 2048; j++) {
// 判断策略是否可行,如果s和j没有同时为1的二进制位,那么s & j == 0
if ((s & j) == 0) {
dp[i][s | j] = (dp[i-1][j] + dp[i][s | j]) % Mod;
}
}
}
int ret = 0;
for (int i = 0; i < 2048; i++) {
ret = (ret + dp[n-1][i]) % Mod;
}
return ret;
}
};
对任一由 n
个小写英文字母组成的字符串 word
,我们可以定义一个 n x n
的矩阵,并满足:
lcp[i][j]
等于子字符串 word[i,...,n-1]
和 word[j,...,n-1]
之间的最长公共前缀的长度。给你一个 n x n
的矩阵 lcp
。返回与 lcp
对应的、按字典序最小的字符串 word
。如果不存在这样的字符串,则返回空字符串。
对于长度相同的两个字符串 a
和 b
,如果在 a
和 b
不同的第一个位置,字符串 a
的字母在字母表中出现的顺序先于 b
中的对应字母,则认为字符串 a
按字典序比字符串 b
小。例如,"aabd"
在字典上小于 "aaca"
,因为二者不同的第一位置是第三个字母,而 'b'
先于 'c'
出现。
这题是很经典的分析题,从lcp
数组的定义出发,我们可以整理出以下几个结论:
lcp[i][j] > 0
,那么s[i] == s[j]
lcp[i][j] > 0
,那么lcp[i+1][j+1] = lcp[i][j] - 1
lcp[i][j] == lcp[j][i]
j + lcp[i][j] <= n
,匹配位置不能越界要使得的字符串最小,我们可以使用贪心的思路,从最小的字母开始使用。这里我为了偷懒直接使用了并查集来判断字符是否一致,如果在一个集合内,说明字符一致。再检查上面这些条件判断是否无解。
class Solution {
public:
vector<int> fa;
// 并查集
void init(int n) {
fa.resize(n+10);
for (int i = 0; i < n; i++) fa[i] = i;
}
int query(int x) {
if (fa[x] == x)
return x;
return query(fa[x]);
}
void un(int a, int b) {
int fi = query(a);
int fj= query(b);
if (fi== fj)
return ;
fa[fj] = fi;
}
bool is_same(int a, int b) {
return query(a) == query(b);
}
string findTheString(vector<vector<int>>& lcp) {
int n = lcp.size();
init(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int ii = i + 1, jj = j + 1;
// 判断lcp[i+1][j+1] == lcp[i][j]-1
if (ii >= 0 && ii < n && jj >= 0 && jj < n && lcp[i][j] > 0 && lcp[i][j] - 1 != lcp[ii][jj]) return "";
// 判断数字是否越界
if (lcp[i][j] && lcp[i][j] + j > n) return "";
// 判断是否对称
if (lcp[i][j] != lcp[j][i]) return "";
// 如果大于0,说明i和j字符相同,即属于同一个集合
if (lcp[i][j]) {
un(i, j);
}else {
// 否则说明属于不同集合,如果它们已经在一个集合了,说明无解
if (is_same(i, j)) return "";
}
}
}
string ret = "";
for (int i = 0; i < n; i++) ret.push_back('-');
// 构造答案
int bias = 0;
for (int i = 0; i < n; i++) {
char c = 'a' + bias;
if (ret[i] == '-') {
bias++;
ret[i] = c;
}else continue;
// 如果26个字母不够使用,也同样无解
if (c > 'z') return "";
for (int j = 0; j < n; j++) {
if (is_same(i, j)) {
ret[j] = c;
}
}
}
return ret;
}
};
赛后看了大佬的博客之后,发现其实可以不用使用并查集。
我们可以直接构造答案,只要lcp[i][j]
大于0,就把答案字符串的j
位填充成和i
位一样。我们一边判断答案是否成立,一边构造这个答案。更多细节可以参考下方代码,我个人觉得这题的难度和第三题差不多,甚至还要稍微容易一些。
不得不说这一场次的确是有些硬核了……
class Solution {
public:
string findTheString(vector<vector<int>>& lcp) {
int n = lcp.size();
string ret = "";
for (int i = 0; i < n; i++) ret.push_back('-');
int bias = 0;
for (int i = 0; i < n; i++) {
// 检查是否有非法的情况
for (int j = 0; j < n; j++) {
int ii = i + 1, jj = j + 1;
if (ii >= 0 && ii < n && jj >= 0 && jj < n && lcp[i][j] > 0 && lcp[i][j] - 1 != lcp[ii][jj]) return "";
if (lcp[i][j] && lcp[i][j] + j > n) return "";
if (lcp[i][j] != lcp[j][i]) return "";
}
if (ret[i] != '-') continue;
char c = 'a' + bias++;
ret[i] = c;
if (c > 'z') return "";
// 构造答案, 如果lcp[i][j] 大于0, 说明两者字符一样
for (int j = 0; j < n; j++) {
if (lcp[i][j]) {
if (ret[j] != '-' && ret[j] != c) return "";
ret[j] = c;
}else if (ret[j] == c) return "";
}
}
return ret;
}
};