chenpaopao

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

动态规划 or 递归

# @lc app=leetcode.cn id=70 lang=python3
#
# [70] 爬楼梯
#

# @lc code=start
class Solution:
    def climbStairs(self, n: int) -> int:
        dp=[0 for i in range(n)]
        
        for i in range(n):
            if i == 0:
                dp[0]=1
                continue
            if i == 1:
                dp[1]=2
                continue
            dp[i]=dp[i-1]+dp[i-2]
        return dp[n-1]

给你两个二进制字符串，返回它们的和（用二进制表示）。

输入为 非空 字符串且只包含数字 1 和 0。

示例 1:

输入: a = "11", b = "1"
输出: "100"

示例 2:

输入: a = "1010", b = "1011"
输出: "10101"

提示：

• 每个字符串仅由字符 '0' 或 '1' 组成。
• 1 <= a.length, b.length <= 10^4
• 字符串如果不是 "0" ，就都不含前导零。

代码：

# @lc app=leetcode.cn id=67 lang=python3
#
# [67] 二进制求和
#

# @lc code=start
from calendar import c


class Solution:
    def addBinary(self,a: str, b: str) -> str:
        def Binary(i,j,carry=0):
            i=int(i)
            j=int(j)
            carry=int(carry)
            carrys=(i+j+carry)//2
            n=(i+j+carry)%2
            return str(n),str(carrys)
        lena=len(a)
        lenb=len(b)
        rev=""
        if lena<lenb:
            c=a
            a=b
            b=c
        carry=0
        lens=max(lena,lenb)
        b="0"*abs(lena-lenb)+b
        for i in range(lens-1,-1,-1):
            #print(a[i],b[i],carry)
            n,carry=Binary(a[i],b[i],carry)
            rev=n+rev
        if carry=="1":
             rev=carry+rev
        return rev

有效数字（按顺序）可以分成以下几个部分：

1. 一个 小数 或者 整数
2. （可选）一个 'e' 或 'E' ，后面跟着一个 整数

小数（按顺序）可以分成以下几个部分：

1. （可选）一个符号字符（'+' 或 '-'）
2. 下述格式之一：
   1. 至少一位数字，后面跟着一个点 '.'
   2. 至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字
   3. 一个点 '.' ，后面跟着至少一位数字

整数（按顺序）可以分成以下几个部分：

1. （可选）一个符号字符（'+' 或 '-'）
2. 至少一位数字

部分有效数字列举如下：

• ["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"]

部分无效数字列举如下：

• ["abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"]

给你一个字符串 s ，如果 s 是一个 有效数字 ，请返回 true 。

解法1:(官方答案)

确定有限状态自动机

#
# @lc app=leetcode.cn id=65 lang=python3
#
# [65] 有效数字
#

# @lc code=start
from enum import Enum

