Продолжаем серию переводов цикла «Трудные вопросы на собеседовании».
Как вы обернете порядок слов (не символов) в строке длиной n при постоянном объеме дополнительной памяти (constant extra space) за линейное время (linear time)?
UPDATE: ответ.
Сначала обратите всю строку (меняя местами первый и последний символы в направлении середины, и т.д.). Этого должно быть достаточной подсказкой для вас. Если нет, читаем дальше.Затем обратите порядок символов в каждом слове. Теперь буквы в словах располагаются в изначальном порядке (т.к. они были обращены два раза), но слова находятся в обратном порядке (первое слово — в конце, и т.д.)
За проявленную активность администрация developers.org.ua рада вручить футболку Олексию Орешко.
Да... помню задавал на собеседовании такую задачку)) пока что результат 50%... правда решил ее давать только 2 челам)) обычно до нее дело не доходит...
2 ЩетининПривіт Малюк, як життя?
2 raggzyУ тебе, до речі, якщо рядок (після розвороту) закінчується словом, то це останнє слово буде написано ззаду наперед. Приклад: на «ab cd» видасть «cd ba».
прикол, решение сразу же было дано, но обсуждение не заканчивается, собрались звери:) просто рвут задачу на куски:)
2 raggzy: Співбесіда ж на ІТ-позицію, а не на філолога — так що код потрібен:)
Эх. оказуется, ее уже решили идейно в посте 11...сорри за офтоп:)
чуваки сорри за and, должно быть &&, привык у ся передефайнивать:)
Еще раз алгоритм, бо система делает текст по дыбильному написанным:)
Alexander Skakunov
anonymous
Олексій Орєшко
long i,j = 0;while true{ while ((i < n) and whitespace(s[i])) i++; // передвигаем первый в начало слова if (i==n) break; j=i+1; while ((j < n) and !whitespace(s[j])) j++; reverse(s,i,j);// разворот найденого слова i=j;// переход к новому слову}Всего 3 прохода по строке. (1 — пункт один, 2 и 3-в вайле, просто разворот каждого слова по сути добавляет еще один проход)
Как я понял условие: Есть только ваша строка, никакой дополнительной памяти (даже копии строки), кроме како-то константного (5−10) кол-ва переменных (long"ов, например) быть не может.Таким образом, строку нельзя ни разрезать, ни вставлять в нее ничего. Можно лишь только менять 2 символа с i и j позиций.В таком ракурсе решение: 1. Просто развернуть строку
for (long i = 0; i < n/2; i++) {char a=s[i]; s[i] = s[n-i-1]; s[n-i-1]=a)Кому не нравится, можете вынести char a за цикл. Всего : Один проход по строке.2. В полученной строке поразворачивать слова.Это реализуется с помощью двух указателей, первый - на начало слова, другой на конец. Разворот такой же, как и в пункте 1.
long i,j = 0;while true{while ((i < n) and whitespace(s[i])) i++; // передвигаем первый в начало словаif (i==n) break;j=i+1;while ((j "milk want I" -> "milk want I"
2 Саша>> Потрібно буде виділити масив, розмір якого залежить від вхідних даних, а також створити копії всіх слів в стрічці і помістити їх у цей масив.Наскільки я зрозумів це речення, то копії всіх слів одночасно перепишуться в масив — тобто, власне, весь вміст входу (за виключенням пробілів) буде переписано.Щодо оптимізації — я мав на увазі, що деталі реалізації можуть суттєво відрізнятись. Крім того, якщо ми використовуємо деякі бібліотечні методи, то деталі їх реалізації, очевидно, напряму впливає на складність кінцевої програми.
2 Olexiy>> Наскільки я зрозумів, то пам’ять має бути лінійна як мінімум (копія всього). Копію всього робити непотрібно, оскільки результат роботи ф-ї записується в той же масив, де були вхідні дані.>> Мова програмування може оптимізувати деякі операції.Оптимізувати може компілятор (а не мова програмування). Оптимізація НІКОЛИ не рообить з неправильної програми — правильну і не змінює складність алгоритму (лінійний, логарифмічний).Компілятор може лише замінювати деякі елементарні (з точки зору мови програмування) операції на еквівалентні або ж викидати частини коду що не впливають на результат.
Хмм...цикл такой for (unsigned i = 0; i < len; ++i)...
Сорри за пост 21. 22+23 моё решение.P.S: Непонимаю почему в один не влезает...= (
{ if(str[i] == ' ') { nF = nL; nL = i - 1; reverse(str,nF,nL); nL +=2; } } reverse(str,nL,len-1); reverse(str,0,len-1); Memo1->Lines->Add(str);
char* str = "Hello my dear friend . How are you ?"; Memo1->Lines->Add(str); Memo1->Lines->Add("---------------------------"); unsigned nF = 0; unsigned nL = 0; unsigned len = strlen(str); for(unsigned i = 0; i Lines->Add(str);
char* str = "Hello my dear friend . How are you ?"; Memo1->Lines->Add(str); Memo1->Lines->Add("---------------------------"); unsigned nF = 0; unsigned nL = 0; unsigned len = strlen(str); for(unsigned i = 0; i Lines->Add(str);
похоже на задачки с алгоритмической олимпиады...
Спробую пояснити на пальцях про «constant extra space».Якщо вашій програмі для обробки вхідних даних довжиною в одну букву (1 слово з однієї букви) необхідно виділити блоки пам’яті сумарним розміром в 1 МБ але коли на вхід передали стрічку, що містить 4 Мільярди слів по 100 букв у кожному слові — програмі все ще буде достатньо цього ж 1 МБ додаткової пам’яті.У випадку ruby: string.split.reverse.join (" ") Потрібно буде виділити масив, розмір якого залежить від вхідних даних, а також створити копії всіх слів в стрічці і помістити їх у цей масив. Відповідно, оцінити розмір додаткової мам’яті не знаючи розміру вхідної стрічки — неможливо.
если используется массив той же длины что и строка, то это constant extra space?
це linear extra space
Поприветствуем Олексия Орешко, координатора TopCoder! Олексий, могли бы вы авторитетно объяснить, что такое этот constant extra space? Ибо народ конфузится, хотя ответы пишет правильные.
Упс, все-таки треба тестити спочатку.
void f(string& s) { reverse(s.begin(), s.end()); int prev = -1; for (int i = 0; i < s.length(); i++) if (s[i] == ' ') { reverse(s.begin() + prev + 1, s.begin() + i); prev = i; } reverse(s.begin() + prev + 1, s.end());}
C++
// Вважаємо, що слова в рядку розділяються пробілами.void f(string& s) { reverse(s.begin(), s.end()); int prev = 0; for (int i = 0; i < s.length(); i++) if (s[i] == ' ') { reverse(s.begin() + prev, s.begin() + i); prev = i; } reverse(s.begin() + prev, s.end());}
Перевертнуть всю строку, а потом перевернуть символы в каждом слове.
string.split.reverse.join (" «)
Прикольно:) Правда, не соблюдено условие задачи — «constant extra space», т.к. используется массив переменной длины.
Да, добавлю сразу — str передается в функцию по ссылке.
Sorry за отвутствие отступов, пробую еще раз только функцию:
function reverse(str, s, e) { for(i = s; i < e/2; i++) { buf = str[i]; str[i] = str[e - i + 1]; str[e - i + 1] = buf; }}
Пусть есть такая функция оборота части строки (псевдокод, str — строка, s — начальный индекс, e — конечный): function reverse (str, s, e) { for (i = s; i < e/2; i++) { buf = str [i]; str [i] = str [e — i + 1]; str [e — i + 1] = buf; } } Первым делом оборачиваем всю строку: reverse (str, 0, n) Затем последовательно находим границы слов (s_word, e_word) и для каждого вызываем: reverse (str, s_word, e_word) Вот как-то так примерно
it [string-matching algorithm] processes the searched text with constant memory space in addition to the string
pregsplit на слова и реверс массива слов.На счет памяти тоже не понял, что имелось в виду? кол-во байт и операции только с массивом символов?
Я б виділяв по слову з початку та кінця рядка, а тоді міняв їх місцями через додаткову пам’ять. І так, до зустрічі вказівників у середині рядка.Хоча, я не до кінця зрозумів обмеження constant extra space.
35 коментарів
Підписатись на коментаріВідписатись від коментарів Коментарі можуть залишати тільки користувачі з підтвердженими акаунтами.