Leetcode刷题日记14（131-140）

问题1：

问题链接：

131. 分割回文串

问题描述：

给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

实例：

示例1： 输入：s="aab" 输出：[["a","a","b"],["aa","b"]]示例2： 输入：s="a" 输出：[["a"]]

代码：

回溯

#输入的视角classSolution:defpartition(self,s:str)->List[List[str]]:n=len(s)ans=[]path=[]# 考虑 i 后面的逗号怎么选# start 表示当前这段回文子串的开始位置defdfs(i:int,start:int)->None:ifi==n:# s 分割完毕ans.append(path.copy())# 复制 pathreturn# 不分割，不选 i 和 i+1 之间的逗号ifi<n-1:# i=n-1 时只能分割# 考虑 i+1 后面的逗号怎么选dfs(i+1,start)# 分割，选 i 和 i+1 之间的逗号（把 s[i] 作为子串的最后一个字符）t=s[start:i+1]ift==t[::-1]:# 判断是否回文path.append(t)# 考虑 i+1 后面的逗号怎么选# start=i+1 表示下一个子串从 i+1 开始dfs(i+1,i+1)path.pop()# 恢复现场dfs(0,0)returnans

#答案的视角classSolution:defpartition(self,s:str)->List[List[str]]:n=len(s)ans=[]path=[]# 考虑 s[i:] 怎么分割defdfs(i:int)->None:ifi==n:# s 分割完毕ans.append(path.copy())# 复制 pathreturnforjinrange(i,n):# 枚举子串的结束位置t=s[i:j+1]# 分割出子串 tift==t[::-1]:# 判断 t 是不是回文串path.append(t)# 考虑剩余的 s[j+1:] 怎么分割dfs(j+1)path.pop()# 恢复现场dfs(0)returnans

问题2：

问题链接：

132. 分割回文串 II

问题描述：

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。 返回符合要求的 最少分割次数 。

实例：

示例1： 输入：s="aab" 输出：1解释：只需一次分割就可将 s 分割成["aa","b"]这样两个回文子串。 示例2： 输入：s="a" 输出：0示例3： 输入：s="ab" 输出：1

代码：

记忆化搜索

classSolution:defminCut(self,s:str)->int:# 返回 s[l:r+1] 是否为回文串@cache# 缓存装饰器，避免重复计算 is_palindrome（一行代码实现记忆化）defis_palindrome(l:int,r:int)->bool:ifl>=r:returnTruereturns[l]==s[r]andis_palindrome(l+1,r-1)@cache# 缓存装饰器，避免重复计算 dfs（一行代码实现记忆化）defdfs(r:int)->int:ifis_palindrome(0,r):# 已是回文串，无需分割return0res=infforlinrange(1,r+1):# 枚举分割位置ifis_palindrome(l,r):res=min(res,dfs(l-1)+1)# 在 l-1 和 l 之间切一刀returnresreturndfs(len(s)-1)

问题3：

问题链接：

133. 克隆图

问题描述：

给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。 图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。 class Node{public int val;public List<Node>neighbors;}测试用例格式： 简单起见，每个节点的值都和它的索引相同。例如，第一个节点值为1（val=1），第二个节点值为2（val=2），以此类推。该图在测试用例中使用邻接列表表示。 邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。 给定节点将始终是图中的第一个节点（值为1）。你必须将 给定节点的拷贝 作为对克隆图的引用返回。

实例：

问题4：

代码：

""" # Definition for a Node. class Node: def __init__(self, val = 0, neighbors = None): self.val = val self.neighbors = neighbors if neighbors is not None else [] """#1.偷懒做法fromtypingimportOptionalclassSolution:defcloneGraph(self,node:Optional['Node'])->Optional['Node']:returncopy.deepcopy(node)

