覚えたら書く

IT関係のデベロッパとして日々覚えたことを書き残したいです。twitter: @yyoshikaw

LeetCode - Maximum Depth of N-ary Tree

LeetCode の Maximum Depth of N-ary Tree を解いてみます。

問題の概要

  • インプット(引数)
    • N個のNodeを持つツリー
  • アウトプット(引数)
    • ツリーの中の中の最大の深さ
    • 最大の深さ = root Nodeから最も遠いリーフNodeまでの最長パス上のNodeの数


ツリーの各Nodeを表現するクラスは以下のように定義されています

import java.util.List;

class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
}


答え

各リーフNode(childが存在しない)まで再帰的に探索して深さを導いて、その最大値を返します。

class Solution {
    public int maxDepth(Node root) {
        if (root == null) {
            return 0;
        }

        int max = 0;
        for (Node child : root.children) {
            max = Math.max(max, maxDepth(child));
        }
        return 1 + max;
    }
}

LeetCode - Reverse String

LeetCode の Reverse String を解いてみます。

問題の概要

  • インプット(引数)
    • charの配列
      • 例:[’h’, 'e', 'l', 'l', 'o']
  • アウトプット(引数)
    • 引数で与えられた配列を逆順にします。アウトプットは戻り値で返すのではなく、引数の配列の内容を逆順にします
    • 例にあげた引数の場合、['o', 'l', 'l', 'e' , 'h'] がアウトプットになります
  • 補足
    • 答えを求めるために新しい配列をallocate(生成)しないでくださいと書いてあります


答え

特に小細工もなく、配列の先頭から順に対応するindex同士の要素をswapするようにしています。
配列の中心位置まで進めば全て入れ替わって、逆順になっていることになります。

class Solution {
    public void reverseString(char[] s) {        
        if (s.length <= 1) {
            return;
        }
        
        int lastIndex = s.length - 1;

        char temp;
        for (int i = 0; i < s.length / 2; i++) {
            temp = s[i];
            s[i] = s[lastIndex - i];
            s[lastIndex - i] = temp;
        }
    }
}

特に難しさも無いのかなというイメージです。
理由は不明ですがこの問題の評価あんまり高くないです。

LeetCode - Add Two Numbers

LeetCode の Add Two Numbers を解いてみます。

問題の概要

  • インプット(引数)
    • 数値の1桁ごとの値を格納した連結リスト(ただし数字は逆順になっている)を2つ
      • 例:(2 -> 4 -> 3)(5 -> 6 -> 4) (342と564の数値を逆順の連結リストで表したもの)
  • アウトプット(戻り値)
    • 与えられた連結リストが表す元の数値どうしを加算したものを連結リストに格納したもの(これも逆順にする)
      • 例にあげた引数の場合、 342 + 465 = 807 なので {7 -> 0 -> 8} を返す必要がある


ちなみに連結リストのクラスは以下で定義されています

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}


答え

解答のコード例としては以下になります。順に各桁を加算していくことになります。
最終的な答えを格納するためのダミーの連結リスト(ListNode)を用意しておきます。

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // ダミーのListNode. 最終的な答えはnext以降に連結される
        ListNode dummyHead = new ListNode(0);
        
        ListNode p = l1;
        ListNode q = l2;
        
        ListNode curr = dummyHead;  // 現在の計算位置
        
        int carry = 0;  // 繰り上がり用の値
        
        // 2つのListNodeのどちらかの終端に来るまで繰り返す
        while (p != null || q != null) {
            int x = (p != null) ? p.val : 0;
            int y = (q != null) ? q.val : 0;
            int sum = carry + x + y;  // 繰り上がりも考慮して加算
            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            
            // 与えられたListNodeの長さは異なる場合もあるので、各々nullチェック必要
            if (p != null) {
                p = p.next;
            }
            if (q != null) {
                q = q.next;
            }
        }
        
        // 最終的に繰り上がっていたらそれも連結する
        if (carry > 0) {
            curr.next = new ListNode(carry);
        }
        
        // ダミーのListNodeの先頭の0という値は意味がないので、next以降の連結リストを返す
        return dummyHead.next;
    }
}

以下のあたりの考慮が抜けないようにしないといけません

  • 加算時の繰り上がり
  • 引数の連結リストの長さは違うかもしれない(数値の桁数が異なるかもしれない)
  • 1番最後の繰り上がり(数値の先頭桁での繰り上がり)



関連サイト

https://euro.qrunch.io/entries/Zu9MHIWO1O4bI4Hv

