python算法和数据结构刷题[3]：哈希表、滑动窗口、双指针、回溯算法、贪心算法

回溯算法

「所有可能的结果」，而不是「结果的个数」，一般情况下，我们就知道需要暴力搜索所有的可行解了，可以用「回溯法」。

回溯算法关键在于:不合适就退回上一步。在回溯算法中，递归用于深入到所有可能的分支，而迭代（通常在递归函数内部的循环中体现）用于探索当前层级的所有可能选项。

组合问题

39. 组合总和 - 力扣（LeetCode）

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

1.路径2.求和3.判断

 回溯算法：

在循环中回溯前有改变操作，调用回溯函数判断是否继续回溯，如果结束当前循环的回溯，在回溯后进行操作。

from typing import List

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        
        def backtrack(candidates, path, target, start):
            if sum(path) == target:
                res.append(path[:])
                return
            if sum(path) > target:
                return
            
            for i in range(start, len(candidates)):
                path.append(candidates[i])
                backtrack(candidates, path, target, i)
                path.pop()
        
        backtrack(candidates, [], target, 0)
        return res

# 实例化Solution类
solution = Solution()

# 定义候选数字列表和目标值
candidates = [2, 3, 6, 7]
target = 7

# 调用combinationSum方法并打印结果
combinations = solution.combinationSum(candidates, target)
print(combinations)

