Задача: №16. 3Sum Closest #medium

Условие:

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

Решение:

class Solution {
    fun threeSumClosest(nums: IntArray, target: Int): Int {
        Arrays.sort(nums)
        var numsLen = nums.size
        var lastTwoSum = nums[numsLen - 1] + nums[numsLen - 2]
        var result = 0
        var distance = Integer.MAX_VALUE

        if (nums[0] + nums[1] + nums[2] > target)  return nums[0] + nums[1] + nums[2]
        if (lastTwoSum + nums[numsLen - 3] < target)  return lastTwoSum + nums[numsLen - 3]
        if (nums[0] == nums[numsLen - 1])  return 3 * nums[0]

        for (i in 0..(numsLen - 3)) {
            var cur0 = nums[i]
            if (i == 0 || cur0 != nums[i-1]) { 
                if (cur0 + nums[i + 1] + nums[i + 2] > target) {
                    if (cur0 + nums[i + 1] + nums[i + 2] - target < distance)  
                        result = cur0 + nums[i + 1] + nums[i + 2]
                    break
                }
                if (cur0 + lastTwoSum <= target) {  
                    if (target - cur0 + lastTwoSum < distance) {
                        distance = target - cur0 + lastTwoSum
                        result = cur0 + lastTwoSum
                    }
                    continue
                }
                var left = i + 1
                var right = numsLen - 1
                while (left < right) {
                    var sum = cur0 + nums[left] + nums[right]
                    if (sum == target)  return target
                    if (Math.abs(target - sum) < distance) {
                        distance = Math.abs(target - sum)
                        result = sum
                    }
                    if (sum > target)
                        right--
                    else
                        left++
                }
            }
        }
        return result
    }
}

Пояснение:
Сортировка: Сначала массив nums сортируется для упрощения поиска.
Инициализация переменных: Определяются переменные для хранения длины массива, суммы последних двух элементов и начального значения результата.
Основной цикл: Проходит по каждому элементу массива, рассматривая его как первый элемент тройки.
Двухуказательный метод: Использует два указателя для поиска двух других элементов массива, которые вместе с текущим элементом дадут сумму, наиболее близкую к target.
Проверка и обновление результата: Сравнивает текущую сумму с целевым значением и обновляет результат, если находится более близкая сумма.
Возврат результата: Функция возвращает сумму, которая является наилучшей суммой тройки элементов, наиболее близкой к целевому значению.

Задача: №17. Letter Combinations of a Phone Number #medium

Условие:

Учитывая строку, содержащую цифры от 2 до 9 включительно, верните все возможные комбинации букв, которые может представлять число. Верните ответ в любом порядке. Соответствие цифр буквам (как на кнопках телефона) приведено ниже. Обратите внимание, что 1 не соответствует никаким буквам.

Решение:

class Solution {
    
    fun letterCombinations(digits: String): List<String> =
        digits.takeIf { it.isNotEmpty() }?.fold(listOf("")) { acc, c ->
            c.letters.flatMap { letter -> acc.map { it + letter } }
        } ?: emptyList()

    private val Char.letters get() = when(this) {
        '2' -> listOf('a', 'b', 'c')
        '3' -> listOf('d', 'e', 'f')
        '4' -> listOf('g', 'h', 'i')
        '5' -> listOf('j', 'k', 'l')
        '6' -> listOf('m', 'n', 'o')
        '7' -> listOf('p', 'q', 'r', 's')
        '8' -> listOf('t', 'u', 'v')
        '9' -> listOf('w', 'x', 'y', 'z')
        else -> listOf()
    }
}

Пояснение:
Проверка пустого ввода: Если входная строка digits пуста, функция возвращает пустой список, так как нет цифр для обработки.

Формирование комбинаций:

Используется метод fold для последовательного обработки каждого символа строки digits. На начальном этапе в аккумулятор передается список, содержащий пустую строку.
Для каждого символа c в digits, получаются возможные буквы, соответствующие этому символу (c.letters).
Далее, для каждой буквы из возможных (letter), происходит объединение этой буквы со всеми строками в текущем аккумуляторе (acc), формируя новые строки. Результат каждого шага объединяется в список, что позволяет формировать все возможные комбинации.
Получение букв по цифре: Метод расширения letters для типа Char возвращает список букв, соответствующих данной цифре. Это позволяет быстро и удобно получить доступ к возможным буквам для каждой цифры в строке.

Задача: №18. 4Sum #medium

Условие:

Учитывая массив nums из n целых чисел, верните массив всех уникальных четверок [nums[a], nums[b], nums[c], nums[d]] таких, что:
0 <= a, b, c, d < n
a, b, c и d различны.
nums[a] + nums[b] + nums[c] + nums[d] == цель
Вы можете вернуть ответ в любом порядке

Решение:

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
    }
}

Пояснение:
В данном решении используется метод поиска всех четырех элементов в массиве, сумма которых равна заданному числу (target). Подход включает сортировку массива и использование трех вложенных циклов для поиска всех возможных комбинаций четырех элементов, удовлетворяющих условию. Вот ключевые моменты решения:

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

Первые вложенные циклы:

Внешний цикл (i) проходит по каждому элементу массива, рассматривая его как первый элемент возможной комбинации.
На каждом шаге проверяется, не был ли предыдущий элемент уже рассмотрен (if (i > 0 && nums[i - 1] == nums[i])), чтобы избежать дублирующихся комбинаций.
Определение целевой суммы для оставшихся элементов:

Рассчитывается targetI, которое представляет собой разницу между общим target и текущим элементом массива nums[i].
Второй вложенный цикл:

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

Рассчитывается targetJ, которое представляет собой разницу между targetI и текущим элементом nums[j].
Третий вложенный цикл:

Третий цикл (k) проходит по оставшимся элементам после j для нахождения третьего элемента комбинации.
Проверяется, не был ли предыдущий элемент уже рассмотрен.
Бинарный поиск:

Для поиска четвертого элемента используется метод binarySearch, что позволяет эффективно находить элемент, сумма с предыдущими тремя элементами которого равна target.
Если элемент найден (l >= 0), добавляется текущая комбинация четырех элементов в список sums.
Возвращение результата:

После завершения всех циклов, список sums содержит все уникальные комбинации четырех элементов, сумма которых равна target. Этот список возвращается в качестве результата.

Задача: №19. Remove Nth Node From End of List #medium

Условие:

Учитывая заголовок связанного списка, удалите n-й узел из конца списка и верните его заголовок.

Решение:

class Solution {
    fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {
        val dummyHead = ListNode(0).apply { next = head }
        var slow = dummyHead
        var fast = head.getOrNull(n)

        while (fast != null) {
            fast = fast.next
            slow = checkNotNull(slow.next)
        }
        val nodeToRemove = slow.next
        slow.next = nodeToRemove?.next
        nodeToRemove?.next = null
        return dummyHead.next
    }

    private fun ListNode?.getOrNull(index: Int): ListNode? {
        var result = this
        var i = 0

        while (i < index && result != null) {
            result = result.next
            i++
        }
        return result
    }
}

Пояснение:
Создание фиктивного узла:

Создается фиктивный узел dummyHead, который указывает на первый узел списка. Это упрощает управление случаями, когда нужно удалить узел в начале списка.
Инициализация двух указателей:

Два указателя slow и fast инициализируются так, что fast находится на n-м узле впереди относительно slow. Это делается с помощью функции getOrNull(n), которая перемещает fast на n шагов вперед.
Двигаем указатели одновременно:

Параллельно перемещаем slow и fast. Как только fast достигнет конца списка, slow окажется перед тем узлом, который нужно удалить, так как он будет n узлов от конца.
Удаление узла:

После завершения предыдущего шага slow будет указывать на узел перед тем, который нужно удалить (slow.next). Указываем slow.next на следующий за удаляемым узел (nodeToRemove.next), effectively skipping the node.
Опционально, устанавливаем nodeToRemove.next в null, чтобы очистить ссылки после удаления узла (это не всегда необходимо, но может помочь в управлении памятью в некоторых языках).
Возврат нового списка:

Возвращается новый список, начинающийся с dummyHead.next, который теперь указывает на первую настоящую ноду после удаления.

Задача: №20. Valid Parentheses #easy

Условие:

Учитывая строку s, содержащую только символы '(', ')', '{', '}', '[' и ']', определите, является ли входная строка допустимой. Входная строка действительна, если: Открытые скобки должны закрываться скобками того же типа.
Открытые скобки должны закрываться в правильном порядке.
Каждой закрывающей скобке соответствует открытая скобка того же типа.

Решение:

class Solution {
    fun isValid(s: String): Boolean {
        
        if (s.length == 1) {
        return false
    }

    val stack = Stack<Char>()

    s.forEach {
        when(it) {
            '(', '[', '{' -> {
                stack.push(it)
            }
            ')', ']', '}' -> {
                if(stack.isEmpty() || !isMatchingPair(stack.pop(), it)) {
                    return false
                }
            }
            else -> return false
        }
    }

    return stack.isEmpty()

    }

fun isMatchingPair(open: Char, close: Char): Boolean {
    return (open == '(' && close == ')')  (open == '[' && close == ']')  (open == '{' && close == '}')
    }
}

Пояснение:
Проверка длины строки:

Сначала проверяется длина строки. Если строка состоит из одного символа, возвращается false, так как невозможно правильно разместить одну скобку.
Использование стека:

Для решения задачи используется стек, структура данных, которая следует принципу LIFO (Last In, First Out). Стек помогает отслеживать открывающиеся скобки и позволяет корректно обрабатывать их пары.
Обход строки:

Для каждой скобки в строке проверяется, является ли она открывающей или закрывающей. Если это открывающая скобка, она добавляется (запихивается) в стек.
Если это закрывающая скобка, сначала проверяется, не пуст ли стек. Если стек пуст, это значит, что нет соответствующей открывающей скобки, и возвращается false.
Если стек не пуст, извлекается (выталкивается) верхний элемент стека и проверяется, соответствует ли он текущей закрывающей скобке с помощью функции isMatchingPair.
Проверка соответствия парных скобок:

Функция isMatchingPair проверяет, соответствует ли пара открывающей и закрывающей скобки. Эта функция возвращает true, если пары совпадают, и false в противном случае.
Проверка пустого стека:

В конце, если стек пустой, это означает, что все открывающие скобки были закрыты корректно, и возвращается true. Если стек не пуст, значит, остались не закрытые скобки, и возвращается false.