力扣热题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 中移除。
- 从当前正在考虑元素,到第 2 * n 个元素为止,枚举出所有可选的元素。对于每一个可选元素:
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 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。 示例 1: 输入:n 3 输出:[“((()))”,“(()())”,“(())()…...
【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)
本文深入探讨了备忘录模式,从定义、组成、实现到使用场景、优缺点、与其他模式的比较,以及最佳实践和替代方案,全面解析了如何在软件开发中有效地保存和恢复对象状态,以支持复杂的撤销操作和历史状态管理。 备忘录模式:…...

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

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

ThreadLoad如何防止内存溢出
优质博文:IT-BLOG-CN 从 ThreadLocalMap看 ThreadLocal使用不当的内存泄漏问题 【1】基础概念 : 首先我们先看看ThreadLocalMap的类图,我们知道 ThreadLocal只是一个工具类,他为用户提供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 阿里云视频直播开发流程
首先来看一下直播效果 推流工具有很多种(例如OBS、阿里云直播Demo推流、等等,我用的是芯象导播)阿里播放器地址 一、直播基础服务概述 官方文档说明 二、直播域名配置需要两个域名(推流域名、播流域名) 官方文档说…...
SQLite 轻量级的嵌入式关系型数据库的替代软件
SQLite 是一个轻量级的嵌入式关系型数据库,由于其简单易用和跨平台的特性,被广泛应用于各种应用程序中。以下是一些可作为SQLite替代品的数据库软件或可视化管理工具: 1. **SQLiteStudio**:这是一个免费、开源的跨平台SQLite数据…...

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

群晖NAS本地搭建可远程交互的大型语言模型LLM聊天机器人
文章目录 前言1. 拉取相关的Docker镜像2. 运行Ollama 镜像3. 运行Chatbot Ollama镜像4. 本地访问5. 群晖安装Cpolar6. 配置公网地址7. 公网访问8. 固定公网地址 前言 本文主要分享如何在群晖NAS本地部署并运行一个基于大语言模型Llama 2的个人本地聊天机器人并结合内网穿透工具…...
TypeScript 构建工具之 webpack
在实际开发中,直接使用TypeScript 编译器的情况不多。 在项目中,需要使用构建工具对代码进行打包,不可能脱离项目使用TypeScript 编译器单独打包TypeScript 。 那如何将 webpack 和 TypeScript 进行集成? 参考文档: 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需求,这个时候我们就用contenteditable"true"来将别的标签修改为可编辑状态,但当我们通过js修改了内容之后光标的位置就是一个问题&…...

51单片机-LED灯蜂鸣器数码管按键DS18B20温度传感器
LDE灯的相关程序 LED灯闪烁 LED流水灯 方法1 方法二: 因为P1口可以直接控制P1^0~P1^7的8个led灯,利用一个8位的二进制数字来进行控制即可。如果要点亮P1^0 只需要给P1口传递 1111 1110即可。 蜂鸣器的使用 什么是蜂鸣器? 蜂鸣器是一种一…...
笔记本一线品牌有哪些
笔记本电脑的一线品牌通常指的是在市场上具有较高市场份额、良好口碑、较强的技术实力和服务能力的品牌。根据目前的信息,笔记本电脑市场的一线品牌主要包括以下几个: 联想 (Lenovo):联想在全球笔记本市场上的占有率较高,其产品线…...

mysql聚合函数和分组
我最近开了几个专栏,诚信互三! > |||《算法专栏》::刷题教程来自网站《代码随想录》。||| > |||《C专栏》::记录我学习C的经历,看完你一定会有收获。||| > |||《Linux专栏》࿱…...
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(Web Application Firewall)是一种安全系统,旨在监控和控制网络流量,以防止攻击,如SQL 注入、跨站脚本(XSS)和拒绝服务(DoS)。 WAF 可以通过多种方式绕过…...

HarmonyOS应用三之组件生命周期和参数传递
目录: 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…...

铭豹扩展坞 USB转网口 突然无法识别解决方法
当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地
借阿里云中企出海大会的东风,以**「云启出海,智联未来|打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办,现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

UDP(Echoserver)
网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法:netstat [选项] 功能:查看网络状态 常用选项: n 拒绝显示别名&#…...

Psychopy音频的使用
Psychopy音频的使用 本文主要解决以下问题: 指定音频引擎与设备;播放音频文件 本文所使用的环境: Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...
数据库分批入库
今天在工作中,遇到一个问题,就是分批查询的时候,由于批次过大导致出现了一些问题,一下是问题描述和解决方案: 示例: // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...
rnn判断string中第一次出现a的下标
# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...
CSS设置元素的宽度根据其内容自动调整
width: fit-content 是 CSS 中的一个属性值,用于设置元素的宽度根据其内容自动调整,确保宽度刚好容纳内容而不会超出。 效果对比 默认情况(width: auto): 块级元素(如 <div>)会占满父容器…...

Docker 本地安装 mysql 数据库
Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker ;并安装。 基础操作不再赘述。 打开 macOS 终端,开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...

华为OD机试-最短木板长度-二分法(A卷,100分)
此题是一个最大化最小值的典型例题, 因为搜索范围是有界的,上界最大木板长度补充的全部木料长度,下界最小木板长度; 即left0,right10^6; 我们可以设置一个候选值x(mid),将木板的长度全部都补充到x,如果成功…...

永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器
一、原理介绍 传统滑模观测器采用如下结构: 传统SMO中LPF会带来相位延迟和幅值衰减,并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF),可以去除高次谐波,并且不用相位补偿就可以获得一个误差较小的转子位…...