初学python的我开始Leetcode题10-1

article/2025/9/8 20:56:48

提示：100道LeetCode热题10-1主要是回溯相关，包括四题：全排列、子集、电话号码的字母组合、组合总和。由于初学，所以我的代码部分仅供参考。

前言

下周是第十六周，然后是两周的期末周，所以马上会缺两周左右......

回溯算法和暴力枚举法都是解决组合、排列、子集等问题的常用方法，但它们在实现方式和效率上有显著的区别。

暴力枚举法是一种直接尝试所有可能情况的方法，直到找到所有符合条件的解。

特点：

  • 简单直接：通过直接列举所有可能的组合、排列或子集来找到解。

  • 时间复杂度高：对于较大的输入规模，暴力枚举法可能会非常慢，因为它尝试了所有可能的情况。

  • 空间复杂度低：通常只需要存储当前的解和最终结果。

适用场景：

  • 输入规模较小，所有可能情况数量不多时。

  • 问题本身没有明显的剪枝空间，即很难通过某种方式减少需要尝试的情况。

回溯算法是一种通过试错来解决问题的算法，它尝试分步解决问题，如果发现当前路径不能得到有效解，则回退到上一步选择另一条路径继续尝试。

特点：

  • 效率较高：通过剪枝（即在发现当前路径不可能产生有效解时提前终止该路径的探索），回溯算法可以避免尝试所有可能的情况，从而提高效率。

  • 空间复杂度可能较高：需要递归调用，可能会占用较多的栈空间。

  • 实现复杂度较高：需要设计递归函数和回溯逻辑，实现相对复杂。

适用场景：

  • 输入规模较大，但问题本身有剪枝空间。

  • 需要找到所有可能的解，而不仅仅是一个解。

提示：以下是本篇文章正文内容，下面结果代码仅供参考

题目1：全排列

1.题目要求：

题目如下：

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

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

示例 2：

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

示例 3：

输入：nums = [1]
输出：[[1]]

提示：

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • nums 中的所有整数 互不相同

代码框架已经提供如下：

class Solution(object):

    def permute(self, nums):

        """

        :type nums: List[int]

        :rtype: List[List[int]]

        """

2.结果代码：

class Solution(object):def permute(self, nums):n=len(nums)res=[]def backtrack(path,used):if len(path)==len(used):res.append(path[:])returnfor i in range(len(used)):if not used[i]:used[i]=Truepath.append(nums[i])                        backtrack(path,used)path.pop()used[i]=Falseused=[False]*len(nums)backtrack([],used)return res

说明：

  1. 初始化变量：

    • n：数组 nums 的长度。

    • res：用于存储所有生成的排列。

  2. 定义递归函数 backtrack：

    • path：当前路径，即当前生成的排列。

    • used：一个布尔数组，用于标记哪些数字已经被使用。

  3. 终止条件：

    • 当 path 的长度等于 nums 的长度时，说明已经生成了一个完整的排列，将其添加到结果列表 res 中。

  4. 递归过程：

    • 遍历 used 数组，找到未被使用的数字。

    • 将找到的数字添加到 path 中，并标记为已使用。

    • 递归调用 backtrack，传入更新后的 path 和 used。

    • 回溯：在递归返回后，将当前选择的数字从 path 中移除，并标记为未使用，以便尝试下一个数字。

  5. 初始化 used 数组：

    • 用于标记哪些数字已经被使用。

  6. 调用 backtrack 函数：

    • 从空路径和所有数字未被使用开始递归。

因为对于每个数字有 n 种选择，总共有 n! 种排列。

因为递归调用的深度最多为 n。

题目2：子集

1.题目要求：

题目如下：

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

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

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

示例 2：

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

提示：

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • nums 中的所有元素 互不相同

代码框架已经提供如下：

class Solution(object):

    def subsets(self, nums):

        """

        :type nums: List[int]

        :rtype: List[List[int]]

        """

2.结果代码：

