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步。

建立一个哈希表：键- 是字母，值- 是二维矩阵中的索引。您将使用它进行快速查找，例如给定字母“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)，则路径只是 x 乘以字符“R”（如果 x 为正）或“L”（如果 x 为负），如果 x 为零，则可能什么都没有，类似地，y 乘以字符 'D ' 如果 y 是正数，或者 'U' 如果 y 是负数，如果 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) 是打印 t 次字符 c 的函数。我定义了路径打印的两种“风格”，一种先打印行移动，另一种先打印列移动。

假设位置 (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

复杂

打印两个位置之间的路径显然在 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 回答