LeetCode - Add Two Numbers

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

問題の概要

• インプット（引数）
  • 数値の１桁ごとの値を格納した連結リスト（ただし数字は逆順になっている）を２つ
    • 例：(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;  // 繰り上がり用の値
        
        // ２つの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;
    }
}

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

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

---

関連サイト

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

LeetCode - Two Sum

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

問題の概要

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

「社会は変えられる: 世界が憧れる日本へ」

「社会は変えられる: 世界が憧れる日本へ」
たまたまこの本を知る機会があり、読んでみました。

社会は変えられる: 世界が憧れる日本へ

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

超高齢社会を迎え、医療費・介護費の膨張には歯止めがかからず、今や世界に冠たる国民皆保険制度は風前の灯火。
ところが医療関係者や製薬企業などの“専門家"は、古い制度や体制に守られ、同時に縛られ、「沈みゆく豪華客船」の中での席取り合戦に終始するばかり。
この苦境を乗り切るため、現役官僚の著者は、社会・経済システムの見直しによる「生涯現役社会」の創設を説く。
社会全体が変わる中で初めて持続可能な社会保障制度の構築が可能になるという。
前途多難に違いないが、関係者がより広い視点から問題を捉えて行動することができれば、
誰一人切り捨てることなく国民皆保険制度を維持する道が見えてくると主張する。
著者は実際にこれまでも、業界内では「不可能」と考えられていた数々の課題に、“部外者"の視点から切り込み、改革を成し遂げてきた。
その経験から、絶望するのは、まだ早いと説く。著者が思い描くのは、次世代に残すべきこの国の未来であり、
世界が羨望と畏敬の念を持って見つめる「憧れの国」日本の姿だ。

目次は以下の通りです

• 第一章： 問題の本質を問い直す
• 第二章： 時代に合わなくなった社会保障制度
• 第三章： 社会は変えられる！ ー 時代に合わない「制度」、業界の「常識」への挑戦
• 第四章： 世界が憧れる日本へ

以下は、導入となっている「はじめに」の部分からの一部抜粋です

先が見えない難しい状況に陥った時に、私たちは往々にしてこれまで通りのやり方を押し通そうとするか、
「仕方がない」と言ってなにもしないことを正当化してしまうものです。
ところが、一歩引いてより広い視座から全体を俯瞰できるかどうかで、その後の展開は大きく変わります。
対応策が見つからなかった課題でも、違った視点から眺めることで、思いがけないヒントが見つかるものです。
現在、日本の社会保障制度は聞き的な状況にあります。
・・・なかでも「年金」の問題は、将来自分が受け取るお金の話ですから、不安に感じる人も多いでしょう。
・・・実は「年金」よりも遥かに深刻な問題を抱えているのが、日本の医療を支える「国民皆保険制度」です。
誰もが当たり前のように利用している公的医療保険が危機的な状況にあります。
・・・

これら含めて日本の現在の医療に関わる制度を、一度乗船すればいつでも自由に最高の食事などを楽しむことができて目的地まで運んでくれる「豪華客船」に例えています。
ただし、この「豪華客船」は今のままでは沈みゆくことがほぼ確実です。
これは、この筆者が指摘しているだけではなく、多くの場面で課題として上がっており、間違いないことです。

筆者は、今一度日本の医療制度の問題点を整理して、どう対策を打つかというよりも、社会の変化に対してどう考え方や構造を変えるべきかといったところを主張しています。

特に、発症した病気を「治す」医療から「予防」や「管理」を基本とする医療へ転換する　という主張は完全に同意します。

ただ、日本の医療制度の問題に対して、あまりに大きな変革が必要となるため、いくら主張されても本当にそんなことが可能なのかと思えてしまいます。
しかし、筆者は官僚としてこれまで多くの無理だとしか思えない課題に取り組み、なんとか解決へ導いてきた事例を三章で述べています。
正直、この章で少ない文章にまとめて書かれていますが、
筆者がいくつものとんでもない苦難へ立ち向い、ギリギリのところまで努力・実行することを諦めず、解決へ導いてきた話は驚きしかありません。

三章の内容を読んでいくつもの難題を解決したこの筆者の主張であれば、医療に関する各種変革に対する話も可能性はゼロではないと感じました。
そしてこの筆者が警鐘を鳴らす問題であるからこそ、日本の医療に関する問題が本当に深刻で、タイムリミットが迫っているとも思えました。

この本を読むべきターゲットは、基本的に日本人全員だと思います。
おおげさな言い方かもしれませんが、現代の日本人がこの筆者の主張を一旦理解することが重要な気がします。
（もちろん、単純な賛成だけではなく批判も出てくると思いますが、とにかくこの本で分かりやすく書かれている現在の日本の課題を理解すべきだと思います）