leetcode精选100

leetcode精选100题

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
class Solution:
    def twoSum1(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        return [[i,j] for i in range(len(nums)) for j in range(len(nums)) if nums[i]+nums[j] == target and i != j][0]
    def twoSum(self, nums, target):
        assist = {}
        for i, num in enumerate(nums):
            other = target - num
            if other not in assist:
                assist[num] = i
            else:
                return [i, assist[other]]

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        """
        分析：
        由于链表是按照逆序的方式存储的，所有最开始的就是各位，因此直接按照按位计算加法即可
        1. 需要计算进位
        2. 需要将最后长的那一个链表加进来
        3. 题目要求返回一个新的链表来表示他们的和，但是如果允许修改原链表的话，可以不申请新的内存
        """
        head = ListNode(0)
        cur = head
        carry = 0
        while l1 or l2:
            data1 = l1.val if l1 else 0
            data2 = l2.val if l2 else 0
            s = data1+data2+carry
            carry = s // 10
            s %= 10
            cur.next = ListNode(s)
            cur = cur.next
            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next
        if carry:
            cur.next = ListNode(1)
        return head.next

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        """
        滑窗法：
        设置两个指针，start和end，每次end+=1，记录当前点访问的次数
        """
        res, start, end = 0, 0, 0
        count_dict ={}
        for c in s:
            end += 1
            count_dict[c] = count_dict.get(c,0)+1
            while count_dict[c] > 1:
                count_dict[s[start]] -= 1
                start += 1
            res = max(res, end-start)
        return res

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        nums = nums1+nums2
        nums.sort()
        if len(nums)%2 == 0:
            return (nums[(len(nums)-1)//2]+nums[(len(nums)-1)//2+1])/2.0
        else:
            return(nums[(len(nums)-1)//2])

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
class Solution:
    def __init__(self):
        self.lens = None
        self.startIndex = None
    def longestPalindrome(self, s: str) -> str:
        ‘‘‘
        # 动态规划，状态转移法
        if not s or len(s) <=1:
            return s
        n = len(s)
        # 状态转移矩阵
        historyRecord = [[0] * n for _ in range(n)]
        self.lens = 1
        self.startIndex = 0
        # 初始化长度为1的回文字符串信息
        for i in range(n):
            historyRecord[i][i] = 1
        # 初始化长度为2的回文字符串信息
        for i in range(n-1):
            if s[i] == s[i+1]:
                historyRecord[i][i+1] = 1
                self.startIndex = i
                self.lens = 2
        # 从3开始遍历长度为k的回文字符串信息
        for k in range(3, n+1):
            i = 0
            while i < n-k+1:
                j = i+k-1
                if s[i] == s[j] and historyRecord[i+1][j-1] == 1:
                    historyRecord[i][j] = 1
                    self.startIndex = i
                    self.lens = k
                i += 1
        # print(self.startIndex, self.lens)
        return s[self.startIndex:self.startIndex+self.lens]
        ‘‘‘
        ‘‘‘
        # 中心扩展法
        if not s and len(s)<=1:
            return s
        self.lens = 1
        self.startIndex = 0
        for i in range(len(s)-1):
            # 当回文数中心为一个数时
            self.expandBothSide(s, i, i)
            # 当回文数中心为两个数时
            self.expandBothSide(s, i, i+1)
        return s[self.startIndex:self.startIndex+self.lens]
    def expandBothSide(self, s, c1, c2):
        n = len(s)
        while c1 >= 0 and c2 < n and s[c1] == s[c2]:
            c1 -= 1
            c2 += 1
        tmpStartIndex = c1 + 1
        tmpLens = c2-c1-1
        if tmpLens > self.lens:
            self.lens = tmpLens
            self.startIndex = tmpStartIndex
    ‘‘‘
        # manacher算法...

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.‘ 和 ‘*‘ 的正则表达式匹配。
class Solution:
    def __init__(self):
        self.memo = dict()
    def isMatch(self, s: str, p: str) -> bool:
        """
        依次遍历s和p的每一个字符：
        1. 如何p[j]不为‘*’和‘.’，此时判断s[i] == p[j],相等i++, j++，不相等返回False
        2. 如果p[j] == ‘.‘,直接i++, j++
        3. 如果p[j+1] == ‘*‘
            a. 如果s[i] ！= s[j], j += 2,继续判断
            b. 如果s[i] == p[j] or p[j] == ‘.‘，分为三种情况，1， *匹配0个，1个和多个 
        """
        # 这里引入备忘录，记录中间结果，减小计算量
        memo = dict()
        def dp(i, j):
            if (i, j) in memo: return memo[(i,j)]
            if j == len(p): return i == len(s)
            first_match = i < len(s) and p[j] in [s[i], ‘.‘]
            if j <= len(p)-2 and p[j+1] == ‘*‘:
                ans = dp(i, j+2) or (first_match and dp(i+1, j))
            else:
                ans = first_match and dp(i+1, j+1)
            memo[(i,j)] = ans
            return ans
        return dp(0,0)

11. 盛最多水的容器
class Solution:
    def maxArea(self, height: List[int]) -> int:
        # 双指针法，每次记录最大面积，指向短的那一条边向中间移动
        max_area = 0
        i = 0
        j = len(height) - 1
        while i < j:
            max_area = max_area if max_area > (j-i)*min(height[i], height[j]) else (j-i)*min(height[i], height[j])
            if height[i] < height[j]:
                i += 1
            else:
                j -= 1
        return max_area

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        """
        1. 先进行排序，时间负责度为O（nlogn）
        2. 选定一个作为参照点，（不是中心点），左右各需一人，且加起来为0，如果小于0，左边++，大于0，右边--
        3. 边界条件优化：
            ①：整个数组同号则误解，nums[0] <= 0 and nums[-1]>=0
            ②：三元组中的左边数为正数，则无解，这里的参照点就是最左边点
            ③：
        """
        length = len(nums) 
        resultList = [] 
        nums.sort() 
        for i in range(0,length-2):
            if i>0 and nums[i] == nums[i-1]:
                continue
            if nums[i]>0:
                break
            j = i + 1 
            k = length - 1 
            while j < k: 
                sum0 = nums[i] + nums[j] + nums[k]
                if sum0 == 0: 
                    resultList.append([nums[i], nums[j], nums[k]])
                    while j < k and nums[j] == nums[j+1]:
                        j += 1
                    while j < k and nums[k]==nums[k-1]:
                        k -= 1
                    j +=1 
                    k -=1
                elif sum0 < 0: 
                    j +=1 
                else: 
                    k -=1
        return resultList

17. 电话号码的字母组合
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        """
        # 非常直观的递归方法
        if not digits:
            return []
        num_char_dict = {‘2‘:"abc",‘3‘:"def",‘4‘:"ghi",‘5‘:"jkl",‘6‘:"mno",‘7‘:"pqrs",‘8‘:"tuv",‘9‘:"wxyz"}
        res = []
        length = len(digits)
        def find_char(i, tmp):
            if i == length:
                res.append(tmp)
                return
            for char in num_char_dict[digits[i]]:
                find_char(i+1, tmp+char)
        find_char(0, "")
        return res
        """
        # DFS
        if not digits:
            return []
        num_char_dict = {‘2‘:"abc",‘3‘:"def",‘4‘:"ghi",‘5‘:"jkl",‘6‘:"mno",‘7‘:"pqrs",‘8‘:"tuv",‘9‘:"wxyz"}
        res = [‘‘]
        for i in digits:
            res = [k+j for k in res for j in num_char_dict[i]]
        return res

20. 有效的括号
class Solution:
    def isValid(self, s: str) -> bool:
        # 模拟入栈，出栈，最后栈为空即可
        pair_dict = {"(":")", "[":"]", "{":"}"}
        stack = []
        length = len(s)
        i = 0
        while length > i:
            if stack and pair_dict.get(stack[-1], 0) == s[i]:
                stack.pop()
            else:
                stack.append(s[i])
            i += 1
        if not stack:
            return True
        else:
            return False

21. 合并两个有序链表
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        ‘‘‘
        # 使用递归操作
        if not l1:
            return l2
        if not l2:
            return l1
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2
        ‘‘‘
        # 使用迭代法
        prehead = ListNode(0)
        new_p = prehead
        while l1 and l2:
            if l1.val <= l2.val:
                new_p.next = l1
                l1 = l1.next
            else:
                new_p.next = l2
                l2 = l2.next
            new_p = new_p.next
        new_p.next = l1 if l1 else l2
        return prehead.next

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        def backtrack(S="", left =0 ,right = 0):
            if len(S) == 2*n:
                ans.append(S)
                return
            if left < n:
                backtrack(S+"(", left+1, right)
            if right < left:
                backtrack(S+")", left, right+1)
        backtrack()
        return ans

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        # 将K个链表两两结合，这里可以采用分治的思想，因此只需要执行logk次合并
        length = len(lists)
        interval = 1
        while interval < length:
            for i in range(0, length-interval, 2*interval):
                lists[i] = self.merge2Lists(lists[i], lists[i+interval])
            interval *= 2
        return lists[0] if length >0 else lists
    def merge2Lists(self, l1, l2):
        if not l1:
            return l2
        if not l2:
            return l1
        if l1.val < l2.val:
            l1.next = self.merge2Lists(l1.next, l2)
            return l1
        else:
            l2.next = self.merge2Lists(l1, l2.next)
            return l2

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        #1. 从后面进行遍历，依次比较相邻数字大小，直到nums[i] > nums[i-1]
        #2. 将该数插入到后面有序数组的相应位置
        #3. 对后面数组进行翻转
        i = len(nums)-2
        while i >= 0 and nums[i] >= nums[i+1]:
            i -= 1
        if i >= 0:
            j = len(nums)-1
            while j >= 0 and nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]
        # 对后面的数组进行翻转
        start = i+1
        end = len(nums)-1
        while start < end:
            nums[start], nums[end] = nums[end], nums[start]
            start += 1
            end -= 1
        print(nums)

给定一个只包含 ‘(‘ 和 ‘)‘ 的字符串，找出最长的包含有效括号的子串的长度。
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        ‘‘‘ 
        采用动态规划方法
        1. 创建一个dp数组，dp[i]表示以第i个字符为结束符的有效括号的长度
        2. 对每两个字符检查一次。
            a. 如果s[i] = ‘)‘,s[i-1] = "(", 那么dp[i] = dp[i-2]+2
            b. 如果s[i] = ‘)‘,s[i-1] = ‘)‘,并且s[i-dp[i-1]-1],那么dp[i] = dp[i-1]+dp[i-dp[i-1]-2]+2
        ‘‘‘
        if not s:
            return 0
        dp = [0 for i in range(len(s))]
        for i in range(1, len(s)):
            if s[i] == ")":
                if s[i-1] == "(":
                    dp[i] = dp[i-2]+2 if i >= 2 else 2
                elif (i - dp[i-1] - 1) >= 0 and s[i-dp[i-1]-1] == "(":
                    print(i)
                    dp[i] = (dp[i-1] + dp[i-dp[i-1]-2]+2) if (i-dp[i-1]) >= 2 else (dp[i-1]+2)
        print(dp)
        return max(dp) 

33. 搜索旋转排序数组
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        """
        logN的题大部分都采用二分法的方式做
        1. 先找出旋转数组的最小值，然后再判断是在左边查找还是右边查找，这里采用二分法查找
        """
        if not nums:
            return -1
        n = len(nums)
        left = 0
        right = n - 1
        while left < right:
            mid = left + (right-left)//2
            if nums[mid] > nums[right]:
                left = mid+1
            else:
                right = mid
        min_index = left
        left = 0
        right = n - 1
        while left <= right:
            mid = (left+right)//2
            realmid = (mid + min_index)%n
            if nums[realmid] == target:
                return realmid
            elif nums[realmid] > target:
                right = mid-1
            else:
                left = mid+1
        return -1

34. 在排序数组中查找元素的第一个和最后一个位置
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        res = []
        if not nums:
            return [-1,-1]
        # 查找最左边的target
        low = 0
        high = len(nums)-1
        while low <= high:
            mid = (low+high)//2
            if nums[mid] >= target:
                high = mid-1
            else:
                low = mid+1
        if 0 <= low and low <= len(nums)-1 and nums[low] == target:
            res.append(low)
        else:
            res.append(-1)
        # 查找最右边的target
        low = 0
        high = len(nums)-1
        while low <= high:
            mid = (low+high)//2
            if nums[mid] <= target:
                low = mid +1
            else:
                high = mid -1
        if 0 <= high and high <= len(nums)-1 and nums[high] == target:
            res.append(high)
        else:
            res.append(-1)
        return res

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        # 该题为求排列模式的回溯算法，通常采用递归实现
        candidates.sort()
        n = len(candidates)
        res = []
        def backtrack(i, tmp_sum, tmp):
            if tmp_sum > target or i == n:
                return 
            if tmp_sum == target:
                res.append(tmp)
                return
            for j in range(i, n):
                if tmp_sum +candidates[j] > target:
                    break
                backtrack(j, tmp_sum+candidates[j], tmp+[candidates[j]])
        backtrack(0,0,[])
        return res

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
class Solution:
    def trap(self, height: List[int]) -> int:
        """
        #对于每一块，找到该块左边和右边最大的块，用次大的高度减去当前高度即为存储水的高度
        #*： 提前通过遍历找到每一个块左边最大的块高度和右边对大块高度
        if not height:
            return 0
        ans = 0
        n = len(height)
        left_max = [0 for _ in range(n)]
        right_max = [0 for _ in range(n)]
        left_max[0] = height[0]
        right_max[-1] = height[-1]
        for i in range(1, n):
            left_max[i] = max(height[i], left_max[i-1])
        for i in range(n-2,-1, -1):
            right_max[i] = max(height[i], right_max[i+1])
        for i in range(1, n-1):
            ans += min(left_max[i], right_max[i]) - height[i]
        return ans
        """
        # 采用栈的做法
        if not height:
            return 0
        n = len(height)
        stack = []
        res = 0
        for i in range(n):
            while stack and height[stack[-1]] < height[i]:
                tmp = stack.pop()
                if not stack:
                    break
                res += (min(height[i], height[stack[-1]]) - height[tmp]) * (i - stack[-1]-1)
            stack.append(i)
        return res

给定一个没有重复数字的序列，返回其所有可能的全排列。
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        # 直接用回溯的方法
        if not nums:
            return []
        res = []
        n = len(nums)
        def backtrack(nums, tmp):
            if len(tmp) == n:
                res.append(tmp)
                return
            for i in range(len(nums)):
                backtrack(nums[:i]+nums[i+1:], tmp+[nums[i]])
        backtrack(nums, [])
        return res
    """
    # 使用库函数
    from itertools import permutations
    return list(itertools.permutations(nums))
    """

给定一个 n × n 的二维矩阵表示一个图像。将图像顺时针旋转 90 度。
class Solution:
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        # 先转置，再反向
        l = len(matrix)
        for i in range(l):
            for j in range(i+1, l):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        for i in range(l):
            matrix[i] = matrix[i][::-1]

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
from collections import defaultdict
class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        # 将每个字符串排序后存入dict中
        res = defaultdict(list)
        for s in strs:
            res[tuple(sorted(s))].append(s)
        return res.values()

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
class Solution:
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        max = -float(‘Inf‘)
        sum = 0
        for i in nums:
            sum = sum+i
            if sum > max:
                max = sum
            if sum <0:
                sum = 0
        return max

给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        ‘‘‘
        超时~！
        # 排列组合的问题，溯源法
        if not nums:
            return False
        n = len(nums)
        already_point = []
        def backtrace(i):
            if i == n-1:
                return True
            if i > n-1 or nums[i] == 0:
                return False
            flag = False
            for j in range(1, nums[i]+1):
                if i+j > n-1:
                    break
                if i+j in already_point:
                    continue
                already_point.append(i+j)
                flag = flag or backtrace(i+j)
            return flag
        return backtrace(0)
        ‘‘‘
        # 贪心法解题
        lastPos = len(nums)-1
        i = len(nums)-1
        while i >= 0:
            if i+nums[i] >= lastPos:
                lastPos = i
            i -= 1
        return lastPos == 0

给出一个区间的集合，请合并所有重叠的区间。
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals = sorted(intervals)
        res = []
        n = len(intervals)
        i = 0
        while i < n:
            left = intervals[i][0]
            right = intervals[i][1]
            while i < n-1 and intervals[i+1][0] <= right:
                i += 1
                right = max(right, intervals[i][1])
            res.append([left, right])
            i+= 1
        return res

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。问总共有多少条不同的路径？
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        ‘‘‘
        # 经典的回溯法
        self.res = 0
        dp = [[-1 for _ in range(n+1)] for _ in range(m+1)]
        def backtrack(i, j):
            if i == m and j == n:
                return 1
            if dp[i][j] != -1:
                return dp[i][j]
            ans = 0
            if i+1 <= m:
                ans += backtrack(i+1, j)
            if j+1 <= n:
                ans += backtrack(i, j+1)
            dp[i][j] = ans
            return ans
        return backtrack(1,1)
        ‘‘‘
        # 使用动态规划
        dp = [[-1 for _ in range(n)] for _ in range(m)]
        # 初始化数据
        for i in range(m):
            dp[i][0] = 1
        for j in range(n):
            dp[0][j] = 1
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j]+dp[i][j-1]
        for i in dp:
            print(i)
        return dp[-1][-1]

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        ‘‘‘
        # 如果将路径和的值卸载grid中，则可以不申请grid数组
        if not grid:
            return 0
        # 使用动态规划
        height = len(grid)
        width = len(grid[0])
        dp = [[-1 for _ in range(width)] for _ in range(height)]
        # 初始化第一行
        dp[0][0] = grid[0][0]
        for i in range(1, width):
            dp[0][i] = dp[0][i-1]+grid[0][i]
        # 初始化第一列
        for i in range(1, height):
            dp[i][0] = dp[i-1][0]+grid[i][0]
        for i in range(1, height):
            for j in range(1, width):
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
        return dp[-1][-1]
        ‘‘‘
        # 由于只能是往右或者往下移动，因此可以只用一维数组来存储状态
        if not grid:
            return 0
        height = len(grid)
        width = len(grid[0])
        dp = [-1 for _ in range(width)]
        for i in range(height - 1, -1, -1):
            for j in range(width - 1, -1, -1):
                if j == width - 1 and i != height - 1:
                    dp[j] = dp[j] + grid[i][j]
                elif i == height - 1 and j != width - 1:
                    dp[j] = dp[j+1] + grid[i][j]
                elif i != height - 1 and j != width - 1:
                    dp[j] = min(dp[j + 1], dp[j]) + grid[i][j]
                else:
                    dp[j] = grid[i][j]
        print(dp[0])
        return dp[0]

