#medium
Задача: 611. Valid Triangle Number

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

Пример:

Input: nums = [2,2,3,4]
Output: 3

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

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

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

3⃣Увеличивайте счетчик на количество подходящих пар для каждого третьего элемента.

😎 Решение:

fun triangleNumber(nums: IntArray): Int {
    nums.sort()
    val n = nums.size
    var count = 0
    
    for (k in n - 1 downTo 2) {
        var i = 0
        var j = k - 1
        while (i < j) {
            if (nums[i] + nums[j] > nums[k]) {
                count += j - i
                j--
            } else {
                i++
            }
        }
    }
    
    return count
}

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

#medium
Задача: 616. Add Bold Tag in String

Вам дана строка s и массив строк words. Вы должны добавить закрытую пару полужирных тегов <b> и </b>, чтобы обернуть подстроки в s, которые существуют в words. Если две такие подстроки пересекаются, вы должны обернуть их вместе только одной парой закрытых полужирных тегов. Если две подстроки, обернутые полужирными тегами, идут подряд, вы должны объединить их. Верните s после добавления полужирных тегов.

Пример:

Input: s = "abcxyz123", words = ["abc","123"]
Output: "<b>abc</b>xyz<b>123</b>"

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

1⃣Найдите все позиции вхождений подстрок из words в строку s и пометьте эти позиции для выделения тегами <b> и </b>.

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

3⃣Постройте новую строку s, добавляя теги <b> и </b> в определенные позиции.

😎 Решение:

fun addBoldTag(s: String, words: Array<String>): String {
    val bold = BooleanArray(s.length)
    
    for (word in words) {
        var start = s.indexOf(word)
        while (start != -1) {
            for (i in start until start + word.length) {
                bold[i] = true
            }
            start = s.indexOf(word, start + 1)
        }
    }
    
    val result = StringBuilder()
    var i = 0
    while (i < s.length) {
        if (bold[i]) {
            result.append("<b>")
            while (i < s.length && bold[i]) {
                result.append(s[i])
                i++
            }
            result.append("</b>")
        } else {
            result.append(s[i])
            i++
        }
    }
    
    return result.toString()
}

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

#medium
Задача: 617. Merge Two Binary Trees

Вам даны два бинарных дерева root1 и root2. Представьте, что при наложении одного из них на другое некоторые узлы двух деревьев перекрываются, а другие - нет. Вам нужно объединить эти два дерева в новое бинарное дерево. Правило слияния таково: если два узла пересекаются, то в качестве нового значения объединенного узла используется сумма значений узлов. В противном случае в качестве узла нового дерева будет использоваться узел NOT null. Возвращается объединенное дерево. Примечание: Процесс объединения должен начинаться с корневых узлов обоих деревьев.

Пример:

Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]

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

1⃣Если один из узлов пуст (null), возвращаем другой узел. Если оба узла пустые, возвращаем null.

2⃣Если оба узла не пустые, создаем новый узел, значение которого равно сумме значений двух узлов. Рекурсивно объединяем левые и правые поддеревья.

3⃣Возвращаем новый узел, который является корнем объединенного дерева.

😎 Решение:

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun mergeTrees(root1: TreeNode?, root2: TreeNode?): TreeNode? {
    if (root1 == null) return root2
    if (root2 == null) return root1
    
    val mergedNode = TreeNode(root1.`val` + root2.`val`)
    mergedNode.left = mergeTrees(root1.left, root2.left)
    mergedNode.right = mergeTrees(root1.right, root2.right)
    
    return mergedNode
}

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

#medium
Задача: 622. Design Circular Queue

