作者： chenpaopao

以数组 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

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：

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

示例 2：

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

提示：

• n == matrix.length == matrix[i].length
• 1 <= n <= 20
• -1000 <= matrix[i][j] <= 1000

思路：先转置，在每行倒序

# @lc code=start
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        mid=0
        n=len(matrix)
        for i  in range(n):
            for j in range(i):
                mid = matrix[i][j]
                matrix[i][j] = matrix[j][i]
                matrix[j][i] =  mid 
        for i  in range(n):
            for j in range(n//2):
                mid=matrix[i][j]
                matrix[i][j]=matrix[i][n-j-1]
                matrix[i][n-j-1] = mid
# @lc code=end

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2：

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

提示：

• 1 <= nums.length <= 8
• -10 <= nums[i] <= 10

递归求解：

# [46] 全排列
#

# @lc code=start
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        import copy
        def subpermute(nums,index):
            if index==0:
               return [[nums[0]]]
            else:
                rev=subpermute(nums,index-1)
                res=list()
                for i in range(len(rev)):
                    #print(rev[i])
                    for j in range(len(rev[i])+1):
                        if j==len(rev[i]) or rev[i][j]!=nums[index]:
                            mid=copy.deepcopy(rev[i])
                        #print(mid)
                            mid.insert(j,nums[index])
                            if mid not in res:
                               res.append(mid)
                        
                return res
        index=len(nums)-1
        return subpermute(nums,index)

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

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

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

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

提示：

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• nums 中的所有整数 互不相同

暴力求解：

# [46] 全排列
#

# @lc code=start
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        import copy
        def subpermute(nums,index):
            if index==0:
               return [[nums[0]]]
            else:
                rev=subpermute(nums,index-1)
                res=list()
                for i in range(len(rev)):
                    #print(rev[i])
                    for j in range(len(rev[i])+1):
    
                        mid=copy.deepcopy(rev[i])
                        #print(mid)
                        mid.insert(j,nums[index])
                        res.append(mid)
                        
                return res
        index=len(nums)-1
        return subpermute(nums,index)

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn ）。

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：

输入：x = 2.10000, n = 3
输出：9.26100

示例 3：

输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

# [50] Pow(x, n)
#

# @lc code=start
class Solution:
    def myPow(self, x: float, n: int) -> float:
        return pow(x, n)