分类： leetcode

给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。

示例 1：

输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。

示例 2：

输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]

示例 3：

输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]

提示：

• 1 <= s.length <= 104
• s 由小写英文字母组成
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 30
• words[i] 由小写英文字母组成

挨个匹配：

# @lc app=leetcode.cn id=30 lang=python3
#
# [30] 串联所有单词的子串
#

# @lc code=start
class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        import copy
        ls=len(s)
        lw=len(words)
        wordlen=len(words[0])
        dicts=dict()
        res=[]
        for i in range(lw):
            if words[i] in  dicts:
                dicts[words[i]]=dicts[words[i]]+1
            else:
                dicts[words[i]]=1
        for i in range(ls-wordlen*lw+1):
            new=copy.copy(dicts)
            rev=1
            for j in range(i,i+wordlen*lw,wordlen):
                if s[j:j+wordlen] in new and new[s[j:j+wordlen]]!=0:
                    new[s[j:j+wordlen]]-=1
                else:
                    rev=0
                    break
            if rev==1:
                res.append(i)
        return res




# @lc code=end

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例 1：

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

法 一：只交换值

# [25] K 个一组翻转链表
#
#法1 ：只交换值
# @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 reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        head1=head
        fhead= ListNode(0,head)
        head2=fhead
        end=0
        while head1!= None:
            nums=list()
            for i in range(k):
                head2=head2.next
                if head2==None:
                    end=1
                    break 
                #print(head2.val)   
                nums.append(head2.val)
            if end==0:
                for i in range(k):
                    head1.val=nums[k-1-i]
                    head1=head1.next
            else:
                for i in range(len(nums)):
                    head1.val=nums[i]
                    head1=head1.next
        return  fhead.next   
# @lc code=end

进阶：

• 你可以设计一个只使用常数额外空间的算法来解决此问题吗？
• 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

法二：节点交换（不只是单纯改变值） 代做。。

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

示例 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

给你一个非负整数 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

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