单程飞行问题

构建一个哈希表,并将每个机场添加到哈希表中。

<key,value> = <airport, count>

如果机场是来源地或目的地,则机场计数将增加。因此,对于每个机场,计数将为2(SRC为1,DST为1),但您旅行的来源和目的地除外,该计数将为1。

你至少要看一次每张票。所以复杂性是O(n)。

总结:下面给出了一个单通算法 . (也就是说,不仅仅是线性的,而是每张票的外观 确切地 一次,这当然是每张票的最佳访问次数)。我之所以总结,是因为有许多看似等效的解决方案,很难找出我添加另一个解决方案的原因。:)

我在一次采访中被问到这个问题。这个概念非常简单:每一张票都是一个单件清单,有概念上的两个元素,SRC和DST。

我们将每一个这样的列表用其第一个和最后一个元素作为键索引到哈希表中,这样,如果一个列表开始或结束于一个特定的元素(机场),我们可以在O(1)中找到它。对于每一张票,当我们看到它从另一张票结束的地方开始时,只需链接这些票(o(1))。类似地,如果它以另一个列表开始的位置结束,则另一个列表联接。当然,当我们链接两个列表时,我们基本上会销毁两个列表并获得一个列表。(n张票的链将在n-1这样的链接之后构建)。

需要注意保持不变,即哈希表键恰好是剩余列表的第一个和最后一个元素。

总而言之,O(N)。

是的,我当场回答了:)

编辑 忘了加一个要点。每个人都提到 二 哈希表,但也有一个这样的技巧,因为算法不变量最多包括它 一 票列表从任何一个城市开始或开始(如果有两个城市,我们将立即加入该城市的列表,并从哈希表中删除该城市)。渐进地没有区别,这只是简单的方法。

编辑2 同样有趣的是,与使用2个具有n个条目的哈希表的解决方案相比 每个 ,此解决方案使用一个哈希表 至多 N/2个条目(如果我们按顺序(例如,1、3、5等)看到票,就会发生这种情况)。因此,除了速度更快之外,它还使用了大约一半的内存。

构造两个哈希表(或尝试),一个在SRC上键入,另一个在DST上键入。随机选择一个票据,并在SRC哈希表中查找其DST。对结果重复该过程,直到到达终点(最终目的地)。现在在DST键控哈希表中查找其SRC。对结果重复该过程,直到到达开始处。

构造散列表需要O(n),构造列表需要O(n),所以整个算法是O(n)。

编辑:实际上,您只需要构造一个哈希表。假设您构造了SRC键控哈希表。随机选择一张票,像以前一样,构建通向最终目的地的清单。然后从尚未添加到列表中的票据中选择另一个随机票据。沿着它的目的地走,直到你找到你最初开始使用的票为止。重复此过程,直到构建完整个列表。这仍然是O(N),因为最坏的情况是你以相反的顺序选择票。

编辑:在我的算法中交换了表名。

它基本上是一个依赖关系图,其中每个票据表示一个节点,并且 SRC 和 DST 机场代表有向链接,因此使用拓扑排序来确定航班顺序。

编辑:尽管这是一张机票,而且你知道你实际上已经制定了一个你可以实际执行的行程,按照UTC中的出发日期和时间排序。

edit2:假设每个机场都有一张使用三个字符代码的机票,则可以使用此处描述的算法( Find three numbers appeared only once )通过将所有机场合并来确定这两个独特的机场。

EdTe3:这里有一些C++来使用XOR方法来实际解决这个问题。总体算法如下,假设从机场到整数的唯一编码(假设机场代码为三个字母,或者使用经纬度将机场位置编码为整数):

首先,xor把所有机场代码放在一起。这应该等于初始源机场或最终目的地机场。因为我们知道初始机场和最终机场是唯一的,所以这个值不应该是零。因为它不是零,所以该值至少有一个位集。该位对应于一个机场中设置的位,而不是另一个机场中设置的位;称之为指示符位。

