1. 反转单词前缀
给你一个下标从 0 开始的字符串 word 和一个字符 ch 。找出 ch 第一次出现的下标 i ，反转 word 中从下标 0 开始、直到下标 i 结束（含下标 i ）的那段字符。如果 word 中不存在字符 ch ，则无需进行任何操作。
返回 结果字符串 。
示例 1：
输入：word = "xyxzxe", ch = "z"
输出："zxyxxe"
解释："z" 第一次也是唯一一次出现是在下标 3 。
反转从下标 0 到下标 3（含下标 3）的这段字符，结果字符串是 "zxyxxe" 。
示例 2：
输入：word = "xyxzxe", ch = "z"
输出："zxyxxe"
解释："z" 第一次也是唯一一次出现是在下标 3 。
反转从下标 0 到下标 3（含下标 3）的这段字符，结果字符串是 "zxyxxe" 。
class Solution:
def reversePrefix(self, word: str, ch: str) -> str:
if ch not in word: return word
word = list(word)
idx = word.index(ch)
return "".join(word[:idx+1][::-1]+word[idx+1:])
2. 可互换矩形的组数
用一个下标从 0 开始的二维整数数组 rectangles 来表示 n 个矩形，其中 rectangles[i] = [widthi, heighti] 表示第 i 个矩形的宽度和高度。
如果两个矩形 i 和 j（i < j）的宽高比相同，则认为这两个矩形 可互换 。更规范的说法是，两个矩形满足 widthi/heighti == widthj/heightj（使用实数除法而非整数除法），则认为这两个矩形 可互换 。
计算并返回 rectangles 中有多少对 可互换 矩形。
示例 1：
输入：rectangles = [[4,8],[3,6],[10,20],[15,30]]
输出：6
解释：下面按下标（从 0 开始）列出可互换矩形的配对情况：
- 矩形 0 和矩形 1 ：4/8 == 3/6
- 矩形 0 和矩形 2 ：4/8 == 10/20
- 矩形 0 和矩形 3 ：4/8 == 15/30
- 矩形 1 和矩形 2 ：3/6 == 10/20
- 矩形 1 和矩形 3 ：3/6 == 15/30
- 矩形 2 和矩形 3 ：10/20 == 15/30
示例 2：
输入：rectangles = [[4,5],[7,8]]
输出：0
解释：不存在成对的可互换矩形。
class Solution:
def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:
d = defaultdict(int)
for w,h in rectangles:
d[w/h] += 1
res = 0
for v,cnt in d.items():
res += comb(cnt, 2)
return res
3. 两个回文子序列长度的最大乘积
给你一个字符串 s ，请你找到 s 中两个 不相交回文子序列，使得它们长度的 乘积最大 。两个子序列在原字符串中如果没有任何相同下标的字符，则它们是 不相交 的。
请你返回两个回文子序列长度可以达到的 最大乘积 。
子序列 指的是从原字符串中删除若干个字符（可以一个也不删除）后，剩余字符不改变顺序而得到的结果。如果一个字符串从前往后读和从后往前读一模一样，那么这个字符串是一个 回文字符串 。
示例 1：
输入：s = "leetcodecom"
输出：9
解释：最优方案是选择 "ete" 作为第一个子序列，"cdc" 作为第二个子序列。
它们的乘积为 3 * 3 = 9 。
示例 2：
输入：s = "bb"
输出：1
解释：最优方案为选择 "b" （第一个字符）作为第一个子序列，"b" （第二个字符）作为第二个子序列。
它们的乘积为 1 * 1 = 1 。
示例 3：
输入：s = "accbcaxxcxx"
输出：25
解释：最优方案为选择 "accca" 作为第一个子序列，"xxcxx" 作为第二个子序列。
它们的乘积为 5 * 5 = 25 。
提示：
2 <= s.length <= 12
s 只含有小写英文字母。
纯粹的暴力dfs，这也能过。。。一般力扣数量级在
10^6内的能过
class Solution:
def maxProduct(self, s: str) -> int:
res = 0
def dfs(a, b, s):
nonlocal res
if not s:
if a[::-1] == a and b[::-1] == b:
res = max(res, len(a)*len(b))
else:
dfs(a+[s[0]],b,s[1:])
dfs(a,b+[s[0]],s[1:])
dfs(a,b,s[1:])
dfs([],[],s)
return res
状态压缩DP 做法：
4. 每棵子树内缺失的最小基因值⭐
超时
class Solution:
def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:
g_nums = defaultdict(set)
g_nums[0].add(nums[0])
for i in range(len(parents)-1, -1, -1):
g_nums[i].add(nums[i])
f = parents[i]
g_nums[f] |= g_nums[i]
def check(nums):
for i in range(1,10**5+1):
if i not in nums:
return i
res = []
for i in range(len(nums)):
res.append(check(g_nums[i]))
return res
发现上面做的，顺序都不一定对。。。
这是抄来的，加了点注释：
class Solution:
def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:
s = set(nums)
gen = -1
for i in range(1, 10**5+1): #最大的产生值
if i not in s:
gen = i
break
d = defaultdict(list) #建树
for i in range(len(parents)):
d[parents[i]].append(i)
ans = [1] * len(nums)
path = []
def dfs(index): #子树能否找到1，并记录走过的节点
if nums[index] == 1:
path.append(index)
return True
for c in d[index]:
if dfs(c):
path.append(index) #注意这里是从后往前记录的
return True
return False
childS = set()
@cache
def dp(index):
childS.add(nums[index])
for c in d[index]:
dp(c)
dfs(0)
#print(path)
minGen = 1
for index in path: #只有path中的节点才用修改值，题目中基因值互不相同。
dp(index)
while minGen in childS:
minGen += 1
ans[index] = minGen
return ans
整理后：
class Solution:
def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:
d = defaultdict(list) # 建树
for i, p in enumerate(parents):
d[p].append(i)
path = [] # dfs寻找需要修改的节点
def dfs(node):
if nums[node] == 1:
path.append(node)
return True
for c in d[node]:
if dfs(c):
path.append(node)
return True
return False
dfs(0)
res = [1]*len(nums)
vis = set()
@lru_cache(None)
def check(i):
vis.add(nums[i])
for c in d[i]:
check(c)
num = 1
for i in path:
check(i)
while num in vis:
num += 1
res[i] = num
return res
启发式….
