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

网站建设中心四川seo

网站建设中心,四川seo,好的网站和网页有哪些,wordpress 最新更新插件题目描述 给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。 示例 1: 输入:digits "23" 输出…

题目描述

        给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

示例 1:

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

示例 2:

输入:digits = ""
输出:[]

示例 3:

输入:digits = "2"
输出:["a","b","c"]

解答

class Solution(object):def letterCombinations(self, digits):""":type digits: str:rtype: List[str]"""# 思路一:回溯法# 对于digit为空的特殊情况,直接返回[]if not digits:return []# 定义数字与字母映射的字典phone_map = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl','6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}# 定义回溯函数# combination:当前已经生成的组合# nextdigits:剩余未处理的数字def backtract(combination,nextdigits):# 如果没有剩余数字,则读入combination并停止if len(nextdigits)==0:output.append(combination)return # 遍历当前数字对应的所有字母,进入下一阶段for letter in phone_map[nextdigits[0]]:# 将当前字母加入组合,并递归处理剩余数字backtract(combination+letter,nextdigits[1:])# 输出字典output=[]# 初始化回溯函数backtract("",digits)return output# # 思路二:构建多叉树# # 对于特殊情况,直接输出[]# if not digits:#     return []# # 定义数字与字母映射的字典# phone_map = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl','6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}# # 定义深度优先搜索(DFS)函数# # node:当前数字对应的字母映射# # path:当前路径,即已生成的部分组合# def dfs(node,path):#     # 如果路径长度等于输入数字长度,表示生成了一个完整组合#     if len(path)==len(digits):#         output.append(path)#         return#     # 如果当前节点为空,直接返回(无效分支)#     if node is None:#         return#     # 遍历当前数字对应的所有字母#     for letter in phone_map[node]:#         dfs(digits[len(path) + 1] if len(path) + 1 < len(digits) else None,path+letter)# output=[]# dfs(digits[0],"")# return output

        思路一,回溯法:其核心思想是逐步生成所有可能的字母组合,通过递归遍历当前数字对应的所有字母,并将当前字母加入到已经生成的部分组合中。当没有剩余数字时,将完整的组合加入结果列表。这种方法的优点是逻辑清晰,容易实现递归树的分支剪枝。

        思路二,多叉树的深度优先搜索:通过构造一棵树,每个数字的字母映射为一层,路径上的节点代表当前生成的组合。通过递归从顶层到叶子节点(即完成一个完整组合)逐层搜索,并将完整的路径加入结果列表。这种方法本质上也是通过递归实现,但更侧重于以树的结构来思考问题。相比回溯法,逻辑上稍复杂,但仍能很好地生成所有组合。

        对比两种方法,回溯法以 "递归 + 剪枝" 的方式,通过遍历每个数字的字母映射生成组合,逻辑简洁明了,易于实现;多叉树的 DFS则从树的结构出发,递归生成字母组合,逻辑上与回溯法类似,但代码中显示了树的层级关系,适合对树结构有直观理解的场景。并且,两种方法在时间复杂度上相同,均为 O(3^n * 4^m)n 为包含3个字母的数字数量,m 为包含4个字母的数字数量)。

知识拓展:深度优先搜索 vs. 广度优先搜索

深度优先搜索(Depth-First Search, DFS)

        概念

        深度优先搜索是一种搜索策略,它会沿着一个路径不断深入到树或图的叶子节点,直到不能再继续深入为止,然后回溯到上一个分支点继续探索其他路径。它优先关注的是路径的深度。

        核心特点

  1. 深入探索:优先沿着路径一直深入到底。
  2. 回溯机制:在某路径不能继续深入时,回到上一个分支点继续探索。
  3. 使用栈结构:可以用递归(隐式栈)或显式栈实现。
    A/ \B   C/ \
D   E# 其邻接表的结构如下:
graph = {'A': ['B', 'C'],'B': ['D', 'E'],'C': ['F'],'D': [],'E': [],'F': []
}

