diff --git a/213/step1.md b/213/step1.md new file mode 100644 index 0000000..dbf0a94 --- /dev/null +++ b/213/step1.md @@ -0,0 +1,44 @@ +# step1 何も見ずに解く +House Robber Iのように考えると、 +ある家まで見た時に盗める最大の金は +「①1つ前の家まで見た時に盗める最大の金」 or 「②2つ前の家まで見た時に盗める最大の金 + ある家で盗める金」 +の大きい方と考えたいところだが、①は問題ないが、②だとnumsの先頭から金を盗んでいる場合だと家が隣になるので答えにならない。 + +となると、②を先頭からは金を奪っていない条件で、2つ前の家まで見た時に盗める最大の金 + ある家で盗める金 +とすれば良い。 + +そうするとnumsの部分配列に関してHouse Robber Iと同様の考えを適用すれば良いことがわかる。 +時間計算量はO(N)で空間計算量もO(N) +Nは最大で100なので1秒以内で余裕で間に合う。 + +配列のスライスではなくインデックスを渡す方法もあるが今回は配列をそのまま渡している。 + +```ruby +# @param {Integer[]} moneys +# @return {Integer} +def rob(moneys) + moneys_size = moneys.size + return 0 if moneys_size == 0 + return moneys.max if moneys_size <= 3 + + [ + max_robbed_amount_in_line(moneys[0...(moneys_size - 1)]), + max_robbed_amount_in_line(moneys[1...(moneys_size - 2)]) + moneys.last + ].max +end + +def max_robbed_amount_in_line(moneys) + moneys_size = moneys.size + return moneys.last if moneys_size == 1 + + max_robbed_amounts = Array.new(moneys_size, 0) + max_robbed_amounts[0] = moneys[0] + max_robbed_amounts[1] = [moneys[0], moneys[1]].max + + (2...moneys_size).each do |i| + max_robbed_amounts[i] = [max_robbed_amounts[i - 1], max_robbed_amounts[i - 2] + moneys[i]].max + end + max_robbed_amounts.last +end +``` + diff --git a/213/step2.md b/213/step2.md new file mode 100644 index 0000000..66efb24 --- /dev/null +++ b/213/step2.md @@ -0,0 +1,45 @@ +# step2 他の方の解答を見る +## リストの分け方 +https://github.com/h1rosaka/arai60/pull/38/files#diff-ce0cd96bb02b9d0f849c47d3ecac921373d9a9834854c70c62942f51d909f929R37-R39 + +最初を含まないリスト、最後を含まないリストに関して計算して、それぞれの最大値を競わせる。 +こっちの方が書きやすいし読みやすい。 + +ついでに空間計算量O(1)で書いてみる。 +あと、ループを0から始めることもできるので書いてみる。 + +```ruby +# @param {Integer[]} moneys +# @return {Integer} +def rob(moneys) + moneys_size = moneys.size + return 0 if moneys_size == 0 + return moneys.max if moneys_size <= 3 + + [ + max_robbed_amount_in_line(moneys[0...(moneys_size - 1)]), + max_robbed_amount_in_line(moneys[1...moneys_size]) + ].max +end + +def max_robbed_amount_in_line(moneys) + max_robbed_amount_two_last = 0 + max_robbed_amount_one_last = 0 + max_robbed_amount = 0 + + moneys.each do |money| + max_robbed_amount = [max_robbed_amount_one_last, max_robbed_amount_two_last + money].max + max_robbed_amount_one_last, max_robbed_amount_two_last = max_robbed_amount, max_robbed_amount_one_last + end + max_robbed_amount +end +``` + +## ヘルパーメソッドの命名について +https://github.com/shintaro1993/arai60/pull/40/files#diff-b0cd43f46a2e0a4b323f085921c5e047630e92d6f24255ed62534e48d0f19ec4R114 + +元のメソッド名が`rob`で、円形に並んだ家から盗める最大値を返すことを期待している。 +この命名が良いかどうかは置いておいて、変えられないものとして考えると、`rob_xxx`といった名前が良いかもしれない。 +`rob_in_line`だと少し情報が少なすぎるか? + + diff --git a/213/step3.md b/213/step3.md new file mode 100644 index 0000000..0727d99 --- /dev/null +++ b/213/step3.md @@ -0,0 +1,25 @@ +# step3 3回続けて10分以内に書いてエラーを出さなければOKとする + +```ruby +# @param {Integer[]} moneys +# @return {Integer} +def rob(moneys) + moneys_size = moneys.size + return 0 if moneys_size == 0 + return moneys.first if moneys_size == 1 + + [rob_in_line(moneys[0...(moneys_size - 1)]), rob_in_line(moneys[1...moneys_size])].max +end + +def rob_in_line(moneys) + max_robbed_amount = 0 + max_robbed_amount_one_last = 0 + max_robbed_amount_two_last = 0 + + moneys.each do |money| + max_robbed_amount = [max_robbed_amount_two_last + money, max_robbed_amount_one_last].max + max_robbed_amount_one_last, max_robbed_amount_two_last = max_robbed_amount, max_robbed_amount_one_last + end + max_robbed_amount +end +``` diff --git a/213/step4.md b/213/step4.md new file mode 100644 index 0000000..5941ee1 --- /dev/null +++ b/213/step4.md @@ -0,0 +1 @@ +## step4 レビューを受けて解答を修正