Category Archives

9 Articles
Posted by Oleksandr Golovatyi on

Вказівники, індексування та приорітет операцій

Задача

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

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.

Posted by Oleksandr Golovatyi on

Знайти k-тий по порядку елемент у двох відсортованих масивах

Задача

Написати функцію яка приймає два відсортовані масиви цілих чисел з унікальними значеннями і знайти 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;
        }
    }
}

Posted by Oleksandr Golovatyi on

Знайти підмасив з найбільшою сумою елементів

Задача

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

Додаткове зауваження. В принципі це доволі відома задача і в мережі можна знайти безліч рішень для неї, наприклад – 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;
        }
    }
}

Posted by Oleksandr Golovatyi on

Знайти елемент що повторюється у масиві унікальних значень

Задача

У масиві з 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; 
    } 
}
Posted by Oleksandr Golovatyi on

Нормалізувати рядок зі шляхом

Задача

У текстовому рядку вказано шлях до файлу чи директорії. В ньому можуть також зустрічатися дві крапки що позначають директорію на один рівень вгору. Треба прибати усі комбінації з двох крапок так щоб “/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;
}

Posted by Oleksandr Golovatyi on

Чи є один рядок здвинутим іншим рядком

Задача

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

Рішення

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

 
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;
}
Posted by Oleksandr Golovatyi on

Встановлення колонок і рядків в 0

Задача

Для масиву розміром 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];
    6.     // scan elements
    7.     for (int i = 0; i < n; ++i)
    8.     {
    9.         for (int j = 0; j < m; ++j)
    10.         {
    11.             if (a[i][j] == 0)
    12.             {
    13.                 row[i] = 1;
    14.                 col[j] = 1;
    15.             }
    16.         }
    17.     }
    19.     // set elements
    20.     for (int i = 0; i < n; ++i)
    21.     {
    22.         for (int j = 0; j < m; ++j)
    23.         {
    24.             if (row[i] == 1 || col[j] == 1)
    25.             {
    26.                 a[i][j] = 0;
    27.             }
    28.         }
    29.     }
    31.     delete [] row;
    32.     delete [] col;
    33. }


* This source code was highlighted with Source Code Highlighter.


    
    





    












    

    



    Posted by  Oleksandr Golovatyi on  


    




	
    
        Як прибрати символи-дублікати з С-рядка

    
    




    
    




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


Починаючи з другого символу для кожного з них перевіряємо чи є такий символ в перевіреному вже рядку. Спочатку в перевіреному рядку лише 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 }