成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

leetcode22. Generate Parentheses

騫諱護(hù) / 821人閱讀

摘要：當(dāng)右括號(hào)和左括號(hào)的剩余量均為時(shí)，及為一個(gè)最終結(jié)果。而則會(huì)在直接原來(lái)的對(duì)象上進(jìn)行修改，其指針仍然指向原來(lái)的對(duì)象。因此在遞歸的過(guò)程中使用一定要注意，對(duì)對(duì)象的修改不要相互干擾。

題目要求 
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

即生成成對(duì)的括號(hào)，其中括號(hào)的數(shù)量為n

思路和代碼

這題還是一道典型的在前一種情況的前提下生成當(dāng)前的情況(backtracking)。這樣的題目往往需要通過(guò)遞歸的方式來(lái)間接記錄當(dāng)前的情況。
類似的題目還包括


combination sum 和 combination sum II




Permutations 和 Permutations II

我們只需要確保即將生成的結(jié)果中右括號(hào)的數(shù)量不會(huì)超過(guò)左括號(hào)即可。當(dāng)右括號(hào)和左括號(hào)的剩余量均為0時(shí)，及為一個(gè)最終結(jié)果。如果左右括號(hào)的剩余量還未達(dá)到0，則將繼續(xù)添加左括號(hào)或是右括號(hào)直到左右括號(hào)剩余量為0。
代碼如下：

    public List generateParenthesis(int n) {
        List result = new ArrayList();
        if(n<=0){
            return result;
        }
        generateParenthesis(result, "(", n-1, n);
        return result;
        
    }
    
    private void generateParenthesis(List result, String current, int leftRemainCount, int rightRemainCount){
        if(leftRemainCount==0){
            while(rightRemainCount-->0){
                current += ")";
            }
            result.add(current);
            return;
        }
        generateParenthesis(result, current+"(", leftRemainCount-1, rightRemainCount);
        if(rightRemainCount>leftRemainCount){
            generateParenthesis(result, current+")", leftRemainCount, rightRemainCount-1);
        }
    }
利用StringBuilder簡(jiǎn)單優(yōu)化

String和StringBuilder的最大區(qū)別在于，對(duì)String的任何修改都會(huì)生成一個(gè)新的String對(duì)象，并將當(dāng)前的String指針指向該新生成的對(duì)象。在字符串修改頻繁的場(chǎng)景下可能會(huì)帶來(lái)大量的內(nèi)存浪費(fèi)。而StringBuilder則會(huì)在直接原來(lái)的對(duì)象上進(jìn)行修改，其指針仍然指向原來(lái)的對(duì)象。因此在遞歸的過(guò)程中使用StringBuilder一定要注意，對(duì)StringBuilder對(duì)象的修改不要相互干擾。
代碼如下：

    public List generateParenthesis2(int n) {
        List rst = new ArrayList<>();
        if(n == 0) {
          return rst;     
        }
        backtracking(rst, new StringBuilder(), n, n);
        return rst;
    }
    private void backtracking(List rst, StringBuilder sb, int left, int right) {
        if(left > right) {
          return;    
        }
        if(left > 0) {
          sb.append("(");
          backtracking(rst, sb, left - 1, right);
          sb.setLength(sb.length() - 1);
        }
        if(right > 0) {
          sb.append(")");
          backtracking(rst, sb, left, right - 1);
          sb.setLength(sb.length() - 1);
        }
        
        if(left == 0 && right == 0) {
          rst.add(sb.toString());  
        }
    }


想要了解更多開(kāi)發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/67100.html

相關(guān)文章

  • LeetCode[22] Generate Parentheses

    摘要：復(fù)雜度思路注意的地方，要限制左括號(hào)和右括號(hào)。每出現(xiàn)一次左括號(hào)，就相對(duì)于限定了，最多只能出現(xiàn)那么多右括號(hào)。所以，為了完成這種限定，用來(lái)控制。不然會(huì)有的情況出現(xiàn)。 LeetCode[22] Generate Parentheses Given n pairs of parentheses, write a function to generate all combinations of ...

    Jonathan Shieber 評(píng)論0 收藏0

  • [LeetCode] 22. Generate Parentheses

    Problem Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is: [ ((())), (()()), (())(), ()(()), ...

    curlyCheng 評(píng)論0 收藏0

  • leetcode 22 Generate Parentheses

    摘要：要求返回一個(gè)中包含組括號(hào)所有可能的符合規(guī)則的組合。例如輸入結(jié)果集應(yīng)當(dāng)是想法輸入的就代表著我們的字符串的組成是個(gè)和個(gè)。我們需要跟蹤和的使用情況，來(lái)判斷下一步的操作是否合法。 題目詳情 Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses....

    figofuture 評(píng)論0 收藏0

  • [Leetcod] Generate Parentheses 產(chǎn)生括號(hào)

    摘要：而對(duì)于右括號(hào)，必須前面放了一個(gè)左括號(hào)，我們才能放一個(gè)右括號(hào)。所以我們根據(jù)剩余可放置左括號(hào)，和剩余可放置右括號(hào)，代入遞歸，就可以求解。 Generate Parentheses 最新更新請(qǐng)見(jiàn)：https://yanjia.me/zh/2019/01/... Given n pairs of parentheses, write a function to generate all co...

    Ilikewhite 評(píng)論0 收藏0

  • leetcode 部分解答索引（持續(xù)更新～）

    摘要：前言從開(kāi)始寫相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒(méi)有按順序?qū)懍F(xiàn)在翻起來(lái)覺(jué)得蠻亂的?？赡艽蠹铱粗卜浅２环奖?。所以在這里做個(gè)索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開(kāi)始寫leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒(méi)有按順序?qū)憽F(xiàn)在翻起來(lái)覺(jué)得蠻亂的?？赡艽蠹铱粗卜浅２环奖?。所以在這里做個(gè)索引嘻嘻。 順序整理 1~50 1...

    leo108 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<