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

力扣热题100_回溯_22_括号生成

文章目录

  • 题目链接
  • 解题思路
  • 解题代码


题目链接

22. 括号生成

数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。

示例 1:
输入:n = 3
输出:[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]

示例 2:
输入:n = 1
输出:[“()”]

解题思路

下面我们根据回溯算法三步走,写出对应的回溯算法。

明确所有选择:括号组合中的每个位置,都可以从 ( 或者 ) 中选出。并且,只有在 symbol < n 的时候,才能选择 (,在 symbol > 0 的时候,才能选择 )。
明确终止条件:当遍历到决策树的叶子节点时,就终止了。即当前路径搜索到末尾时,递归终止。
将决策树和终止条件翻译成代码:

  • 定义回溯函数:
    • backtracking(symbol, index): 函数的传入参数是 symbol(用于表示是否当前组合是否成对匹配),index(当前元素下标),全局变量是 parentheses(用于保存所有有效的括号组合),parenthesis(当前括号组合)。
    • backtracking(symbol, index) 函数代表的含义是:递归根据 symbol,在 ( 和 ) 中选择第 index 个元素。
  • 书写回溯函数主体(给出选择元素、递归搜索、撤销选择部分)。
    • 从当前正在考虑元素,到第 2 * n 个元素为止,枚举出所有可选的元素。对于每一个可选元素:
      • 约束条件:symbol < n 或者 symbol > 0。
      • 选择元素:将其添加到当前括号组合 parenthesis 中。
      • 递归搜索:在选择该元素的情况下,继续递归选择剩下元素。
      • 撤销选择:将该元素从当前括号组合 parenthesis 中移除。
if symbol < n:parenthesis.append('(')backtrack(symbol + 1, index + 1)parenthesis.pop()
if symbol > 0:parenthesis.append(')')backtrack(symbol - 1, index + 1)parenthesis.pop()
  • 明确递归终止条件(给出递归终止条件,以及递归终止时的处理方法)。
    • 当遍历到决策树的叶子节点时,就终止了。也就是当 index == 2 * n 时,递归停止。
    • 并且在 symbol == 0 时,当前组合才是有效的,此时将其加入到最终答案数组中。

解题代码

class Solution:def generateParenthesis(self, n: int) -> List[str]:parentheses = []parenthesis = []def backtrack(symbol, index):if n * 2 == index:if symbol == 0:parentheses.append("".join(parenthesis))else:if symbol < n:parenthesis.append('(')backtrack(symbol + 1, index + 1)parenthesis.pop()if symbol > 0:parenthesis.append(')')backtrack(symbol - 1, index + 1)parenthesis.pop()backtrack(0, 0)return parentheses

参考资料:datawhalechina

相关文章:

力扣热题100_回溯_22_括号生成

文章目录 题目链接解题思路解题代码 题目链接 22. 括号生成 数字 n 代表生成括号的对数&#xff0c;请你设计一个函数&#xff0c;用于能够生成所有可能的并且 有效的 括号组合。 示例 1&#xff1a; 输入&#xff1a;n 3 输出&#xff1a;[“((()))”,“(()())”,“(())()…...

【k8s】ubuntu24.04 containerd 手动从1.7.15 换为1.7.20

24.04的这个应该是apt 安装的1.7.20-1 root@k8s-master-pfsrv:~# sudo apt update && sudo apt install containerd.io -y 命中:1 http://mirrors.aliyun.com/docker-ce/linux/ubuntu noble InRelease 命中:2 https://dl.google.com/linux/chrome/deb stable InRelease…...

Java二十三种设计模式-备忘录模式(19/23)

本文深入探讨了备忘录模式&#xff0c;从定义、组成、实现到使用场景、优缺点、与其他模式的比较&#xff0c;以及最佳实践和替代方案&#xff0c;全面解析了如何在软件开发中有效地保存和恢复对象状态&#xff0c;以支持复杂的撤销操作和历史状态管理。 备忘录模式&#xff1a…...

js一些杂乱理解

