覚えたら書く

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

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などの存在も知っておいても損は無いかもしれません。

「仕事ごっこ ~その“あたりまえ”、いまどき必要ですか?」

「仕事ごっこ ~その“あたりまえ”、いまどき必要ですか?」 を読んでみました。

仕事ごっこ ~その“あたりまえ

仕事ごっこ ~その“あたりまえ"、いまどき必要ですか?


内容紹介は以下のようになっています

「郵送」「印刷して配布」
「とりあえず打ち合わせ」
「手書き」「メールを送ったら電話で確認」「押印」
「メール添付で圧縮してパスワードつけて、パスワードは別送」
「ひたすらテレアポ」「とにかく相見積り、コンペ」
「年末年始の挨拶や表敬訪問」「スーツ&ネクタイ」「ダイバーシティごっこ」

ちょっと待って、それってホントに必要ですか?

仕事のスピードを遅くし、時間をムダにし、成長機会を奪い、社外の人とのコラボレーションを邪魔し、
優秀な人を遠ざける慣習やルール――それが、“仕事ごっこ"。

これまでの常識を、シニカルなものがたり+ツッコミで、笑い飛ばしながらアップデート! 


この本では冒頭で、仕事ごっこ を以下のように定義しています。

  • 生まれた当初は合理性があったものの、時代や環境や価値観の変化、および技術の進化にともない、生産性やモチベーションの足をひっぱる厄介者と化した仕事や慣習。
  • コラボレーション、ひいてその組織とそこで働く人の剣山な成長を邪魔する形骸化した仕事や慣習。あるいは、仕事のための仕事。


冒頭では、さらに以下のようにも書かれています。

仕事は生きものです。生まれた当初は意味があった。しかし、時代の変化、法制度の変化、テクノロジーの変化、働く人たちやお客さんの価値観の変化・・・さまざまな変化の中で、やがて陳腐化し、時代遅れになります。
そうして、いつの間にか私たちの足をひっぱる厄介者になってしまっているのです。
仕事は生きもの。だからこそ、いったん立ち止まり、正しくアップデート(最新化)していかなければなりません。


この後、各章で、特に大企業でありがちな 仕事ごっこ の事例が紹介されています。

よく分かるなーと思える事例もあれば、まだそんなことしてるの?とさえ思う事例もあります。
どれもこれも、当初は何らかの意味があったのでしょうが、今となっては仕事の生産性を落とすだけのものと化しているものがほとんどです。


薄い本で内容も平易なので、すぐ読み終わることができます。


ただし、難しいなーと思ったのが、
この本をもっとも読んでほしい上級の役職の人ほど、この本を手に取ることはないだろうということです。

若手の方が読んで、内容に納得し自分より下の世代には 仕事ごっこ が残らないように努力するしかないのかな・・・
と、なかなか難しさも感じました。