ARCHANGEL's blog

ARCHANGEL

Посетитель
Мудрец
Сообщения
16
Реакции
432
Привет, буду здесь делиться своими успехами (или не очень) в освоении олимпиадного программирования и решении задач.

Первая задача - поиск двух чисел, сумма которых известна. Решение за О ( n ). Условие: дан массив уникальных числе типа integer. И дана сумма двух чисел S - тоже int. Предполагается, что в массиве есть такая пара, сумма которых равна наперёд заданному значению S. Найти эти два числа и вывести их в любом порядке.

Решение сводится к созданию хеш-таблицы, куда складываются числа при проходе по массиву. Один проход приходится сделать по-любому, потому и получается сложность O( n ). При проходе по массиву из S вычитается значение текущего элемента, и полученная разность ищется в хеш-таблице. Если разность там уже есть, то возвращается текущий элемент и эта разность. Если нет, то текущий элемент заносится в хэш-таблицу:

Solution:
#include <algorithm>
#include <vector>
#include <unordered_set>
using namespace std;

vector<int> twoNumberSum(vector<int> array, int targetSum)
{
  std::unordered_set<int> table;
 
   try{
   std::for_each(array.cbegin(), array.cend(),[&table, targetSum]
                        (int element)
                        {
                           const auto y = targetSum - element;
                           const auto iter = table.find(y);
                           if (iter != table.cend())
                           {
                              throw std::vector<int>{element, y};
                           }
                           table.insert(element);
                        });
   }
   catch (const std::vector<int>& result)
   {
      return result;
   }
  return {};
}
Сообщение объединено:

Аналогичная предыдущей, но немного более сложная задача - поиск трёх чисел, сумма которых задана. По сравнению с предыдущей задаче есть различия в условии - нужно вывести всё триплеты (три числа, которые при сложении дают заданную сумму) в отсортированном порядке (с отсортированными элементами внутри триплета). Решается за O ( n * n ). Подход отличается от предыдущего решения, так как здесь не используются хеш-таблицы. Используется в текущей реализации тот факт, что можно эффективно отсортировать массив "на месте" (без дополнительной памяти), потом один раз пройтись по отсортированному массиву и для каждого элемента искать ещё два недостающих. Причём поиск этот специфический - начинается от крайнего левого и крайнего правого элементов, и если сумма меньше нужного значения, то её (сумму) надо увеличивать. Потому делается сдвиг вправо для крайнего левого элемента. Если же сумма больше - до сдвигается влево крайний правый:

Solution:
#include <algorithm>
#include <vector>
using namespace std;

vector<vector<int>> threeNumberSum(vector<int> array, int targetSum)
{
  std::sort(array.begin(), array.end());
    vector<vector<int>> result;
    
    for (auto it = array.cbegin(); it != array.cend() - 2; ++it)
    {
        auto left = it + 1;
        auto right = array.cend() - 1;
        while (left < right)
        {
            const auto checkSum = *it + *left + *right;
            if (checkSum == targetSum)
            {
                result.push_back({*it, *left, *right});
                ++left;
                --right;
            }
            else if (checkSum > targetSum)
            {
                --right;
            }
            else if (checkSum < targetSum)
            {
                ++left;
            }
        }
    }
    
  return result;
}
Сообщение объединено:

Следующая задача - проверка вхождения всех элементов последовательности в бОльшую последовательность. Например, у нас есть последовательность а [1,2,4,5], и есть бОльшая последовательность b [1,2,3,4,5]. Так вот a входит в b, потому как все элементы из b есть в a, и порядок элементов сохранён. Решается "в лоб" за O ( n ). Делается проход по b, и текущий элемент сравнивается с первым из a. Если совпали, то увеличиваются индексы для обеих последовательностей, если нет - только для b. И так, пока не обойдём хотя бы одну из последовательностей:

Solution:
using namespace std;

bool isValidSubsequence(vector<int> array, vector<int> sequence)
{
  auto it = sequence.cbegin();

    for (auto itArray = array.cbegin(); itArray != array.cend(); ++itArray)
    {
        if (it == sequence.cend())
        {
            return true;
        }
        
        if (*itArray == *it)
        {
            ++it;
        }
    }
    
    return it == sequence.cend();
}
 
Последнее редактирование:

ARCHANGEL

Посетитель
Мудрец
Сообщения
16
Реакции
432
Следующая задача - поиск в BST (Binary Search Tree) элемента, максимально близкого по значению к заданному. Иными словами - у нас есть дерево (о его балансировке предварительно ничего неизвестно), узел которого представлен значением и двумя указателями на левое и правое поддерево. И есть искомый элемент, который в самом дереве может и не встречаться. Нужно найти элемент, максимально близкий к заданному по значению (из имеющихся в дереве) и вывести.

При решении следует учесть 3 случая:
1. В дереве вообще нет элементов. Тогда выводим -1.
2. В дереве только один элемент. Тогда автоматически - ближайший.
3. В дереве больше 1 элемента, и нужен итеративный обход его поддеревьев.

"Расстояние" или "похожесть" элементов вычисляется на основании модуля разности (абсолютному значению).
Сложность O( log n) в среднем случае, и O ( n ) - в худшем (при несбалансированном дереве), по памяти итеративный алгоритм имеет сложность O ( 1 ).

Solution:
class BST {
public:
  int value;
  BST *left;
  BST *right;

  BST(int val);
  BST &insert(int val);
};

template <typename T>
T abs(T value)
{
    return (value < 0) ? -value : value;
}

int findClosestValueInBst(BST *tree, int target)
{
    if (!tree)
        return -1;

    int closest = tree->value;
    int difference = abs(closest - target);
    auto* current = tree;
  
    while (current)
    {
        const int diff = abs(current->value - target);
        if (diff < difference)
        {
            difference = diff;
            closest = current->value;
        }
      
        if (current->value > target)
        {
            current = current->left;
        }
        else if (current->value < target)
        {
            current = current->right;
        }
        else
        {
            return current->value;
        }
    }
  
    return closest;
}
 
Последнее редактирование:

ARCHANGEL

Посетитель
Мудрец
Сообщения
16
Реакции
432
Задача, позволяющая более подробно изучить BST (Binary search tree). Нужно реализовать три метода: insert, contains и remove. Методы имеют такие сигнатуры:
signatures:
BST& insert(int val);
bool contains(int val);
BST& remove(int val);
Дерево поиска имеет следующую структуру (справа - все элементы, которые больше либо равны текущему, слева - меньшие):
BST:
class BST {
public:
    int value;
    BST* left;
    BST* right;

    BST(int val) {
        value = val;
        left = NULL;
        right = NULL;
    }
};
Нужно добавить в класс недостающие методы и имплементацию. Перед началом решения нужно упомянуть два неочевидных условия.
1. Не бывает пустых деревьев. У любого BST, как минимум, есть заданное значение value.
2. Нельзя удалить вершину из дерева, если она в нём последняя. Тут уже нужно удалять всё дерево.

Начнём с метода insert.
Т.к. дерево упорядочено, мы должны найти правильную позицию для вставки нового элемента. Нам нужно найти такой элемент, к которому мы могли бы добавить дочерний элемент (новый узел с заданным значением - параметром на входе для insert), не нарушая правил упорядочивания элементов в дереве. Начиная от корня, мы сравниваем значение со значением в узле корня. Если значение на входе меньше, то двигаемся влево, иначе - наоборот, вправо. И так, пока не дойдём до пустого указателя. Как дошли - вставляем на эту позицию новый элемент.

insert:
BST& insert(int val)
    {
        BST* current = this;

        while (current)
        {
            if (current->value <= val)
            {
                if (current->right)
                {
                    current = current->right;
                }
                else
                {
                    current->right = new BST(val);
                    break;
                }
            }
            else// if (current->val > value)
            {
                if (current->left)
                {
                    current = current->left;
                }
                else
                {
                    current->left = new BST(val);
                    break;
                }
            }
        }

        return *this;
    }
Теперь - contains.

Принцип здесь такой же, но с той лишь разницей, что нам не нужно размещать в куче новые узла дерева:

contains:
bool contains(int val)
    {
        BST* current = this;

        while (current)
        {
            if (current->value < val)
            {
                current = current->right;
            }
            else if (current->value > val)
            {
                current = current->left;
            }
            else
            {
                return true;
            }
        }

        return false;
    }
Самое сложное - remove.

Удаление - самая трудная часть, потому что имеет много особых случаев. Идея в том, что нам нужно хранить ещё и указатель на родителя (помимо элемента, который мы собираемся удалять), к тому же могут быть случаи, когда родителя нет (если делается удаления корневой вершины), и когда удаляемый узел содержит 1,2 или вообще не содержит дочерних узлов.
remove:
BST& remove(int val, BST* parent = nullptr)
    {
        BST* current = this;

        while (current)
        {
            if (current->value < val)
            {
                parent = current;
                current = current->right;
            }
            else if (current->value > val)
            {
                parent = current;
                current = current->left;
            }
            else
            {
                if (current->left && current->right)
                {
                    current->value = current->right->GetMinValue();
                    current->right->remove(current->value, current);
                }
                else if (!parent)
                {
                    if (current->right)
                    {
                        current->value = current->right->value;
                        current->left = current->right->left;
                        const auto tmp = current->right;
                        current->right = current->right->right;
                        delete tmp;
                    }
                    else if (current->left)
                    {
                        current->value = current->left->value;
                        current->right = current->left->right;
                        const auto tmp = current->left;
                        current->left = current->left->left;
                        delete tmp;
                    }
                    else
                    { }
                }
                else if (parent->left == current)
                {
                    parent->left = (current->left) ? current->left : current->right;
                    delete current;
                }
                else if (parent->right == current)
                {
                    parent->right = (current->left) ? current->left : current->right;
                    delete current;
                }
                break;
            }
        }
        return *this;
    }
 

ARCHANGEL

Посетитель
Мудрец
Сообщения
16
Реакции
432
Ещё одна задача про двоичные деревья. У нас есть двоичное дерево, нужно найти в нём все простые пути от корня до каждого из листьев этого дерева и посчитать сумму значений всех узлов, которые в такой путь попали. Решение делается с помощью рекурсивного обхода графа в глубину. Временная сложность такого алгоритма O ( n ). В этот раз решил добавить main с небольшим тестом - для наглядности:

Solution:
#include <iostream>
#include <vector>
#include <algorithm>


class BinaryTree {
public:
    int value;
    BinaryTree* left;
    BinaryTree* right;

    BinaryTree(int value) {
        this->value = value;
        left = NULL;
        right = NULL;
    }
};

std::vector<int> branchSums(BinaryTree* root)
{
    if (!root)
    {
        return {};
    }

    auto leftValues = branchSums(root->left);
    auto rightValues = branchSums(root->right);

    std::move(rightValues.begin(), rightValues.end(),
        std::back_inserter(leftValues));

    if (leftValues.empty())
    {
        return { root->value };
    }

    for (auto& x : leftValues)
    {
        x += root->value;
    }

    return leftValues;
}

int main()
{
    BinaryTree one(1), two(2), three(3);
    one.left = &two;
    one.right = &three;
    auto x = branchSums(&one);
    for (auto& element: x)
    {
        std::cout << element << std::endl;
    }
    return 0;
}
 

ARCHANGEL

Посетитель
Мудрец
Сообщения
16
Реакции
432
Следующая задача - опять про бинарные деревья. Нужно посчитать сумму расстояний от корня до каждого узла. Расстояние - количество переходов от одной вершины к другой до достижения конечной вершины. Т.е. если мы идём от корня к его левой дочерней вершине, то у левой вершины расстояние будет равно 1. У правой - тоже. У их дочерних вершин - расстояние 2, и т.д. Решается обходом в ширину с сохранением промежуточных расстояний до каждой уже посещённой вершины:

Solution:
using namespace std;
#include <list>

class BinaryTree {
public:
  int value;
  BinaryTree *left;
  BinaryTree *right;

  BinaryTree(int value) {
    this->value = value;
    left = NULL;
    right = NULL;
  }
};

struct Vertex
{
    BinaryTree* tree;
    int distance;
    Vertex(BinaryTree* t, int d):
        tree(t), distance(d)
        { }
};


int nodeDepths(BinaryTree *root)
{
    if (!root)
    {
        return -1;
    }
    
  std::list<Vertex> vertexes;
    vertexes.push_back({root, 0});
    int result = 0;
    
    while (!vertexes.empty())
    {
        const auto current = vertexes.front();
        vertexes.pop_front();
        
        result += current.distance;
        if (current.tree->left)
        {
            vertexes.push_back({current.tree->left, current.distance + 1});
        }
        
        if (current.tree->right)
        {
            vertexes.push_back({current.tree->right, current.distance + 1});
        }
    }
    
  return result;
}
 

ARCHANGEL

Посетитель
Мудрец
Сообщения
16
Реакции
432
На очереди задача про обход дерева в глубину. У нас есть дерево, у каждой вершины этого дерева есть дочерние вершины (их может от 0 до n). Нужно вывести имена всех вершин в порядке их посещения, если известно, что нужно делать обход в глубину, а дочерние узлы обходить слева направо. Идея обхода в глубину - помещать вершину в некий список, и новые вершины для обхода записывать в начало списка (запись в конец - обход в ширину). Сложность O ( n + e ), n - количество вершин, e - количество рёбер.

Solution:
#include <vector>
#include <list>
using namespace std;

// эта шутка будет использована для прогона тестов, потому тут нет main
class Node {
public:
  string name;
  vector<Node *> children;

  Node(string str) { name = str; }

vector<string> depthFirstSearch(vector<string>* array)
    {
        std::list<Node*> visitOrder{ this };

        while (!visitOrder.empty())
        {
            const auto element = visitOrder.front();
            visitOrder.pop_front();

            array->push_back(element->name);
            const auto children = element->children;
            for (auto it = children.crbegin(); it != children.crend(); ++it)
            {
                visitOrder.push_front(*it);
            }
        }

        return *array;
    }

  Node *addChild(string name) {
    Node *child = new Node(name);
    children.push_back(child);
    return this;
  }
};
 

ARCHANGEL

Посетитель
Мудрец
Сообщения
16
Реакции
432
Следующая задача будет про очень известный алгоритм поиска подстроки в строке: Кнута-Морриса-Пратта (КМП). Я очень долго думал, как бы так его описать, но понял, что все попытки выглядят коряво и убого. Потому приведу здесь ссылку на прекрасное описание (лучшее из тех, что я находил): КМП

И приведу здесь ту реализацию, которую я заимплементил после прочтения:

Solution:
bool MyKMP(const std::string& text, const std::string& pattern)
{
    std::vector<size_t> prefix(pattern.length(), 0);

    for (size_t i = 1;i < prefix.size();++i)
    {
        size_t j = prefix[i - 1];
        while (j > 0 && pattern[i] != pattern[j])
        {
            j = prefix[j - 1];
        }

        if (pattern[i] == pattern[j])
        {
            j++;
        }

        prefix[i] = j;
    }

    size_t k = 0;
    for (size_t q = 0;q < text.length();++q)
    {
        while (k > 0 && text[q] != pattern[k])
        {
            k = prefix[k - 1];
        }

        if (text[q] == pattern[k])
        {
            k++;
        }

        if (k == pattern.length())
        {
            return true;
        }
    }

    return false;
}
 

ARCHANGEL