#广搜fromtypingimportOptionalclassSolution:defcloneGraph(self,node:Optional['Node'])->Optional['Node']:ifnotnode:returnNone# 空节点不拷贝clone_nodes={node.val:Node(node.val)}# 存储每一个拷贝过的节点，并克隆起点节点queue=[node]# 用于广度优先搜索的队列，且起点节点入队whilequeue:cur=queue.pop(0)# 从队列中获取一个待处理的节点clone_node=clone_nodes[cur.val]# 待处理的节点一定是克隆好了的，直接获取其克隆节点forneighborincur.neighbors:# 处理当前节点的邻接节点ifneighbor.valnotinclone_nodes:clone_nodes[neighbor.val]=Node(neighbor.val)# 如果邻接节点未拷贝，则拷贝queue.append(neighbor)# 未拷贝的节点说明还没有处理，加入队列等待处理clone_node.neighbors.append(clone_nodes[neighbor.val])# 将邻接节点的拷贝节点加入当前节点的拷贝节点的邻接列表returnclone_nodes[node.val]# 返回起点节点的克隆节点

#深搜fromtypingimportOptionalclassSolution:def__init__(self):self.clone_nodes={}# 存储每一个克隆过的节点defcloneGraph(self,node:Optional['Node'])->Optional['Node']:ifnotnode:returnNone# 空节点不克隆ifnode.valinself.clone_nodes:returnself.clone_nodes[node.val]# 克隆了的节点不重复克隆clone_node=Node(node.val)# 创建一个克隆后的节点self.clone_nodes[node.val]=clone_node# 存储克隆节点forneighborinnode.neighbors:# 克隆节点 克隆 被克隆节点的邻接列表clone_node.neighbors.append(self.cloneGraph(neighbor))returnclone_node

问题4：

问题链接：

134. 加油站

问题描述：

在一条环路上有 n 个加油站，其中第i个加油站有汽油 gas[i]升。 你有一辆油箱容量无限的的汽车，从第i个加油站开往第i+1个加油站需要消耗汽油 cost[i]升。你从其中的一个加油站出发，开始时油箱为空。 给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回-1。如果存在解，则 保证 它是 唯一 的。

实例：

示例1:输入:gas=[1,2,3,4,5],cost=[3,4,5,1,2]输出:3解释:从3号加油站(索引为3处)出发，可获得4升汽油。此时油箱有=0+4=4升汽油 开往4号加油站，此时油箱有4-1+5=8升汽油 开往0号加油站，此时油箱有8-2+1=7升汽油 开往1号加油站，此时油箱有7-3+2=6升汽油 开往2号加油站，此时油箱有6-4+3=5升汽油 开往3号加油站，你需要消耗5升汽油，正好足够你返回到3号加油站。 因此，3可为起始索引。 示例2:输入:gas=[2,3,4],cost=[3,4,3]输出:-1解释:你不能从0号或1号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。 我们从2号加油站出发，可以获得4升汽油。 此时油箱有=0+4=4升汽油 开往0号加油站，此时油箱有4-3+2=3升汽油 开往1号加油站，此时油箱有3-3+3=3升汽油 你无法返回2号加油站，因为返程需要消耗4升汽油，但是你的油箱只有3升汽油。 因此，无论怎样，你都不可能绕环路行驶一周。

代码：

classSolution:defcanCompleteCircuit(self,gas:List[int],cost:List[int])->int:ans=min_s=s=0#s为油量，min_s表示最小油量fori,(g,c)inenumerate(zip(gas,cost)):s+=g-cifs<min_s:min_s=s# 更新最小油量ans=i+1# 注意 s 减去 c 之后，汽车在 i+1 而不是 ireturn-1ifs<0elseans

问题5：

问题链接：

135. 分发糖果

问题描述：

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。 你需要按照以下要求，给这些孩子分发糖果： 每个孩子至少分配到1个糖果。 相邻两个孩子中，评分更高的那个会获得更多的糖果。 请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

实例：

示例1： 输入：ratings=[1,0,2]输出：5解释：你可以分别给第一个、第二个、第三个孩子分发2、1、2颗糖果。 示例2： 输入：ratings=[1,2,2]输出：4解释：你可以分别给第一个、第二个、第三个孩子分发1、2、1颗糖果。 第三个孩子只得到1颗糖果，这满足题面中的两个条件。

代码：

classSolution:defcandy(self,ratings:List[int])->int:left=[1for_inrange(len(ratings))]right=left[:]foriinrange(1,len(ratings)):ifratings[i]>ratings[i-1]:left[i]=left[i-1]+1count=left[-1]foriinrange(len(ratings)-2,-1,-1):ifratings[i]>ratings[i+1]:right[i]=right[i+1]+1count+=max(left[i],right[i])returncount

