BETA

LeetCodeに騙されるな

投稿日:2020-01-05
最終更新:2020-01-05

はじめに

LeetCodeは基本的に良問揃いだと思いますが、その問題説明文は意外と雑に感じる時があります。Atcoder^1 からスタートして、LeetCodeに移り、鼻歌まじりで楽しく1日1LC^2 していたのですが、進めるにつれ、ちょいちょい雑な問題文に出会ってリズムが崩れたので、その対策をメモしておこうと思います。言語はRubyでやってます。

206. Reverse Linked List の Ruby の解を知りたいだけの場合は、最後の方の「参考になったサイト」を見るのが早いと思います。

前兆

14. Longest Common Prefix あたりで、回答欄に見慣れないコメント文を見つける。

# @param {String[]} strs  
# @return {String}  
def longest_common_prefix(strs)  
end  

StackOverflow 先生に聞いてみると、この2行は YARDというドキュメント生成ツールのお作法で書かれているようだ。

その意味は longest_common_prefixstrsという{String[]}インスタンスを引数にとり、{String}インスタンスを返すということのようだ

ところで、{String[]}インスタンスってなに? 問題文には


Input:["flower","flow","flight"]  

ってなってるので、入力は Array っぽく思えるけど、これ実は文字列なの?ということは、配列にしたかったら、eval(strs)とかした方がいいの?

確かめてみると

# @param {String[]} strs  
# @return {String}  
def longest_common_prefix(strs)  
  p strs.class # => Array  
end  

普通に Array でした... {String[]}ってなに?、Stringの配列ってこと?Java 族の人が書いた?

206. Reverse Linked List

Linked Listを反転させる問題 なのだがこれも、問題文だけ見ると「え?」となる。

Input: 1->2->3->4->5->NULL  
Output: 5->4->3->2->1->NULL  

とかなっていて、いやいや、これが本当の入出力なら、趣旨を無視する輩なら、普通に文字列処理で返せてしまうがな。たとえばこんなワンライナーで。


def reverse_list(head)  
  split("->").slice(0, head.split("->").size-1).reverse.push("NULL").join("->")  
end  

しかも、Run Code でテストしてみるとそこの表記は


Your input: [1,2,3,4,5]  
Your output: [1,2,3,4,5]  
Expected: [5,4,3,2,1]  

とかでてくるので、「え?input, outputともに配列?」ってなる。が、もちろんちがう。回答欄をみてみると:


# Definition for singly-linked list.  
# class ListNode  
#     attr_accessor :val, :next  
#     def initialize(val)  
#         @val = val  
#         @next = nil  
#     end  
# end  

# @param {ListNode} head  
# @return {ListNode}  
def reverse_list(head)  
end  

YARD 的には ListNodeインスタンスを受け取って、ListNodeインスタンスを返せということらしい。どんな入力値渡してきているのかを確認するために、Run Code で入力値をそのまま直接標準出力に出してみる。


# @param {ListNode} head  
# @return {ListNode}  
def reverse_list(head)  
  p head # => #<ListNode:0x0000000001a4ea38 @val=1, @next=#<ListNode:0x0000000001a4ea10 @val=2, @next=#<ListNode:0x0000000001a4e9e8 @val=3, @next=#<ListNode:0x0000000001a4e9c0 @val=4, @next=#<ListNode:0x0000000001a4e998 @val=5, @next=nil>>>>>  
end  

なるほど、確かに ListNodeオブジェクトっぽいものが渡されている。わかってきた。ということはおそらく、この入力値はこのように作られているのではないか


class ListNode  
  attr_accessor :val, :next  
  def initialize(val)  
    @val = val  
    @next = nil  
  end  
end  

ln1 = ListNode.new(1)  
ln2 = ListNode.new(2)  
ln3 = ListNode.new(3)  
ln4 = ListNode.new(4)  
ln5 = ListNode.new(5)  

ln1.next = ln2  
ln2.next = ln3  
ln3.next = ln4  
ln4.next = ln5  

