当前位置： 首页 > 编程日记 > 正文

递归/回溯：Generate Parentheses生成合法括号

编程日记 2024-04-20 04:00:00

已知n组括号，开发一个程序，生成这n组括号所有的合法的组合可能。 例如:n = 3
结果为: ["((()))", “(()())”, “(())()”, “()(())”, “()()()”]

首先思考如何生成所有的括号组合的可能性，即例如2组括号，总共4个符号组合的可能型，那么每个位置就有两种括号的可能性，要么左括号，要么右括号，此时可以写出如代码：

void generate(string item, int n, std::vector<string> &result) {if (item.size() == 2 * n) {result.push_back(item);return ;}generate(item + "(", n , result);generate(item + ")", n , result);
} std::vector<string> generate_parenthesed(int n) {std::vector<string> result;generate("", n, result);return result;
}

测试如上代码,可以看到2组括号总共可能有16中组合的可能性:

2
((((
((()
(()(
(())
()((
()()
())(
()))
)(((
)(()
)()(
)())
))((
))()
)))(
))))

但是根据输出结果，我们显然能够看出来很多结果并不符合 合法括号的要求，那么什么是合法的括号呢？或者说如何生成一个合法的括号呢？

根据括号的规律：

  1. 初始括号一定是左括号
  2. 括号集中左括号的数目一定和右括号的数目相等
  3. 添加括号的过程中如果左括号的数目大于右括号，则才能够添加右括号，否则不能添加右括号

基于以上过程，实现如下:

