akmhmgc · akmhmgc · Oct 9, 2025 · oda · Oct 12, 2025 · akmhmgc
diff --git a/283/step1.md 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
@@ -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
@@ -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
@@ -0,0 +1 @@
+## step4 レビューを受けて解答を修正
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1 @@
		## step4 レビューを受けて解答を修正