以图中的搜索为例,假设我们从节点 A 出发,目标是访问所有节点,则深度优先的访问顺序为:A → B → D → E → C,其搜索过程如下:

  1. A 出发,访问 B
  2. B 深入到 D,访问 D
  3. D 回溯到 B,然后访问 E
  4. B 回溯到 A,然后访问 C

        实现(递归版本)

def dfs(node, visited):if node in visited:  # 如果节点已访问过,直接返回returnvisited.add(node)    # 标记当前节点为已访问print(node)          # 访问当前节点for neighbor in graph[node]:  # 遍历临接表中的相邻节点dfs(neighbor, visited)

广度优先搜索(Breadth-First Search, BFS)

        概念

        广度优先搜索是一种搜索策略,它从起始节点开始,按照层次逐层向外扩展,直到找到目标或访问完所有节点。它优先关注的是路径的宽度。

        核心特点

  1. 逐层探索:先访问当前层的所有节点,再访问下一层的节点。
  2. 使用队列结构:通过队列(FIFO)存储待访问的节点。
    A/ \B   C/ \
D   E

        还是以同样的图为例,从节点 A 出发,其访问顺序为: A → B → C → D → E,其搜索过程如下:

  1. A 出发,访问 A
  2. 访问 A 的所有直接相邻节点:BC
  3. 访问 B 的相邻节点:DE

        实现

from collections import dequedef bfs(start):queue = deque([start])  # 初始化队列visited = set()         # 用于存储已访问的节点while queue:node = queue.popleft()  # 从队列头部取出一个节点if node not in visited:visited.add(node)   # 标记为已访问print(node)         # 访问当前节点queue.extend(graph[node])  # 将相邻节点加入队列

两者对比

属性

深度优先搜索 (DFS)

广度优先搜索 (BFS)

搜索策略一条路径深入到底,无法继续时回溯。按层次逐层搜索,每层节点按宽度扩展。
数据结构栈(递归或显式栈)。队列(FIFO)。
适用场景适用于寻找深度路径,如迷宫寻路问题。适用于寻找最短路径,如图的最短路径问题。
时间复杂度O(V+E),其中 V 是顶点数,E 是边数。O(V+E),与 DFS 相同。
空间复杂度最坏情况下需要存储所有递归栈帧。需要存储整个图的一层节点。
实现难度易于实现,递归实现尤为简单。需要显式维护队列,相对复杂一些。

感谢阅读,希望对你有所帮助~

http://www.ds6.com.cn/news/57705.html

相关文章:

  • 商业网站建设费用网络营销方案3000字
  • 网站备案登记查询系统如何提高百度搜索排名
  • 运城网站建设价格三十个知识点带你学党章
  • 高端制作网站设计seo平台怎么样
  • 租用服务器一般是谁帮助维护网站安全信息推广服务
  • 广州网站建设网站制作公司seo免费优化
  • 北京口碑最好的装修公司泰州百度seo公司
  • 网站有备案 去掉备案百度竞价推广效果怎么样
  • 丰涵网站建设科技友情链接在线观看
  • 优秀手机网站模板图片企业老板培训课程
  • 晓风彩票门户网站建设网络推广公司口碑
  • 上海人才网北京seo教师
  • wordpress图片css企业站seo案例分析
  • 亚马逊网站建设做什么营业推广的概念
  • 免费下载网站模板国外b站浏览器
  • 站点推广是什么意思北京百度推广客服电话多少
  • 泉州网站制作企业软文街官网
  • 孝感网站开发郑州seo关键词
  • 如何购买网站空间国产免费crm系统有哪些
  • 海南响应式网页建设方案网站关键词优化排名怎么做
  • 做网站推广价格郑州做网站推广电话
  • 备案 网站内容怎么做网络宣传推广
  • 做网站一定要用ps吗网站优化排名哪家好
  • 武汉前端网站开发公司app推广营销
  • 花店网站建设构思网店运营推广方案
  • 网站设计公司业务怎么做win7系统优化大师
  • 济阳做网站哪家好实时热点新闻事件
  • ps做网站 字体多大学校招生网络营销方案
  • 网站建设是设计师吗中国目前最好的搜索引擎
  • 在网站做登记表备案 如果修改整合营销是什么