22. 括号生成 (js)

[crawler-django]

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

输入：n = 3
输出：[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

---

问题1: 这看起来跟生成多少种排序有点像啊, 如123三个数生成多少种排序, 排成 123, 132, 213, 231, 312, 321这些, 是不是有什么联系呢?
答: 其实括号比这个还简单的多, 不用按那种排序方法来想. 生成3个括号对数, 无非就是三个'('和三个')'. 总长度一看就知2n, 2*3=6啊. 暴力递归去重就可以了。

问题2: 道理我都懂, 如何实现呢? �
答: 不急, 咱慢慢来. 首先咱分为两步:

1. 先想办法能生成所有的值: 递归和控制结束.
2. 在生成的时候判断是否值非法. 比如是'('就加1, ')'就减1. 就按n等于3算, 值如果大于3了那么肯定非法, 小于0也肯定非法, 只有走完了总长度值为0才把值保存.

示例代码:

	const generateArr = (newArr, start, end, vaildScore, goalArr) => {
                // newArr为样板值, goalArr为存储数据的数组
		if (vaildScore > (end/2) || vaildScore < 0) {
			return
		}

		if (start >= end) {
			if (vaildScore === 0) {
				goalArr.push(newArr.join(''))
			} else {
				return
			}
		} else {
			newArr[start] = '('
			generateArr(newArr, start + 1, end, vaildScore + 1, goalArr)

			newArr[start] = ')'
			generateArr(newArr, start + 1, end, vaildScore - 1, goalArr)
		}

		
	}

	var generateParenthesis = function(n) {  // leetcode初始函数
		let arr = []    
		generateArr([], 0, 2 * n, 0, arr)

		return arr
	};

        console.log(generateParenthesis(3))  // 打印结果

因为可以预知它的非法值, 在非法值产生的时候就可以停止继续递归下去. 停止不必要的消耗.
这种方法称为'回溯算法'. '回溯算法'是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯” 返回，尝试别的路径.
当时解决这问题所能想到最好的解就是如此了.. (还有一种动态规划的, 下次研究.)

成果(才80%):

---

动态规划的写法: 动态规划就是划分为一个个子步骤, 存储起来重复的子步骤.

那么就有疑问了, 这括号生成的重复子步骤是啥? 这是使用动态规划最难的一点, 首先得找到它们的规律.

我们用F(n)来表示括号生成函数. 首先能确认F(0) = [''], F[1] = ['()']. 那F(2) = ?。 我们自己手算的话 F(2) = ['()()', '(())'].

那换成公式呢? F(2) = (F(0)) + F(1), (F(1)) + F(0). 是不是?

再试试F(3), F(3) = (F(0)) + F(2), (F(1)) + F(1), (F(2)) + F(0). 是不是? F(2)我们上面计算了, 有两个元素, 所以(F(0)) + F(2) 肯定会是2个. 1 x 2嘛, 只有两个结果. 同理(F(2)) + F(0)也是, 2 * 1 = 2. 所以F(3)有5个元素. 而且也是我们规律所列出来的元素. 不信可以试试.

那么我们的公式就有着落了. F(x) = (F(n)) + F(x - n - 1) 的累加, 0 <= n <= x-1. x > n.
把它们写成代码:

var generateParenthesis = function(n) {   
   
    let list = []

   const generateFun = (n) => {

       if (list[n]) {
           return list[n]
       }

       if (n == 0 || n == 1) {
           list[0] = ['']
           list[1] = ['()']

           return list[n]
       }


       let result = []

       for(let i = 0; i < n; i += 1) {
           let left = generateFun(i)
           let right = generateFun(n - i - 1)

           for (let leftIndex = 0; leftIndex < left.length; leftIndex += 1) {
               let leftValue = `(${left[leftIndex]})`

               for (let rightIndex = 0; rightIndex < right.length; rightIndex += 1) {
                   let rightValue = right[rightIndex]

                   result.push(leftValue + rightValue)
               }
           }
       }

       list[n] = result

       return list[n]
   }

    return generateFun(n)

};

console.log(generateParenthesis(4))

运行结果:

内存消耗成果可观, 击败了100%。