LeetCodeを200問解いてみた

ここ1,2ヶ月プライベートの時間を使ってleetcodeの問題を解いていたが解いた問題数が200を超えたのでここにまとめたいと思う。

解き始めたきっかけ

これはgoogleなどの大手外資の面接に使われているからと言うのが一番大きな理由だ。
それらで求められている知識なら身につけておいた方が良いだろうという考えに至った。
また筆者はrecursionCSと言うサイトでアルゴリズムとデータ構造について学習をしているのでその定着度がどれ程かを測りたかったと言う思いもある。

解いた問題の内訳

レベルで言うとeasy50%midium49%、残りの1%でhardといった感じだ。
だってhard見るからに難しいんだもん。。。。笑
データ構造の観点で言うと一通り解いたと思う。配列、ハッシュマップ、連結リスト、スタック、キュー、BST、グラフなどなど。。
グラフだけは上述したrecursionCSで概念しか学んでいなかったのでこちらを使って学習した。

200問解いて思うこと

解き始めの頃はeasy問題でも全く解法が思い浮かないことがしょっちゅうあったが、それでも解説見て時間を置いて再挑戦->解説見て再挑戦を繰り返していると意外に解けるようになるものである。
高校・大学受験の数学を思い出した笑
またデータ構造のパワーと言うのを思い知った。
二分木の階層構造というデータ構造を学んでいる人ならおそらく大半の人は知っているであろう有名な問題があったのだが、これを力技で実装した時はまあ酷いコードになった。。

java.zenn

import java.util.*;

class BinaryTree {
    public int data;
    public BinaryTree left;
    public BinaryTree right;

    public BinaryTree() {}
    public BinaryTree(int data) { this.data = data; }
    public BinaryTree(int data, BinaryTree left, BinaryTree right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
}

class Solution{
    public static List<Integer> levelOrderTraversal(BinaryTree root){
        int depth = maximumDepth(root);
        //各深さをキー、階層ごとの値の配列をバリューでもつハッシュを作成
        HashMap<Integer, ArrayList<Integer>> hash = new HashMap<>();
        for(int i = 0; i < depth; i++){
            ArrayList<Integer> list = new ArrayList<>();
            hash.put(i, list);
        } 
        hash.get(0).add(root.data);
        hash = levelOrderTraversalHelper(root.left, root.right, hash, 1, depth);
        //ハッシュの各バリューを連結
        ArrayList<Integer> result = new ArrayList<>();
        for(Integer key : hash.keySet()){
            result.addAll(hash.get(key));
        }
        for(int i = result.size() - 1; 0 <= i; i--){
            if(result.get(i) == null){
                result.remove(i);
                continue;
            }
            break;
        }
        return result;
    }
    public static HashMap<Integer, ArrayList<Integer>> levelOrderTraversalHelper(BinaryTree left, BinaryTree right, HashMap<Integer, ArrayList<Integer>> hash, int depth, int maxDepth){
        if(left != null){
            hash.get(depth).add(left.data);
        } else {
            hash.get(depth).add(null);
        }
        if(right != null){
            hash.get(depth).add(right.data);
        } else {
            hash.get(depth).add(null);
        }
        if(depth + 1>= maxDepth) return hash;
        if(left != null) hash = levelOrderTraversalHelper(left.left, left.right, hash, depth + 1, maxDepth);
        if(right != null) hash = levelOrderTraversalHelper(right.left, right.right, hash, depth + 1, maxDepth);
        return hash;     
    }
    public static int maximumDepth(BinaryTree root){
        if(root == null) return 0;
        int maxDepth = 1;
        return maximumDepthHelper(root, 1, 1);
    }
    public static int maximumDepthHelper(BinaryTree root, int tmpDepth, int maxDepth){
        if(root.left == null && root.right == null) return tmpDepth;
        if(root.left != null && maximumDepthHelper(root.left, tmpDepth + 1, maxDepth) > maxDepth) maxDepth = maximumDepthHelper(root.left, tmpDepth + 1, maxDepth);
        if(root.right != null && maximumDepthHelper(root.right, tmpDepth + 1, maxDepth) > maxDepth) maxDepth = maximumDepthHelper(root.right, tmpDepth + 1, maxDepth);
        return maxDepth;
    }
}

しかし、この煩雑なコードもQueueを使うと以下のように大変スッキリする。

zenn.java

import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.ArrayDeque;

class BinaryTree<E>{
    public E data;
    public BinaryTree<E> left;
    public BinaryTree<E> right;

