Проблема с односторонним полетом

Ответ 1

Постройте хэш-таблицу и добавьте каждый аэропорт в хэш-таблицу.

<key,value> = <airport, count>

Граф для аэропорта увеличивается, если аэропорт является либо источником, либо пунктом назначения. Таким образом, для каждого аэропорта счет будет равен 2 (1 для src и 1 для dst), за исключением источника и места назначения вашей поездки, у которого будет счет 1.

Вам нужно посмотреть каждый билет хотя бы один раз. Таким образом, сложность O (n).

Ответ 2

Резюме: ниже предоставляется однопроходный алгоритм. (I.e., а не только линейно, но каждый билет выглядит ровно один раз, что, конечно же, является оптимальным количеством посещений за билет). Я поставил резюме, потому что есть много, казалось бы, эквивалентных решений, и было бы трудно определить, почему я добавил еще один.:)

Я был задан этот вопрос в интервью. Концепция чрезвычайно проста: каждый билет представляет собой одноэлементный список, с концептуально двумя элементами, src и dst.

Мы индексируем каждый такой список в хэш-таблице, используя его первый и последний элементы в качестве ключей, поэтому мы можем найти в O (1), если список начинается или заканчивается в определенном элементе (аэропорту). Для каждого билета, когда мы видим, что он начинается там, где заканчивается другой список, просто связывайте списки (O (1)). Точно так же, если он заканчивается, когда начинается другой список, присоединяется другой список. Конечно, когда мы связываем два списка, мы в основном уничтожаем их и получаем один. (Цепочка N билетов будет построена после N-1 таких ссылок).

Необходимо поддерживать инвариант, чтобы ключи хеш-таблицы были точно первым и последним элементами остальных списков.

В целом, O (N).

И да, я ответил, что на месте:)

Изменить Забыл добавить важный момент. Каждый упоминает два хеш-таблицы, но один делает трюк, потому что инвариант алгоритмов включает в себя, что не более \strong > один список билетов начинается или начинается в любом одном городе (если их два, мы сразу присоединяемся к спискам в этот город, и удалите этот город из хэш-таблицы). Асимптотически нет разницы, это просто проще.

Редактировать 2 Интересно также, что по сравнению с решениями, использующими 2 хэш-таблицы с N элементами каждый, это решение использует одну хэш-таблицу с не более N/2 записей (что если мы увидим билеты в порядке, скажем, 1, 3, 5 и т.д.). Таким образом, это использует примерно половину памяти, кроме того, что быстрее.

Ответ 3

Построить две таблицы хэшей (или пытается), один из которых - src, а другой - dst. Выберите один случайный случай и посмотрите его dst в таблице src-hash. Повторите этот процесс для результата, пока вы не достигнете цели (конечный пункт назначения). Теперь найдите его src в таблице хэш-таблицы с dst-keyed. Повторите процесс для результата, пока не нажмете начало.

Построение хэш-таблиц принимает O (n), а построение списка принимает O (n), поэтому весь алгоритм O (n).

EDIT: на самом деле вам нужно построить только одну хеш-таблицу. Скажем, вы строите хэш-таблицу с ключом src. Выберите один билет в случайном порядке и, как и раньше, создайте список, который приведет к окончательному месту назначения. Затем выберите другой случайный билет из билетов, которые еще не добавлены в список. Следуйте по месту назначения, пока не нажмете на билет, с которого вы начали сначала. Повторите этот процесс, пока вы не построите весь список. Он все еще O (n), поскольку в худшем случае вы выбираете билеты в обратном порядке.

Изменить: получили имена таблиц, замененных в моем алгоритме.

Ответ 4

В основном это график зависимости, в котором каждый билет представляет собой node и src и dst аэропорт представляет собой направленные ссылки, поэтому используйте топологическую сортировку, чтобы определить порядок полета.

EDIT: Хотя, так как это билет авиакомпании, и вы знаете, что на самом деле вы сделали маршрут, который вы могли физически выполнять, сортируйте по дате и времени вылета в UTC.

EDIT2: Предполагая, что в каждом аэропорту у вас есть билет, который использует трехсимвольный код, вы можете использовать описанный здесь алгоритм (Найти три номера, появляющиеся только один раз), чтобы определить два уникальных аэропорта, объединив все аэропорты.

