chenpaopao – 第 59 页 – 研究方向:语音识别语音大模型职业追求:AI改变世界，语音服务世界

leetcodeday24 –两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

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

代码：

# [24] 两两交换链表中的节点
#

# @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 swapPairs(self, head: ListNode) -> ListNode:
        # head0 = ListNode(0,head)
        if head==None or head.next==None:
            return head
        head0=head
        headr=head.next

        while head0!=None:
            head1=head0
            head2=head0.next
            head3=head2.next
            #print(head3.val)
            head2.next=head1
            if head3==None:    
                head1.next=None
                #print("is 1")
                return headr
            if head3.next==None:
                head1.next=head3
                #print("is 2")

                return headr
            else:
                head1.next=head3.next
                #print(head3.val)
                #print("is 0")

                head0=head3
                #print(head0.val)
        return headr

leetcodeday69 –求sqrt

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4
输出：2

示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

二分法求解：

# @lc app=leetcode.cn id=69 lang=python3
#
# [69] Sqrt(x)
#
#二分法
# @lc code=start
class Solution:
    def mySqrt( self,x: int) -> int:
        mid=x//2
        end=x
        start=0
        if x==1:
            return 1
        while end>start+1:
            l=mid**2            
            if  l==x:
                return mid
            if  l<x :
                start=mid
                mid = (mid+end)//2
                continue
            if  l>x:
                end=mid
                mid = (mid)//2
                continue
        return start

leetcodeday70 –爬楼梯

假设你正在爬楼梯。需要 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]

leetcodeday65–二进制求和

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

输入为非空字符串且只包含数字 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

leetcodeday64 –有效数字

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

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

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

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

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

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

部分有效数字列举如下：

["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

leetcodeday64 –最小路径和

给定一个包含非负整数的 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]

leetcodeday63 –不同路径 II

一个机器人位于一个 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]

leetcodeday62 –不同路径

一个机器人位于一个 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)

leetcodeday61–旋转链表

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

代码：

# @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

leetcodeday60 –排列序列

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

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

"123"
"132"
"213"
"231"
"312"
"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