2

次のグリッドがあります。

A B C D
E F G H
I J K L
M N O P
Q R S T
U V W X
Y Z

カーソルは常に A から始まり、左 (L)、右 (R)、上 (U)、下 (D)、Enter (E) の操作があります。質問: 文字列が与えられた場合、その文字列を生成する一連の操作を出力してください。

例えば ​​：

> INPUT : CGH 
> OUTPUT : R R E D E R E

この質問は面接で私に聞かれました。

My approach: マンハッタン距離を計算してグラフ上で BFS を実行することでこれを解決しようと考えましたが、最適ではないと思います。さらに、すべての文字のマンハッタン距離を変更する必要があります。前もって感謝します

4

4 に答える 4

3

素朴なアプローチから始めることができます。ヒント: 最初のシーケンスを行列として見てください。すべての文字には位置があります: 行と列のインデックスです。

ステップ1。

ハッシュテーブルを作成します:キーは文字、値は 2 次元行列のインデックスです。これを高速検索に使用します。たとえば、文字「C」が与えられた場合、その行列インデックスは何ですか? [0,2]です。

入力を繰り返し処理して保存する必要があるため、ビルドには O(N) 時間と O(N) スペースが必要です。文字を解決するには、平均的なケースで O(1) かかります + 適切なハッシュ関数を使用する場合、O(N) の最悪のケースは問題になりません。

ステップ2。

入力から 2 文字を指定すると、オフセットが解決されます。これにより、出力シーケンスの目的のチャンクが得られます。

これには O(1) 時間と O(1) スペースが必要です。

ステップ 3。

シーケンスの最後に到達するまで、手順 2 を繰り返します。

これには、出力の構築に使用される O(N) 時間と O(N) スペースが必要です。

概要。

このソリューションでは、ハッシュテーブルを使用して文字をすばやく検索します。パス (L/R/U/D/E) を解決するためのオフセット O(N) 時間の計算量と O(N) の空間計算量も必要です。

于 2012-09-02T20:26:57.453 に答える
1

まず、グリッド内の文字の位置は簡単に計算できます。

function get_pos( c : char)
begin
  int col ← (c-'A') modulo 4
  int row ← (c-'A') div 4
  return (row,col)
end

位置 (6,2) と (6,3) を使用できると仮定します

セル座標間の減算を次のように簡単に定義できます。

function subtract( pos1, pos2 : position )
begin
  return (pos2.row-pos1.row, pos2.col-pos1.col)
end

減算によってペア (x,y) が得られる場合、パスは単純に文字 'R' の x 倍 (x が正の場合) または x が負の場合 'L' であり、x がゼロの場合は何もない可能性があり、同様に y 倍の文字 'D ' y が正の場合、または y が負の場合は「U」、y がゼロの場合はおそらく何もない場合、文字「E」で終了します。

function print_row_path( pos1, pos2 : position )
begin
  path ← subtract(pos1,pos2)
  if path.row > 0 then
    print_times_char(path.row,'R')
  else if path.row < 0
    print_times_char(-path.row,'L')
  end if
end


function print_col_path( pos1, pos2 : position )
begin
  path ← subtract(pos1,pos2)
  if path.col > 0 then
    print_times_char(path.col,'D')
  else if path.col < 0
    print_times_char(-path.col,'U')
  end if
end

function print_path_direction( pos1, pos2 : position ; first_direction : direction )
begin
  if (first_direction = FIRST_MOVE_ROW) then
    print_row_path(pos1,pos2)
    print_col_path(pos1,pos2)
  else
    print_col_path(pos1,pos2)
    print_row_path(pos1,pos2)
  end if
  print 'E'
end

function print_path(start, end : char)
begin
  position pos1 ← get_pos(start)
  position pos2 ← get_pos(end)
  print_path_direction(pos1,pos2, FIRST_MOVE_ROW)
end

print_times_char(t,c) は、文字 c の t 倍を出力する関数です。パス印刷の 2 つの「フレーバー」を定義しました。1 つは行の動きを最初に印刷し、もう 1 つは列の動きを最初に印刷します。

位置 (6,2) と (6,3) が禁止されていると仮定します

位置 (6,2) と (6,3) の使用が許可されていない場合:

  • 'A' ≤ start,end ≤ 'X' または 'Y' ≤ start,end ≤ 'Z' の場合: (6,2) または (6.3) はパスで使用されません
  • if 'A' ≤ start ≤ 'X' and 'Y' ≤ end ≤ 'Z' : 禁止されたセルを使用しないようにするには、最初に列の動きを出力します
  • if 'A' ≤ end ≤ 'X' and 'Y' ≤ start ≤ 'Z' : 今回は行の動きを最初に出力する必要があります

擬似コード:

function print_path_wo_forbidden(start, end : char)
begin
  position pos1 ← get_pos(start)
  position pos2 ← get_pos(end)
  if if 'A' ≤ start ≤ 'X' and 'Y' ≤ end ≤ 'Z' then
    print_path_direction(pos1,pos2, FIRST_MOVE_COLUMN)
  else
    print_path_direction(pos1,pos2, FIRST_MOVE_COLUMN)
  end if
end

複雑

2 つの位置の間のパスの出力は明らかに O(1) で行われるため、長さ n の文字列の場合、O(n) アルゴリズムを構築できます。

于 2012-09-02T22:09:27.717 に答える
0

文字を座標のペアA = [0,0], F = [1,1]などで表すことができます。その後、現在の文字と目的の文字の間のオフセットを計算してそれを使用するだけです。

于 2012-09-02T20:09:57.050 に答える
0

oleski が言ったことですが、正直なところ、特に言語にネイティブのハッシュテーブルがない場合、ハッシュテーブルは不必要なプログラミング作業が多すぎます。

多くの場合、次のように配列を使用してグリッドの位置をマッピングする方がはるかに簡単です。

struct point{
   int x; 
   int y;
};

point map[256];
point['C'] = (0,2);
于 2012-09-02T23:38:55.103 に答える