接下来,设置两个bucket,每个bucket具有第一步中的xoled值。现在,对于每一张机票,根据是否设置了指示符位对每个机场进行桶式处理,并将机场代码与桶中的值进行异或处理。同时记录每一个航班的出发地机场和目的地机场的数量。

处理完所有的票后,选择其中一个桶。发送到该存储桶的源机场数应大于或小于发送到该存储桶的目标机场数。如果源机场的数量小于目的地机场的数量,则表示初始源机场(唯一唯一唯一的源机场)已发送到另一个bucket。这意味着当前bucket中的值是初始源机场的标识符!相反,如果目的地机场的数量小于源机场的数量,则最终目的地机场被发送到另一个bucket,因此当前bucket是最终目的地机场的标识符!

struct ticket
{
    int src;
    int dst;
};

int get_airport_bucket_index(
    int airport_code, 
    int discriminating_bit)
{
    return (airport_code & discriminating_bit)==discriminating_bit ? 1 : 0;
}

void find_trip_endpoints(const ticket *tickets, size_t ticket_count, int *out_src, int *out_dst)
{
    int xor_residual= 0;

    for (const ticket *current_ticket= tickets, *end_ticket= tickets + ticket_count; current_ticket!=end_ticket; ++current_ticket)
    {
        xor_residual^= current_ticket->src;
        xor_residual^= current_ticket->dst;
    }

    // now xor_residual will be equal to the starting airport xor ending airport
    // since starting airport!=ending airport, they have at least one bit that is not in common
    // 

    int discriminating_bit= xor_residual & (-xor_residual);

    assert(discriminating_bit!=0);

    int airport_codes[2]= { xor_residual, xor_residual };
    int src_count[2]= { 0, 0 };
    int dst_count[2]= { 0, 0 };

    for (const ticket *current_ticket= tickets, *end_ticket= tickets + ticket_count; current_ticket!=end_ticket; ++current_ticket)
    {
        int src_index= get_airport_bucket_index(current_ticket->src, discriminating_bit);

        airport_codes[src_index]^= current_ticket->src;
        src_count[src_index]+= 1;

        int dst_index= get_airport_bucket_index(current_ticket->dst, discriminating_bit);
        airport_codes[dst_index]^= current_ticket->dst;
        dst_count[dst_index]+= 1;
    }

    assert((airport_codes[0]^airport_codes[1])==xor_residual);
    assert(abs(src_count[0]-dst_count[0])==1); // all airports with the bit set/unset will be accounted for as well as either the source or destination
    assert(abs(src_count[1]-dst_count[1])==1);
    assert((src_count[0]-dst_count[0])==-(src_count[1]-dst_count[1]));

    int src_index= src_count[0]-dst_count[0]<0 ? 0 : 1; 
    // if src < dst, that means we put more dst into the source bucket than dst, which means the initial source went into the other bucket, which means it should be equal to this bucket!

    assert(get_airport_bucket_index(airport_codes[src_index], discriminating_bit)!=src_index);

    *out_src= airport_codes[src_index];
    *out_dst= airport_codes[!src_index];

    return;
}

int main()
{
    ticket test0[]= { { 1, 2 } };
    ticket test1[]= { { 1, 2 }, { 2, 3 } };
    ticket test2[]= { { 1, 2 }, { 2, 3 }, { 3, 4 } };
    ticket test3[]= { { 2, 3 }, { 3, 4 }, { 1, 2 } };
    ticket test4[]= { { 2, 1 }, { 3, 2 }, { 4, 3 } };
    ticket test5[]= { { 1, 3 }, { 3, 5 }, { 5, 2 } };

    int initial_src, final_dst;

    find_trip_endpoints(test0, sizeof(test0)/sizeof(*test0), &initial_src, &final_dst);
    assert(initial_src==1);
    assert(final_dst==2);

    find_trip_endpoints(test1, sizeof(test1)/sizeof(*test1), &initial_src, &final_dst);
    assert(initial_src==1);
    assert(final_dst==3);

    find_trip_endpoints(test2, sizeof(test2)/sizeof(*test2), &initial_src, &final_dst);
    assert(initial_src==1);
    assert(final_dst==4);

    find_trip_endpoints(test3, sizeof(test3)/sizeof(*test3), &initial_src, &final_dst);
    assert(initial_src==1);
    assert(final_dst==4);

    find_trip_endpoints(test4, sizeof(test4)/sizeof(*test4), &initial_src, &final_dst);
    assert(initial_src==4);
    assert(final_dst==1);

    find_trip_endpoints(test5, sizeof(test5)/sizeof(*test5), &initial_src, &final_dst);
    assert(initial_src==1);
    assert(final_dst==2);

    return 0;
}

