LEETCODE，LeetCode:Generate Parentheses-函數-匯編語言學習筆記

LEETCODE，LeetCode:Generate Parentheses

2023-10-15 阅读 29 评论 0

摘要：題目鏈接 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: LEETCODE？"((()))", "(()())", "(())()", "()(())", "()()()

題目鏈接

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:

LEETCODE？"((()))", "(()())", "(())()", "()(())", "()()()"

所有組合的個數其實是一個卡特蘭數。

leetcode 1，我們這樣來構造一個合法的字符串：首先第一個位置肯定是“（”，對于后面位置:

1、如果前一個字符是“（”：那么我們可以在當前位置上加入“）”（字符“）”一定有剩余）；如果“（”字符還有剩余，也可以在當前位置加入“（” ? ? ? ? ? ? ? ? ? ? ? ? ?本文地址

2、如果前一個字符是“）”：如果當前“（”和“）”剩余的數目不同（即其那面的括號沒有完全匹配），可以在當前位置上加入“）”；如果“（”字符還有剩余，也可以在當前位置加入“（”

 1 class Solution {
 2 public:
 3     vector<string> generateParenthesis(int n) {
 4         string tmpres(n<<1, '(');
 5         vector<string> res;
 6         helper(1, tmpres, res, n-1, n);
 7         return res;
 8     }
 9 private:
10     void helper(int index, string &tmpres, vector<string>&res, int leftNum, int rightNum)
11     {
12         if(index >= tmpres.size()){res.push_back(tmpres); return;}
13         if(tmpres[index-1] == '(')
14         {
15             tmpres[index] = ')';
16             helper(index+1, tmpres, res, leftNum, rightNum-1);
17             if(leftNum > 0)
18             {
19                 tmpres[index] = '(';
20                 helper(index+1, tmpres, res, leftNum-1, rightNum);
21             }
22         }
23         else
24         {
25             if(leftNum != rightNum)
26             {
27                 tmpres[index] = ')';
28                 helper(index+1, tmpres, res, leftNum, rightNum-1);
29             }
30             if(leftNum > 0)
31             {
32                 tmpres[index] = '(';
33                 helper(index+1, tmpres, res, leftNum-1, rightNum);
34             }
35         }
36     }
37 };

leetcode all in one，其實對于某個合法的字符串，我們可以發現從合法字符串的任何一個位置看，“（”的數目 >= ")"的數目，即剩余的“（”的數目 <= 剩余的"）"數目, 因此就有以下更加簡潔的代碼

 1 class Solution {
 2 public:
 3     vector<string> generateParenthesis(int n) {
 4         string tmpres;
 5         vector<string> res;
 6         helper(tmpres, res, n, n);
 7         return res;
 8     }
 9 private:
10     void helper(string &tmpres, vector<string>&res, int leftNum, int rightNum)
11     {
12         if(leftNum > rightNum)return;
13         if(leftNum == 0 && rightNum == 0)
14         {
15             res.push_back(tmpres);
16             return;
17         }
18         if(leftNum > 0)
19         {
20             tmpres.push_back('(');
21             helper(tmpres, res, leftNum-1, rightNum);
22             tmpres.pop_back();
23         }
24         if(rightNum > 0)
25         {
26             tmpres.push_back(')');
27             helper(tmpres, res, leftNum, rightNum-1);
28             tmpres.pop_back();
29         }
30     }
31 };

轉載于:https://www.cnblogs.com/TenosDoIt/p/3776583.html

原文链接：https://hbdhgg.com/3/139251.html

发表评论: