Leetcode 第 142 场双周赛题解
Leetcode 第 142 场双周赛题解题目1：3330. 找到初始输入字符串 I
思路
方案数等于相邻类似字母对的个数加 1。
代码
/*
* @lc app=leetcode.cn id=3330 lang=cpp
*
* 找到初始输入字符串 I
*/
// @lc code=start
class Solution
{
public:
int possibleStringCount(string word)
{
int ans = 1;
for (int i = 1; i < word.length(); i++)
if (word == word)
ans++;
return ans;
}
};
// @lc code=end
复杂度分析
时间复杂度：O(n)，此中 n 是字符串 word 的长度。
空间复杂度：O(1)。
题目2：
思路
直接模仿，两次遍历。
一遍创建新树。创建新树不能直接在原来的树上直接修改，直接修改会导致已经遍历过的节点的子树受到影响。
一遍统计子树大小。
代码
/*
* @lc app=leetcode.cn id=3331 lang=cpp
*
* 修改后子树的大小
*/
// @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;
while (t != -1 && s != s)
t = parent;
if (t != -1 && s == s)
newParent = t;
else
newParent = parent;
}
// 统计子树大小
vector<int> ans(n, 1);
for (int i = 0; i < n; i++)
{
int t = newParent;
while (t != -1)
{
ans++;
t = newParent;
}
}
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。
[*]前往别的一座都会。枚举前往都会 d=0,1,2,⋯,n−1，接下来需要办理的问题为：第 i+1 天到第 k−1 天，从都会 d 开始旅游，可以得到的最多点数，即 dfs(i,j)=dfs(i+1,d)+travelScore。
所有情况取最大值，就得到了 dfs(i,j)。
代码
动态规划：
/*
* @lc app=leetcode.cn id=3332 lang=cpp
*
* 旅客可以得到的最多点数
*/
// @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++)
{
// 留在当前城市 j
dp = dp + stayScore;
// 来自另外一座城市 d
for (int d = 0; d < n; d++)
dp = max(dp, dp + travelScore);
}
int ans = INT_MIN;
// 枚举城市 i 作为终点
for (int i = 0; i < n; i++)
ans = max(ans, dp);
return ans;
}
};
// @lc code=end
影象化搜索：
#
# @lc app=leetcode.cn id=3332 lang=python3
#
# 旅客可以得到的最多点数
#
# @lc code=start
class Solution:
def maxScore(self, n: int, k: int, stayScore: List], travelScore: List]) -> int:
@cache
def dfs(i: int, j: int) -> int:
if i == k:
return 0
# 留在当前城市 j
res1 = dfs(i + 1, j) + stayScore
# 来自另外一座城市 d
res2 = max(dfs(i + 1, d) + s for d, s in enumerate(travelScore))
return max(res1, res2)
return max(dfs(0, i) for i in range(n))# 枚举城市 i 作为终点
# @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
代码
/*
* @lc app=leetcode.cn id=3333 lang=cpp
*
* 找到初始输入字符串 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 != word)
{
if (cnts.size() < k)
cnts.push_back(cnt);
ans = ans * cnt % MOD;
cnt = 0;
}
}
int m = cnts.size();
if (m >= k) // 任何输入的字符串都至少为 k
return ans;
vector<vector<int>> dp(m + 1, vector<int>(k));
// 初始化
dp = 1;
vector<int> s(k + 1);
// 状态转移
for (int i = 0; i < m; i++)
{
for (int j = 0; j < k; j++)
s = (s + dp) % MOD;
// j <= i 的 dp 都是 0
for (int j = i + 1; j < k; j++)
dp = (s - s, 0)]) % MOD;
}
ans -= reduce(dp.begin() + m, dp.end(), 0LL);
return (ans % MOD + MOD) % MOD; // 保证结果非负
}
};
// @lc code=end
复杂度分析
时间复杂度：O(n+k2)，此中 n 是字符串 word 的长度。
空间复杂度：O(k)。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]