给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。
示例
例如,给出 n = 3,生成结果为:["((()))","(()())","(())()","()(())","()()()"]
思路
我们知道,有且仅有两种情况,生成的括号序列不合法
我们不停的加左括号,其实如果左括号超过 n 的时候,它肯定不是合法序列了。因为合法序列一定是 n 个左括号和 n 个右括号。
如果添加括号的过程中,如果右括号的总数量大于左括号的总数量了,后边不论再添加什么,它都不可能是合法序列了。
基于上边的两点,我们只要避免它们,就可以保证我们生成的括号一定是合法的了。
详解
采用回溯法,即把问题的解空间转化成了图或者树的结构表示,然后,使用深度优先搜索策略进行遍历,遍历的过程中记录和寻找所有可行解或者最优解。
如果自定义的字符串长度足够且走到这里,那么就说明这个组合是合适的,我们把它保存。
否则,递归执行添加左括号,添加右括号的操作。
递归结束条件为结果字符串长度等于左右括号的总个数(2n),则返回最终结果。
代码
/*** @param {number} n* @return {string[]}*/const generateParenthesis = n => {const res = [];const gen = (str = '', l = 0, r = 0) => {// 如果自定义的字符串长度足够且走到这里,那么就说明这个组合是合适的if (str.length === 2 * n) {res.push(str);return;}// 下面的逻辑:左括号必须出现在右括号的前面// 只有在 l >= n 的 时候,才不能添加左括号,其他都可添加if (l < n) {gen(`${str}(`, l + 1, r);}// 如果右括号没有左括号多,我们就可以添加一个右括号if (r < l) {gen(`${str})`, l, r + 1);}};gen();return res;};
复杂度分析
我们的复杂度分析依赖于理解 generateParenthesis(n) 中有多少个元素。这个分析需要更多的背景来解释,但事实证明这是第 n 个卡塔兰数 ,这是由 渐近界定的。
时间复杂度:,在回溯过程中,每个有效序列最多需要 n 步。
空间复杂度:,如上所述,并使用 的空间来存储序列。
思路
整体的实现思路也是回溯法,也是递归来实现该思路,唯一不同的是,递归的结束条件是左右括号都消费尽。
详解
采用回溯法,即把问题的解空间转化成了图或者树的结构表示,然后,使用深度优先搜索策略进行遍历,遍历的过程中记录和寻找所有可行解或者最优解。
首先,先从左括号开始填充。
然后,填充右括号,保证两类括号数目一致,平衡。
递归结束条件为左右括号均消费尽,则输出结果。
代码
/*** @param {number} n* @return {number}*/const generateParenthesis = n => {const res = [];// left :左括号个数, right:右括号个数function helper (left, right, max, str) {if (left === max && right === max) {res.push(str);return;}// 先从左括号开始填充if (left < max) {helper(left + 1, right, max, `${str}(`);}// 保证两类括号数目一致if (left > right) {helper(left, right + 1, max, `${str})`);}}helper(0, 0, n, '');return res;};
复杂度分析
本方法也是使用回溯法,只是具体实现方式不同,因此,复杂度也是一样的。
时间复杂度:
在回溯过程中,每个有效序列最多需要 步。
空间复杂度:
如上所述,并使用 的空间来存储序列。
给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明:解集不能包含重复的子集。
示例
输入: nums = [1,2,3]输出:[[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[]]
设置初始二维数组[[]],依次把每个数加入到数组中的每一个元素中,并保留原来的所有元素。
初始化二维数组来存储所有子集;
使用双层遍历,外层遍历 nums 数组,内层遍历二维数组,将每个元素与二维数组每项合并,并保留二维数组原有的元素
并将得到的新子集与二维数组元素合并,最后得到所有子集;
例如:输入 nums = [1, 2, 3] 初始化二维数组存储所有子集 result = [[]] 然后遍历 nums, 1 添加到[], 结果为 [[], [1]]; 2 添加到[], [1], 结果为 [[], [1], [2], [1, 2]]; 3 添加到[], [1], [2], [1, 2], 结果为 [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]];
const subsets = (nums) => {let result = [[]]; // 初始化二维数组for (let i of nums) {const temp = [];for (let k of result) {temp.push(k.concat(i)); // 依次把每个元素添加到数组中}result = result.concat(temp);}return result;}
时间复杂度:
根据上述算法,每次循环 result 数组的次数为 , 则计算总数为 ,根据等比数列计算公式得到循环总次数为 ,所以时间复杂度为 。
空间复杂度:
根据排列组合原理,子集包含一个数字的情况所耗费的存储空间为 ,包含两个数字所耗费的存储空间为 ,根据算法得出 共需要 个存储空间,根据排列组合公式求和可得需要 个额外存储空间, 所以算法空间复杂度为 。
从数学角度看,求子集其实是一个排列组合问题,比如 nums = [1, 2, 3],存在四种情况:
都不选,情况共有 种
只选 1 个数,情况共有 种
选 2 个数,情况共有 种
全选,情况共有 种
落到数组中的每个数字,都有两种可能,选与不选,我们用 1 标识选,用 0 标识不选。 则 [] 表示为 000,[1, 2, 3] 表示为 111,我们通过转化为二进制表示法,遍历 000 - 111 的所有组合,即可求出所有子集。
详解
根据上述分析,我们得出加入数组为 nums,则针对每位存在选与不选两种情况,那么所有组合数为 个。
针对每一种组合情况,我们可以取出该二进制表示法中的每一位,如 110,我们分别通过向右移位并和 1 求与,判断最低为的值为 0 或者 1。
如果得到结果为 1,那么表示该位表示的数字在原数组中被选中,存入暂存数组,一轮遍历后即可获得该组子集的数字组合。将所有子集数字组合一起存入结果数组,即求出所有子集。
代码
const subsets = (nums) => {// 子集的数量const len = nums.length;const setNums = Math.pow(2, len);const result = [];for (let i = 0; i < setNums; i++) {let temp = [];// 判断该二进制表示法中,每一个位是否存在for (let j = 0; j < len; j++) {if (1 & (i >> j)) { // 如果该位为 1,则存入组合数组temp.push(nums[j]);}}result.push(temp);}return result;};
复杂度分析
时间复杂度:
一共包含 个组合需要 次计算,所以时间复杂度为 。
空间复杂度:
给定一个仅包含数字 2-9
的字符串,返回所有它能表示的字母组合。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
示例
输入:"23"输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
思路
利用队列的先进先出的特点,把队列中的第一个元素拿出,再与后面的挨个拼接
a, b, c --> b, c, ad, ae, af --> c, ad, ae, af, bd, be, bf -> ...
详解
先在队列中插入一个空字符
取出队列中的第一个元素,与后一位数字对应的字符进行挨个拼接
重复第二步,直到结束
代码
const letterCombinations = function (digits) {const map = {2: ['a', 'b', 'c'],3: ['d', 'e', 'f'],4: ['g', 'h', 'i'],5: ['j', 'k', 'l'],6: ['m', 'n', 'o'],7: ['p', 'q', 'r', 's'],8: ['t', 'u', 'v'],9: ['w', 'x', 'y', 'z']};if (!digits) {return [];}const res = [''];for (let i = 0; i < digits.length; i++) {const letters = map[digits[i]];const size = res.length;for (let j = 0; j < size; j++) {const temp = res.shift(0); // 取出第一个元素for (let k = 0; k < letters.length; k++) {res.push(`${temp}${letters[k]}`); // 第一个元素与后一位数字对应的字符进行挨个拼接}}}return res;};
复杂度分析
时间复杂度:
通过数组的 push 我们发现,循环的次数和最后数组的长度是一样的,然而数组的长度有和输入多个3个字母的数目、4个字母的数目有关,得出时间复杂度为
其中 为3个字母的数目, 为4个字母的数目
空间复杂度:
最后结果的长度和输入的数字有关,得出复杂度为
思路
这道题有点排列组合的味道,我们可以穷举所有的可能性,找到所有的可能性
详解
如果还有数字需要被输入,就继续遍历数字对应的字母进行组合 prefix
+ letter
当发现没有数字输入时,说明已经走完了,得到结果
代码
const map = {2: ['a', 'b', 'c'],3: ['d', 'e', 'f'],4: ['g', 'h', 'i'],5: ['j', 'k', 'l'],6: ['m', 'n', 'o'],7: ['p', 'q', 'r', 's'],8: ['t', 'u', 'v'],9: ['w', 'x', 'y', 'z']};const letterCombinations = function (digits) {const result = [];function backtrack (prefix, next) {// 发现没有字母需要输入时,就可以返回了if (next.length === 0) {result.push(prefix);} else {const digit = next[0];const letters = map[digit]; // 获取对应的各个字母for (let i = 0; i < letters.length; i++) {backtrack(prefix + letters[i], next.substr(1));}}}if (digits.length !== 0) {backtrack('', digits);}return result;};
复杂度分析
时间复杂度:
空间复杂度: