Go java 算法之括號(hào)生成示例詳解
括號(hào)生成
數(shù)字 n 代表生成括號(hào)的對(duì)數(shù)，請(qǐng)你設(shè)計(jì)一個(gè)函數(shù)，用于能夠生成所有可能的并且 有效的 括號(hào)組合。
- 示例 1：
輸入：n = 3
輸出：["((()))","(()())","(())()","()(())","()()()"]
- 示例 2：
輸入：n = 1
輸出：["()"]
提示：
1 <= n <= 8
方法一：深度優(yōu)先遍歷（java）
首先我們需要知道一個(gè)結(jié)論，一個(gè)合法的括號(hào)序列需要滿足兩個(gè)條件：
1、左右括號(hào)數(shù)量相等
2、任意前綴中左括號(hào)數(shù)量 >= 右括號(hào)數(shù)量 （也就是說每一個(gè)右括號(hào)總能找到相匹配的左括號(hào)）
題目要求我們生成n對(duì)的合法括號(hào)序列組合，因此可以考慮使用深度優(yōu)先搜索
將搜索順序定義為枚舉序列的每一位填什么，那么最終的答案一定是由n個(gè)左括號(hào)和n個(gè)右括號(hào)組成。
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);
}
}
}
時(shí)間復(fù)雜度：o(4^n / n^(1/2))
空間復(fù)雜度：o(n)
方法一：深度優(yōu)先遍歷（go）
具體方法分析已在上文中表述
根據(jù)題目條件生成一顆樹，并對(duì)這顆樹生枝葉的條件按照題目進(jìn)行限制。
需要左右括號(hào)都大于0個(gè)時(shí)才可以進(jìn)行生成樹的操作（等于0的特殊情況）
生成樹之后生出左節(jié)點(diǎn)的條件：左括號(hào)的剩余數(shù)量大于0
生成樹之后生成右節(jié)點(diǎn)條件：左括號(hào)的剩余數(shù)量 小于 右括號(hào)的剩余數(shù)量
當(dāng)左右括號(hào)都為0時(shí)，為成功出口，此時(shí)進(jìn)行結(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
時(shí)間復(fù)雜度：o(4^n / n^(1/2))
空間復(fù)雜度：o(n)
以上就是Go java 算法之括號(hào)生成示例詳解的詳細(xì)內(nèi)容，更多關(guān)于Go java 算法括號(hào)生成的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
Go語(yǔ)言有一個(gè)特殊的函數(shù)init，先于main函數(shù)執(zhí)行，實(shí)現(xiàn)包級(jí)別的一些初始化操作。這篇文章介紹了Go中的Init函數(shù)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-07-07
Go語(yǔ)言中的len函數(shù)是一個(gè)內(nèi)建函數(shù),用于獲取數(shù)組、切片、字符串、映射和通道等數(shù)據(jù)類型的長(zhǎng)度或大小,本文介紹了len函數(shù)在不同數(shù)據(jù)類型中的使用場(chǎng)景和特點(diǎn),感興趣的可以了解一下2024-10-10
使用Golang實(shí)現(xiàn)WebSocket心跳機(jī)制
WebSocket是一種在客戶端和服務(wù)器之間實(shí)現(xiàn)全雙工通信的協(xié)議,它允許實(shí)時(shí)地傳輸數(shù)據(jù),并且比傳統(tǒng)的HTTP請(qǐng)求更加高效,在使用Golang構(gòu)建WebSocket應(yīng)用程序時(shí),一個(gè)重要的考慮因素是如何實(shí)現(xiàn)心跳機(jī)制,所以本文將探討如何使用Golang實(shí)現(xiàn)WebSocket心跳2023-11-11
使用golang在windows上設(shè)置全局快捷鍵的操作
最近在工作中,總是重復(fù)的做事,想著自己設(shè)置一個(gè)快捷鍵實(shí)現(xiàn)windows 剪貼板的功能,所以本文小編給大家分享了使用golang在windows上設(shè)置全局快捷鍵的操作,文中有相關(guān)的代碼示例供大家參考,需要的朋友可以參考下2024-02-02
golang對(duì)自定義類型進(jìn)行排序的解決方法
學(xué)習(xí)一門編程語(yǔ)言，要掌握原子數(shù)據(jù)類型，還需要掌握自定義數(shù)據(jù)類型。下面這篇文章主要給大家介紹了關(guān)于golang如何對(duì)自定義類型進(jìn)行排序的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，需要的朋友可以參考下。2017-12-12
Zap是我個(gè)人比較喜歡的日志庫(kù)，是uber開源的，有較好的性能，在項(xiàng)目開發(fā)中，經(jīng)常需要把程序運(yùn)行過程中各種信息記錄下來，有了詳細(xì)的日志有助于問題排查和功能優(yōu)化，但如何選擇和使用性能好功能強(qiáng)大的日志庫(kù)，這個(gè)就需要我們從多角度考慮2023-03-03
這篇文章主要介紹了golang映射Map的方法步驟，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-09-09
golang 數(shù)組隨機(jī)排序的實(shí)現(xiàn)
本文主要介紹了golang 數(shù)組隨機(jī)排序的實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-12-12
GO語(yǔ)言實(shí)現(xiàn)的http抓包分析工具pproxy介紹
這篇文章主要介紹了GO語(yǔ)言實(shí)現(xiàn)的http抓包分析工具pproxy介紹,本文同時(shí)對(duì)比了Fiddler、Charles等抓包軟件,需要的朋友可以參考下2015-03-03
這篇文章主要介紹了golang字符串本質(zhì)與原理詳解，golang中的字符串指的是所有8比特位字節(jié)字符串的集合，通常是UTF-8編碼的文本，更多相關(guān)內(nèi)容需要的小伙伴可以參考一下2022-06-06