创建两个数据结构:

Route
{
  start
  end
  list of flights where flight[n].dest = flight[n+1].src
}

List of Routes

然后:

foreach (flight in random set)
{
  added to route = false;
  foreach (route in list of routes)
  {
    if (flight.src = route.end)
    {
      if (!added_to_route)
      {
        add flight to end of route
        added to route = true
      }
      else
      {
        merge routes
        next flight
      }
    }
    if (flight.dest = route.start)
    {
      if (!added_to_route)
      {
        add flight to start of route
        added to route = true
      }
      else
      {
        merge routes
        next flight
      }
    }
  }
  if (!added to route)
  {
    create route
  }
}

放入两个散列: 结束=src->des; 发送至“des”->SRC

选择任何机场作为起点。

while(to_end[S] != null)
   S = to_end[S];

S现在是您的最终目的地。重复另一张地图,找到你的起点。

如果没有正确的检查,这感觉是O(N),前提是您有一个合适的哈希表实现。

散列表不适用于大尺寸(例如原始问题中的数十亿);任何与之合作的人都知道它们只适用于小的集合。相反,您可以使用二进制搜索树,这将给您带来复杂性O(n log n)。

最简单的方法是使用两个过程:首先将它们全部添加到树中,由SRC索引。第二个遍历树并将节点收集到一个数组中。

我们能做得更好吗?我们可以,如果我们真的想:我们可以一次完成。将每个票据表示为喜欢列表中的一个节点。最初,每个节点的 下一个 指针。对于每个票据,在索引中输入其SRC和DEST。如果发生冲突,这意味着我们已经拥有了相邻的票据;连接节点并从索引中删除匹配项。完成后,您将只通过一次,并且拥有一个空索引,以及一个按顺序排列的所有票的链接列表。

这个方法明显更快:它只通过一次,而不是两次;而且存储空间明显更小(最坏的情况是:n/2;最好的情况是:1;典型的情况是:sqrt(n)),因此您可以实际使用哈希而不是二进制搜索树。

每个机场都是 node . 每张票都是 edge . 制作一个邻接矩阵来表示图形。这可以作为压缩边缘的位字段来完成。您的起点将是没有路径进入它的节点(它的列将为空)。一旦你知道了这一点,你只需沿着现有的道路走。

或者你可以建立一个机场可索引的结构。每一张票你都会查到 src 和 dst . 如果找不到任何一个机场,则需要将新机场添加到列表中。当找到每一个时,您设置一个出发机场的出口指针指向目的地,而目的地的到达指针指向出发机场。当您没有票时,您必须遍历整个列表,以确定谁没有进入的路径。

另一种方法是,当您遇到每张票时,将一个可变长度的迷你旅行列表连接在一起。每次添加一张票时,您都会看到任何现有迷你旅行的结束是否与您的票的SRC或DEST匹配。如果没有,那么您当前的机票将成为自己的迷你旅行,并添加到列表中。如果是这样的话,那么新的票将被附加到它匹配的现有行程的末尾,可能将两个现有的小行程拼接在一起,在这种情况下,它将把小行程列表缩短一个。

这是单路径状态机矩阵的简单情况。 抱歉,伪代码是C样式的,但是用对象来表达这个想法比较容易。

