Задачи из книги Г. Лакман Макдауэлл «Карьера программиста»

Реализация выполнена на С99.

1 Массивы и строки

1. Реализуйте алгоритм, определяющий, все ли символы в строке встречаются один раз.

Если изменение строки разрешено, ее можно отсортировать (например, быстрой сортировкой O(n*logn)), а затем последовательно сравнить соседние элементы (O(n)).

Решение задачи потребует дополнительной памяти для хранения отметок элементов, встречавшихся в строке. Объем этой памяти зависит от количества уникальных символов алфавита, использованного в строке. Если их меньше 32 (например, только буквы a-z), то достаточно использовать один int (4*8 бит).

#include <string.h>

int is_unique_chars(const char *s)
{
    if (strlen(s) > 256) return 0; 

    int check = 0;

    for (int i = 0; i < strlen(s); i++) {
        int val = s[i] - 'a';
        if ( (check & (1 << val)) > 0 )
            return 0;
        check |= (1 << val);
    }
    return 1;
}

Если алфавит более обширен, то понадобится массив. 256 -- максимальное количество уникальных символов, помещающихся в char. Если для символов использован более "широкий" тип, то уникальных символов будет больше, однако принцип построения решения не изменится.

2. Реализуйте функцию void reverse(char* str) на С или C++. Функция должна циклически сдвигать строку, заканчивающуюся символом null.

#include <string.h>

void reverse(char *s)
{
    for (int i = 0, j = strlen(s)-1; i < j; i++, j--) {
        int c = s[i];
        s[i] = s[j];
        s[j] = c;
    }
}

3. Для двух строк напишите метод, определяющий, является ли одна строка перестановкой другой.

4. Напишите метод, заменяющий все пробелы в строке символами '%20'. Можно предположить, что длина строки позволяет сохранить дополнительные символы и «истинная» длина строки известна.

Пример:
Ввод: "Mr John Smith"
Вывод: "Mr%20John%20Smith"

5. Реализуйте метод, осуществляющий сжатие строки, на основе счетчика повторяющихся символов. Например, строка aabcccccaaa должна превратиться в а2b1с5а3. Если «сжатая» строка оказывается длиннее исходной, метод должен вернуть исходную строку.

6. Дано: изображение в виде матрицы размером NxN, где каждый пиксель занимает 4 байта. Напишите метод, поворачивающий изображение на 90°.

7. Напишите алгоритм, реализующий следующее условие: если элемент матрицы в точке МхN равен 0, то весь столбец и вся строка обнуляются.

8. Допустим, что существует метод isSubstring, проверяющий, является ли одно слово подстрокой другого. Для двух строк, s1 и s2, напишите код проверки, получена ли строка s2 циклическим сдвигом s1, используя только один вызов метода isSubstring

Пример: слово waterbottle получено циклическим сдвигом erbottlewat.