问题6：

问题链接：

136. 只出现一次的数字

问题描述：

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

实例：

示例1： 输入：nums=[2,2,1]输出：1示例2： 输入：nums=[4,1,2,1,2]输出：4示例3： 输入：nums=[1]输出：1

代码：

#使用哈希classSolution:defsingleNumber(self,nums:List[int])->int:count_n=Counter(nums)forkey,valueincount_n.items():ifvalue==1:returnkey

问题7：

问题链接：

137. 只出现一次的数字 II

问题描述：

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。 你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

实例：

示例1： 输入：nums=[2,2,3,2]输出：3示例2： 输入：nums=[0,1,0,1,0,1,99]输出：99

代码：

classSolution:defsingleNumber(self,nums:List[int])->int:ones,twos=0,0fornuminnums:ones=ones^num&~twos twos=twos^num&~onesreturnones

问题8：

问题链接：

138. 随机链表的复制

问题描述：

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。 例如，如果原链表中有 X 和 Y 两个节点，其中 X.random-->Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random-->y 。 返回复制链表的头节点。 用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个[val,random_index]表示： val：一个表示 Node.val 的整数。 random_index：随机指针指向的节点索引（范围从0到 n-1）；如果不指向任何节点，则为 null 。 你的代码 只 接受原链表的头节点 head 作为传入参数。

实例：

代码：

""" # Definition for a Node. class Node: def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None): self.val = int(x) self.next = next self.random = random """classSolution:defcopyRandomList(self,head:'Node')->'Node':ifnothead:returnhead# 复制所有节点，插入原节点的后面cur=headwhilecur:cur.next=Node(cur.val,cur.next,None)cur=cur.next.next# 连接所有复制的节点的random指针cur=head copyHead=head.nextwhilecur:ifcur.random:cur.next.random=cur.random.nextcur=cur.next.next# 断开原链表与复制链表之间的连接cur=head cur_=copyHeadwhilecurandcur_:cur.next=cur_.nextcur=cur.nextifcur:cur_.next=cur.nextcur_=cur_.nextreturncopyHead

问题9：

问题链接：

139. 单词拆分

问题描述：

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

实例：

示例1： 输入:s="leetcode",wordDict=["leet","code"]输出:true 解释:返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。 示例2： 输入:s="applepenapple",wordDict=["apple","pen"]输出:true 解释:返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。 注意，你可以重复使用字典中的单词。 示例3： 输入:s="catsandog",wordDict=["cats","dog","sand","and","cat"]输出:false

代码：

classSolution:defwordBreak(self,s:str,wordDict:List[str])->bool:n=len(s)@cachedefdfs(i):ifi==n:returnTrueforjinrange(i+1,n+1):ifs[i:j]inwordDictanddfs(j):returnTruereturnFalsereturndfs(0)

问题10：

问题链接：

140. 单词拆分 II

问题描述：

给定一个字符串 s 和一个字符串字典 wordDict ，在字符串 s 中增加空格来构建一个句子，使得句子中所有的单词都在词典中。以任意顺序 返回所有这些可能的句子。 注意：词典中的同一个单词可能在分段中被重复使用多次。

实例：

示例1： 输入:s="catsanddog",wordDict=["cat","cats","and","sand","dog"]输出:["cats and dog","cat sand dog"]示例2： 输入:s="pineapplepenapple",wordDict=["apple","pen","applepen","pine","pineapple"]输出:["pine apple pen apple","pineapple pen apple","pine applepen apple"]解释:注意你可以重复使用字典中的单词。 示例3： 输入:s="catsandog",wordDict=["cats","dog","sand","and","cat"]输出:[]

代码：

classSolution:# 超时defwordBreak(self,s:str,wordDict:List[str])->List[str]:res=[]#wordDict=set(wordDict)defdfs(wordDict,temp,pos):#ifpos==len(s):res.append(" ".join(temp))returnforiinrange(pos,len(s)+1):ifs[pos:i]inwordDict:temp.append(s[pos:i])dfs(wordDict,temp,i)temp.pop()#dfs(wordDict,[],0)returnres