首先,构造一个收费高速公路矩阵。 请阅读我对收费矩阵是什么的描述(不要在意FSM的答案,只需解释收费矩阵)。 What are some strategies for testing large state machines? .

但是,您所描述的限制使案例成为一个简单的单路径状态机。它是最简单的状态机,可以完全覆盖。

对于5个机场的简单情况,
垂直节点=SRC/入口点,
水平节点=DST/出口点。

   A1 A2 A3 A4 A5
A1        x
A2  x
A3           x
A4              x
A5     x

请注意,对于每一行以及每一列,不应该有多个转换。

要获得机器的路径,您需要将矩阵排序为

   A1 A2 A3 A4 A5
A2  x
A1        x
A3           x
A4              x
A5     x

或者排序成对角正方形矩阵——有序对的特征向量。

   A1 A2 A3 A4 A5
A2  x
A5     x
A1        x
A3           x
A4              x

其中,订购的是门票列表:

A2:A1、A5:A2、A1:A3、A3:A4、A4:A5。

或者用更正式的符号,

<a2,a1>, <a5,a2>, <a1,a3>, <a3,a4>, <a4,a5>.

六羟甲基三聚氰胺六甲醚。。订了一对吧?在Lisp中闻到递归的味道?

<a2,<a1,<a3,<a4,a5>>>>

机器有两种模式,

1. 旅行计划-你不知道怎么做 那里有很多机场,你呢 需要一个通用的旅行计划 机场数量不明
2. 旅行重建-你拥有所有 过去一次旅行的收费站票 但它们都是一堆 您的杂物箱/行李袋。

我猜你的问题是关于旅行重建。所以,你从那堆票中随机挑选一张又一张。

我们推测这票堆的大小是不确定的。

     tak mnx cda 
bom    0
daj       0
phi           0

其中0值表示未排序的票据。让我们将无序票据定义为其DST与另一票据的SRC不匹配的票据。

下一张罚单发现mnx(dst)=kul(src)匹配。

     tak mnx cda kul
bom    0
daj       1
phi           0
mnx               0

在您选择下一张机票的任何时候,它都有可能连接两个连续的机场。如果发生这种情况,您将从这两个节点中创建一个集群节点:

<bom,tak>, <daj,<mnx,kul>>

矩阵被约化,

     tak cda kul
bom    0
daj          L1
phi       0

在哪里?

L1 = <daj,<mnx,kul>>

这是主列表的子列表。

继续随机挑选下一张票。

     tak cda kul svn xml phi
bom    0
daj          L1
phi       0
olm               0
jdk                   0
klm                       0

将existent.dst与new.src匹配
或existent.src到new.dst:

     tak cda kul svn xml
bom    0
daj          L1
olm               0
jdk                   0
klm      L2


<bom,tak>, <daj,<mnx,kul>>, <<klm,phi>, cda>

以上拓扑练习仅用于视觉理解。下面是算法解。

这个概念是将有序对集群到子列表中,以减少我们用来存放票据的散列结构的负担。逐渐地,将会有越来越多的伪票(由合并的匹配票形成),每个伪票包含越来越多的有序目的地子列表。最后,将在其子列表中保留一个包含完整行程向量的伪票据。

正如你所看到的,也许这是最好的Lisp。

然而,作为链表和地图的练习…

创建以下结构:

class Ticket:MapEntry<src, Vector<dst> >{
  src, dst
  Vector<dst> dstVec; // sublist of mergers

  //constructor
  Ticket(src,dst){
    this.src=src;
    this.dst=dst;
    this.dstVec.append(dst);
  }
}

class TicketHash<x>{
  x -> TicketMapEntry;

  void add(Ticket t){
    super.put(t.x, t);
  }
}

所以实际上,

TicketHash<src>{
  src -> TicketMapEntry;

  void add(Ticket t){
    super.put(t.src, t);
  }
}

TicketHash<dst>{
  dst -> TicketMapEntry;

  void add(Ticket t){
    super.put(t.dst, t);
  }
}    

