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

中国设计网站导航高德地图国际版

中国设计网站导航,高德地图国际版,百度网站公司信息推广怎么做的,wordpress添加3d地图吗优质博文:IT-BLOG-CN 一、题目 数字n代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。 示例 1: 输入:n 3 输出:["((()))","(()())","(())(…

优质博文:IT-BLOG-CN

在这里插入图片描述

一、题目

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

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

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

1 <= n <= 8

二、代码

【1】暴力法: 我们可以生成所有2^2n()字符构成的序列,然后我们检查每一个是否有效即可。为了生成所有序列,我们可以使用递归。长度为n的序列就是在长度为n−1的序列前加一个()。为了检查序列是否有效,我们遍历这个序列,并使用一个变量balance表示左括号的数量减去右括号的数量。如果在遍历过程中balance的值小于零,或者结束时balance的值不为零,那么该序列就是无效的,否则它是有效的。

class Solution {public List<String> generateParenthesis(int n) {List<String> combinations = new ArrayList<String>();generateAll(new char[2 * n], 0, combinations);return combinations;}public void generateAll(char[] current, int pos, List<String> result) {if (pos == current.length) {if (valid(current)) {result.add(new String(current));}} else {current[pos] = '(';generateAll(current, pos + 1, result);current[pos] = ')';generateAll(current, pos + 1, result);}}public boolean valid(char[] current) {int balance = 0;for (char c: current) {if (c == '(') {++balance;} else {--balance;}if (balance < 0) {return false;}}return balance == 0;}
}

时间复杂度: O(2^2n * n),对于2^2n个序列中的每一个,我们用于建立和验证该序列的复杂度为O(n)
空间复杂度: O(n),除了答案数组之外,我们所需要的空间取决于递归栈的深度,每一层递归函数需要O(1)的空间,最多递归2n层,因此空间复杂度为O(n)

【2】回溯法: 方法一还有改进的余地:我们可以只在序列仍然保持有效时才添加(),而不是像 方法一 那样每次添加。我们可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点,如果左括号数量不大于n,我们可以放一个左括号。如果右括号数量小于左括号的数量,我们可以放一个右括号。

class Solution {public List<String> generateParenthesis(int n) {List<String> ans = new ArrayList<String>();backtrack(ans, new StringBuilder(), 0, 0, n);return ans;}public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {if (cur.length() == max * 2) {ans.add(cur.toString());return;}if (open < max) {cur.append('(');backtrack(ans, cur, open + 1, close, max);cur.deleteCharAt(cur.length() - 1);}if (close < open) {cur.append(')');backtrack(ans, cur, open, close + 1, max);cur.deleteCharAt(cur.length() - 1);}}
}

我们的复杂度分析依赖于理解generateParenthesis(n)中有多少个元素。这个分析超出了本文的范畴,但事实证明这是第n个卡特兰数1/(n+1)(2n/n),这是由4n/n渐近界定的。
时间复杂度: O(4n/n),在回溯过程中,每个答案需要O(n)的时间复制到答案数组中。
空间复杂度: O(n),除了答案数组之外,我们所需要的空间取决于递归栈的深度,每一层递归函数需要O(1)的空间,最多递归2n层,因此空间复杂度为O(n)

【3】按括号序列的长度递归: 任何一个括号序列都一定是由(开头,并且第一个(一定有一个唯一与之对应的)。这样一来,每一个括号序列可以用(a)b来表示,其中ab分别是一个合法的括号序列(可以为空)。那么,要生成所有长度为2n的括号序列,我们定义一个函数generate(n)来返回所有可能的括号序列。那么在函数generate(n)的过程中:
1、我们需要枚举与第一个(对应的)的位置2i+1
2、递归调用generate(i)即可计算a的所有可能性;
3、递归调用generate(n−i−1)即可计算b的所有可能性;
4、遍历ab的所有可能性并拼接,即可得到所有长度为2n的括号序列。
为了节省计算时间,我们在每次generate(i)函数返回之前,把返回值存储起来,下次再调用generate(i)时可以直接返回,不需要再递归计算。

class Solution {ArrayList[] cache = new ArrayList[100];public List<String> generate(int n) {if (cache[n] != null) {return cache[n];}ArrayList<String> ans = new ArrayList<String>();if (n == 0) {ans.add("");} else {for (int c = 0; c < n; ++c) {for (String left: generate(c)) {for (String right: generate(n - 1 - c)) {ans.add("(" + left + ")" + right);}}}}cache[n] = ans;return ans;}public List<String> generateParenthesis(int n) {return generate(n);}
}

时间复杂度: O(4^n/n),该分析与方法二类似。
空间复杂度: O(4^n/n),此方法除答案数组外,中间过程中会存储与答案数组同样数量级的临时数组,是我们所需要的空间复杂度。

http://www.yayakq.cn/news/995371/

相关文章:

  • 网站模板制作工具电子商城网站建设价格
  • 网站设计制作代码管理系统的设计与实现
  • 建设一个营销网站有哪些步骤传奇世界网页版星装
  • 做公司网站怎么做手机版中学网站建设方案计划
  • 网站策划建设阶段的推广网做英文网站
  • 佛山企业网站建设渠道广告代理
  • 查找网站备案信息php做网站技术方案
  • 商洛免费做网站公司wordpress 子页面 404
  • 个人网站界面设计图片html登录页面设计代码
  • 做个人网站要注意什么海口网站建设在线
  • 吃的网站要怎么做简单的网站设计开发
  • 没网站域名可以做备案吗买网站服务器要多少钱
  • 安卓手机做网站网站建设手机端pc端分开
  • 企业网站公司单位有哪些电商自学网
  • wordpress 引号 主题 remove_filter优化网站速度的要点
  • c 网站建设教程视频教程中国兰州网首页
  • 青岛建设企业网站哪个网站可以做c语言的题
  • 营销型网站关键词多少为好北京城乡建设官方网站
  • 景县做个油管的网站怎么做上海网架公司
  • 外贸企业网站制作fqapps com网站怎么做
  • 邯郸网站建设怎么做服务号wordpress
  • 网站图片计时器怎么做标准的软件开发流程
  • 邯郸网站制作找谁wordpress 增加浮动条
  • 重庆做网站 外包公司有哪些音乐门户网站模板
  • 网站流量100g重庆网站seo好不好
  • phpnow搭建本地网站西安手机商城网站建设
  • 邢台当地网站建设小程序网站备案
  • 郑州网站建设专注乐云seo福田专业网站建设公司
  • 长春网站建设net企查查企业信息查询官网登录入口
  • 做网站需要的条件动易学校网站管理系统