    public BinaryTree() {}
    public BinaryTree(E data) { this.data = data; }
    public BinaryTree(E data, BinaryTree<E> left, BinaryTree<E> right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
}

class Solution{
    public static List<Integer> levelOrderTraversal(BinaryTree<Integer> root){
        List<Integer> res = new ArrayList<>();
        if(root == null) return res;
        Queue<BinaryTree<Integer>> queue = new ArrayDeque<>();
        queue.add(root);
        while(!queue.isEmpty()){
            BinaryTree<Integer> node = queue.poll();
            res.add(node.data);
            if(node.left != null) queue.add(node.left);
            if(node.right != null) queue.add(node.right);
        }
        return res;
    }
}

このようにアルゴリズムとデータ構造はただ知っているだけでは大して役には立たない。
それぞれメリット・デメリットがあるので使い所を見極めるのが非常に大事だと思う。
そういう意味ではleetcodeで問題を解き続けることによってどのような時にどのデータ構造を使えば良いかが感覚的に身に付いたと思う。

仕事で役に立つの？

直接的に役に立ったことは残念ながら今のところない。
進研ゼミのように勉強したことと全く同じ問題が出るなんて仕事では稀なのだ。。
しかし類似問題が出ることもある。
あるクラスのインスタンスを格納したリストがあり、それをあるメンバ変数のもつ値によって並び替えたいといったタスクがあった。

zenn.java

class Hoge{
    char foo;
    int data;
    Hoge(char foo, int data){
        this.char = foo;
	this.data = data;
    }
}

List<Hoge> hoges = new ArrayList<>();
hoges.add(new Hoge('a',1);
hoges.add(new Hoge('b',2);
hoges.add(new Hoge('c',3);
...

こういったリストがあり、最初にfooがaのデータを、次にcのデータをといった感じで表示させたいと言ったものだった。
完全にランダムなのでソートも使えず、以下のようにコードになっていた。

for(int i=0; i<hoges.size(); i++){
    if(hoge.get(i).char == 'a') System.out.println(hoge.get(i));
}
for(int i=0; i<hoges.size(); i++){
    if(hoge.get(i).char == 'c') System.out.println(hoge.get(i));
}
...

お気づきだと思うが、遅い。。。
hogesのサイズがnで表示させたいとするとO(n^2)の計算量になる。

そこで以下のように書き換えてみた

zenn.java

Map<Character, Hoge> cache = new HashMap<>();
for(int i=0; i<hoges.size(); i++){
    Hoge hoge = hoges.get(i);
    cache.put(hoge.char, hoge);
}
System.out.println(cache.get('a'));
System.out.println(cache.get('c'));
...

最初にHashMapを使いマッピングを行うことで計算量をO(n)に減らすことが出来た。

他にもグラフ構造を使ってデータのグルーピングをしたりなどもした。
これらはデータ構造の知識がなければとてもじゃないが出来なかっただろう。

まとめ

アルゴリズムとデータ構造の学習は自分のレベルを一つ引き上げてくれたのは疑いようもない。
ただこれだけで一流にもなれるかというともちろんそんなことはない。
これはあくまでソフトウェア工学の一つのテーマに過ぎない。
UNIX,ネットワーク,DB,OOP,デザインパターンなどまだまだ自分が知らないことはたくさんある。
果てしない道のりだが情報系を出ていない人間がエンジニアとして食っていくにはこれは必須だろう。