Задача

Що буде виведено на екран в результаті виконання наступної програми,

char *c[]={
    "ENTER",
    "NEW",
    "POINT",
    "FIRST"

};
  
char **cp[]={c+3,c+2,c+1,c};
  
char ***cpp=cp;
  
main()

{
    printf("%s",**++cpp);
    printf("%s ",*--*++cpp+3);
    printf("%s",*cpp[-2]+3);
    printf("%sn",cpp[-1][-1]+1);

}

Рішення

Насправді не все так складно, спробуємо помалювати стрілочки.

Отже після ініціалізації усих змінних маємо приблизно таку картину:

Тепер дивимося що станеться в процесі виконання printf(“%s”,**++cpp): срр пересунеться на елемент [1], а після розіменування отримаємо рядок POINT:

При виконанні printf(“%s “,*–*++cpp+3) срр знову пересунеться на наступний елемент, далі вказівник на NEW на який тепер вказує cpp буде пересунуто на попередній елемент (ENTER), після чого буде виведено рядок починаючи з 3-го елемента. Отже матимемо тепер на екрані POINTER_:

Рядок printf(“%s”,*cpp[-2]+3) – відступаємо на 2 елементи назад від тієї позиції що на неї вказує cpp, розіменовуємо (маємо рядок FIRST) і виводимо текст з 3-го символа. Отже маємо PONTER ST:

Для printf(“%sn”,cpp[-1][-1]+1) відступаємо від поточної позиції cpp на одну назад (вказуємо на рядок POINT), відступаємо на рядок від нього назад (вказуємо на NEW), і виводимо з 1-го символа.

Отже остаточний рядок буде POINTER STEW.

Задача

Написати функцію яка приймає два відсортовані масиви цілих чисел з унікальними значеннями і знайти k-тий по порядку елемент.

Зробити це треба швидше ніж за лінійний час.

Рішення

Якщо просто мати по індексу на масив і пересувати їх на найменший елемент то усього нам знадобиться k ітерацій.

Так само якщо ми спробуємо злити масиви то не вдасться зробити це швидше ніж за лінійнипй час.

Якщо ж скористатися бінарним пошуком то загальна складність становитиме O(lg M + lg N), де M та N розміри вхідних масивів.

Робимо ми це так:

  1. будуємо індекси i та j такі що i + j == k – 1. Наприклад ділимо відрізки навпіл.
  2. якщо B[j-1] < A[i] < B[j] то A[j] є результатом пошуку
  3. якщо A[i-1] < B[j] < A[i] то результатом буде B[j]
  4. модифікуємо індекси таким чином:
    1. якщо A[i] < B[j] то:
      1. якщо B[j] є останнім елементом у массиві то значення яке ми шукаємо знаходиться в A
      2. інакше пересуваємо j на половину масиву вліво, і рівно на стільки ж позицій пересуваємо i (для того щоб їх сума дорівнювала k)
    2. Робимо схожі перевірки:
      1. якщо A[i] є останнім елементом у массиві то значення яке ми шукаємо знаходиться в B
      2. інакше пересуваємо i на половину масиву вліво, і рівно на стільки ж позицій пересуваємо j
  5. повертаємося до кроку 2.
