diff --git a/6/step1.md b/6/step1.md new file mode 100644 index 0000000..3cc92c9 --- /dev/null +++ b/6/step1.md @@ -0,0 +1,69 @@ +# step1 何も見ずに解く + +3行の場合であれば、 +文字の先頭から1行目->2行目->3行目->2行目->1行目->2行目 +みたいな感じで進んでいって、各行の文字を左から見た文字を追加していけば良い。 + +Nを文字列の長さとすると、 +時間計算量はO(N) +空間計算量もO(N) +Nの最大値は1000なので余裕で1秒以内に間に合う。 + +```ruby +# @param {String} s +# @param {Integer} num_rows +# @return {String} +def convert(s, num_rows) + return s if num_rows == 1 + + chars_by_row = Array.new(num_rows) { [] } + row = 0 + is_down = true + s.each_char do |char| + chars_by_row[row] << char + + if row.zero? + is_down = true + row = 1 + elsif row == num_rows - 1 + is_down = false + row = num_rows - 2 + else + row = is_down ? row + 1 : row - 1 + end + end + chars_by_row.inject("") { |result, chars| result << chars.join } +end +``` + +Rubyの文字列はミュータブルなので以下のように書いてもコストは変わらない。 + +```ruby +# @param {String} s +# @param {Integer} num_rows +# @return {String} +def convert(s, num_rows) + return s if num_rows == 1 + + strings_by_row = Array.new(num_rows) { "" } + row = 0 + is_down = true + s.each_char do |char| + strings_by_row[row] << char + + if row.zero? + is_down = true + row = 1 + elsif row == num_rows - 1 + is_down = false + row = num_rows - 2 + else + row = is_down ? row + 1 : row - 1 + end + end + strings_by_row.join +end +``` + +むしろ手元でベンチマークをとったらこっちの方がわずかにパフォーマンスがよかった。 +わかりやすさは変わらないのでどっちでもいいな。 diff --git a/6/step2.md b/6/step2.md new file mode 100644 index 0000000..051f01b --- /dev/null +++ b/6/step2.md @@ -0,0 +1,26 @@ +# step2 他の方の解答を見る +- https://github.com/olsen-blue/Arai60/pull/61 + +step1で`is_down`としていたが、`is_going_down`の方がいいかも。`is_downward`とか。 +あとis_downの切り替えとrowの更新を同時にやらずに分けた方が見やすいな。 + +```ruby +# @param {String} s +# @param {Integer} num_rows +# @return {String} +def convert(s, num_rows) + return s if num_rows == 1 + + chars_by_row = Array.new(num_rows) { [] } + row = 0 + is_downward = true + s.each_char do |char| + chars_by_row[row] << char + + is_downward = true if row.zero? + is_downward = false if row == num_rows - 1 + row = is_downward ? row + 1 : row - 1 + end + chars_by_row.inject("") { |result, chars| result << chars.join } +end +``` diff --git a/6/step3.md b/6/step3.md new file mode 100644 index 0000000..92a9f7d --- /dev/null +++ b/6/step3.md @@ -0,0 +1,22 @@ +# step3 3回続けて10分以内に書いてエラーを出さなければOKとする + +```ruby +# @param {String} s +# @param {Integer} num_rows +# @return {String} +def convert(s, num_rows) + return s if num_rows == 1 + + strings_by_row = Array.new(num_rows) { "" } + row = 0 + is_downward = true + s.each_char do |char| + strings_by_row[row] << char + + is_downward = true if row.zero? + is_downward = false if row == num_rows - 1 + row = is_downward ? row + 1 : row - 1 + end + strings_by_row.join +end +``` diff --git a/6/step4.md b/6/step4.md new file mode 100644 index 0000000..5941ee1 --- /dev/null +++ b/6/step4.md @@ -0,0 +1 @@ +## step4 レビューを受けて解答を修正