17. 电话号码的字母组合 - 力扣（LeetCode）

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        #数字对应的英文字母列表
        word_list = ["0", "0", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
        #如果是空字符串直接返回空列表
        if digits == "":
            return []
        #保存结果列表
        result = []
        #输入的digits的长度，作为回溯函数返回的判断条件
        lenth = len(digits)
        #回溯函数（path当前路径，默认为""）
        def back_track(digits, index, path):
            #如果目前path的长度和digits的长度相等，说明已经遍历完一趟，返回结果列表
            if len(path) == lenth:
                #加入result列表
                result.append(path)
                #返回
                return
            #遍历当前索引的数字对应的英文列表
            for word in word_list[int(digits[index])]:
                #路径加上当前字母
                path = path + word
                #递归下一个数字对应的英文列表
                back_track(digits, index + 1, path)
                #撤销当前字母
                path = path[:-1]
        back_track(digits, 0, "")
        return result

分割问题

131. 分割回文串 - 力扣（LeetCode）

class Solution(object):
    def partition(self, s):
        # 判断字符串是否为回文
        self.is_palindrome = lambda s: s == s[::-1]
        # 初始化结果列表，用于存储所有可能的分割方式
        result = []
        # 从空路径开始回溯
        self.backtrack(s, result, [])
        return result
        
    def backtrack(self, s, result, path):
        # 如果s为空，说明已经处理完所有字符，将当前路径加入结果列表
        if not s:
            result.append(path)
            return
        
        # 遍历字符串s，尝试每一种可能的分割方式
        for i in range(1, len(s) + 1):
            # 截取当前子串
            substring = s[:i]
            # 如果当前子串是回文，则继续递归处理剩余的字符串
            if self.is_palindrome(substring):
                # 将当前子串加入路径，并递归处理剩余字符串
                self.backtrack(s[i:], result, path + [substring])

# 实例化Solution类
solution = Solution()

# 定义字符串
s = "aab"

# 调用partition方法并打印结果
partitions = solution.partition(s)
print(partitions)

子集问题

78. 子集 - 力扣（LeetCode）

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集

start参数和i+1，指示了在递归过程中应该从数组的哪个位置开始考虑元素，以避免重复的组合。

每多一个数增加一次结果

from typing import List

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        """
        生成给定数字列表的所有可能子集。
        
        :param nums: 用于生成子集的整数列表。
        :return: 包含所有可能子集的列表。
        """
        if not nums:
            return []
        
        res = []
        n = len(nums)
        
        # 定义递归辅助函数，用于回溯生成子集
        def backtrack(start: int, current_subset: List[int]):
            """
            回溯辅助函数。
            
            :param start: 当前子集开始遍历的索引。
            :param current_subset: 当前正在构建的子集。
            """
            # 将当前子集的副本添加到结果列表中
            res.append(current_subset[:])
            
            # 遍历剩余元素，尝试将其加入到子集中
            for i in range(start, n):
                # 将当前元素加入到子集，并递归继续构建子集
                backtrack(i + 1, current_subset + [nums[i]])
        
        # 从空子集开始回溯过程
        backtrack(0, [])
        return res

# 示例用法：
solution = Solution()
print(solution.subsets([1, 2, 3]))

排列问题

46. 全排列 - 力扣（LeetCode）

from typing import List

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def backtrack(start, end):
            # 所有数都填完了，将当前排列加入结果集
            if start == end:
                res.append(nums[:])
            for i in range(start, end):
                # 交换前缀，将第 i 个元素固定在第 start 位
                nums[start], nums[i] = nums[i], nums[start]
                # 递归填下一个数
                backtrack(start + 1, end)
                # 撤销操作
                nums[start], nums[i] = nums[i], nums[start]
        
        res = []
        backtrack(0, len(nums))
        return res

# 实例化并调用
solution = Solution()
nums = [1, 2, 3]
print(solution.permute(nums))

每循环完列表一次添加一次结果

棋盘问题

51. N 皇后 - 力扣（LeetCode）

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        # 从上往下放棋子
        # 按照row从小到大放置皇后
        board = [['.'] * n for _ in range(n)]
        res = []

        # 表示board中小于row的那些行（row上面的那些行）已经放置皇后了
        # 这一步开始往第row行放皇后
        def backtrack(row):
            n = len(board)
            # 如果到最后一行了，则将结果添加到res里
            if row == n:
                tmp = [''.join(i) for i in board]
                res.append(tmp)
                return

            for col in range(n):
                if not self.isValid(board, row, col):
                    continue
                board[row][col] = 'Q'
                backtrack(row + 1)
                board[row][col] = '.'
        backtrack(0)

        return res 

            

    # 查看是否可以在board[row][col]的位置放置皇后
    def isValid(self, board, row, col):
        n = len(board)
        
        # 查看上方是否有Q
        for i in range(row):
            if board[i][col] == 'Q':
                return False

        # 查看右上方是否有Q
        for i, j in zip(range(row - 1, -1, -1), range(col + 1, n, 1)):
            if board[i][j] == 'Q':
                return False
        
        # 查看左上方是否有Q
        for i, j in zip(range(row - 1, -1, -1), range(col - 1, -1, -1)):
            if board[i][j] == 'Q':
                return False
        
        return True 

作者：山鬼TJU

79. 单词搜索 - 力扣（LeetCode）

class Solution(object):
    
    # 定义上下左右四个行走方向
    directs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        m = len(board)
        if m == 0:
            return False
        n = len(board[0])
        mark = [[0 for _ in range(n)] for _ in range(m)]
                
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == word[0]:
                    # 将该元素标记为已使用
                    mark[i][j] = 1
                    if self.backtrack(i, j, mark, board, word[1:]) == True:
                        return True
                    else:
                        # 回溯
                        mark[i][j] = 0
        return False
        
        
    def backtrack(self, i, j, mark, board, word):
        if len(word) == 0:
            return True
        
        for direct in self.directs:
            cur_i = i + direct[0]
            cur_j = j + direct[1]
            
            if cur_i >= 0 and cur_i < len(board) and cur_j >= 0 and cur_j < len(board[0]) and board[cur_i][cur_j] == word[0]:
                # 如果是已经使用过的元素，忽略
                if mark[cur_i][cur_j] == 1:
                    continue
                # 将该元素标记为已使用
                mark[cur_i][cur_j] = 1
                if self.backtrack(cur_i, cur_j, mark, board, word[1:]) == True:
                    return True
                else:
                    # 回溯
                    mark[cur_i][cur_j] = 0
        return False

22. 括号生成 - 力扣（LeetCode）

可以插入 ） 的前提是 ( 的数量大于 ）

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        res = []
        self.dfs(res, n, n, '')
        return res
        
    def dfs(self, res, left, right, path):
        if left == 0 and right == 0:
            res.append(path)
            return
        if left > 0:
            self.dfs(res, left - 1, right, path + '(')
        if left < right:
            self.dfs(res, left, right - 1, path + ')')

贪心算法

例如，有一堆钞票，你可以拿走十张，如果想达到最大的金额，你要怎么拿？

指定每次拿最大的，最终结果就是拿走最大数额的钱。

每次拿最大的就是局部最优，最后拿走最大数额的钱就是推出全局最优。

• 将问题分解为若干个子问题
• 找出适合的贪心策略
• 求解每一个子问题的最优解
• 将局部最优解堆叠成全局最优解

121. 买卖股票的最佳时机 - 力扣（LeetCode）

因为股票就买卖一次，那么贪心的想法很自然就是取最左最小值，取最右最大值，那么得到的差值就是最大利润。

def max_profit(prices):
    if not prices:
        return 0

    max_profit = 0
    min_price = prices[0]

    for price in prices:
        # 更新到目前为止遇到的最小价格
        min_price = min(min_price, price)
        # 计算在当前价格卖出时的利润，并更新最大利润
        max_profit = max(max_profit, price - min_price)

    return max_profit

# 示例
prices = [7, 1, 5, 3, 6, 4]
print(max_profit(prices))  # 输出应为 5

 55. 跳跃游戏 - 力扣（LeetCode）

def can_jump(nums):
    # 最远能到达的位置
    max_reach = 0
    # 遍历数组
    for i, num in enumerate(nums):
        # 如果当前位置超过最远能到达的位置，说明无法到达当前位置
        if i > max_reach:
            return False
        # 更新最远能到达的位置
        max_reach = max(max_reach, i + num)
        # 如果最远能到达的位置已经覆盖了最后一个下标，则可以到达
        if max_reach >= len(nums) - 1:
            return True
    return True

# 示例
nums = [2, 3, 1, 1, 4]
print(can_jump(nums))  # 输出应为 True

 45. 跳跃游戏 II - 力扣（LeetCode）

def min_jumps(nums):
    n = len(nums)
    # 如果数组只有一个元素，不需要跳跃
    if n <= 1:
        return 0
    
    # 当前跳跃能到达的最远位置
    current_end = 0
    # 下一步跳跃能到达的最远位置
    farthest = 0
    # 跳跃次数
    jumps = 0
    
    # 遍历数组，但不包括最后一个元素，因为目标是在最后一个元素处停止
    for i in range(n - 1):
        # 更新最远能到达的位置
        farthest = max(farthest, i + nums[i])
        # 如果到达了当前跳跃的边界
        if i == current_end:
            # 增加跳跃次数
            jumps += 1
            # 更新当前跳跃的边界
            current_end = farthest
            # 如果当前跳跃的边界已经覆盖了最后一个元素，则可以停止
            if current_end >= n - 1:
                break
    
    return jumps

# 示例
nums = [2, 3, 1, 1, 4]
print(min_jumps(nums))  # 输出应为 2

 763. 划分字母区间 - 力扣（LeetCode）

def partitionLabels(s):
    # 记录每个字符最后出现的位置
    last = {c: i for i, c in enumerate(s)}
    ans = []
    start = end = 0
    
    # 遍历字符串
    for i, c in enumerate(s):
        # 更新当前片段的结束位置
        end = max(end, last[c])
        # 如果当前位置是当前片段的结束位置
        if i == end:
            # 记录当前片段的长度
            ans.append(end - start + 1)
            # 更新下一个片段的开始位置
            start = end + 1

    return ans

# 示例
s = "ababcbacadefegdehijhklij"
print(partitionLabels(s))  # 输出

哈希表

1. 两数之和 - 力扣（LeetCode）

创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable = dict()
        for i, num in enumerate(nums):
            if target - num in hashtable:
                return [hashtable[target - num], i]
            hashtable[nums[i]] = i
        return []

 49. 字母异位词分组 - 力扣（LeetCode）

class Solution:
    def groupAnagrams(self, strings: List[str]) -> List[List[str]]:
        mp = collections.defaultdict(list) # define a map from str to list of str
        for string in strings:
            key = "".join(sorted(string))
            mp[key].append(string)
        
        return list(mp.values())

128. 最长连续序列 - 力扣（LeetCode）

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        ans = 0
        st = set(nums)  # 把 nums 转成哈希集合
        for x in st:  # 遍历哈希集合
            if x - 1 in st:
                continue
            # x 是序列的起点
            y = x + 1
            while y in st:  # 不断查找下一个数是否在哈希集合中
                y += 1
            # 循环结束后，y-1 是最后一个在哈希集合中的数
            ans = max(ans, y - x)  # 从 x 到 y-1 一共 y-x 个数
        return ans

作者：灵茶山艾府

560. 和为 K 的子数组 - 力扣（LeetCode）

前后缀分解+哈希表

前缀和指一个数组的某下标之前的所有数组元素的和（包含其自身）

from collections import defaultdict

class Solution:
    def subarraySum(self, nums: list, k: int) -> int:
        # 初始化计数器，用于记录和为k的子数组的数量
        count = 0
        n = len(nums)
        
        # 使用defaultdict来存储前缀和出现的次数，初始时前缀和为0出现1次
        preSums = defaultdict(int)
        preSums[0] = 1

        # 初始化前缀和为0
        presum = 0
        
        # 遍历数组中的每个元素
        for i in range(n):
            # 更新当前的前缀和
            presum += nums[i]
            
            # 如果存在某个前缀和等于当前前缀和减去k，则说明存在一个子数组的和为k
            # defaultdict的特性使得当key不存在时返回0，所以这里不需要判断key是否存在
            count += preSums[presum - k]

            # 将当前前缀和出现的次数加1
            preSums[presum] += 1
        
        # 返回和为k的子数组的数量
        return count

双指针

283. 移动零 - 力扣（LeetCode）

快慢指针，当碰到0时i会比i0走的快

from typing import List

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        # 初始化一个指针i0，用于指向下一个非零元素应该放置的位置
        i0 = 0
        
        # 遍历数组中的每个元素
        for i in range(len(nums)):
            # 如果当前元素不是0，则将其与i0指向的位置的元素交换
            if nums[i]:
                # 交换元素，将非零元素移动到i0指向的位置
                nums[i], nums[i0] = nums[i0], nums[i]
                # 移动i0指针到下一个位置
                i0 += 1
        
        # 注意：这个方法直接修改了输入的数组，不需要返回值

11. 盛最多水的容器 - 力扣（LeetCode）

对撞指针两个指针列表一边一个向中间靠近，同时根据两者的高度判断两个指针是否前进

class Solution:
    def maxArea(self, height: List[int]) -> int:
        ans = left = 0
        right = len(height) - 1
        while left < right:
            area = (right - left) * min(height[left], height[right])
            ans = max(ans, area)
            if height[left] < height[right]:
                # height[left] 与右边的任意线段都无法组成一个比 ans 更大的面积
                left += 1
            else:
                # height[right] 与左边的任意线段都无法组成一个比 ans 更大的面积
                right -= 1
        return ans

42. 接雨水 - 力扣（LeetCode）

对撞指针

from typing import List

class Solution:
    def trap(self, height: List[int]) -> int:
        # 初始化答案变量、左指针、前缀最大高度、后缀最大高度
        ans = left = pre_max = suf_max = 0
        # 初始化右指针指向数组的最后一个元素
        right = len(height) - 1
        
        # 当左指针小于右指针时，继续循环
        while left < right:
            # 更新当前左指针指向的柱子的前缀最大高度
            pre_max = max(pre_max, height[left])
            # 更新当前右指针指向的柱子的后缀最大高度
            suf_max = max(suf_max, height[right])
            
            # 如果左指针的前缀最大高度小于右指针的后缀最大高度
            if pre_max < suf_max:
                # 计算当前左指针位置可以捕获的水量，并累加到答案中
                ans += pre_max - height[left]
                # 移动左指针到下一个位置
                left += 1
            else:
                # 计算当前右指针位置可以捕获的水量，并累加到答案中
                ans += suf_max - height[right]
                # 移动右指针到下一个位置
                right -= 1
        
        # 返回计算出的总水量
        return ans

 15. 三数之和 - 力扣（LeetCode）

def threeSum(nums):
    # 首先对数组进行排序
    nums.sort()
    result = []
    
    # 遍历数组，直到倒数第三个元素
    for i in range(len(nums) - 2):
        # 如果当前数字大于0，则后面的数字都大于0，不可能和为0，直接返回结果
        if nums[i] > 0:
            return result
        # 跳过可能重复的数字
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        
        # 初始化双指针
        left, right = i + 1, len(nums) - 1
        
        # 使用双指针遍历
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            
            # 如果三数之和小于0，左指针右移
            if total < 0:
                left += 1
            # 如果三数之和大于0，右指针左移
            elif total > 0:
                right -= 1
            # 如果三数之和等于0，添加到结果中，并移动左右指针
            else:
                result.append([nums[i], nums[left], nums[right]])
                # 跳过可能重复的数字
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1
                
    return result

# 示例
nums = [-1, 0, 1, 2, -1, -4]
print(threeSum(nums))  # 输出应为[[-1, -1, 2], [-1, 0, 1]]

滑动窗口

在滑动窗口中，通常会使用两个指针，这两个指针分别被称为“快指针”和“慢指针”（也有其他叫法，如“左指针”和“右指针”），它们在数组或链表上移动以维护一个窗口。

• 快指针（右指针）：通常用于扩展窗口，即向右移动，探索新的元素。
• 慢指针（左指针）：通常用于收缩窗口，即向右移动，移除窗口中的元素。

3. 无重复字符的最长子串 - 力扣（LeetCode）

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串的长度。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left,right = 0,0
        res = 0
        if len(s) == 0:
            return 0
        if s.count(s[0]) == len(s):
            return 1
        if len(set(s)) == len(s):
            return len(s)
        while right < len(s):
            if s[right] not in s[left:right]:
                right +=1
                res = max(res,len(s[left:right]))
            else:
                while s[right] in s[left:right]:
                    left +=1
        return res

 438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

class Solution:
    def findAnagrams(self, s: str, p: str) -> list:
        n, m, res = len(s), len(p), []  # 初始化字符串s和p的长度，以及结果列表
        if n < m: return res  # 如果s的长度小于p，则不可能包含异位词，直接返回空列表

        # 初始化两个长度为26的数组，用于存储字符计数
        p_cnt = [0] * 26
        s_cnt = [0] * 26

        # 统计字符串p中每个字符的出现次数
        for i in range(m):
            p_cnt[ord(p[i]) - ord('a')] += 1
        
        left = 0  # 初始化滑动窗口的左边界
        for right in range(n):  # 遍历字符串s
            cur_right = ord(s[right]) - ord('a')  # 计算当前字符在数组中的索引
            s_cnt[cur_right] += 1  # 增加当前字符的计数

            # 如果当前字符在s中的出现次数超过了在p中的出现次数，移动左边界
            while s_cnt[cur_right] > p_cnt[cur_right]:
                cur_left = ord(s[left]) - ord('a')  # 计算左边界字符在数组中的索引
                s_cnt[cur_left] -= 1  # 减少左边界字符的计数
                left += 1  # 移动左边界

            # 如果滑动窗口的大小等于p的长度，则找到了一个异位词
            if right - left + 1 == m:
                res.append(left)  # 将左边界索引添加到结果列表中

        return res  # 返回所有异位词的起始索引列表

239. 滑动窗口最大值 - 力扣（LeetCode）

单调递减的双端队列来保存窗口中的元素索引，确保队列的首部始终是当前窗口的最大值的索引。

双端队列：deque允许在队列的两端进行插入和删除操作。

from collections import deque

def maxSlidingWindow(nums, k):
    if not nums or k == 0:
        return []
    
    deque = deque()  # 存储元素索引的单调队列
    result = []  # 存储结果
    
    for i in range(len(nums)):
        # 移除所有小于当前元素的索引
        while deque and nums[deque[-1]] <= nums[i]:
            deque.pop()
        
        # 将当前元素的索引加入队列
        deque.append(i)
        
        # 移除不在窗口内的索引
        if deque[0] < i - k + 1:
            deque.popleft()
        
        # 当窗口大小达到 k 时，记录当前窗口的最大值
        if i >= k - 1:
            result.append(nums[deque[0]])
    
    return result

76. 最小覆盖子串 - 力扣（LeetCode）

1. 初始化两个指针，left 和 right，它们分别表示滑动窗口的左右边界。
2. 使用两个哈希表（或字典）来记录当前窗口中的字符频率和目标字符串 t 中字符的频率。
3. 扩展 right 指针来增加窗口的大小，直到窗口包含了 t 中所有的字符。
4. 一旦窗口包含了 t 中所有的字符，尝试通过移动 left 指针来缩小窗口的大小，同时保持窗口包含 t 中所有的字符。
5. 在每次移动 left 指针时，如果窗口仍然包含 t 中所有的字符，则更新最小子串的长度和起始位置。
6. 重复步骤 3 和 4，直到 right 指针到达字符串 s 的末尾。

def min_window(s, t):
    if not t or not s:
        return ""

    # 初始化需要的字符及其频率
    need = {}
    for char in t:
        need[char] = need.get(char, 0) + 1#从字典中获取 char 对应的值。如果 char 不在字典中，则返回默认值 0

    # 初始化窗口中的字符及其频率
    window = {}
    valid = 0  # 用于记录窗口中满足 need 条件的字符个数

    left, right = 0, 0
    start, length = 0, float('inf')  # 最小子串的起始位置和长度

    while right < len(s):
        # 即将移入窗口的字符
        c = s[right]
        # 右移窗口
        right += 1

        # 更新窗口中的字符频率
        if c in need:
            window[c] = window.get(c, 0) + 1
            if window[c] == need[c]:
                valid += 1

        # 判断左侧窗口是否要收缩
        while valid == len(need):
            # 更新最小子串
            if right - left < length:
                start = left
                length = right - left

            # 即将移出窗口的字符
            d = s[left]
            # 左移窗口
            left += 1

            # 更新窗口中的字符频率
            if d in need:
                if window[d] == need[d]:
                    valid -= 1
                window[d] -= 1

    # 返回最小子串
    return "" if length == float('inf') else s[start:start + length]

# 示例
s = "ADOBECODEBANC"
t = "ABC"
print(min_window(s, t))  # 输出 "BANC"

广度优先搜索算法基本用的就是队列，深度优先搜索算法（DFS）用的基本都是递归