Практические задачи
Практические задачи на C# — алгоритмы со строками и массивами, рекурсия и приёмы на месте.
6 вопросов
JuniorКодОчень частоРазвернуть char[] на месте за O(n) и O(1) памяти
Развернуть char[] на месте за O(n) и O(1) памяти
Два индекса l = 0 и r = s.Length - 1. Пока l < r, меняйте местами s[l] и s[r] (кортежный обмен (s[l], s[r]) = (s[r], s[l])), затем l++ и r--. Цикл кончается, когда они пересекаются, разворачивая на месте. O(n) по времени, O(1) дополнительной памяти.
Типичные ошибки
- ✗Идти до самого конца и менять дважды, восстанавливая исходный порядок
- ✗Выделять второй массив, нарушая требование O(1) дополнительной памяти
- ✗Возвращать новое значение вместо изменения переданного массива на месте
Уточняющие вопросы
- →Почему цикл должен останавливаться на
l < r, а не идти до конца? - →Как суррогатные пары (эмодзи) ломают наивный разворот по
char?
JuniorКодЧастоНайти n-е число Фибоначчи итеративно за O(n) и O(1)
Найти n-е число Фибоначчи итеративно за O(n) и O(1)
Держите два скользящих значения a = 0, b = 1. Цикл n раз: вычисляйте b как a + b и сдвигайте a к старому b кортежным обновлением (a, b) = (b, a + b). Верните a. Это O(n) по времени, O(1) памяти — без массива и без экспоненциальной рекурсии.
Типичные ошибки
- ✗Использовать наивную двойную рекурсию — она экспоненциальна O(2^n), а не O(n)
- ✗Выделять массив всех n значений, тратя O(n) памяти, когда хватает O(1)
- ✗Ошибка на единицу в цикле, из-за которой
Fib(0)илиFib(1)даёт неверное начало
Уточняющие вопросы
- →Почему наивная рекурсия экспоненциальна и как мемоизация это исправляет?
- →При каком
nFibпереполняетlong?
JuniorКодЧастоПроверка строки на палиндром за O(n), игнорируя регистр и не-буквы
Проверка строки на палиндром за O(n), игнорируя регистр и не-буквы
Два указателя l = 0 и r = s.Length - 1, идущие к центру. Пропускайте любой символ, где char.IsLetter ложно, с любой стороны, затем сравнивайте через char.ToLower; несовпадение возвращает false. Встреча в центре возвращает true. O(n) по времени, O(1) дополнительной памяти.
Типичные ошибки
- ✗Строить очищенную/развёрнутую копию, что стоит O(n) памяти вместо O(1)
- ✗Сравнивать символы без приведения регистра через
char.ToLower - ✗Забыть пропускать не-буквы с ОБЕИХ сторон перед каждым сравнением
Уточняющие вопросы
- →Как заодно учитывать цифры как значимые символы?
- →Почему пропуск не-букв внутри цикла сохраняет общую сложность O(n)?
MiddleКодЧастоУдалить дубликаты из массива, сохранив порядок первого появления, за O(n)
Удалить дубликаты из массива, сохранив порядок первого появления, за O(n)
Пройдите nums один раз с HashSet<int> seen и List<int> result. Для каждого значения seen.Add(n) возвращает false, если оно уже есть — пропускаем; при true добавляем в result. Верните result.ToArray(). Множество даёт O(1) проверку, поэтому весь проход — O(n), а порядок сохраняется.
Типичные ошибки
- ✗Сортировать сначала, разрушая требуемый порядок первого появления
- ✗Проверять вхождение вложенным циклом, делая это O(n²) вместо O(n)
- ✗Возвращать
set.ToArray()напрямую, что не гарантирует порядок вставки
Уточняющие вопросы
- →Почему возврат bool из
HashSet.Addэкономит отдельный вызовContains? - →Как дедуплицировать поток, который не помещается в память?
JuniorКодИногдаВычислить n! рекурсией, помня про переполнение
Вычислить n! рекурсией, помня про переполнение
Рекурсия: базовый случай n <= 1 возвращает 1 (покрывает 0 и 1), иначе n * Factorial(n - 1). Приведите к long, чтобы произведение расширялось рано. Поскольку 21! переполняет long, оберните умножение в checked, чтобы бросить исключение, а не тихо переполниться. O(n) вызовов.
Типичные ошибки
- ✗Возвращать
0в базовом случае вместо1, обнуляя всё произведение - ✗Считать в
int, так что произведение переполняется задолго до пределаlong - ✗Полагать, что
longне переполняется —21!уже переполняет, тихо безchecked
Уточняющие вопросы
- →При каком
nFactorialпереполняетlongи какBigIntegerэто меняет? - →Как переписать это итеративно, чтобы избежать глубокой рекурсии?
MiddleКодРедкоПоменять местами два элемента массива без временной переменной
Поменять местами два элемента массива без временной переменной
Кортежный обмен: (a[i], a[j]) = (a[j], a[i]). Правая часть вычисляется полностью до присваиваний, поэтому оба элемента меняются безопасно — даже при i == j, где просто перезаписывается то же значение. Не нужна временная переменная, и нет арифметического/XOR-трюка, обнуляющего элемент при самообмене.
Типичные ошибки
- ✗Использовать XOR или сложение/вычитание, обнуляющие элемент при
i == j - ✗Считать арифметический обмен безопасным — он может переполнить
intна больших значениях - ✗Протаскивать две локальные копии — это просто переименованная временная переменная
Уточняющие вопросы
- →Почему именно XOR-обмен обнуляет элемент при
i == j? - →Как кортежный обмен вычисляет правую часть до присваивания?
