Недалёкий разбор

Дано: в задаче «Ханойская башня» нужно переместить стопку дисков с одного колышка на другой, следуя следующим правилам: 1) Одновременно можно перемещать только один диск. 2) Диск можно положить только на больший диск или на пустой колышек. 3) Все диски начинаются на одной колышке и должны быть перемещены на другую колышку с помощью промежуточной колышки. Решение будет производится с помощью рекурсии, а точнее вызова 2 рекурсивных функций за один шаг. Первый шаг. Назовём нашу функцию HanoiTower,...

«Обход в ширину» или «Поиск в ширину» (Breadth first traversal or Breadth first Search) - это рекурсивный алгоритм поиска всех вершин графа или древовидной структуры данных. Для простоты предполагается, что все вершины достижимы из начальной вершины. BFS использует для обхода структуру данных: очередь (queue) Стандартная реализация ВFS помещает каждую вершину графа в одну из двух категорий: Цель алгоритма - пометить каждую вершину, как посещенную, избегая циклов. Алгоритм работает следующим образом: Давайте посмотрим, как алгоритм «поиска в ширину» работает на примере...

Дано: Задан двумерный двоичный массив m x n, представляющий собой карту из «1» (земля) и «0» (вода), нужно найти количество островов на карте. Примечание: Остров окружен водой и образуется путем соединения соседних земель по горизонтали или вертикали. Предполагаются, что все четыре края карты окружены водой. Пример 1: Вход: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] Выход: 1 Пример 2: Вход: grid = [ ["1","1","0","0","0"], ...

Дано: целое число n, верните true, если оно является степенью двойки. В противном случае возвращается false. Пример 1: Дано: n = 1 Выход: true Пример 2: Дано: n = 16 Выход: true Пример 3: Дано: n = 3 Выход: false Ограничения: -2^31 <= n <= 2^31 - 1 Решения: 1) Наивный подход class Solution: def isPowerOfTwo(self, n: int) -> bool: if n <= 0: return False if n == 1: return True while (n % 2 == 0): n /= 2 return n == 1 Отсекаем...

Дано: массив целых чисел nums четной длины, состоящий из равного количества положительных и отрицательных целых чисел. Необходимо переставить элементы nums таким образом, чтобы измененный массив соответствовал заданным условиям: - Каждое следующее число имеет противоположный знак. - Для всех целых чисел с одинаковым знаком сохраняется порядок, в котором они находились в nums. - Переупорядоченный массив начинается с положительного целого числа. Пример 1: Дано: nums = [3,1,-2,-5,2,-4] Ответ: [3,-2,1,-5,2,-4] Пример 2: Дано: nums = [-1,1] Ответ: [1,-1] Ограничения: 2 <= nums...

Дано: матрица m x n Надо: верните все элементы матрицы в спиральном порядке. Пример 1: Дано: matrix= [[1,2,3],[4,5,6],[7,8,9]] Ответ: [1,2,3,6,9,8,7,4,5] Пример 2: Дано: matrix= [[1,2,3,4],[5,6,7,8],[9,10,11,12]] Ответ: [1,2,3,4,8,12,11,10,9,5,6,7] Ограничения: m == matrix.length n == matrix[i].length 1 <= m, n <= 10 -100 <= matrix[i][j] <= 100 Решение: class Solution: def spiralOrder(self, matrix: List[List[int]]) -> List[int]: result = [] start_col, end_col, start_row,...

Дано: В Крестики-нолики(Tic Tac Toe) играют два игрока A и B на сетке 3 x 3. Задан двумерный целочисленный массив moves, где moves[i] = [rowi, coli], в итоге на i-й ходе [rowi][coli], будет выявлен победитель, если он существует (A или B). В случае, если игра заканчивается вничью, возвращается "Ничья" (Draw). Если еще есть ходы, которые нужно сыграть, верните "Ожидание хода" (Pending). Ответ должен содержать имя игрока A или B, Draw(Ничья) или Pending(Ожидание хода) Ходы соответствуют правилам игры в Крестики-нолики, сетка изначально пуста, и игрок A будет играть первым...

Дано: массив строк strs, сгруппируйте строки по спискам в соответствии, являются ли они анаграммами или нет. Вы можете вернуть ответ в любом порядке. Анаграмма - это слово или фраза, образованная путем перестановки букв другого слова или фразы, обычно с использованием всех исходных букв ровно один раз. Пример 1: Дано: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]. Ответ: [["bat"],["nat","tan"],["ate","eat","tea"]] Пример 2: Дано: strs = [""] Ответ: [[""]] Пример 3: Дано: strs = ["a"] Ответ: [["a"]] Ограничения: 1 <= strs...

Сортировка подсчётом (Counting sort) Самая простая по алгоритму сортировка, которая лучше всего работает, когда у нас достаточно большое количество одинаковых значений. Смысл прост: посчитать, сколько каких значений имеется в последовательности, и вывести их по порядку именно столько раз.Сложность: O(n) Сортировка вставками (Insertion sort) Каждый элемент массива вставляется на правильное (относительно остальных) место в новом, отсортированном массиве. Так как кроме обхода всех элементов массива,...

3. Сложность корня O (√n) 4. Сложность степени O (n^x) Сложность многочленов увеличивается с ростом степени А) n– Одиночный цикл от 1 до n даёт O(n) Б) n^2 – сумма арифметической прогрессии Простые программы можно анализировать с помощью подсчёта в них количества вложенных циклов. Одиночный цикл в n итераций даёт f( n ) = n. Цикл внутри цикла — f( n ) = n2. Цикл внутри цикла внутри цикла — f( n ) = n3...

Разберёмся к какому алгоритму надо стремиться: 1) O(1) имеет наименьшую сложность. Часто называемый «постоянный по времени», если вы можете создать алгоритм для решения проблемы с O(1), то это будет лучший выбор алгоритма. Фактически, любая программа, не содержащая циклы, имеет O(1), потому что в этом случае требуется константное число инструкций (конечно, при отсутствии рекурсии. Давайте рассмотрим программу на Python, которая складывает два значения из массива и записывает результат в новую переменную:...