LeetCode解いたメモ #2 & #3

色々と思い立って，LeetCodeを始めました．無理のない範囲でポチポチと続けていきたいと思ってます．

色々とミスったところや考えの言語化のために問題を解くときに考えたことや間違えた原因などをブログに書いていこうかなとか思いました．これも無理のない範囲でやりたいです*1．

今日は#2 Add Two Numbers と #3 Longest Substring Without Repeating Characters をやったのでそれの話．

#2 Add Two Numbers

leetcode.com

問題

• ある数字の数値を1桁ずつ逆順に格納した連結リストが2つ(l1, l2)与えられる
  • 例えば 235 という数字は 5 -> 3 -> 2 とリストとして表現されている
• 元の数字同士を加算したものを同様に連結リストとして格納し，先頭の要素を返却する
  • 例: 2 -> 4 -> 3 と 5 -> 6 -> 4 が与えられた場合，342 + 465 = 807 なので 7 -> 0 -> 8 となり，7が格納された要素を返却する

回答

github.com

• まず，2つの引数それぞれの現在見ている要素のポインタを定義する
  • curr_l1 と curr_l2
• また，最終的な解答を格納するためのリストを定義し，同様に現在見ている要素のポインタを定義する
  • head_node と current_node
• で，curr_l1 と curr_l2 が両方とも次のnodeがなくなるまでループを回す
  • ループの中で，それぞれ各要素の数値を足して，解答の要素に入れてポインタを更新していく
  • 最終的に， head_node.next が求めるリストの始点になるのでそれをreturnしてやる
• 繰り上がりは carry として変数に格納し，次のポインタの計算時に持ち越す
  • リストの走査が終わっているときは，末尾にくっつけてあげる
• l1, l2のリスト長が同一とは限らないので，先に終わったリストの値は0として丸めてあげる

雑感

• 普段あまりリストを意識して使わないので，しばらく悩んだ
• が，なんとなく思い出したら後はデバッグしながら解いていった感じ
• デバッグ中，繰り上がりや長さの異なるケースの考慮が漏れてて少し悩んだ

#3 Longest Substring Without Repeating Characters

leetcode.com

問題

• ある文字列sが与えられて，それに対してユニークな文字のみで作られた文字列の最長の長さを返却する問題
  • 例: abcabc だと abcが最長な部分文字列で 3 を返却
  • 例: pwwkew だと 3文字目以降の wke か4文字目以降の kew が最長な部分文字列で， 3 を返却

回答

github.com

• 文字列を1字ずつの配列に変換し，1文字ずつループを回す
• substrに走査済みの重複のない部分文字列を格納しておき，そこに走査中の1字が含まれていないかチェックする
• 含まれていない場合はsubstrに文字を追加し，もし文字長が更新されればそっちも更新
• 含まれている場合は，重複文字の位置の次以降の文字を抽出し，末尾に走査中の文字を追加する
  • 例えば substrが abcd のときに bという文字が来た場合，b以降の文字 cd にはbが含まれないため，重複文字のない部分文字列としては cd と現在の文字を加えた cdb となる

雑感

• この問題は実装していて2つの考慮漏れが起きてWAをだした
  • 1つは重複文字があったときの部分文字列の扱い
    • 何も考えずに空文字を入れていたら，aab のときの最長の部分文字列がbとなってしまいFail
  • もう1つは，重複文字の切り取り方法のバグ (↑直後にだした)
    • 更新後の部分文字列は対象の文字だけだろうと思ったら abac みたいなケースのときに bac が最長となるべきなのに ac となってしまいFail

*1:ブログを書くのがしんどいなら問題だけ解いていったほうがいいよねと思ってます