Нахождение “Энного узла от конца” связанного списка
Это, кажется, дает корректный ответ, но я не уверен, действительно ли это - лучший способ пойти о вещах. Кажется, что я посещаю первые n узлы слишком много раз. Какие-либо предложения? Обратите внимание, что я должен сделать это с отдельно связанным списком.
Node *findNodeFromLast( Node *head, int n )
{
Node *currentNode;
Node *behindCurrent;
currentNode = head;
for( int i = 0; i < n; i++ ) {
if( currentNode->next ) {
currentNode = currentNode->next;
} else {
return NULL;
}
}
behindCurrent = head;
while( currentNode->next ) {
currentNode = currentNode->next;
behindCurrent = behindCurrent->next;
}
return behindCurrent;
}
5 ответов
Другой способ сделать это без двойного посещения узлов:
Создать пустой массив размера n, указатель на этот массив, начиная с индекса 0, и начать итерацию с начала связанного списка. Каждый раз, когда вы посещаете узел, сохраняйте его в текущем индексе массива и перемещайте указатель массива. Когда вы заполняете массив, оберните и перезапишите элементы, которые вы сохранили ранее. Когда вы дойдете до конца списка, указатель будет указывать на элемент n из конца списка.
Но это тоже всего лишь алгоритм O (n). То, что вы сейчас делаете, нормально. Я не вижу веских причин менять это.
В Python итеративный:
digit_map = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz',
}
def word_numbers(input):
input = str(input)
ret = ['']
for char in input:
letters = digit_map.get(char, '')
ret = [prefix+letter for prefix in ret for letter in letters]
return ret
ret - это список результатов на данный момент; первоначально он заполняется одним предметом, пустой последовательностью. Затем, для каждого символа во входной последовательности, он ищет список букв, которые соответствуют ему из dict, определенного в верхней части. Затем список ret заменяется каждой комбинацией существующего префикса и возможной буквы.
Посмотрите эти две ссылки для действительно тщательного анализа того, что и как вы можете общаться между веб-сайтом, с которого вы запускаете приложение clickonce, и самим приложением.
- Обеспечение безопасности развертываний ClickOnce
- Обеспечение работы ClickOnce с аутентификацией ASP.NET Forms
Основной метод состоит в динамическом изменении файлов манифестов на веб-сервере, с которого запускается приложение (и помните, что эти файлы манифестов должны быть переподписаны после их изменения).
Хотя это все равно не позволит передавать «параметры» как таковые, вы можете моделировать «параметры» путем динамического включения дополнительного конфигурационного файла, который приложение может прочитать при запуске.
-121--3199702-Можно использовать список с двойными связями, который также содержит адрес родителя. Трансверсал гораздо проще, так как вы можете начать в конце и работать свой путь к началу.
Сначала подсчитайте количество узлов в списке. Затем пройдитесь еще раз, отсчитав на n узлов меньше. По-прежнему алгоритм O (n), это неизбежно.
Запуск двух указателей. Переместите вперед первый N элементов, а затем переместите каждый указатель на 1 элемент. Когда первый указатель достигнет конца, второй указатель даст ответ.
РЕДАКТИРОВАТЬ : Да, это практически тот же код, что и в вопросе. Но я чувствую, что псевдокод проясняет ситуацию. Чтобы ответить на вопрос, другого выхода нет, так как первые N элементы должны быть посещены дважды. Если N мало, это не имеет значения. Если N велико, второй цикл будет маленьким. Так что это всегда решение O (n) .
Ваше время работы все еще равно O (n), поэтому я не вижу, чтобы с ним возникли какие-либо проблемы.
По идее, вы можете разделить список на две части: часть перед возвращаемым узлом и часть после. По одной из этих частей придется пройти дважды. Ваша реализация выбрала первый, с тем преимуществом, что не требуется дополнительной памяти (кроме пары временных переменных).
Как вариант, вы можете создать стек, пройти по списку и поместить каждый элемент в стек, а затем вытащить n элементов. Тогда вы дважды пройдете конец списка, а не начало. Это имеет недостаток, заключающийся в том, что список сохраняется в памяти дважды. (Вы можете сделать стек немного умнее, сохраняя только n элементов и удаляя их из нижней части стека по мере добавления новых; тогда вы используете достаточно места только для хранения n узлов.)
Я предполагаю что вы не можете уничтожить список, переставив его на место. Тогда это постоянная память, все еще O (n), по-прежнему дважды проходя конец списка.