きょうのJAVA part 4
今日やったこと
ALDS1_8_A Binary Search Tree Ⅰ
https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/8/ALDS1_8_A
insert と print のみの二分探索木 二分探索木は 左の子のキー ≦ 親のキー ≦ 右の子のキー になるような木のこと 出力は中間順巡回 → 先行順巡回の順で出力 親を保存しておいて自分のキーと二分探索木の根のキーと大きさを比べていく null になれば終了
ALDS1_8_B Binary Search Tree Ⅱ
https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/8/ALDS1_8_B
上のやつに find を追加した二分探索木 節点が null になるかキーが一致するまで二分探索木の根のキーと大きさを比べていく 見つかったらその節点を返す 見つからなかったら null を返す null なら no それ以外は yes
ALDS1_8_C Binary Search Tree Ⅲ
https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/8/ALDS1_8_C
上のやつに delete を追加した二分探索木 正直あんまり理解できていない 何をしてるかはなんとなくわかる 子がいるかいないかで操作が変わる いなければその節点を消去するだけでいい ひとつしかないならその子を消した節点のところに持ってくる ふたつあるときはその節点の次に大きい節点を見つけてくる必要がある これを successor とかって言うんだっけ 2パターンあるから注意 あとは君の目で確かめてくれ
きょうのJAVA part 3
今日やったこと
ALDS1_12_A Minimum Spanning Tree
https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/12/ALDS1_12_A
みなさんご存じプリム法ですね 私は知らないです
任意に選んだ始点から行くことのできる節点の中で、一番重みが少ない節点に行く だったかな あまり詳しくは覚えていない
本当に任意の始点から始めても同じなのか試したら同じだった プリムさんすごい
まだ木構造を完全に理解しているわけではないので解像度を上げたい
ちなみに自力で書こうとしたら答えがオーバーフロウしました だめだね
ダイクストラ法の元になってる？らしい 詳しくないからこれ以上語るとボロがでそうなので終わっておこう 詳しく知りたい人は下の記事を見るといいかも
プリム法による最小全域木を求めるアルゴリズム | アルゴリズムロジック
やっぱりわからないものがわかるようになるのは楽しいね 人生は勉強や
きょうのJAVA part 2
今日やったこと
ALDS1_8_A Binary Search Tree Ⅰ
https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/8/ALDS1_8_A
Cでは疑似コード通りに書いて通した JAVAでは...？
TLEです クソデカテストケースは時間切れ 一応4までは通った
class でノードを作っていろいろした 先人の知恵は参考にしよう
多分もっと簡単にできるパッケージ？があるんだろうけど、如何せん Scanner しか入れられないので...
しかし
ALDS1_8_B Binary Search Tree Ⅱ
https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/8/ALDS1_8_B
こいつは通るんだなこれが どうしてかは知らない おしえてえろえらいひと
まあこれで木が実装できることがわかったのでとりあえずヨシ！
明日はもっと書けるよね！ハム太郎！
・
・
・
・
・
・
・
ﾍｹｯ
きょうのJAVA part 1
今日やったこと
ALDS1_7_A Rooted Trees
https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/7/ALDS1_7_A
深い再帰をすると [java.lang.StackOverflowError] が出るみたい
もしくは無限再帰
先駆者のコードを見ると <ArrayList> なるものを活用している
私が import 出来て使えるものは Scanner のみ（03/09現在）なのでとりあえず後回し
ALDS1_7_B Binary Trees
https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/7/ALDS1_7_B
ALDS1_7_C Tree Walk
https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/7/ALDS1_7_C
こっちは簡単に通った n が小さいから再帰が少なく済むんだろうな