TicketHash<dst> mapbyDst = hash of map entries(dst->Ticket), key=dst
TicketHash<src> mapbySrc = hash of map entries(src->Ticket), key=src

当一张票从一堆中随机挑选出来时,

void pickTicket(Ticket t){
  // does t.dst exist in mapbyDst?
  // i.e. attempt to match src of next ticket to dst of an existent ticket.
  Ticket zt = dstExists(t);

  // check if the merged ticket also matches the other end.
  if(zt!=null)
    t = zt;

  // attempt to match dst of next ticket to src of an existent ticket.
  if (srcExists(t)!=null) return;

  // otherwise if unmatched either way, add the new ticket
  else {
    // Add t.dst to list of existing dst
    mapbyDst.add(t); 
    mapbySrc.add(t);
  }
}

检查是否存在DST:

Ticket dstExists(Ticket t){
  // find existing ticket whose dst matches t.src
  Ticket zt = mapbyDst.getEntry(t.src);

  if (zt==null) return false; //no match

  // an ordered pair is matched...

  //Merge new ticket into existent ticket
  //retain existent ticket and discard new ticket.
  Ticket xt = mapbySrc.getEntry(t.src);

  //append sublist of new ticket to sublist of existent ticket
  xt.srcVec.join(t.srcVec); // join the two linked lists.

  // remove the matched dst ticket from mapbyDst
  mapbyDst.remove(zt);
  // replace it with the merged ticket from mapbySrc
  mapbyDst.add(zt);

  return zt;
}

Ticket srcExists(Ticket t){
  // find existing ticket whose dst matches t.src
  Ticket zt = mapbySrc.getEntry(t.dst);

  if (zt==null) return false; //no match

  // an ordered pair is matched...

  //Merge new ticket into existent ticket
  //retain existent ticket and discard new ticket.
  Ticket xt = mapbyDst.getEntry(t.dst);

  //append sublist of new ticket to sublist of existent ticket
  xt.srcVec.join(t.srcVec); // join the two linked lists.

  // remove the matched dst ticket from mapbyDst
  mapbySrc.remove(zt);
  // replace it with the merged ticket from mapbySrc
  mapbySrc.add(zt);

  return zt;
}

检查是否存在源代码:

Ticket srcExists(Ticket t){
  // find existing ticket whose src matches t.dst
  Ticket zt = mapbySrc.getEntry(t.dst);

  if (zt == null) return null;

  // if an ordered pair is matched

  // remove the dst from mapbyDst
  mapbySrc.remove(zt);

  //Merge new ticket into existent ticket
  //reinsert existent ticket and discard new ticket.
  mapbySrc.getEntry(zt);

  //append sublist of new ticket to sublist of existent ticket
  zt.srcVec.append(t.srcVec);
  return zt;
}

我有一种感觉,上面有相当多的打字错误,但概念应该是正确的。如果有错别字,有人可以帮你改正。

最简单的方法是使用哈希表,但它没有最好的最坏情况的复杂性( O(n) ^二 ) )

而是:

1. 创建一组包含(SRC、DST)的节点 o(n)
2. 将节点添加到列表中并按SRC排序 O(n log n)
3. 对于每一个 (目的地) 节点,在列表中搜索相应的 (源) 结点 O(n log n)
4. 查找起始节点(例如,使用拓扑排序,或在步骤3中标记节点) o(n)

总体: O(n log n)

(对于这两种算法,我们假设字符串的长度可以忽略不计,即比较为O(1))。

不需要散列或类似的东西。 这里的实际输入大小不一定是门票数量(例如 n 但是总的尺寸(比如 n )票的总数 char 需要对它们进行编码。

如果我们有一个字母表 K 字符(此处 K 大约是42)我们可以使用bucketsort技术对 n 总大小的字符串 n 用字母编码的 K 字符在 o(n+n+k) 时间。如果 n=n (琐碎)和 k=n (井) n 是几十亿,不是吗)

