100 детей берутся за руки в круг, начинают считать с первого ребенка, считают до 3 и выходят из очереди.Следующий ребенок продолжает считать с 1 и повторяет счет, чтобы найти позицию последнего ребенка, оставшегося в очереди.
Это очень классический алгоритмический вопрос, и я часто обращаюсь к нему во время интервью. Этот вопрос вполне разрешим при позитивном мышлении, но, к сожалению, почти никто из опрошенных не может правильно ответить на этот вопрос.
Итак, как ответить на этот вопрос, давайте попробуем вместе!
Решение 1. Отнеситесь к жизни и смерти легкомысленно, сделайте это, если не согласны
Во-первых, мы пытаемся решить это с позитивным мышлением.Мы моделируем 100 человек с набором, и значение в наборе записывает индекс человека в исходной очереди (начиная с 0). Чтобы обеспечить универсальность функции, мы используем n для представления количества людей в очереди и m для представления позиции исключения из очереди:
В этой статье мы используем язык Java для объяснения.Если вы хотите увидеть реализацию на других языках, оставьте сообщение в публичном аккаунте WeChat «Ouyang Feng Studio».
public static int f(int n, int m) {
// 这里用一个集合模拟队列
List<Integer> list = new ArrayList<>();
for (int i = 0; i < n; i ++) {
list.add(i);
}
// 计数器，记录报数序号
int count = 0;
// 当前循环的队列位置索引
int index = 0;
while (list.size() > 1) {
count ++;
// 这里还要注意一个问题，如果报数来到了队列尾部，我们需要从第一个人继续往下报数
// 因此这里的索引计数器需要归0
if (index >= list.size()) {
index = 0;
}
// 接下来开始循环报数，将序号为m的人移出队列
if (count >= m) {
// 移出队列，同时计数器归0
list.remove(index);
count = 0;
}
index ++;
}
return list.get(0);
}
Приведенное выше решение проще всего придумать, вопрос в том, правильно ли это сделать?
Очевидно неправильно! Здесь упускается из виду одна проблема: как только кто-то в очереди удаляется из очереди, индекс очереди изменится. Например, предположим, что третий человек удален, обычно индекс следующего человека должен быть 4. На самом деле индекс человека по-прежнему равен 3, потому что подсчет индекса непрерывен. Индекс удаленного человека также исчезнет, а индекс всех позади сдвинется вперед на одну позицию.
Это наиболее вероятная проблема с вышеприведенным решением. Зная первопричину проблемы, мы продолжим улучшать код.
Мы добавляем строку кода после строки 28 приведенного выше кода.После удаления символа из очереди значение индекса уменьшается на единицу:
// 接下来开始循环报数，将序号为m的人移出队列
if (count >= m) {
// 移出队列，同时计数器归0
list.remove(index);
count = 0;
// 这里的索引要减1
index --;
}
После модификации пробуем запустить приведенный выше код, передать в функцию значения 100 и 3 и получить результат 90. Ответ правильный.
Решение 2. Не бойтесь жизни и смерти, продолжайте двигаться вперед
В дополнение к вышеупомянутым решениям, есть также общее решение метода решения задачи, данное напрямую, то есть, независимо от три-семь-два-один, зациклиться до тех пор, пока не будет выведен результат.
Это решение также требует построения пользовательской очереди, но форма очереди изменилась.Мы используем булев массив длины n для построения пользовательской очереди.
Полный код этого решения выглядит следующим образом:
public static int f(int n, int m) {
Boolean[] arr = new Boolean[n];
for (int i = 0; i < arr.length; i ++) {
arr[i] = true;
}
// 队列中还剩余的人数
int leftCount = arr.length;
// 计数器，记录报数序号
int count = 0;
// 当前循环的队列位置索引
int index = 0;
while (leftCount > 1) {
if (arr[index]) {
count++;
}
if (count == m) {
arr[index] = false;
count = 0;
leftCount --;
}
index ++;
// 这里同样需要处理计数到达队列尾部的情况
if (index >= n) {
index = 0;
}
}
int result = 0;
for (int i = 0; i < arr.length; i ++) {
if (arr[i]) {
result = i;
break;
}
}
return result;
}
По сравнению с первым решением, это решение имеет более высокую временную сложность и больше циклов, а количество циклов почти в 3-5 раз больше, чем в первом решении, а то и больше. Но по сравнению с первым решением это решение легче принять, и в нем не нужно учитывать изменение индекса. На собеседовании, если вы не можете придумать никакого решения, я рекомендую вам использовать это решение.
Решение 3. Умело используйте связанный список, чтобы восстановить сцену
Анализируя вопросы теста, нетрудно обнаружить, что это структура связанного списка, с которой мы хорошо знакомы. В третьем решении мы пытаемся смоделировать эту пользовательскую очередь, используя связанный список, и посмотрим, сможем ли мы получить какие-то сюрпризы.
Поскольку всегда используется односторонняя отчетность, мы используем односторонний связанный список для имитации этой структуры данных:
// 这里用Child类来模拟每一个参与的小孩，其中的value值保存的是当前用户的索引
public class Child {
// 简单起见，这里我们全部使用public
public Child next;
public int value;
public Child(int value) {
this.value = value;
}
}
public static int f(int n, int m) {
Child head = new Child(0);
Child current = head;
for (int i = 1; i < n; i ++) {
Child child = new Child(i);
current.next = child;
current = child;
}
// 为了构建首尾相接的链表，这里我们主动将尾节点与头结点连接起来
// 当前节点恰好指向尾节点
current.next = head;
// 接下来再移动一次指针，让current指向头节点
// 为了方便获取前一个节点，这里我们用一个变量表示前一个节点
Child prev = current;
current = current.next;
// 定义计数器
int count = 0;
// 一旦收尾相接，当前节点指向了自身，证明队列中只有一个用户了，跳出循环，游戏结束
while (current.next != current) {
count ++;
if (count == m) {
prev.next = current.next;
count = 0;
}
prev = current;
current = current.next;
}
return current.value;
}
Выше приведен полный код этого решения, который содержит подробное объяснение каждой строки кода. В этом решении мы используем связанный список для имитации очереди символов и имитируем подсчет, управляя перемещением указателя текущего пользователя. Наконец, когда указатель следующего пользователя пользователя указывает на себя, цикл прерывается, игра заканчивается, и текущий пользователь становится последним пользователем, оставшимся в очереди.
Это решение проще для понимания, чем два приведенных выше решения, и временная сложность этого решения невелика, а количество циклов такое же, как и у первого решения. На данный момент он является лучшим из всех решений.
Итак, есть ли лучшее решение?
Решение 4: Математический Дафа, девяносто девять возвращаются к одному
Информатика неотделима от математики! Наконец, давайте попробуем, попробуем использовать оружие математики, чтобы решить эту задачу более тонко. Поскольку это обычное действие, мы можем быть уверены, что для этого должен существовать фиксированный математический закон.
Но теперь вопрос в том, как найти этот закон? Это не кажется легким.
Здесь мы сначала предполагаем, что общее количествоn, заявленное числоmлюдей исключают из очереди, используютf(n, m)Указывает позицию человека, оказавшегося в очереди.
Для того, чтобы всем было легче понять, давайте сначала рассмотрим практический пример, предположив n=5, m=3, то есть в очереди всего 5 человек, а люди, сообщившие число 3, исключен из очереди.
第一轮报数，位置为3的人出列
[1, 2, x, 4, 5]
出列后，从4开始报数，我们将开始报数的人挪到第一位，剩下的人按照报数的顺序往后排，得到一个新的队列：
[4, 5, 1, 2]
从这里，我们开始第二轮报数，这一轮报数位置为1的人出列
[4, 5, x, 2]
我们继续按照上面的方式，转换队列，重新第三轮报数：
[2, 4, 5] => [2, 4, x]
第四轮：
[2, 4] => [x, 4]
第五轮：
[4]
Вышеупомянутоеn = 5, m = 3В случае полного отчета мы обращаем внимание только на изменения в первом отчете.
После завершения первого раунда подсчета очередь преобразуется из [1, 2, 3, 4, 5] в [4, 5, 2, 1].
- Очередь 1: [1, 2, 3, 4, 5]
- Очередь 2: [4, 5, 1, 2]
Обратите внимание: если мы не обращаем внимания на положение символов в очереди, мы фокусируемся только на самой очереди. Как связаны эти две очереди?
- Обе очереди начинают отсчет с 1
- Разница между двумя когортами всего 1
Здесь очень тонко, что на самом деле можно рассматривать как очередь символов с номером 5 и очередь символов с номером 4. если мы используемQЕсли он представляет собой очередь, можно использовать первую очередьQ(5)означает, что вторая очередь может использоваться сQ(4)Представлять,Q(4)в реальностиQ(5)подочередь.
В этих двух очередях также есть два элемента помех [1, 2], для устранения помех меняем их на [6, 7], а именно:
- Очередь 1: [1, 2, 3, 4, 5]
- Очередь 2: [4, 5, 6, 7]
на этот раз очередьQ(5)а такжеQ(4)Есть некая взаимосвязь, и значения индекса в одной и той же позиции ровно 3 разные (на самом деле это значение m, почему m? Вы сами можете подумать).
Далее мы обращаем внимание на первый раунд отчетов во второй очереди, и человек, сообщивший число 3, выбывает из очереди, что составляет 6 во второй очереди. Итак, какова именно позиция ТА в исходной очереди? Ответ 1, что на самом деле6 % 5Значение, полученное путем взятия модуля.
Кажется, здесь существует фиксированное правило, а именно: если предположить, что позиция лица, исключенного из очереди в первом раунде отчетности в очереди 2, равна x2 в очереди 2, а позиция в очереди 1 равна x1, должно быть следующее соотношение между x2 и x1:
x1 = (x2 + 3) % 5
Уравнение первого раунда подсчета установлено, затем установлен ли второй раунд подсчета? Установлено ли оно до последнего оставшегося человека? Ответ: конечно.
Отсюда мы можем предположитьf(n, m)а такжеf(n, m - 1)Существуют следующие отношения:
f(n, m) = (f(n - 1, m) + m) % n
Чтобы углубить ваше понимание, мы снова покажем вам процесс конвертации с картинками:
Вышеупомянутый процесс перевода других людей n-1 в подочередь n-1 после того, как пользователь, чье количество отчетов равно m в первый раз, исключен из очереди с длиной очереди n.
Отсюда можно сделать вывод, что преобразование здесь универсально и приведенная выше формула применима ко всем случаям.
В приведенной выше формуле мы не рассматривали ситуацию, когда в текущей очереди находится только один человек, здесь мы дополняем ее, чтобы получить следующую рекурсивную формулу:
f(n, m) = 0 (n = 1)
f(n, m) = (f(n - 1, m) + m) % n (n > 1)
После получения приведенной выше рекурсивной формулы задача становится простой:
public static int f(int n, int m) {
if (n == 1) return 0;
return (f(n - 1, m) + m) % n;
}
Переключившись на тернарный оператор, мы можем даже ответить на этот вопрос одной строкой кода:
public static int f(int n, int m) {
return n == 1 ? 0 : (f(n - 1, m) + m) % n;
}
Лучшие практики
Выше приведены несколько распространенных решений «проблемы кольца Джозефа». Наиболее эффективным является четвертое решение, за которым следуют первое и третье решения. Второе решение является наименее эффективным, но его легче всего придумать. Хотя эта проблема может быть наиболее эффективно решена с помощью математической индукции, я все же рекомендую третье решение, наиболее совместимое с компьютерным мышлением. При этом сложность алгоритма невелика. Но если вы работаете с программой, требующей высокой производительности, конечно, четвертое решение — лучший выбор.
Суммировать
В процессе ответа на этот вопрос мы использовали связанный список, который является очень распространенной структурой данных. Может быть, вы используете его много, но не знаете об этом. Проблемы со связанными списками часто возникают в алгоритмах. Если вы хотите узнать больше о связанных списках, обратите внимание на паблик «Ouyang Feng Studio». В следующей статье мы поговорим о тех проблемах алгоритмов, связанных со связанными списками.