NinaLabo

個人ゲーム開発者の技術メモ

【LeetCode】20. Valid Parentheses(Easy)

【最初に】

LeetCode 8個目に挑戦です

leetcode.com


 

 

【問題】

次の '('')''{''}''['']' の文字だけを含んだ文字列の括弧対応が正しいか判定せよ。空文字列は正しいと判定すること。 

Example 1:

Input: "()"
Output: true

Example 2:

Input: "()[]{}"
Output: true

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

 

【とりあえず】

思いつくのは左括弧の場合はStackに格納し、右括弧の場合はStackから取り出して括弧の対応が正しいか判定する、かな。

f:id:ninagreen:20191113020438p:plain

 

 できた!

f:id:ninagreen:20191113020503p:plain

【解答を見る】

だいたい↑と同じことやってた

 

【最後に】

最初に解いた内容と解答が同じだったのははじめてだな

 

【LeetCode】104. Maximum Depth of Binary Tree(Easy)

【最初に】

LeetCode 7個目に挑戦です

leetcode.com

 

 

【問題】

与えられたバイナリツリー(二分木)の最大深度を求めよ

Example:

Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its depth = 3.

 

【とりあえず】

再帰処理で全探索する。左と右で深度の大きいほうを返し続ければ最大深度になるはず。

f:id:ninagreen:20191112023129p:plain

 

できた!

f:id:ninagreen:20191112023152p:plain

 

【解答を見る】

と思ったらPremiumに加入してないと解答が見れないようになってる!仕方ないので、Discussionを見てみる。あ、そうか別にCheckChildとか別関数を作らなくても、もともとのmaxDepth関数を再帰させればいいのか。

 

f:id:ninagreen:20191112024114p:plain

引数が子要素を持たないノードの場合、maxDepth(root->left) も maxDepth(root->right) も0が帰ってくる。その状態から+1ずつしていけば深さを求めることができる。

 

できた!

f:id:ninagreen:20191112024439p:plain

余計なメソッド呼び出しがなくなったからか、実行速度も16msから8msにあがってる!

 