Посетитель
Мудрец
Сообщения
16
Реакции
432
Наша следующая задача - проверка на виладность Binary Search Tree. Как мы знаем, BST обладает свойством, согласно которому все узлы слева от текущего имеют меньшие значения, а справа - больше либо равны. Для проверки мы рекурсивно обходим дерево и проверяем на каждом шаге, соблюдается ли это свойство. Для проверки мы должны хранить допустимые для текущего узла значения минимума и максимума. Для корня они (условно) равны плюс(минус) бесконечности (на практике это максимально возможное значение для int и минимально возможное), и на каждом шаге они корректируются из учёта значений уже пройденных вершин. Сложность O ( n ):

Solution:
#include <limits>

class BST {
public:
  int value;
  BST *left;
  BST *right;

  BST(int val);
  BST &insert(int val);
};

bool ValidateHelper(BST* tree, int min, int max)
{
    if (!tree)
    {
        return true;
    }
    
    if (tree->value < min || tree->value >= max)
    {
        return false;
    }
    
    return ValidateHelper(tree->left, min, tree->value) &&
        ValidateHelper(tree->right, tree->value, max);
}

bool validateBst(BST *tree)
{
   return ValidateHelper(tree, std::numeric_limits<int>::min(),
                                                std::numeric_limits<int>::max());
}
 

ARCHANGEL

Посетитель
Мудрец
Сообщения
16
Реакции
432
В следующей задаче нам дан отсортированный массив int элементов, нужно из него сделать Binary Search Tree минимальной высоты. Решение сводится к взятию середины из диапазона в массиве. Используется приём, который очень применяется при программировании алгоритмов для обхода деревьев. Делается некую вспомогательная функция (helper function), которая вызывается из основной один раз с некоторыми начальными параметрами. Потом внутри себя эта вспомогательная функция вызывается многократно, попутно корректируя параметры, пока не доходит до некоторого условия, являющегося сигналом к завершению рекурсии.

Здесь начальными условиями являются первый и последний элементы массива, по мере обхода мы добавляем элемент из середины диапазона (середины массива), и строим новые диапазоны (слева и справа от середины), куда сама середина уже не входит! Также индексы должны быть знаковыми (int), т.к. в ходе их вычисления может произойти вычитание из нулевого индекса, а проверка окончания рекурсии устроена так, что для границ диапазона левая граница должна быть меньше либо равна правой.

Сложность этого O ( n ):

Solution:
BST* MinHeightBstHelper(std::vector<int>& array, int left, int right,
    BST* node)
{
    if (left <= right)
    {
        const auto middle = (left + right) / 2;
        if (node)
        {
            node->insert(array[middle]);
        }
        else
        {
            node = new BST(array[middle]);
        }

        MinHeightBstHelper(array, left, middle - 1, node);
        MinHeightBstHelper(array, middle + 1, right, node);
    }
    return node;
}

BST* minHeightBst(vector<int> array)
{
    return MinHeightBstHelper(array, 0, array.size() - 1, nullptr);
}
 

ARCHANGEL

Посетитель
Мудрец
Сообщения
16
Реакции
432
Следующая задача - создание структуры данных Binary Heap. Пирамида, она же куча, она же бинарная куча - структура данных, которая хорошо подходит для очередей с приоритетом. Представляет собой практически полное, или просто полное дерево, т.е. все уровни, за исключением последнего, должны быть заполнены. В последнем могут отсутствовать некоторые крайние листья справа.

В зависимости от условия доминирования, пирамида может быть HeapMax или HeapMin. Иными словами, пирамида считается правильной, если выполняется определённое условие доминирования родительских узлов - родитель больше (меньше) своих двух потомков. Больше - HeapMax, меньше - HeapMin.

В интерфейсе такой структуры важными являются методы вставки (Insert), удаления (Remove) и создания пирамиды из неупорядоченного массива. Ещё выделяют такие понятия, как восходящие и нисходящие построения пирамиды. При восходящем методе корректировка условия доминирования делается от корня дерева к листьям, а при нисходящем - наоборот. А вот как выглядит реализация:

Solution:
template <typename T>
class BinaryHeap
{
public:
    BinaryHeap() :
        m_comparator(std::greater<T>())
    {

    }
    explicit BinaryHeap(const std::vector<T>& elements):
        m_comparator(std::greater<T>())
    {
        m_heap = elements;
        BuildHeap();
    }
    BinaryHeap(const std::vector<T>& elements, std::function<bool(T,T)> compare):
        m_comparator(compare)
    {
        m_heap = elements;
        BuildHeap();
    }
    void BuildHeap()
    {
        const auto lastNumber = m_heap.size() - 1;
        const auto middleNumber = lastNumber / 2;

        for (auto i = middleNumber; i > 0; --i)
        {
            SiftDown(i);
        }
        SiftDown(0);
    }
    void Insert(T value)
    {
        m_heap.push_back(value);
        SiftUp(m_heap.size() - 1);
    }
    void Remove(unsigned int number)
    {
        const auto lastElement = m_heap.size() - 1;
        std::swap(m_heap[lastElement], m_heap[number]);
        m_heap.resize(m_heap.size() - 1);
        SiftDown(number);
    }

private:
    void SiftDown(unsigned int position)
    {
        const auto lastNumber = m_heap.size() - 1;

        while (position < lastNumber)
        {
            const auto leftChild = (position << 1) + 1;
            const auto rightChild = (position + 1) << 1;

            if (leftChild > lastNumber)
            {
                break;
            }

            if (m_comparator(m_heap[position], m_heap[leftChild]))
            {
                std::swap(m_heap[position], m_heap[leftChild]);
            }

            if (rightChild > lastNumber)
            {
                break;
            }

            if (m_comparator(m_heap[position], m_heap[rightChild]))
            {
                std::swap(m_heap[position], m_heap[rightChild]);
            }

            ++position;
        }
    }
    void SiftUp(unsigned int position)
    {
        while (position)
        {
            const auto root = (position - 1) >> 1;
            if (m_comparator(m_heap[root], m_heap[position]))
            {
                std::swap(m_heap[root], m_heap[position]);
                position = root;
            }
            else
            {
                break;
            }
        }
    }

    std::vector<T> m_heap;
    std::function<bool(T, T)> m_comparator;
};
 
Последнее редактирование:

ARCHANGEL

Посетитель
Мудрец
Сообщения
16
Реакции
432
Задача на динамическое программирование. Нам дан массив целых положительных чисел. Нужно найти максимальную сумму чисел, не расположенных по соседству. Т.е. в эту самую сумму могут входить числа, разница индексов которых больше 1. Написание самого алгоритма - тривиально, а вот составление реккурентной формулы - более сложная задача.

Для решения задачи создаётся второй массив, по размеру равный исходному. Элементы этого массива вычисляются по такому соотношению:

newArray = std::max(newArray[i - 1], newArray[i - 2] + inputArray);

Поскольку, мы либо берём значение, полученное на предыдущем шаге (и к такому значению нельзя прибавить текущий элемент), либо прибавляем текущий элемент к значению, полученному 2 шага назад.

Solution:
#include <vector>
using namespace std;

int maxSubsetSumNoAdjacent(vector<int> array)
{
  if (array.empty())
    {
        return 0;
    }
    
    std::vector<int> maxSums(array.size());
    for (size_t i = 0;i < array.size();++i)
    {
        switch (i)
        {
            case 0:
                maxSums[i] = array[i];
                break;
            case 1:
                maxSums[i] = std::max(array[i], array[i- 1]);
                break;
            default:
                maxSums[i] = std::max(maxSums[i - 1],
                                                         maxSums[i - 2] + array[i]);
                break;
        }
    }
 
    return *maxSums.crbegin();
}
 

ARCHANGEL

Посетитель
Мудрец
Сообщения
16
Реакции
432
Сегодня у нас очередная задача на динамическое программирование. Нужно написать функцию, которая вычислит, сколькими способами можно разменять заданную сумму, имея лишь купюры определённого номинала. Имплементация очень проста, но всё (как всегда в динамическом программировании) усложняется рекуррентным соотношением.