EDIT3: Здесь некоторые С++ для решения этой проблемы с помощью метода xor. Общий алгоритм заключается в следующем: при условии, что уникальная кодировка из аэропорта в целое число (либо при наличии трехбуквенного кода аэропорта, либо для кодирования местоположения аэропорта в целочисленном размере с использованием широты и долготы):

Во-первых, XOR все коды аэропорта вместе. Это должно быть равно первоначальному исходному аэропорту XOR в конечном аэропорту назначения. Поскольку мы знаем, что первоначальный аэропорт и последний аэропорт уникальны, это значение не должно быть равным нулю. Поскольку он не равен нулю, в этом значении будет установлен хотя бы один бит. Этот бит соответствует бит, который установлен в одном из аэропортов и не установлен в другом; назовите это бит обозначения.

Затем установите два ведра, каждый из которых имеет значение XORed с первого шага. Теперь, для каждого билета, ведите каждый аэропорт в зависимости от того, установлен он бит-указатель или нет, и код аэропорта со значением в ковше. Также следить за каждым ведром, сколько источников аэропортов и аэропортов назначения отправились в это ведро.

После обработки всех билетов выберите один из ковшей. Количество аэропортов-источников, отправленных в это ведро, должно быть на одно большее или меньшее количество аэропортов назначения, отправленных в это ведро. Если количество аэропортов-источников меньше, чем количество аэропортов назначения, это означает, что первоначальный аэропорт-источник (единственный уникальный аэропорт-источник) был отправлен в другое ведро. Это означает, что значение в текущем ковше является идентификатором для исходного источника аэропорта! И наоборот, если количество аэропортов назначения меньше, чем количество аэропортов-источников, конечный аэропорт назначения был отправлен в другое ведро, поэтому текущий ковш является идентификатором для конечного аэропорта назначения.

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;
}

Ответ 5

Создайте две структуры данных:

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
  }
}

Ответ 6

Поместите в два хэша:   to_end = src → des;   to_beg = des → src

Выберите любой аэропорт в качестве отправной точки S.

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

S теперь ваш конечный пункт назначения. Повторите с другой картой, чтобы найти отправную точку.

Без правильной проверки это чувствует O (N), если у вас есть достойная реализация таблицы Hash.

Ответ 7

Хэш-таблица не будет работать для больших размеров (например, миллиарды в исходном вопросе); любой, кто работал с ними, знает, что они хороши только для небольших наборов. Вместо этого вы можете использовать двоичное дерево поиска, которое даст вам сложность O (n log n).

Самый простой способ - с двумя проходами: Первый добавляет их все в дерево, индексированное src. Второй идет по дереву и собирает узлы в массив.

Мы можем сделать лучше? Мы можем, если мы действительно хотим: мы можем сделать это за один проход. Представляйте каждый билет как node в любимом списке. Первоначально каждый node имеет нулевые значения для следующего указателя. Для каждого билета введите оба индекса src и dest в индекс. Если есть столкновение, это означает, что у нас уже есть соседний билет; подключить узлы и удалить совпадение из индекса. Когда вы закончите, вы сделаете только один проход и получите пустой индекс и связанный список всех билетов в порядке.

Этот метод значительно быстрее: это только один проход, а не два; и магазин значительно меньше (наихудший случай: n/2, лучший случай: 1, типичный случай: sqrt (n)), достаточно, чтобы вы могли фактически использовать хеш вместо двоичного дерева поиска.

Ответ 8

Каждый аэропорт - node. Каждый билет - edge. Создайте матрицу смежности для представления графика. Это можно сделать в виде битового поля для сжатия ребер. Отправной точкой будет node, в котором нет пути (столбец будет пустым). Как только вы это знаете, вы просто следуете путям, которые существуют.

В качестве альтернативы вы можете построить структуру, индексируемую аэропортом. Для каждого билета вы просматриваете его src и dst. Если ни один из них не найден, вам необходимо добавить новые аэропорты в свой список. Когда каждый найден, вы устанавливаете указатель выхода из аэропорта отправления, чтобы указать на пункт назначения, а указатель прибытия пункта указывать на аэропорт вылета. Когда у вас нет билетов, вы должны пройти весь список, чтобы определить, у кого нет пути.

Другим способом было бы иметь список мини-поездок с переменной длиной, с которым вы соединяетесь вместе, когда вы сталкиваетесь с каждым билетом. Каждый раз, когда вы добавляете билет, вы видите, соответствуют ли концы любой существующей мини-поездки либо src, либо dest вашего билета. Если нет, то ваш текущий билет становится его мини-поездкой и добавляется в список. Если это так, то новый билет привязан к концу (-ам) существующего маршрута (-ов), который он соответствует, возможно, сращивая две существующие мини-поездки вместе, и в этом случае он сократит список мини-поездок на один.

Ответ 9

Это простой случай матрицы состояния конечного состояния. Извините, что псевдокод был в стиле С#, но было легче выразить идею с помощью объектов.

Сначала построим матрицу магистралей. Прочитайте мое описание того, что такое матрица магистралей (не беспокойтесь по поводу ответа FSM, просто объяснение матрицы магистралей) в Какие существуют стратегии тестирования больших государственных машин?.

Однако описанные вами ограничения делают случайным простым конечным автоматом. Это самый простой государственный автомат с полным покрытием.

Для простого случая из 5 аэропортов,
vert nodes = src/точки входа,
узлы horiz = 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>>>>

Существует два режима работы машины:

• планирование поездки - вы не знаете, как многие аэропорты есть, и вы нужен общий план поездки для неопределенное количество аэропортов
• восстановление поездки - у вас есть все билеты на тупик прошлой поездки но они все один большой стек в ваш бардачок/багажный мешок.

Я предполагаю, что ваш вопрос о восстановлении поездки. Таким образом, вы выбираете один билет за другим случайно из этой кучи билетов.

Мы предполагаем, что куча билетов имеет неопределенный размер.

     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

В любой момент вы выбираете следующий билет, есть вероятность, что он соединяет два последовательных аэропорта. Если это произойдет, вы создадите кластер node из этих двух узлов:

<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;
}

Проверить наличие существующего src:

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;
}

У меня такое чувство, что у вышеупомянутого есть довольно опечатки, но концепция должна быть правильной. Любая опечатка найдена, кто-то может ее исправить, plsss.

Ответ 10

Самый простой способ - с хэш-таблицами, но у него нет наилучшей наихудшей сложности (O (n ²))

Вместо

• Создайте кучу узлов, содержащих (src, dst) O (n)
• Добавить узлы в список и отсортировать по src O (n log n)
• Для каждого (адресата) node найдите список для соответствующего (источника) node O (n log n)
• Найдите начало node (например, используя топологическую сортировку или маркирующие узлы на шаге 3) O (n)

В целом: O (n log n)

(Для обоих алгоритмов мы предполагаем, что длина строк пренебрежимо мала, то есть сравнение O (1))

Ответ 11

Нет необходимости в хэшах или чем-то подобном. Реальный размер ввода здесь не обязательно означает количество билетов (скажем n), но общий "размер" (скажем, N) билетов, общее количество char, необходимое для их кодирования.

Если у нас есть алфавит из k символов (здесь k примерно 42), мы можем использовать методы bucketsort для сортировки массива из n строк общего размера N, которые кодируются алфавитом из k символов в O (n + N + k) времени. Следующее работает, если n <= N (тривиальное) и k <= N (лунка N - это миллиарды, не так ли)

• В порядке, в котором указаны билеты, извлеките все коды аэропорта из билетов и сохраните их в struct, который имеет код в виде строки и индекс билета в виде номера.
• Bucketsort этот массив struct в соответствии с их кодом
• Запустите пронумерованный сортированный массив и назначьте порядковый номер (начиная с 0) с каждым новым кодом авиакомпании. Для всех элементов с одним и тем же кодом (они последовательны) перейдите в билет (мы сохранили номер с кодом) и изменим код (выберите справа, src или dst) билета на порядковый номер.
• Во время этого пробега через массив мы можем идентифицировать исходный источник src0.
• Теперь все билеты имеют src и dst, переписанные как порядковые номера, и билеты могут быть интерпретированы как один список, начинающийся с src0.
• Сделайте список в списке (= toplogical sort с отслеживанием расстояния от src0) на билетах.

Ответ 12

Если вы предполагаете структуру списка соединений, которая может хранить все (возможно, на диске):

• Создайте две пустые хеш-таблицы S и D
• захватить первый элемент
• найдите src в D
• Если найдено, удалите связанный с ним node из D и привяжите его к текущему node
• Если не найден, вставьте node в S keyed on src
• повторить с 3 другим способом src ↔ des, S ↔ D
• повторите с 2 со следующим node.

