[Leetcode] [Tutorial] 回溯
文章目录
- 46. 全排列
- Solution
- 78. 子集
- Solution
- 17. 电话号码的字母组合
- Solution
- 39. 组合总和
- Solution
- 22. 括号生成
- Solution
46. 全排列
给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例:
输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Solution
class Solution:def permute(self, nums: List[int]) -> List[List[int]]:def backtrack(path):if len(path) == len(nums):res.append(path[:])returnfor num in nums:if num not in path:path.append(num)backtrack(path)path.pop()res = []backtrack([])return res
在backtrack函数中,我们通过一个for循环来遍历nums中的所有元素,并尝试将其添加到path的末尾。每当我们递归调用backtrack函数后,我们就会移除path的最后一个元素,并在下一次for循环迭代中尝试添加下一个元素。
78. 子集
给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例:
输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Solution
class Solution:def subsets(self, nums: List[int]) -> List[List[int]]:def backtrack(start, path):res.append(path[:])for i in range(start, len(nums)):path.append(nums[i])backtrack(i + 1, path)path.pop()res = []backtrack(0, [])return res
我们可以还使用位掩码(bitmask)的方法。
class Solution:def subsets(self, nums: List[int]) -> List[List[int]]:n = len(nums)output = []for i in range(2**n):# generate bitmask, from 0..00 to 1..11bitmask = bin(i)[2:].zfill(n)# append subset corresponding to that bitmaskoutput.append([nums[j] for j in range(n) if bitmask[j] == '1'])return output
bin(i)是 Python 的内置函数,用于将整数 i 转换成二进制字符串。例如,bin(3) 将返回 ‘0b11’。‘0b’ 是表示这是一个二进制数。
.zfill(n)是 Python 字符串的一个方法,用于在字符串前面填充 0,直到字符串的长度为 n。例如,‘11’.zfill(3) 将返回 ‘011’。
17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

