Задача: 927. Three Equal Parts
Сложность: hard

Вам дан массив arr, состоящий только из нулей и единиц. Разделите массив на три непустые части так, чтобы все эти части представляли одно и то же двоичное значение. Если это возможно, верните любой [i, j] с i + 1 < j, такой что: arr[0], arr[1], ..., arr[i] - это первая часть, arr[i + 1], arr[i + 2], ...., arr[j - 1] - вторая часть, и arr[j], arr[j + 1], ..., arr[arr.length - 1] - третья часть. Все три части имеют одинаковые двоичные значения. Если это невозможно, верните [-1, -1]. Обратите внимание, что вся часть используется при рассмотрении того, какое двоичное значение она представляет. Например, [1,1,0] представляет 6 в десятичной системе, а не 3. Кроме того, допускаются ведущие нули, поэтому [0,1,1] и [1,1] представляют одно и то же значение.

Пример:

Input: arr = [1,0,1,0,1]
Output: [0,3]

👨‍💻 Алгоритм:

1⃣Подсчитать количество единиц в массиве.

2⃣Если количество единиц не делится на три, вернуть [-1, -1].
Найти индексы начала каждой части, игнорируя ведущие нули.
Использовать эти индексы для проверки, могут ли три части быть одинаковыми.

3⃣Если три части одинаковы, вернуть соответствующие индексы, иначе вернуть [-1, -1].

😎 Решение:

class Solution {
    fun threeEqualParts(arr: IntArray): IntArray {
        val ones = arr.sum()
        if (ones % 3 != 0) return intArrayOf(-1, -1)
        if (ones == 0) return intArrayOf(0, arr.size - 1)

        val partOnes = ones / 3
        var first = 0
        var second = 0
        var third = 0
        var cnt = 0
        for (i in arr.indices) {
            if (arr[i] == 1) {
                when (cnt) {
                    0 -> first = i
                    partOnes -> second = i
                    2 * partOnes -> third = i
                }
                cnt++
            }
        }

        while (third < arr.size && arr[first] == arr[second] && arr[first] == arr[third]) {
            first++
            second++
            third++
        }

        return if (third == arr.size) intArrayOf(first - 1, second) else intArrayOf(-1, -1)
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 66. Plus One
Сложность: easy

Вам дано большое число, представленное в виде массива целых чисел digits, где каждый элемент digits[i] — это i-я цифра числа. Цифры расположены в порядке от старшей к младшей слева направо. Большое число не содержит ведущих нулей.

Увеличьте большое число на один и верните результирующий массив цифр.

Пример:

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1,2,4].

👨‍💻 Алгоритм:

1⃣Проходим по входному массиву, начиная с конца массива.

2⃣Устанавливаем все девятки на конце массива в ноль. Если мы встречаем цифру, не равную девяти, увеличиваем её на один. Работа выполнена — возвращаем массив цифр.

3⃣Мы здесь, потому что все цифры были равны девяти. Теперь они все установлены в ноль. Затем мы добавляем цифру 1 в начало остальных цифр и возвращаем результат.

😎 Решение:

class Solution {
    fun plusOne(digits: IntArray): IntArray {
        val n = digits.size
        for (i in n - 1 downTo 0) {
            if (digits[i] == 9) {
                digits[i] = 0
            } else {
                digits[i]++
                return digits
            }
        }
        val result = IntArray(n + 1)
        result[0] = 1
        return result
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 358. Rearrange String k Distance Apart
Сложность: hard

Дана строка s и целое число k, переставьте символы в s так, чтобы одинаковые символы находились на расстоянии не менее k друг от друга. Если невозможно переставить строку, верните пустую строку "".

Пример:

Input: s = "aabbcc", k = 3
Output: "abcabc"
Explanation: The same letters are at least a distance of 3 from each other.

👨‍💻 Алгоритм:

1⃣Создайте словарь частот для символов строки и определите максимальную частоту.

2⃣Разделите символы на группы по частоте и создайте сегменты для размещения символов.

3⃣Распределите оставшиеся символы по сегментам, проверяя условия, и объедините сегменты в итоговую строку.

😎 Решение:

class Solution {
    fun rearrangeString(s: String, k: Int): String {
        val freqs = mutableMapOf<Char, Int>()
        var maxFreq = 0
        
        for (char in s) {
            freqs[char] = freqs.getOrDefault(char, 0) + 1
            maxFreq = maxOf(maxFreq, freqs[char]!!)
        }
        
        val mostChars = freqs.filter { it.value == maxFreq }.keys
        val secondChars = freqs.filter { it.value == maxFreq - 1 }.keys
        
        val segments = Array(maxFreq) { StringBuilder() }
        
        for (i in 0 until maxFreq) {
            for (char in mostChars) {
                segments[i].append(char)
            }
            if (i < maxFreq - 1) {
                for (char in secondChars) {
                    segments[i].append(char)
                }
            }
        }
        
        var segmentId = 0
        
        for ((char, freq) in freqs) {
            if (char in mostChars || char in secondChars) {
                continue
            }
            
            var freq = freq
            while (freq > 0) {
                segments[segmentId].append(char)
                segmentId = (segmentId + 1) % (maxFreq - 1)
                freq--
            }
        }
        
        for (i in 0 until maxFreq - 1) {
            if (segments[i].length < k) {
                return ""
            }
        }
        
        return segments.joinToString("") { it.toString() }
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1481. Least Number of Unique Integers after K Removals
Сложность: medium

Дан массив целых чисел arr и целое число k. Найдите минимальное количество уникальных целых чисел после удаления ровно k элементов.

Пример:

Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.

👨‍💻 Алгоритм:

1⃣Инициализация и построение частотного массива:
Создайте хеш-таблицу для отслеживания частот элементов массива arr.
Итеративно увеличивайте частоту элементов в хеш-таблице.

2⃣Сортировка и удаление элементов:
Создайте массив частот и заполните его значениями из хеш-таблицы.
Отсортируйте массив частот.
Инициализируйте переменную для отслеживания числа удаленных элементов и итеративно добавляйте частоты, пока количество удаленных элементов не превысит k.

3⃣Возвращение результата:
Если количество удаленных элементов превысило k, верните оставшееся количество уникальных элементов.
Если все элементы были удалены, верните 0.

😎 Решение:

class Solution {
    fun findLeastNumOfUniqueInts(arr: IntArray, k: Int): Int {
        val freqMap = mutableMapOf<Int, Int>()
        for (num in arr) {
            freqMap[num] = freqMap.getOrDefault(num, 0) + 1
        }
        
        val frequencies = freqMap.values.sorted()
        
        var elementsRemoved = 0
        for (i in frequencies.indices) {
            elementsRemoved += frequencies[i]
            if (elementsRemoved > k) {
                return frequencies.size - i
            }
        }
        
        return 0
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 468. Validate IP Address
Сложность: medium

Допустимый IPv4-адрес — это IP в форме "x1.x2.x3.x4", где 0 <= xi <= 255 и xi не может содержать ведущие нули. Например, "192.168.1.1" и "192.168.1.0" являются допустимыми IPv4-адресами, тогда как "192.168.01.1", "192.168.1.00" и "[email protected]" являются недопустимыми IPv4-адресами.

Допустимый IPv6-адрес — это IP в форме "x1:x2:x3:x4:x5:x6:x7
", где:
1 <= xi.length <= 4
xi — это шестнадцатеричная строка, которая может содержать цифры, строчные английские буквы ('a' до 'f') и прописные английские буквы ('A' до 'F').
Ведущие нули в xi допускаются.

Пример:

Input: queryIP = "172.16.254.1"
Output: "IPv4"
Explanation: This is a valid IPv4 address, return "IPv4".

👨‍💻 Алгоритм:

1⃣Для проверки адреса IPv4:
Разделить IP на четыре части по разделителю ".".
Проверить каждую подстроку:
Является ли она целым числом между 0 и 255.
Не содержит ли она ведущих нулей (исключение — число "0").

2⃣Для проверки адреса IPv6:
Разделить IP на восемь частей по разделителю ":".
Проверить каждую подстроку:
Является ли она шестнадцатеричным числом длиной от 1 до 4 символов.

3⃣Если IP не соответствует ни одному из форматов, вернуть "Neither".

😎 Решение:

class Solution {
    fun validateIPv4(IP: String): String {
        val nums = IP.split(".")
        for (x in nums) {
            if (x.length == 0 || x.length > 3) return "Neither"
            if (x[0] == '0' && x.length != 1) return "Neither"
            for (ch in x) {
                if (!ch.isDigit()) return "Neither"
            }
            if (x.toInt() > 255) return "Neither"
        }
        return "IPv4"
    }

    fun validateIPv6(IP: String): String {
        val nums = IP.split(":")
        val hexdigits = "0123456789abcdefABCDEF"
        for (x in nums) {
            if (x.length == 0 || x.length > 4) return "Neither"
            for (ch in x) {
                if (hexdigits.indexOf(ch) == -1) return "Neither"
            }
        }
        return "IPv6"
    }

    fun validIPAddress(IP: String): String {
        return when {
            IP.count { it == '.' } == 3 -> validateIPv4(IP)
            IP.count { it == ':' } == 7 -> validateIPv6(IP)
            else -> "Neither"
        }
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 957. Prison Cells After N Days
Сложность: medium

Есть 8 тюремных камер в ряду, и каждая камера либо занята, либо пуста.
Каждый день статус камеры, занята она или пуста, меняется по следующим правилам:
Если у камеры два соседних соседа, которые оба заняты или оба пусты, то камера становится занятой.
В противном случае, она становится пустой.
Учтите, что поскольку тюрьма — это ряд, у первой и последней камер в ряду не может быть двух соседних соседей.

Вам дан целочисленный массив cells, где cells[i] == 1, если i-я камера занята, и cells[i] == 0, если i-я камера пуста, и вам дано целое число n.
Верните состояние тюрьмы после n дней (т.е. после n таких изменений, описанных выше).

Пример:

Input: cells = [0,1,0,1,1,0,0,1], n = 7
Output: [0,0,1,1,0,0,0,0]
Explanation: The following table summarizes the state of the prison on each day:
Day 0: [0, 1, 0, 1, 1, 0, 0, 1]
Day 1: [0, 1, 1, 0, 0, 0, 0, 0]
Day 2: [0, 0, 0, 0, 1, 1, 1, 0]
Day 3: [0, 1, 1, 0, 0, 1, 0, 0]
Day 4: [0, 0, 0, 0, 0, 1, 0, 0]
Day 5: [0, 1, 1, 1, 0, 1, 0, 0]
Day 6: [0, 0, 1, 0, 1, 1, 0, 0]
Day 7: [0, 0, 1, 1, 0, 0, 0, 0]

👨‍💻 Алгоритм:

1⃣Преобразуйте текущее состояние камер в целое число с помощью битовой маски. Это позволит удобно отслеживать повторяющиеся состояния.

2⃣Симулируйте изменение состояния камер день за днем, записывая каждое состояние в хэш-таблицу. Если обнаруживается повторяющееся состояние, вычислите длину цикла и уменьшите количество оставшихся дней с учетом этого цикла.

3⃣Продолжайте симуляцию, пока не достигнете заданного числа дней, либо используйте цикл для ускорения процесса.

😎 Решение:

class Solution {
    fun cellsToBitmap(cells: IntArray): Int {
        var stateBitmap = 0
        for (cell in cells) {
            stateBitmap = (stateBitmap shl 1) or cell
        }
        return stateBitmap
    }

    fun nextDay(cells: IntArray): IntArray {
        val newCells = IntArray(cells.size)
        for (i in 1 until cells.size - 1) {
            newCells[i] = if (cells[i - 1] == cells[i + 1]) 1 else 0
        }
        return newCells
    }

    fun prisonAfterNDays(cells: IntArray, N: Int): IntArray {
        var cells = cells
        var N = N
        val seen = mutableMapOf<Int, Int>()
        var isFastForwarded = false

        while (N > 0) {
            if (!isFastForwarded) {
                val stateBitmap = cellsToBitmap(cells)
                if (stateBitmap in seen) {
                    N %= seen[stateBitmap]!! - N
                    isFastForwarded = true
                } else {
                    seen[stateBitmap] = N
                }
            }

            if (N > 0) {
                N--
                cells = nextDay(cells)
            }
        }
        return cells
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 298. Binary Tree Longest Consecutive Sequence
Сложность: medium

Дан корень бинарного дерева, верните длину самого длинного пути последовательных значений.

Путь последовательных значений — это путь, где значения увеличиваются на единицу вдоль пути.

Обратите внимание, что путь может начинаться с любого узла в дереве, и вы не можете перейти от узла к его родителю на пути.

Пример:

Input: root = [1,null,3,2,4,null,null,null,5]
Output: 3
Explanation: Longest consecutive sequence path is 3-4-5, so return 3.

👨‍💻 Алгоритм:

1⃣Инициализация и начало обхода:
Начните обход дерева с корневого узла.
Инициализируйте переменную length, чтобы хранить текущую длину последовательного пути, и передавайте её вниз по дереву.

2⃣Сравнение текущего узла с родительским узлом:
Для каждого узла сравните его значение со значением родительского узла.
Если значение текущего узла на единицу больше значения родительского узла, увеличьте length.
Если значение текущего узла не является последовательным (не больше на единицу), сбросьте length на 1.

3⃣Обход дерева:
Рекурсивно обходите левое и правое поддерево, передавая обновлённое значение length.
В каждом узле обновляйте максимальную длину последовательного пути, если текущая длина больше.

😎 Решение:

class Solution {
    private var maxLength = 0

    fun longestConsecutive(root: TreeNode?): Int {
        dfs(root, null, 0)
        return maxLength
    }

    private fun dfs(node: TreeNode?, parent: TreeNode?, length: Int) {
        if (node == null) return
        var currentLength = length
        if (parent != null && node.`val` == parent.`val` + 1) {
            currentLength += 1
        } else {
            currentLength = 1
        }
        maxLength = maxOf(maxLength, currentLength)
        dfs(node.left, node, currentLength)
        dfs(node.right, node, currentLength)
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 300. Longest Increasing Subsequence
Сложность: medium

Дан массив целых чисел nums, верните длину самой длинной строго возрастающей подпоследовательности.

Пример:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

👨‍💻 Алгоритм:

1⃣Инициализируйте массив dp длиной nums.length, все элементы которого равны 1. dp[i] представляет длину самой длинной возрастающей подпоследовательности, которая заканчивается элементом с индексом i.

2⃣Итерируйтесь от i = 1 до i = nums.length - 1. В каждой итерации используйте второй цикл for для итерации от j = 0 до j = i - 1 (все элементы перед i). Для каждого элемента перед i, проверьте, меньше ли этот элемент, чем nums[i]. Если да, установите dp[i] = max(dp[i], dp[j] + 1).

3⃣Верните максимальное значение из dp.

😎 Решение:

class Solution {
    fun lengthOfLIS(nums: IntArray): Int {
        if (nums.isEmpty()) return 0

        val dp = IntArray(nums.size) { 1 }

        for (i in 1 until nums.size) {
            for (j in 0 until i) {
                if (nums[i] > nums[j]) {
                    dp[i] = maxOf(dp[i], dp[j] + 1)
                }
            }
        }

        return dp.maxOrNull() ?: 0
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 230. Kth Smallest Element in a BST
Сложность: medium

Дан корень бинарного дерева поиска и целое число k. Верните k-ое по величине значение (нумерация с 1) среди всех значений узлов в дереве.

Пример:

Input: root = [3,1,4,null,2], k = 1
Output: 1

👨‍💻 Алгоритм:

1⃣Инициализация стека и обход в глубину: Инициализируйте стек для хранения узлов дерева. Начните обход дерева в глубину, начиная с корня, и перемещайтесь влево, добавляя каждый узел в стек, пока не достигнете самого левого узла.

2⃣Извлечение узлов и проверка: Когда достигнете самого левого узла, извлеките узел из стека и уменьшите значение k на 1. Если k становится равным нулю, верните значение текущего узла, так как это и есть k-ое по величине значение.

3⃣Переход к правому поддереву: Если k не равен нулю, переместитесь к правому поддереву текущего узла и продолжайте обход, повторяя шаги 1 и 2, пока не найдете k-ое по величине значение.

😎 Решение:

class Solution {
    fun kthSmallest(root: TreeNode?, k: Int): Int {
        val stack = LinkedList<TreeNode>()
        var root = root
        var k = k

        while (true) {
            while (root != null) {
                stack.push(root)
                root = root.left
            }
            root = stack.pop()
            if (--k == 0) return root.`val`
            root = root.right
        }
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 675. Cut Off Trees for Golf Event
Сложность: hard

Вам необходимо срубить все деревья в лесу для проведения гольф-мероприятия. Лес представлен в виде матрицы m x n. В этой матрице:

- 0 означает, что ячейка непроходима.
- 1 представляет собой пустую проходимую ячейку.
- Число больше 1 представляет собой дерево в ячейке, и это число обозначает высоту дерева.

За один шаг вы можете передвигаться в любом из четырех направлений: север, восток, юг и запад. Если вы стоите в ячейке с деревом, вы можете выбрать, срубить его или нет.

Вы должны срубить деревья в порядке от самого низкого до самого высокого. Когда вы срубаете дерево, значение в его ячейке становится 1 (пустая ячейка).

Начиная с точки (0, 0), верните минимальное количество шагов, необходимых для того, чтобы срубить все деревья. Если невозможно срубить все деревья, верните -1.

Примечание: Входные данные сформированы так, что нет двух деревьев с одинаковой высотой, и нужно срубить как минимум одно дерево.

Пример:

Input: forest = [[1,2,3],[0,0,4],[7,6,5]]
Output: 6
Explanation: Following the path above allows you to cut off the trees from shortest to tallest in 6 steps.

👨‍💻 Алгоритм:

1⃣Начиная с (0, 0), для каждого дерева в порядке возрастания высоты будем вычислять расстояние от текущего местоположения до следующего дерева (и перемещаться туда), добавляя это расстояние к ответу.

2⃣Формулируем задачу как предоставление функции расстояния dist(forest, sr, sc, tr, tc), которая вычисляет расстояние от точки (sr, sc) до цели (tr, tc) с учетом препятствий, где dist[i][j] == 0. (Эта функция расстояния вернет -1, если путь невозможен.)

3⃣Далее следует код и анализ сложности, которые общие для всех трех подходов. Затем алгоритмы, представленные в наших подходах, будут сосредоточены только на предоставлении нашей функции dist.

😎 Решение:

class Solution {
    fun cutOffTree(forest: List<List<Int>>): Int {
        val trees = forest.withIndex().flatMap { (r, row) ->
            row.withIndex().mapNotNull { (c, v) ->
                if (v > 1) Triple(v, r, c) else null
            }
        }.sortedBy { it.first }
        
        var sr = 0
        var sc = 0
        var ans = 0
        for ((_, tr, tc) in trees) {
            val d = dist(forest, sr, sc, tr, tc)
            if (d < 0) return -1
            ans += d
            sr = tr
            sc = tc
        }
        return ans
    }

    fun dist(forest: List<List<Int>>, sr: Int, sc: Int, tr: Int, tc: Int): Int {
        // Implement the distance function here
        return 0
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 253. Meeting Rooms II
Сложность: medium

Дан массив интервалов времени встреч intervals, где intervals[i] = [starti, endi]. Верните минимальное количество необходимых конференц-залов.

Пример:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2

👨‍💻 Алгоритм:

1⃣Отсортируйте встречи по времени их начала и инициализируйте мин-кучу с временем окончания первой встречи.

2⃣Для каждой последующей встречи проверьте, свободна ли комната (сравните время начала встречи с минимальным временем окончания в куче):
Если свободна, обновите время окончания этой комнаты.
Если не свободна, добавьте новое время окончания в кучу.

3⃣После обработки всех встреч размер кучи будет равен минимальному количеству необходимых комнат.

😎 Решение:

import java.util.*

class Solution {
    fun minMeetingRooms(intervals: Array<IntArray>): Int {
        intervals.sortBy { it[0] }
        val heap = PriorityQueue<Int>()
        heap.add(intervals[0][1])
        
        for (i in 1 until intervals.size) {
            if (intervals[i][0] >= heap.peek()) {
                heap.poll()
            }
            heap.add(intervals[i][1])
        }
        return heap.size
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1530. Number of Good Leaf Nodes Pairs
Сложность: medium

Вам дан корень бинарного дерева и целое число distance. Пара двух различных листовых узлов бинарного дерева называется хорошей, если длина кратчайшего пути между ними меньше или равна distance.

Верните количество хороших пар листовых узлов в дереве.

Пример:

Input: root = [1,2,3,null,4], distance = 3
Output: 1
Explanation: The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.

👨‍💻 Алгоритм:

1⃣ Инициализируйте список смежности для преобразования дерева в граф и множество для хранения листовых узлов. Используйте вспомогательный метод traverseTree для обхода дерева, чтобы построить граф и найти листовые узлы. В параметрах поддерживайте текущий узел, а также родительский узел. Если текущий узел является листом, добавьте его в множество. В списке смежности добавьте текущий узел в список соседей родительского узла и наоборот. Рекурсивно вызовите traverseTree для левого и правого дочернего узла текущего узла.

2⃣ Инициализируйте переменную ans для подсчета количества хороших пар листовых узлов. Итеративно переберите каждый листовой узел в множестве. Запустите BFS для текущего листового узла. BFS можно прервать досрочно, как только будут обнаружены все узлы, находящиеся на расстоянии от текущего листового узла. Увеличьте ans для каждого листового узла, найденного в каждом запуске BFS.

3⃣ Верните ans / 2. Мы считаем каждую пару дважды, поэтому нужно разделить на 2, чтобы получить фактическое количество.

😎 Решение:

class Solution {
    fun countPairs(root: TreeNode?, distance: Int): Int {
        val graph = mutableMapOf<TreeNode, MutableList<TreeNode>>()
        val leafNodes = mutableSetOf<TreeNode>()
        traverseTree(root, null, graph, leafNodes)
        var ans = 0
        for (leaf in leafNodes) {
            val bfsQueue: Queue<TreeNode> = LinkedList()
            val seen = mutableSetOf<TreeNode>()
            bfsQueue.add(leaf)
            seen.add(leaf)
            for (i in 0..distance) {
                val size = bfsQueue.size
                for (j in 0 until size) {
                    val currNode = bfsQueue.poll()
                    if (leafNodes.contains(currNode) && currNode != leaf) {
                        ans++
                    }
                    graph[currNode]?.let {
                        for (neighbor in it) {
                            if (!seen.contains(neighbor)) {
                                bfsQueue.add(neighbor)
                                seen.add(neighbor)
                            }
                        }
                    }
                }
            }
        }
        return ans / 2
    }

    private fun traverseTree(currNode: TreeNode?, prevNode: TreeNode?,
                             graph: MutableMap<TreeNode, MutableList<TreeNode>>, leafNodes: MutableSet<TreeNode>) {
        if (currNode == null) {
            return
        }
        if (currNode.left == null && currNode.right == null) {
            leafNodes.add(currNode)
        }
        if (prevNode != null) {
            graph.computeIfAbsent(prevNode) { mutableListOf() }.add(currNode)
            graph.computeIfAbsent(currNode) { mutableListOf() }.add(prevNode)
        }
        traverseTree(currNode.left, currNode, graph, leafNodes)
        traverseTree(currNode.right, currNode, graph, leafNodes)
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 628. Maximum Product of Three Numbers
Сложность: medium

Задав целочисленный массив nums, найдите три числа, произведение которых максимально, и верните максимальное произведение.

Пример:

Input: nums = [1,2,3]
Output: 6

👨‍💻 Алгоритм:

1⃣Отсортируйте массив nums.

2⃣Найдите два возможных максимальных произведения: Произведение трех наибольших элементов массива. Произведение двух наименьших (отрицательных) и одного наибольшего элемента массива.

3⃣Верните максимальное из двух найденных произведений.

😎 Решение:

fun maximumProduct(nums: IntArray): Int {
    nums.sort()
    val n = nums.size
    val max1 = nums[n - 1] * nums[n - 2] * nums[n - 3]
    val max2 = nums[0] * nums[1] * nums[n - 1]
    return kotlin.math.max(max1, max2)
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 259. 3Sum Smaller
Сложность: medium

Дан массив из n целых чисел nums и целое число target. Найдите количество троек индексов i, j, k, удовлетворяющих условию 0 <= i < j < k < n и nums[i] + nums[j] + nums[k] < target.

Пример:

Input: nums = [-2,0,1,3], target = 2
Output: 2
Explanation: Because there are two triplets which sums are less than 2:
[-2,0,1]
[-2,0,3]

👨‍💻 Алгоритм:

1⃣Отсортируйте массив nums.

2⃣Для каждого элемента nums[i] от 0 до n-3 найдите количество пар индексов j и k (где i < j < k), таких что nums[i] + nums[j] + nums[k] < target. Используйте функцию twoSumSmaller, которая ищет количество пар с суммой меньше заданного значения.

3⃣В функции twoSumSmaller используйте бинарный поиск для поиска верхней границы индекса k и подсчета количества подходящих пар.

😎 Решение:

class Solution {
    fun threeSumSmaller(nums: IntArray, target: Int): Int {
        nums.sort()
        var sum = 0
        for (i in 0 until nums.size - 2) {
            sum += twoSumSmaller(nums, i + 1, target - nums[i])
        }
        return sum
    }

    private fun twoSumSmaller(nums: IntArray, startIndex: Int, target: Int): Int {
        var sum = 0
        for (i in startIndex until nums.size - 1) {
            val j = binarySearch(nums, i, target - nums[i])
            sum += j - i
        }
        return sum
    }

    private fun binarySearch(nums: IntArray, startIndex: Int, target: Int): Int {
        var left = startIndex
        var right = nums.size - 1
        while (left < right) {
            val mid = (left

Ставь 👍 и забирай 📚 Базу знаний

Задача №18. 4Sum
Сложность: medium

Учитывая массив nums из n целых чисел, верните массив всех уникальных четверок \([nums[a], nums[b], nums[c], nums[d]]\) таких, что:
- \(0 \leq a, b, c, d < n\)
- \(a, b, c\) и \(d\) различны.
- \(nums[a] + nums[b] + nums[c] + nums[d] = target\)

Вы можете вернуть ответ в любом порядке.

Пример:

Input: nums = [1,0,-1,0,-2,2], target = 0  
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]  

👨‍💻 Алгоритм:

1⃣ Отсортировать массив для упрощения поиска и исключения дубликатов.

2⃣ Использовать три вложенных цикла, фиксируя три элемента и применяя бинарный поиск для нахождения четвертого.

3⃣ Исключить дубликаты и оптимизировать поиск за счет границ суммы.

😎 Решение:

class Solution {
    fun fourSum(nums: IntArray, target: Int): List<List<Int>> {
        nums.sort()
        val target: Long = target.toLong()
        val sums = mutableListOf<List<Int>>()
        val lastIndex = nums.size - 1

        for (i in 0..lastIndex - 3) {
            if (i > 0 && nums[i - 1] == nums[i]) continue

            val targetI = target - nums[i]

            if (targetI < nums[i].toLong() + nums[i + 1].toLong() + nums[i + 2].toLong()) break
            if (targetI > nums[lastIndex].toLong() + nums[lastIndex - 1].toLong() + nums[lastIndex - 2].toLong()) {
                continue
            }

            for (j in i + 1..lastIndex - 2) {
                if (j > i + 1 && nums[j - 1] == nums[j]) continue

                val targetJ = targetI - nums[j]

                if (targetJ < nums[j].toLong() + nums[j + 1].toLong()) break
                if (targetJ > nums[lastIndex].toLong() + nums[lastIndex - 1].toLong()) continue

                for (k in j + 1..lastIndex - 1) {
                    if (k > j + 1 && nums[k - 1] == nums[k]) continue

                    val targetK = targetJ - nums[k]
                    val l = nums.binarySearch(targetK.toInt(), fromIndex = k + 1)
                    if (l >= 0) {
                        sums.add(listOf(nums[i], nums[j], nums[k], nums[l]))
                    }
                }
            }
        }

        return sums
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 280. Wiggle Sort
Сложность: medium

Дан целочисленный массив nums, упорядочьте его так, чтобы nums[0] <= nums[1] >= nums[2] <= nums[3]....

Вы можете считать, что входной массив всегда имеет допустимый ответ.

Пример:

Input: nums = [3,5,2,1,6,4]
Output: [3,5,1,6,2,4]
Explanation: [1,6,2,5,3,4] is also accepted.

👨‍💻 Алгоритм:

1⃣Итерируйтесь по каждому элементу с индексом i в массиве nums, начиная с 0 и до nums.length - 2, так как последний элемент не имеет следующего элемента для обмена.

2⃣Проверьте, является ли i четным и nums[i] > nums[i + 1]. Если это так, поменяйте местами nums[i] и nums[i + 1].

3⃣Проверьте, является ли i нечетным и nums[i] < nums[i + 1]. Если это так, поменяйте местами nums[i] и nums[i + 1].

😎 Решение:

class Solution {
    private fun swap(nums: IntArray, i: Int, j: Int) {
        val temp = nums[i]
        nums[i] = nums[j]
        nums[j] = temp
    }

    fun wiggleSort(nums: IntArray) {
        for (i in 0 until nums.size - 1) {
            if ((i % 2 == 0 && nums[i] > nums[i + 1]) || (i % 2 == 1 && nums[i] < nums[i + 1])) {
                swap(nums, i, i + 1)
            }
        }
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 372. Super Pow
Сложность: medium

Ваша задача — вычислить а^b mod 1337, где a - положительное число, а b - чрезвычайно большое положительное целое число, заданное в виде массива.

Пример:

Input: a = 2, b = [3]
Output: 8

👨‍💻 Алгоритм:

1⃣Разделите задачу на более мелкие задачи: вычислите a^b mod 1337, используя свойства модульной арифметики и степенной функции. Разделите большой показатель b на меньшие части, чтобы обрабатывать их по очереди.

2⃣Используйте метод быстрого возведения в степень (pow) для эффективного вычисления больших степеней с модулем 1337.

3⃣Объедините результаты для каждой части показателя b, используя свойства модульной арифметики: (a^b) % 1337 = ((a^(b1)) % 1337 * (a^(b2)) % 1337 * ...) % 1337.

😎 Решение:

class Solution {
    fun getSum(a: Int, b: Int): Int {
        var x = kotlin.math.abs(a)
        var y = kotlin.math.abs(b)
        if (x < y) return getSum(b, a)
        val sign = if (a > 0) 1 else -1

        if (a * b >= 0) {
            while (y != 0) {
                val carry = (x and y) shl 1
                x = x xor y
                y = carry
            }
        } else {
            while (y != 0) {
                val borrow = ((x.inv()) and y) shl 1
                x = x xor y
                y = borrow
            }
        }
        return x * sign
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 401. Binary Watch
Сложность: easy

Бинарные часы имеют 4 светодиода сверху для представления часов (0-11) и 6 светодиодов снизу для представления минут (0-59). Каждый светодиод представляет ноль или единицу, при этом младший разряд находится справа.

Пример:

Input: turnedOn = 1
Output: ["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]

👨‍💻 Алгоритм:

1⃣Генерация всех возможных комбинаций:
Переберите все возможные значения для часов и минут.
Используйте битовые операции для подсчета количества единиц в бинарном представлении числа.

2⃣Проверка количества горящих светодиодов:
Для каждой комбинации проверьте, соответствует ли сумма единиц в бинарном представлении часов и минут заданному количеству горящих светодиодов.

3⃣Форматирование результата:
Если комбинация часов и минут соответствует условию, отформатируйте их в виде строки "часы:минуты" и добавьте в список результатов.

😎 Решение:

import "fmt"

func readBinaryWatch(turnedOn int) []string {
    results := []string{}
    for h := 0; h < 12; h++ {
        for m := 0; m < 60; m++ {
            if bitCount(h)+bitCount(m) == turnedOn {
                results = append(results, fmt.Sprintf("%d:%02d", h, m))
            }
        }
    }
    return results
}

func bitCount(n int) int {
    count := 0
    for n > 0 {
        count += n & 1
        n >>= 1
    }
    return count
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1509. Minimum Difference Between Largest and Smallest Value in Three Moves
Сложность: medium

Вам дан массив целых чисел nums.

За один ход вы можете выбрать один элемент массива nums и изменить его на любое значение.

Верните минимальную разницу между наибольшим и наименьшим значением в массиве nums после выполнения не более трех ходов.

Пример:

Input: nums = [5,3,2,4]
Output: 0
Explanation: We can make at most 3 moves.
In the first move, change 2 to 3. nums becomes [5,3,3,4].
In the second move, change 4 to 3. nums becomes [5,3,3,3].
In the third move, change 5 to 3. nums becomes [3,3,3,3].
After performing 3 moves, the difference between the minimum and maximum is 3 - 3 = 0.

👨‍💻 Алгоритм:

1⃣Инициализация: определите размер массива nums, если размер меньше или равен 4, верните 0. Отсортируйте массив nums и инициализируйте переменную minDiff очень большим числом.

2⃣Итерация по первым четырем элементам отсортированного массива: для каждого индекса left от 0 до 3 вычислите соответствующий правый индекс, разницу между элементами на этих индексах и обновите minDiff с минимальным значением.

3⃣Верните minDiff, которое хранит минимальную разницу между наибольшими и наименьшими значениями после удаления до трех элементов.

😎 Решение:

class Solution {
    fun minDifference(nums: IntArray): Int {
        val numsSize = nums.size
        
        if (numsSize <= 4) return 0
        
        nums.sort()
        
        var minDiff = Int.MAX_VALUE
        
        for (left in 0 until 4) {
            val right = numsSize - 4 + left
            minDiff = minOf(minDiff, nums[right] - nums[left])
        }
        
        return minDiff
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 57. Insert Interval
Сложность: medium

Вам дан массив непересекающихся интервалов intervals, где intervals[i] = [starti, endi] представляет начало и конец i-го интервала, и массив intervals отсортирован в порядке возрастания по starti. Вам также дан интервал newInterval = [start, end], представляющий начало и конец другого интервала.

Вставьте newInterval в массив intervals так, чтобы intervals оставался отсортированным в порядке возрастания по starti и в intervals не было бы перекрывающихся интервалов (при необходимости объедините перекрывающиеся интервалы).

Верните массив intervals после вставки.

Обратите внимание, что не обязательно модифицировать массив intervals на месте. Вы можете создать новый массив и вернуть его.

Пример:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

👨‍💻 Алгоритм:

1⃣ Инициализация переменных:
Инициализируются переменные n и i для хранения размера массива интервалов и текущего индекса соответственно, а также пустой массив res для хранения результата.

2⃣Обработка случаев без перекрытия и с перекрытием:
В случае отсутствия перекрытия до вставки, проходим через массив интервалов до тех пор, пока конечная точка текущего интервала меньше начальной точки нового интервала. Добавляем текущий интервал в массив res и переходим к следующему.
В случае перекрытия, продолжаем обход, пока начальная точка нового интервала меньше или равна конечной точке текущего интервала. Обновляем начальные и конечные точки нового интервала, объединяя перекрывающиеся интервалы в один.

3⃣Обработка интервалов после вставки:
Проходим через оставшиеся интервалы после индекса i и добавляем их в массив res. Это включает интервалы, которые следуют после нового интервала и не перекрываются с ним.
Возвращаем массив res, содержащий все интервалы с корректно вставленным новым интервалом.

😎 Решение:

class Solution {
    fun insert(intervals: List<List<Int>>, newInterval: MutableList<Int>): List<List<Int>> {
        val n = intervals.size
        var i = 0
        val res = mutableListOf<List<Int>>()

        while (i < n && intervals[i][1] < newInterval[0]) {
            res.add(intervals[i])
            i++
        }

        while (i < n && newInterval[1] >= intervals[i][0]) {
            newInterval[0] = minOf(newInterval[0], intervals[i][0])
            newInterval[1] = maxOf(newInterval[1], intervals[i][1])
            i++
        }
        res.add(newInterval)

        while (i < n) {
            res.add(intervals[i])
            i++
        }

        return res
    }
}

Ставь 👍 и забирай 📚 Базу знаний