/*left和right代表剩余括号数，left代表还剩下多少个左括号未添加，right代表还剩下多少个右括号未添加*/
void generate_leagal(string item, int left, int right, std::vector<string> &result) {if(left == 0 && right == 0) {result.push_back(item);return;}if(left > 0) { //当还有剩余的左括号未添加，则添加左括号generate_leagal(item + "(", left - 1, right, result);}if (left < right) { //当已添加的左括号的数目大于右括号，则才能够添加右括号generate_leagal(item + ")", left, right - 1, result);}
}std::vector<string> generate_parenthesed(int n) {std::vector<string> result;generate_leagal("", n, n, result);return result;
}

测试代码如下:

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>/*
已知n组括号，开发一个程序，生成这n组括号所有的合法的组合可能。 例如:n = 3
结果为: ["((()))", "(()())", "(())()", "()(())", "()()()"]
*/using namespace std;void generate_leagal(string item, int left, int right, std::vector<string> &result) {if(left == 0 && right == 0) {result.push_back(item);return;}if(left > 0) {generate_leagal(item + "(", left - 1, right, result);}if (left < right) {generate_leagal(item + ")", left, right - 1, result);}
}std::vector<string> generate_parenthesed(int n) {std::vector<string> result;generate_leagal("", n, n, result);return result;
}int main(int argc, char const *argv[])
{int n;std::vector<string> result;cin >> n;result = generate_parenthesed(n);for (int i = 0;i < result.size(); ++i) {cout << result[i] << endl;}return 0;
}

输出如下:

#输入
4
#输出
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()

https://www.dkcj.cn/info/4942.html

相关文章：

利用“哨兵”“实现双链表

利用“哨兵”“实现双链表 下面的代码用一个”哨兵“实现双链表&#xff0c;感觉很简洁&#xff0c;中间也有点绕&#xff0c;暂时实现&#xff0c;供学习之用 static Node list_handle {&list_handle,&list_handle, };bool addNode(Node* node) {if (node NULL){re…

编程日记2024/04/20 03:30:00

suse linux显示乱码,open suse11.4中文乱码问题

winland0704 于 2011-04-07 00:56:10发表:不是乱码&#xff0c;而是字符编码标准不一样。windows的文本使用GBK&#xff0c;国标码。Linux使用Unicode编码。解决参看&#xff1a;hi.baidu.com/winland0704/blog/item/c58008512cc843c9b645aef1.html四、其他的一些问题3、文本编…

编程日记2024/04/20 03:00:00

软件破解系列之OD中断方法

OD中断方法浅探 Ollydbg是一个新的32位的汇编层调试软件。适应于windows98、me、2000、xp和2003操作系统。由于他具有图形窗口界面&#xff0c;所以操作方便、直观&#xff0c;是cracker的好工具。 由于Ollydbg没有了TRW2000的万能断点&#xff0c;所以许多的新手感觉到用Ollyd…

编程日记2024/04/20 02:30:00

MongoDB系列：二、MongoDB常用操作练习

最近在自学MongoDB&#xff0c;在此记录一下&#xff0c;当做学习笔记了&#xff08;不断更新中&#xff09;&#xff01;&#xff01; 一、背景 MongoDB 是一个基于分布式文件存储的数据库。由 C 语言编写。旨在为 WEB 应用提供可扩展的高性能数据存储解决方案。它是一个介于关…

编程日记2024/04/20 02:00:00

递归/回溯：八皇后问题N-Queens

N皇后问题是计算机科学中最为经典的问题之一&#xff0c;该问题可追溯到1848年&#xff0c;由国 际西洋棋棋手马克斯贝瑟尔于提出了8皇后问题。 将N个皇后放摆放在N*N的棋盘中&#xff0c;互相不可攻击&#xff0c;有多少种摆放方式&#xff0c;每种摆 放方式具体是怎样的? 8…

编程日记2024/04/20 01:30:00

KS103超声波测距模块

max232&#xff1a;电平转换芯片&#xff0c;将电脑的RS-232标准串口&#xff08;高12V&#xff0c;低-12V&#xff09;转换为&#xff08;高5V&#xff0c;低0V&#xff09;。 电脑串口&#xff08;RS -232&#xff09; > 单片机串口&#xff08;TTL串口&#xff09; SIPEX…

编程日记2024/04/20 01:00:00

linux 硬盘操作,linux常用disk磁盘操作命令

#按照目录大小排序战士最前面15个目录或者文件du -xB M --max-depth2 /var | sort -rn | head -n 15#列出当前所有子目录的文件大小du -h --max-depth1#列出当前文件或者目录最大的10个du -s * | sort -n | tail#按照目录大小从大到小排序du -b --max-depth 1 | sort -nr | per…

编程日记2024/04/20 00:30:00

在Spring中采用声明式方法对Hibernate和JDBC进行统一的事务配置（AOP）

<?xml version"1.0" encoding"UTF-8"?><beans xmlns"http://www.springframework.org/schema/beans" xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance" xmlns:aop"http://www.springframework.…

编程日记2024/04/20 00:00:00

Leetcode 213.大家劫舍II

打家劫舍II 你是一个专业的小偷&#xff0c;计划偷窃沿街的房屋&#xff0c;每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈&#xff0c;这意味着第一个房屋和最后一个房屋是紧挨着的。同时&#xff0c;相邻的房屋装有相互连通的防盗系统&#xff0c;如果两间相邻的房…

编程日记2024/04/19 23:30:00

替代Druid，HakariCP 为什么这么快？

这次源码探究，真的感觉看到了无数个小细节，无数个小优化，积少成多。平时开发过程中，一些小的细节也一定要“扣”。

编程日记2024/04/19 23:00:02

递归/分治：归并排序

前言 分治算法: 将一个规模为N的问题分解为K个规模较小的子问题&#xff0c;这些子问题相互独立且与原问题性质相同。求出 子问题的解后进行合并&#xff0c;就可得到原问题的解。 步骤如下: 分解&#xff0c;将要解决的问题划分成若 干规模较小的同类问题;求解&#xff0c;…

编程日记2024/04/19 23:00:00

Java中volatile 的使用场景有哪些？

volatile是一种轻量级的同步机制，它能保证共享变量的可见性，同时禁止重排序保证了操作的有序性，但是它无法保证原子性。所以使用volatilevolatile。

编程日记2024/04/19 22:30:05

JDK22 正式发布了 ！

Java 22 除了推出了新的增强功能和特性，也获得 Java Management Service (JMS) 的支持，这是一项新的 Oracle 云基础设施远程软件服务(Oracle Cloud Infrastructure, OCI) 原生服务，提供统一的控制台和仪表盘，帮助企业管理本地或云端的 Java 运行时和应用。使包含运行时计算值的字符串更容易表达，简化 Java 程序的开发工作，同时提高将用户提供的值编写成字符串，并将字符串传递给其他系统的程序的安全性。支持开发人员自由地表达构造器的行为。

编程日记2024/04/19 22:30:05

Jackson 用起来！

你可以创建自定义序列化器和反序列化器以自定义特定字段或类的序列化和反序列化行为。为此，请创建一个实现或接口的类，并在需要自定义的字段或类上使用和注解。@Override// ...其他代码...优势性能优异：Jackson在序列化和反序列化过程中表现出优秀的性能，通常比其他Java JSON库更快。灵活性：通过注解、自定义序列化器/反序列化器等功能，Jackson提供了丰富的配置选项，允许你根据需求灵活地处理JSON数据。易于使用：Jackson的API设计简洁明了，易于学习和使用。

编程日记2024/04/19 22:30:05

Swift中的问号?和感叹号!

Swift语言使用var定义变量&#xff0c;但和别的语言不同&#xff0c;Swift里不会自动给变量赋初始值&#xff0c;也就是说变量不会有默认值&#xff0c;所以要求使用变量之前必须要对其初始化。如果在使用变量之前不进行初始化就会报错&#xff1a; var stringValue : String …

编程日记2024/04/19 22:30:00

拜托！别再滥用 ! = null 判空了！！

另外，也许受此习惯影响，他们总潜意识地认为，所有的返回都是不可信任的，为了保护自己程序，就加了大量的判空。如果你养成习惯，都是这样写代码（返回空collections而不返回null)，你调用自己写的方法时，就能大胆地忽略判空）这种情况下，null是个”看上去“合理的值，例如，我查询数据库，某个查询条件下，就是没有对应值，此时null算是表达了“空”的概念。最终，项目中会存在大量判空代码，多么丑陋繁冗！，而不要返回null，这样调用侧就能大胆地处理这个返回，例如调用侧拿到返回后，可以直接。