O(n) время. Что касается пространства, парадокс дня рождения (или что-то в этом роде), ваш набор данных будет намного меньше, чем полный набор. В случае неудачи, когда он все еще доходит до большого (наихудший вариант O(n)), вы можете выселить случайные прогоны из хеш-таблицы и вставить их в конец очереди обработки. Ваша скорость может идти в банк, но до тех пор, пока вы можете далеко зайти в трэшольд для ожидающих столкновений (~ O(sqrt(n))), вы должны ожидать, что ваш набор данных (таблицы и входная очередь в сочетании) будет регулярно сокращаться.

Ответ 13

Мне кажется, что подход основан на графике.

Каждый аэропорт - node, каждый билет - это край. Пусть теперь все грани ненаправлены.

На первом этапе вы строите график: для каждого билета вы просматриваете источник и пункт назначения и создаете границу между ними.

Теперь, когда граф построен, мы знаем, что он ацикличен и что через него проходит один путь. В конце концов, у вас есть только билеты на поездки, которые вы взяли, и вы никогда не посещали один и тот же аэропорт.

На втором этапе вы просматриваете график: выберите любой node и инициируйте поиск в обоих направлениях, пока не найдете, что вы не можете продолжить. Это ваш источник и пункт назначения.

Если вам нужно конкретно указать, какой источник и какой пункт назначения, добавьте свойство каталога к каждому ребру (но держите его неориентированным графом). После того, как у вас есть источник-источник и пункт назначения, вы можете указать, какая из них основана на связанном с ним ребре.

Сложность этого алгоритма будет зависеть от времени, которое требуется для поиска конкретного node. Если вы можете достичь O (1), тогда время должно быть линейным. У вас есть n билетов, поэтому вам нужно выполнить O (N) шагов для построения графика, а затем O (N) для поиска и O (N) для восстановления пути. Еще O (N). Матрица смежности даст вам это.

Если вы не можете сэкономить место, вы можете сделать хэш для узлов, что даст вам O (1) при оптимальном хэшировании и все это дерьмо.

Ответ 14

Обратите внимание, что если задача была only, чтобы определить аэропорты источника и назначения (вместо восстановления всей поездки), головоломка, вероятно, станет более интересной.

А именно, предполагая, что коды аэропортов указаны как целые числа, аэропорты источника и получателя могут быть определены с использованием O (1) проходов данных и дополнительной памяти O (1) (т.е. без использования хеш-таблиц, сортировки, двоичного поиска, и т.п.).

Конечно, как только вы найдете источник, также становится тривиальным вопросом для индексации и прохождения полного маршрута, но с этой точки в целом это потребует как минимум O (n) дополнительной памяти (если вы не можете сортировать данные, которые, кстати, позволяют решить исходную задачу в O (n log n) времени с O (1) дополнительной памятью)

Ответ 15

Забудьте о структурах данных и графиках на мгновение.

Сначала я должен указать, что все сделали предположение, что нет петель. Если маршрут проходит через один аэропорт в два раза больше, чем проблема, более значительная проблема.

Но пока сохраняем это предположение.

Входные данные уже являются упорядоченным набором. Каждый билет является элементом отношения, которое вводит порядок в несколько аэропортов. (Английский язык не мой родной язык, поэтому это могут быть не правильные математические термины)

Каждый билет содержит следующую информацию: airportX < airportY, поэтому, выполняя один проход через билеты, алгоритм может воссоздать упорядоченный список, начиная с любого аэропорта.

Теперь отбросьте "линейное предположение". Никакое отношение заказа не может быть определено из такого рода вещей. Входные данные должны рассматриваться как правила производства для формальной грамматики, где набор грамматической лексики представляет собой набор имен арипонов. Билет такой:

src: A
dst: B

- фактически пара производств:

A->AB
B->AB

из которого вы можете сохранить только один.

Теперь вам нужно создать все возможные предложения, но вы можете использовать каждое производственное правило один раз. Самое длинное предложение, которое использует каждое его производство только один раз, является правильным решением.

Ответ 16

Необходимые условия

Прежде всего, создайте какую-то структуру подтриппа, которая содержит часть вашего маршрута.

Например, если ваше полное отключение a-b-c-d-e-f-g, субтрип может быть b-c-d, т.е. связанным подпунктом вашей поездки.

