LeetCode Hot 100刷题笔记(2)

65.电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

解：

法1：遍历所有结果，构造字符串

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        num_str={
            '2':'abc',
            '3':'def',
            '4':'ghi',
            '5':'jkl',
            '6':'mno',
            '7':'pqrs',
            '8':'tuv',
            '9':'wxyz'
        }
        ans=[[]]
        for i in digits:
            i_str=num_str[i]
            path=[]
            for j in  ans:
                for c in i_str:
                    temp=j[:]
                    temp.append(c)
                    path.append(temp)
            ans=path[:]
        res=[]
        for i in ans:
            res.append(''.join(i))

        return res

法2：递归回溯

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        num_str={
            '2':'abc',
            '3':'def',
            '4':'ghi',
            '5':'jkl',
            '6':'mno',
            '7':'pqrs',
            '8':'tuv',
            '9':'wxyz'
        }
        n = len(digits)
        if n == 0:
            return []
  
        ans = []
        path = [''] * n  # 注意 path 长度一开始就是 n，不是空列表

        def dfs(i: int) -> None:
            if i == n:
                ans.append(''.join(path))
                return
            for c in num_str[digits[i]]:
                path[i] = c  # 直接覆盖
                dfs(i + 1)

        dfs(0)
        return ans

66.字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

测试用例保证输出的长度不会超过 10⁵。

示例 1：

输入：s = "3[a]2[bc]"
输出："aaabcbc"

解：

