2024.9.12 Python 累加数,子串操作,分割回文串,长度最小的子数组,整数拆分
1.分割回文串
给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是回文串返回 s 所有可能的分割方案。
示例 1:
输入:s = “aab”
输出:[[“a”,“a”,“b”],[“aa”,“b”]]
示例 2:
输入:s = “a”
输出:[[“a”]]
from typing import List
class Solution:def partition(self,s:str)->List[List[str]]:ans=[]def backtrack(i,path): #1.if i ==len(s): #2.ans.append(path[:])returnfor j in range(i,len(s)): #3.substr=s[i:j+1]if substr==substr[::-1]:backtrack(j+1,path+[substr]) #4.backtrack(0,[])return ans
代码逻辑:
这个题我完全想明白了,在之前的8.26的文章中,我写了一种办法,但是那种办法我完全没有学会看懂,这次我理解了,首先把i理解为起点,把j理解为终点,backtrack(j+1)的目的是把当前字符串存起来以后,以j+1为起点进一步找回文串。大概逻辑这样以后我们深挖代码逻辑:
1.定义backtrack,backtrack的目标是,找以i为起始的字符串,判断是否为回文串,如果当前子串已经是回文串了,那么存起来,以下一个下标为基础继续找是否有回文串,如果有那么就继续重复,直到i为len(s)时停止
2.if的判断是给输出的条件
3.这个题的难点就在这里,这个for循环其实是遍历末尾的意思,从i到j的串如果是回文串,那么就继续下一层,如果不是回文串,那么就继续增大j
4.这样的写法就不需要pop了,直接加就ok了
2.长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 子数组
[numsl, numsl+1, …, numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。
示例 1:
输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2:
输入:target = 4, nums = [1,4,4]
输出:1
示例 3:
输入:target = 11, nums = [1,1,1,1,1,1,1,1]
输出:0
class Solution:def minSubArrayLen(self, target: int, nums: List[int]) -> int:left=0right=0res=100001tmp_sum=nums[0]while right<len(nums):if tmp_sum<target:right+=1if right<len(nums):tmp_sum+=nums[right]elif tmp_sum>=target:res=min(right+1-left,res)tmp_sum-=nums[left]left+=1if left>right: right+=1if right<len(nums):tmp_sum+=nums[right]if res==100001:res=0return res
3.整数拆分
给定一个正整数 n ,将其拆分为 k 个 正整数 的和( k >= 2 ),并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
示例 1:
输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
class Solution:def integerBreak(self, n: int) -> int:if n <= 3:return n - 1dp = [0] * (n + 1)dp[2] = 1for i in range(3, n + 1):dp[i] = max(2 * (i - 2), 2 * dp[i - 2], 3 * (i - 3), 3 * dp[i - 3])return dp[n]
非常好的动态规划的例子,使我旋转
class Solution:def integerBreak(self, n: int) -> int:step=0if n==3:return 2if n==2:return 1while not (n==0 or n==2 or n==4):n-=3step+=1if n==0 :n=1return (3**step)*n
或者写成n//3和n%3来判断,无非就是几种可能,都考虑一下O(1)的计算方法就出来了。
4.累加数
累加数 是一个字符串,组成它的数字可以形成累加序列。
一个有效的 累加序列 必须 至少 包含 3 个数。除了最开始的两个数以外,序列中的每个后续数字必须是它之前两个数字之和。
给你一个只包含数字 ‘0’-‘9’ 的字符串,编写一个算法来判断给定输入是否是 累加数 。如果是,返回 true ;否则,返回 false 。
说明:累加序列里的数,除数字 0 之外,不会 以 0 开头,所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。
示例 1:
输入:“112358”
输出:true
解释:累加序列为: 1, 1, 2, 3, 5, 8 。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
示例 2:
输入:“199100199”
输出:true
解释:累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199
class Solution:def isAdditiveNumber(self, num: str) -> bool:def addStrings(num1, num2):i, j, carry, result = len(num1) - 1, len(num2) - 1, 0, []while i >= 0 or j >= 0 or carry:digit1 = int(num1[i]) if i >= 0 else 0digit2 = int(num2[j]) if j >= 0 else 0total = digit1 + digit2 + carrycarry = total // 10result.append(str(total % 10))i, j = i - 1, j - 1return ''.join(result[::-1])def isValidSequence(start1, start2):prevStart, currStart, nextStart = 0, start1, start2while nextStart < len(num):# 3.if (num[prevStart] == '0' and start1 > prevStart + 1) or (num[currStart] == '0' and start2 > currStart + 1):return False #4.expectedSum = addStrings(num[prevStart:currStart], num[currStart:nextStart])#5.if num[nextStart:nextStart+len(expectedSum)] != expectedSum: #6.return FalseprevStart, currStart, nextStart = currStart, nextStart, nextStart + len(expectedSum)return Truefor firstEnd in range(1, len(num) - 1):for secondEnd in range(firstEnd + 1, len(num)):if isValidSequence(firstEnd, secondEnd):return Truereturn False
代码逻辑:
1.addString函数,用来计算两个字符串的加法,比如[1,2,3]和[4,5,6,7]相加,那么就应该是7和3加,然后carry记录升位,如果i已经=-1了,那么就输出0,分别计算每一位,存入列表里,然后之后再反向输出’'.join。写这个代码的目的是为了处理大数,万一这个字符串究极大,那么单纯的int加减就会非常的难。尤其是C语言的时候。
2.isValid函数是判断分组后的字符串是否是按照要求的,其实还是双指针,第一个指针最开始是不动的,所以进函数的时候是0,while跳出的条件是,第三个指针超出len的时候,就跳了
3.while函数的目的是为了在当前条件下,向下走,而不是确定cur边界,就是说,在下面的for循环中,我们用来确定前两个数具体是谁,然后我们根据前两个数来计算第三个值的期望,如果他是我们要找的值,那么就往下走,检查下一组,
4.首先加限定条件,如果指针一指到了0,同时指针二和他隔了一个,也就是说currStart>prev+1,那么就可以判死刑了,current指针也如此,如果遇到,0,同时下一个还隔了一个,那告辞。
5.expectedSum = addStrings(num[prevStart:currStart], num[currStart:nextStart])这个算下来就是我们的期望,我们希望第三个数是谁
6.num[nextStart:nextStart+len(expectedSum)]这个很巧,如果不一致直接告辞,继续下一次分割,如果一致,那么就像链表一样,全部向下移动一格,while安然结束,return True
7.两个for循环循所有的起始。
8.if not num.startswith(expectedSum, nextStart): return False这个代码可以替换6.的代码。