Трудный вопрос на собеседовании #4
Каким образом можно циклично сдвинуть строку длиной n на m символов при константной дополнительной памяти за линейное время?
UPDATE: ответ.
Все про українське ІТ в телеграмі — підписуйтеся на канал DOU
Каким образом можно циклично сдвинуть строку длиной n на m символов при константной дополнительной памяти за линейное время?
UPDATE: ответ.
Все про українське ІТ в телеграмі — підписуйтеся на канал DOU
Богдан Штепан — Back-end Software Engineer, який створює контент для LeetCode. Ми поговорили з ним про роботу, «золотий стандарт FAANG» у вигляді задачок, особливості контракту з LeetCode та інсайди щодо розвитку порталу. 14
Первинне інтерв’ю при наймі зазвичай проходить саме з HR-менеджером, який дивиться, наскільки кандидат загалом відповідає компанії і чи варто «пропускати» його далі, на наступні етапи співбесіди. 62
І кандидатам, і рекрутерам/HR завжди потрібно підвищувати свій професіоналізм, але це відбудеться, тільки коли ми навчимося слухати і чути один одного і тим більше поважати роботу один одного. 175
Определите, на каком символе от начала строки вы хотите быть после сдвига. Затем разделите строку на две части так, чтобы этот символ был первым во второй «половине» строки. Оберните каждую часть на месте, затем оберните всю результирующую строку.
Вы слишком усложняете.Сдвиг влево на М символов есть перестановка местами двух подстрок из М и N-M символов.Перестановка без дополнительной памяти делается следующим образом: АБЦД1234567 -> ДЦБА1234567 -> ДЦБА7654321 -> 1234567АБЦДКак все уже догадались, на каждом шаге мы разворачиваем некоторую подстроку задом наперед.Вот мы и свели задачу к предыдущей — как обратить строку за линейное время без доп.памяти уже бурно обсуждалась при трудоустройстве в стартапы.Так-то.
Мда... Александру накидали тут кусков кода. Поди разберись чей как работает: -)
char s[] = "asdasfmnsbd sdf".toCharArray();int n = s.length;int m = 3;int count = 0;int j = 0,i;char dop,tmp;// пока не обработали всеwhile (count<n){ i=j;dop = s[i];do {tmp = s[(n+i-m%n)%n];s[(n+i-m%n)%n] = dop;i=(n+i-m%n)%n;dop = tmp;count++;}while (i!=j); // пока не пришли на начало циклаj++; // увеличиваем остаток рассматриваемого класса}System.out.println(s);
Ну, наверное ниче нового не внесу, но как еще один вариант можно рассмотреть.Идея 1) сдвиг на m равносилен сдвигу на m%n2) сдвигать можно в стиле: Идейно цикл: запомнить то, на чем сейчас, перейти на m%n символов влево/вправо, влупить туда то, что запомнил, перед этим запомнить то, что там было.Но тут появляются приколы. Решение математикой.Если m и n не взаимопростые, то цикл пройдется не по всем елементам, а по классу одинаковых остатков стартового символа.Для этого (не вычисляя никаких НСД/НСК) мы просто итерируем все классы одинаковы х остатков. Можно начинать с 0, потом 1,...и так пока не переитерируем все символы, используя каунтер уже сдвинутиых символов. Можно было б вычислить шаги сразу -, но нет смысла, т.к там надо будет НСКНСД...Ну вот такое решение на JAVA. Влом было красиво оформлять с параметрами...
кудато else прапало при посте
} else {m = n-m;for(int i=n-(m/2)-1;i>=0;i--){swap(str,i,((n-m)+(i%m)));}}
при буфере в 1 char, время выполнения = O (n- (m/2)):
public static void main(String[] args) {char[] str = {'0','1','2','3','4','5','6','7','8','9'};int n = str.length;int m=4;if (n/2>=m) {for(int i=0;i=0;i--){swap(str,i,((n-m)+(i%m)));}}System.err.println(Arrays.toString(str)); } static void swap(char[] str, int i1, int i2 ){char t = str[i1];str[i1] = str[i2];str[i2] = t; }
Ага, возвращает std: string: size_type или size_t. Исправлюсь.А по второму вопросу, анализ хидерных файлов студии показал что это тип unsigned. Как по ГОСТУ, я к сожалению не знаю
-
Я имел ввиду, что количество обменов зависит от длины строки, а не от велечины сдвига.А чем конструкция «const int m=str.length (); » плоха? Я специально ее и вводил, чтобы если ненароком захочу изменить m, то компилятор выдал бы мне предупреждение. Стараюсь стремиться к безопасному программированию так сказать...
-
-
Правда у Vladа алгоритм тоже вроде как линейный. По крайней мере количество перестановок при любом n одинаково.
Вот версия без вложенных циклов и рекурсий
void move(std::string& str, int n){const int m=str.length();int pos=0, start=0;char ch=str[0];for(int i=0;i<m;i++){pos=(pos+n)%m;std::swap(str[pos], ch);if(pos==start){pos=start+=1;ch=str[start];}}}
-
2 ВладА, вірно, треба замінити на doMove (s, last, m — ((i — start) % m)); наdoMove (s, last, m — ((last — start) % m)); Хоча в сьомій студії таке працювало, коли я тестува (змінна і зберігає значення, якого вона набула в циклі, а з областями видимості у них проблеми)
-
2 VladВін розбиває перестановку букв на незалежні циклічні перестановки, і переставляє кожну таку циклічну перестановку окремо (красиво, до речі, вийшло:)
-
-
-
Сдвиг вправо для C#:
public static string Shift(string s, int m) { char[] input = s.ToCharArray(); int n = s.Length; int k = <a href="n, m">Наибольший общий делитель</a>; int count = n / k; for (int shift = 0; shift < k; shift++) { char old = input[shift]; for (int index = 1; index < count; index++) { int currentIndex = (shift + index * m) % n; char tmp = input[currentIndex]; input[currentIndex] = old; old = tmp; } input[shift] = old; } return new string(input); }
-
@4, не поможет ли
code { white-space: pre }
? Если это портит малину для кода внутри строки, то можно добавлять
pre
автоматически если внутри
code
есть переносы строки. Ану орлы, бегом задачку решите, не только ж байты переставлять. =))
>> Кстати, чтобы код был секси, надо заключать его в теги pre+codeЩось ніяк не виходить.
void doMove(string& s, int start, int m) { m %= (s.length() - start); if (m == 0) return; int last = s.length() - m; for (int i = start; i < last; i++) swap(s[i], s[i + m]); doMove(s, last, m - ((i - start) % m));}
void doMove(string& s, int start, int m) {m %= (s.length() - start);if (m == 0)return;int last = s.length() - m;for (int i = start; i < last; i++)swap(s[i], s[i + m]);doMove(s, last, m - ((i - start) % m));}
2 mdm>> Тогда нужно с начала строки и до shift-1 копировать символы в буфер размером kбайт, затем сдвигать всю строку влево на k байт и символы из буфера копировать в конец строки.Так, а що робити, якщо вони не влізуть в буфер розміром к байт, бо к менше, ніж shift?
Класна задача, раніше такої не бачив.Будемо вважати, що зсуваємо вліво.Яка ідея придумалась: Йдемо зліва направо, і обмінюємо символ з номером і на символ з номером і + m, допоки не дійдемо до моменту, коли цього зробити не можна, бо і + m вилазить за межі.Наприклад, зсуваємо рядок «abcdefg» на 3 символи вліво: abcdefg -> dbcaefg -> decabfg -> defabcg -> defgbcaТепер запускаємо рекурсивно ту саму операцію на хвості, але з іншим m (в даному випадку — зсуваємо bca на два символи вліво). Якщо тепер акуратно реалізувати, то виходить: void doMove (string& s, int start, int m) { m %= (s.length () — start); if (m == 0) return; int last = s.length () — m; for (int i = start; i < last; i++) swap (s [i], s [i + m]); doMove (s, last, m — ((i — start) % m)); } На д/з лишаємо доведення того, що час виконання буде лінійним.ПСДана реалізація, насправді, теоретично може жерти лінійну пам’ять, якщо підібрати правильні Н та М (питання — які?:) через те, що траплятиметься забагато вкладених викликів методу, але цей самий метод можна легко переписати ітеративно, а не рекурсивно.
2 ВсеволодНаверное вы правы.Тогда уместно будет использовать XOR для перестановки соответствующих символов в строке. Время будет = O (m/k).
А ведь-таки так! Тогда нужно с начала строки и до shift-1 копировать символы в буфер размером k байт, затем сдвигать всю строку влево на k байт и символы из буфера копировать в конец строки. Или наоборот.
Условие «за линейное время» в моём решение соблюдено.А условие «при константной доп. памяти» решается копированием символовиз первой части строки в конец второй части с использованием фиксированногопо размеру буфера. Если буфер будет равен одному символу, то мы решаем этузадачу на O (m) времени.
Задачка сама по себе не очень сложная — сделать из «колбаса» «басакол».
str = str.substr(shift) + str.substr(0, shift-1);
А вот решить ее, соблюдая ограничения — уже труднее: при константной дополнительной памяти за линейное время
Символы «съелись». Короче, свопаем вот так: swap (start... (shift-1), shift...end), где «...» это диапазон.
Псевдокод: shift = m % n; str = str.substr (shift) + str.substr (0, shift-1); Сначала вычисляем на сколько символов нужно реально сдвинуть (если вдруг m > n), а затем меняем местами части строки: start... (shift-1) shift...end.Вроде так:)
38 коментарів
Підписатись на коментаріВідписатись від коментарів Коментарі можуть залишати тільки користувачі з підтвердженими акаунтами.