递归，当字符为数字时，计算k，当字符为字母时，向res中加，当字符为‘[’时，说明重复开始，当前k为重复次数，当字符为‘[’时，说明重复结束。

class Solution:
    def decodeString(self, s: str) -> str:
        i=0
        def decode()->str:
            nonlocal i
            res=''
            k=0
            while i<len(s):
                c=s[i]
                i+=1
                if  '0'<=c<='9':
                    k=k*10+int(c)
                elif 'a'<=c<='z':
                    res+=c 
                elif c=='[':
                    res+=decode()*k
                    k=0
                elif c==']':
                    break
            return res
       
        return  decode()

67.数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

解：

通过快排逻辑快速定位第k大元素位置

class Solution:
    def partition(self,nums:List[int],left:int,right:int)->int:

        i=randint(left,right)
        povit=nums[i]

        nums[left],nums[i]=nums[i],nums[left]

        l,r=left+1,right

        while True:
            while l<=r and nums[l]<povit:
                l+=1
            while l<=r and nums[r]>povit:
                r-=1
            if l>=r:
                break
            nums[l],nums[r]=nums[r],nums[l]
            l+=1
            r-=1
        nums[left],nums[r]=nums[r],nums[left]
        return r

    def findKthLargest(self, nums: List[int], k: int) -> int:
        target_num=len(nums)-k
        left,right=0,len(nums)-1
        while True:
            i=self.partition(nums,left,right)
            if i==target_num:
                return nums[i]
            elif i>target_num:
                right=i-1
            elif i<target_num:
                left=i+1

68.组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

解：

每次选择选或不选，递归回溯

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        ans = []
        path = []

        def dfs(i: int, left: int) -> None:
            if left == 0:
                # 找到一个合法组合
                ans.append(path.copy())
                return

            if i == len(candidates) or left < candidates[i]:
                return

            # 不选
            dfs(i + 1, left)

            # 选
            path.append(candidates[i])
            dfs(i, left - candidates[i])
            path.pop()  # 恢复现场

        dfs(0, target)
        return ans

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 向左旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 下标 3 上向左旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

解：

找到最小值位置，分成两段二分查找，闭区间写法注意越界判定处理

class Solution:
    def findmin(self,nums:List[int])->int:
        left,right=0,len(nums)-1
        while left<=right:
            mid=(left+right)//2
            if nums[mid]<nums[-1]:
                right=mid-1
            else:
                left=mid+1
        if left<0:
            return 0
        elif left>len(nums)-1:
            return len(nums)-1
        else:
            return left

    def erfen(self, nums: List[int], target: int,left:int,right:int)->int:
        while left<=right:
            mid=(left+right)//2
            if nums[mid]<target:
                left=mid+1
            else:
                right=mid-1
        if 0 <= left < len(nums) and nums[left] == target:
            return left
        else:
            return -1

    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        k=self.findmin(nums)
        if target>nums[-1]:
            return self.erfen(nums,target,0,k-1)
        else :
            return self.erfen(nums,target,k,len(nums)-1)

70.前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1：

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

输出：[1,2]

解：

统计频率后以频率为key进行桶排序，再反向遍历合并前k高个元素

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # 第一步：统计每个元素的出现次数
        cnt = Counter(nums)
        max_cnt = max(cnt.values())

        # 第二步：把出现次数相同的元素，放到同一个桶中
        buckets = [[] for _ in range(max_cnt + 1)]  # 也可以用 defaultdict(list)
        for x, c in cnt.items():
            buckets[c].append(x)

        # 第三步：倒序遍历 buckets，把出现次数前 k 大的元素加入答案
        ans = []
        for bucket in buckets[::-1]:
            ans += bucket
            # 注意题目保证答案唯一，一定会出现恰好等于 k 的情况
            if len(ans) == k:
                return ans

71.杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

解：

nums[i][j]=nums[i-1][j-1]+nums[i-1][j]

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        ans=[[1]*(i+1)for i in range(numRows)]
        for i in range(2,numRows):
            for j in range(1,i):
                ans[i][j]=ans[i-1][j-1]+ans[i-1][j]
        return ans

72.打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

解：

#ans[i+2]=max(ans[i]+nums[i],ans[i+1])

class Solution:
    def rob(self, nums: List[int]) -> int:
        #ans[i+2]=max(ans[i]+nums[i],ans[i+1])
        ans=[0]*(len(nums)+2)
        for i in range(0,len(nums)):
            ans[i+2]=max(ans[i+1],ans[i]+nums[i])
        return ans[-1]

73.括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

解：

选或不选，dfs(left,right),left为左括号数，right为右括号数，left小于n则可选左括号，right小于left则可选右括号，right为n是结束。

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans=[]
        path=['']*(2*n)
        def dfs(Left:int,right:int)->None:
            if right==n:
                ans.append(''.join(path))
                return
            if Left<n:
                path[Left+right]='('
                dfs(Left+1,right)
            if right<Left:
                path[Left+right]=')'
                dfs(Left,right+1)
        dfs(0,0)
        return ans

74.单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCCED"
输出：true

解：

dfs,寻找所有可能起点进行dfs,将结果进行或操作，即有一条路通即可

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        row,col=len(board),len(board[0])
        def dfs(r:int,c:int,k:int)->bool:
            if board[r][c]!=word[k]:
                return False
            if k==len(word)-1:
                return True
            board[r][c]=''
            for x,y in (r,c-1),(r+1,c),(r,c+1),(r-1,c):
                if 0<=x<row and 0<=y<col :
                    if dfs(x,y,k+1):
                        return True
            board[r][c]=word[k]
            return False
        ans=False
        for i in range(row):
            for j in range(col):
                if board[i][j]==word[0]:
                    ans=ans or dfs(i,j,0)
        return ans

75.每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

解：

单调栈，动态维护近期最大值.从左向右思考不知道下一个更大值在哪，从右向左思考可以获取这些信息

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        ans = [0] * n
        st = []
        for i in range(n - 1, -1, -1):
            t = temperatures[i]
            #新的数大于老的数，老数弹出
            while st and t >= temperatures[st[-1]]:
                st.pop()
            #弹出后数栈不为空，[-1]位置上即为最近的大于本身的数
            if st:
                ans[i] = st[-1] - i
            #将新数入栈
            st.append(i)
        return ans

76.跳跃游戏 II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置在下标 0。

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处：

0 <= j <= nums[i] 且
i + j < n

返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

解：

cur记录N步能到达的最远距离，right记录以上一步和这一步之间的某点为起点能到达的最远距离。

class Solution:
    def jump(self, nums: List[int]) -> int:
        cur=0
        right=0
        step=0
        for i in range(len(nums)-1):
            right=max(i+nums[i],right)
            if i==cur:
                cur=right
                step+=1
        return step

77.划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 "ababcc" 能够被分为 ["abab", "cc"]，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。示例 1：

输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。

解：

将分段内所有字母第一个出现的位置与最后一个出现的位置合并即为一个满足要求的分段，起始位置从起点开始即可，终点需要知道字母最终出现的位置，因此先遍历一次记录每个字母的终点

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        hs={}
        start=end=0
        ans=[]
        for i,c in enumerate(s):
            hs[c]=i
        for i,c in enumerate(s):
            end=max(end,hs[c])
            if i==end:
                ans.append(end-start+1)
                start=end+1
                end=end+1
        return ans

78.完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n = 12
输出：3
解释：12 = 4 + 4 + 4

解：

递归方法，选或不选

@cache
def dfs(x:int,left:int)->bool:
    if x==0 :
        #left不为0则错误，用inf忽略此路径
        return inf if left else 0
    if x*x>left:
        return dfs(x-1,left)
    return min(dfs(x-1,left),dfs(x,left-x*x)+1)
class Solution:

    def numSquares(self, n: int) -> int:

        return dfs(isqrt(n),n)

递推

N = 10000 #n小于等于10000，题目条件
f = [[0] * (N + 1) for _ in range(isqrt(N) + 1)]
f[0] = [0] + [inf] * N
for i in range(1, len(f)):
    for j in range(N + 1):
        if j < i * i:
            f[i][j] = f[i - 1][j]  # 只能不选
        else:
            f[i][j] = min(f[i - 1][j], f[i][j - i * i] + 1)  # 不选 vs 选

class Solution:
    def numSquares(self, n: int) -> int:
        return f[isqrt(n)][n]  # 也可以写 f[-1][n]

79. 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1

解：

递归，选或不选

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        coins_sort=sorted(coins)
        n=len(coins)
        def dfs(x:int,left:int)->int:
            if x==-1:
                return inf if left else 0
            if left<coins_sort[x]:
                return dfs(x-1,left)
            return min(dfs(x-1,left),dfs(x,left-coins_sort[x])+1)
        ans=dfs(n-1,amount)
        return ans if ans<inf else -1

递推：

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        n = len(coins)
        f = [[inf] * (amount + 1) for _ in range(n + 1)]
        f[0][0] = 0
        for i, x in enumerate(coins):
            for c in range(amount + 1):
                if c < x:  #c<x，不取币
                    f[i + 1][c] = f[i][c]
                else:     #c>=x，取币
                    f[i + 1][c] = min(f[i][c], f[i + 1][c - x] + 1)
        ans = f[n][amount]
        return ans if ans < inf else -1

80.单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

解：

从后向前，匹配切片是否在词表中，在的话则将剩余部分进行递归

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        max_len=max(map(len,wordDict))
        words=set(wordDict)
        @cache
        def dfs(i:int)->bool:
            if i==0:
                return True
            for j in range(i-1,max(i-max_len-1,-1),-1):
                if s[j:i] in words and dfs(j):
                    return True
            return False
        return dfs(len(s))

81.最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

解：

从第0个元素开始逐步向右展开遍历区间，每次扩展一个元素，遍历前序分别当作上一跳起点，判断是否递增，是则进行一次比较。

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        f=[0]*len(nums)
        for i,x in enumerate(nums):
            for j,y in enumerate(nums[:i]):
                if x>y:
                    f[i]=max(f[i],f[j])
            f[i]+=1
        return max(f)

82.乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

请注意，一个只包含一个元素的数组的乘积是这个元素的值。

示例 1:

输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

解：

最大最小都记录并运算，避免符号影响

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        n=len(nums)
        f_min=[0]*n
        f_max=[0]*n 
        f_max[0]=f_min[0]=nums[0]
        for i in range(1,n):
            x=nums[i]
            f_min[i]=min(f_max[i-1]*x,f_min[i-1]*x,x)
            f_max[i]=max(f_max[i-1]*x,f_min[i-1]*x,x)
        return max(f_max)

83.分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

解：

每两个字符之间均可选择断开或不断开，遍历所有选择并判断是否回文

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n=len(s)
        ans=[]
        path=[]

        def dfs(i:int,start:int)->None:
            if i==n:
                ans.append(path[:])
                return
            if i<n-1:
                dfs(i+1,start)
            t=s[start:i+1]
            if t==t[::-1]:
                path.append(t)
                dfs(i+1,i+1)
                path.pop()
        dfs(0,0)
        return ans

84.寻找旋转排序数组中的最小值

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

解：

旋转前是有序的，同样可以采用二分查找，

若nums[mid]<nums[-1],则最小值位于[left,mid],反之位于[mid,right]

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left,right=0,len(nums)-1
        while left<=right:
            mid=(left+right)//2
            if nums[mid]<nums[-1]:
                right=mid-1
            else:
                left=mid+1
        i= min(left,len(nums)-1) #最小值位于最后时left会越界，取min防止越界
        return nums[i]

85. 寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

解：

暂时给出O（(m+n)/2）的方法

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        m, n = len(nums1), len(nums2)
        total_length = m + n
        
        # 1. 确定需要收集的目标位置（索引从0开始）
        if total_length % 2 == 1:
            # 奇数：只取中间1个
            target_indices = [total_length // 2]
        else:
            # 偶数：取中间2个
            target_indices = [total_length // 2 - 1, total_length // 2]
        
        l1 = l2 = 0  # 双指针
        current_index = 0  # 当前遍历到的全局索引
        result = []  # 存储目标位置的元素
        
        # 2. 遍历直到收集完所有目标元素（核心优化：提前终止）
        while len(result) < len(target_indices):
            # 安全获取当前要取的元素（优先处理边界）
            if l1 >= m:
                # nums1已遍历完，只取nums2
                val = nums2[l2]
                l2 += 1
            elif l2 >= n:
                # nums2已遍历完，只取nums1
                val = nums1[l1]
                l1 += 1
            else:
                # 取两个数组中较小的元素
                if nums1[l1] < nums2[l2]:
                    val = nums1[l1]
                    l1 += 1
                else:
                    val = nums2[l2]
                    l2 += 1
            
            # 3. 如果当前索引是目标索引，收集元素
            if current_index in target_indices:
                result.append(val)
            
            current_index += 1
        
        # 4. 计算中位数
        return sum(result) / len(result)

86.分割等和子集

给你一个 只包含正整数 的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

解：

选或不选，递归

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        n_sum=sum(nums)
        n=len(nums)
        @cache
        def dfs(i:int,j:int)->bool:
            if i<0:
                return j==0
            if j<nums[i]:
                return dfs(i-1,j)
            return dfs(i-1,j-nums[i]) or dfs(i-1,j)
        return n_sum%2==0 and dfs(n-1,n_sum//2)

递推形式，思想也为选或不选，遍历n个节点能选到的结果置true

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        s = sum(nums)
        if s % 2:
            return False
        s //= 2  # 注意这里把 s 减半了
        n = len(nums)
        f = [[False] * (s + 1) for _ in range(n + 1)]
        f[0][0] = True
        for i, x in enumerate(nums):
            for j in range(s + 1):
                f[i + 1][j] = j >= x and f[i][j - x] or f[i][j]
        return f[n][s]

87.不同路径

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

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

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

示例 1：

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

解：

m[i][j]=m[i-1][j]+m[i][j-1]

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        mp=[[1]*n for _ in range(m)]
        for i in range(1,m):
            for j in range(1,n):
                mp[i][j]=mp[i-1][j]+mp[i][j-1]
        return mp[m-1][n-1]

88.最小路径和

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

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

示例 1：

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

解：

m[i][j]+=min(m[i-1][j],m[i][j-1])

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        row,col = len(grid),len(grid[0])
        for i in range(1,row):
            grid[i][0]+=grid[i-1][0]
        for i in range(1,col):
            grid[0][i]+=grid[0][i-1]
        for i in range(1,row):
            for j in range(1,col):
                grid[i][j]+=min(grid[i-1][j],grid[i][j-1])
        return grid[row-1][col-1]

89.最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

解：

遍历字符串，以字符为中心向两侧扩展，寻找最长回文

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n=len(s)
        ans_left=ans_right=0
        for i in range(2*n-1):
            l,r=i//2,(i+1)//2
            while l>=0 and r<n and s[l]==s[r]:
                l-=1
                r+=1
            if r-l-1>ans_right-ans_left:
                ans_left,ans_right=l+1,r 
        return s[ans_left:ans_right]

90.最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace" ，它的长度为 3 。

解：

把text1作为纵轴，text2作为横轴，挨个对比，字母相同则mp[i][j]=mp[i-1][j-1]+1,不同则直接继承mp[i][j]=max(mp[i-1][j],mp[i][j-1])

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m,n=len(text1),len(text2)
        mp=[[0]*(n+1) for _ in range(m+1)]
        for i in range(1,m+1):
            for j in range(1,n+1):
                if text1[i-1]==text2[j-1]:
                    mp[i][j]=mp[i-1][j-1]+1
                else:
                    mp[i][j]=max(mp[i-1][j],mp[i][j-1])
        return mp[m][n]

91.编辑距离

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

解：

word1作为纵轴，word2作为横轴，初始化第一行，值为range(len(s)+1),含义是一个字符串一直跳过直到第一个首字母匹配上需要操作的次数，第一列在遍历时初始化.遍历时遇到两种情况，匹配与不匹配，匹配则都向后移一个元素，不匹配则选择删除（插入）或替换

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n,m =len(word1),len(word2)
        f=[[0]*(m+1) for _ in range(n+1)]
        f[0]=list(range(m+1))
        for i,x in enumerate(word1):
            f[i+1][0]=i+1
            for j,y in enumerate(word2):
                #相等则进下一步，不等则A插入或B插入或替换
                f[i+1][j+1]=f[i][j] if x==y else min(f[i][j+1],f[i+1][j],f[i][j])+1
        return f[n][m]

92.只出现一次的数字

给你一个非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：

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

输出：1

解:

利用异或运算 a^a=0的特性，将出现两次的数清除，剩下结果即为只出现一次的数

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res=0
        for i in nums:
            res ^=i 
        return res

93.多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

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

解：

摩尔投票法，类似打擂台一换一，多数元素超过半数，一换一最后剩下的元素一定是它

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        cnt=1
        last=nums[0]
        for i in range(1,len(nums)):
            if cnt==0:
                last=nums[i]
                cnt+=1
                continue
            if nums[i]!=last:
                cnt-=1
            else:
                cnt+=1
        return last

94.颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

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

解：

三指针，中间指针指向0，则跟左指针交换，指向2则跟右指针交换

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # 分别指向0，1，2区域
        low, mid, high = 0, 0, len(nums) - 1
        # mid是活动指针
        while mid <= high:
            if nums[mid] == 0:  # 说明要交换到0区
                nums[low], nums[mid] = nums[mid], nums[low]
                low += 1
                mid += 1
            elif nums[mid] == 1:  # 正好
                mid += 1
            else:  # 否则交换到2区
                nums[mid], nums[high] = nums[high], nums[mid]
                high -= 1

95.下一个排列

整数数组的一个排列就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums ，找出 nums 的下一个排列。

必须原地修改，只允许使用额外常数空间。

示例 1：

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

解：

从右往左找到右边存在比左边大的数，思路为判断左边的数是否比起相邻的右边的数小，若是，则找到

在从右往左寻找第一个比此数大的数，交换位置

再将left+1至结尾进行反转，将原本的降序转为升序，得到最小尾部

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n=len(nums)
        i=n-2
        while i>=0 and nums[i]>=nums[i+1]:
            i-=1
        if i>=0:
            j=n-1
            while nums[j]<=nums[i]:
                j-=1
            nums[i],nums[j]=nums[j],nums[i]
        left,right = i+1,n-1
        while left<right:
            nums[left],nums[right]=nums[right],nums[left]
            left+=1
            right-=1

96.寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

示例 1：

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

解：

法1：

把元素换到对的位置上，使得nums[i]=nums[nums[i]-1]

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        n = len(nums)
        # 遍历每个位置，将元素归位
        for i in range(n):
            # 当当前元素不在自己的正确位置时，才处理
            while nums[i] != i + 1:
                # 取出当前元素的值
                val = nums[i]
                # 检查：val的正确位置（val-1）是否已有相同值 → 说明val重复
                if nums[val - 1] == val:
                    return val
                # 否则，将val交换到正确位置
                nums[i], nums[val - 1] = nums[val - 1], nums[i]

法2：

把列表抽象成链表，找环列表nums[i]的下一跳是nums[nums[i]]

# 代码逻辑同 142. 环形链表 II
class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow = fast = 0  # 0 一定不在环上，适合作为起点
        while True:
            slow = nums[slow]  # 等价于 slow = slow.next
            fast = nums[nums[fast]]  # 等价于 fast = fast.next.next
            if fast == slow:  # 快慢指针移动到同一个节点
                break

        head = 0  # 再用一个指针，从起点出发
        while slow != head:
            slow = nums[slow]
            head = nums[head]
        return slow  # 入环口即重复元素

97.字符串相加

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库（比如 BigInteger），也不能直接将输入的字符串转换为整数形式。

示例 1：

输入：num1 = "11", num2 = "123"
输出："134"

解：

模拟加法计算即可

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        res=""
        #指向两数个位
        i,j,carry=len(num1)-1,len(num2)-1,0
        while i>=0 or j>=0:
        #数不存在补0
            n1=int(num1[i]) if i >=0 else 0
            n2=int(num2[j]) if j >=0 else 0
            tmp=n1+n2+carry
            carry=tmp//10
            res=str(tmp%10)+res
            i,j=i-1,j-1
        #进位还存在则加一位1
        return '1'+res if carry else res