【最後に】

 Solutionは無料で全部見れると思ってたのに・・(TーT

【LeetCode】83. Remove Duplicates from Sorted List(Easy)

【最初に】

LeetCode 6個目に挑戦です

leetcode.com

 

 

【問題】

与えられたLinkedListから重複を排除せよ

Example 1:

Input: 1->1->2
Output: 1->2

Example 2:

Input: 1->1->2->3->3
Output: 1->2->3

 

【とりあえず】

ぱっと思いつくのは、前回の↓と同様にLinkedListをループで回して過去に調べた数字は可変長配列に保存しておき、重複した数字が出現した場合はnextを次の次のノードに書き換えるというもの。

ninagreen.hatenablog.com

 

f:id:ninagreen:20191110042015p:plain

 

できた!

f:id:ninagreen:20191110042043p:plain

 

【解答を見る】

どうやら問題のLinkedListはソートされている前提らしい。であれば、過去に調べた値をvectorに入れて比較せずとも、前の値と次の値を比較するだけで問題ない。

f:id:ninagreen:20191112020405p:plain

こちらのほうがvectorに値を保存しないので、空間計算量がO(n) → O(1) になる。
 

【最後に】

問題文の最初に"sorted"って書いてありました。

Given a sorted linked list, 

よく読まないと.. ですね

 

 

【LeetCode】141. Linked List Cycle(Easy)

【最初に】

LeetCode 5個目に挑戦です

 

leetcode.com

 

 

【問題】

与えられたLinkedListが循環しているかどうか判定せよ  

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

 

【1.とりあえず】

ぱっと思いついたのは、LinkedListをループさせて可変長配列に詰めていく。過去のノードと同じノードが出てきたら循環参照していると判定する。

 

f:id:ninagreen:20191110025557p:plain

できた!

f:id:ninagreen:20191110025956p:plain

 

【2.違うパターン】

問題文の最後に

Can you solve it using O(1) (i.e. constant) memory?

とあるので、空間計算量がO(1)になるように考えてみる(今はLinkedListを全件ループして配列に格納しているのでO(n)になっている)

 

時間計算量はO(n)→O(n^2) になっちゃうけど、とにかく保存せずにループ回しまくってみる。

 

f:id:ninagreen:20191110031450p:plain

 

ひどいコードだけど一応できた!

f:id:ninagreen:20191110031549p:plain

 

【3.解答を見てみる】

2つの異なるスピードのポインターを持てばいいのでは?とあるが、個人的にはなかなか馴染みのない考え方。要は足の速い選手と遅い選手がいて、遅い選手が1進むたびに速い選手が2進むとすると、循環参照していた場合、足の速い選手が1ずつ周回遅れの遅い選手との距離を縮めて行っていつか追いつくというもの。やってみた。

 

f:id:ninagreen:20191110034015p:plain

 

できた!

f:id:ninagreen:20191110034029p:plain

 

これだと2のパターンよりループ回数も少なくて済むし、1のパターンよりメモリ使用量も少なくても済む。

 

【最後に】

最初に考えた人、頭いいなあ

 

 

【LeetCode】13. Roman to Integer(Easy)

【最初に】

LeetCode 4個目に挑戦です

leetcode.com


 

 

 

【問題】

https://leetcode.com/problems/roman-to-integer/

ローマ数字を整数に変換せよ

Example 1:

Input: "III"
Output: 3

Example 2:

Input: "IV"
Output: 4

Example 3:

Input: "IX"
Output: 9

Example 4:

Input: "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 5:

Input: "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
 

【とりあえず】

文字から数字に置き換えて足していく。前の文字より数字が小さければ前の文字から引いた数字を足していく。

f:id:ninagreen:20191108015257p:plain

f:id:ninagreen:20191108015315p:plain

 

できた!

f:id:ninagreen:20191108015355p:plain


【解答をチラ見..】

しようと思ったら、この問題には解答がない!そんな問題あるんですね。簡単だからいらないでしょ?ってこと??

 

【LeetCode】9. Palindrome Number (Easy)

【最初に】

LeetCode 3個目に挑戦です

leetcode.com

 

 

 

【問題】

https://leetcode.com/problems/palindrome-number/

回文の整数(前から読んでも後ろから読んでも同じ数値になっている)かどうかを判定せよ。

Example 1:

Input: 121
Output: true

Example 2:

Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

 

【とりあえず】

数値を文字列にして前からと後ろからで比較してみる

f:id:ninagreen:20191107233351p:plain

 

できた!

f:id:ninagreen:20191107233439p:plain

 

【違うパターン】

Coud you solve it without converting the integer to a string?

問題の最後に、integerをstringに変換せずに解いてみない?とある。

うーん、これって前回やった数値を逆にするのを使えばいけるんじゃない?

ninagreen.hatenablog.com

 

ということで、やってみた。

f:id:ninagreen:20191107235432p:plain

 

マイナスの場合は判定するまでもなくfalse、オーバーフローの場合もfalseにしつつ、数値を逆に並び替える。最後に入力された数字と並び替えた数字を比較して同じかどうかを返す。

 

できた!

f:id:ninagreen:20191107235601p:plain

 

 

【解答をチラ見する】

解答は数値を半分だけ逆順にすれば、回文であれば残りの数字と同じになるよねという考え方のよう。例えば、1221であれば1桁目と2桁目の21を逆順にした12は、残りの3桁目と4桁目と同じになる。

 

f:id:ninagreen:20191108004646p:plain

最後の判定で10で割った値と比較しているのは、数字が奇数だった場合、例えば入力値が12321の場合、x=12、result=123になるのでこのままだとfalseになってしまうから。真ん中の値は何でもいいので、resultを10で割って12に無理やりしている。

また、最初に10で割り切れる数を除外しているのは、例えば入力値が10の場合、最終的にx <= resultにならないとwhileループを抜けないので、ループを抜ける頃には x=0、result=1 になっている。このままだと回文でないにも関わらず、奇数計算用の x == result / 10 で true になってしまうので事前に除外する必要がある。

 

全部並べ換えるよりループは半分で済むけど、なんかわかりにくいように思うのは私だけ...?

 

【最後に】

以前やった問題とほぼ同じ問題かと思ったけど、そんなの出ないよね。

【LeetCode】7. Reverse Integer (Easy)

【最初に】

LeetCode 2個目に挑戦です

leetcode.com

 

 

 

【問題】

https://leetcode.com/problems/reverse-integer/

32bit signed integer(−231 〜 231 − 1) の桁を逆順にせよ。 逆順の数値がオーバーフローした場合は0を返すものとする

Example 1:

Input: 123
Output: 321

Example 2:

Input: -123
Output: -321

Example 3:

Input: 120
Output: 21

 

 

【とりあえず】

パッと思いつくのは、文字列にして1つずつ逆順にして最後に数値に変換。頑張って書いてみたけど、これだと-123の時に-321ではなく321になっちゃうんですよね

f:id:ninagreen:20191107011119p:plain

もうめちゃくちゃだけど、マイナスかどうか最初に判定してやれば一応単純ケースでは動く。

f:id:ninagreen:20191107011848p:plain

あぁ、ひどいコード。オーバーフローにも対応できていないし、入力が0の場合にも答えが違う。

 

【解答を見る】

ここで文字列に置き換えずに数値として扱わないとオーバーフロー判定が面倒で、全然筋が違いそうな気がしてくる。ヒントを見ようと思ったけど、みんなスラスラ解けるからなのかこの問題にヒントはない。仕方ないので解答をチラ見する。そうか、10で割っていって余りをとれば1桁ずつ取れるじゃないの

f:id:ninagreen:20191107013317p:plain

めっちゃ簡単でした。10で割り続けるとintだといつか0になるのでwhile文を抜ける。

 

オーバーフローチェックを入れるとこんな感じかな。やっとできた。

f:id:ninagreen:20191107014538p:plain

 

時間計算量は O(log(x))だそう。計算量の求め方はこちらがわかりやすかったです

qiita.com

 

Oの中身はこういうルールで表記するらしい。

  1. 最高次数の項以外は落とす: 3n^2+5n+100 -> 3n^2
  2. 係数を無視する3n^2 -> n^2

例えば、上記のコードのループ回数は、

n=1のとき1回

n=10のとき2回

n=100のとき3回

つまり

n=10^kのときk+1回、つまり \log_{10} n - 1 回となり、

底数と減算は無視できるので、計算量はO(log(x))となるんじゃないかと思う。

 

【最後に】

新卒の頃とかにもっと基礎を勉強しとけば良かったなあ