Leetcode 第 142 场双周赛题解

Leetcode 第 142 场双周赛题解

题目1：3330. 找到初始输入字符串 I

思路

方案数等于相邻相同字母对的个数加 1。

代码

/** @lc app=leetcode.cn id=3330 lang=cpp** [3330] 找到初始输入字符串 I*/// @lc code=start
class Solution
{
public:int possibleStringCount(string word){int ans = 1;for (int i = 1; i < word.length(); i++)if (word[i - 1] == word[i])ans++;return ans;}
};
// @lc code=end

复杂度分析

时间复杂度：O(n)，其中 n 是字符串 word 的长度。

空间复杂度：O(1)。

题目2：

思路

直接模拟，两次遍历。

一遍建立新树。建立新树不能直接在原来的树上直接修改，直接修改会导致已经遍历过的节点的子树受到影响。

一遍统计子树大小。

代码

/** @lc app=leetcode.cn id=3331 lang=cpp** [3331] 修改后子树的大小*/// @lc code=start
class Solution
{
public:vector<int> findSubtreeSizes(vector<int> &parent, string s){int n = parent.size();vector<int> newParent(n, 1);// 建立新树for (int i = 0; i < n; i++){int t = parent[i];while (t != -1 && s[t] != s[i])t = parent[t];if (t != -1 && s[i] == s[t])newParent[i] = t;elsenewParent[i] = parent[i];}// 统计子树大小vector<int> ans(n, 1);for (int i = 0; i < n; i++){int t = newParent[i];while (t != -1){ans[t]++;t = newParent[t];}}return ans;}
};
// @lc code=end

复杂度分析

时间复杂度：O(n+∣Σ∣)，其中 n 是字符串 s 的长度，∣Σ∣=26 是字符集合的大小。

空间复杂度：O(n)，其中 n 是字符串 s 的长度。

题目3：3332. 旅客可以得到的最多点数

思路

定义状态为 dfs(i,j)，表示第 i 天到第 k−1 天，从城市 j 开始旅游，可以获得的最多点数。

分类讨论：

• 留在当前城市。接下来需要解决的问题为：第 i+1 天到第 k−1 天，从城市 j 开始旅游，可以获得的最多点数，即 dfs(i,j)=dfs(i+1,j)+stayScore[i][j]。
• 前往另外一座城市。枚举前往城市 d=0,1,2,⋯,n−1，接下来需要解决的问题为：第 i+1 天到第 k−1 天，从城市 d 开始旅游，可以获得的最多点数，即 dfs(i,j)=dfs(i+1,d)+travelScore[j][d]。

所有情况取最大值，就得到了 dfs(i,j)。

代码

动态规划：

/** @lc app=leetcode.cn id=3332 lang=cpp** [3332] 旅客可以得到的最多点数*/// @lc code=start
class Solution
{
public:int maxScore(int n, int k, vector<vector<int>> &stayScore, vector<vector<int>> &travelScore){vector<vector<int>> dp(k + 1, vector<int>(n, 0));// 状态转移for (int i = 1; i <= k; i++)for (int j = 0; j < n; j++){// 留在当前城市 jdp[i][j] = dp[i - 1][j] + stayScore[i - 1][j];// 来自另外一座城市 dfor (int d = 0; d < n; d++)dp[i][j] = max(dp[i][j], dp[i - 1][d] + travelScore[d][j]);}int ans = INT_MIN;// 枚举城市 i 作为终点for (int i = 0; i < n; i++)ans = max(ans, dp[k][i]);return ans;}
};
// @lc code=end

记忆化搜索：

#
# @lc app=leetcode.cn id=3332 lang=python3
#
# [3332] 旅客可以得到的最多点数
## @lc code=start
class Solution:def maxScore(self, n: int, k: int, stayScore: List[List[int]], travelScore: List[List[int]]) -> int:@cachedef dfs(i: int, j: int) -> int:if i == k:return 0# 留在当前城市 jres1 = dfs(i + 1, j) + stayScore[i][j]# 来自另外一座城市 dres2 = max(dfs(i + 1, d) + s for d, s in enumerate(travelScore[j]))return max(res1, res2)return max(dfs(0, i) for i in range(n))  # 枚举城市 i 作为终点
# @lc code=end

复杂度分析

时间复杂度：O(kn²)。由于每个状态只会计算一次，动态规划的时间复杂度 = 状态个数 × 单个状态的计算时间。本题状态个数等于 O(kn)，单个状态的计算时间为 O(n)，所以总的时间复杂度为 O(kn²)。

空间复杂度：O(kn)。保存多少状态，就需要多少空间。

题目4：

思路

正难则反+前缀和优化 DP

题解：

https://leetcode.cn/problems/find-the-original-typed-string-ii/solutions/2966856/zheng-nan-ze-fan-qian-zhui-he-you-hua-dp-5mi9/?source=vscode

代码

/** @lc app=leetcode.cn id=3333 lang=cpp** [3333] 找到初始输入字符串 II*/// @lc code=start
class Solution
{
private:const int MOD = 1'000'000'007;public:int possibleStringCount(string word, int k){int n = word.length();if (n < k)return 0;vector<int> cnts;long long ans = 1;int cnt = 0;for (int i = 0; i < n; i++){cnt++;if (i == n - 1 || word[i] != word[i + 1]){if (cnts.size() < k)cnts.push_back(cnt);ans = ans * cnt % MOD;cnt = 0;}}int m = cnts.size();if (m >= k) // 任何输入的字符串都至少为 kreturn ans;vector<vector<int>> dp(m + 1, vector<int>(k));// 初始化dp[0][0] = 1;vector<int> s(k + 1);// 状态转移for (int i = 0; i < m; i++){for (int j = 0; j < k; j++)s[j + 1] = (s[j] + dp[i][j]) % MOD;// j <= i 的 dp[i][j] 都是 0for (int j = i + 1; j < k; j++)dp[i + 1][j] = (s[j] - s[max(j - cnts[i], 0)]) % MOD;}ans -= reduce(dp[m].begin() + m, dp[m].end(), 0LL);return (ans % MOD + MOD) % MOD; // 保证结果非负}
};
// @lc code=end

复杂度分析

时间复杂度：O(n+k²)，其中 n 是字符串 word 的长度。

空间复杂度：O(k)。