class Solution:
    def isNumber(self, s: str) -> bool:
        State = Enum("State", [
            "STATE_INITIAL",
            "STATE_INT_SIGN",
            "STATE_INTEGER",
            "STATE_POINT",
            "STATE_POINT_WITHOUT_INT",
            "STATE_FRACTION",
            "STATE_EXP",
            "STATE_EXP_SIGN",
            "STATE_EXP_NUMBER",
            "STATE_END"
        ])
        Chartype = Enum("Chartype", [
            "CHAR_NUMBER",
            "CHAR_EXP",
            "CHAR_POINT",
            "CHAR_SIGN",
            "CHAR_ILLEGAL"
        ])

        def toChartype(ch: str) -> Chartype:
            if ch.isdigit():
                return Chartype.CHAR_NUMBER
            elif ch.lower() == "e":
                return Chartype.CHAR_EXP
            elif ch == ".":
                return Chartype.CHAR_POINT
            elif ch == "+" or ch == "-":
                return Chartype.CHAR_SIGN
            else:
                return Chartype.CHAR_ILLEGAL
        
        transfer = {
            State.STATE_INITIAL: {
                Chartype.CHAR_NUMBER: State.STATE_INTEGER,
                Chartype.CHAR_POINT: State.STATE_POINT_WITHOUT_INT,
                Chartype.CHAR_SIGN: State.STATE_INT_SIGN
            },
            State.STATE_INT_SIGN: {
                Chartype.CHAR_NUMBER: State.STATE_INTEGER,
                Chartype.CHAR_POINT: State.STATE_POINT_WITHOUT_INT
            },
            State.STATE_INTEGER: {
                Chartype.CHAR_NUMBER: State.STATE_INTEGER,
                Chartype.CHAR_EXP: State.STATE_EXP,
                Chartype.CHAR_POINT: State.STATE_POINT
            },
            State.STATE_POINT: {
                Chartype.CHAR_NUMBER: State.STATE_FRACTION,
                Chartype.CHAR_EXP: State.STATE_EXP
            },
            State.STATE_POINT_WITHOUT_INT: {
                Chartype.CHAR_NUMBER: State.STATE_FRACTION
            },
            State.STATE_FRACTION: {
                Chartype.CHAR_NUMBER: State.STATE_FRACTION,
                Chartype.CHAR_EXP: State.STATE_EXP
            },
            State.STATE_EXP: {
                Chartype.CHAR_NUMBER: State.STATE_EXP_NUMBER,
                Chartype.CHAR_SIGN: State.STATE_EXP_SIGN
            },
            State.STATE_EXP_SIGN: {
                Chartype.CHAR_NUMBER: State.STATE_EXP_NUMBER
            },
            State.STATE_EXP_NUMBER: {
                Chartype.CHAR_NUMBER: State.STATE_EXP_NUMBER
            },
        }

        st = State.STATE_INITIAL
        for ch in s:
            typ = toChartype(ch)
            if typ not in transfer[st]:
                return False
            st = transfer[st][typ]
        
        return st in [State.STATE_INTEGER, State.STATE_POINT, State.STATE_FRACTION, State.STATE_EXP_NUMBER, State.STATE_END]
# @lc code=end

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 100

思路：动态规划

# @lc app=leetcode.cn id=64 lang=python3
#
# [64] 最小路径和
#
#动态规划 dp[i][j]时到i,j的最小路径和
# @lc code=start
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        row = len(grid)
        col = len(grid[0])
        dp=[[0]*col for i in range(row)]
        for i in range(row):
            for j in range(col):
                if i == 0 and j!=0:
                    dp[i][j]=dp[i][j-1]+grid[i][j]
                elif j == 0 and i!=0:
                    dp[i][j]=dp[i-1][j]+grid[i][j]
                elif i==0 and j==0:
                    dp[i][j]=grid[0][0]
                else :
                    dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]
        return dp[row-1][col-1]

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1：

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

动态规划：dp[i][j]表示从00到ij的所有可能的路径数量（一般dp数组就表示我们要求的结果）

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:

        m, n = len(obstacleGrid), len(obstacleGrid[0])
        if m == 1 and n == 1:
            if obstacleGrid[0][0] == 1: return 0
            else: return 1
        
        dp = [[0] * n for _ in range(m)]

        for i in range(m):
            if obstacleGrid[i][0] == 1: break
            dp[i][0] = 1
        
        for j in range(n):
            if obstacleGrid[0][j] == 1: break
            dp[0][j] = 1
        
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 1:
                    dp[i][j] = 0
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        
        return dp[-1][-1]

一个机器人位于一个 m x n网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

输入：m = 3, n = 7
输出：28

示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

思路：将该问题转换为：走m-1 步1，走n-1步0，所有的排列组合：

即 m-1 个A和 n-1个B的排列组合数：

采用推导法：已知 m-1 个A和 n-1个B的排列组合数 ，那么根据 m-1 个A和 n-1个B的排列组合数 推导m个A，n个B的排列组合数。

(1) 当有m个A和n个B时，总的排列数为(m+n)!/m!/n!;

(2) 由于不知道m和n哪个大，故两个值都减1，最后知道m和n中其中一个为0；

(3) 当有m-1个A和n-1个B时，总的排列数为(m+n-2)!/(m-1)!/(n-1)!;

(4)这样两个的关系为：fun(m,n) = fun(m-1,n-1)(m+n)(m+n-1)/m/n;

# @lc app=leetcode.cn id=62 lang=python3
#
# [62] 不同路径
#

# @lc code=start
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        m=m-1
        n=n-1
        def subuniquePaths(m,n):
            if m==0 or n==0:
                return 1
            else:
                return int(subuniquePaths(m - 1 , n - 1)*(m + n)*(m+n-1)/m/n)
        return subuniquePaths(m,n)

给你一个链表的头节点 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