【LeetCode】26. Remove Duplicates from Sorted Arrayを解いてみた
はじめに
コーディングテスト対策としてLeetCodeの7. Reverse Integerを解いていく。
問題文を和訳
これは、O(1) の余分なメモリを使用して入力配列をin-placeで変更することによって行う必要があります。
明確化:
戻り値が整数であるのに、答えが配列である理由が混乱していますか?
入力配列は参照によって渡されることに注意してください。
つまり、入力配列への変更は呼び出し側にも認識されます。
内部的には、次のように考えることができます。
numsは参照によって渡されます。（つまり、コピーを作成せずに）
int len = removeDuplicates（nums）;
関数内のnumsへの変更は、呼び出し元に認識されます。
関数から返された長さを使用して、最初のlen要素を出力します。
for（int i = 0; i <len; i ++）{
print（nums [i]）;
}
Input: nums = [1,1,2]
Output: 2, nums = [1,2]
Explanation: Your function should return length = 2
with the first two elements of nums being 1 and 2 respectively.
It doesn't matter what you leave beyond the returned length.
回答
26_RemoveDuplicatesfromSortedArray.rb
def remove_duplicates(nums)
index = 0
if nums.length == 0
return 0
end
for i in 0...nums.length do
if nums[i] != nums[index]
index += 1
nums[index] = nums[i]
end
end
return index + 1
end
最後に
難易度はEasyでした。
テンプレートメソッドパターンとは？
テンプレートメソッドパターンはGoFのデザインパターンの一種です。
このパターンは、基底クラスに不変の部分を記述し、変わる部分はサブクラスに定義するメソッドにカプセル化するというモノです。
変わるものと変わらないものを分離するという設計の考えに基づいています。
つまり次の2つのオブジェクトによって構成されます。
- 骨格となる「抽象的な基底クラス」
- 実際の処理を行う「サブクラス」
メリット
基底クラス側に、「不変の基本的なアルゴリズム」を配置可能になる。
「高レベルの処理を制御すること」に集中できる。
サブクラス側に、「変化するロジック」を置ける
「詳細を埋めること」に集中できる
似通った部分を共通化して「サブクラスに対してスーパクラスで実装されている抽象メソッドを実装する」という責任を与えることが可能になる。
実装例
基底クラス
class Test
def open()
raise NotImplementedError.new("#{self.class}##{__method__}")
end
def close()
raise NotImplementedError.new("#{self.class}##{__method__}")
end
def output()
raise NotImplementedError.new("#{self.class}##{__method__}")
end
def display
open()
5.times do
output()
end
close()
end
end
サブクラス
class SubTest < Test
def initialize(string)
@string = string
end
def open
print 'open!'
end
def close
print 'close!'
end
def output
print @string
end
end
実行例
sub_test = SubTest.new('テスト')
sub_test.display
#=> open!
#=> "テスト"
#=> "テスト"
#=> "テスト"
#=> "テスト"
#=> "テスト"
#=> close!