Разработайте свою реализацию круговой очереди. Круговая очередь - это линейная структура данных, в которой операции выполняются по принципу FIFO (First In First Out), а последняя позиция соединяется с первой, образуя круг. Одно из преимуществ круговой очереди заключается в том, что мы можем использовать пространство перед очередью. В обычной очереди, когда очередь становится полной, мы не можем вставить следующий элемент, даже если перед очередью есть свободное место. Но с помощью круговой очереди мы можем использовать пространство для хранения новых значений. Реализация класса MyCircularQueue: MyCircularQueue(k) Инициализирует объект с размером очереди k. int Front() Получает первый элемент из очереди. Если очередь пуста, возвращается -1. int Rear() Получает последний элемент из очереди. Если очередь пуста, возвращается -1. boolean enQueue(int value) Вставляет элемент в циклическую очередь. Возвращает true, если операция прошла успешно. boolean deQueue() Удаляет элемент из круговой очереди. Возвращает true, если операция выполнена успешно. boolean isEmpty() Проверяет, пуста ли круговая очередь. boolean isFull() Проверяет, заполнена ли круговая очередь. Вы должны решить проблему без использования встроенной структуры данных очереди в вашем языке программирования.

Пример:

Input
["MyCircularQueue", "enQueue", "enQueue", "enQueue", "enQueue", "Rear", "isFull", "deQueue", "enQueue", "Rear"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 3, true, true, true, 4]

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

1⃣Используйте массив фиксированного размера для хранения элементов очереди и два указателя: front для отслеживания начала очереди и rear для отслеживания конца очереди.

2⃣Реализуйте методы enQueue и deQueue для вставки и удаления элементов, обновляя указатели по круговому принципу.

3⃣Реализуйте методы Front, Rear, isEmpty и isFull для доступа к элементам и проверки состояния очереди.

😎 Решение:

class MyCircularQueue(k: Int) {
    private val queue: IntArray = IntArray(k) { -1 }
    private var front: Int = 0
    private var rear: Int = -1
    private var size: Int = 0
    private val capacity: Int = k
    
    fun enQueue(value: Int): Boolean {
        if (isFull()) {
            return false
        }
        rear = (rear + 1) % capacity
        queue[rear] = value
        size++
        return true
    }
    
    fun deQueue(): Boolean {
        if (isEmpty()) {
            return false
        }
        front = (front + 1) % capacity
        size--
        return true
    }
    
    fun Front(): Int {
        return if (isEmpty()) -1 else queue[front]
    }
    
    fun Rear(): Int {
        return if (isEmpty()) -1 else queue[rear]
    }
    
    fun isEmpty(): Boolean {
        return size == 0
    }
    
    fun isFull(): Boolean {
        return size == capacity
    }
}

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

#medium
Задача: 623. Add One Row to Tree

Учитывая корень бинарного дерева и два целых числа val и depth, добавьте ряд узлов со значением val на заданную глубину depth. Обратите внимание, что корневой узел находится на глубине 1. Правило добавления таково: учитывая целое число depth, для каждого ненулевого узла дерева cur на глубине depth - 1 создайте два узла дерева со значением val в качестве левого поддерева корня cur и правого поддерева корня.
Оригинальное левое поддерево cur должно быть левым поддеревом нового корня левого поддерева. Оригинальное правое поддерево cur должно быть правым поддеревом нового корня правого поддерева. Если глубина == 1, то есть глубина - 1 вообще не существует, создайте узел дерева со значением val как новый корень всего оригинального дерева, а оригинальное дерево - левое поддерево нового корня.

Пример:

Input: root = [4,2,6,3,1,5], val = 1, depth = 2
Output: [4,1,1,2,null,null,6,3,1,5]

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

1⃣Если depth равна 1, создайте новый корень со значением val и сделайте текущий корень левым поддеревом нового корня.

2⃣Используйте обход в ширину (BFS) для поиска всех узлов на глубине depth - 1.

3⃣Для каждого узла на глубине depth - 1, вставьте новые узлы со значением val в качестве левого и правого поддеревьев, сохраняя исходные поддеревья.

😎 Решение:

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun addOneRow(root: TreeNode?, `val`: Int, depth: Int): TreeNode? {
    if (depth == 1) {
        return TreeNode(`val`).apply { left = root }
    }
    
    val queue = mutableListOf<TreeNode>()
    root?.let { queue.add(it) }
    var currentDepth = 1
    
    while (queue.isNotEmpty()) {
        if (currentDepth == depth - 1) {
            queue.forEach { node ->
                node.left = TreeNode(`val`).apply { left = node.left }
                node.right = TreeNode(`val`).apply { right = node.right }
            }
            break
        }
        currentDepth++
        val nextQueue = mutableListOf<TreeNode>()
        queue.forEach { node ->
            node.left?.let { nextQueue.add(it) }
            node.right?.let { nextQueue.add(it) }
        }
        queue.clear()
        queue.addAll(nextQueue)
    }
    
    return root
}

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