Теперь создайте два хеш-таблицы, которые отображают город в структуру субтрипа, в которой находится город. Таким образом, один Hashtable обозначает город, откуда начинается субтрип, а другой - города, в которых заканчивается субтрип. Это означает, что один город может встречаться не один раз в одном из хеш-таблиц.

Как мы увидим позже, не каждый город должен быть сохранен, а только начало и конец каждого субтрипа.

Построение подпунктов

Теперь, возьмите билеты только один за другим. Мы предполагаем, что билет должен идти от x до y (представлен (x,y)). Check, wheter x - это конец какой-либо субтрип s (так как каждый город посещается только один раз, это уже не может быть конец другого субтрипа). Если x является началом, просто добавьте текущий билет (x,y) в конец субтрипа s. Если нет субтрипа, заканчивающегося на x, проверьте, есть ли субтрип t, начинающийся с y. Если да, добавьте (x,y) в начало t. Если такой субтрип t также не существует, просто создайте новый подтип, содержащий только (x,y).

Работа с субтрипами должна выполняться с использованием специальных "трюков".

• Создание нового subtrip s, содержащего (x,y), должно добавить x в хеш-таблицу для "городов-подпунктов" и добавить y в хеш-таблицу для "городов, заканчивающих завершение".
• Добавление нового билета (x,y) в начале субтрипа s=(y,...), следует удалить y из хеш-таблицы начальных городов и вместо этого добавить x в хэш-таблицу начальных городов.
• Добавление нового билета (x,y) в конец субтрипа s=(...,x), следует удалить x из хэш-таблицы конечных городов и вместо этого добавить y в хэш-таблицу конечных городов.

С этой структурой подтрипты, соответствующие городу, могут быть выполнены с амортизацией O (1).

После этого для всех билетов у нас есть несколько субтитров. Обратите внимание на то, что после этой процедуры мы имеем не более (n-1)/2 = O(n) такие подпункты.

Конкатенация субтрипсов

Теперь мы просто рассматриваем субтрипы один за другим. Если у нас есть subtrip s=(x,...,y), мы просто посмотрим в нашу хэш-таблицу конечных городов, если есть субтрип t=(...,x), заканчивающийся на x. Если это так, мы присоединяем t и s к новой подтриппе. Если нет, мы знаем, что s является нашей первой подтрипкой; то мы смотрим, если есть еще одна субтрип u=(y,...), начинающаяся с y. Если это так, мы объединяем s и u. Мы делаем это до тех пор, пока не останется только одна субтрип (эта подсечка - это все наше первоначальное путешествие).

Надеюсь, я не пропустил somtehing, но этот алгоритм должен работать в:

• построение всех подтриппов (не более O(n)) может быть выполнено в O(n), если мы реализуем добавление билетов в подтип в O(1). Это не должно быть проблемой, если у нас есть хорошая структура указателя или что-то в этом роде (реализация subtrips в качестве связанных списков). Также изменение двух значений в хеш-таблице (амортизируется) O(1). Таким образом, эта фаза потребляет O(n) время.
• объединение конвейеров до тех пор, пока не останется только один, также можно сделать в O(n). Слишком это видно, нам просто нужно посмотреть, что делается на втором этапе: поиск Hashtable, который требует амортизации O(1) и конкатенации субтрип, которые могут быть выполнены в O(1) с конкатенацией указателя или чем-то.

Таким образом, весь алгоритм занимает время O(n), что может быть оптимальным O -bound, так как, по крайней мере, каждый билет, возможно, потребуется посмотреть.

Ответ 17

Я написал небольшую программу python, использует две таблицы хэша для подсчета и другую для сопоставления src to 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 )

Ответ 18

Я приведу здесь более общее решение проблемы:

Вы можете остановиться несколько раз в одном и том же аэропорту, но каждый билет нужно использовать ровно 1 раз

Вы можете иметь более 1 билета на каждую часть поездки.

Каждый билет содержит аэропорт и аэропорт.

Все ваши билеты отсортированы случайным образом.

Вы забыли исходный аэропорт отправления (самый первый рейс) и пункт назначения (последний день).

Мой метод возвращает список городов (вектор), которые содержат все указанные города, если такая цепочка существует, и пустой список в противном случае. Когда есть несколько способов путешествовать по городам, метод возвращает лексикографически наименьший список.

#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
    }