力扣56~60题
题56(中等):
分析:
显然可以贪心也可以动态规划
python代码:
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
s_intervals=sorted(intervals,key=Solution.sort_rule)
res=[]
start,end=s_intervals[0][0],s_intervals[0][1]
for i in s_intervals:
#如果新区间和上一个区间没有交集,则直接将新区间加入结果集
if i[0]>end:
res.append([start,end])
start=i[0]
end=i[1]
end=max(end,i[1])
res.append([start, end])
return res
@staticmethod
def sort_rule(item):
return item[0]
题57(中等):
分析:
显然可以贪心也可以动态规划,其实就是上一题的变形
python代码:
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
new_i=intervals.copy()
new_i.append(newInterval)
s_intervals=sorted(new_i,key=Solution.sort_rule)
res=[]
start,end=s_intervals[0][0],s_intervals[0][1]
for i in s_intervals:
#如果新区间和上一个区间没有交集,则直接将新区间加入结果集
if i[0]>end:
res.append([start,end])
start=i[0]
end=i[1]
end=max(end,i[1])
res.append([start, end])
return res
@staticmethod
def sort_rule(item):
return item[0]
题58(简单):
分析:
python代码:
class Solution:
def lengthOfLastWord(self, s: str) -> int:
word_list=s.split(' ')
word_list=[i for i in word_list if i !='']
return len(word_list[-1])
题59(中等):
分析:
这个螺旋我们做第二次了,如果会写贪吃蛇就能搞这个,如果会这个,再学一下图形界面就应该可以写一个贪吃蛇小游戏了,我之前做了纯c版贪吃蛇,还有qt的,可以看看我的其他博客内容
python代码:
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
#按顺序走要走n*n个数,
end=n*n
#设置x,y位置,p_x,p_y作为方向
x,y,p_x,p_y=0,0,1,0
#设置结果的初始值
res=[[0 for i in range(n)] for i in range(n)]
i=1
while i<=end:
res[y][x]=i
#在右上角
if p_x==1 and (x+p_x>=n or res[y+p_y][x+p_x]!=0 ):
p_x=0
p_y=1
#在右下角
if p_y==1 and (y+p_y>=n or res[y+p_y][x+p_x]!=0):
p_x=-1
p_y=0
#在左下角
if p_x==-1 and ( x+p_x<0 or res[y+p_y][x+p_x]!=0):
p_x=0
p_y=-1
#在左上角
if p_y==-1 and (y+p_y<0 or res[y+p_y][x+p_x]!=0 ):
p_x=1
p_y=0
i+=1
x+=p_x
y+=p_y
return res
题60(困难):
分析:
这道题第一反应是暴力递归求排列再取值,其实没必要这样,主要是它要取第k个,我们想象1,2,3来说
如果k在【1,2】那么第一个数就是1,如果k在【3,4】就是2……
这个时候来判断第二个数字,有n-1种情况,每种情况之间间隔(n-2)!个,思路就来了
python代码:
class Solution:
def getPermutation(self, n: int, k: int) -> str:
if k==Solution.get_n_factorial(n):
return ''.join(str(i) for i in range(n,0,-1))
n_list=[Solution.get_n_factorial(i) for i in range(n-1,0,-1)]
res=''
num=0
leave=k
#num剩余取值
nums=[str(i) for i in range(n,0,-1)]
for index,value in enumerate(n_list):
num=math.ceil(leave/value)
leave=leave%value
res+=str(nums[len(nums)-num])
nums.remove(str(nums[len(nums)-num]))
if leave==0:
res=res+''.join(nums)
break
return res
@staticmethod
def get_n_factorial(n):
res=1
for i in range(1,n+1):
res*=i
return res