{"id":1862,"date":"2016-03-07T15:06:04","date_gmt":"2016-03-07T07:06:04","guid":{"rendered":"http:\/\/boweihe.me\/?p=1862"},"modified":"2016-03-07T15:06:04","modified_gmt":"2016-03-07T07:06:04","slug":"leetcode-22-generate-parentheses","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=1862","title":{"rendered":"LeetCode 22. Generate Parentheses"},"content":{"rendered":"

\u9898\u76ee\uff1a<\/strong>https:\/\/leetcode.com\/problems\/generate-parentheses\/
\n\u601d\u8def\uff1a<\/strong>
\n\u4e3b\u8981\u95ee\u9898\u662f\uff0c\u4ec0\u4e48\u65f6\u5019\u53ef\u4ee5\u52a0\u5de6\u62ec\u53f7\uff0c\u4ec0\u4e48\u65f6\u5019\u53ef\u4ee5\u52a0\u53f3\u62ec\u53f7\u3002\u8fd9\u9700\u8981\u5224\u65ad\u5f53\u524d\u5df2\u6709\u5b57\u4e32\u7684\u5de6\u53f3\u62ec\u53f7\u4e2a\u6570\uff0c\u6709\u4ee5\u4e0b\u4e09\u79cd\u60c5\u51b5\uff1a<\/p>\n

    \n
  1. \u5982\u679c\u5f53\u524d\u5de6\u62ec\u53f7\u7684\u6570\u76ee\u7b49\u4e8e(\u4e5f\u53ef\u4ee5\u8bf4\u5c0f\u7b49\u4e8e\uff0c\u4e0d\u8fc7\u5c0f\u4e8e\u7684\u60c5\u51b5\u662f\u51fa\u9519\u4e86)\u53f3\u62ec\u53f7\u4e86\uff0c\u6bd4\u5982()<\/em>\uff0c\u90a3\u53ea\u80fd\u52a0\u5de6\u62ec\u53f7\uff1b<\/li>\n
  2. \u5982\u679c\u5f53\u524d\u5de6\u62ec\u53f7\u6570\u76ee\u5927\u4e8e\u53f3\u62ec\u53f7\uff0c\u6bd4\u5982((()\uff0c<\/em>\u90a3\u4e48\n
      \n
    1. \u5982\u679c\u8fd8\u6709\u5269\u5de6\u62ec\u53f7\u7684\u914d\u989d\uff0c\u53ef\u4ee5\u52a0\u5de6\u62ec\u53f7\uff08\u65b0\u5206\u652f\u4e86\uff09\uff1b<\/li>\n
    2. \u5426\u5219\u53ea\u80fd\u52a0\u53f3\u62ec\u53f7\uff08\u5728\u539f\u6709\u7b54\u6848\u4e0a\u64cd\u4f5c\u5373\u53ef\uff09\uff1b<\/li>\n<\/ol>\n<\/li>\n<\/ol>\n

      \u4ee3\u7801\uff1a<\/strong><\/p>\n

      class Solution {\npublic:\n\tvector<string> generateParenthesis(int n) {\n\t\tvector<string> results;\n\t\tvector<pair<int, int>> parSize;\n\t\t\/\/ If size('(') <= size(')'), we can only append '(';\n\t\t\/\/ Else, append '(' or ')' if it doesn't reach the quota\n\t\tint count = 1;\n\t\tresults.push_back(string(\"(\"));\n\t\tparSize.push_back(pair<int, int>(1, 0));\n\t\tint resultSz;\n\t\twhile (count < n * 2) {\n\t\t\tresultSz = results.size();\n\t\t\tint lsize, rsize;\n\t\t\tfor (int i = 0; i<resultSz; i++) {\n\t\t\t\tlsize = parSize[i].first;\n\t\t\t\trsize = parSize[i].second;\n\t\t\t\tif (lsize <= rsize) {\n\t\t\t\t\tresults[i] += \"(\";\n\t\t\t\t\tparSize[i].first++;\n\t\t\t\t}\n\t\t\t\telse {\n\t\t\t\t\tif (lsize < n) {\n\t\t\t\t\t\tstring cpStr = results[i] + \"(\";\n\t\t\t\t\t\tpair<int, int> cpSz = parSize[i];\n\t\t\t\t\t\tcpSz.first++;\n\t\t\t\t\t\tresults.push_back(cpStr);\n\t\t\t\t\t\tparSize.push_back(cpSz);\n\t\t\t\t\t}\n\t\t\t\t\tresults[i] += \")\";\n\t\t\t\t\tparSize[i].second++;\n\t\t\t\t}\n\t\t\t}\n\t\t\tcount++;\n\t\t}\n\t\treturn results;\n\t}\n};<\/pre>\n
       <\/p>\n","protected":false},"excerpt":{"rendered":"
      \u9898\u76ee\uff1ahttps:\/\/leetcode.com\/problems\/generate-parentheses\/ \u601d\u8def\uff1a \u4e3b\u8981\u95ee\u9898\u662f\uff0c\u4ec0\u4e48\u65f6\u5019\u53ef\u4ee5\u52a0\u5de6\u62ec\u53f7\uff0c\u4ec0\u4e48\u65f6\u5019\u53ef\u4ee5\u52a0\u53f3\u62ec\u53f7\u3002\u8fd9\u9700\u8981\u5224\u65ad\u5f53\u524d\u5df2\u6709\u5b57\u4e32\u7684\u5de6\u53f3\u62ec\u53f7\u4e2a\u6570\uff0c\u6709\u4ee5\u4e0b\u4e09\u79cd\u60c5\u51b5\uff1a \u5982\u679c\u5f53\u524d\u5de6\u62ec\u53f7\u7684\u6570\u76ee\u7b49\u4e8e(\u4e5f\u53ef\u4ee5\u8bf4\u5c0f\u7b49\u4e8e\uff0c\u4e0d\u8fc7\u5c0f\u4e8e\u7684\u60c5\u51b5\u662f\u51fa\u9519\u4e86)\u53f3\u62ec\u53f7\u4e86\uff0c\u6bd4\u5982()\uff0c\u90a3\u53ea\u80fd\u52a0\u5de6\u62ec\u53f7\uff1b \u5982\u679c\u5f53\u524d\u5de6\u62ec\u53f7\u6570\u76ee\u5927\u4e8e\u53f3\u62ec\u53f7\uff0c\u6bd4\u5982((()\uff0c\u90a3\u4e48 \u5982\u679c\u8fd8\u6709\u5269\u5de6\u62ec\u53f7\u7684\u914d\u989d\uff0c\u53ef\u4ee5\u52a0\u5de6\u62ec\u53f7\uff08\u65b0\u5206\u652f\u4e86\uff09\uff1b \u5426\u5219\u53ea\u80fd\u52a0\u53f3\u62ec\u53f7\uff08\u5728\u539f\u6709\u7b54\u6848\u4e0a\u64cd\u4f5c\u5373\u53ef\uff09\uff1b \u4ee3\u7801\uff1a class Solution { public: vector<string> generateParenthesis(int n) { vector<string> results; vector<pair<int, int>> parSize; \/\/ If size(‘(‘) <= size(‘)’), we can only append ‘(‘; \/\/ Else, append ‘(‘ or ‘)’ if it doesn’t reach the quota int count = 1; results.push_back(string(“(“)); parSize.push_back(pair<int, int>(1, 0)); int resultSz; while (count […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[66],"class_list":["post-1862","post","type-post","status-publish","format-standard","hentry","category-study","tag-leetcode-oj"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/1862","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1862"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/1862\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1862"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1862"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1862"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}