首页 > 其他分享 >【LeetCode Hot 100】22. 括号生成

【LeetCode Hot 100】22. 括号生成

时间:2024-09-29 13:13:53浏览次数:9  
标签:return 22 temp back 括号 Hot close 100 open

题目描述

要求生成所有“合法”的括号字符串,就首先需要弄清楚括号字符串的合法性定义,也就是说如果我们现在有一个由小括号组成的字符串,该如何判断其是否符合要求。此前做过判断括号串是否合法的题目,那道题目中一般在遍历过程中维护一个栈,因为每个后括号都需要在已经遍历的子串中找到自己对应的前括号。这个题目中的合法性判断应该稍微简单一些,因为本题中只有小括号一种括号,因此我们可以将使用栈存储前面遍历的元素,简化为使用一个整型变量维护前括号的数量。这样一来,实际实现过程可以使用open存储前括号的数量,close存储后括号的数量,遍历结束时只有open == close时字符串才合法,此外,整个遍历过程中open >= close都需要成立,毕竟后括号必须有且仅有一个对应的前括号。

    bool check(string& s, int n) {
        int open = 0, close = 0;
        for (char c : s) {
            switch (c) {
            case '(':
                open++; break;
            case ')':
                close++; break;
            default:
                return false;
            }
            if (open > n) return false;
            if (close > open) return false;
        }
        return true;
    }

只关心openclose的大小关系,就可以将两个变量简化为一个变量balance,可以理解成前后括号的数量是否平衡。

    bool check(string& temp) {
        int balance = 0;
        for (const char& c : temp) {
            if (c == '(') balance++;
            else balance--;
            if (balance < 0) return false;
        }
        if (balance == 0) return true;
        else return false;
    }

明确了如何判断括号字符串的合法性,就可以想用回溯算法枚举所有可能的括号字符串,将所有合法的结果存入结果数组中返回。

    void backtrack(vector<string>& result, string& s, int idx, int n) {
        if (idx >= 2 * n) {
            if (check(s, n)) result.push_back(s);
            return;
        }
        s.push_back('(');
        backtrack(result, s, idx + 1, n);
        s.pop_back();
        s.push_back(')');
        backtrack(result, s, idx + 1, n);
        s.pop_back();
    }

    vector<string> generateParenthesis(int n) {
        vector<string> result;
        string s;
        backtrack(result, s, 0, n);
        return result;
    }

但是其实没有必要将整个串枚举完,而是可以在枚举过程中判断当前子串的合法性,即前括号与后括号的数量关系,因为显然如果前面一部分子串已经不合法,再继续深入下去的整个串一定不可能合法。这实际上也是一种对回溯算法的剪枝。

class Solution {
public:
    void backtrack(vector<string>& res, string& temp, int open, int close, int n) {
        if (temp.length() == n * 2) {
            res.push_back(temp);
            return;
        }
        if (open < n) {
            temp.push_back('(');
            backtrack(res, temp, open + 1, close, n);
            temp.pop_back();
        }
        if (close < open) {
            temp.push_back(')');
            backtrack(res, temp, open, close + 1, n);
            temp.pop_back();
        }
    }

    vector<string> generateParenthesis(int n) {
        vector<string> res;
        string temp;
        backtrack(res, temp, 0, 0, n);
        return res;
    }
};

顺带一提,这个题目需要对字符串进行回溯,C++中的字符串实际上就是一个字符向量数组,但是Java中需要使用StringBuilder或者StringBuffer提供的接口。根据力扣的提测结果,前者更快些(但是缺点在于线程不安全)。

标签:return,22,temp,back,括号,Hot,close,100,open
From: https://www.cnblogs.com/louistang0524/p/18439504

