Задание 1 Скобки



Задача кодирования в квадратных скобках — Обучение кодированию — Codility
Строка S, состоящая из N символов, считается правильно вложенной, если выполняется любое из следующих условий: S…app.codility.com



Решение:

Это простая задача для использования контейнера стека. Никаких хитростей нет. На самом деле это простейший парсер на основе конечного автомата. Все остальные подобные парсеры, даже очень сложные парсеры для языков программирования, выглядят так. Идея проста. Мы читаем символы один за другим и помещаем их в переменную, содержащую состояние нашего конечного автомата — «c». Конечный автомат переключает свое состояние на основе этих данных. Это приводит к запуску кода, соответствующего этому состоянию. Код обрабатывает состояние, а затем мы читаем следующий символ, который переключает машину в другое состояние.

Для решения этой задачи нам нужно найти закрывающую скобку для каждой открывающей скобки. Наиболее естественным контейнером для этой задачи является стек, потому что скобки могут быть вложены одна в другую. Итак, мы помещаем в стек половину скобок (открывающие скобки) и каждый раз, когда встречаем закрывающую скобку в правильно вложенной строке, удаляем из стека закрывающую скобку, соответствующую этой. Если тип скобок не тот или стек пуст, это означает, что скобки в строке не вложены должным образом. В этом случае мы должны вернуть ошибку.

В С++ это выглядит так:

int check_brackets(const std::string &s) {
    if (s.empty()) { return 1; }

    auto s_len = s.length();

    if (s_len % 2) { return 0; }//the length cannot be an odd number

    std::stack<char> stack;

    auto no_pair = [&stack](char c) {
        if (stack.empty() || stack.top() != c) {
            return true;
        }
        stack.pop();
        return false;
    };

    for (auto c: s) {
        switch (c) {
            case ')':
                if (no_pair('(')) { return 0; }
                break;
            case ']':
                if (no_pair('[')) { return 0; }
                break;
            case '}':
                if (no_pair('{')) { return 0; }
                break;
            default:
                stack.push(c);
        }
    }
    return stack.empty() ? 1 : 0;
}

Задание 2 Рыба



Задание по кодированию рыбы — Учиться программировать — Codility
Вам дано два непустых массива A и B, состоящих из N целых чисел. Массивы A и B представляют N прожорливых рыб в…app.codility.com



Решение:

На самом деле у нас есть два вида рыб, которые движутся навстречу друг другу. Итак, мы должны просканировать течение, найти рыбу, которая движется вниз по течению, и сравнить их с рыбой, которая движется вверх по течению. Лучшей емкостью для сбора рыбы вниз по течению является стог, потому что, когда мы будем брать рыбу из стога для сравнения, она будет направлена ​​в противоположную сторону от рыбы вверх по течению.

Задача аналогична предыдущей. У нас есть два вида рыбы вместо трех видов скобок. Нам нужно сравнить эти виды и оставить только те, которые соответствуют заданным критериям.

В С++ это выглядит так:

int fish_stream(const vector<int> &fish, const vector<int> &directions) {
    const auto UPSTREAM = 0;
    int left = 0, fish_num = fish.size();
    std::stack<int> stack;
    // scan the stream
    for(int i = 0; i < fish_num; ++i) {
        // if fish moves upstream
        if(UPSTREAM == directions[i]) {
            // compare it with downstream fish in front of it and remove
            // from the stack all fish less than our one 
            // because they are eaten
            while(!stack.empty() && (stack.top() < fish[i])) {
                stack.pop();
            }
            // if we have no opposite fish which moves downstream 
            // just count our fish and leave it in the stream.
            if(stack.empty()) {
                left++;
            }
        }
        // if fish moves downstream add it to the stack
        else {
            stack.push(fish[i]);
        }
    }
    return left + stack.size();
}

Задание 3 Вложенность



Вложенная задача кодирования — Learn to Code — Codility
Строка S, состоящая из N символов, называется правильно вложенной, если: S пуста; S имеет форму «(U), где U — это…app.codility.com»



Решение:

Эта задача настолько проста, что решению даже не нужен стек для сравнения открывающих и закрывающих скобок. Достаточно посчитать их количество и убедиться, что количество открывающих скобок совпадает с количеством закрывающих скобок.

int check_nested(const string& s) {
    if (s.empty()) { return 1; }
    //the length cannot be an odd number
    if (s.length() % 2) { return 0; }
    int left_brackets = 0;
    for(auto c: s) {
        if(c == '(') {
            left_brackets ++;
        }
        else if(left_brackets > 0) {
            left_brackets --;
        }
        else {
            return 0;
        }
    }
    return left_brackets ? 0 : 1;
}

Задание 4 Каменная стена



Задание по кодированию StoneWall — Learn to Code — Codility
Вы собираетесь построить каменную стену. Стена должна быть прямой и иметь длину N метров, а ее толщина должна быть…app.codility.com