#medium
Задача: 624. Maximum Distance in Arrays

Вам дано m массивов, где каждый массив отсортирован по возрастанию. Вы можете взять два целых числа из двух разных массивов (каждый массив выбирает одно) и вычислить расстояние. Мы определяем расстояние между двумя целыми числами a и b как их абсолютную разность |a - b|. Верните максимальное расстояние.

Пример:

Input: arrays = [[1,2,3],[4,5],[1,2,3]]
Output: 4

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

1⃣Найдите минимальный элемент из всех первых элементов массивов и максимальный элемент из всех последних элементов массивов.

2⃣Рассчитайте максимальное расстояние между минимальным и максимальным элементами.

3⃣Верните это максимальное расстояние.

😎 Решение:

fun maxDistance(arrays: List<List<Int>>): Int {
    var minVal = arrays[0][0]
    var maxVal = arrays[0].last()
    var maxDistance = 0
    
    for (i in 1 until arrays.size) {
        maxDistance = maxOf(maxDistance, kotlin.math.abs(arrays[i].last() - minVal), kotlin.math.abs(arrays[i][0] - maxVal))
        minVal = minOf(minVal, arrays[i][0])
        maxVal = maxOf(maxVal, arrays[i].last())
    }
    
    return maxDistance
}

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

#medium
Задача: 625. Minimum Factorization

Если задано целое положительное число num, верните наименьшее целое положительное число x, умножение каждого разряда которого равно num. Если ответа нет или ответ не помещается в 32-битное знаковое целое число, возвращается 0.

Пример:

Input: num = 48
Output: 68

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

1⃣Если num равно 1, верните 1. Инициализируйте массив для хранения множителей.

2⃣Разделите num на множители от 9 до 2, пока num больше 1. Если в процессе остаются множители больше 9, верните 0.

3⃣Постройте результат, собирая найденные множители в обратном порядке. Если результат больше 32-битного целого числа, верните 0.

😎 Решение:

fun smallestFactorization(num: Int): Int {
    if (num == 1) return 1
    
    var num = num
    val factors = mutableListOf<Int>()
    
    for (i in 9 downTo 2) {
        while (num % i == 0) {
            factors.add(i)
            num /= i
        }
    }
    
    if (num > 1) return 0
    
    var result: Long = 0
    for (factor in factors.asReversed()) {
        result = result * 10 + factor
        if (result > Int.MAX_VALUE) return 0
    }
    
    return result.toInt()
}

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

#medium
Задача: 628. Maximum Product of Three Numbers

Задав целочисленный массив 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)
}

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

#hard
Задача: 629. K Inverse Pairs Array

Для целочисленного массива nums инверсная пара - это пара целых чисел [i, j], где 0 <= i < j < nums.length и nums[i] > nums[j]. Учитывая два целых числа n и k, верните количество различных массивов, состоящих из чисел от 1 до n, в которых существует ровно k инверсных пар. Поскольку ответ может быть огромным, верните его по модулю 109 + 7.

Пример:

Input: n = 3, k = 0
Output: 1

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

1⃣Инициализация
Создайте двумерный массив dp размером [n+1][k+1] и установите начальное значение dp[0][0] = 1. Остальные значения установите в 0.

2⃣Заполнение DP-таблицы
Используйте два вложенных цикла для заполнения таблицы DP. Внешний цикл перебирает длину массива i от 1 до n, а внутренний цикл перебирает количество инверсий j от 0 до k. Если j == 0, то dp[i][j] = 1. В противном случае обновляйте dp[i][j] с учетом всех возможных позиций вставки нового элемента в массив длины i-1.

3⃣Возвращение результата
Результатом будет значение dp[n][k].

😎 Решение:

fun kInversePairs(n: Int, k: Int): Int {
    val MOD = 1000000007
    val dp = Array(n + 1) { IntArray(k + 1) }
    dp[0][0] = 1

    for (i in 1..n) {
        dp[i][0] = 1
        for (j in 1..k) {
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
            if (j >= i) {
                dp[i][j] -= dp[i - 1][j - i]
            }
            dp[i][j] = (dp[i][j] + MOD) % MOD
        }
    }

    return dp[n][k]
}

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

#easy
Задача: 434. Number of Segments in a String

Дана строка s, верните количество сегментов в строке.

Сегмент определяется как непрерывная последовательность символов, отличных от пробелов.

Пример:

Input: s = "Hello, my name is John"
Output: 5
Explanation: The five segments are ["Hello,", "my", "name", "is", "John"]

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

1⃣Инициализируйте счетчик сегментов segment_count равным 0.

2⃣Итеративно пройдитесь по строке s. Для каждого индекса i проверьте, начинается ли на этом индексе сегмент: Если символ s[i] не является пробелом, и (либо это первый символ строки, либо предыдущий символ s[i-1] является пробелом), увеличьте segment_count.

3⃣Верните segment_count.

😎 Решение:

class Solution {
    fun countSegments(s: String): Int {
        var segmentCount = 0
        for (i in s.indices) {
            if ((i == 0 || s[i - 1] == ' ') && s[i] != ' ') {
                segmentCount++
            }
        }
        return segmentCount
    }
}

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

#hard
Задача: 630. Course Schedule III

Имеется n различных онлайн-курсов, пронумерованных от 1 до n. Вам дан массив courses, где courses[i] = [durationi, lastDayi] указывает, что i-й курс должен быть пройден непрерывно в течениеi дней и должен быть закончен до или в lastDayi. Вы начинаете в 1-й день и не можете проходить два или более курсов одновременно. Верните максимальное количество курсов, которые вы можете пройти.

Пример:

Input: courses = [[100,200],[200,1300],[1000,1250],[2000,3200]]
Output: 3

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

1⃣Сортировка курсов
Отсортируйте курсы по их конечным датам (lastDay). Это позволяет проходить курсы как можно ближе к их крайним срокам.

2⃣Проход по курсам
Используйте приоритетную очередь (max-heap) для отслеживания продолжительности пройденных курсов.

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

😎 Решение:

import java.util.PriorityQueue

fun scheduleCourse(courses: Array<IntArray>): Int {
    courses.sortBy { it[1] }
    val maxHeap = PriorityQueue<Int>(reverseOrder())
    var totalTime = 0

    for (course in courses) {
        val duration = course[0]
        val lastDay = course[1]
        maxHeap.add(duration)
        totalTime += duration

        if (totalTime > lastDay) {
            totalTime -= maxHeap.poll()
        }
    }

    return maxHeap.size
}

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

#hard
Задача: 354. Russian Doll Envelopes

Вам дан двумерный массив целых чисел envelopes, где envelopes[i] = [wi, hi] представляет ширину и высоту конверта.

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

Примечание: Вы не можете поворачивать конверт.

Пример:

Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

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

1⃣Отсортируйте массив конвертов по возрастанию по первой размерности (ширине) и по убыванию по второй размерности (высоте).

2⃣Извлеките вторую размерность (высоты) отсортированного массива.

3⃣Найдите длину наибольшей возрастающей подпоследовательности в массиве высот.

😎 Решение:

class Solution {
    fun lengthOfLIS(nums: IntArray): Int {
        val dp = IntArray(nums.size)
        var len = 0
        for (num in nums) {
            var i = dp.binarySearch(0, len, num)
            if (i < 0) i = -(i + 1)
            dp[i] = num
            if (i == len) len++
        }
        return len
    }

    fun maxEnvelopes(envelopes: Array<IntArray>): Int {
        envelopes.sortWith(Comparator { arr1, arr2 ->
            if (arr1[0] == arr2[0]) arr2[1] - arr1[1]
            else arr1[0] - arr2[0]
        })
        val secondDim = envelopes.map { it[1] }.toIntArray()
        return lengthOfLIS(secondDim)
    }
}

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

#medium
Задача: 435. Non-overlapping Intervals

Дан массив интервалов intervals, где intervals[i] = [starti, endi]. Верните минимальное количество интервалов, которые нужно удалить, чтобы остальные интервалы не пересекались.