js 的值类型和引用类型 引用类型:object,array,function值类型:诸如number,stringboolean,null,Undefined,Symbol js使用变量访问对象属性示例 var myDog "Hunter"; var dogs { Fido: "Mutt", Hunter: "Doberman", Snoopie: "Beagle&q…...

机器学习 之 线性回归算法

目录 线性回归&#xff1a;理解与应用 什么是线性回归&#xff1f; 一元线性回归 正态分布的重要性 多元线性回归 实例讲解 数据准备 数据分析 构建模型 训练模型 验证模型 应用模型 代码实现 线性回归&#xff1a;理解与应用 线性回归是一种广泛使用的统计方法&…...

ThreadLoad如何防止内存溢出

优质博文&#xff1a;IT-BLOG-CN 从 ThreadLocalMap看 ThreadLocal使用不当的内存泄漏问题 【1】基础概念 &#xff1a; 首先我们先看看ThreadLocalMap的类图&#xff0c;我们知道 ThreadLocal只是一个工具类&#xff0c;他为用户提供get、set、remove接口操作实际存放本地变…...

2024.8.19 学习记录 —— 作业

一、TCP机械臂测试 #include <myhead.h>#define SER_PORT 8888 // 与服务器保持一致 #define SER_IP "192.168.0.114" // 服务器ip地址int main(int argc, const char *argv[]) {// 创建文件描述符打开键盘文件int fd open("/dev/input/event1…...

Java 阿里云视频直播开发流程

首先来看一下直播效果 推流工具有很多种&#xff08;例如OBS、阿里云直播Demo推流、等等&#xff0c;我用的是芯象导播&#xff09;阿里播放器地址 一、直播基础服务概述 官方文档说明 二、直播域名配置需要两个域名&#xff08;推流域名、播流域名&#xff09; 官方文档说…...

SQLite 轻量级的嵌入式关系型数据库的替代软件

SQLite 是一个轻量级的嵌入式关系型数据库&#xff0c;由于其简单易用和跨平台的特性&#xff0c;被广泛应用于各种应用程序中。以下是一些可作为SQLite替代品的数据库软件或可视化管理工具&#xff1a; 1. **SQLiteStudio**&#xff1a;这是一个免费、开源的跨平台SQLite数据…...

Flutter-自适用高度PageView

需求 在 Flutter 中&#xff0c;PageView 是一个非常常用的组件&#xff0c;能够实现多个页面的滑动切换。然而&#xff0c;默认的 PageView 高度是固定的&#xff0c;这在展示不同高度的页面时&#xff0c;可能会导致不必要的空白或内容裁剪问题。为了使 PageView 能够根据每…...

群晖NAS本地搭建可远程交互的大型语言模型LLM聊天机器人

文章目录 前言1. 拉取相关的Docker镜像2. 运行Ollama 镜像3. 运行Chatbot Ollama镜像4. 本地访问5. 群晖安装Cpolar6. 配置公网地址7. 公网访问8. 固定公网地址 前言 本文主要分享如何在群晖NAS本地部署并运行一个基于大语言模型Llama 2的个人本地聊天机器人并结合内网穿透工具…...

TypeScript 构建工具之 webpack

在实际开发中&#xff0c;直接使用TypeScript 编译器的情况不多。 在项目中&#xff0c;需要使用构建工具对代码进行打包&#xff0c;不可能脱离项目使用TypeScript 编译器单独打包TypeScript 。 那如何将 webpack 和 TypeScript 进行集成&#xff1f; 参考文档&#xff1a; w…...

conda环境下在pycharm中调试scrapy项目

前提条件 已经创建好了conda环境已经安装好了scrapy框架项目初始化完成 编写一个爬虫脚本 import scrapyclass StackOverflowSpider(scrapy.Spider):name stackoverflowstart_urls [http://stackoverflow.com/questions?sortvotes]def parse(self, response):print("…...

contenteditable=“true“的标签限制字数的时候修改光标位置

contenteditable"true"的标签限制字数的时候修改光标位置 有时候input和textarea并不能完全满足ui需求&#xff0c;这个时候我们就用contenteditable"true"来将别的标签修改为可编辑状态&#xff0c;但当我们通过js修改了内容之后光标的位置就是一个问题&…...

51单片机-LED灯蜂鸣器数码管按键DS18B20温度传感器

LDE灯的相关程序 LED灯闪烁 LED流水灯 方法1 方法二&#xff1a; 因为P1口可以直接控制P1^0~P1^7的8个led灯&#xff0c;利用一个8位的二进制数字来进行控制即可。如果要点亮P1^0 只需要给P1口传递 1111 1110即可。 蜂鸣器的使用 什么是蜂鸣器&#xff1f; 蜂鸣器是一种一…...

笔记本一线品牌有哪些

笔记本电脑的一线品牌通常指的是在市场上具有较高市场份额、良好口碑、较强的技术实力和服务能力的品牌。根据目前的信息&#xff0c;笔记本电脑市场的一线品牌主要包括以下几个&#xff1a; 联想 (Lenovo)&#xff1a;联想在全球笔记本市场上的占有率较高&#xff0c;其产品线…...

mysql聚合函数和分组

我最近开了几个专栏&#xff0c;诚信互三&#xff01; > |||《算法专栏》&#xff1a;&#xff1a;刷题教程来自网站《代码随想录》。||| > |||《C专栏》&#xff1a;&#xff1a;记录我学习C的经历&#xff0c;看完你一定会有收获。||| > |||《Linux专栏》&#xff1…...

ubuntu20.04+RealSenseD455

ubuntu20.04安装驱动双目相机RealSenseD455 安装环境安装RealSense SDK 2.0ROS包安装启动Realsense摄像头存在的 bugD455标定安装环境 系统:Ubuntu20.04 ROS:Noetic 视觉传感器:Intel RealSense D455 安装RealSense SDK 2.0 该安装有两种方式,一个是用命令安装,另一个是…...

WAF绕过技巧

WAF绕过技巧 WAF&#xff08;Web Application Firewall&#xff09;是一种安全系统&#xff0c;旨在监控和控制网络流量&#xff0c;以防止攻击&#xff0c;如SQL 注入、跨站脚本&#xff08;XSS&#xff09;和拒绝服务&#xff08;DoS&#xff09;。 WAF 可以通过多种方式绕过…...

HarmonyOS应用三之组件生命周期和参数传递

目录&#xff1a; 1、生命周期的执行顺序2、页面数据传递3、图片的读取4、数据的备份和恢复5、轮播图6、页面布局图 1、生命周期的执行顺序 /** Copyright (c) 2023 Huawei Device Co., Ltd.* Licensed under the Apache License, Version 2.0 (the "License");* yo…...

css实现圆环展示百分比,根据值动态展示所占比例

代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...

加密通信 + 行为分析:运营商行业安全防御体系重构

在数字经济蓬勃发展的时代&#xff0c;运营商作为信息通信网络的核心枢纽&#xff0c;承载着海量用户数据与关键业务传输&#xff0c;其安全防御体系的可靠性直接关乎国家安全、社会稳定与企业发展。随着网络攻击手段的不断升级&#xff0c;传统安全防护体系逐渐暴露出局限性&a…...

数据结构第5章:树和二叉树完全指南(自整理详细图文笔记)

名人说&#xff1a;莫道桑榆晚&#xff0c;为霞尚满天。——刘禹锡&#xff08;刘梦得&#xff0c;诗豪&#xff09; 原创笔记&#xff1a;Code_流苏(CSDN)&#xff08;一个喜欢古诗词和编程的Coder&#x1f60a;&#xff09; 上一篇&#xff1a;《数据结构第4章 数组和广义表》…...

JDK 17 序列化是怎么回事

如何序列化&#xff1f;其实很简单&#xff0c;就是根据每个类型&#xff0c;用工厂类调用。逐个完成。 没什么漂亮的代码&#xff0c;只有有效、稳定的代码。 代码中调用toJson toJson 代码 mapper.writeValueAsString ObjectMapper DefaultSerializerProvider 一堆实…...

基于单片机的宠物屋智能系统设计与实现(论文+源码)

本设计基于单片机的宠物屋智能系统核心是实现对宠物生活环境及状态的智能管理。系统以单片机为中枢&#xff0c;连接红外测温传感器&#xff0c;可实时精准捕捉宠物体温变化&#xff0c;以便及时发现健康异常&#xff1b;水位检测传感器时刻监测饮用水余量&#xff0c;防止宠物…...