iT邦幫忙

2

【小馬的LeetCode練功坊】22. Generate Parentheses (Medium)

參考題目: LeetCode- 22. Generate Parentheses

題目: 給定一個正整數n,回傳所有合法的n對括號,

input: n = 3
output:
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

解析: 這是一道蠻經典的問題,
要是合法的n對括號,
那麼右括號的數量永遠不能大於左括號,
我是採用deque的方式解,
定義一個結構,記錄括號字串、
再用兩個整數記錄目前用的左、右括號數量

如果左括號還沒用到n個,則可以添加左括號;
如果左括號數量>右括號數量,則可以添加右括號

C++解法(窮舉法、4ms)

class Solution {
struct parenthesis{
    string expr;
    int left;
    int right;    
};
public:
    vector<string> generateParenthesis(int n) {
        deque<parenthesis> res = {{"(",1,0}};
        while(res.front().left< n || res.front().right< n){
            parenthesis p = res.front();
            string c = p.expr;
            int left = p.left, right=p.right;
            res.pop_front();
            if(left<n){
                res.push_back({c+'(', left+1, right});
            }
            if(right<n && left>right)
                res.push_back({c+')', left, right+1});
        }
        vector<string> ans;
        for(auto r: res){
            ans.push_back(r.expr);
        }
        return ans;
    }
};

python 解法(窮舉法、24ms)

from collections import deque
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = deque([('(',1,0)])
        while res[0][1]< n or res[0][2]< n:
            c, left, right = res.popleft()
            if left<n:
                res.append((c+'(', left+1, right))
            if right<n and left>right:
                res.append((c+')', left, right+1))
        return [r[0] for r in res]

zerojudge類似題的解析

挑戰完此題後,小馬緊接著挑戰zerojudge上面有一道類似題
題目: zerojudge- a229: 括號匹配問題

小馬將在leetcode上解好的程式拿來解這題,
卻發現不論是python解或是c++解都會超時,
先上第一個嘗試的解法:
(所以說感覺某些問題zerojudge比leetcode還要難,程式執行時間有些嚴格)

解法一: 用leetcode上的解存下所有的答案(TLE, 超時)

#include <iostream>
#include <vector>
#include <string>
#include <deque>
using namespace std;

struct parenthesis{
    string expr;
    int left;
    int right;    
};

vector<string> generateParenthesis(int n) {
    deque<parenthesis> res = {{"(",1,0}};
    while(res.front().left< n || res.front().right< n){
        parenthesis p = res.front();
        string c = p.expr;
        int left = p.left, right=p.right;
        res.pop_front();
        if(left<n){
            res.push_back({c+'(', left+1, right});
        }
        if(right<n && left>right)
            res.push_back({c+')', left, right+1});
    }
    vector<string> ans;
    for(auto r: res){
        ans.push_back(r.expr);
    }
    return ans;
}

int main()
{
    int n;
    while(cin >> n){
        vector<string> result= generateParenthesis(n);
        for(string r : result){
            cout<<r<<endl;
        }
    }
    return 0;
}

於是小馬仔細思索超時的原因,
應該是此題並不像leetcode要求把所有的答案存下來並回傳,
所以其實可以只用一個字串,
在搜索過程中,如果一旦搜到一組答案即印出來,
避免花大量空間儲存答案

第二即是常見的問題,C語言的scanf, printf比c++的cin, cout來的快,
嘗試用scanf, printf取代cin, cout,
這兩個優化都做了才過關

解法二: 節省空間,搜到答案即印出(AC)

#include <iostream>
#include <string>
using namespace std;

void generateParenthesis(string &res, int left, int right, int n) {
    if(left==n && right==n){
        printf("%s\n", res.c_str());
        return;
    }
    int now = left+right;
    if(left<n){
        res[now]='(';
        generateParenthesis(res, left+1, right, n);
    }
    if(right<n && left>right){
        res[now]=')';
        generateParenthesis(res, left, right+1, n);
    }
}

int main()
{
    int n;
    while(scanf("%d", &n)!= EOF){
        string res(2*n, '0');
        generateParenthesis(res, 0, 0, n);
    }
    return 0;
}

尚未有邦友留言

立即登入留言