内容简介:想刷刷leetcode锻炼写自己写代码的能力,关于写代码,我觉得它不仅仅是写代码,而是写你的想法。为什么有的人会写成一坨,而有的人代码工整,美感,这个一方面是一个人写之前是否有思考清楚,另外一方面是写代码的习惯了。代码只是表达思想的一种首先想到的是,每一个位置都有两种可能性:2^6 = 64。
想刷刷leetcode锻炼写自己写代码的能力,关于写代码,我觉得它不仅仅是写代码,而是写你的想法。为什么有的人会写成一坨,而有的人代码工整,美感,这个一方面是一个人写之前是否有思考清楚,另外一方面是写代码的习惯了。
代码只是表达思想的一种
题目
给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且 有效的 括号组合。
例如,给出 n = 3,生成结果为:
[ "((()))", "(()())", "(())()", "()(())", "()()()" ] 复制代码
解题
首先想到的是,每一个位置都有两种可能性:2^6 = 64。
-
有一些很明显就错误的,比如:"((( ((("
- 排除显而易见错误的,即左括号与右括号数量不等的
-
有错误不是那么明显看出来的,比如:"))) (((" , "()) (()"
- 开头是右括号的,直接去掉,这个其实代表右括号已经出现的数量大于左括号出现的数量
正确的方案是,首先要放入左括号"(",后续要有一个与之对应的括号,同时在任何位置,有括号")"的数量不能大于"("的数量,否则,"())" 就是错误的。
代码
- 首先定义一个方法,要知道当前左括号与有括号的数量,并且知道当前的字符串
/** * * @param left 代表当前已经出现的左括号数量 * @param right 代表当前已经出现的右括号数量 * @param n 代表生成括号的对数 * @param s 代表当前的字符串,可能还未处理完 * @param res 保存所有括号字符串的列表 */ private void generateParenthesis(int left, int right, int n, String s,List<String> res) { } 复制代码
- 目前比较喜欢的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; } ... } 复制代码
- 中间的执行过程。首先要放入左括号,然后再放入有括号
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); } } 复制代码
- 最终代码为
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); } } } 复制代码
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
加密与解密(第4版)
段钢 / 电子工业出版社 / 2018-10-1 / 198
《加密与解密(第4版)》以加密与解密为切入点,讲述了软件安全领域的基础知识和技能,如调试技能、逆向分析、加密保护、外壳开发、虚拟机设计等。这些知识彼此联系,读者在掌握这些内容之后,很容易就能在漏洞分析、安全编程、病毒分析、软件保护等领域进行扩展。从就业的角度来说,掌握加密与解密的相关技术,可以提高自身的竞争能力;从个人成长的角度来说,研究软件安全技术有助于掌握一些系统底层知识,是提升职业技能的重要......一起来看看 《加密与解密(第4版)》 这本书的介绍吧!