分类： leetcode

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k个位置。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

示例 2：

输入：head = [0,1,2], k = 4
输出：[2,0,1]

提示：

• 链表中节点的数目在范围 [0, 500] 内
• -100 <= Node.val <= 100
• 0 <= k <= 2 * 109

代码：

# @lc app=leetcode.cn id=61 lang=python3
#
# [61] 旋转链表
#

# @lc code=start
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        def lenlink(head):
            i=0
            while head != None:
                head=head.next
                i=i+1
            return i
        lens=lenlink(head)
        if lens==0:
            return head
        k=k%(lens) 
        newlist=ListNode(0,None)
        newcur=newlist
        cur1 = head
        cur2 = head
        for i in range(lens-k):
            cur1=cur1.next
            #print(cur1.val)
        for i in range(lens):
            if i < k:
               newcur.val= cur1.val
               print(newcur.val)
               cur1=cur1.next
               newcur.next=ListNode(0,None)
               newcur=newcur.next
            
            else:
               newcur.val= cur2.val
               #print(cur2.val)
               cur2=cur2.next
               if i<lens-1:
                    newcur.next=ListNode(0,None)
               newcur=newcur.next 
        return newlist

给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

给定 n 和 k，返回第 k 个排列。

示例 1：

输入：n = 3, k = 3
输出："213"

示例 2：

输入：n = 4, k = 9
输出："2314"

示例 3：

输入：n = 3, k = 1
输出："123"

提示：

• 1 <= n <= 9
• 1 <= k <= n!

# @lc app=leetcode.cn id=60 lang=python3
#
# [60] 排列序列
#

# @lc code=start
class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        nums=[i for i in range(1,n+1)]

        def subgetPermutation(N,k,nums,str1): 
          import math
            #print(k)
          while 1:
            if k<0 or len(nums)==1: 
                str1=str1+str(nums[0])
                return str1
            x=math.factorial(N-1)
            for i in range(1,len(nums)+1):
                if i*x>=k:    
                    k=k-(i-1)*x if k-(i-1)*x>0 else k
                    N=N-1
                    #print(i,k,N,nums)

                    str1=str1+str(nums[i-1])
                    #print(str1)
                    nums.remove(nums[i-1])
                    #print(nums)
                    break
        return subgetPermutation(n,k,nums,"")
# @lc code=end

给你一个 无重叠的 ，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

示例 1：

输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]

示例 2：

输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]
解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

示例 3：

输入：intervals = [], newInterval = [5,7]
输出：[[5,7]]

示例 4：

输入：intervals = [[1,5]], newInterval = [2,3]
输出：[[1,5]]

示例 5：

输入：intervals = [[1,5]], newInterval = [2,7]
输出：[[1,7]]

提示：

• 0 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= intervals[i][0] <= intervals[i][1] <= 105
• intervals 根据 intervals[i][0] 按 升序 排列
• newInterval.length == 2
• 0 <= newInterval[0] <= newInterval[1] <= 105

代码实现：

#
# [57] 插入区间
#

# @lc code=start
class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        intervals.append(newInterval)
        import copy
        x=intervals
        y=copy.deepcopy(intervals) 
        lens=len(y)
        x.sort(key=lambda x: (x[0], -x[1]))
        y.sort(key=lambda x: (x[1], -x[0]))
        #print(x,y)

        i=x.index(newInterval)
        j=y.index(newInterval)
        if i>0 and x[i][0]<=x[i-1][1]:
            i=i-1
        if j<lens-1 and y[j][1]>=y[j+1][0]:
            j=j+1
        #print(i)
        return x[0:i]+[[x[i][0],y[j][1]]]+y[j+1:]

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1：

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

示例 2：

输入：n = 1
输出：[[1]]

提示：

• 1 <= n <= 20

# @lc app=leetcode.cn id=59 lang=python3
#
# [59] 螺旋矩阵 II
#

# @lc code=start
from calendar import c


