生成)
22. 括號(hào)生成 - 力扣LeetCode數(shù)字n代表生成括號(hào)的對(duì)數(shù)請(qǐng)你設(shè)計(jì)一個(gè)函數(shù)用于能夠生成所有可能的并且有效的括號(hào)組合。示例 1輸入n 3輸出[((())),(()()),(())(),()(()),()()()]示例 2輸入n 1輸出[()]提示1 n 8本質(zhì)在 0, 1, 2, ... , 2n - 1 中選擇 n 個(gè)位置填入左括號(hào)其余 n 個(gè)位置填入右括號(hào)。需要注意的是對(duì)于這個(gè)字符串的任意前綴右括號(hào)的個(gè)數(shù)必須不大于左括號(hào)的個(gè)數(shù)因?yàn)樽罄ㄌ?hào)多了后面還可以補(bǔ)右括號(hào)前面的右括號(hào)多了后面補(bǔ)左括號(hào)也無(wú)法構(gòu)成一對(duì)括號(hào)所以對(duì)于單個(gè)位置來(lái)說(shuō)問(wèn)題就變成 選或不選 即選左括號(hào)還是選右括號(hào)。如果當(dāng)前左右括號(hào)數(shù)量相等那么就必須填左括號(hào)如果右括號(hào)個(gè)數(shù)小于左括號(hào)個(gè)數(shù)那么填右括號(hào)。由于一開(kāi)始左右括號(hào)數(shù)量均為 0按照這個(gè)策略第一個(gè)位置填入的必然是左括號(hào)顯然后續(xù)不可能出現(xiàn)右括號(hào)數(shù)量比左括號(hào)多的情況這是合理的class Solution: def generateParenthesis(self, n: int) - List[str]: ans [] path [] * (n * 2) # n 個(gè)左括號(hào)n個(gè)右括號(hào) # left:左括號(hào)數(shù)量right:右括號(hào)數(shù)量 def dfs(left: int, right:int) - None: if right n: # 2n 個(gè)括號(hào)全部填完 ans.append(.join(path)) return if left n: # 左括號(hào)數(shù)量沒(méi)有達(dá)到 n可以填 path[left right] ( dfs(left 1, right) if right left: path[left right] ) dfs(left, right 1) dfs(0, 0) return ans這里不需要做恢復(fù)現(xiàn)場(chǎng)因?yàn)槭侵苯痈采w left right 位置的元素的pythonfrom typing import List def generateParenthesis(n: int) - List[str]: ans [] path [] * (n * 2) # left: 左括號(hào)數(shù)量right: 右括號(hào)數(shù)量 def dfs(left: int, right: int) - None: if right n: # 填充完畢 ans.append(.join(path)) return if left n: # 可以填充左括號(hào) path[left right] ( # 直接覆蓋因此如果填充完畢path 不需要清空 dfs(left 1, right) if right left: # 可以填充右括號(hào) path[left right] ) dfs(left, right 1) dfs(0, 0) return ans def main(): with open(input.txt, r) as f: nums f.read().split() # 遍歷 input.txt 中的 n for num in nums: n int(num) result generateParenthesis(n) # 輸出結(jié)果 print(fn {n}) print(result) print() if __name__ __main__: main()Javaimport java.io.BufferedReader; import java.io.FileReader; import java.util.ArrayList; import java.util.List; public class main { static int n; static ListString ans; static char[] path; public static ListString generateParenthesis(int n) { main.n n; ans new ArrayList(); path new char[n * 2]; dfs(0, 0); return ans; } public static void dfs(int left, int right) { if(right n) { // 填充完畢 ans.add(new String(path)); return; } if(left n) { path[left right] (; dfs(left 1, right); } if(right left) { path[left right] ); dfs(left, right 1); } } public static void main(String[] args) throws Exception { BufferedReader br new BufferedReader(new FileReader(input.txt)); StringBuilder sb new StringBuilder(); String line; while((line br.readLine()) ! null) { if(line.isEmpty()) { continue; } int n Integer.parseInt(line.trim()); ListString result generateParenthesis(n); sb.append(n ).append(n).append(\n); sb.append(result).append(\n\n); } System.out.println(sb); } }Gopackage main import ( fmt os strconv strings ) var ans []string var path []byte func dfs(n int, left int, right int) { if right n { ans append(ans, string(path)) return } if left n { path[leftright] ( dfs(n, left1, right) } if right left { path[leftright] ) dfs(n, left, right1) } } func generateParenthesis(n int) []string { ans nil path make([]byte, n*2) dfs(n, 0, 0) return ans } func main() { data, _ : os.ReadFile(input.txt) nums : strings.Fields(string(data)) for _, s : range nums { n, _ : strconv.Atoi(s) result : generateParenthesis(n) fmt.Printf(n %d\n, n) fmt.Println(result) fmt.Println() } }C#includeiostream #includevector #includestring #includefstream using namespace std; vectorstringans; string path; void dfs(int n, int left, int right) { if(right n) { ans.emplace_back(path); return; } if(left n) { path[left right] (; dfs(n, left 1, right); } if(right left) { path[left right] ); dfs(n, left, right 1); } } vectorstring generateParenthesis(int n) { ans.clear(); path string(n * 2, ); dfs(n, 0, 0); return ans; } int main() { ifstream ifs(input.txt); int n; while(ifs n) { auto result generateParenthesis(n); cout n n endl; cout [; for(int i 0; i result.size(); i) { cout result[i]; if(i ! result.size() - 1) { cout ,; } } cout ] endl endl; } return 0; }TypeScriptimport * as fs from fs; function generateParenthesis(n: number) :string[] { let ans:string[] []; let path:string[] new Array(n * 2); function dfs(left: number, right: number) { if(right n) { ans.push(path.join()); return; } if(left n) { path[left right] (; dfs(left 1, right); } if(right left) { path[left right] ); dfs(left, right 1); } } dfs(0, 0); return ans; } function main() { const data fs.readFileSync( input.txt, utf-8 ); const nums data.trim().split(/\s/); for(const s of nums) { const n Number(s); const result generateParenthesis(n); console.log(n ${n}); console.log(result); console.log(); } } main(); 力扣22-括號(hào)生成
22. 括號(hào)生成 - 力扣LeetCode數(shù)字n代表生成括號(hào)的對(duì)數(shù)請(qǐng)你設(shè)計(jì)一個(gè)函數(shù)用于能夠生成所有可能的并且有效的括號(hào)組合。示例 1輸入n 3輸出[((())),(()()),(())(),()(()),()()()]示例 2輸入n 1輸出[()]提示1 n 8本質(zhì)在 0, 1, 2, ... , 2n - 1 中選擇 n 個(gè)位置填入左括號(hào)其余 n 個(gè)位置填入右括號(hào)。需要注意的是對(duì)于這個(gè)字符串的任意前綴右括號(hào)的個(gè)數(shù)必須不大于左括號(hào)的個(gè)數(shù)因?yàn)樽罄ㄌ?hào)多了后面還可以補(bǔ)右括號(hào)前面的右括號(hào)多了后面補(bǔ)左括號(hào)也無(wú)法構(gòu)成一對(duì)括號(hào)所以對(duì)于單個(gè)位置來(lái)說(shuō)問(wèn)題就變成 選或不選 即選左括號(hào)還是選右括號(hào)。如果當(dāng)前左右括號(hào)數(shù)量相等那么就必須填左括號(hào)如果右括號(hào)個(gè)數(shù)小于左括號(hào)個(gè)數(shù)那么填右括號(hào)。由于一開(kāi)始左右括號(hào)數(shù)量均為 0按照這個(gè)策略第一個(gè)位置填入的必然是左括號(hào)顯然后續(xù)不可能出現(xiàn)右括號(hào)數(shù)量比左括號(hào)多的情況這是合理的class Solution: def generateParenthesis(self, n: int) - List[str]: ans [] path [] * (n * 2) # n 個(gè)左括號(hào)n個(gè)右括號(hào) # left:左括號(hào)數(shù)量right:右括號(hào)數(shù)量 def dfs(left: int, right:int) - None: if right n: # 2n 個(gè)括號(hào)全部填完 ans.append(.join(path)) return if left n: # 左括號(hào)數(shù)量沒(méi)有達(dá)到 n可以填 path[left right] ( dfs(left 1, right) if right left: path[left right] ) dfs(left, right 1) dfs(0, 0) return ans這里不需要做恢復(fù)現(xiàn)場(chǎng)因?yàn)槭侵苯痈采w left right 位置的元素的pythonfrom typing import List def generateParenthesis(n: int) - List[str]: ans [] path [] * (n * 2) # left: 左括號(hào)數(shù)量right: 右括號(hào)數(shù)量 def dfs(left: int, right: int) - None: if right n: # 填充完畢 ans.append(.join(path)) return if left n: # 可以填充左括號(hào) path[left right] ( # 直接覆蓋因此如果填充完畢path 不需要清空 dfs(left 1, right) if right left: # 可以填充右括號(hào) path[left right] ) dfs(left, right 1) dfs(0, 0) return ans def main(): with open(input.txt, r) as f: nums f.read().split() # 遍歷 input.txt 中的 n for num in nums: n int(num) result generateParenthesis(n) # 輸出結(jié)果 print(fn {n}) print(result) print() if __name__ __main__: main()Javaimport java.io.BufferedReader; import java.io.FileReader; import java.util.ArrayList; import java.util.List; public class main { static int n; static ListString ans; static char[] path; public static ListString generateParenthesis(int n) { main.n n; ans new ArrayList(); path new char[n * 2]; dfs(0, 0); return ans; } public static void dfs(int left, int right) { if(right n) { // 填充完畢 ans.add(new String(path)); return; } if(left n) { path[left right] (; dfs(left 1, right); } if(right left) { path[left right] ); dfs(left, right 1); } } public static void main(String[] args) throws Exception { BufferedReader br new BufferedReader(new FileReader(input.txt)); StringBuilder sb new StringBuilder(); String line; while((line br.readLine()) ! null) { if(line.isEmpty()) { continue; } int n Integer.parseInt(line.trim()); ListString result generateParenthesis(n); sb.append(n ).append(n).append(\n); sb.append(result).append(\n\n); } System.out.println(sb); } }Gopackage main import ( fmt os strconv strings ) var ans []string var path []byte func dfs(n int, left int, right int) { if right n { ans append(ans, string(path)) return } if left n { path[leftright] ( dfs(n, left1, right) } if right left { path[leftright] ) dfs(n, left, right1) } } func generateParenthesis(n int) []string { ans nil path make([]byte, n*2) dfs(n, 0, 0) return ans } func main() { data, _ : os.ReadFile(input.txt) nums : strings.Fields(string(data)) for _, s : range nums { n, _ : strconv.Atoi(s) result : generateParenthesis(n) fmt.Printf(n %d\n, n) fmt.Println(result) fmt.Println() } }C#includeiostream #includevector #includestring #includefstream using namespace std; vectorstringans; string path; void dfs(int n, int left, int right) { if(right n) { ans.emplace_back(path); return; } if(left n) { path[left right] (; dfs(n, left 1, right); } if(right left) { path[left right] ); dfs(n, left, right 1); } } vectorstring generateParenthesis(int n) { ans.clear(); path string(n * 2, ); dfs(n, 0, 0); return ans; } int main() { ifstream ifs(input.txt); int n; while(ifs n) { auto result generateParenthesis(n); cout n n endl; cout [; for(int i 0; i result.size(); i) { cout result[i]; if(i ! result.size() - 1) { cout ,; } } cout ] endl endl; } return 0; }TypeScriptimport * as fs from fs; function generateParenthesis(n: number) :string[] { let ans:string[] []; let path:string[] new Array(n * 2); function dfs(left: number, right: number) { if(right n) { ans.push(path.join()); return; } if(left n) { path[left right] (; dfs(left 1, right); } if(right left) { path[left right] ); dfs(left, right 1); } } dfs(0, 0); return ans; } function main() { const data fs.readFileSync( input.txt, utf-8 ); const nums data.trim().split(/\s/); for(const s of nums) { const n Number(s); const result generateParenthesis(n); console.log(n ${n}); console.log(result); console.log(); } } main();