Решение:

Задача состоит в том, чтобы построить «линию горизонта Манхэттена», используя минимальное количество прямоугольных блоков.

Проще говоря, нам нужно покрыть заданную фигуру минимальным количеством прямоугольников. Эта фигура выглядит как линия горизонта большого города с его небоскребами, поэтому эта задача называется «проблема горизонта Манхэттена».

Абстрактный алгоритм:

  • разбить каждый элемент массива на подблоки для хранения в стеке
  • для каждого последующего элемента массива проверяйте, есть ли в стеке существующие блоки, которые могут его создать.
  • добавлять новый блок в стек только в том случае, если невозможно повторно использовать подблоки из стека

Пример

[8, 8, 5, 7, 9, 8, 7, 4, 8] будут разбиты на следующие 7 уникальных блоков:

(0,8) //8

(0,8) //8

(0,5) //5 (после очистки стека)

(0,5), (5,7) //7

(0,5), (5,7), (7,9) //9

(0,5), (5,7), (7,8) //8 (после извлечения стека)

(0,5), (5,7) //7 (после извлечения из стека)

(0,4) // 4 (после очистки стека)

(0,4), (4,8) //8

Решение на C++ выглядит так:

int stone_wall(const vector<int> &v) {
    std::stack<int> stack;
    int stones = 0;
    for (auto height : v) {
        while (!stack.empty() && stack.top() > height) {
            stack.pop();
        }
        if (!stack.empty() && stack.top() == height) {
            continue;
        }
        stones++;
        stack.push(height);
    }
    return stones;
}

Это решение сканирует линию горизонта слева направо. Он хранит в стеке последовательность горизонтальных ребер, так что их высота образует возрастающую последовательность. Всякий раз, когда вершина пройдена, она устраняется путем создания каменных блоков, которые ее покрывают. Каждое горизонтальное ребро может быть помещено в стек и извлечено из стека один раз. Следовательно, временная сложность этого решения равна O(N).

То же решение в Python:

def solution(H):
    block_cnt = 0
    stack = []
    for height in H:
        # remove all blocks that are bigger than my height
        while len(stack) != 0 and stack[-1] > height:
            stack.pop()
        if len(stack) != 0 and stack[-1] == height:
            # we already paid for this size
            pass
        else:
            # new block is required, push it's size to the stack
            block_cnt += 1
            stack.append(height)
return block_cnt

Вот описание решения этой задачи с сайта Codility, которое было удалено оттуда в 2012 году. Может кому-то это добавит понимания:

Эта задача является вариантом задачи, известной как задача о прямолинейном горизонте или задача о горизонте Манхэттена, в которой задана линия горизонта города, причем каждое здание составляет прямоугольник для линия горизонта, и возникает вопрос: какое минимальное количество зданий требуется для создания данной линии горизонта? Горизонт соответствует форме стены, а здания соответствуют каменным блокам.

На первый взгляд проблемы кажутся разными. С одной стороны, здания должны стоять на земле, а соответствующие им прямоугольники могут перекрываться. С другой стороны, каменные блоки не могут перекрываться, но один блок может быть помещен поверх другого. Однако, как мы увидим, обе проблемы можно решить одним и тем же методом.

Интуиция подсказывает нам, что, удлиняя каждый каменный блок до земли, мы получаем набор зданий, образующих заданный горизонт. Обратное наблюдение менее очевидно.

Количество каменных блоков (или зданий) не больше, чем количество горизонтальных ребер, которые находятся над землей на линии горизонта. Просто для каждого такого ребра мы можем поставить отдельное здание, или каменный блок, стоящий на земле. Чтобы использовать меньше каменных блоков, один каменный блок должен примыкать к нескольким горизонтальным краям линии горизонта. Когда это возможно? Ясно, что если два горизонтальных ребра примыкают к одному и тому же каменному блоку, то они должны быть одной высоты. Более того, каменная стена между двумя ребрами не может быть ниже ребер. Оказывается, этих двух условий достаточно.

Пик, показанный на рисунке выше, должен быть сделан из цельного каменного блока. Но какой высоты должен быть этот каменный блок? Оказывается, сделать его нижний край на одном уровне с верхним из двух соседних горизонтальных краев — это всегда хороший выбор. Используя такую ​​жадную стратегию, любые два горизонтальных ребра линии горизонта, удовлетворяющие указанным выше условиям, примыкают к одному и тому же каменному блоку. Применение этой жадной стратегии к данным примера дает следующее решение:

Если вам интересна эта тема, есть сильно оптимизированное, но более сложное решение этой проблемы. Вы можете прочитать об этом здесь: https://www.researchgate.net/publication/221049934_A_Skyline-Based_Heuristic_for_the_2D_Rectangular_Strip_Packing_Problem

Вернитесь к оглавлению.