括号生成-LeetCode22

栏目: 编程工具 · 发布时间: 5年前

内容简介:想刷刷leetcode锻炼写自己写代码的能力,关于写代码,我觉得它不仅仅是写代码,而是写你的想法。为什么有的人会写成一坨,而有的人代码工整,美感,这个一方面是一个人写之前是否有思考清楚,另外一方面是写代码的习惯了。代码只是表达思想的一种首先想到的是,每一个位置都有两种可能性:2^6 = 64。

想刷刷leetcode锻炼写自己写代码的能力,关于写代码,我觉得它不仅仅是写代码,而是写你的想法。为什么有的人会写成一坨,而有的人代码工整,美感,这个一方面是一个人写之前是否有思考清楚,另外一方面是写代码的习惯了。

代码只是表达思想的一种

题目

给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且 有效的 括号组合。

例如,给出 n = 3,生成结果为:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]
复制代码

解题

首先想到的是,每一个位置都有两种可能性:2^6 = 64。

  • 有一些很明显就错误的,比如:"((( ((("
    • 排除显而易见错误的,即左括号与右括号数量不等的
  • 有错误不是那么明显看出来的,比如:"))) (((" , "()) (()"
    • 开头是右括号的,直接去掉,这个其实代表右括号已经出现的数量大于左括号出现的数量

正确的方案是,首先要放入左括号"(",后续要有一个与之对应的括号,同时在任何位置,有括号")"的数量不能大于"("的数量,否则,"())" 就是错误的。

代码

  1. 首先定义一个方法,要知道当前左括号与有括号的数量,并且知道当前的字符串
/**
     *
     * @param left 代表当前已经出现的左括号数量
     * @param right 代表当前已经出现的右括号数量
     * @param n 代表生成括号的对数
     * @param s 代表当前的字符串,可能还未处理完
     * @param res 保存所有括号字符串的列表
     */
     private void generateParenthesis(int left, int right, int n, String s,List<String> res) {
         
     }
复制代码
  1. 目前比较喜欢的debug方式为通过打印,来看代码是否符合自己的预期,另外这次写一下终止条件
private void generateParenthesis(int left, int right, int n, String s,List<String> res) {

        System.out.printf("当前的字符串为:%s ,左:%d,右%d \n",s,left,right);
        // 终止条件
        if (left == n && right == n){
            res.add(s);
            return;
        }
        ...
    }
复制代码
  1. 中间的执行过程。首先要放入左括号,然后再放入有括号
private void generateParenthesis(int left, int right, int n, String s,List<String> res) {

        System.out.printf("当前的字符串为:%s ,左:%d,右%d \n",s,left,right);
        // 终止条件
        if (left == n && right == n){
            res.add(s);
            return;
        }

        // 保证首先添加的是左括号
        if (left < n){
            generateParenthesis(left+1,right,n,s + "(",res);
        }

        // 注意,这里的right < left,代表的意思是
        // 首先我们肯定要放入左括号才是合法的,这样的话,任何时刻,左括号的数量只能比右括号的数量多
        if (right < n && right < left){
            generateParenthesis(left,right+1,n,s + ")",res);
        }

    }
复制代码
  1. 最终代码为
public class Solution_22 {
    /**
     * n = 3 生成
     * [
     *   "((()))",
     *   "(()())",
     *   "(())()",
     *   "()(())",
     *   "()()()"
     * ]
     *
     * 每一个位置都有两种可能性:2^6 = 64。
     *    有一些很明显就错误的,比如:"((( ((("
     *        - 排除显而易见错误的,即左括号与右括号数量不等的
     *    有错误不是那么明显看出来的,比如:"))) (((" , "()) (()"
     *        - 开头是右括号的,直接去掉,这个其实代表右括号已经出现的数量大于左括号出现的数量
     *
     * 正确的方案是首先放左括号,后面只需要有对应的右括号才行
     */

    public static void main(String[] args) {
        List<String> list = new Solution_22().generateParenthesis(3);
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
    }

    public List<String> generateParenthesis(int n) {
        if(n == 0){
            return Collections.emptyList();
        }

        List res = new LinkedList<String>();
        generateParenthesis(0,0,n,"",res);
        return res;
    }

    /**
     *
     * @param left 代表当前已经出现的左括号数量
     * @param right 代表当前已经出现的右括号数量
     * @param n 代表生成括号的对数
     * @param s 代表当前的字符串,可能还未处理完
     * @param res 保存所有括号字符串的列表
     */
    private void generateParenthesis(int left, int right, int n, String s,List<String> res) {

        System.out.printf("当前的字符串为:%s ,左:%d,右%d \n",s,left,right);
        // 终止条件
        if (left == n && right == n){
            res.add(s);
            return;
        }

        // 保证首先添加的是左括号
        if (left < n){
            generateParenthesis(left+1,right,n,s + "(",res);
        }

        // 注意,这里的right < left,代表的意思是
        // 首先我们肯定要放入左括号才是合法的,这样的话,任何时刻,左括号的数量只能比右括号的数量多
        if (right < n && right < left){
            generateParenthesis(left,right+1,n,s + ")",res);
        }

    }
}
复制代码

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

学习JavaScript数据结构与算法(第2版)

学习JavaScript数据结构与算法(第2版)

[巴西] Loiane Groner / 邓 钢、孙晓博、吴 双、陈 迪、袁 源 / 人民邮电出版社 / 2017-9 / 49.00元

本书首先介绍了JavaScript 语言的基础知识以及ES6 和ES7 中引入的新功能,接下来讨论了数组、栈、队列、链表、集合、字典、散列表、树、图等数据结构,之后探讨了各种排序和搜索算法,包括冒泡排序、选择排序、插入排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序、顺序搜索、二分搜索,然后介绍了动态规划和贪心算法等常用的高级算法以及函数式编程,最后还介绍了如何计算算法的复杂度。一起来看看 《学习JavaScript数据结构与算法(第2版)》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

MD5 加密
MD5 加密

MD5 加密工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换