搭建邮箱注册网站网页设计与网站建设的概述

当前位置： 首页 > news >正文

搭建邮箱注册网站,网页设计与网站建设的概述,濮阳网站建设网站,网站建设的经过的阶段回溯算法 「所有可能的结果」#xff0c;而不是「结果的个数」#xff0c;一般情况下#xff0c;我们就知道需要暴力搜索所有的可行解了#xff0c;可以用「回溯法」。 回溯算法关键在于:不合适就退回上一步。在回溯算法中#xff0c;递归用于深入到所有可能的分支…回溯算法 「所有可能的结果」而不是「结果的个数」一般情况下我们就知道需要暴力搜索所有的可行解了可以用「回溯法」。 回溯算法关键在于:不合适就退回上一步。在回溯算法中递归用于深入到所有可能的分支而迭代通常在递归函数内部的循环中体现用于探索当前层级的所有可能选项。 组合问题

1. 组合总和 - 力扣LeetCode 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 并以列表形式返回。你可以按 任意顺序 返回这些组合。 1.路径2.求和3.判断 回溯算法 在循环中回溯前有改变操作调用回溯函数判断是否继续回溯如果结束当前循环的回溯在回溯后进行操作。 from typing import Listclass 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[:])returnif sum(path) target:returnfor 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)
2. 电话号码的字母组合 - 力扣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分割问题
3. 分割回文串 - 力扣LeetCode class Solution(object):def partition(self, s):# 判断字符串是否为回文self.is_palindrome lambda s: s s[::-1]# 初始化结果列表用于存储所有可能的分割方式result []# 从空路径开始回溯self.backtrack(s, result, [])return resultdef 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) 子集问题
4. 子集 - 力扣LeetCode 给你一个整数数组 nums 数组中的元素 互不相同 。返回该数组所有可能的子集 start参数和i1指示了在递归过程中应该从数组的哪个位置开始考虑元素以避免重复的组合。 每多一个数增加一次结果 from typing import Listclass 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])) 排列问题
5. 全排列 - 力扣LeetCode from typing import Listclass 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)) 每循环完列表一次添加一次结果 棋盘问题
6. 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)returnfor col in range(n):if not self.isValid(board, row, col):continueboard[row][col] Qbacktrack(row 1)board[row][col] .backtrack(0)return res # 查看是否可以在board[row][col]的位置放置皇后def isValid(self, board, row, col):n len(board)# 查看上方是否有Qfor i in range(row):if board[i][col] Q:return False# 查看右上方是否有Qfor i, j in zip(range(row - 1, -1, -1), range(col 1, n, 1)):if board[i][j] Q:return False# 查看左上方是否有Qfor i, j in zip(range(row - 1, -1, -1), range(col - 1, -1, -1)):if board[i][j] Q:return Falsereturn True 作者山鬼TJU
7. 单词搜索 - 力扣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: boolm len(board)if m 0:return Falsen 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] 1if self.backtrack(i, j, mark, board, word[1:]) True:return Trueelse:# 回溯mark[i][j] 0return Falsedef backtrack(self, i, j, mark, board, word):if len(word) 0:return Truefor 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] 1if self.backtrack(cur_i, cur_j, mark, board, word[1:]) True:return Trueelse:# 回溯mark[cur_i][cur_j] 0return False22. 括号生成 - 力扣LeetCode 可以插入  的前提是 ( 的数量大于  class Solution(object):def generateParenthesis(self, n)::type n: int:rtype: List[str]res []self.dfs(res, n, n, )return resdef dfs(self, res, left, right, path):if left 0 and right 0:res.append(path)returnif left 0:self.dfs(res, left - 1, right, path ()if left right:self.dfs(res, left, right - 1, path ))贪心算法 例如有一堆钞票你可以拿走十张如果想达到最大的金额你要怎么拿 指定每次拿最大的最终结果就是拿走最大数额的钱。 每次拿最大的就是局部最优最后拿走最大数额的钱就是推出全局最优。 将问题分解为若干个子问题找出适合的贪心策略求解每一个子问题的最优解将局部最优解堆叠成全局最优解
8. 买卖股票的最佳时机 - 力扣LeetCode 因为股票就买卖一次那么贪心的想法很自然就是取最左最小值取最右最大值那么得到的差值就是最大利润。 def max_profit(prices):if not prices:return 0max_profit 0min_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 Truereturn 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:breakreturn 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 1return ans# 示例 s ababcbacadefegdehijhklij print(partitionLabels(s)) # 输出 哈希表
9. 两数之和 - 力扣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]] ireturn [] 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 strfor string in strings:key .join(sorted(string))mp[key].append(string)return list(mp.values())
10. 最长连续序列 - 力扣LeetCode class Solution:def longestConsecutive(self, nums: List[int]) - int:ans 0st set(nums) # 把 nums 转成哈希集合for x in st: # 遍历哈希集合if x - 1 in st:continue# x 是序列的起点y x 1while 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 defaultdictclass Solution:def subarraySum(self, nums: list, k: int) - int:# 初始化计数器用于记录和为k的子数组的数量count 0n len(nums)# 使用defaultdict来存储前缀和出现的次数初始时前缀和为0出现1次preSums defaultdict(int)preSums[0] 1# 初始化前缀和为0presum 0# 遍历数组中的每个元素for i in range(n):# 更新当前的前缀和presum nums[i]# 如果存在某个前缀和等于当前前缀和减去k则说明存在一个子数组的和为k# defaultdict的特性使得当key不存在时返回0所以这里不需要判断key是否存在count preSums[presum - k]# 将当前前缀和出现的次数加1preSums[presum] 1# 返回和为k的子数组的数量return count 双指针
11. 移动零 - 力扣LeetCode 快慢指针当碰到0时i会比i0走的快 from typing import Listclass 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# 注意这个方法直接修改了输入的数组不需要返回值
12. 盛最多水的容器 - 力扣LeetCode 对撞指针两个指针列表一边一个向中间靠近同时根据两者的高度判断两个指针是否前进 class Solution:def maxArea(self, height: List[int]) - int:ans left 0right len(height) - 1while left right:area (right - left) * min(height[left], height[right])ans max(ans, area)if height[left] height[right]:# height[left] 与右边的任意线段都无法组成一个比 ans 更大的面积left 1else:# height[right] 与左边的任意线段都无法组成一个比 ans 更大的面积right - 1return ans42. 接雨水 - 力扣LeetCode 对撞指针 from typing import Listclass 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 1else:# 计算当前右指针位置可以捕获的水量并累加到答案中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 1while left right and nums[right] nums[right - 1]:right - 1left 1right - 1return 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,0res 0if len(s) 0:return 0if s.count(s[0]) len(s):return 1if len(set(s)) len(s):return len(s)while right len(s):if s[right] not in s[left:right]:right 1res max(res,len(s[left:right]))else:while s[right] in s[left:right]:left 1return res438. 找到字符串中所有字母异位词 - 力扣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] * 26s_cnt [0] * 26# 统计字符串p中每个字符的出现次数for i in range(m):p_cnt[ord(p[i]) - ord(a)] 1left 0 # 初始化滑动窗口的左边界for right in range(n): # 遍历字符串scur_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 # 返回所有异位词的起始索引列表
13. 滑动窗口最大值 - 力扣LeetCode 单调递减的双端队列来保存窗口中的元素索引确保队列的首部始终是当前窗口的最大值的索引。 双端队列deque允许在队列的两端进行插入和删除操作。 from collections import dequedef 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
14. 最小覆盖子串 - 力扣LeetCode 初始化两个指针left 和 right它们分别表示滑动窗口的左右边界。使用两个哈希表或字典来记录当前窗口中的字符频率和目标字符串 t 中字符的频率。扩展 right 指针来增加窗口的大小直到窗口包含了 t 中所有的字符。一旦窗口包含了 t 中所有的字符尝试通过移动 left 指针来缩小窗口的大小同时保持窗口包含 t 中所有的字符。在每次移动 left 指针时如果窗口仍然包含 t 中所有的字符则更新最小子串的长度和起始位置。重复步骤 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, 0start, length 0, float(inf) # 最小子串的起始位置和长度while right len(s):# 即将移入窗口的字符c s[right]# 右移窗口right 1# 更新窗口中的字符频率if c in need:window[c] window.get(c, 0) 1if window[c] need[c]:valid 1# 判断左侧窗口是否要收缩while valid len(need):# 更新最小子串if right - left length:start leftlength right - left# 即将移出窗口的字符d s[left]# 左移窗口left 1# 更新窗口中的字符频率if d in need:if window[d] need[d]:valid - 1window[d] - 1# 返回最小子串return if length float(inf) else s[start:start length]# 示例 s ADOBECODEBANC t ABC print(min_window(s, t)) # 输出 BANC 广度优先搜索算法基本用的就是队列深度优先搜索算法DFS用的基本都是递归