Swift | LeetCode

Задача: 761. Special Binary String Сложность: hard Специальные двоичные строки - это двоичные строки, обладающие следующими двумя свойствами: количество 0 равно количеству 1. Каждый префикс двоичной строки имеет не меньше 1, чем 0. Вам дана специальная двоичная строка s. Ход состоит в выборе двух последовательных, непустых специальных подстрок s и их обмене. Две строки являются последовательными, если последний символ первой строки находится ровно на один индекс раньше первого символа второй стр...

Задача: 1538. Guess the Majority in a Hidden Array Сложность: medium У нас есть целочисленный массив nums, где все числа в nums равны 0 или 1. Вам не будет предоставлен прямой доступ к массиву, вместо этого у вас будет API ArrayReader, который имеет следующие функции: int query(int a, int b, int c, int d): где 0 <= a < b < c < d < ArrayReader.length(). Функция возвращает распределение значений 4 элементов и возвращает: 4: если значения всех 4 элементов одинаковы (0 или 1). 2: если три элемента и...

Задача: 60. Permutation Sequence Сложность: hard Множество [1, 2, 3, ..., n] содержит в общей сложности n! уникальных перестановок. Списком и маркировкой всех перестановок по порядку, мы получаем следующую последовательность для n = 3: "123" "132" "213" "231" "312" "321" Дано n и k, верните k-ю перестановку последовательности. Пример: Input: n = 3, k = 3 Output: "213" 👨‍💻 Алгоритм: 1⃣Сгенерируйте входной массив nums чисел от 1 до N. 2⃣Вычислите все факториальные основы от 0 до (N−1)!. 3⃣Уменьш...

Задача: 74. Search a 2D Matrix Сложность: medium Вам дана матрица из целых чисел размером m на n с следующими двумя свойствами: Каждая строка отсортирована в порядке неубывания. Первое число каждой строки больше последнего числа предыдущей строки. Дано целое число target. Верните true, если target присутствует в матрице, и false в противном случае. Вы должны написать решение с временной сложностью O(log(m n)). Пример: Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 Output: tr...

Задача: 827. Making A Large Island Сложность: hard Вам дан n x n бинарный матрица grid. Вам разрешено изменить не более одного 0 на 1. Верните размер самого большого острова в grid после выполнения этой операции. Остров — это группа 1, соединенных в 4 направлениях. Пример: Input: grid = [[1,1],[1,0]] Output: 4 Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4. 👨‍💻 Алгоритм: 1⃣Пройдите по матрице и пометьте каждую группу, используя уникальный индекс, и зап...

Задача: 1101. The Earliest Moment When Everyone Become Friends Сложность: medium В социальной группе есть n человек, пронумерованных от 0 до n - 1. Вам дан массив logs, где logs[i] = [timestampi, xi, yi] указывает, что xi и yi станут друзьями в момент времени timestampi. Дружба является симметричной. Это означает, что если a является другом b, то b является другом a. Также человек a знаком с человеком b, если a является другом b или a является другом кого-то, кто знаком с b. Верните самое раннее...

Задача: 1318. Minimum Flips to Make a OR b Equal to c Сложность: medium Даны три положительных числа a, b и c. Верните минимальное количество переворотов, необходимых в некоторых битах a и b, чтобы сделать (a OR b == c) (побитовая операция OR). Операция переворота состоит из изменения любого отдельного бита с 1 на 0 или с 0 на 1 в их двоичном представлении. Пример: Input: a = 2, b = 6, c = 5 Output: 3 Explanation: After flips a = 1 , b = 4 , c = 5 such that (a OR b == c) 👨‍💻 Алгоритм: 1⃣Инициа...

Задача: 1230. Toss Strange Coins Сложность: medium У вас есть несколько монет. Вероятность выпадения орла для i-й монеты равна prob[i]. Верните вероятность того, что количество монет, на которых выпал орел, равно target, если вы подбросите каждую монету ровно один раз. Пример: Input: prob = [0.5,0.5,0.5,0.5,0.5], target = 0 Output: 0.03125 👨‍💻 Алгоритм: 1⃣Инициализация: Создайте переменную n и инициализируйте её размером массива prob. Создайте 2D массив dp размером n + 1 строк и target + 1 сто...

Задача: 1017. Convert to Base -2 Сложность: medium Если задано целое число n, верните двоичную строку, представляющую его в базе -2. Обратите внимание, что возвращаемая строка не должна содержать ведущих нулей, за исключением случаев, когда строка равна "0". Пример: Input: n = 2 Output: "110" 👨‍💻 Алгоритм: 1⃣Инициализация переменных: Создайте пустую строку для хранения двоичного представления числа. Используйте цикл для вычисления каждой цифры числа в базе -2. 2⃣Вычисление цифр: В цикле, пока ...

Задача: 895. Maximum Frequency Stack Сложность: hard Разработайте структуру данных, похожую на стек, чтобы заталкивать элементы в стек и вытаскивать из него самый частый элемент. Реализуйте класс FreqStack: FreqStack() строит пустой стек частот. void push(int val) заталкивает целое число val на вершину стека. int pop() удаляет и возвращает самый частый элемент в стеке. Если есть равенство в выборе самого частого элемента, то удаляется и возвращается элемент, который ближе всего к вершине стека. ...