class Solution(object):def subsets(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""def backtrack(start, path):# 将当前路径添加到结果列表中results.append(path[:])# 遍历从 start 开始的所有元素for i in range(start, len(nums)):# 选择当前元素path.append(nums[i])# 递归调用 backtrackbacktrack(i + 1, path)# 回溯：移除当前元素path.pop()results = []backtrack(0, [])return results

说明：

  1. 定义递归函数 backtrack：

    • start：当前递归的起始位置。

    • path：当前路径，即当前生成的子集。

  2. 终止条件：

    • 当 path 被添加到结果列表 results 中时，说明已经生成了一个完整的子集。

  3. 递归过程：

    • 从 start 开始遍历所有元素，找到未被选择的元素。

    • 将找到的元素添加到 path 中，并标记为已选择。

    • 递归调用 backtrack，传入更新后的 start 和 path。

    • 回溯：在递归返回后，将当前选择的元素从 path 中移除，并标记为未选择，以便尝试下一个元素。

  4. 初始化结果列表 results：

    • 用于存储所有生成的子集。

  5. 调用 backtrack 函数：

    • 从起始位置 0 和空路径开始递归。

因为对于每个元素，有 2 种选择（选择或不选择），总共有 2n 个子集。

因为递归调用的深度最多为 n。

题目3：电话号码的字母组合

1.题目要求：

题目如下：

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 0 <= digits.length <= 4
  • digits[i] 是范围 ['2', '9'] 的一个数字。

代码框架已经提供如下：

class Solution(object):

    def letterCombinations(self, digits):

        """

        :type digits: str

        :rtype: List[str]

        """

2.结果代码：

class Solution(object):def letterCombinations(self, digits):""":type digits: str:rtype: List[str]"""if not digits:return []# 定义数字到字母的映射phone_map = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl','6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}def backtrack(index, path):# 终止条件：如果当前路径长度等于 digits 的长度，说明已经生成了一个完整的组合if index == len(digits):combinations.append("".join(path))return# 获取当前数字对应的所有可能字母possible_letters = phone_map[digits[index]]for letter in possible_letters:# 选择当前字母path.append(letter)# 递归调用 backtrackbacktrack(index + 1, path)# 回溯：移除当前字母path.pop()combinations = []backtrack(0, [])return combinations

说明：

  1. 定义递归函数 backtrack：

    • index：当前递归的索引位置。

    • path：当前路径，即当前生成的字母组合。

  2. 终止条件：

    • 当 index 等于 digits 的长度时，说明已经生成了一个完整的字母组合，将其添加到结果列表 combinations 中。

  3. 递归过程：

    • 获取当前数字对应的所有可能字母。

    • 遍历所有可能的字母，将其添加到 path 中，并标记为已选择。

    • 递归调用 backtrack，传入更新后的 index 和 path。

    • 回溯：在递归返回后，将当前选择的字母从 path 中移除，并标记为未选择，以便尝试下一个字母。

  4. 初始化结果列表 combinations：

    • 用于存储所有生成的字母组合。

  5. 调用 backtrack 函数：

    • 从索引位置 0 和空路径开始递归。

题目4：组合总和

1.题目要求：

题目如下：

给你一个 无重复元素 的整数数组 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 。
仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []

提示：

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • candidates 的所有元素 互不相同
  • 1 <= target <= 40

代码框架已经提供如下：

class Solution(object):

    def combinationSum(self, candidates, target):

        """

        :type candidates: List[int]

        :type target: int

        :rtype: List[List[int]]

        """

2.结果代码：

class Solution(object):def combinationSum(self, candidates, target):""":type candidates: List[int]:type target: int:rtype: List[List[int]]"""def backtrack(remaining, path, start):if remaining == 0:results.append(path[:])returnfor i in range(start, len(candidates)):if candidates[i] > remaining:breakpath.append(candidates[i])backtrack(remaining - candidates[i], path, i)path.pop()results = []candidates.sort()  # 排序可以避免重复组合backtrack(target, [], 0)return results

说明：

  1. 定义递归函数 backtrack：

    • remaining：剩余需要找到的和。

    • path：当前路径，即当前生成的组合。

    • start：当前递归的起始位置，用于避免重复使用同一个数字。

  2. 终止条件：

    • 当 remaining 等于 0 时，说明已经找到了一个有效的组合，将其添加到结果列表 results 中。

  3. 递归过程：

    • 从 start 开始遍历所有元素，找到可以添加到当前组合中的数字。

    • 将找到的数字添加到 path 中，并递归调用 backtrack，传入更新后的 remaining 和 path。

    • 回溯：在递归返回后，将当前选择的数字从 path 中移除，以便尝试下一个数字。

  4. 初始化结果列表 results：

    • 用于存储所有生成的组合。

  5. 调用 backtrack 函数：

    • 从剩余和 target 和空路径开始递归。

  6. 排序：

    • 对 candidates 进行排序，可以避免重复组合。

总结

针对回溯的四种题型进行了学习，了解了部分有关回溯与python的相关知识，大家加油！


http://www.hkcw.cn/article/nYkggjlAGs.shtml

相关文章

IPTV电视直播 1.6.0 | 手机电视直播 秒播无卡顿

IPTV电视直播 1.6.0 | 手机电视直播 秒播无卡顿

电视直播是一款功能强大且用户体验优秀的电视直播软件。它提供了丰富的节目资源&#xff0c;并支持高清画质播放&#xff0c;无论是家庭娱乐、移动办公还是学习&#xff0c;都能满足用户的需求。该应用完全无广告、无弹窗&#xff0c;确保用户享受纯净的观看体验。此外&#xf…
阅读更多...
BugKu Web渗透之备份是个好习惯

BugKu Web渗透之备份是个好习惯

启动场景后&#xff0c;网页显示一段字符串。 看起来像md5值&#xff0c;但是又过长了。 步骤一&#xff1a;右键查看源代码&#xff0c;没有发现任何异常。 步骤二&#xff1a;使用dirsearch去查看是否有其他可疑文件。 在终端输入&#xff1a; dirsearch -u http://117.72.…
阅读更多...
深入理解 SELinux：通过 Nginx 和 SSH 服务配置实践安全上下文与端口策略

深入理解 SELinux：通过 Nginx 和 SSH 服务配置实践安全上下文与端口策略

目录 一、引言 二、实验环境说明 三、实验 1&#xff1a;Nginx 服务安全上下文配置 3.1 实验目标 3.2 操作步骤 1. 开启 SELinux 并重启系统 2. 安装 Nginx 并创建自定义目录 3. 配置 Nginx 指向自定义目录 4. 分析 SELinux 上下文冲突 5. 修改上下文为合法类型 6. 验…
阅读更多...
Linux 开发工具

Linux 开发工具

1.sudo白名单 我们如果要让普通用户有sudo的权限 我们就要登录root用户 在/etc/sudoers目录下 通过文本编辑器&#xff08;我用的是vim&#xff09; 将要添加的用户 直接添加进去 如下图光标行就是我添加的白名单用户 然后我们添加的这个ly_centos就有sudo的权限了 2.gcc…
阅读更多...
React 第四十九节 Router中useNavigation的具体使用详解及注意事项

React 第四十九节 Router中useNavigation的具体使用详解及注意事项

前言 useNavigation 是 React Router 中一个强大的钩子&#xff0c;用于获取当前页面导航的状态信息。 它可以帮助开发者根据导航状态优化用户体验&#xff0c;如显示加载指示器、防止重复提交等。 一、useNavigation核心用途 检测导航状态&#xff1a;判断当前是否正在进行…
阅读更多...
从数据持久化到网络通信与OpenCV：Qt应用程序开发的深度探索与实战

从数据持久化到网络通信与OpenCV：Qt应用程序开发的深度探索与实战

文章目录 前言一、QSettings&#xff1a;轻量级数据持久化方案1.1 QSettings 主要特点1.2 QSettings 常用函数整理 二、数据库2.1 连接SQLite数据库2.2 建表2.3 增删改 三、网络编程3.1 网络分层3.2 IP地址3.3 端口号3.4 基于TCP的Socket通信3.4 相关接口3.4.1核心类3.4.2 通信…
阅读更多...
【产品经理从0到1】自媒体端产品设计

【产品经理从0到1】自媒体端产品设计

后台的定义 “后台” 与“前台”都是相对独立的平台&#xff0c;前台是服务于互联网用户的平台 &#xff0c;后台主要是支撑前台页面内容、数据及对前台业务情况的统计分析的系统&#xff1b; 后台与前台的区别 第1&#xff1a;使用用户不同 前台用户&#xff1a;互联网用户…
阅读更多...
Ubuntu20.04操作系统ssh开启oot账户登录

Ubuntu20.04操作系统ssh开启oot账户登录

文章目录 1 前提2 设置root密码3 允许ssh登录root账户3.1 编辑配置文件3.2 重启ssh服务 4 安全注意事项 1 前提 ssh可以使用普通用户正常登录。 2 设置root密码 打开终端&#xff0c;设置密码 sudo passwd root # 设置root密码3 允许ssh登录root账户 3.1 编辑配置文件 su…
阅读更多...
四叉树实现四边形网格

四叉树实现四边形网格

import matplotlib.pyplot as plt import matplotlib.patches as patches import numpy as np # 四叉树节点 class QuadNode:def __init__(self, x, y, width, height, depth):self.x xself.y yself.width widthself.height heightself.depth depthself.children []self.…
阅读更多...
园区智能化集成平台汇报方案

园区智能化集成平台汇报方案

该方案为园区智能化集成平台设计，依据《智能建筑设计标准》等 20 余项国家与行业规范，针对传统园区信息孤岛、反应滞后、经验流失、管理粗放等痛点，构建可视化智慧园区管理平台，实现大屏数据可视化、三维设备监控、智慧运维（含工单管理、巡检打卡）、能源能耗分析、AI 安防…
阅读更多...
C#中的BeginInvoke和EndInvoke：异步编程的双剑客

C#中的BeginInvoke和EndInvoke：异步编程的双剑客

文章目录 引言1. BeginInvoke和EndInvoke的基本概念1.1 什么是BeginInvoke和EndInvoke1.2 重要概念解释 2. 委托中的BeginInvoke和EndInvoke2.1 BeginInvoke方法2.2 EndInvoke方法2.3 两者的关系 3. 使用方式与模式3.1 等待模式3.2 轮询模式3.3 等待句柄模式3.4 回调模式 4. 底…
阅读更多...
基于通义千问的儿童陪伴学习和成长的智能应用架构。

基于通义千问的儿童陪伴学习和成长的智能应用架构。

1.整体架构概览 我们的儿童聊天助手将采用典型的语音交互系统架构，结合大模型能力和外部知识库： 2. 技术方案分解 2.1. 前端应用/设备 选择： 移动App（iOS/Android）、Web应用，或者集成到智能音箱/平板等硬件设备中。技术栈： 移动App： React Native / Flutter (跨平台…
阅读更多...
【STIP】安全Transformer推理协议

【STIP】安全Transformer推理协议

Secure Transformer Inference Protocol 论文地址&#xff1a;https://arxiv.org/abs/2312.00025 摘要 模型参数和用户数据的安全性对于基于 Transformer 的服务&#xff08;例如 ChatGPT&#xff09;至关重要。虽然最近在安全两方协议方面取得的进步成功地解决了服务 Transf…
阅读更多...
MyBatisPlus（1）：快速入门

MyBatisPlus（1）：快速入门

我们知道&#xff0c;MyBatis是一个优秀的操作数据库的持久层框架&#xff08;优秀持久层框架——MyBatis&#xff09;&#xff0c;其基于底层的JDBC进行高度封装&#xff0c;极大的简化了开发。但是对于单表操作而言&#xff0c;我们需要重复地编写简单的CRUD语句。这其实是不…
阅读更多...
【ARM】【FPGA】【硬件开发】Chapter.1 AXI4总线协议

【ARM】【FPGA】【硬件开发】Chapter.1 AXI4总线协议

Chapter.1 AXI4总线协议 作者&#xff1a;齐花Guyc(CAUC) 一、总线介绍 AXI4总线 AXI4总线就像是SoC内部的“高速公路”&#xff0c;负责在不同硬件模块之间高效传输数据。 AXI4协议通过 5个独立通道 传输数据和控制信号&#xff0c;每个通道都有自己的信号线&#xff0c;互…
阅读更多...
.NET 7 AOT 使用及 .NET 与 Go 语言互操作详解

.NET 7 AOT 使用及 .NET 与 Go 语言互操作详解

.NET 7 AOT 使用及 .NET 与 Go 语言互操作详解 目录 .NET 7 AOT 使用及 .NET 与 Go 语言互操作详解 一、背景与技术概述 1.1 AOT 编译技术简介 1.2 Go 语言与 .NET 的互补性 二、.NET 7 AOT 编译实践 2.1 环境准备 2.2 创建 AOT 项目 2.3 AOT 编译流程 2.4 调试信息处…
阅读更多...
Shortest path 代码

Shortest path 代码

Project https://graphics.cs.utah.edu/research/projects/shortest-path-to-boundary/ Build and Debug Fork:(在Win10上&#xff09; https://github.com/chunleili/Shortest-Path-to-Boundary-for-Self-Intersecting-Meshes commit hash d3160168d2b6a58188d12e6cd959da…
阅读更多...
Spring框架学习day1--基础概念

Spring框架学习day1--基础概念

Spring基础部分**轻量级的**IOC&#xff1a;控制反转&#xff08;对象由自己管理变成交给框架管理&#xff09;AOP&#xff1a;面向切面编程一站式BaenSpring体系结构 Spring Hello World 搭建 Spring基础部分 Spring是一个轻量级的IOC、AOP的一站式java开发框架&#xff0c;为…
阅读更多...
立志成为一名优秀测试开发工程师(第九天)——使用fiddler工具、request库进行接口测试

立志成为一名优秀测试开发工程师(第九天)——使用fiddler工具、request库进行接口测试

接口测试学习 目录 一、接口测试的介绍 二、抓包软件Fiddler的使用 三、使用Python的Request库发送get、post请求&#xff1a; 1.get请求 2.post请求 四、总结 登录接口实现 认证请求处理 异常处理 高级配置 接口测试工具类封装 测试用例设计规范 Cookie处理方案 …
阅读更多...
【面板数据】各地区新型数字基础设施数据集（2002-2025年）

【面板数据】各地区新型数字基础设施数据集（2002-2025年）

新型数字基础设施是利用新一代信息技术&#xff08;如5G、人工智能、物联网、大数据、区块链等&#xff09;构建的基础设施体系&#xff0c;主要服务于信息传输、计算存储、智能分析和融合应用等环节。新型数字基础设施作为引领经济社会数字化转型的重要支撑&#xff0c;在各地…
阅读更多...
推荐文章

Copyright @ 2022~2023