Я считаю, что следующее решение работает правильно и использует память 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 на предыдущей итерации, поскольку, когда мы переводим ее в правильное положение, она должна пропустить одну позицию для 1-го элемента и одну позицию для 4-го элемента:
? ? ? ? 5
Повторяя эту же логику, мы получаем, что предыдущий индекс был бы 7:
? ? ? ? ? ? 7
Теперь, для следующего шага, мы знаем, что мы бы опустили конфету на две позиции, потому чтомы выпали 1-й и 4-й элементы.Однако, это поставило бы нашу конфету в положение 9, которое было бы удалено.Это означает, что вместо этого мы поставили бы конфету в положение 10:
? ? ? ? ? ? ? ? ? 10
На данный момент, поскольку осталось 10 конфет, мы знаем, что полностью изменили процесс и сделали это.Поскольку последним местом отдыха нашей конфетки была позиция 10, мы знаем, что ответом является то, что десятая конфета - это та, которая была съедена, что идеально соответствует нашей предыдущей работе!
Уловка этого подхода заключается в том, что мыне нужно много памяти, чтобы заставить его работать.В частности, на каждом шаге нам нужно отслеживать только несколько вещей:
- По какому индексу в данный момент находится последняя конфета? Нам нужно это, чтобы знать, кудастоп.
- Сколько квадратов ниже этого индекса? Нам нужно это знать, сколько элементов удаляется на каждом шаге.
- Что будет дальшесовершенный квадрат? Нам нужно это знать, когда число квадратов, удаляемых каждый раз, увеличивается.
- Какой последний индекс мы исследовали? Этот алгоритм работает, выполняя процесс в обратном направлении.Итак, в какой-то момент мы поймем, что запустили его один раз слишком много.Когда это происходит, нам нужно иметь возможность «сделать резервную копию» шага, чтобы перейти к последнему индексу, который не перескочил.
Учитывая это, мы имеем следующий алгоритм:
- Установите текущий индекс равным 1.
- Установите число меньших совершенных квадратов равным 1.
- Установите следующий идеальный квадрат равным 4.
- Установитепоследний меньший индекс равен 1.
- Хотя текущий индекс меньше n:
- Установите последний меньший индекс как текущий индекс (запомните решение до сих пор).
- Установить текущий индекс + = количество меньших совершенных квадратов (запустить процесс в обратном направлении на один шаг)
- Если текущий индекс равен следующему идеальному квадрату, добавить к нему один (крайний случай выполненияназад, если мы попали в идеальный квадрат, мы должны быть на шаг впереди него)
- Если текущий индекс больше, чем следующий идеальный квадрат (теперь на каждом шаге удаляется больше чисел):
- Установите идеальный квадрат, чтобы быть рядом с идеальнымquare.
- Добавьте единицу к числу идеальных квадратов, меньших, чем индекс.
- Возвращает последний меньший индекс.
Для хранения всех значений требуется только 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's 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.
Надеюсь, это поможет!