leetcode | C++ | 189 Rotate Array | задача повернуть массив из Top Interview 150
HTML-код
- Опубликовано: 10 янв 2024
- Есть такой сайт leetcode, где можно найти задачи с разных собеседований.
Выбираете проблему, читаете описание, внимательно изучаете примеры.
Выбираете язык программирования и вставляете свою реализацию в подготовленную функцию.
Далее можно запустить тесты и отправить на сервер для проверки, он покажет место в рейтинге, которое занял Ваш код по памяти и производительности.
leetcode.com/
leetcode.com/problems/rotate-...
Задача из Top Interview 150
189. Дан массив с целыми числами. Необходимо повернуть его направо на к шагов, где к - неотрицательное число.
#cpp
#leetcode
#leetcodesolutions
Вы чего? обычный циклический сдвиг поворотом называете??? капешник какой-то … жертвы егэ не иначе
Прикольно. Спасибо
У меня есть более интересный метод решения, но он для тех кто любит опасность, мы меняем указатель на мисив на n шагов, голуву записываем в конец, и надеемся что нечего критически важного не сломалось
@@xkjeiw93uqj нет, сдесь я и написал про опасность, ты берёшь и меняешь указатель памяти на 4 байта (ну если ты используешь числа char) и в конце дописываешь голову, ты выходишь за границы масива в этом и заключается опасность
Я немного не понял задачу но суть это не меняет мы двигаемся указатель в другую сторону и хвост перетаскиваем в перед
Должно работать на массиве [1,2] и k = 5 и выход должен быть [2,1]. Величина k может быть больше, чем длина массива.
познавательно
Еще есть std::rotate.
Кажется, что можно за 1 вызов STL осуществить указанное.
А именно std::rotate(v.begin(), v.begin( ) + 3, v.end( ));
Для работы - да, а тут вопрос с собеседования, думаю, они захотят увидеть подробный алгоритм реализации. std::rotate вряд ли реализуешь сходу, а вот std::reverse это почти swap, который легко реализовать.
@@DariaEmacsкак раз хотел оставить комментарий насчёт собеседования. Тут нужно общаться конкретно с интервьюером, что он думает на этот счет. Потому что использование уже готового решения в виде std::reverse их тоже могут не устроить. Вот)
А так, поход интересный.
Почему только это называется поворотом справа? Куда понятнее циклический сдвиг вправо. И объяснений лишних не нужно) но это уже к авторам задачи
Сомневаюсь что reverse самый быстрый способ.
Быстрее всего через новый массив и 2 memcpy.
Самый быстрый из методов, которые расходуют память O(1).
А сложность самого метода reverse какая?
Exactly std::distance(first, last) / 2 swaps.
Я ее уже посчитала в O(n)
А через цикл и функцию swap, или ее нету у массива, не оч помню
Идея что-то подобное написать, про эффективность не могу ничего сказать
#define s 15
// s - размерность массива
//...
for(int i=0; i
Должно работать на массиве [1,2] и k = 5 и выход должен быть [2,1]. Величина k может быть больше, чем длина массива. У Вас выйдет за границы массива. И в цикле, кажется, что-то не так. Обмениваются одни и те же значения mass[s].
@@DariaEmacs ой, опечатка в клаве там swap(mass[i], mass[s])
А нет, оно все равно не работает
@@skarty7672потому что поворот массива на 1 это не смена первого и последнего элемента местами, а первый становится вторым, второй - третьим и т.д. и потом последний становится первым, то есть надо свапать все элементы массива для каждого K, для к = 4 нужно просвапать K * S раз, указанный алгоритм будет свапать фиксированно 2 * S раз
Эту хрень можно и без цикла сделать, с 3 переменной массива
На массиве [1,2] и k = 5 и выход должен быть [2,1], получится с 3 переменной?
@@DariaEmacs, k может быть больше nums.size()? тогда и с арифметикой указателей решение должно работать немного иначе. Но вообще, решение крутое, хоть и контр-интуитивное. Интуитивно хочется сделать nums.size() свапов, а не 2*nums.size() свапов. Ассимптотика та же, но разница может оказаться существенной.