資訊專欄INFORMATION COLUMN
摘要：代碼不過這一題標準的解法是回溯法?；厮莘ㄔ谏扇倪^程中進行剪枝，使得效率最大。并且不需要判重，因為回溯就是一次性生成全集，所以不會重復。
題目地址：
https://leetcode-cn.com/probl...
題目描述：
給出 n 代表生成括號的對數(shù)，請你寫出一個函數(shù)，使其能夠生成所有可能的并且有效的括號組合。
例如，給出 n = 3，生成結(jié)果為：
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
解答：
這一題可以用遞歸來做，若現(xiàn)在有n-1對的有效括號組合，求第n對的有序括號組合，只需要在n-1對的組成中不斷添加"()"就可以保證生成有效的括號組合，不過這樣可能會重復，因此再使用一個hash表來去重。
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;
}
}
不過這一題標準的解法是回溯法?；厮莘ㄔ谏扇倪^程中進行剪枝，使得效率最大。并且不需要判重，因為回溯就是一次性生成全集，所以不會重復。剪枝需要用到兩個變量，一個是當前過程中左括號數(shù)量l和當前過程中右括號數(shù)量r，若r>l則一定無解，則剪去這個部分。
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)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/73381.html
摘要：題目地址題目描述給定一個二叉樹和一個目標和，找到所有從根節(jié)點到葉子節(jié)點路徑總和等于給定目標和的路徑。說明葉子節(jié)點是指沒有子節(jié)點的節(jié)點。示例給定如下二叉樹，以及目標和，返回解答遞歸。以的右子樹為根并且和為的路徑加上若該路徑存在。 題目地址：https://leetcode-cn.com/probl...題目描述：給定一個二叉樹和一個目標和，找到所有從根節(jié)點到葉子節(jié)點路徑總和等于給定目標和...
摘要：示例輸入輸出解釋答案應(yīng)為除去外，在區(qū)間內(nèi)的所有數(shù)字。即這個數(shù)最多位。解答這一題就是利用回溯法求組合數(shù)，從這個集合中求。 題目地址：https://leetcode-cn.com/probl...題目描述：給定一個非負整數(shù) n，計算各位數(shù)字都不同的數(shù)字 x 的個數(shù)，其中 0 ≤ x < 10的n次方 。 示例: 輸入: 2輸出: 91 解釋: 答案應(yīng)為除去 11,22,33,44,55,...
摘要：圖因此可以成為樹，在所有可能的樹中，具有最小高度的樹被稱為最小高度樹。給出這樣的一個圖，寫出一個函數(shù)找到所有的最小高度樹并返回他們的根節(jié)點。因此使用一個數(shù)組代表每個節(jié)點的入度，若入度為就是葉子節(jié)點。 題目地址：https://leetcode-cn.com/probl...題目描述： 對于一個具有樹特征的無向圖，我們可選擇任何一個節(jié)點作為根。圖因此可以成為樹，在所有可能的樹中，具有最小...
摘要：關(guān)于遞歸這里提一兩點遞歸基本有這幾步遞歸的模板，終止條件，遞歸調(diào)用，邏輯處理。 ?作者簡介：大家好，我是車神哥，府學路18號的車神? ?個人主頁：應(yīng)無所住而生...
閱讀 2488·2021-10-09 09:44
閱讀 2228·2021-10-08 10:05
閱讀 3513·2021-07-26 23:38
閱讀 3124·2019-08-28 18:16
閱讀 893·2019-08-26 11:55
閱讀 1911·2019-08-23 18:29
閱讀 2130·2019-08-23 18:05
閱讀 1437·2019-08-23 17:02
