Ответ 1
Я считаю, что следующее решение работает правильно и использует память O (1), предполагая, что вы можете удерживать целое число в O (1) пространстве. Идея состоит в том, чтобы попытаться запустить этот процесс назад, пока вы не обретете окончательное положение правильной части конфеты.
Проследим пример этой проблемы, где n = 10. Тогда получим:
1 2 3 4 5 6 7 8 9 10
X X X
2 3 5 6 7 8 10
X X
3 5 7 8 10
X X
5 7 10
X
7 10
X
10
Теперь предположим, что мы хотим вычислить конечный результат для этой проблемы. Мы знаем, что, когда мы закончили, конфеты съели в позиции 1, так как осталось только один кусочек конфеты. Поэтому попробуйте настроить его следующим образом:
1
Теперь мы знаем, что на предыдущей итерации конфеты с индексом 1, должно быть, были съедены. Это означает, что последняя конфета была фактически в положении 2 в последний раз:
? 2
На итерации до этого мы знаем, что, поскольку конфеты 1 были съедены, наша конфета должна была быть в положении 3:
? ? 3
В этот момент мы снова возвращаем одну итерацию. Мы знаем, что конфеты 1 были съедены, но конфеты 4 тоже были съедены. Это означает, что индекс нашей конфеты должен был быть 5 на предыдущей итерации, так как, когда мы подбрасываем его до своего правильного положения, он должен был пропустить одно место для первого элемента и одно пятно для 4-го элемента:
? ? ? ? 5
Повторяя эту же логику, получим, что предыдущий индекс был бы 7:
? ? ? ? ? ? 7
Теперь, для следующего шага, мы знаем, что мы бы разбили конфеты на две позиции, потому что мы бросили 1-й и 4-й элементы. Однако это положило бы нашу конфету в позицию 9, которая была бы удалена. Это означает, что вместо этого мы помещаем конфету в положение 10:
? ? ? ? ? ? ? ? ? 10
В этот момент, поскольку осталось 10 конфет, мы знаем, что мы полностью изменили процесс и закончили. Поскольку последнее место отдыха нашей конфеты было позицией 10, мы знаем, что ответ заключается в том, что 10-я конфета - это та, которая была съедена, что идеально соответствует нашей предыдущей работе!
Трюк этого подхода заключается в том, что нам не нужно много памяти, чтобы заставить его работать. В частности, на каждом шаге нам нужно отслеживать только несколько вещей:
- Какой индекс - последний кусок конфеты в настоящее время? Нам нужно это знать, где остановиться.
- Сколько квадратов ниже этого индекса? Нам нужно знать, сколько элементов удаляется на каждом шаге.
- Что представляет собой следующий идеальный квадрат? Нам нужно это знать, когда количество удаляемых квадратов увеличивается каждый раз.
- Что было последним индексом, который мы исследовали? Этот алгоритм работает, запустив процесс назад, поэтому в какой-то момент мы поймем, что мы запустили его один раз слишком много. Когда это произойдет, мы должны иметь возможность "создать резервную копию" шага, чтобы перейти к последнему индексу, который не перешагнул.
Учитывая это, мы имеем следующий алгоритм:
- Установите текущий индекс на 1.
- Задайте количество меньших совершенных квадратов до 1.
- Установите следующий идеальный квадрат на 4.
- Установите последний меньший индекс равным 1.
- Пока текущий индекс меньше n:
- Установите последний меньший индекс как текущий индекс (помните решение до сих пор).
- Установить текущий индекс + = число меньших совершенных квадратов (запустите процесс назад на один шаг)
- Если текущий индекс равен следующему совершенному квадрату, добавьте его к нему (крайний случай запуска его назад, если мы нажмем идеальный квадрат, мы должны пройти его один шаг).
- Если текущий индекс больше, чем следующий идеальный квадрат (теперь на каждом шаге удаляется больше номеров):
- Установите идеальный квадрат, чтобы быть следующим идеальным квадратом.
- Добавьте один к числу совершенных квадратов, меньших индекса.
- Возвращает последний меньший индекс.
Для хранения всех значений требуется только память O (1).
Попробуйте пример! При n = 20, если мы работаем через формальный процесс, получаем следующее:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
X X X X
2 3 5 6 7 8 10 11 12 13 14 15 17 18 19 20
X X X X
3 5 7 8 10 11 13 14 15 17 18 19
X X X
5 7 10 11 13 14 17 18 19
X X X
7 10 13 14 17 18
X X
10 13 17 18
X X
13 17
X
17
Если мы запустим наш алгоритм, получим
Current Index Next Square Smaller Squares
1 4 1
2 4 1
3 4 1
5 9 2
7 9 2
10 16 3
13 16 3
17 25 4
21 25 4
Так как 21 > 20, последний меньший индекс равен 17, поэтому мы возвращаем 17, что является правильным ответом!
Написано как код C, не предполагая полного переполнения:
int EatenCandyIndex(int n) {
int currIndex = 1;
int numSmallerSquares = 1;
/* Rather than tracking the next square, track the root of the next
* square. We can just square this to get the next square.
*/
int rootOfNextSquare = 2;
/* The last spot where the candy would be before we had Too Much Candy. */
int lastIndex = 1;
while (currIndex <= n) {
lastIndex = currIndex;
currIndex += numSmallerSquares;
if (currIndex == rootOfNextSquare * rootOfNextSquare)
++currIndex;
if (currIndex > rootOfNextSquare * rootOfNextSquare) {
++numSmallerSquares;
++rootOfNextSquare;
}
}
return lastIndex;
}
Однако, как написано, этот алгоритм не особенно эффективен. В частности, посмотрите на его поведение в примере, где n = 20. Заметим, что у нас есть три раунда, где размер шага один, два с шагом размером два и три и т.д. Вместо того, чтобы эти раунды встречаются явно, мы могли бы вместо этого вычислить сколько раундов придется выполнять с этим размером шага, а затем просто запустить все эти шаги сразу. Таким образом, у нас всегда есть один раунд с размером один, один раунд с размером два, один раунд с размером три и т.д. Для этого на каждом шаге нам нужно будет увидеть, какова наша следующая цель; это будет либо число n, либо следующий совершенный квадрат. Как только мы нашли свою цель, нам нужно посмотреть, сколько шагов требуется для ее получения. Если текущий индекс равен i, а наша цель равна t, и если размер шага равен k, тогда нам нужно взять & lceil; (t - i)/k & rceil; шаги, чтобы добраться туда. Используя симпатичный трюк с целым делением, мы можем вычислить это как
int numSteps = ((t - i) + (k - 1)) / k;
Это дает нам следующий обновленный алгоритм:
int EatenCandyIndexFaster(int n) {
int currIndex = 1;
int numSmallerSquares = 1;
/* Rather than tracking the next square, track the root of the next
* square. We can just square this to get the next square.
*/
int rootOfNextSquare = 2;
while (true) {
/* Figure out what our target is. */
int target = min(n, rootOfNextSquare * rootOfNextSquare);
/* See how many steps are required. */
int numSteps = ((target - currIndex) + (numSmallerSquares - 1)) / numSmallerSquares;
/* See where we'd end up if we took one fewer than this many steps forward. */
int lastIndex = currIndex + (numSteps - 1) * numSmallerSquares;
/* Take that many steps forward. */
currIndex += numSmallerSquares * numSteps;
/* There is an edge case here: if we hit our number but it a perfect square,
* we want to return the previous value.
*/
if (currIndex == n && n == rootOfNextSquare * rootOfNextSquare)
return lastIndex;
/* Otherwise, if we hit the target number exactly, return it. */
if (currIndex == n)
return currIndex;
/* Otherwise, if we overshot the target number, hand back where we'd be if we
* took one fewer step.
*/
if (currIndex > n)
return lastIndex;
/* Oh well; didn't make it. If we hit a perfect square, skip it. */
if (currIndex == rootOfNextSquare * rootOfNextSquare)
++currIndex;
++numSmallerSquares;
++rootOfNextSquare;
}
}
Эта оптимизированная версия алгоритма работает в O (& radic; N) времени и использует O (1) пространство. Причиной временной привязки является то, что каждый шаг алгоритма переходит к следующему совершенному квадрату, и только O (& radic; N) идеальные квадраты меньше N.
Надеюсь, это поможет!