class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        rev=[[0]*n for i in range(n)]
        rstart=0
        cstart=0
        rend=n-1
        cend=n-1
        mid=1
        while cend>=cstart and rstart<=rend:
            for l in range(cstart,cend+1):
                rev[rstart][l]=mid
                mid=mid+1
            #rev.extend(matrix[rstart][cstart:cend+1])
            for l in range(rstart+1,rend):
                rev[l][cend]=mid   
                mid=mid+1
            for l in range(cend,cstart-1,-1):
                rev[rend][l]=mid   
                mid=mid+1
            #rev.extend(matrix[rend][cstart:cend+1][::-1])
            for l in range(rend-1,rstart,-1):
                rev[l][cstart]=mid   
                mid=mid+1
            cend=cend-1
            cstart=cstart+1
            rstart=rstart+1
            rend=rend-1
        if n//2!=n/2:
            rev[n//2][n//2]=n*n
        return rev

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

第一次尝试：

# [56] 合并区间
#

# @lc code=start
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # def takeSecond(elem):
        #     return elem[0]
       
        # intervals.sort(key=takeSecond)       
        def submatch(intervals):
            rev=list()
            i=0
            j=0
            lens=len(intervals)
            intervals.sort(key=lambda x: (x[0], x[1]))
            maxy=0 
            while i<lens:
                maxy=max(maxy,intervals[i][1])          
                if j<lens-1 and intervals[i][1]>=intervals[j+1][0]:
                    maxy=max(maxy,intervals[j+1][1])   
                    j=j+1         
                else:
                    maxy=max(maxy,intervals[j][1]) 
                    rev.append([intervals[i][0],maxy])
                    i=j+1
                    j=i
            return rev
        
        rev=submatch(intervals)
        while rev!=submatch(rev):
            rev=submatch(rev)
        return rev

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

提示：

• 1 <= nums.length <= 3 * 104
• 0 <= nums[i] <= 105

思路：看是否nums中的元素能否经过0.

# @lc app=leetcode.cn id=55 lang=python3
#
# [55] 跳跃游戏
#

# @lc code=start
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        re=0
        if nums==[0]:
            return True
        if 0 not in nums:
            return True
        for i in range(len(nums)-1,-1,-1):
            if nums[i]==0:
                j=0
                re=0
                while j<i:
                    if nums[j]<=(i-j) and i!=len(nums)-1:
                       j=j+1
                       continue
                    elif  nums[j]<(i-j) and i==len(nums)-1:
                       j=j+1
                       continue
                    else:
                        re=1 # True
                        break
                if re==0:
                    return False
        if re == 1:
            return True 
        else:return False    
                #return False

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 10
• -100 <= matrix[i][j] <= 100

代码实现：

# @lc app=leetcode.cn id=54 lang=python3
#
# [54] 螺旋矩阵
#

# @lc code=start
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        rstart=0
        cstart=0
        rend=len(matrix)-1
        cend=len(matrix[0])-1
        rev=list()
        if cstart==cend:
            for i in matrix:
                rev.extend(i) 
            return rev
        if  rstart==rend:
            return matrix[0]
        while rstart<rend and cstart<cend :
            print(rstart,rend,cstart,cend)
            for l in range(cstart,cend+1):
                rev.append(matrix[rstart][l])    
            #rev.extend(matrix[rstart][cstart:cend+1])
            for l in range(rstart+1,rend):
                rev.append(matrix[l][cend])
            for l in range(cend,cstart-1,-1):
                rev.append(matrix[rend][l])
            #rev.extend(matrix[rend][cstart:cend+1][::-1])
            for l in range(rend-1,rstart,-1):
                rev.append(matrix[l][cstart])
            #print(rev)
            cend=cend-1
            cstart=cstart+1
            rstart=rstart+1
            rend=rend-1
        if rstart==rend and cstart!=cend:
            print("fff")
            for l in range(cstart,cend+1):
                #print(matrix[rstart][l])
                rev.append(matrix[rstart][l]) 
        elif cstart==cend and rstart!=rend:
            for l in range(rstart,rend+1):
                #print(matrix[l][cstart])
                rev.append(matrix[l][cstart]) 
        elif rstart==rend and cstart==cend:
            rev.append(matrix[rstart][cstart]) 
        return rev

# @lc code=end

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1：

输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。

示例 2：

输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。

示例 3：

输入：digits = [0]
输出：[1]

提示：

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9

#
# [66] 加一
#

# @lc code=start
class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        def sub(s):
            s[-1]=s[-1]+1
            i=len(s)-1
            while i>=0:
                if s[0]==10:
                    s=[1,0]+s[1:]
                elif s[i]==10:
                    s[i]=0
                    s[i-1]=s[i-1]+1
                    i=i-1
                else:

                    return s
        if digits==[9]:
            return [1,0]
        else:
            return sub(digits)

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中最后一个单词的长度。

单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。

示例 1：

输入：s = "Hello World"
输出：5

示例 2：

输入：s = "   fly me   to   the moon  "
输出：4

示例 3：

输入：s = "luffy is still joyboy"
输出：6

提示：

• 1 <= s.length <= 104
• s 仅有英文字母和空格 ' ' 组成
• s 中至少存在一个单词

# @lc app=leetcode.cn id=58 lang=python3
#
# [58] 最后一个单词的长度
#

# @lc code=start
class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        s=s.rstrip()
        for i in range(len(s)-1,-1,-1):
            if s[i] == " ":
                return len(s[i+1:])
        return len(s)
# @lc code=end

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

提示：

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] 仅包含小写字母

暴力破万法：

# @lc app=leetcode.cn id=49 lang=python3
#
# [49] 字母异位词分组
#

# @lc code=start
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        def matchstr(s,p):
            lens=len(s)
            lenp=len(p)
            if lens==lenp:
                for i in  range(len(p)):
                    if p[i] in s:
                        h=s.index(p[i])
                        s=s[0:h]+s[h+1:]
                        continue
                    else:
                        return False
                return True
            else:return False
        rev=list()
        rev.append([strs[0]])
        for i in range(1,len(strs)):
            k=0
            for j in range(len(rev)):
                #print(rev,j,i)
                if matchstr(rev[j][0],strs[i]):
                    rev[j].append(strs[i])
                    k=1
                    break
            if k==0:
                rev.append([strs[i]])
        return rev