编程日记2024/04/19 22:00:02

ffmpeg java linux水印,Linux环境用FFmpeg给视频加水印详细步骤

FFmpeg给视频添加水印&#xff0c;根据官方文档的介绍可以知道FFmpeg在编译安装的时候还需要加 –enable-libfreetype、–enable-libfontconfig、 --enable-libfribidi 这几个参数&#xff0c;而这几个组件又需要从外面编译安装&#xff0c;我看很多博主直接用FFmpeg命令加水印…

编程日记2024/04/19 22:00:00

red hat DHCP服务器配置

[ 基本操作 ] rpm –q dhcp / rpm -ql grep dhcp [ 查询DHCP ] yum –y install dhcp dhcp -devel service dhcpd start [ 启动 ] service dhcpd status [ 查看DHCP状态 ] chkconfig – level 3 5 dhcpd on [ 改变启动级别为3 5 自动启动服务 ] service ne…

编程日记2024/04/19 21:30:00

axios解决调用后端接口跨域问题

vue-cli通过是本地代理的方式解决接口跨域问题的。但是在vue-cli的默认项目配置中这个代理是没有配置的&#xff0c;如果现在项目中使用&#xff0c;必须手动配置config/index.js文件 ... proxyTable: {/api: { //将www.exaple.com印射为/apistarget: https://www.example.c…

编程日记2024/04/19 21:00:00

递归/归并：count of smaller numbers求逆序数

已知数组nums&#xff0c;求新数组count&#xff0c;count[i]代表了在nums[i]右侧且比 nums[i]小的元素个数。 例如: nums [5, 2, 6, 1], count [2, 1, 1, 0]; nums [6, 6, 6, 1, 1, 1], count [3, 3, 3, 0, 0, 0]; nums [5, -7, 9, 1, 3, 5, -2, 1], count [5, 0, 5, 1…

编程日记2024/04/19 20:30:00

远程计划任务管理

