IT评测·应用市场-qidao123.com
标题:
1.8-9号Python猛刷动态规划
[打印本页]
作者:
惊雷无声
时间:
2025-1-10 05:28
标题:
1.8-9号Python猛刷动态规划
今日宽恕:总结不是纠结过去，表达不是“见斑知豹”，还要更多信息整合后去回答。
标题一
3297.统计重新分列后包含另一个字符串|
示例 1：
输入：
word1 = "abcabc", word2 = "abc"
输出：
10
解释：
除了长度为 1 和 2 的全部子字符串都是合法的。
示例 2：
输入：
word1 = "abcabc", word2 = "aaabc"
输出：
0
解释：
1 <= word1.length <= 105
1 <= word2.length <= 104
word1 和 word2 都只包含小写英文字母。
思绪：滑动窗口
遍历s，右移动right， 大于即是 t 字母出现次数的窗口，如果满足，缩小left。
这里只必要调解s和t出现差值，
class Solution:
def validSubstringCount(self, s: str, t: str) -> int:
if len(s) < len(t):
return 0
# t字母出现次数与s差
diff = defaultdict(int)
for c in t:
diff[c] +=1
#窗口less 个字母出现次数比t少
less = len(diff)
ans = left = 0
for c in s:
diff[c] -= 1
if diff[c] == 0:
# c移入窗口，窗口内c出现次数和t一样
less -= 1
while less == 0:
if diff[s[left]] == 0:
# s[left] 移出窗口前，检查次数
#与t一样，窗口内s[left] 比t少
less +=1
diff[s[left]] +=1
left +=1
ans +=left
return ans
复制代码
因为子串可以重排，只要子串可以涵盖（见 76 题）字符串 t，那么子串就可以通过重排，使得 t 是子串的前缀。以是本题是 76. 最小覆盖子串的
求个数版本
，做法都是滑动窗口
滑动窗口的内层循环竣事时，右端点固定在 right，左端点在 0,1,2,…,left−1 的全部子串都是合法的，这一共有 left 个，把 left 参加答案。
标题二
62. 不同路径 - 力扣（LeetCode）
示例 2：
<strong>输入：</strong>m = 3, n = 2
<strong>输出：</strong>3
<strong>解释：</strong>
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
复制代码
提示：
1 <= m, n <= 100
标题数据保证答案小于即是 2 * 109
思绪一：只能左移或下移，肯定要移动下移m-1，左移n-1
以是有 Cm+n−2m−1
思绪二：
动态方程：dp
[j] = dp[i-1][j] + dp
[j-1]
注意，对于第一行 dp[0][j]，大概第一列 dp
[0]，由于都是在边界，以是只能为1
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
cur = [1]*n
for i in range(1,m):
for j in range(1,n):
cur[j] += cur[j-1]
return cur[-1]
复制代码
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
欢迎光临 IT评测·应用市场-qidao123.com (https://dis.qidao123.com/)
Powered by Discuz! X3.4
