锐客网

  1. 首页 > 生活百科 > it技术 > >

leetcode 22 生成括号

IT知识leetcode

知是行的主意,行是知的功夫。这篇文章主要讲述leetcode 22 生成括号相关的知识，希望能为你提供帮助。
【leetcode 22 生成括号】leetcode 22 生成括号

??https://leetcode-cn.com/problems/generate-parentheses/?? 
  /* 当n=1时 ()



当n=2时()() (())





当n=3时

[ "()(())", "()()()" "(())()", "(()())", "((()))", ]



思路：找规律：



 
任何一个括号序列都一定是由 ( 开头，并且第一个 ( 一定有一个唯一与之对应的 )。这样一来，每一个括号序列可以用 (a)b 来表示，其中 a 与 b 分别是一个合法的括号序列（可以为空）。
 
n = 0



n = 1

()相当于( 里面n=0 )



n = 2



()()相当于 ( 里面n=0 )右n=1

(())相当于 ( 里面n=1 )





n = 3



() (())相当于 ( 里面n=0 )右n=2

() ()()相当于 ( 里面n=0 )右n=2



(()) ()相当于 ( 里面n=1 )右n=1



( ()() )相当于 ( 里面n=2 )

( (()) )相当于 ( 里面n=2 ) */



function generateParenthesis(n)



if (n === 0)

return []



const result = []



for (let i = 0; i < = n - 1; i++)

let left = generateParenthesis(i) let right = generateParenthesis(n - i - 1) left.forEach((itemLeft) => right.forEach((itemRight) => result.push(`($itemLeft)$itemRight`) ) )



return result









const r = generateParenthesis(3)

console.log(r);     ============================================================   // iteration(使用迭代) var generateParenthesis = function(n)



const results = [[], [()]]



for (let i = 2; i < = n; i++)



const result = []

  for (let j = 0; j < = i - 1; j++) const leftInner = results[j] const right = results[i - j -1] leftInner.forEach((itemLeft) => right.forEach((itemRight) => result.push(`($itemLeft)$itemRight`) ) )results[i] = result



return results[n]



;

    =================================================   回溯法



var generateParenthsis = function (n) let list = [] function generate(left, right, s) if (left === n & & right === n) list.push(s) return// 生成左括号的条件应该是 left的数量 小于n if (left < n) generate(left + 1, right, s + ()// 生成右括号的条件应该是 left的数量大于right的数量 () ((() if (left > right) generate(left, right + 1, s + ))generate(0, 0, ) return list



const r = generateParenthsis(3)

console.log(r);


    推荐阅读


    上一篇：工作一年总结

    下一篇：JVM复习笔记