0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

leetcode141 を解いてみた

Posted at

方針

自分で1回はプロセスを考える。解けなくてもOK。
解けなかったときは、振り返ることが可能な程度まで言語化する。
※考え方おかしくない?というのがあればご指摘くださいまし。
※解けなかった、苦戦したものを記事にする。

問題紹介

問題は以下URL参照

最初の考え

  • こんなのリスト内をループさせる。配列に保存。次回ループ時に値が存在するかを判定すればいいんじゃね。
初回.py
class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        mem = []
        while head != None:

            count = mem.count(head.val)
            mem.append(head.val)
            head = head.next
            if count > 0:
                return True

        return False

思考中

  • 重複してるときのテストケースで落ちた...
    • link先の値が複数あるときは弾かないといけないのか...(´・ω・`)
  • input中の重複数値を洗い出すとかやれば大丈夫なんだけど、制限されてて確認できない(詰んだ)

結果

Solutionsを確認しました(´・ω・`)

  • 2つの速度でポインタを循環させて、一致した場合には循環しているのでTrue(ポインタの遭遇率が最近高い)
    • この手の問題はポインタを利用すればいいということを学んだよ。類似の使い方をする問題も多そうな気がする。
  • 前提として、循環していない場合のデータ構造はhead.next=Noneと考えた方が良さそう。
    • 値だけで判別すると繋ぎ先があるように思えるが、データ構造としてはそれは誤り。⇦ここの誤解が今回解けなかった原因。

そもそものアプローチがズレてたのが悔しいですね...(´・ω・`)

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?