2011年12月11日日曜日

TopCoder SRM272 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。問題文について、おおまかに説明する。

2つの数のハミング距離というものは2進数表現したときに、値が異なる位置の数である(同じ長さにするために、先頭に0を補うこともある)。例えば"11010"と"01100"は1、3、4桁目の値が違うので、ハミング距離は3になる。numbers[]といういくつかの2進数が文字列が配列として与えられる。それらの数からもっともハミング距離が小さくなる組のその距離を返せ。なお、numbers[]に登場する文字列はすべて長さが同じになっているものとする。

私の解答はこちら。

public class HammingDistance {

 public int minDistance(String[] numbers) {
  int max = numbers[0].length();
  for( int i=0 ; i<numbers.length ; i++ ){
   for( int j=i+1 ; j<numbers.length ; j++ ){
    int diff = 0;
    for( int k=0 ; k<numbers[i].length() ; k++ ){
     if( numbers[i].charAt(k) != numbers[j].charAt(k) ) diff++;
    }
    if( diff < max ) max = diff;
   }
  }
  return max;
 }

}

得点は246.57/250で比較的容易に解けました。i、jの2重ループで2つの文字列の組を、kで比較するので全部で3重ループになりました。

0 件のコメント:

コメントを投稿

フォロワー

ブログ アーカイブ

ページビューの合計