示例 1:
输入:digits = “23”
输出:[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
Solution
39. 组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。
对于给定的输入,保证和为 target 的不同组合数少于 150 个。
示例 1:
输入:candidates = [2,3,6,7], target = 7
输出:[[2,2,3],[7]]
Solution
class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:def backtrack(target, path, start):if target == 0:res.append(path[:])returnfor i in range(start, len(candidates)):if candidates[i] > target:continuepath.append(candidates[i])backtrack(target - candidates[i], path, i)path.pop()res = []backtrack(target, [], 0)return res
22. 括号生成
数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
示例 1:
输入:n = 3
输出:[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]
Solution
class Solution:def generateParenthesis(self, n: int) -> List[str]:def backtrack(s, left, right):if len(s) == n * 2:res.append(''.join(s))returnif left < n:s.append('(')left += 1backtrack(s, left, right)s.pop()left -= 1if left > right:s.append(')')right += 1backtrack(s, left, right)s.pop()right -= 1res = []backtrack([], 0, 0)return res
s是一个字符列表,当你要将最终结果添加到res时,你需要用 ‘’.join(s) 把s转换为字符串。
实际上,left和right的值都可以自动“回溯”到他们在函数调用开始时的状态。
class Solution:def generateParenthesis(self, n: int) -> List[str]:def backtrack(s, left, right):if len(s) == n * 2:res.append(s)returnif left < n:backtrack(s + '(', left + 1, right)if right < left:backtrack(s + ')', left, right + 1)res = []backtrack('', 0, 0)return res
相关文章:
[Leetcode] [Tutorial] 回溯
文章目录 46. 全排列Solution 78. 子集Solution 17. 电话号码的字母组合Solution 39. 组合总和Solution 22. 括号生成Solution 46. 全排列 给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 示例: 输入&…...
STM32 CubeMX USB_MSC(存储设备U盘)
STM32 CubeMX STM32 CubeMX USB_MSC(存储设备U盘) STM32 CubeMX前言 《使用内部Flash》——U盘一、STM32 CubeMX 设置USB时钟设置USB使能UBS功能选择FATFS功能 二、代码部分修改代码"usbd_storage_if.c"修改代码"user_diskio.c"main函数初始化插…...
湘大 XTU OJ 1214 A+B IV 题解:数位移动的本质+布尔变量标记+朴素模拟
一、链接 AB IV 二、题目 题目描述 小明喜欢做ab的算术,但是他经常忘记把末位对齐,再进行加,所以,经常会算错。 比如1213,他把12左移了1位,结果变成了133。 小明已经算了一些等式,请计算一下…...
以商业大数据技术助力数据合规流通体系建立,合合信息参编《数据经纪从业人员评价规范》团标
经国务院批准,由北京市人民政府、国家发展和改革委员会、工业和信息化部、商务部、国家互联网信息办公室、中国科学技术协会共同主办的2023 全球数字经济大会于近期隆重召开。由数交数据经纪(深圳)有限公司为主要发起单位,合合信息…...
【论文阅读】Deep Instance Segmentation With Automotive Radar Detection Points
基于汽车雷达检测点的深度实例分割 一个区别: automotive radar 汽车雷达 : 分辨率低,点云稀疏,语义上模糊,不适合直接使用用于密集LiDAR点开发的方法 ; 返回的物体图像不如LIDAR精确,可以…...
易服客工作室:如何创建有用的内容日历
利用技巧和工具优化您的内容营销效率和效果。创建一个内容日历,您的整个团队都会从中受益! 欢迎来到熙熙攘攘、瞬息万变的内容营销世界,在这里,截止日期到来的速度比喝咖啡的猎豹还要快。 现在,想象一下在没有地图、…...
Excel革命,基于电子表格开发的新工具,不是Access和Power Fx
深谙其道 在日常工作中,Excel是许多人不可或缺的办公工具。 是微软的旗下产品,属于Microsoft 365套件中的一部分,强大的数据处理和计算功能,被普遍应用在全球各行各业的人群当中,是一款强大且普及的电子表格软件。 于…...
“崩溃”漏洞会影响英特尔 CPU 的使用寿命,可能会泄露加密密钥等
对于 CPU 安全漏洞来说,本周是重要的一周。昨天,不同的安全研究人员发布了两个不同漏洞的详细信息,一个影响多代英特尔处理器,另一个影响最新的 AMD CPU。“ Downfall ”和“ Inception ”(分别)是不同的错…...
17.电话号码的字母组合(回溯)
目录 一、题目 二、代码 一、题目 17. 电话号码的字母组合 - 力扣(LeetCode) 二、代码 class Solution {const char*data[10]{"","","abc","def","ghi","jkl","mno","pq…...
Redis小例子
MAC电脑下Redis的安装: brew install redis下面给一个Java操作redis的小例子 import redis.clients.jedis.Jedis;public class Demo {public static void main(String[] args) {// 创建 Jedis 客户端实例,连接到本地 Redis 服务器,默认端口…...
ETLCloud+MaxCompute实现云数据仓库的高效实时同步
MaxCompute介绍 MaxCompute是适用于数据分析场景的企业级SaaS(Software as a Service)模式云数据仓库,以Serverless架构提供快速、全托管的在线数据仓库服务,消除了传统数据平台在资源扩展性和弹性方面的限制,最小化用…...
HTTP代理授权方式介绍
在网络爬虫过程中,我们经常需要使用HTTP代理来实现IP隐藏、突破限制或提高抓取效率。而为了确保代理的正常使用,并避免被滥用,代理服务商通常会采用授权方式。在本文中,我们将介绍几种常见的HTTP代理授权方式,以帮助你…...
《合成孔径雷达成像算法与实现》Figure3.4
代码对补零信号与未补零信号都进行了实现,补零信号更加贴近书中图3.4的样子: clc clear all close all%参数设置 TBP 100; %时间带宽积 T 10e-6; %脉冲持续时间 alpha_os [1.4,1.2,1.0,0…...
qt5.15.2 使用mysql8.1
报错: QMYSQL driver not loaded 报错:无 QMYSQL 使用 QStringList drivers QSqlDatabase::drivers(); //获取现在可用的数据库驱动 foreach(QString driver, drivers) qDebug() << driver; “QSQLITE” “QMARIADB” “QMYSQL” “QMYSQL3” “…...
广州华锐互动:VR3D课程在线教育平台为职业院校提供沉浸式的虚拟现实学习体验
随着科技的飞速发展,虚拟现实(VR)和增强现实(AR)技术已经逐渐渗透到我们生活的各个领域。其中,VR3D课程在线教育平台作为一种新兴的教育方式,正在逐渐改变我们的学习方式和体验。本文将详细介绍VR3D课程在线教育平台的应用前景及特点。 VR3D课…...
clion run qt 问题汇总
一、Error copying file “D:/soft/QT/5.15.2/mingw81_64/bin/Qt5Cored.dll” to “D:/work/Ccode/qtproject/cmake-build-debug-qtmingw”.报错 查看路径下确实没有Qt5Cored.dll,只有Qt5Core.dll 注释掉cmakelist中的这三行 重新执行后成功 二、使用CLion编辑u…...
深入理解spring面经
1 了解SpringMVC的处理流程吗? 用户发送请求至前端控制器DispatcherServlet。DispatcherServlet通过处理器映射器HandlerMapping找到对应的处理器。DispatcherServlet将请求提交给对应的处理器Controller。Controller处理完请求后返回ModelAndView。DispatcherServ…...
2023年,App运行小游戏,可以玩出什么创意?
疫情过后,一地鸡毛。游戏行业的日子也不好过。来看看移动游戏收入:2022年,移动游戏收入达到920亿美元,同比下降6.4%。这告诉我们,2022年对移动游戏市场来说是一个小挫折。 但不管是下挫还是上升,移动游戏市…...
景嘉微电子2021笔试题
笔试时间:2020.10.11。 岗位:嵌入式软件开发工程师。 题型:60分钟,45道题,时间紧任务重。 选择题25道,判断题12道,填空题5道,编程题3道。 长沙景嘉微电子,在长沙找嵌入式工作,景嘉微的薪资是top级别的。并且公司有很多开发平台,都可以去应聘试试。 选择题 1、求…...
selenium官网文档阅读总结(day 4)
1.selenium的工作原理 selenium的工作原理涉及以下主要组件和步骤: (1)WebDriver:这是selenium的核心组件,它是一个用于控制浏览器的API。WebDriver提供了许多方法,用于在浏览器中模拟用户操作。不同的浏览器需要相应…...
网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
【Linux】C语言执行shell指令
在C语言中执行Shell指令 在C语言中,有几种方法可以执行Shell指令: 1. 使用system()函数 这是最简单的方法,包含在stdlib.h头文件中: #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...
【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...
HTML前端开发:JavaScript 常用事件详解
作为前端开发的核心,JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例: 1. onclick - 点击事件 当元素被单击时触发(左键点击) button.onclick function() {alert("按钮被点击了!&…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...
uniapp中使用aixos 报错
问题: 在uniapp中使用aixos,运行后报如下错误: AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...
【分享】推荐一些办公小工具
1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由:大部分的转换软件需要收费,要么功能不齐全,而开会员又用不了几次浪费钱,借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要: 近期,在使用较新版本的OpenSSH客户端连接老旧SSH服务器时,会遇到 "no matching key exchange method found", "n…...
