Kuehar's Blog

二分探索の書き方 なぜこのような書き方をしなければならないのか？ 二分探索の書き方 を実装するときにPythonでは中間値の宣言を mid = ( left + right ) // 2 で済みますが、Javaでは以下のような書き方をする必要があります。 mid = left + ( right - left ) / 2 ; ちなみにこれはC++にも当てはまります。 mid = left + ( right - left ) / 2 ; なぜこのような書き方をしなければならないのか？ 何故このような書き方をしなければならないかというと、仮に left + right の値が 2^31-1 よりも大きければ、オーバーフローして負の値になるからです。 例えば、Javaでそのような長さの配列が与えられ、読み込んでしまった場合には例外として ArrayIndexOutOfBoundsException が発生します。 C++の場合には不正な書き込みが発生し、メモリ破壊などに繋がることもあります。 Pythonでは整数値にはオーバーフローがなく、オーバーフローを意識するような処理を書かなくても処理を行うため、とてつもなく大きな値でも計算時の精度は落ちません。 二分探索を書くときには気をつけようってことで一応メモを残しておきます。

LeetCodeのLongest Substring Without Repeating Charactersにて LeetCodeのLongest Substring Without Repeating Charactersにて Sliding Windowアルゴリズムを実装している例を写経している時に int [ ] chars = new int [ 26 ] ; という表現を見つけたので何故このような宣言をしているかを調べた。 結果としては単純にアルファベットの数分の領域を確保するために行なっているよう。 他にも int [ ] chars = new int [ 128 ] ; や、 int [ ] chars = new int [ 256 ] ; が存在するが、これらは int[128] は ASCII用、 int[256] は拡張 ASCII用ということだった。 ASCIIは７ビット、拡張ASCIIは８ビットを使用していることを考えれば容易に思いつくはずなのに、調べないと分からなかったので記事にしました。 多分また調べるんだろうなぁ…

この記事を書いた理由 この記事を書いた理由 最近買った Elements of Programming Interviews in Java: The Insiders’ Guide にて以下のようなコードがあったため。 これ自体は書いてあるコメントの通り配列 A と pivotIndex を引数に貰い、最初に pivotIndex より小さな値、その後に pivotIndex と同じ値、その後に pivotIndex よりも大きな値の順に配列を並び替えるというアルゴリズム。 Enum に馴染みが余りなかったため気になって調べた。 列挙型といい、使うと定数を宣言するのに読みやすいコードになるらしい。 そしてその後にちょくちょく登場する ordinal 。これは enum 型から列挙した内容の順番を取り出し、比較に使えるというもの。 定数を列挙できるのは便利なように見えるので使えたら使いたい。 でも使わないんだろうなぁ・・・ そういえばこの本はKindle版で売っていたので買いました。やっぱり電子書籍だと自炊しなくて良いから楽ですね。

出典 Elements of Programming Interviews in Python: The Insiders’ Guide (English Edition) 問題 数値の入った配列が渡されます。 偶数の値が最初に現れるように配列の値を並べ替えなければしてください。 なお、追加で配列を用意してはなりません。 解法 # List[int] -> None def even_odd ( A ) : next_even , next_odd = 0 , len ( A ) - 1 while next_even < next_odd : if A [ next_even ] % 2 == 0 : next_even += 1 else : A [ next_even ] , A [ next_odd ] = A [ next_odd ] , A [ next_even ] next_odd -= 1 # Time Complexity O(N) # The additional space complexity O(1) 値が2で割り切れる時はイテレーションのインデックスを後ろにずらし、そうでない場合には入れ替え（スワップ）と後ろのインデックスを前にずらすことで比較的容易に実装が出来ます。

仕事の時に余りにも前傾姿勢 すぎたので。 2022年は姿勢を美しくしようということでディスプレイを覗き込まなくても良い環境を作ろうと思いました。 買ったのは サンワサプライ Bluetoothキーボード SKB-BT25BK と ダイソーでたまたま売っていた300円のゲーミングマウス風マウス。 この記事もそれらを使って書いていますが中々快適。 打鍵感もいいし。 やはり外付けモニターのみだと視線が上がって覗き込まなくて良い。 当初は昇降デスクを買いたいなと思っていたけれどもそんなに必要か？という貧乏性からくるお金使いたくない欲が爆発してその案は四散した。 後捨てるのめんどくさそう。偏見かもしれないけど。 次に考えたのがPCスタンド。 でもなんか側から見たらちょっと間抜けに見えるのでボツ。 ということで貧乏性と見栄えを気にして2000円くらいのキーボードと330円のマウスでなんとかしました。 ボーナス入ったらHHKBとか買おうかと思っていたけどそんな欲も消し飛ぶくらいには落ち着いています。なんか不思議。

最長部分共通問題を解いているときに 最長部分共通問題を解いているときに 気になったので調べてみた。 最長共通部分列(Common Longest Subsequence) の問題を解いている最中にこの記事を読んでいて、あれ？これだと最長の共通部分が何文字分あるのか返せてないな、でも二次元配列ってどう返すんだっけ？ となったので調査。 ちなみに max(dp) や max(max(dp)) では返せませんでした。 結論としては ここ が参考になった。 大人しく従ったら上手く返せたのでメモがてら記事を書いておく。 max ( list ( map ( lambda x : max ( x ) , dp ) ) ) これで返すか、 from itertools import chain list ( chain ( * a ) ) max ( chain ( * a ) ) こう返すかの二択っぽい。 ちなみにつまづいていた最長部分共通問題は これ で、ソースコード(メモ化とDPを試した)は ここ 。 時間がある人はぜひ解いてみてください。

 という話。 そもそも何でそんな話に？ 文字列をバイトで区切って処理を行おうとした時の話。 これOracleから取り出すときにsubstrb関数を使ってバイト数を指定すれば楽じゃね？ という考えに至り、実際にそれを試したがテストを行った時にあらびっくり。 半角も全角も同じ桁数で区切られているじゃありませんか。 これはまずい。半角1バイト全角2バイトじゃないの！？という考えを持っていたのでパニクった。 ってことでひとまず原因を調べたところ、タイトルの内容に辿り着きました。 固定バイト数で考えられるからプラスに働くこともあるが、今回は知らないが故に時間を無駄にかけてしまった・・・ NVARCHAR2、便利なので何でもかんでもNVARCHAR2に設定していいわけではない、という教訓を得ました。 取り方を知っていれば一発で解決じゃん、という考えもあるのでコードをメモ的に取っておくと良いかも。やるかは分からない。