1. 按照票的顺序,从票中提取所有机场代码,并将其存储在 struct 它将代码作为字符串,票据索引作为数字。
2. 对数组进行bucketsort排序 结构 S根据他们的代码
3. 运行经过排序的数组并分配一个序号(从 零 )每个新遇到的航空公司代码。对于具有相同代码(它们是连续的)的所有元素,请转到票据(我们已用代码存储了编号)并更改代码(选择右侧, src 或 dst )把票换成序数。
4. 在这个数组运行期间,我们可以识别原始源 src0 .
5. 现在所有的票都有了 SRC 和 DST 重写为序数,票据可以被解释为一个以 SRC0 .
6. 做一个列表排序(=toplogical sort,跟踪距离 SRC0 )在票上。

如果您假设一个可以存储所有内容(可能在磁盘上)的可接合列表结构:

1. 创建2个空哈希表s和d
2. 抓住第一个元素
3. 在D中查找其SRC
4. 如果找到,从D中删除关联的节点并将其链接到当前节点
5. 如果找不到,请将节点插入到SRC上的键控中
6. 从3开始,以另一种方式重复src<->des,s<->d
7. 对下一个节点从2重复。

O(n) 时间。至于空间, birthday paradox (或类似的东西)将使您的数据集比完整集小很多。在坏运气的情况下,它仍然变得很大(最坏的情况是 o(n) )可以从哈希表中逐出随机运行,并将它们插入到处理队列的末尾。你的速度可以达到极限,但只要你能远远超过预期碰撞的三倍。(~ O(sqrt(n)) )您应该期望看到数据集(表和输入队列的组合)定期收缩。

在我看来,基于图的方法是基于这里的。

每个机场都是一个节点,每张票都是一个边缘。现在让我们把每一条边都弄直。

在第一个阶段,您将构建图表:对于每个票据,您将查找源和目标,并在它们之间构建一条边。

现在这个图被构造出来了,我们知道它是非循环的,并且只有一条路径通过它。毕竟,你只有旅行的票,而且你从来没有去过同一个机场。

在第二阶段,您将搜索图形:选择任意节点,然后在两个方向上启动搜索,直到您发现无法继续。这些是您的来源和目的地。

如果您需要明确指出哪一个是源,哪一个是目的地,请向每个边缘添加一个目录属性(但保持它是一个无向图)。一旦您有了候选源和目标,您就可以根据连接到它们的边来判断哪个是哪个。

此算法的复杂性将取决于查找特定节点所需的时间。如果你能得到O(1),那么时间应该是线性的。你有n张票,所以你需要O(n)个步骤来构建图表,然后O(n)个步骤来搜索,O(n)个步骤来重建路径。仍然O(n)。一个邻接矩阵会给你这个。

如果你不能腾出空间,你可以为节点做一个散列,这会给你在最优散列下的O(1)和所有的垃圾。

注意,如果任务是 只有 为了确定源机场和目的地机场(而不是重建整个旅程),这个难题可能会变得更有趣。

也就是说,假设机场代码是以整数形式给出的,则可以使用O(1)个数据传递和O(1)个附加内存(即,不使用哈希表、排序、二进制搜索等)来确定源机场和目的机场。

当然,一旦找到了源,索引和遍历整个路径也就变成了一件无关紧要的事情,但从这一点来看,无论如何,至少需要O(n)个额外的内存(除非您可以对数据进行就地排序,这样,就可以用O(1)个额外的内存在O(n log n)时间内解决原始任务)。

让我们暂时忘记数据结构和图表。

首先,我需要指出的是,每个人都假设没有循环。如果这条路线经过一个机场的时间比经过一个机场的时间长两倍,那问题就大得多。

但我们暂时保留这个假设。

实际上,输入数据已经是一个有序集。每一张票都是关系的一个元素,它为一组机场引入了秩序。(英语不是我的母语,所以这些可能不是正确的数学术语)

每张票上都有这样的信息: airportX < airportY 因此,在一次通过机票时,算法可以从任何机场重新创建一个有序的列表。