有时你需要远程管理或运行一批机器&#xff0c;但是按要求你没有权限或者不能安装客户端&#xff0c;下面的批处理可能帮上你的忙&#xff0c;将下方代码保存为批处理&#xff0c;并创建Clients.txt&#xff0c;存放的是以回车分隔的IP echo off setlocal enabledelayedexpansi…

编程日记2024/04/19 20:00:00

linux shell for 循环变量,shell for循环总结

1 shell for循环语法for 变量 in 列表docommand1command2...commandNdone1.1 读取列表中的值#!/bin/bashfor test in apple boy cat dogdoecho The next state is $testdone结果&#xff1a;The next state is appleThe next state is boyThe next state is catThe next state …

编程日记2024/04/19 19:30:00

自定义堆栈（回文检测）

using System; using System.Collections;namespace CStack {class Program{static void Main(string[] args){CStack alist new CStack();string ch;string word "上海自来水来自海上";bool isPalindrome true;for (int x 0; x < word.Length; x){alist.Push…

编程日记2024/04/19 19:00:00

二叉树(C++)：创建，前中后序遍历（递归+非递归），获取叶子节点个数，获取树的高度

文章目录前言创建二叉树先序遍历中序遍历后序遍历获取叶子节点个数获取树的高度测试代码前言 现有如下二叉树: 关于二叉树的相关操作&#xff0c;我们能够发现二叉树从根节点到子节点&#xff0c;以及每个中间节点基本都能够拆分为若干个子节点的操作&#xff0c;且每个子节点…

编程日记2024/04/19 18:30:00

6月11号=》121页-125页

6.1　　样式单概述 W3C已经给出了两种样式单语言的推荐标准&#xff0c;一种是级联样式单CSS(Cascading Style Sheets)&#xff0c; 另一种是可扩展样式单语言XSL(eXtensible Stylesheet Language)。 6.1.1　　CSS CSS主要提供如下两个功能&#xff1a; 1&#xff1a;对页面的字…

编程日记2024/04/19 18:00:00

linux cp sync,通过SSH使用Rsync传输文件，复制和同步文件及目录

在本文中&#xff0c;我们将解释如何通过SSH使用rsync复制文件。当涉及在网络上的系统之间传输文件时&#xff0c;Linux和Unix用户可以使用许多工具&#xff0c;最流行的数据传输协议是SSH和FTP&#xff0c;虽然FTP很受欢迎&#xff0c;但总是喜欢使用SSH&#xff0c;因为它是传…

编程日记2024/04/19 17:30:00

【Java笔记】C++与Java的对比

接口&#xff1a; C可以多重继承&#xff0c;而Java不可以。但是Java里一个类可以声明实现多个接口。

编程日记2024/04/19 17:00:00

cf792b循环链表

头尾链接一下就好&#xff0c; /* 1 2 3 4 5 6 7:4 5 6 7 1 2 3:2 3 5 6 7 1:5 6 7 1 3:6 7 1 3:1 3 7 */ #include<bits/stdc.h> using namespace std; int main(){int n,k,q[200],nxt[200],p,pre,tot;scanf("%d%d",&n,&k);for(int i1;i&…

编程日记2024/04/19 16:30:00

二叉树：路径之和 Path Sum

给定一个二叉树与整数sum&#xff0c;找出所有从根节点到叶结点的路径&#xff0c;这些路 径上的节点值累加和为sum 即创建一个二叉树&#xff0c;要求二叉树中有一个路径从根节点到叶节点到路径加起来代表到和为 给定的sum 如下二叉树 给定路径之和为18&#xff0c;则需要输…

编程日记2024/04/19 16:00:00

从零开始编写自己的C#框架（16）——Web层后端父类

从零开始编写自己的C#框架&#xff08;16&#xff09;——Web层后端父类 原文:从零开始编写自己的C#框架&#xff08;16&#xff09;——Web层后端父类 本章节讲述的各个类是后端系统的核心之一&#xff0c;涉及到系统安全验证、操作日志记录、页面与按键权限控制、后端页面功能…

编程日记2024/04/19 15:30:00