p ln1 # => #<ListNode:0x007fbd46967138 @val=1, @next=#<ListNode:0x007fbd469670c0 @val=2, @next=#<ListNode:0x007fbd46967048 @val=3, @next=#<ListNode:0x007fbd46967020 @val=4, @next=#<ListNode:0x007fbd46966ff8 @val=5, @next=nil>>>>>  

さっき、p head したときと同じような出力になっていて、それっぽい感じです。ここで意味がわかってきたので、タイトルの趣旨としては終わりですが、ついでに206の解法について考えてみます。

Solution

基本的に、ポインタを反転させるという考え方のようです。

Iterative

繰り返し的な解き方


def reverse_list(head)  
  prev = nil  
  curr = head  
  #puts "curr: #{curr}, prev: #{prev}"  
  until curr.nil?  
    temp = curr.next  
    curr.next = prev  
    prev = curr  
    curr = temp  
    #puts "curr: #{curr}, prev: #{prev}, temp: #{temp}"  
  end  
  prev  
end  

要は、最後の nil に当たるまでノード毎にポインタを反転させていくみたいです。絵で書くとこんな感じでしょうか。


prev  
↓  
nil  1 -> 2 -> 3 -> 4 -> 5 -> nil  
     ↑  
     curr  

curr = head(=1)  
temp <= curr.next(=2)  
curr.next <= prev(=nil)  
prev <= curr(=1)  
curr <= temp(=2)  

       prev  
       ↓  
nil <- 1    2 -> 3 -> 4 -> 5 -> nil  
            ↑  
            curr  

curr = 2  
temp <= curr.next(=3)  
curr.next <= prev(=1)  
prev <= curr(=2)  
curr <= temp(=3)  

            prev  
            ↓  
nil <- 1 <- 2    3 -> 4 -> 5 -> nil  
                 ↑  
                 curr  
curr = 3  
temp <= curr.next(=4)  
curr.next <= prev(=2)  
prev <= curr(=3)  
curr <= temp(=4)  

                 prev  
                 ↓  
nil <- 1 <- 2 <- 3    4 -> 5 -> nil  
                      ↑  
                      curr  

curr = 4  
temp <= curr.next(=5)  
curr.next <= prev(=3)  
prev <= curr(=4)  
curr <= temp(=5)  

                      prev  
                      ↓  
nil <- 1 <- 2 <- 3 <- 4    5 -> nil  
                           ↑  
                           curr  
curr = 5  
temp <= curr.next(=nil)  
curr.next <= prev(=4)  
prev <= curr(=5)  
curr <= temp(=nil)  

                           prev  
                           ↓  
nil <- 1 <- 2 <- 3 <- 4 <- 5    nil  
                                ↑  
                                curr  
curr = nil になったので終わり  

Recursive

再起的な解き方


def reverse_list(head)  
  return head if head.nil? || head.next.nil?  

  p = reverse_list(head.next)  
  head.next.next = head  
  head.next = nil  
  p  
end  

分かりやすくはないですね。head.next.next = head とか何やってんの?なんですが、たとえば、2からみて、3のノード(つまりhead.next)のポインタ(つまりhead.next.next)を自分に向けるみたいな感じでしょうか

1 -> 2 -> 3 -> 4 -> 5 -> nil  
     ↑  
    ココ  

パフォーマンス

Iterative


Runtime: 36 ms, faster than 72.64% of Ruby online submissions for Reverse Linked List.  
Memory Usage: 9.5 MB, less than 100.00% of Ruby online submissions for Reverse Linked List.  

Recursive


Runtime: 32 ms, faster than 93.01% of Ruby online submissions for Reverse Linked List.  
Memory Usage: 9.9 MB, less than 100.00% of Ruby online submissions for Reverse Linked List.  

参考にしたサイト

LeetCode in Ruby: 206 Reverse Linked List^3

技術ブログをはじめよう Qrunch(クランチ)は、プログラマの技術アプトプットに特化したブログサービスです
駆け出しエンジニアからエキスパートまで全ての方々のアウトプットを歓迎しております!
or 外部アカウントで 登録 / ログイン する
クランチについてもっと詳しく

この記事が掲載されているブログ

ジオン軍の技術ブログ

よく一緒に読まれる記事

0件のコメント

ブログ開設 or ログイン してコメントを送ってみよう