现在让我们放弃“线性假设”。在这种情况下,不能定义订单关系。输入数据必须被视为正式语法的生产规则,其中语法的词汇集是一组ariport名称。 像这样的票:

src: A
dst: B

实际上是一对作品:

A->AB
B->AB

从中你只能保留一个。

现在,您必须生成每个可能的句子,但是您可以使用每个生成规则一次。最长的句子只使用一次它的每一个生产是一个正确的解决方案。

先决条件

首先,创建一种包含路线一部分的子标题结构。

例如,如果您的整个行程是 a-b-c-d-e-f-g ,子标题可以是 b-c-d ,也就是说,你旅行的一个连接的子路径。

现在,创建两个哈希表,将一个城市映射到包含该城市的子列表结构。因此,一个hashtable代表一个子字符串开始的城市,另一个代表一个子字符串结束的城市。这意味着,一个城市在一个哈希表中最多只能出现一次。

正如我们稍后将看到的,不是每个城市都需要存储,而是每个子条的开始和结束。

构造子脚本

现在,一张接一张地拿着票。我们假设票是从 x 到 y (以…为代表) (x,y) )检查一下 X 是一些潜规则的结束 s (因为每个城市只能访问一次,所以它不能是另一个子标题的结尾)。如果 X 是开始,只需添加当前票据 (x,y) 在子标题的末尾 S . 如果没有以 X ,检查是否有子标题 t 从开始 Y . 如果是,添加 (x,y) 在 T . 如果没有这样的潜台词 T ,只需创建包含 (x,y) .

处理子脚本应该使用一些特殊的“技巧”。

• 创建新的子标题 S 包含 (x,y) 应该加 X 到“子标题开始城市”的哈希表中,并添加 Y 到“子标题结束城市”的哈希表。
• 添加新票据 (x,y) 在子标题的开头 s=(y,...) 应该删除 Y 从开始城市的哈希表中添加 X 开始城市的哈希表。
• 添加新票据 (x,y) 在子标题的末尾 s=(...,x) 应该删除 X 从结束城市的哈希表中添加 Y 结束城市的哈希表。

有了这个结构,对应一个城市的子脚本可以在摊销O(1)中完成。

在所有的票都完成之后,我们有一些子脚本。注意我们最多有 (n-1)/2 = O(n) 这样的子脚本在程序之后。

连接子脚本

现在,我们一个接一个地考虑这些子脚本。如果我们有秘密消息 s=(x,...,y) ,我们只需查看结束城市的哈希表,如果有子列表 t=(...,x) 以结尾 X . 如果是,我们将 T 和 S 一个新的副标题。如果不是,我们知道 S 是我们的第一个子句;然后,我们看,如果还有另一个子句 u=(y,...) 从开始 Y . 如果是,我们将 S 和 u . 我们这样做,直到只剩下一个子裂口(这个子裂口就是我们最初的旅程)。

我希望我没有忽视Somtehing,但是这个算法应该运行在:

• 构造所有子脚本(最多 O(n) )可以在 o(n) ,如果我们实现向子条目的添加票据 O(1) . 如果我们有一些很好的指针结构或者类似的结构(将子脚本实现为链表),这应该没有问题。同时改变哈希表中的两个值是(摊销) O(1) . 因此,此阶段消耗 o(n) 时间。
• 连接子脚本直到只剩下一个子脚本,也可以在 o(n) . 也看到了这一点,我们只需要看看在第二阶段中做了什么:哈希表查找,需要进行分摊 O(1) 以及可以在 O(1) 有指针连接之类的。

因此,整个算法需要时间 o(n) 哪一个 可以 是最优的 O -因为至少每一张票 可以 需要看一下。

我编写了一个小型的python程序,使用两个哈希表,一个用于计数,另一个用于SRC到DST映射。 复杂性取决于字典的实现。如果字典有O(1),那么复杂度是O(n),如果字典有O(lg(n)),就像在stl映射中一样,那么复杂度是O(n lg(n))。