Пример:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

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

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

2⃣Инициализируйте переменную ответа ans = 0 и целое число k для представления самого последнего времени окончания. k следует инициализировать небольшим значением, например, INT_MIN.

3⃣Итеративно пройдитесь по интервалам. Для каждого интервала: Если время начала больше или равно k, обновите k до времени окончания текущего интервала. В противном случае увеличьте ans. Верните ans.

😎 Решение:

class Solution {
    fun eraseOverlapIntervals(intervals: Array<IntArray>): Int {
        intervals.sortBy { it[1] }
        var ans = 0
        var k = Int.MIN_VALUE
        
        for (interval in intervals) {
            val x = interval[0]
            val y = interval[1]
            if (x >= k) {
                k = y
            } else {
                ans++
            }
        }
        
        return ans
    }
}

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

#hard
Задача: 358. Rearrange String k Distance Apart

Дана строка 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() }
    }
}

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

#easy
Задача: 559. Maximum Depth of N-ary Tree

Дано n-арное дерево, найдите его максимальную глубину.

Максимальная глубина - это количество узлов вдоль самого длинного пути от корневого узла до самого дальнего листового узла.

Сериализация ввода n-арного дерева представлена в порядке уровня, каждая группа дочерних узлов разделена значением null (см. примеры).

Пример:

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

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

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

2⃣Здесь мы демонстрируем пример с использованием стратегии поиска в глубину (DFS - Depth First Search).

3⃣Применяя DFS, проходим через все узлы дерева, вычисляя максимальную глубину.

😎 Решение:

class Solution {
    fun maxDepth(root: Node?): Int {
        if (root == null) {
            return 0
        } else if (root.children.isEmpty()) {
            return 1
        } else {
            val heights = root.children.map { maxDepth(it) }
            return heights.maxOrNull()!! + 1
        }
    }
}

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

#medium
Задача: 560. Subarray Sum Equals K

Дан массив целых чисел nums и целое число k, вернуть общее количество подмассивов, сумма которых равна k.

Подмассив - это непрерывная непустая последовательность элементов внутри массива.

Пример:

Input: nums = [1,1,1], k = 2
Output: 2

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

1⃣Самый простой метод - рассмотреть каждый возможный подмассив данного массива nums.

2⃣Найти сумму элементов каждого из этих подмассивов и проверить равенство полученной суммы с заданным k.

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

😎 Решение:

class Solution {
    fun subarraySum(nums: IntArray, k: Int): Int {
        var count = 0
        for (start in nums.indices) {
            for (end in start + 1..nums.size) {
                var sum = 0
                for (i in start until end) {
                    sum += nums[i]
                }
                if (sum == k) {
                    count++
                }
            }
        }
        return count
    }
}

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

#easy
Задача: 561. Array Partition

Дан массив целых чисел nums из 2n элементов. Разделите эти числа на n пар (a1, b1), (a2, b2), ..., (an, bn) так, чтобы сумма min(ai, bi) для всех i была максимальной. Верните максимальную сумму.

Пример:

Input: nums = [1,4,3,2]
Output: 4
Explanation: All possible pairings (ignoring the ordering of elements) are:
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
So the maximum possible sum is 4.

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

1⃣Отсортируйте массив nums в неубывающем порядке.

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

3⃣Суммируйте выбранные элементы и верните эту сумму.

😎 Решение:

class Solution {
    fun arrayPairSum(nums: IntArray): Int {
        nums.sort()
        var sum = 0
        for (i in nums.indices step 2) {
            sum += nums[i]
        }
        return sum
    }
}

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

#medium
Задача: 562. Longest Line of Consecutive One in Matrix

Дана бинарная матрица размера m x n. Вернуть длину самой длинной последовательной линии из единиц в матрице.

Линия может быть горизонтальной, вертикальной, диагональной или анти-диагональной.

Пример:

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

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

1⃣Создайте 3 матрицы для хранения текущей длины последовательных единиц: horizontal, vertical, diagonal и anti_diagonal.

2⃣Итерируйте через каждый элемент матрицы: Если элемент равен 1, обновите соответствующие значения в матрицах horizontal, vertical, diagonal и anti_diagonal. Обновите максимальную длину последовательной линии.

