資訊專欄INFORMATION COLUMN
摘要：代碼不過(guò)這一題標(biāo)準(zhǔn)的解法是回溯法。回溯法在生成全集的過(guò)程中進(jìn)行剪枝，使得效率最大。并且不需要判重，因?yàn)榛厮菥褪且淮涡陨扇圆粫?huì)重復(fù)。
題目地址：
https://leetcode-cn.com/probl...
題目描述：
給出 n 代表生成括號(hào)的對(duì)數(shù)，請(qǐng)你寫(xiě)出一個(gè)函數(shù)，使其能夠生成所有可能的并且有效的括號(hào)組合。
例如，給出 n = 3，生成結(jié)果為：
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
解答：
這一題可以用遞歸來(lái)做，若現(xiàn)在有n-1對(duì)的有效括號(hào)組合，求第n對(duì)的有序括號(hào)組合，只需要在n-1對(duì)的組成中不斷添加"()"就可以保證生成有效的括號(hào)組合，不過(guò)這樣可能會(huì)重復(fù)，因此再使用一個(gè)hash表來(lái)去重。
java ac代碼:
class Solution {
HashSet set = new HashSet(2000);
public List generateParenthesis(int n) {
List ans = new ArrayList();
if(n == 1)
{
ans.add("()");
set.add("()");
return ans;
}
Listtemp = generateParenthesis(n-1);
for(String s:temp)
{
int k = 0;
while(k < s.length()){
if(!set.contains(s.substring(0,k+1)+"()"+s.substring(k+1))){
ans.add(s.substring(0,k+1)+"()"+s.substring(k+1));
set.add(s.substring(0,k+1)+"()"+s.substring(k+1));
}
k++;
}
}
return ans;
}
}
不過(guò)這一題標(biāo)準(zhǔn)的解法是回溯法?；厮莘ㄔ谏扇倪^(guò)程中進(jìn)行剪枝，使得效率最大。并且不需要判重，因?yàn)榛厮菥褪且淮涡陨扇圆粫?huì)重復(fù)。剪枝需要用到兩個(gè)變量，一個(gè)是當(dāng)前過(guò)程中左括號(hào)數(shù)量l和當(dāng)前過(guò)程中右括號(hào)數(shù)量r，若r>l則一定無(wú)解，則剪去這個(gè)部分。
java ac代碼：
class Solution {
List ans = new ArrayList();
public List generateParenthesis(int n) {
char[]temp = new char[n*2];
temp[0] = "(";
backtrack(1,n*2,1,0,temp);
return ans;
}
void backtrack(int i,int n,int l,int r,char[]temp)
{
if(i == n)
{
if(l == r)
ans.add(new String(temp));
return;
}
if(r>l)return;
temp[i] = "(";
backtrack(i+1,n,l+1,r,temp);
temp[i] = ")";
backtrack(i+1,n,l,r+1,temp);
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/73381.html
摘要：題目地址題目描述給定一個(gè)二叉樹(shù)和一個(gè)目標(biāo)和，找到所有從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)路徑總和等于給定目標(biāo)和的路徑。說(shuō)明葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。示例給定如下二叉樹(shù)，以及目標(biāo)和，返回解答遞歸。以的右子樹(shù)為根并且和為的路徑加上若該路徑存在。 題目地址：https://leetcode-cn.com/probl...題目描述：給定一個(gè)二叉樹(shù)和一個(gè)目標(biāo)和，找到所有從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)路徑總和等于給定目標(biāo)和...
摘要：示例輸入輸出解釋答案應(yīng)為除去外，在區(qū)間內(nèi)的所有數(shù)字。即這個(gè)數(shù)最多位。解答這一題就是利用回溯法求組合數(shù)，從這個(gè)集合中求。 題目地址：https://leetcode-cn.com/probl...題目描述：給定一個(gè)非負(fù)整數(shù) n，計(jì)算各位數(shù)字都不同的數(shù)字 x 的個(gè)數(shù)，其中 0 ≤ x < 10的n次方 。 示例: 輸入: 2輸出: 91 解釋: 答案應(yīng)為除去 11,22,33,44,55,...
摘要：圖因此可以成為樹(shù)，在所有可能的樹(shù)中，具有最小高度的樹(shù)被稱為最小高度樹(shù)。給出這樣的一個(gè)圖，寫(xiě)出一個(gè)函數(shù)找到所有的最小高度樹(shù)并返回他們的根節(jié)點(diǎn)。因此使用一個(gè)數(shù)組代表每個(gè)節(jié)點(diǎn)的入度，若入度為就是葉子節(jié)點(diǎn)。 題目地址：https://leetcode-cn.com/probl...題目描述： 對(duì)于一個(gè)具有樹(shù)特征的無(wú)向圖，我們可選擇任何一個(gè)節(jié)點(diǎn)作為根。圖因此可以成為樹(shù)，在所有可能的樹(shù)中，具有最小...
摘要：關(guān)于遞歸這里提一兩點(diǎn)遞歸基本有這幾步遞歸的模板，終止條件，遞歸調(diào)用，邏輯處理。 ?作者簡(jiǎn)介：大家好，我是車(chē)神哥，府學(xué)路18號(hào)的車(chē)神? ?個(gè)人主頁(yè)：應(yīng)無(wú)所住而生...
閱讀 2406·2021-10-09 09:44
閱讀 2139·2021-10-08 10:05
閱讀 3431·2021-07-26 23:38
閱讀 3008·2019-08-28 18:16
閱讀 820·2019-08-26 11:55
閱讀 1827·2019-08-23 18:29
閱讀 2042·2019-08-23 18:05
閱讀 1372·2019-08-23 17:02
