Поиск дубликатов
Задача 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();
}
};
Задача 217 Contains Duplicate с leetcode
🔍 Условие
• Учитывая целочисленный массив nums, вернуть true, если хотя бы одно значение появляется как минимум дважды в массиве, и вернуть false, если каждый элемент уникален
📚 Подход к решению
• Из-за того что уникальных элементов меньше или равно исходному размеру входного массива, то можно просто сравнить эти величины
#middle #algorithms #tasks
💡Решение
Задача Перемещение нулей
🔍 Условие
• Необходимо перенести все нули в конец массива, не меняя порядок следования ненулевых элементов
• Сделать всё надо 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++]);
}
}
};
🔍 Условие
• Необходимо перенести все нули в конец массива, не меняя порядок следования ненулевых элементов
• Сделать всё надо in-place (на том же самом массиве)
📚 Подход к решению
• Воспользоваться методом двух указателей. Когда один указывает на предыдущий элемент, а другой на следующий. Если предыдущий нулевой, то менять со следующим
#middle #algorithms #tasks
💡Решение
👍9
Ханойская башня
• Есть три башни. Цель игры состоит в том, чтобы переместить все диски на третью башню, но вы не можете поместить диск большего размера на диск меньшего размера
• Необходимо создать функцию, которая принимает число дисков в качестве аргумента и возвращает минимальное количество шагов, необходимое для завершения игры
Подсказки
• Можно использовать библиотеку <cmath>
• Можно использовать функцию возведения в степень pow
Tower of Hanoi (edabit)
#middle #algorithms #tasks
Решение
#include <cmath>
int towerHanoi(int discs) {
return pow(2, discs) — 1;
}
• Есть три башни. Цель игры состоит в том, чтобы переместить все диски на третью башню, но вы не можете поместить диск большего размера на диск меньшего размера
• Необходимо создать функцию, которая принимает число дисков в качестве аргумента и возвращает минимальное количество шагов, необходимое для завершения игры
Подсказки
• Можно использовать библиотеку <cmath>
• Можно использовать функцию возведения в степень pow
Tower of Hanoi (edabit)
#middle #algorithms #tasks
Решение
⚙️ Search in a Binary Search Tree
В задаче требуется реализовать поиск по бинарному дереву
Подход к решению
- Реализуется с помощью рекурсивного алгоритма
- Сначала обходим левое поддерево, а затем правое
#tasks #middle
Решение
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
if (!root)
return nullptr;
if (root->val == val)
return root;
if (val < root->val)
return searchBST(root->left, val);
else
return searchBST(root->right, val);
}
};
В задаче требуется реализовать поиск по бинарному дереву
Подход к решению
- Реализуется с помощью рекурсивного алгоритма
- Сначала обходим левое поддерево, а затем правое
#tasks #middle
Решение
👍2
🧿 Задача Простая пара
Дан массив целых чисел arr и целое число n. Найдите из данного массива пару чисел [x, y] такую, что x * y = n. Если пара не найдена, вернуть [0, 0]
👉A Simple Pair (edabit)
#middle #tasks
Решение
std::pair simplePair(std::vector arr, int n) {
for (int i = 0; i < arr.size()-1; ++i) {
for (int j = i+1; j < arr.size(); ++j) {
if (arr[i] * arr[j] == n) {
return std::make_pair(arr[i], arr[j]);
}
}
}
return std::make_pair( 0, 0 );
}
Дан массив целых чисел arr и целое число n. Найдите из данного массива пару чисел [x, y] такую, что x * y = n. Если пара не найдена, вернуть [0, 0]
👉A Simple Pair (edabit)
#middle #tasks
Решение
👍1