重庆seo整站优化报价,导购类网站模板,wordpress不能更新插件,免费推广的平台Leetcode 2911. Minimum Changes to Make K Semi-palindromes 1. 解题思路2. 代码实现 题目链接#xff1a;2911. Minimum Changes to Make K Semi-palindromes
1. 解题思路
这一题属实也是把我坑惨了……
坦率地说#xff0c;这道题本身并没有啥难度#xff0c;但是坑爹…Leetcode 2911. Minimum Changes to Make K Semi-palindromes 1. 解题思路2. 代码实现 题目链接2911. Minimum Changes to Make K Semi-palindromes
1. 解题思路
这一题属实也是把我坑惨了……
坦率地说这道题本身并没有啥难度但是坑爹的是题目表述简直有毒有两个细节题目里面压根没提一个是我从中文版本的题目当中发现的另一个则是我根据失败的样例当中反推出来的这简直有毒……
这道题本身思路上还是挺直接的就是一个动态规划的题目考虑每一种切分的方式然后考察其中最小的变化次数即可。
然后对于每一个切分得到的子串我们要求其变化所需的最小变化次数我们只需要找到其所有对长度 l l l整除的 d d d然后切分semi子串再考察其中每一种分法下所需的变化次数之和最后取最小值即可。
因此我们就将上述题目拆分完成了后续只要对其实现一下即可测试发现是可以在有效时间内完成所有测试样例的。
但是这里但是就来了题目中遗漏了两个非常非常重要的说明把我给坑惨了
首先这里semi-palindrome的定义事实上要求将其使用d进行切分后每一个子串都得是回文其次题中也没有具体说但是实际测试发现这里对子串的切分要求每一个子串长度至少为2。
这简直就是简直了
到底谁出的题目啊只能说出来挨打
2. 代码实现
给出python代码实现如下
class Solution:def minimumChanges(self, s: str, k: int) - int:n len(s)lru_cache(None)def count(sub):cnt 0n len(sub)for i in range(n//2):if sub[i] ! sub[n-1-i]:cnt 1return cntlru_cache(None)def count_change(s):if s s[::-1]:return 0n len(s)ans count(s)for d in range(len(s)//2, 0, -1):if n % d ! 0:continuek n // dcnt 0for i in range(d):sub .join([s[ij*d] for j in range(k)])cnt count(sub)ans min(ans, cnt)return anslru_cache(None)def dp(idx, k):if idx2*k n:return math.infelif k 1:return count_change(s[idx:])return min(count_change(s[idx:j]) dp(j, k-1) for j in range(idx2, n))ans dp(0, k)return ans 提交代码评测得到耗时5650ms占用内存71.8MB。