相关文章

  • 南沙C++信奥老师解一本通题 1221:分成互质组
    ​ 【题目描述】给定n个正整数,将它们分组,使得每组中任意两个数互质。至少要分成多少个组?【输入】第一行是一个正整数n。1≤n≤10。第二行是n个不大于10000的正整数。【输出】一个正整数,即最少需要的组数。【输入样例】6142033117143175【输出样例】3......
  • [米联客-XILINX-H3_CZ08_7100] FPGA_SDK入门篇连载-08PS 私有看门狗定时器实验
    软件版本:VIVADO2021.1操作系统:WIN1064bit硬件平台:适用XILINXA7/K7/Z7/ZU/KU系列FPGA实验平台:米联客-MLK-H3-CZ08-7100开发板板卡获取平台:https://milianke.tmall.com/登录“米联客”FPGA社区http://www.uisrc.com视频课程、答疑解惑!目录1概述2系统框图3中断资......
  • [米联客-XILINX-H3_CZ08_7100] FPGA_SDK入门篇连载-18 PL AXI-GPIO实验
    软件版本:VIVADO2021.1操作系统:WIN1064bit硬件平台:适用XILINXA7/K7/Z7/ZU/KU系列FPGA实验平台:米联客-MLK-H3-CZ08-7100开发板板卡获取平台:https://milianke.tmall.com/登录“米联客”FPGA社区http://www.uisrc.com视频课程、答疑解惑!目录1概述2系统框图3AXI-GPI......
  • [米联客-XILINX-H3_CZ08_7100] FPGA_SDK入门篇连载-26PL 自定义 AXI-Lite-频率计
    软件版本:VIVADO2021.1操作系统:WIN1064bit硬件平台:适用XILINXA7/K7/Z7/ZU/KU系列FPGA实验平台:米联客-MLK-H3-CZ08-7100开发板板卡获取平台:https://milianke.tmall.com/登录“米联客”FPGA社区http://www.uisrc.com视频课程、答疑解惑!目录1概述2系统框图3等精度......
  • [米联客-XILINX-H3_CZ08_7100] FPGA_SDK入门篇连载-23PL 自定义 AXI-Lite 协议 IP
    软件版本:VIVADO2021.1操作系统:WIN1064bit硬件平台:适用XILINXA7/K7/Z7/ZU/KU系列FPGA实验平台:米联客-MLK-H3-CZ08-7100开发板板卡获取平台:https://milianke.tmall.com/登录“米联客”FPGA社区http://www.uisrc.com视频课程、答疑解惑!目录1概述2系统框图3AXI总线......
  • 公共数据开放多期DID(2000-2022年)
    公共数据开放是指政府或公共机构将所拥有的数据资源向社会公众开放,以供免费或低成本使用。本研究旨在通过多期DID分析方法,评估公共数据开放政策对不同地区经济发展、社会创新和政府透明度等方面的影响。2000年-2022年公共数据开放多期DID(大数据).zip资源-CSDN文库字段:行政区......
  • 基于VU9P的4路 100G光纤 6U VPX板卡
    基于VU9P的4路100G光纤6UVPX板卡一款VPX的光纤接入卡,板卡的前面板提供4路100GQSFP28+接口(16路GTY接口),后出线接入到VPX背板,提供28路GTY接口。板卡的P1提供16lanePCI-E3.0接口,可运行一路16X的接口协议,板卡的P2提供两组PCI-E3.08X接口,可提供两组8X的接口协议。板上提供......
  • 20221409童诗嘉《密码系统设计》第四周
    20221409童诗嘉《密码系统设计》第四周AI对学习内容的总结要求让kimi阅读学习内容并进行总结,教材内容可以使用微信读书或者云班课电子教材HeadFirstC嗨翻C语言第五章:Structs,Unions,andBitfields:Rollingyourownstructures1、编译过程与多源文件管理:编译流程:......
  • 题解:P9947 [USACO20JAN] Photoshoot B
    P9947[USACO20JAN]PhotoshootB题解纯模拟!在\(a_{1}\)算出来之后,我们就可以通过\(b\)数组可以求出以后\(a\)数组的所有元素。要判断是否为排列,我们可以使用一个\(vis\)做桶,为了保证字典序最小,我们可以从\(1\)开始枚举,每次枚举前要清空一下\(vis\)数组,最后使用......
  • 华为OD机试2024年E卷-转骰子[200分]( Java | Python3 | C++ | C语言 | JsNode | Go )实
    题目描述骰子是一个立方体,每个面一个数字,初始为左1,右2,前3(观察者方向),后4,上5,下6,用123456表示这个状态,放置在平面上,可以向左翻转(用L表示向左翻转1次),可以向右翻转(用R表示向右翻转1次),可以向前翻转(用F表示向前翻转1次),可以向后翻转(用B表示向后翻转1次),可以逆时针旋转(......