力扣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