Go java 算法之括號生成示例詳解

更新時間：2022年08月23日 09:58:42 作者：黃丫丫

這篇文章主要為大家介紹了Go java 算法之括號生成示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪

括號生成

數(shù)字 n 代表生成括號的對數(shù)，請你設(shè)計一個函數(shù)，用于能夠生成所有可能的并且有效的括號組合。

示例 1：

輸入：n = 3

輸出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

輸入：n = 1

輸出：["()"]

提示：

1 <= n <= 8

方法一：深度優(yōu)先遍歷（java）

首先我們需要知道一個結(jié)論，一個合法的括號序列需要滿足兩個條件：

1、左右括號數(shù)量相等

2、任意前綴中左括號數(shù)量 >= 右括號數(shù)量（也就是說每一個右括號總能找到相匹配的左括號）

題目要求我們生成n對的合法括號序列組合，因此可以考慮使用深度優(yōu)先搜索

將搜索順序定義為枚舉序列的每一位填什么，那么最終的答案一定是由n個左括號和n個右括號組成。

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<String>();
        backtrack(ans, new StringBuilder(), 0, 0, n);
        return ans;
    }
    public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
        if (cur.length() == max * 2) {
            ans.add(cur.toString());
            return;
        }
        if (open < max) {
            cur.append('(');
            backtrack(ans, cur, open + 1, close, max);
            cur.deleteCharAt(cur.length() - 1);
        }
        if (close < open) {
            cur.append(')');
            backtrack(ans, cur, open, close + 1, max);
            cur.deleteCharAt(cur.length() - 1);
        }
    }
}

時間復雜度：o(4^n / n^(1/2))

空間復雜度：o(n)

方法一：深度優(yōu)先遍歷（go）

具體方法分析已在上文中表述

根據(jù)題目條件生成一顆樹，并對這顆樹生枝葉的條件按照題目進行限制。

需要左右括號都大于0個時才可以進行生成樹的操作（等于0的特殊情況）

生成樹之后生出左節(jié)點的條件：左括號的剩余數(shù)量大于0

生成樹之后生成右節(jié)點條件：左括號的剩余數(shù)量小于右括號的剩余數(shù)量

當左右括號都為0時，為成功出口，此時進行結(jié)算，保存結(jié)果。

	var ans []string
	var backtrack func([]byte, int, int)
	backtrack = func(bytes []byte, left int, right int) {
		if len(bytes) == 2*n {
			ans = append(ans, string(bytes))
			return
		}
		if left < n {
			bytes = append(bytes,'(')
			backtrack(bytes, left+1, right)
			bytes = bytes[:len(bytes)-1]
		}
		if right < left{
			bytes = append(bytes, ')')
			backtrack(bytes, left, right + 1)
			bytes = bytes[:len(bytes)-1]
		}
	}
	var container []byte
	backtrack(container, 0, 0)
	return ans

時間復雜度：o(4^n / n^(1/2))

空間復雜度：o(n)

以上就是Go java 算法之括號生成示例詳解的詳細內(nèi)容，更多關(guān)于Go java 算法括號生成的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: