アルゴリズム1000本ノック（１０）: Lowest Common Ancestor of a Binary Tree
問題
LeetCode より拝借しています.
２分木とそのノードである２点が与えられた時, ２点の最も下位の
共通親ノード = lowest common ancestor (LCA)
を返却するアルゴリズムを実装せよ.
WikipediaによるLCAの定義:
"The lowest common ancestor とは２分木 T における２ノード
v, w 間において v, w両方を子孫に持つ中で最も下層にある親ノードを指す.
(v, wの一方が他方の親となっている場合も含める)."
_______3______
/ \
___5__ ___1__
/ \ / \
6 _2 0 8
/ \
7 4
例えば, 上の木においてノード 5 と 1 の the lowest common ancestor (LCA) は
3 となる. また 5 と 4 の場合は 5 となる.
解法
一方のノードを P 他方を Q と呼ぶことにします. この問題を解くには, 親ノートから P, Q にいたる経路を何らかの情報で取得する必要があります.
たとえば全ノードを探索して, ノードをキーとに, その親を値に持つハッシュマップを構築することを考えます. そうすると, 平均ではO(1)で P -> Pの親 -> ... と Q -> Qの親 ->... と順にrootまで親をたどっていくことが可能になるので, お互いのrootまでの経路で最後に共通のノードだったものがLCAだということが分かります. 素直に両方の経路を比較すると O(MN) (M, Nはそれぞれの経路長) の時間がかかってしまうので, ここでも片方をまず走査して存在するノードをすべてハッシュマップ (あるいはSet, 集合でも構いません. 検索が平均で O(1) なデータ構造であることがキモです) に保存して, あらためて他方を順に走査していき, ハッシュマップに存在している最後の値を求めます.
Python code:
Java code:
計算量: O(K) (Kは与えられた木の要素数), これは子 -> 親 データを格納するハッシュマップの構築がボトルネックとなるためです.
空間量: O(K), これも上に同様です.
上ではハッシュマップを用いて子から親へとたどっていきましたが, もっと素直にrootからP, およびQへの親から子までの経路を保存する方法も有効です. この場合は root - P の経路, root - Q の経路をrootからたどっていき, 最初に２経路間で異なるノードが出現したときの直前のノードがLCAとなります.
Python code:
Java code:
経路はListでも問題無いですが, 先頭と末尾だけを扱うため Deque でも問題なく機能します. 再帰が少しわかりにくいですが, 対象のノードが見つからなかった場合は 経路に保存したノードは廃棄して状態を元に戻す必要があるため, findPath / constructPath メソッドの最後にその処理を行っています.
アルゴリズム1000本ノック（９）: Longest Substring Without Repeating Characters
問題
本問は LeetCode から引用しております.
与えられた文字列から, 同じ文字を含まない最長の部分文字列の長さを返却せよ. たとえば "abcabcbb" であれば "abc" の長さ3, "bbbbb" であれば "b" の長さ1となる.
解法
与えられた文字列を1度走査するだけで解くことができます. 各文字について, 既に文字列中に存在していたかどうかを把握するために HashMapにインデックスを値として格納していきます.
上図の例のように, 重複する文字を見つけるまではひたすら長さを伸ばしていき, あるインデックス j で重複を検出( その文字列は既にインデックス i に存在していた ) したら, その時点での最長の文字列は S[i+1] 〜 S[j] になる事がわかります.
それ以降の走査においてはインデックス i+1 以降のみを対象に同じ処理を繰り返していきます. つまりここから先では i+1 を開始点としてそれ以前に文字が存在していたかどうかは気にしなくてよくなる, ということです.
Java code:
計算量: O(N), space 空間量: O(N) (Nは与えられた文字列長).
アルゴリズム1000本ノック（８）: Add 2 numbers
Problem
問題は LeetCode より拝借しています.
正の整数を保持する２つの単方向リストが与えられた時, 各要素を１つの桁のように考えて ２つのリストの合計値を保持するリストを返却せよ. 次の要素への桁上りも考慮すること. Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8
Solution
整数同士の足し算の筆算を行うようなイメージです. （見た目的には低い位と高い位の順番が逆ですが） ２つのリストの先頭から開始して, 合計値を求め, 10以上の場合は次の要素の計算に1を持ち越していく繰り返しです. 先に片方のリストが空になった場合は一方の値だけを合計値として扱います. 両方のリストが空になった時点で計算は終了です.
最後の計算結果が10以上であった場合には, 最後に1を持ち越しておくことをお忘れなく.
Java code:
Nを２つのリストの内長い方の長さだとして, 計算量・空間量ともにO(N)となります.
ただし空間量に関しては, 今回のプログラムでは結果の格納に新しい単方向リストを用意していますが, 実際には片方のリストを上書きしていく形でも実行結果に影響は及ぼしません. この場合は余分な空間量は消費しないことになります.
Tax Return(確定申告)の延長申請 -CA州の場合-
今年もTax Returnの〆切が近づいてきて、周りの方々もバタバタと用意しております。
自分も遅ればせながらTurboTaxあたりで挑戦しようとしてみたのですが、
今年は移民手続き等の関係もあってちょっとどう処理すればいいのか
分からないケースも含まれていて、結局会計士さんにお願いすることにしました。
アメリカの確定申告は〆切に間に合わない場合は延長申請を出す事で期限を
延ばすことができます。最終的に今年は〆切に間に合ったのですが、
そちらの提出も途中まで考えていたので、そのやり方を書き残しておきます。
1. IRS向け
Form4868を提出します。こちらを締切日までに提出できればとりあえず延長が可能です。オンラインでも申請可能ですので、間に合いそうに無い方はチェックしてみると良いかと。
書き方は特に迷う部分は無いと思いますが、支払情報の部分に注意が必要です。
この延長申請はあくまで確定申告のフォームを提出する〆切の延長であって、税金の支払い期限の延長ができるわけではないのです。
したがって、支払い額をestimateでも構わないので計算し、このフォームを郵送で
提出する場合は小切手を同封するか、オンラインの場合は支払いもオンラインで
同時に済ませてしまいましょう。
多めに払うことに問題はありません、きっちり申告すればそのあと返ってきます。
少なかった場合はペナルティとして利子が発生してきますので、注意が必要です。
なおSSNがまだ手に入っていない場合はITINの番号が必要となりますが、
それもない場合は"ITIN TO BE REQUESTED", あるいは"SSN TO BE REQUESTED"
などと記載して出しておくと良いみたいです（参考）。
2. 州向け
カリフォルニア州は2015年現在、「延長の自動適用」が認められている州の
１つですので、特に何もしなくても、IRS向けの延長申請さえ出してしまえば
あとで同時に確定申告書類を出すのみで、何の問題もありません。
注意:
自分は会計士ではないので、ここに掲載されている情報は2015年時点で私が調べられた範囲でのものとなります。この情報を鵜呑みにして問題が発生しても責任は取りかねますので、不安な方はご自身でよく調べるか、会計士さんの助けを借りるのが一番だと思います。
