はじめに
LeetCode はプログラミングの問題集のような学習サイト。
下記ルールで挑戦している。
ルール：
・No.1から順に解く（苦手な問題もスキップせずに正解できるまで頑張る！）
・難易度がNormalやHardの問題はスキップする（LeetCode初体験なのでまずはEasyだけ！）
・有料会員限定の問題はスキップする（今回はとりあえず無料の範囲で！）
本日、正解数が40問に到達したので、いったんそこまでの感想というか記録をこの記事に残す。
解いた問題の記録
1. Two Sum
https://leetcode.com/problems/two-sum/
int型配列の中から2つ選んで足し算して、ある目標値を作る。例えば「6 を作るには 3,2,4 の中からどれとどれを取るべきか答えよ」といった感じ。
普通に二重ループで全探索して正解できた。
二分探索すればO(NlogN)で行けそう。
9. Palindrome Number
https://leetcode.com/problems/palindrome-number/
整数が回文かどうか判定する。例えば「121」はtrue。
String型に変換してからループをまわして判定した。int型は最大でも10桁だからループ数は最大でも5周で済む、十分高速。
どうしてもString型に変換したくないなら、除算と剰余をうまくやれば狙った位の値を取れるけど、労力に見合うほど高速化しない気も。
13. Roman to Integer
https://leetcode.com/problems/roman-to-integer/
ローマ数字⇒アラビア数字 の変換をする。例えばIV⇒4。
アラビア数字⇒ローマ数字 の変換のほうが簡単なので、それを1から順番に試した（答えを全探索）ところ、まさかの実行時間制限超過という結果になった。しょうがないので探索前に答えをざっくり絞り込むことで時間短縮したら正解となった。
ちなみにインチキ技として、ローマ数字とアラビア数字の全組合せをソースコード内にあらかじめ埋め込んでおくというズルいコードを提出したら正解判定されて笑ってしまった。
14. Longest Common Prefix
https://leetcode.com/problems/longest-common-prefix/
英単語に共通する接頭辞を求める。
英単語集合を辞書順ソートして、先頭の英単語と最後尾の英単語を比較するだけのひらめき問題。
20. Valid Parentheses
https://leetcode.com/problems/valid-parentheses/
カッコの整合性判定。
「大カッコを閉じたあとは何カッコを閉じるんだっけ？」といった記録が必要だったので、久々にDequeを使った。JavaのDequeでよく使うメソッドはpush, pop, peek, isEmptyあたりかな（popはデータを取り出すけどpeekは見るだけ）。
21. Merge Two Sorted Lists
https://leetcode.com/problems/merge-two-sorted-lists/
２本の連結リストのマージ。
連結リストはデータ構造のド定番だが自分はコーディング経験がなく、イメージがちっとも湧いてこなかった。まるで初めて触るプログラミング言語のよう。LeetCodeのDiscuss（他ユーザの投稿）を見ながら３～４時間ほど取り組んで最終的に正解できたものの、結局他ユーザのコードを丸コピペしたようなものが完成した。悔しい。
26. Remove Duplicates from Sorted Array
https://leetcode.com/problems/remove-duplicates-from-sorted-array/
int型配列で、他と重複している値をゴミとし、ゴミだけを配列の後ろのほうへ追いやる。
この問題には「in-placeでやること」という特殊ルールが設けられており、元の配列をそのまま結果配列として完成させなければならない。そこでゴミを上書きで消していくロジックにした。
ちなみにメモリ節約の趣旨からは外れるが、結果用配列を別途用意して値を入れていくロジックを提出してみたら一応正解にはなった。
27. Remove Element
https://leetcode.com/problems/remove-element/
int型配列で、特定の値をゴミとし、ゴミだけを配列の後ろのほうへ追いやる。
この問題もまた「in-placeでやること」という特殊ルールがあるが、さっきの問題より簡単。今度は上書きではなく、配列内でスワップを繰り返すことで配列を完成形に近づけていくロジックにしてみた。
28. Implement strStr()
https://leetcode.com/problems/implement-strstr/
Javaの文字列検索関数 indexOf() と同じことをする関数を自作する問題。
効率の良い文字列検索といえば真っ先に思いつくのはクヌース=モリス=プラット法だが、今回はまぁ普通に全探索した。
35. Search Insert Position
https://leetcode.com/problems/search-insert-position/
まるで挿入ソートのように、数値の正しい挿入場所を配列内から探す。
一見簡単そうだが、なんと「O(log n)のアルゴリズムでやれ」という特殊ルールが書いてある。つまり、二分探索を知らない人やそもそもオーダー記法を知らない人はここでジ・エンド。いよいよこういう問題が来たかー。LeetCodeはただの文法練習サイトではないことを再認識させられたのであった。
53. Maximum Subarray
https://leetcode.com/problems/maximum-subarray/
総和が最大になるような "連続した部分配列" を配列内から探す。
良い戦略が思いつかず。累積和も尺取り法も使えず。全探索したらやはり実行時間制限超過。諦めてググったところ、なんと英語版Wikipediaに個別ページを発見、Kadaneのアルゴリズムという手法がよく知られているらしいことが判明。もしかして有名な問題なのかな。
Kadaneのアルゴリズムのイメージとしては「直前までの区間和が正だったら引き続き区間を伸ばしてハイスコアを狙うけど、直前までの区間和が負だったらいったん仕切り直し（現在地点から区間をリスタート）する」といった考え方。なるほどこれは思いつかなかった。
それにしてもこの問題、こんなアルゴリズムの閃きを要求するくせにEasyだし、しかも発展学習として「分割統治法も考えてみてね」とか書いてあるし、色々やばい。
58. Length of Last Word
https://leetcode.com/problems/length-of-last-word/
英文をスペースで区切ったとき、最後に出現する英単語の長さを求める。
普通にうしろから1文字ずつ調べた。
ついでに、trimとsplitとlengthを使う（これならソースコードたったの1行で書ける！）という方法も提出し、こちらも正解を得られた。
66. Plus One
https://leetcode.com/problems/plus-one/
数字に1を足すだけ…だが、数字は最大で100桁もあり、長さ100の配列で与えられる。
繰り上がりに気を付けて答えを出していく。
BigIntegerを使うという裏技もアリかも（試してない）。
67. Add Binary
https://leetcode.com/problems/add-binary/
いわゆる「全加算器」。
制約の都合上いったん10進数に変換する方法は使えないため、地道に下位の桁から答えを出していった。基礎的だが良い問題。
69. Sqrt(x)
https://leetcode.com/problems/sqrtx/
平方根を求める。
普通に線形探索して終わり。int型の最大値 2^31-1 = 約21億(10桁) に収まる制約で良かった。
70. Climbing Stairs
https://leetcode.com/problems/climbing-stairs/
階段の上り方が何通りあるか数える。
DPの入門として定番の問題である。LeetCodeにもとうとうDPが出てきたかー。今回は "配るDP" で正解。
83. Remove Duplicates from Sorted List
https://leetcode.com/problems/remove-duplicates-from-sorted-list/
連結リストのつなぎかえ。
以前挑んだ「21. Merge Two Sorted Lists」と同様、問題の意図は分かるし、うまいところまでは行くのだが、どうしてもバグが取れなかった。連結リストはどうもダメだ。
88. Merge Sorted Array
https://leetcode.com/problems/merge-sorted-array/
２つの配列のマージ。
素直にポインタ２個を独立に動かしていくのが正攻法な気がするが、今回は Arrays.sort() で一瞬で終わらせた。
94. Binary Tree Inorder Traversal
https://leetcode.com/problems/binary-tree-inorder-traversal/
二分木を "Inorder Traversal" (通りがかり順) で走査する。
「行きがけ順」と「帰りがけ順」しか知らなかったので初耳だった。やること自体は再帰関数を回しながら配列を作るだけなので楽勝。
100. Same Tree
https://leetcode.com/problems/same-tree/
ふたつの二分木が等しい構造かどうか判定する。
さきほどの問題で作った走査アルゴリズムを流用し、走査中の「新ノードに到達した」「左が突き当たった」「右が突き当たった」「上のノードに帰ってきた」といった足取りを記録し、それを比較することで判定した。
101. Symmetric Tree
https://leetcode.com/problems/symmetric-tree/
二分木が左右対称の構造かどうか判定する。
さきほどの問題の応用といった感じ。通常版の走査を左サイドで走らせ、左右反転版の走査を右サイドで走らせた。
104. Maximum Depth of Binary Tree
https://leetcode.com/problems/maximum-depth-of-binary-tree/
二分木の高さを求める。
走査中、現在地の深さを常に保持していれば分かる。
108. Convert Sorted Array to Binary Search Tree
https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
ソート済みの配列をもとに、平衡二分探索木を作る。
木を作るタイプの問題が初登場。それなのにいきなり平衡二分探索木がテーマでビックリ。まあ考え方は分かりやすい（二分探索と同じように配列をどんどん分断しながら再帰関数を回す）。
110. Balanced Binary Tree
https://leetcode.com/problems/balanced-binary-tree/
二分木が「どの "兄弟" も "自分を根とする部分木の高さ" の差が1以下」を満たしているかどうか判定する。
まず再帰関数の走査で「自分を根とする部分木の高さ」を求めて、その後にBFSして判定した。…のだが、BFS中に "一人っ子" の考慮が抜けていて不正解を連発してしまい結構苦戦した。むずいむずい。
111. Minimum Depth of Binary Tree
https://leetcode.com/problems/minimum-depth-of-binary-tree/
二分木で、最も低い位置にある葉の高さを求める。
だんだん深く調べていきたいのでBFS。楽勝！
112. Path Sum
https://leetcode.com/problems/path-sum/
各ノードが値を持っている二分木において、根から葉までのパスのうち、値の総和が目標値と一致するものを探す。
まるで累積和のように、二分木を探索しながら総和をどんどん葉のほうへ持ち越していけばいいので、これもBFSで解決。
118. Pascal's Triangle
https://leetcode.com/problems/pascals-triangle/
パスカルの三角形を作る。
まぁ…それだけ。
119. Pascal's Triangle II
https://leetcode.com/problems/pascals-triangle-ii/
パスカルの三角形を作る。
ひとつ前の問題とほぼ同じ。
121. Best Time to Buy and Sell Stock
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
int型の配列から値を２つ（aとbとする）選び出し、その差 b - a を最大化する。ただし b は a よりも後ろから選ばなければならない。
a と b の位置関係が重要なので、単純に最大値と最小値を選ぶだけではダメ。二重ループで全探索すればO(n^2)で解けそうだが、配列を左から順に見ていき、答えの候補を更新しつつハイスコアも更新していくことでO(n)で解けた。競プロっぽい問題だった。
125. Valid Palindrome
https://leetcode.com/problems/valid-palindrome/
文字列が回文かどうか判定する、ただし英数字以外の文字（記号やスペース等）は無視する。
ここは素直に、英数字だけを拾いながら大文字小文字区別せず見ていった。
136. Single Number
https://leetcode.com/problems/single-number/
配列の中から、一度しか登場しない値を探す。
各値が登場したことを何らかの手段で覚えておけばよさそうだが、今回は配列をソートしてペア同士を並ばせることで答えを浮かび上がらせた。
141. Linked List Cycle
https://leetcode.com/problems/linked-list-cycle/
連結リスト内にループ（一度通ったノードに戻る）があるかどうか判定する。
問題の制約上、ノード数は最大で1万個らしいので、スタートノードから1万ノード先まで実際にたどっていって途中で突き当たったらfalse。
144. Binary Tree Preorder Traversal
https://leetcode.com/problems/binary-tree-preorder-traversal/
二分木を "Preorder Traversal" (行きがけ順) で走査する。
ちょっと前にあった「通りがかり順」のプログラムをちょこっと改造するだけだった。
145. Binary Tree Postorder Traversal
https://leetcode.com/problems/binary-tree-postorder-traversal/
二分木を "Postorder Traversal" (帰りがけ順) で走査する。
これで通りがかり順・行きがけ順・帰りがけ順を３つまとめて理解できた。
155. Min Stack
https://leetcode.com/problems/min-stack/
いつでもgetMin()できるようなスタッククラスを自分で作る。
今まではメソッドだったがこれはクラス自体を作る問題。
getMin()されるたびに全要素を探索するようなものを作ってしまうと実行時間制限超過になりそうな気がしたので、
クラス内にdequeを2個用意する（値保管用と最小値保管用）というアイデアでやってみたら無事一発正解。楽しい～。
160. Intersection of Two Linked Lists
https://leetcode.com/problems/intersection-of-two-linked-lists/
連結リストのノードが2つ与えられるので、やがて合流するか判定する。
いまいち分からず、Discussでみんなのやり方をチラ見。なるほど足並みそろえて探索していくのか。そこからは自力でコーディングできたのでヨシ。
168. Excel Sheet Column Title
https://leetcode.com/problems/excel-sheet-column-title/
1⇒A、26⇒Z、28⇒AB、123456789⇒JJDDJA のようにExcel列名を求める。
これとほぼ同じ問題をAtCoderで見たことがある（abc171_c）が、そのときも解けなかった思い出がある。
軽く解法のコツを調べたところ、規則性を見つけて答えの下位から順に求めていくといいらしい。それをヒントになんとかできた。
169. Majority Element
https://leetcode.com/problems/majority-element/
int型配列で、最頻値を探す。ただしこの問題では、最頻値の出現回数は全体の半分より大きいことが保証されている。
ということでデータの最小値と中央値付近だけ見れば答えが確定できちゃう。
171. Excel Sheet Column Number
https://leetcode.com/problems/excel-sheet-column-number/
A⇒1、Z⇒26、AB⇒28、JJDDJA⇒123456789 のようにExcelの何列目かを求める。
26進数と同じ考えですんなりできた。
175. Combine Two Tables
https://leetcode.com/problems/combine-two-tables/
DBにおいて、IDで紐付けて2つのテーブルを連結し、指定されたカラムのレコードを表示させる。
ここにきてSQLで答える問題が初登場。ここまで全部Javaでやってきたのだが、まさかSQLを強制されるとは。
とはいえこれは簡単で、2つのテーブルをLEFT JOINすれば勝てる。
全体的な感想
- 40問のうち30問くらいは何もヒントを見ないで解けたと思う。楽しかった。
- 40問のうち20問くらいは、答えを出すアイデアを２つ以上思いつくことができたと思う。
- 下調べしてなかった自分が悪いのだが、使う技術を制限されてキツかった（もちろん良い刺激にはなった）。
- いきなりSQLを強制されたときは驚いた。
- ちなみにBashを強制してくる問題も今後出てくる模様。
- 連結リストとか二分木とか、決められたデータ構造を使って答えなければならない問題も多く、自分で自由にコーディングできないぶん適応力が求められた。
- 有名なアルゴリズムをある程度知っていないとEasyでもキツい。
- むしろ調べながらチャレンジしてほしいのかも。
- 問題文は全文英語だがそんなに困らず、なんとかなった。問題ごとにデータの具体例も書いてあるし、何をすべきかはすぐ理解できる。
- Discuss機能（他ユーザの投稿）が便利すぎてメッチャ勉強になる。自分で解けなかった問題はまずDiscussを見てヒントを得るようにしていた。
というわけで今のところ、LeetCodeはプログラミング初心者向けサイトではないという印象が強く残っている。
サイト内のどこかに初心者向けコンテンツも別途あるのかもしれない。もっとサイト全体をあちこち見てみようかな。
引き続き41問目以降も気が向いたときにチャレンジしていきたい！
以上です。