Часто в таких задачах (на динамическое программирование) есть некая величина (у нас это сумма денег), и есть некий массив значений (номиналы купюр). Для решения создаётся массив А (условно), размер которого либо равен этой скалярной величине (сумме денег), либо как-то с ней связан - здесь будет на единицу больше. Дальше как-то поочерёдно перебираются значения из заданного массива (номиналы купюр) и подставляются в некую формулу. Вычисленные по формуле значения записываются в массив А.

Здесь у нас массив А будет на единицу больше (как было сказано ранее), потому что в первом элементе массива хранится особый базовый случай. Этот первый элемент будет равен 1. Когда у вас сумма денег равна нулю, вы не можете выдать ни одной купюры - у вас нет вариантов. Почему тогда 1? Версия "у нас один вариант - пустое множество" - полная ерунда, просто такой базовый случай нужен для удобства вычислений.

Далее в цикле индекс массива А сравнивается со значением номинала текущей купюры (т.е. у нас два вложенных цикла). Если индекс больше либо равен, то значение массива увеличивается на значение по индекса разности первого индекса и номинала (весьма путанное объяснение, но будет код). Именно здесь нам и пригодится базовый случай, который при успехе этого сравнения будет записывать 1 в массив (изначально массив инициализируется нулями). И ещё - индекс массив стартует в цикле со значения 1 (не 0) - это важно.

Solution:
unsigned int GetWaysOfChange(unsigned int revard, const std::vector<unsigned int>& coins)
{
    std::vector<unsigned int> ways(revard + 1, 0);
    ways[0] = 1;

    for (const auto& coin: coins)
    {
        for (unsigned int i = 1;i < revard + 1;++i)
        {
            if (i >= coin)
            {
                ways[i] += ways[i - coin];
            }
        }
    }

    return *ways.crbegin();
}
 

ARCHANGEL

Посетитель
Мудрец
Сообщения
16
Реакции
432
Продолжаем тему размена монет. Сегодня у нас задача, аналогичная предыдущей, но теперь мы должны выдать число, равное минимальному количеству купюр для размена или -1, если размен невозможен. Иными словами, если есть несколько вариантов размена, мы выбираем тот, который состоит из меньшего количества купюр.

Solution:
#include <algorithm>
#include <vector>
#include <limits>
using namespace std;

int minNumberOfCoinsForChange(int n, vector<int> denoms)
{
    std::sort(denoms.begin(), denoms.end());
    std::vector<unsigned int> variants(n + 1, std::numeric_limits<int>::max());
    variants[0] = 0;

    for (const auto& denom : denoms)
    {
        for (size_t i = 0; i < variants.size(); ++i)
        {
            if (static_cast<unsigned int>(denom) <= i)
            {
                variants[i] = std::min(variants[i], 1 + variants[i - denom]);
            }
        }
    }
    return (*variants.crbegin() != std::numeric_limits<int>::max()) ?
        *variants.crbegin() : -1;
}
Здесь есть небольшой нюанс в строке сравнения variants = std::min(variants, 1 + variants[i - denom]);
Если хотите оставить такой порядок (i - denom, а не denom - i), то придётся использовать беззнаковые целые (unsigned int).
 

ARCHANGEL

Посетитель
Мудрец
Сообщения
16
Реакции
432
Сегодня у нас серию алгоритмов сортировки открывает Пузырьковая сортировка. Говорит особо нечего, реализация лобовая:

Solution:
#include <vector>
using namespace std;

vector<int> bubbleSort(vector<int> array)
{
    if (array.size() == 0 || array.size() == 1)
    {
        return array;
    }
    
  bool permutations;   
    
    do{
        permutations = false;
        for (size_t i = 0;i < array.size() - 1;++i)
        {
            if (array[i] > array[i + 1])
            {
                std::swap(array[i], array[i + 1]);
                permutations = true;               
            }
        }
    }while (permutations);
    
  return array;
}
Один совет - не используйте такое в своём коде. Алгоритм, имхо, который не стыдно и забыть.
 
Верх Низ