3⃣Верните максимальную длину.

😎 Решение:

class Solution {
    fun longestLine(mat: Array<IntArray>): Int {
        if (mat.isEmpty() || mat[0].isEmpty()) return 0
        
        val m = mat.size
        val n = mat[0].size
        var maxLength = 0
        
        val horizontal = Array(m) { IntArray(n) }
        val vertical = Array(m) { IntArray(n) }
        val diagonal = Array(m) { IntArray(n) }
        val antiDiagonal = Array(m) { IntArray(n) }
        
        for (i in mat.indices) {
            for (j in mat[0].indices) {
                if (mat[i][j] == 1) {
                    horizontal[i][j] = (if (j > 0) horizontal[i][j - 1] else 0) + 1
                    vertical[i][j] = (if (i > 0) vertical[i - 1][j] else 0) + 1
                    diagonal[i][j] = (if (i > 0 && j > 0) diagonal[i - 1][j - 1] else 0) + 1
                    antiDiagonal[i][j] = (if (i > 0 && j < n - 1) antiDiagonal[i - 1][j + 1] else 0) + 1
                    
                    maxLength = maxOf(maxLength, horizontal[i][j], vertical[i][j], diagonal[i][j], antiDiagonal[i][j])
                }
            }
        }
        
        return maxLength
    }
}

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

#easy
Задача: 563. Binary Tree Tilt

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

Наклон узла дерева - это абсолютная разница между суммой всех значений узлов левого поддерева и всех значений узлов правого поддерева. Если у узла нет левого потомка, то сумма значений узлов левого поддерева считается равной 0. То же правило применяется, если у узла нет правого потомка.

Пример:

Input: root = [1,2,3]
Output: 1
Explanation: 
Tilt of node 2 : |0-0| = 0 (no children)
Tilt of node 3 : |0-0| = 0 (no children)
Tilt of node 1 : |2-3| = 1 (left subtree is just left child, so sum is 2; right subtree is just right child, so sum is 3)
Sum of every tilt : 0 + 0 + 1 = 1

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

1⃣Определите рекурсивную функцию, которая вычисляет сумму значений узлов поддерева и наклон текущего узла.

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

3⃣Верните общую сумму наклонов всех узлов.

😎 Решение:

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

class Solution {
    private var totalTilt = 0
    
    fun findTilt(root: TreeNode?): Int {
        fun sumAndTilt(node: TreeNode?): Int {
            if (node == null) return 0
            val leftSum = sumAndTilt(node.left)
            val rightSum = sumAndTilt(node.right)
            val nodeTilt = kotlin.math.abs(leftSum - rightSum)
            totalTilt += nodeTilt
            return node.`val` + leftSum + rightSum
        }
        
        sumAndTilt(root)
        return totalTilt
    }
}

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

#medium
Задача: 669. Trim a Binary Search Tree

Дано корневое дерево двоичного поиска и нижняя и верхняя границы как low и high. Обрежьте дерево так, чтобы все его элементы лежали в диапазоне [low, high]. Обрезка дерева не должна изменять относительную структуру элементов, которые останутся в дереве (то есть любой потомок узла должен оставаться потомком). Можно доказать, что существует единственный ответ.

Верните корень обрезанного дерева двоичного поиска. Обратите внимание, что корень может измениться в зависимости от заданных границ.

Пример:

Input: root = [1,0,2], low = 1, high = 2
Output: [1,null,2]

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

1⃣Если node.val > high, то обрезанное двоичное дерево должно находиться слева от узла.

2⃣Если node.val < low, то обрезанное двоичное дерево должно находиться справа от узла.

3⃣В противном случае обрезаем обе стороны дерева.

😎 Решение:

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

class Solution {
    fun trimBST(root: TreeNode?, low: Int, high: Int): TreeNode? {
        root ?: return null
        if (root.`val` > high) return trimBST(root.left, low, high)
        if (root.`val` < low) return trimBST(root.right, low, high)
        root.left = trimBST(root.left, low, high)
        root.right = trimBST(root.right, low, high)
        return root
    }
}

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