推薦閱讀
- CSDN主頁
- GitHub開源地址
- Unity3D插件分享
- 簡書地址
- 我的個人博客
- QQ群：1040082875
大家好，我是小魔龍，Unity3D軟體工程師，VR、AR，虛擬仿真方向，不定時更新軟體開發技巧，生活感悟，覺得有用記得一鍵三連哦，
一、題目
1、演算法題目
“給定一個整數n，生成所有有效的括號組合，”
題目鏈接：
來源：力扣（LeetCode）
鏈接：22. 括號生成 - 力扣（LeetCode） (leetcode-cn.com)
2、題目描述
數字 n 代表生成括號的對數，請你設計一個函式，用于能夠生成所有可能的并且 有效的 括號組合，
有效括號組合需滿足：左括號必須以正確的順序閉合，
示例 1：
輸入： n = 3
輸出： ["((()))","(()())","(())()","()(())","()()()"]
示例 2：
輸入： n = 1
輸出： ["()"]
二、解題
1、思路分析
這道題可以采用暴力破解法，生成所有字符構成的序列，然后檢查有效即可，
2、代碼實作
采用遞回生成所有序列，然后用左括號數量減去右括號數量，判斷序列是否有效，代碼參考：
public class Solution {
public IList<string> GenerateParenthesis(int n) {
List<string> res = new List<string>();
if (n == 0)
res.Add("");
else
{
for (var i = 0; i < n; i++)
{
foreach (var left in GenerateParenthesis(i))
{
foreach (var right in GenerateParenthesis(n - i - 1))
{
res.Add("(" + left + ")" + right);
}
}
}
}
return res;
}
}
3、時間復雜度
時間復雜度 ： O(22nn)
對于 22nn 個序列中的每一個，我們用于建立和驗證該序列的復雜度為 O(n)，
空間復雜度： O(n)
除了答案陣列之外，我們所需要的空間取決于遞回堆疊的深度，每一層遞回函式需要 O(1) 的空間，最多遞回 2n 層，因此空間復雜度為 O(n)，
三、總結
回溯的話，要么設定一個全域的唯一狀態，然后去遞回，
要么自己管理一個堆疊或佇列，每次儲存相應的狀態，然后去遍歷狀態樹，
我一般不太喜歡函式遞回，因為函式呼叫稍慢些，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/336320.html
標籤：其他
下一篇：＜2021SC@SDUSC＞ 開源游戲引擎 Overload 代碼模塊分析 之 OvTools（四）—— Utils（上）