diff --git a/22/step1.md b/22/step1.md new file mode 100644 index 0000000..4721e88 --- /dev/null +++ b/22/step1.md @@ -0,0 +1,65 @@ +# step1 何も見ずに解く + +backtracking を使う。 + +- `(`の数が n 個より少なければ`(`を 1 つつなげる +- `)`の数が`(`より少なければ`)`を 1 つつなげる + +というパターンで分類。`)`の数が n と一致した時に parenthesis が完成するので答えに含める。 + +```ruby +# @param {Integer} n +# @return {String[]} +def generate_parenthesis(n) + combinations = [] + generate_parenthesis_helper = lambda do |parenthesis, left ,right| + if right == n + combinations << parenthesis.join + return + end + if left < n + parenthesis << "(" + generate_parenthesis_helper.call(parenthesis, left + 1, right) + parenthesis.pop + end + if right < left + parenthesis << ")" + generate_parenthesis_helper.call(parenthesis, left, right + 1) + parenthesis.pop + end + end + generate_parenthesis_helper.call([], 0, 0) + combinations +end +``` + +他には、 +可能なだけ左を入れる + 右を一つ入れる +という分類もできる。 + +```ruby +# @param {Integer} n +# @return {String[]} +def generate_parenthesis(n) + combinations = [] + generate_parenthesis = lambda do |parenthesis, left ,right| + if right == n + combinations << parenthesis.join + return + end + (1..(n - left)).each do |i| + i.times { parenthesis << "(" } + parenthesis << ")" + generate_parenthesis.call(parenthesis, left + i, right + 1) + (i + 1).times { parenthesis.pop } + end + if left > right + parenthesis << ")" + generate_parenthesis.call(parenthesis, left, right + 1) + parenthesis.pop + end + end + generate_parenthesis.call([], 0, 0) + combinations +end +``` diff --git a/22/step2.md b/22/step2.md new file mode 100644 index 0000000..170c970 --- /dev/null +++ b/22/step2.md @@ -0,0 +1,30 @@ +# step2 他の方の解答を見る +https://github.com/olsen-blue/Arai60/pull/54/files/a0087de7fa136c0c271a07ec29a364c67f40d849#r2022389382 + +> はじめの括弧とそれに対応する括弧に注目して「(A)B」と分けるのも分類ですね。 + +この考え方は全く頭になかった。 + +```ruby +# @param {Integer} n +# @return {String[]} +def generate_parenthesis(n) + return [""] if n == 0 + + combinations = [] + n.times do |i| + lefts = generate_parenthesis(i) + rights = generate_parenthesis(n - i - 1) + lefts.each do |left| + rights.each do |right| + combinations << "(" + left + ")" + right + end + end + end + combinations +end +``` + + +https://github.com/tokuhirat/LeetCode/pull/53/files#diff-edeaf9ab4fec143afff62d1f44e6f5d9ca2d7c345ff74d8c89f41ee178034827R81-R101 +使った括弧の数か、残りの括弧の数か。 diff --git a/22/step3.md b/22/step3.md new file mode 100644 index 0000000..78d8a01 --- /dev/null +++ b/22/step3.md @@ -0,0 +1,27 @@ +# step3 3回続けて10分以内に書いてエラーを出さなければOKとする + +```ruby +# @param {Integer} n +# @return {String[]} +def generate_parenthesis(n) + result = [] + generate_parenthesis_helper = lambda do |left, right, parenthesis| + if right == n + result << parenthesis.join + return + end + if left < n + parenthesis << "(" + generate_parenthesis_helper.call(left + 1, right, parenthesis) + parenthesis.pop + end + if right < left + parenthesis << ")" + generate_parenthesis_helper.call(left, right + 1, parenthesis) + parenthesis.pop + end + end + generate_parenthesis_helper.call(0, 0, []) + result +end +``` diff --git a/22/step4.md b/22/step4.md new file mode 100644 index 0000000..5941ee1 --- /dev/null +++ b/22/step4.md @@ -0,0 +1 @@ +## step4 レビューを受けて解答を修正