70. 爬楼梯
class Solution:
    def climbStairs(self, n: int) -> int:
        # f(1) = 1 f(2)=2 f(3) = f(1)+f(2) ----> f(n) = f(n-1)+f(n-2)
        if n <= 0:
            return 0
        if n == 1:
            return 1
        if n == 2:
            return 2
        f = [0 for _ in range(n)]
        f[0] = 1
        f[1] = 2
        for i in range(2, n):
            f[i] = f[i-2]+f[i-1]
        return f[-1]

72. 编辑距离
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        # 动态规划，ed二维数组，ed[i][j]表示word1长度为i的子串到word2长度为j的子串之间的编辑距离
        ‘‘‘
        1. 建立一个2为数组D，表示将s1的i子串变为s2的j子串所需要的编辑距离
            a. i = 0时，D[i][j] = j
            b. j = 0 时， D[i][j] = i
        2. 增：如果计算出了D(i, j-1)的值，那么D(i, j) 等于D(i,j-1)+1
        3. 删：如果计算出了D(i-1, j)的值，那么D（i，j）等于D（i-1, j）+1
        4. 改：如果计算出了D（i-1, j-1）的值，如果s1[i]==s2[j],则D（i,j） = D(i-1, j-1),否则，D（i,j） = D(i-1, j-1)+1：将s2[j]改为s1[i]
        ‘‘‘
        if not word1:
            return len(word2)
        if not word2:
            return len(word1)
        len1 = len(word1)
        len2 = len(word2)
        # 这里长度必须加1，因为可以从“”开始变，这里的长度为0，一共n+1个长度
        et = [[-1 for _ in range(len2+1)] for _ in range(len1+1)]
        # 初始化部分值
        for i in range(len1+1):
            et[i][0] = i
        for j in range(len2+1):
            et[0][j] = j
        for i in range(1, len1+1):
            for j in range(1, len2+1):
                # 这里之所以要减1，是由于i和j为1的时候对应第一个字符，即0，所以要减1
                if word1[i-1] == word2[j-1]:
                    et[i][j] = min(et[i-1][j]+1, et[i][j-1]+1, et[i-1][j-1])
                else:
                    et[i][j] = min(et[i-1][j]+1, et[i][j-1]+1, et[i-1][j-1]+1)
        return et[-1][-1]

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # 设置三个指针pre, cur, end, pre始终指向 0，end指向2，cur指向当前值
        # 初始化：pre、cur为0， end为n-1
        # 1. 当cur指向0，则cur与pre的值交换，两者都右移； 2. 当end指向2时， 则cur与end的值交换，end向左移；3. 知道cur==end返回。
        length = len(nums)
        pre = cur = 0
        end = length - 1
        while cur <= end:
            if nums[cur] == 0:
                nums[pre], nums[cur] = nums[cur], nums[pre]
                pre += 1
                cur += 1
            elif nums[cur] == 2:
                nums[end], nums[cur] = nums[cur], nums[end]
                end -= 1
            else:
                cur += 1

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。
from collections import Counter
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        # 使用滑窗法
        dict_t = Counter(t)
        required = len(dict_t)
        l = r = 0
        formed = 0
        window_counts = {}
        ans = (float("Inf"), None, None)
        while r < len(s):
            char = s[r]
            window_counts[char] = window_counts.get(char, 0)+1
            # 这里子串要包含T中所有的字母，且重复的字符也算进去
            if char in dict_t and window_counts[char] == dict_t[char]:
                formed += 1
            # 窗口满足条件，开始收缩窗口
            while l <= r and formed == required:
                char = s[l]
                if r-l+1 < ans[0]:
                    ans = (r-l+1, l, r)
                window_counts[char] -= 1
                if char in dict_t and window_counts[char] < dict_t[char]:
                    formed -= 1
                l += 1
            r += 1
        return "" if ans[0] == float("Inf") else s[ans[1]:ans[2]+1]

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
from itertools import combinations
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ‘‘‘
        # 全排列问题
        res = []
        def permute(nums, tmp):
            res.append(tmp)
            if not nums:
                return
            for j in range(len(nums)):
                permute(nums[j+1:], tmp+[nums[j]])
        permute(nums, [])
        return res
        ‘‘‘
        # 使用库函数
        res = []
        for i in range(len(nums)+1):
            for tmp in itertools.combinations(nums, i):
                res.append(tmp)
        return res