import random
# actual journey: a-> b -> c -> ... g -> h
journey = [('a','b'), ('b','c'), ('c','d'), ('d','e'), ('e','f'), ('f','g'), ('g','h')]
#shuffle the journey.
random.shuffle(journey)
print("shffled journey : ", journey )
# Hashmap to get the count of each place
map_count = {}
# Hashmap to find the route, contains src to dst mapping
map_route = {}

# fill the hashtable
for j in journey:
    source = j[0]; dest = j[1]
    map_route[source] = dest
    i = map_count.get(source, 0)
    map_count[ source ] = i+1
    i = map_count.get(dest, 0)
    map_count[ dest ] = i+1

start = ''
# find the start point: the map entry with count = 1 and 
# key exists in map_route.
for (key,val) in map_count.items():
    if map_count[key] == 1 and map_route.has_key(key):
        start = key
        break

print("journey started at : %s" % start)
route = [] # the route
n = len(journey)  # number of cities.
while n:
    route.append( (start, map_route[start]) )
    start = map_route[start]
    n -= 1

print(" Route : " , route )

我在此提供了一个更通用的问题解决方案:

你可以在同一个机场停几次,但每一张票只能用一次

您每次旅行的票可以多于一张。

每张机票包含SRC和DST机场。

你所有的票都是随机分类的。

你忘记了最初的出发机场(第一个SRC)和目的地(最后一个DST)。

我的方法返回包含所有指定城市的城市列表(向量),如果存在这样的链,则返回空列表。当有几种方法可以在城市中旅行时,该方法将返回词典中最小的列表。

#include<vector>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<set>
#include<map>

using namespace std;

struct StringPairHash
{
    size_t operator()(const pair<string, string> &p) const {
        return hash<string>()(p.first) ^ hash<string>()(p.second);
    }
};

void calcItineraryRec(const multimap<string, string> &cities, string start,
    vector<string> &itinerary, vector<string> &res,
    unordered_set<pair<string, string>, StringPairHash> &visited, bool &found)
{
    if (visited.size() == cities.size()) {
        found = true;
        res = itinerary;
        return;
    }
    if (!found) {
        auto pos = cities.equal_range(start);
        for (auto p = pos.first; p != pos.second; ++p) {
            if (visited.find({ *p }) == visited.end()) {
                visited.insert({ *p });
                itinerary.push_back(p->second);
                calcItineraryRec(cities, p->second, itinerary, res, visited, found);
                itinerary.pop_back();
                visited.erase({ *p });
            }
        }
    }
}

vector<string> calcItinerary(vector<pair<string, string>> &citiesPairs)
{
    if (citiesPairs.size() < 1)
        return {};

    multimap<string, string> cities;
    set<string> uniqueCities;
    for (auto entry : citiesPairs) {
        cities.insert({ entry });
        uniqueCities.insert(entry.first);
        uniqueCities.insert(entry.second);
    }

    for (const auto &startCity : uniqueCities) {
        vector<string> itinerary;
        itinerary.push_back(startCity);
        unordered_set<pair<string, string>, StringPairHash> visited;
        bool found = false;
        vector<string> res;
        calcItineraryRec(cities, startCity, itinerary, res, visited, found);
        if (res.size() - 1 == cities.size())
            return res;
    }
    return {};
}

以下是用法示例:

    int main()
    {
        vector<pair<string, string>> cities = { {"Y", "Z"}, {"W", "X"}, {"X", "Y"}, {"Y", "W"}, {"W", "Y"}};
        vector<string> itinerary = calcItinerary(cities); // { "W", "X", "Y", "W", "Y", "Z" }
        // another route is possible {W Y W X Y Z}, but the route above is lexicographically smaller.

        cities = { {"Y", "Z"}, {"W", "X"}, {"X", "Y"}, {"W", "Y"} };
        itinerary = calcItinerary(cities);  // empty, no way to travel all cities using each ticket exactly one time
    }