力扣(LeetCode)22

dack 發布于2019-08-16 15:16 / 3506人閱讀

摘要：代碼不過這一題標準的解法是回溯法。回溯法在生成全集的過程中進行剪枝，使得效率最大。并且不需要判重，因為回溯就是一次性生成全集，所以不會重復。

題目地址：
https://leetcode-cn.com/probl...
題目描述：
給出 n 代表生成括號的對數，請你寫出一個函數，使其能夠生成所有可能的并且有效的括號組合。

例如，給出 n = 3，生成結果為：

[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
解答：
這一題可以用遞歸來做，若現在有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;
        
    }
}

不過這一題標準的解法是回溯法。回溯法在生成全集的過程中進行剪枝，使得效率最大。并且不需要判重，因為回溯就是一次性生成全集，所以不會重復。剪枝需要用到兩個變量，一個是當前過程中左括號數量l和當前過程中右括號數量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);
        
    }
}

云服務器 GPU云服務器力扣 LeetCode LeetCode_String leetcode_35_SearchIn

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/73381.html

力扣(LeetCode)113

摘要：題目地址題目描述給定一個二叉樹和一個目標和，找到所有從根節點到葉子節點路徑總和等于給定目標和的路徑。說明葉子節點是指沒有子節點的節點。示例給定如下二叉樹，以及目標和，返回解答遞歸。以的右子樹為根并且和為的路徑加上若該路徑存在。題目地址：https://leetcode-cn.com/probl...題目描述：給定一個二叉樹和一個目標和，找到所有從根節點到葉子節點路徑總和等于給定目標和...

HelKyle 2019-08-16 15:37 評論0 收藏0
力扣(LeetCode)357

摘要：示例輸入輸出解釋答案應為除去外，在區間內的所有數字。即這個數最多位。解答這一題就是利用回溯法求組合數，從這個集合中求。題目地址：https://leetcode-cn.com/probl...題目描述：給定一個非負整數 n，計算各位數字都不同的數字 x 的個數，其中 0 ≤ x < 10的n次方。示例: 輸入: 2輸出: 91 解釋: 答案應為除去 11,22,33,44,55,...

JasinYip 2019-08-16 15:17 評論0 收藏0
力扣(LeetCode)310

摘要：圖因此可以成為樹，在所有可能的樹中，具有最小高度的樹被稱為最小高度樹。給出這樣的一個圖，寫出一個函數找到所有的最小高度樹并返回他們的根節點。因此使用一個數組代表每個節點的入度，若入度為就是葉子節點。題目地址：https://leetcode-cn.com/probl...題目描述：對于一個具有樹特征的無向圖，我們可選擇任何一個節點作為根。圖因此可以成為樹，在所有可能的樹中，具有最小...

amuqiao 2019-08-16 16:13 評論0 收藏0
＜LeetCode天梯＞Day026 反轉鏈表（遞歸法+（迭代法）雙鏈表法） | 初級算法 | Py

摘要：關于遞歸這里提一兩點遞歸基本有這幾步遞歸的模板，終止條件，遞歸調用，邏輯處理。 ?作者簡介：大家好，我是車神哥，府學路18號的車神? ?個人主頁：應無所住而生...

imingyu 2021-11-17 09:33 評論0 收藏0