给定一个二维网格和一个单词，找出该单词是否存在于网格中。
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        # dfs+回溯算法
        row = len(board)
        col = len(board[0])
        def backtrace(i, j, k, visited):
            if k == len(word):
                return True
            # 四个方向均可查看
            for x, y in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
                tmp_i = i+x
                tmp_j = j+y
                if 0 <= tmp_i < row and 0 <= tmp_j < col and visited[tmp_i][tmp_j] != 1 and board[tmp_i][tmp_j] == word[k]:
                    visited[tmp_i][tmp_j] = 1
                    if backtrace(tmp_i, tmp_j, k+1, visited):
                        return True
                    visited[tmp_i][tmp_j] = 0
            return False
        visited = [[0 for _ in range(col)] for _ in range(row)]
        for i in range(row):
            for j in range(col):
                if board[i][j] == word[0]:
                    visited[i][j] = 1
                    if backtrace(i, j, 1, visited):
                        return True
                    visited[i][j] = 0
        return False

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        ‘‘‘
        # 该方法超时！
        # 使用分治法，先找出最低的柱子，则：1. 确定了柱子的高度，矩形宽为整个的宽度；2. 在最矮柱子的左边；3. 在右边
        return self.calculateArea(heights, 0, len(heights)-1)
    def calculateArea(self, heights, start, end):
        if start > end:
            return 0
        minindex = start
        for i in range(start, end+1):
            if heights[i] < heights[minindex]:
                minindex = i
        return max([heights[minindex]*(end-start+1), self.calculateArea(heights, start, minindex-1), self.calculateArea(heights, minindex+1, end)])
    ‘‘‘
        # 使用栈的方法
        stack = []
        heights = [0] + heights + [0]
        res = 0
        for i in range(len(heights)):
            while stack and heights[stack[-1]] > heights[i]:
                tmp = stack.pop()
                res = max(res, heights[tmp]*(i - stack[-1]-1))
            stack.append(i)
        return res

