diff --git a/283/step1.md b/283/step1.md new file mode 100644 index 0000000..5253a08 --- /dev/null +++ b/283/step1.md @@ -0,0 +1,31 @@ +# step1 何も見ずに解く + +以下を行うとよさそう +0,1の位置にそれぞれleft,rightをおく +- leftの位置に0がない時はそれぞれ1進める +- leftの位置に0がある時 + - rightの位置に0以外がある時は交換して、それぞれ1進める + - rightの位置に0がある時はrightを1進める + +時間計算量はO(N)で、空間計算量はO(1) +Nの最大値は10^4なので1秒以内に間に合う + +```ruby +# @param {Integer[]} nums +# @return {Void} Do not return anything, modify nums in-place instead. +def move_zeroes(nums) + return nums if nums.size <= 1 + + left = 0 + (1...(nums.size)).each do |right| + if !nums[left].zero? + left += 1 + next + end + if !nums[right].zero? + nums[left], nums[right] = nums[right], nums[left] + left += 1 + end + end +end +``` diff --git a/283/step2.md b/283/step2.md new file mode 100644 index 0000000..70da309 --- /dev/null +++ b/283/step2.md @@ -0,0 +1,84 @@ +# step2 他の方の解答を見る +https://github.com/fhiyo/leetcode/pull/54 + +https://github.com/fhiyo/leetcode/pull/54/files#diff-2f8b85074aa38861aa9dd6fbe0c5f1b540a06f8618d7552b4ffd05da21f795d3R40-R46 + +先頭にそれぞれleft,rightをおく +1. rightの位置に0がない時はleftとrightの値を交換してleftを進める +2. rightを進める + +1,2を繰り返してrightが末尾までいったら終了 +という考え方。 +step1ではleftの位置に何があるかを含めていたが、要らなかった。 + +```ruby +# @param {Integer[]} nums +# @return {Void} Do not return anything, modify nums in-place instead. +def move_zeroes(nums) + left = 0 + nums.size.times do |right| + next if nums[right].zero? + + nums[left], nums[right] = nums[right], nums[left] + left += 1 + end +end +``` + +https://github.com/fhiyo/leetcode/pull/54/files/40f6172e4c7a6b29303a6b66464dd512300ac477#diff-2f8b85074aa38861aa9dd6fbe0c5f1b540a06f8618d7552b4ffd05da21f795d3R87-R98 + + +```ruby +# @param {Integer[]} nums +# @return {Void} Do not return anything, modify nums in-place instead. +def move_zeroes(nums) + last_non_zero_index = 0 + nums.each do |num| + next if num.zero? + nums[last_non_zero_index] = num + last_non_zero_index += 1 + end + last_non_zero_index.upto(nums.size - 1).each { |i| nums[i] = 0 } +end +``` + +> まとめて 0 fill は、loop unrolling できたりするのでちょっと嬉しいこともあるでしょう。 +https://github.com/fhiyo/leetcode/pull/54/files/40f6172e4c7a6b29303a6b66464dd512300ac477#r1729230640 + +loop unrollingという言葉を初めて知った。 + +RubyでもArray#fillだと処理を最適化しているようだった。 + +```ruby +require 'benchmark' + +n = 10 ** 6 +array1 = Array.new(n, 1) +array2 = Array.new(n, 1) +Benchmark.bm(7) do |x| + x.report("loop") { (0...n).each { |i| array1[i] = 0 } } + x.report("fill") { array2.fill(0, 0...n) } +end +``` + +``` + user system total real +loop 0.028068 0.000177 0.028245 ( 0.028289) +fill 0.000235 0.000150 0.000385 ( 0.000391) +``` + +なので以下のように書ける。 + +```ruby +# @param {Integer[]} nums +# @return {Void} Do not return anything, modify nums in-place instead. +def move_zeroes(nums) + last_non_zero_index = 0 + nums.each do |num| + next if num.zero? + nums[last_non_zero_index] = num + last_non_zero_index += 1 + end + nums.fill(0, last_non_zero_index...(nums.size)) +end +``` diff --git a/283/step3.md b/283/step3.md new file mode 100644 index 0000000..79f9569 --- /dev/null +++ b/283/step3.md @@ -0,0 +1,16 @@ +# step3 3回続けて10分以内に書いてエラーを出さなければOKとする + +```ruby +# @param {Integer[]} nums +# @return {Void} Do not return anything, modify nums in-place instead. +def move_zeroes(nums) + # leftより左には0以外の値がくる + left = 0 + nums.size.times do |right| + next if nums[right].zero? + + nums[left], nums[right] = nums[right], nums[left] + left += 1 + end +end +``` diff --git a/283/step4.md b/283/step4.md new file mode 100644 index 0000000..5941ee1 --- /dev/null +++ b/283/step4.md @@ -0,0 +1 @@ +## step4 レビューを受けて解答を修正