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.

Код на gist:

Задача

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

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

Задача

Рішення

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.

С-рядок – масив/послідовність символів що закінчується символом з кодом 0.

void reverse(char*str) 
{ 
    char* end = str; 
    char tmp; 
    if (str) 
    { 
        while (*end++); 
        --end; 
        while (str < end) 
        { 
            tmp =*str; 
            *str++=*end; 
            *end--= tmp; 
        } 
    } 
}

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

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