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版で売っていたので買いました。やっぱり電子書籍だと自炊しなくて良いから楽ですね。

indexOf関数とは 実際のソースを見よう ナイーブ法ってなんぞや indexOf関数とは ドキュメント はここ。 indexOf の細かい使い方は説明はしないが、簡単にいうと二つの文字列を比較して重複する箇所がある場合にその開始部分のインデックスを返すというもの。 実際のソースを見よう どのように実装されているのかが気になったので jdkの中に存在するsrc.zipを解凍して確認してみることに。 public int indexOf ( String str ) { return indexOf ( str , 0 ) ; } public int indexOf ( String str , int fromIndex ) { return indexOf ( value , 0 , value . length , str . value , 0 , str . value . length , fromIndex ) ; } static int indexOf ( char [ ] source , int sourceOffset , int sourceCount , char [ ] target , int targetOffset , int targetCount , int fromIndex ) { if ( fromIndex >= sourceCount ) { return ( targetCount == 0 ? sourceCount : - 1 ) ; } if ( fromIndex < 0 ) { fromIndex = 0 ; } if ( targetCount == 0 ) { return fromIndex ; } char

非効率はやめよう ということでよくあるコードとして紹介されていた内容をそのままメモ。 使えるようにしておく。 public class concat { // ループごとにStringBuilderオブジェクトを生成し、2回のappend処理を行う。非効率になる可能性高し。 static String concatTest1 ( String [ ] array ) { String result = "" ; for ( String s : array ) { result += s ; // +=演算で文字列結合 } return result ; } // 効率よし。ただしイミュータブルなStringを使わないことでバグが出やすくなるためそこの安全性を取るか効率を取るかはご自由に。 static String concatTest2 ( String [ ] array ) { StringBuilder result = new StringBuilder ( ) ; for ( String s : array ) { result . append ( s ) ; // +=演算で文字列結合 } return result . toString ( ) ; } }

Javaの ? true a:b;←これ何よと思ったので Javaの ? true a:b;←これ何よと思ったので 発端はLeetCode。 Javaで書くか〜と思い、書いた後に Solution で使われていたこれ。 public ListNode addTwoNumbers ( ListNode l1 , ListNode l2 ) { ListNode dummyHead = new ListNode ( 0 ) ; ListNode p = l1 , q = l2 , curr = dummyHead ; int carry = 0 ; 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 ; if ( p != null ) p = p . next ; if ( q != null ) q = q . next ; } if ( carry > 0 ) { curr . next = new ListNode ( carry ) ; } return dummyHead . next ; } ということで調べた。 三項演算子だった。 ? true a : b ; 評価式がtrueの場合、 : の左側(この場合は a )が返る、ということで、値を返すだけならば書きやすくなる。

StringBuilderとStringBufferの違いを言えるか 違い 備考 StringBuilderとStringBufferの違いを言えるか という話。 どっちでもいいんじゃん？というのが大多数の正直な意見かもしれないがどうせ使うならいい方を使いたい。 ということで調査、アンドメモ。 違い StringBuilderはJava5で導入された。 それ以前から使われていたのがStringBuffer。 二つの違いは排他制御があるかどうか。 Java8の StringBuilder ドキュメントでは、 文字の可変シーケンスです。このクラスは、StringBufferと互換性があるAPIを提供しますが、同期化は保証されません。このクラスは、文字列バッファが単一のスレッド(一般的なケース)により使用されていた場合のStringBufferの簡単な代替として使用されるよう設計されています。このクラスは、ほとんどの実装で高速に実行されるので、可能な場合は、StringBufferよりも優先して使用することをお薦めします。 と書いてある。 StringBufferを使用すればメソッドが呼ばれる度にStringbufferオブジェクトがロックされます。 つまり排他制御が行われるわけですが、それと同時に速度も犠牲にしている。 もっというとほとんどのケースの場合、スレッドセーフである必要がないためStringBuilderの方が速いし基本はこっちを使っておけば良い、という話。 ちなみに逆にStringBufferの方が明確に良いケースってあるんですかね。 パッと思いつかないのでどこかで考えてそれでパターン分けしていれば困ることは無くなりそう。 備考 StringBuilderの構造はこんな感じ。

文字列を処理しようという時に・・・ 文字列を後ろから抽出したい時は 文字列を処理しようという時に・・・ IndexOutOfBoundsException と StringIndexOutOfBoundsException 、これらの例外に出くわすことが多いので。 メモ程度の内容。 まあ存在しないインデックスを指定するときがほとんど。 例えば以下のコードのように。 class Main { public static void main ( String [ ] args ) { String s = "abc" ; // 以下の例はいずれもStringIndexOutOfBoundsExceptionが発生する s . charAt ( - 1 ) ; s . charAt ( 3 ) ; // 抜き出し位置が存在しないので例外が投げられる s . substring ( 1 , 3 ) ; // そもそもsubstring(開始位置,終了位置)なので対応していない s . substring ( 2 , 1 ) ; } } 文字列を後ろから抽出したい時は String型 . substring ( String型 . length - 切り出したい文字列の長さ ) ; というやり方でやっといてね！とのこと。

JavaでStringを生成する時はnew生成をやめようね！！という話。 なぜ書くのか 調査でどういう結論に至ったのか JavaでStringを生成する時はnew生成をやめようね！！という話。 String s = new String ( "0123456789" ) ; という書き方の話。 なぜ書くのか String a1 = "Hoge" ; String型を宣言するときにこういう書き方をしていたが、最初のnewする書き方と何が違うのか気になったので調べてみると違うものとして扱われてたのでメモ。 調査でどういう結論に至ったのか String s = new String ( "0123456789" ) ; という書き方は通常のオブジェクト同様にヒープ領域にインスタンスを作成する。 対して、 String a1 = "Hoge" ; String a2 = "Hoge" ; この書き方は定数として定数プールに保存される。 あえてnew Stringを使う明確な理由がない限り、Stringを変数に設定する場合は、 String str = "Hoge" ; というようにリテラルを直接指定し、 new String は使わないのがセオリーとなる。 そうすればStringオブジェクトを必要最低限で済ませることができ、メモリにもまたパフォーマンス的にもよい結果となる、らしい。 ちなみに文字列を作成した場合、JVMはまず最初に定数プールを見に行き、もし定数プールに同様の文字列が存在する場合には同じ参照を与える。 String型が不変の理由もここら辺にありそう。 それはまた別の記事で調べたいときに書きます。 今回は以上。