Leetcode 第 415 场周赛题解
Leetcode 第 415 场周赛题解
- Leetcode 第 415 场周赛题解
- 题目1：3289. 数字小镇中的捣蛋鬼
- 思路
- 代码
- 复杂度分析
- 题目2：3290. 最高乘法得分
- 思路
- 代码
- 复杂度分析
- 题目3：3291. 形成目标字符串需要的最少字符串数 I
- 思路
- 代码
- 复杂度分析
- 题目4：3292. 形成目标字符串需要的最少字符串数 II
- 思路
- 代码
- 复杂度分析
Leetcode 第 415 场周赛题解
题目1：3289. 数字小镇中的捣蛋鬼
思路
用一个哈希表记录数组 nums 中每一个元素的出现次数，出现次数为 2 的数字即为答案。
代码
/*
* @lc app=leetcode.cn id=3289 lang=cpp
*
* [3289] 数字小镇中的捣蛋鬼
*/
// @lc code=start
class Solution
{
public:
vector<int> getSneakyNumbers(vector<int> &nums)
{
unordered_map<int, int> cnt;
for (int &num : nums)
cnt[num]++;
vector<int> ans;
for (auto &[num, c] : cnt)
if (c == 2)
ans.push_back(num);
return ans;
}
};
// @lc code=end
复杂度分析
时间复杂度：O(n)，其中 n 是数组 nums 的长度。
空间复杂度：O(n)，其中 n 是数组 nums 的长度。
题目2：3290. 最高乘法得分
思路
动态规划。
设 dp[i][j] 表示从 b[0] 到 b[i-1] 选 j 个数，与 a[0] 到 a[j-1] 计算点积，结果的最大值。
考虑 b[i] 数字，分类讨论：
- 如果不选 b[i]，那么需要解决的问题为：从 b[0] 到 b[i−1] 选 j+1 个数，与 a[0] 到 a[j] 计算点积，结果的最大值，即 dp[i−1,j]。
- 如果选 b[i]，那么需要解决的问题为：从 b[0] 到 b[i−1] 选 j 个数，与 a[0] 到 a[j−1] 计算点积，结果的最大值，即 dp[i−1,j−1]+a[j]⋅b[i]。
这两种情况取最大值。
代码
/*
* @lc app=leetcode.cn id=3290 lang=cpp
*
* [3290] 最高乘法得分
*/
// @lc code=start
class Solution
{
public:
long long maxScore(vector<int> &a, vector<int> &b)
{
int n = b.size();
// dp[i][j] 表示从 b[0] 到 b[i] 选 j+1 个数，与 a[0] 到 a[j] 计算点积，结果的最大值
vector<vector<long long>> dp(n + 1, vector<long long>(5));
// 初始化
for (int j = 1; j < 5; j++)
dp[0][j] = (long long)INT_MIN * 20;
// 状态转移
for (int i = 1; i <= n; i++)
for (int j = 1; j < 5; j++)
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + (long long)a[j - 1] * b[i - 1]);
return dp[n][4];
}
};
// @lc code=end
复杂度分析
时间复杂度：O(m * n)，其中 m=4 是数组 a 的长度，n 是数组 b 的长度。
空间复杂度：O(m * n)，其中 m=4 是数组 a 的长度，n 是数组 b 的长度。
题目3：3291. 形成目标字符串需要的最少字符串数 I
思路
线段树 + 动态规划。
首先对于所有的word，我们都可以使用Trie来初始化，方便查找最长前缀。
我们定义 dp[i] 为 target 前i项的答案。初始化dp[0]为0，其他均为INT_MAX。
对于每个可以到达的 dp[i] ，我们只需要考虑 target 的 [i+1,n] 区间最长可行前缀。
所以顺着前缀树，从target[i+1]开始向下，找出一个Trie中最长的与target前缀相等的前缀。我们假设找到的最长长度是len。接着，由于一个可行前缀去掉后面任意多个字符仍然可行，我们遍历 j=1～len，更新：dp[i+j]=min(dp[i+j],dp[i]+1)。
最后返回dp[n]。
代码
/*
* @lc app=leetcode.cn id=3291 lang=cpp
*
* [3291] 形成目标字符串需要的最少字符串数 I
*/
// @lc code=start
// 线段树
struct TrieNode
{
TrieNode *child[26] = {nullptr};
};
class Trie
{
public:
TrieNode *root;
Trie() { root = new TrieNode(); }
void insert(string &word)
{
TrieNode *node = root;
for (char &c : word)
{
int index = c - 'a';
if (node->child[index] == nullptr)
node->child[index] = new TrieNode();
node = node->child[index];
}
}
vector<int> search(string &target, int pos)
{
TrieNode *node = root;
vector<int> pres;
for (int i = pos; i < target.size(); i++)
{
int index = target[i] - 'a';
if (node->child[index] == nullptr)
break;
node = node->child[index];
pres.push_back(i - pos + 1);
}
return pres;
}
};
class Solution
{
public:
int minValidStrings(vector<string> &words, string target)
{
Trie trie;
// 将所有单词插入前缀树
for (string &word : words)
trie.insert(word);
int n = target.size();
vector<int> dp(n + 1, INT_MAX);
// 初始化
dp[0] = 0;
// 状态转移
for (int i = 0; i < n; i++)
{
if (dp[i] == INT_MAX)
continue;
vector<int> pres = trie.search(target, i);
for (int len : pres)
dp[i + len] = min(dp[i + len], dp[i] + 1);
}
return dp[n] == INT_MAX ? -1 : dp[n];
}
};
// @lc code=end
复杂度分析
时间复杂度：O(n2)，其中 n 是字符串 target 的长度。
空间复杂度：O(L * U)，其中 L 是 words 中所有字符串的长度之和，U = 26 是小写字母的个数。
题目4：3292. 形成目标字符串需要的最少字符串数 II
思路
题解：https://leetcode.cn/problems/minimum-number-of-valid-strings-to-form-target-ii/solutions/2917929/ac-zi-dong-ji-pythonjavacgo-by-endlessch-hcqk/
字符串哈希 + 动态规划。
用线段树处理 words，这个方法在题目 4 会超时。
一般地，对于每个 i，都计算一个最大的 leni，满足从 target[i] 开始的长为 leni 的子串是某个 words[i] 的前缀。
预处理每个 words[i] 的每个前缀的字符串哈希值，按照前缀长度分组，保存到不同的集合中。每个集合保存的是相同前缀长度的哈希值。
对于 i，二分 leni，每次 check 只需要看子串哈希值是否在集合中。
代码
/*
* @lc app=leetcode.cn id=3292 lang=cpp
*
* [3292] 形成目标字符串需要的最少字符串数 II
*/
// @lc code=start
class Solution
{
public:
int minValidStrings(const vector<string> &words, const string &target)
{
int n = target.length();
// 多项式字符串哈希（方便计算子串哈希值）
// 哈希函数 hash(s) = s[0] * base^(n-1) + s[1] * base^(n-2) + ... + s[n-2] * base + s[n-1]
const int MOD = 1'070'777'777;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int BASE = uniform_int_distribution<>(8e8, 9e8)(rng); // 随机 base，防止 hack
vector<int> pow_base(n + 1); // pow_base[i] = base^i
vector<int> pre_hash(n + 1); // 前缀哈希值 pre_hash[i] = hash(s[:i])
pow_base[0] = 1;
for (int i = 0; i < n; i++)
{
pow_base[i + 1] = (long long)pow_base[i] * BASE % MOD;
pre_hash[i + 1] = ((long long)pre_hash[i] * BASE + target[i]) % MOD; // 秦九韶算法计算多项式哈希
}
// 计算 target[l] 到 target[r-1] 的哈希值
auto sub_hash = [&](int l, int r)
{
return ((pre_hash[r] - (long long)pre_hash[l] * pow_base[r - l]) % MOD + MOD) % MOD;
};
int max_len = 0;
for (auto &w : words)
{
max_len = max(max_len, (int)w.length());
}
vector<unordered_set<int>> sets(max_len);
for (auto &w : words)
{
long long h = 0;
for (int j = 0; j < w.size(); j++)
{
h = (h * BASE + w[j]) % MOD;
sets[j].insert(h); // 注意 j 从 0 开始
}
}
auto calc_sz = [&](int i) -> int
{
// 开区间二分，left 一定满足要求，right 一定不满足要求
int left = 0, right = min(n - i, max_len) + 1;
while (left + 1 < right)
{
int mid = (left + right) / 2;
(sets[mid - 1].contains(sub_hash(i, i + mid)) ? left : right) = mid;
}
return left;
};
int ans = 0;
int cur_r = 0; // 已建造的桥的右端点
int nxt_r = 0; // 下一座桥的右端点的最大值
for (int i = 0; i < n; i++)
{
int sz = calc_sz(i);
nxt_r = max(nxt_r, i + sz);
if (i == cur_r)
{ // 到达已建造的桥的右端点
if (i == nxt_r)
{ // 无论怎么造桥，都无法从 i 到 i+1
return -1;
}
cur_r = nxt_r; // 造一座桥
ans++;
}
}
return ans;
}
};
// @lc code=end
复杂度分析
时间复杂度：O(L+nlogn)，其中 n 是字符串 target 的长度，L 是 words 中所有字符串的长度之和。
空间复杂度：O(L+n)其中 n 是字符串 target 的长度，L 是 words 中所有字符串的长度之和。