Leetcode 第 142 场双周赛题解

Leetcode 第 142 场双周赛题解

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

思路

方案数等于相邻类似字母对的个数加 1。
代码

1. /*
2. * @lc app=leetcode.cn id=3330 lang=cpp
3. *
4. * [3330] 找到初始输入字符串 I
5. */
7. // @lc code=start
8. class Solution
9. {
10. public:
11.     int possibleStringCount(string word)
12.     {
13.         int ans = 1;
14.         for (int i = 1; i < word.length(); i++)
15.             if (word[i - 1] == word[i])
16.                 ans++;
18.         return ans;
19.     }
20. };
21. // @lc code=end

复制代码

复杂度分析

时间复杂度：O(n)，此中 n 是字符串 word 的长度。
空间复杂度：O(1)。
题目2：

思路

直接模仿，两次遍历。
一遍创建新树。创建新树不能直接在原来的树上直接修改，直接修改会导致已经遍历过的节点的子树受到影响。
一遍统计子树大小。
代码

1. /*
2. * @lc app=leetcode.cn id=3331 lang=cpp
3. *
4. * [3331] 修改后子树的大小
5. */
7. // @lc code=start
8. class Solution
9. {
10. public:
11.     vector<int> findSubtreeSizes(vector<int> &parent, string s)
12.     {
13.         int n = parent.size();
14.         vector<int> newParent(n, 1);
16.         // 建立新树
17.         for (int i = 0; i < n; i++)
18.         {
19.             int t = parent[i];
20.             while (t != -1 && s[t] != s[i])
21.                 t = parent[t];
23.             if (t != -1 && s[i] == s[t])
24.                 newParent[i] = t;
25.             else
26.                 newParent[i] = parent[i];
27.         }
29.         // 统计子树大小
30.         vector<int> ans(n, 1);
31.         for (int i = 0; i < n; i++)
32.         {
33.             int t = newParent[i];
34.             while (t != -1)
35.             {
36.                 ans[t]++;
37.                 t = newParent[t];
38.             }
39.         }
41.         return ans;
42.     }
43. };
44. // @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[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)。
代码

动态规划：

1. /*
2. * @lc app=leetcode.cn id=3332 lang=cpp
3. *
4. * [3332] 旅客可以得到的最多点数
5. */
7. // @lc code=start
8. class Solution
9. {
10. public:
11.     int maxScore(int n, int k, vector<vector<int>> &stayScore, vector<vector<int>> &travelScore)
12.     {
13.         vector<vector<int>> dp(k + 1, vector<int>(n, 0));
14.         // 状态转移
15.         for (int i = 1; i <= k; i++)
16.             for (int j = 0; j < n; j++)
17.             {
18.                 // 留在当前城市 j
19.                 dp[i][j] = dp[i - 1][j] + stayScore[i - 1][j];
20.                 // 来自另外一座城市 d
21.                 for (int d = 0; d < n; d++)
22.                     dp[i][j] = max(dp[i][j], dp[i - 1][d] + travelScore[d][j]);
23.             }
25.         int ans = INT_MIN;
26.         // 枚举城市 i 作为终点
27.         for (int i = 0; i < n; i++)
28.             ans = max(ans, dp[k][i]);
30.         return ans;
31.     }
32. };
33. // @lc code=end

复制代码

影象化搜索：

1. #
2. # @lc app=leetcode.cn id=3332 lang=python3
3. #
4. # [3332] 旅客可以得到的最多点数
5. #
7. # @lc code=start
8. class Solution:
9.     def maxScore(self, n: int, k: int, stayScore: List[List[int]], travelScore: List[List[int]]) -> int:
10.         
11.         @cache
12.         def dfs(i: int, j: int) -> int:
13.             if i == k:
14.                 return 0
16.             # 留在当前城市 j
17.             res1 = dfs(i + 1, j) + stayScore[i][j]
18.             # 来自另外一座城市 d
19.             res2 = max(dfs(i + 1, d) + s for d, s in enumerate(travelScore[j]))
20.             
21.             return max(res1, res2)
22.         
23.         return max(dfs(0, i) for i in range(n))  # 枚举城市 i 作为终点
24. # @lc code=end

复制代码

复杂度分析

时间复杂度：O(kn2)。由于每个状态只管帐算一次，动态规划的时间复杂度 = 状态个数 × 单个状态的计算时间。本题状态个数等于 O(kn)，单个状态的计算时间为 O(n)，所以总的时间复杂度为 O(kn2)。
空间复杂度：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
代码

1. /*
2. * @lc app=leetcode.cn id=3333 lang=cpp
3. *
4. * [3333] 找到初始输入字符串 II
5. */
7. // @lc code=start
8. class Solution
9. {
10. private:
11.     const int MOD = 1'000'000'007;
13. public:
14.     int possibleStringCount(string word, int k)
15.     {
16.         int n = word.length();
17.         if (n < k)
18.             return 0;
20.         vector<int> cnts;
21.         long long ans = 1;
22.         int cnt = 0;
23.         for (int i = 0; i < n; i++)
24.         {
25.             cnt++;
26.             if (i == n - 1 || word[i] != word[i + 1])
27.             {
28.                 if (cnts.size() < k)
29.                     cnts.push_back(cnt);
30.                 ans = ans * cnt % MOD;
31.                 cnt = 0;
32.             }
33.         }
35.         int m = cnts.size();
36.         if (m >= k) // 任何输入的字符串都至少为 k
37.             return ans;
39.         vector<vector<int>> dp(m + 1, vector<int>(k));
40.         // 初始化
41.         dp[0][0] = 1;
42.         vector<int> s(k + 1);
43.         // 状态转移
44.         for (int i = 0; i < m; i++)
45.         {
46.             for (int j = 0; j < k; j++)
47.                 s[j + 1] = (s[j] + dp[i][j]) % MOD;
48.             // j <= i 的 dp[i][j] 都是 0
49.             for (int j = i + 1; j < k; j++)
50.                 dp[i + 1][j] = (s[j] - s[max(j - cnts[i], 0)]) % MOD;
51.         }
53.         ans -= reduce(dp[m].begin() + m, dp[m].end(), 0LL);
54.         return (ans % MOD + MOD) % MOD; // 保证结果非负
55.     }
56. };
57. // @lc code=end

复制代码

复杂度分析

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

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。