【2019-08-13】leetcode(131-140)
2019-08-14 本文已影响0人
BigBigFlower
131、分隔回文串
"""
分割回文串
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
深度优先搜索
"""
class Solution:
def partition(self, s: str) -> List[List[str]]:
def dfs(s,path,res):
if not s:
res.append(path)
return
for i in range(len(s)):
if s[:i+1]==s[i::-1]:
dfs(s[i+1:],path+[s[:i+1]],res)
tmp,res=[],[]
dfs(s,tmp,res)
return res
132、分隔回文串II
"""
分隔回文串II
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回符合要求的最少分割次数。
动态规划,自顶向上
"""
class Solution:
def minCut(self, s: str) -> int:
min_s = list(range(len(s)))
n = len(s)
dp = [[False] * n for _ in range(n)]
for i in range(n):
for j in range(i+1):
if s[i] == s[j] and (i - j < 2 or dp[j + 1][i - 1]):
dp[j][i] = True
if j == 0:
min_s[i] = 0
else:
min_s[i] = min(min_s[i], min_s[j - 1] + 1)
return min_s[-1]
133、克隆图
"""
克隆图
给定无向连通图中一个节点的引用，返回该图的深拷贝（克隆）。
图中的每个节点都包含它的值 val（Int） 和其邻居的列表（list[Node]）。
图遍历：
深度优先
广度优先
"""
"""
# Definition for a Node.
class Node:
def __init__(self, val, neighbors):
self.val = val
self.neighbors = neighbors
"""
#DFS
class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
lookup={}
def dfs(node):
if not node:
return
if node in lookup:
return lookup[node]
clone=Node(node.val,[])
lookup[node]=clone
for n in node.neighbors:
clone.neighbors.append(dfs(n))
return clone
return dfs(node)
#BFS
class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
from collections import deque
lookup={}
def bfs(node):
if not node:
return
clone=Node(node.val,[])
lookup[node]=clone
queue=deque()
queue.appendleft(node)
while queue:
tmp=queue.pop()
for n in tmp.neighbors:
if n not in lookup:
lookup[n]=Node(n.val,[])
queue.appendleft(n)
lookup[tmp].neighbors.append(lookup[n])
return clone
return bfs(node)
134、加油站
"""
加油站
在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。
"""
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
total=0
curr=0
strat=0
n=len(gas)
for i in range(n):
total=total+gas[i]-cost[i]
curr=curr+gas[i]-cost[i]
if curr<0:
start=i+1
curr=0
if total>=0:
return start
else:
return -1
135、分发糖果
"""
分发糖果
贪心算法
老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
你需要按照以下要求，帮助老师给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
相邻的孩子中，评分高的孩子必须获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢？
"""
class Solution:
def candy(self, ratings: List[int]) -> int:
l=len(ratings)
total=[1]*l
for i in range(1,l):#从左往右，右边>左边 total+1
if ratings[i]>ratings[i-1]:
total[i]+=1
for i in range(l-1,0,-1):#从右往左，左边>右边
if ratings[i-1]>ratings[i]:
total[i]=max(total[i - 1], total[i] + 1)
return sum(total)
136、只出现一次的数字
"""
只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
异或
a=60 b=13
a = 0011 1100
b = 0000 1101
a^b=0011 0001 按位异或运算符:当两对应的二进位相异时，结果为1
a^b= 49
a&b = 0000 1100 按位与运算符：参与运算的两个值,如果两个相应位都为1,则该位的结果为1,否则为0
a&b = 12
a|b = 0011 1101 按位或运算符：只要对应的二个二进位有一个为1时，结果位就为1。
a|b =61
~a = 1100 0011 按位取反运算符：对数据的每个二进制位取反,即把1变为0,把0变为1 。~x 类似于 -x-1
~a=-61
a << 2=1111 0000 左移动运算符：运算数的各二进位全部左移若干位，由 << 右边的数字指定了移动的位数，高位丢弃，低位补0。
a << 2=240
a >> 2=0000 1111 右移动运算符：把">>"左边的运算数的各二进位全部右移若干位，>> 右边的数字指定了移动的位数
a >> 2=15
"""
class Solution:
def singleNumber(self, nums: List[int]) -> int:
l=len(nums)
res=0
for i in range(l):
res=res^nums[i]
return res
137、只出现一次的数字II
"""
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
"""
#字典统计 非常慢
class Solution:
def singleNumber(self, nums: List[int]) -> int:
dict={}
for i in nums:
dict[i] = dict.get(i, 0) + 1
for key,value in dict.items():
if value == 1:
return key
#通用解法
#出现3次的数字的二进制表示的每一位加起来能被3整除
class Solution:
def singleNumber(self, nums: List[int]) -> int:
bit=[0]*32
for j in range(32):
for i in range(len(nums)):
num=nums[i]>>j
bit[j]+= num & 1
res=0
for i in range(31,-1,-1):
res<<=1
res+=bit[i]%3
return res
138、复制带随机指针的链表
'''
复制带随机指针的链表
给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的深拷贝。
'''
"""
# Definition for a Node.
class Node:
def __init__(self, val, next, random):
self.val = val
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
if not head:
return None
lookup={}
node=head
while node:
lookup[node]=Node(node.val,None,None)
node=node.next
node=head
while node:
lookup[node].next=lookup.get(node.next)
lookup[node].random=lookup.get(node.random)
node=node.next
return lookup[head]
139、单词拆分
'''
单词拆分
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，
判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
'''
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
n = len(s)
if not wordDict:
return not s
dp = [False] * (n + 1)
dp[0] = True
for i in range(1, n + 1):
for j in range(i - 1, -1, -1):
if dp[j] and s[j:i] in wordDict:
dp[i] = True
break
return dp[-1]
140、单词拆分 II
'''
单词拆分 II
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。
输入:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
输出:
[
"cats and dog",
"cat sand dog"
]
'''
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
import functools
if not wordDict:return []
wordDict = set(wordDict)
max_len = max(map(len, wordDict))
@functools.lru_cache(None) # lru_cache装饰器是Python标准库实现的易于使用的记忆功能。
def helper(s):
res = []
if not s:
res.append("")
return res
for i in range(len(s)):
if i < max_len and s[:i+1] in wordDict:
for t in helper(s[i+1:]):
if not t:
res.append(s[:i+1])
else:
res.append(s[:i+1] + " " + t)
return res
return helper(s)