int findKthSmallest(int *a, int m, int *b, int n, int k) { if (m < 0 || n < 0 || k < 0 || k >= m + n) return -1; if (k == 0) return min(a[0], b[0]); if (k == m + n - 1) return max(a[m - 1], b[n - 1]); for (int i = min(k /2, m - 1), j = k - i; ; ) { int ai = i >= m ? INT_MAX : a[i]; int ai_1 = i <= 0 ? INT_MIN : (i > m ? a[m - 1] : a[i - 1]); int bj = j >= n ? INT_MAX : b[j]; int bj_1 = j <= 0 ? INT_MIN : (j > n ? b[n - 1] : b[j - 1]); if (bj_1 < ai && ai < bj) return ai; if (ai_1 < bj && bj < ai) return bj; int x; if (bj < ai) { if (j == n - 1) { return a[k - j - 1]; } x = i; i /= 2; j += x - 1; } else // a[i] < b[j] { if (i == m - 1) { return b[k - i -1]; } x = j; j /= 2; i += x - j; } } }

Задача

Дано масив цілих чисел. Треба знайти підмасив елементів з найбільшою сумою – тобто знайти і суму і індекси.

Додаткове зауваження. В принципі це доволі відома задача і в мережі можна знайти безліч рішень для неї, наприклад – http://sites.google.com/site/computationalthinking/kadanealgorithm, або http://www.algorithmist.com/index.php/Kadane’s_Algorithm. Але є одна річ на яку треба звернути увагу – усі елементи вхідного масиву можуть бути від’ємними. А цього якраз усі ті наведені реалізації і не враховують.

Тобто треба не лише в масиві { 10, –1, –1, 18, –20, 30 } знайти виділений підмасив, але і в такому як  { –8, –2, –10 } знайти підмасив з одного елемента (-2).

Рішення

void find_the_biggest_subarray( int *a, size_t n, long int &sum, size_t &start, size_t &end) { sum = LONG_MIN; size_t curStart = start = end = 0; if (!a || n == 0) return; long curSum = sum = a[0]; for (size_t i = 1; i < n; ++i) { if (curSum < 0 && a[i] > curSum) { curSum = a[i]; curStart = i; } else { curSum += a[i]; } if (curSum > sum) { sum = curSum; start = curStart; end = i; } } }

Задача

У масиві з N елементів присутні усі елементи від 1 до N, але один з них продубльовано. Треба знайти цей елемент за лінійний час без використання додаткової пам’яті.

Рішення

Рішення полягає в тому щоб кожен елемент помістити в ту позицію в масиві яка дорівнює його значенню. Як тільки знайдемо елемент позиція якого вже зайнята таким самим значенням ми знайшли дублікат.

Для кожного елемента масиву з індексом і виконаємо наступні дії:

  1. Беремо поточний елемент x = a[i]
  2. Якщо x == i то збільшити і та повернитуся до кроку 1.
  3. Якщо  a[x] == x то ми знайшли елемент який дублюється, інакше обміняти місцями значення a[i] та a[x] і повернутися до кроку і.
int find_duplicated_item(int*a, size_t n) 
{ 
    int result =-1, x =0; 
    for (size_t i =0; i < n; ) 
    { 
        if (a[i] != i +1) 
        { 
            x = a[i]; 
            
            if (a[x] == x) 
            { 
                result = x; 
                break; 
            } 
            
            a[i] = a[x]; 
            a[x] = x; 
        } 
        else ++i; 
    } 
}

Задача

У текстовому рядку вказано шлях до файлу чи директорії. В ньому можуть також зустрічатися дві крапки що позначають директорію на один рівень вгору. Треба прибати усі комбінації з двох крапок так щоб “/dir1/dir3” та “/dir1/dir2/../dir3/” стали ідентичними.

Рішення

Маабуть найпростішим буде рішення з вказівниками для читання та запису. Пересуваємо вказівник для читання доки не знайдемо послідовність “/../”. Далі пересуваємося від знайденої послідовності назад до першого попереднього символу “/” – це буде вказівник для запису.

Потім копіюємо рядок починаючи з позиції (вказвіник для читання + 3) у позицію (вказівник для запису). Після копіювання читання треба продовжити з тієї позиції в яку почали записувати (на випадок якщо у рядку є послідовності з більше ніж двох “..” послідовно).

int remove_double_dots(char *s) { for (char *r = s; *r;) { if (r[0] == '/' && r[1] == '.' && r[2] == '.' && (r[3] == '/' || r[3] == '')) { char *w = r - 1; for (; w >= s && *w != '/'; --w); if (w < s) return -1; char *p = w; r += 3; while (*w++ = *r++); r = p; } else { ++r; } } return 0; }

У такого рішення є недолік – частини рядку постійно копіюються і при великій кількості “..” цей алгоритм буде неефективним.

Для покращення ми можемо зробити наступне. Кожного разу коли знаходимо у рядку символ “/” за яким йде звичайна директорія додаємо адресу цієї піддиректорії у спеціальний масив. Коли ж знаходимо послідовність “/../” то вилучаємо з масиву останній елемент і пропускаємо знайдену послідовність. Таким чином ми знаходимо адреси усих піддиректорій за один прохід.

Далі треба послідовно скопіювати усі піддиректорії з масиву у результуючий рядок.

int remove_double_dots_with_stack(char *s) { size_t slashes = 0; for (char *p = s; *p; ++p) { if (*p == '/') ++slashes; } if (slashes == 0) return 0; std::vector<char*> words(slashes + 1); size_t word = 0; for (char *p = s; *p; ) { if (*p == '/') { if (p[1] == '.' && p[2] == '.' && (p[3] == '/' || p[3] == '')) { if (word > 0) { --word; p += 3; } else { return -1; } } else { words[word++] = ++p; } } else { ++p; } } char *w = s; for (size_t i = 0; i < word; ++i) { *w++ = '/'; for (char *p = words[i]; *p && *p != '/'; ++p) { *w++ = *p; } } *w = ''; return 0; }

Задача

Треба визначити для двох рядків чи є один з них результатом циклічного зсуву символів іншого рядка.

Рішення

Якщо додати до першого рядка його копію то другий рядок має бути підрядком сумарного рядка, якщо звісно це ті ж самі рядки.

 
bool IsRotation(char *s1, char *s2)
{
    bool result = false;
    int l1 = strlen(s1), l2 = strlen(s2);
    if (l1 == l2 && l1 > 0)
    {
        char *s = new char[l1 * 2 + 1];

        strcpy(s, s1); // concat strings
        strcpy(s + l1, s1)

        result = strstr(s, s2) != NULL;
        delete []s;
    }

    return result;
}

Задача

Для масиву розміром MxN якщо будь-який елемент дорівнює 0 встановити всі елементи його рядка і колонки в 0.

Рішення

Головна проблема полягає в тому щоб при встановленні елементів у 0 не враховувати їх при подальшому пошуку. Інакше змінені елементи будуть можуть бути просканованим пізніше і призведуть до встановлення в 0 нових елементів.
Найпростішим рішенням буде створити копію матриці в якій і міняти елементи, а сканування проводити лише на оригінальній матриці.
Але насправді немає необхідності  у всих MxN елементах – нам достатньо лише знати в яких рядках та стовпцях зустрівся хоча б один 0.
    1. void SetZeroes(int* a, int n, int m)
    2. {
    3.     int *row = new int[m];
    4.     int *col = new int[n];
    5.     // scan elements
    6.     for (int i = 0; i < n; ++i)
    7.     {
    8.         for (int j = 0; j < m; ++j)
    9.         {
    10.             if (a[i][j] == 0)
    11.             {
    12.                 row[i] = 1;
    13.                 col[j] = 1;
    14.             }
    15.         }
    16.     }
    17.     // set elements
    18.     for (int i = 0; i < n; ++i)
    19.     {
    20.         for (int j = 0; j < m; ++j)
    21.         {
    22.             if (row[i] == 1 || col[j] == 1)
    23.             {
    24.                 a[i][j] = 0;
    25.             }
    26.         }
    27.     }
    28.     delete [] row;
    29.     delete [] col;
    30. }

* This source code was highlighted with Source Code Highlighter.

Без використання додаткової пам’яті

Починаючи з другого символу для кожного з них перевіряємо чи є такий символ в перевіреному вже рядку. Спочатку в перевіреному рядку лише 1 символ який гарантовано є унікальним.

1 void removeDuplicates(char *str) 2 { 3 int len = strlen(str); 4 if (len < 2) return; 5 6 int tail = 1; 7 for (int i = 1; i < len; ++i) 8 { 9 for (int j = 0; j < tail; ++j) 10 { 11 if (str[i] == str[j]) break; 12 } 13 14 if (j == tail) 15 { 16 str[tail++] = str[i]; 17 } 18 } 19 20 str[tail] = 0; 21 }

З використанням додаткової пам’яті

Просто підраховуємо кількість входжень кожного символу в рядок.

1 void removeDuplicates(char *str) 2 { 3 int len = strlen(str); 4 if (len < 2) return; 5 6 bool hit[256] = { false }; 7 hit[str[0]] = true; 8 9 int tail = 1; 10 for (int i = 1; i < len; ++i) 11 { 12 if (!hit[str[i]]) 13 { 14 hit[str[i]] = true; 15 str[tail++] = str[i]; 16 } 17 } 18 19 str[tail] = 0; 20 }