LeetCode - Two Sum

LeetCode の Two Sum を解いてみます。

問題の概要

  • インプット(引数)
    • 数値の配列とターゲットの数値
  • アウトプット(戻り値)
    • 与えられた配列の数値を足し合わせてターゲットの数値と一致する2つの数値の組み合わせ。その2つの数値のインデックスを配列で返す。
  • 補足
    • 与えられる数値群から必ず一意に答えが得られると仮定してよい。同じ要素は二度使用しない。


Brute Force

ブルートフォース(総当たり)のアプローチでやると以下のようになります。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int complement; 
        for (int x = 0; x < nums.length; x++) {  
            complement = target - nums[x];
            for (int y = 0; y < nums.length; y++) { 
                //同じ値は利用しないので除外する(次に処理を移す)
                if (x == y) { 
                    continue;
                } 
                if (nums[y] == complement) {
                    return new int[] {x, y};
                }
            }            
        }
        throw new IllegalStateException("params is invalid");
    }
}

これだと、Status = Accepted, Runtime = 36ms, Memory = 37.5 MB という結果になりました。


One-pass Hash Table

候補となる数値を見つけながら順次HashMapに値を格納していくやり方です。

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // key=加算の候補の数値, その数値が格納されていた配列上のindex
        Map<Integer, Integer> map = new HashMap<>();
        map.put(nums[0], 0);  // numsの最初の数値だけでは絶対に答えは求まらないのでとりあえずHashMapに格納する

        int complement;
        for (int i = 1; i < nums.length; i++) {
            complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] {i, map.get(complement)};
            }
            map.put(nums[i], i);
        }
        throw new IllegalStateException("params is invalid");
    }
}

これだと、Status = Accepted, Runtime = 2ms, Memory = 37.3 MB という結果になりました。

総当たりでやるよりも効率的です。

他にも Two-pass Hash Table というやり方もあります。具体的な解説は LeetCode の Solution を読んでもらった方が良いです。



関連サイト

文字型(char型)に対するInteger.valueOfの結果

Java で 数字の文字列を int型に変換する際には、Integer.valueOf を利用するのが一般的です。

例えば以下のような感じ。

public class ToInteger {
    public static void main(String[] args) {
        System.out.println(Integer.valueOf("1"));
        System.out.println(Integer.valueOf("2"));
        System.out.println(Integer.valueOf("3"));
        System.out.println(Integer.valueOf("4"));
        System.out.println(Integer.valueOf("5"));
    }
}


出力結果

1
2
3
4
5

なんの変哲もない結果です。


では、これをString型ではなくchar型でやってみましょう。

public class ToInteger {
    public static void main(String[] args) {
        System.out.println(Integer.valueOf('1'));
        System.out.println(Integer.valueOf('2'));
        System.out.println(Integer.valueOf('3'));
        System.out.println(Integer.valueOf('4'));
        System.out.println(Integer.valueOf('5'));
   }
}


出力結果

49
50
51
52
53

ほとんどの人が望んでいない結果が出力されています。


最初のString型でのInteger.valueOfInteger.valueOf(String s) が呼び出されていますが、
後者のchar型の場合は、Integer.valueOf(int i) が呼び出されています。

というわけでchar型の場合 int型にキャストされて Integer.valueOf が呼び出されているのと同様です。


char型の値を int型 にキャストした値を出力してみると

public class ToInteger {
    public static void main(String[] args) {
        System.out.println((int) '1');
        System.out.println((int) '2');
        System.out.println((int) '3');
        System.out.println((int) '4');
        System.out.println((int) '5');
    }
}


出力結果

49
50
51
52
53

さきほどと同様の結果が出力されます。これはASCIIコードになっている状態です。


では、数字を意味するchar型をそのままの見た目の数値に変換したい場合、どうすればいいかというと Character.getNumericValue というメソッドが用意されているので、これを使いましょう。

public class ToInteger {
    public static void main(String[] args) {
        System.out.println(Character.getNumericValue('1'));
        System.out.println(Character.getNumericValue('2'));
        System.out.println(Character.getNumericValue('3'));
        System.out.println(Character.getNumericValue('4'));
        System.out.println(Character.getNumericValue('5'));
    }
}


出力結果

1
2
3
4
5

望んだ結果となりました。


まとめ

Java で char型を利用するケースが必ずしも多くないため、こんな挙動について知らなくてもいいかもしれないですが、
はまると一瞬混乱を招くので、一応Character.getNumericValueなどの存在も知っておいても損は無いかもしれません。