Поиск дубликатов

Задача 217 Contains Duplicate с leetcode

🔍 Условие
• Учитывая целочисленный массив nums, вернуть true, если хотя бы одно значение появляется как минимум дважды в массиве, и вернуть false, если каждый элемент уникален

📚 Подход к решению
• Из-за того что уникальных элементов меньше или равно исходному размеру входного массива, то можно просто сравнить эти величины

#middle #algorithms #tasks

💡Решение
class Solution {
public:
bool containsDuplicate(vector& nums) {
set testSet(nums.begin(), nums.end());
return testSet.size() < nums.size();
}
};

Задача Перемещение нулей

🔍 Условие
• Необходимо перенести все нули в конец массива, не меняя порядок следования ненулевых элементов
• Сделать всё надо in-place (на том же самом массиве)

📚 Подход к решению
• Воспользоваться методом двух указателей. Когда один указывает на предыдущий элемент, а другой на следующий. Если предыдущий нулевой, то менять со следующим

#middle #algorithms #tasks

💡Решение
class Solution {
public:
void moveZeroes(vector& nums) {
for (size_t i = 0, j = 0; i < nums.size(); ++i) {
if (nums[i])
swap(nums[i], nums[j++]);
}
}
};

Ханойская башня

• Есть три башни. Цель игры состоит в том, чтобы переместить все диски на третью башню, но вы не можете поместить диск большего размера на диск меньшего размера
• Необходимо создать функцию, которая принимает число дисков в качестве аргумента и возвращает минимальное количество шагов, необходимое для завершения игры

Подсказки

• Можно использовать библиотеку <cmath>
• Можно использовать функцию возведения в степень pow

Tower of Hanoi (edabit)

#middle #algorithms #tasks

Решение
#include <cmath>
int towerHanoi(int discs) {
return pow(2, discs) — 1;
}