给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
class Solution(object):
    def maximalRectangle(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        maxarea = 0
        dp = [[0] * len(matrix[0]) for _ in range(len(matrix))]
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == ‘0‘:
                    continue
                # 计算当前点作为矩形右下角点的宽度
                width = dp[i][j] = dp[i][j-1] + 1 if j else 1
                for k in range(i, -1, -1):
                    # 求出矩形的宽度
                    width = min(width, dp[k][j])
                    maxarea = max(maxarea, width*(i-k+1))
        return maxarea

给定一个二叉树，返回它的中序 遍历。
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        ‘‘‘
        # 先使用递归的方法完成
        res = []
        def inorder_traversal(root):
            if not root:
                return 
            inorder_traversal(root.left)
            res.append(root.val)
            inorder_traversal(root.right)
        inorder_traversal(root)
        return res
        ‘‘‘
        # 使用栈的方法
        res = []
        stack = []
        cur = root
        while cur or stack:
            while cur:
                stack.append(cur)
                cur = cur.left
            cur = stack.pop()
            res.append(cur.val)
            cur = cur.right
        return res

给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
class Solution:
    def numTrees(self, n: int) -> int:
        # 二叉搜索树又称为二叉排序树，其左子树上的所有点均小于它根节点的值，右子树上的所有点据大于根节点的值
        # 假设n个节点存在二叉排序树为G(n),令f(i)为根节点为i的二叉排序树的个数，则G(n) = f(1)+f(2)+...+f(n)
        # f(i) = G(i-1)*G(n-i)
        # G(n) = G(0)*G(n-1) + G(1)*G(n-2)+ ... + G(n-1)*G(0): **又名卡特兰数**
        dp = [0 for _ in range(n+1)]
        dp[0] = 1
        dp[1] = 1
        for i in range(2, n+1):
            for j in range(1, i+1):
                dp[i] += dp[j-1]*dp[i-j]
        return dp[n]

给定一个二叉树，判断其是否是一个有效的二叉搜索树。
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        # 二叉搜索树的中序遍历是否是一个升序数组
        self.pre = -float("inf")
        def judge_bst(root):
            if not root:
                return True 
            l = judge_bst(root.left)
            if root.val <= self.pre:
                return False
            self.pre = root.val
            r = judge_bst(root.right)
            return l and r
        return judge_bst(root)

给定一个二叉树，检查它是否是镜像对称的。
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        # 1. 分别按照左中右和右中左的顺序，看遍历是否相等
        # 2. 将其根节点分为两份，形成两个树，判断两个树是否镜像对称
        def isMirror(root1, root2):
            if not root1 and not root2:
                return True
            if not root1 or not root2:
                return False
            return root1.val == root2.val and isMirror(root1.left, root2.right) and isMirror(root1.right, root2.left)
        return isMirror(root,root)