Задача: №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.

Задача: 46. Permutations #medium
Условие:

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

Решение:

class Solution {
    fun permute(nums: IntArray): List<List<Int>> {
        val answer: MutableList<List<Int>> = mutableListOf()
        permutations(mutableListOf(), nums.toMutableList(), answer)
        return answer
    }
    
    fun permutations(current: MutableList<Int>, remaining: MutableList<Int>, result: MutableList<List<Int>>) {
        if(remaining.isEmpty()) result.add(current)
        remaining.forEach {
            current.add(it)
            permutations(current.toMutableList(), remaining.toMutableList().also { m -> m.remove(it) }, result)
            current.removeAt(current.size - 1)
        }
    }
}

Пояснение:
Этот код представляет функцию `permute`, которая принимает массив целых чисел `nums` и возвращает все возможные перестановки чисел в этом массиве в виде списка списков целых чисел. Для этого реализована рекурсивная функция `permutations`, которая добавляет все возможные перестановки в список `result`.

При вызове `permute` сначала создается пустой список `answer`, который будет содержать все перестановки. Затем вызывается функция `permutations`, которая принимает три параметра: `current` (текущая перестановка), `remaining` (оставшиеся для перестановки числа) и `result` (список, куда будут добавляться итоговые перестановки).

Функция `permutations` рекурсивно формирует все возможные перестановки чисел из массива `nums`. Она добавляет текущий элемент в `current`, удаляет его из `remaining` и рекурсивно вызывает саму себя. После завершения рекурсивного вызова элемент удаляется из `current`, чтобы подготовиться к следующей комбинации перестановок.

Когда все числа из `nums` в `remaining` закончатся (пустой массив), текущая перестановка `current` добавляется в список результатов `result`.

Затем возвращается список `answer`, содержащий все возможные перестановки чисел из исходного массива `nums`.

Задача: 45. Jump Game ll #medium
Условие:

Вам предоставляется массив целых чисел nums с индексом 0 и длиной n. Изначально вы располагаетесь в nums [0].
Каждый элемент nums [i] представляет максимальную длину прямого перехода от индекса i. Другими словами, если вы находитесь в nums [1], вы можете перейти к любому nums [i + j], где:
• <=j<= nums[i] и
• i+j <n
Возвращает минимальное количество переходов для достижения nums [n -
11. Тестовые примеры генерируются таким образом, чтобы вы могли достичь значений [n - 1].

Решение:

class Solution {
    fun jump(nums: IntArray): Int {
        val m = nums.size
        if(m<2){
            return 0
        }
        val dp = IntArray(m){Int.MAX_VALUE}
        dp[0] = 0
        var t = 0
        for (i in 0 until m){
            for(j in 1 until nums[i]+1){
                if(i+j<m){
                    dp[i+j] = minOf(dp[i+j], dp[i]+1)                    
                }
            }
        }
        return dp[m-1]
    }
}

Пояснение:
Эта функция `jump` принимает массив целых чисел `nums` и возвращает минимальное количество прыжков, необходимых для достижения последнего элемента данного массива.
Сначала мы проверяем размер массива `nums`. Если он меньше 2, то возвращаем 0, так как нет необходимости в прыжках.
Затем мы создаем массив `dp` размером `m`, равным размеру массива `nums`. Для каждого элемента массива `dp` устанавливаем начальное значение `Int.MAX_VALUE`, за исключением первого элемента `dp[0]`, который устанавливаем равным 0, так как количество прыжков до самого себя равно 0.
Затем начинаем итерацию по массиву `nums`. Для каждого элемента `nums[i]` мы начинаем внутренний цикл для прыжков от 1 до `nums[i]`, обновляя элементы массива `dp[i+j]`, если новое значение меньше текущего значения плюс 1.
По завершении всех итераций возвращаем значение из массива `dp[m-1]`, которое представляет минимальное количество прыжков до последнего элемента массива.

Задача: 44. Wildcard Matching #hard
Условие:

Учитывая входную строку (строки) и шаблон (p), реализуйте сопоставление шаблонов с подстановочными знаками с поддержкой '?' и '*', где:
"?'
Соответствует любому отдельному символу.
'*'
Соответствует любой последовательности символов (включая пустую последовательность).
Соответствие должно охватывать всю входную строку (не частичное).

Решение:

class Solution {
    fun isMatch(s: String, p: String): Boolean {
        val ss = s.split("").filter{it -> it != ""}
        val ps = p.split("").filter{it -> it != ""}
        val m = ps.size
        val n = ss.size
        var i1 = 0
        var i2 = 0
        var start = -1
        while (i2 < n){
            if (i1<m && (ps[i1]==ss[i2] || ps[i1]=="?")){
                i1 = i1+1
                i2 = i2+1
            }
            else if(i1<m && ps[i1]=="*"){
                start = i1
                i1 = i1+1
            }
            else if(start != -1){
                i2 = i2-(i1-start-1)+1
                i1 = start+1
            }
            else{
                return false
            }
        }
        while (i1<m && ps[i1]=="*"){
            i1++
        }
        if (i1==m){
            return true
        }
        return false
    }
}

Пояснение:
Данная функция `isMatch` принимает две строки `s` и `p` и проверяет, соответствует ли строка `s` шаблону `p`. В данном случае символ `*` в шаблоне `p` может заменять любую последовательность символов, включая пустую последовательность, а символ `?` может заменять один любой символ.

Для начала мы разделяем строки `s` и `p` на массивы символов, фильтруя пустые строки, которые могут появиться из-за применения `split("")`. Затем мы инициализируем переменные `m` и `n` как размеры массивов `ps` и `ss` соответственно.

Затем мы итерируем по символам в массиве `ss`, используя два указателя `i1` и `i2` для позиций в массивах `ps` и `ss`. Мы также используем переменную `start` для отслеживания начала символа `*` в шаблоне.

В цикле проверяем каждую пару символов из `ps` и `ss`:
- Если символы совпадают или `ps[i1]` равен `?`, увеличиваем оба указателя.
- Если `ps[i1]` равен `*`, запоминаем текущую позицию в `start`.
- Если текущий символ не совпадает и нет символа `*`, то, если мы ранее встретили `*`, сдвигаем указатель `i2` и восстанавливаем `i1` на место начала `*`, чтобы попробовать снова.

После завершения итерации по массиву `ss`, мы проверяем на оставшиеся символы `*` в шаблоне `p` и, если они остались, пропускаем их, так как они могут заменять любое количество символов. Если после этого `i1` равен размеру `ps`, то возвращаем `true`, иначе возвращаем `false`.

Задача: №21. Merge Two Sorted Lists #easy

Условие:

Вам даны заголовки двух отсортированных связанных списков list1 и list2. Объедините два списка в один отсортированный список. Список должен быть составлен путем сращивания узлов первых двух списков. Возвращает заголовок объединенного связанного списка.

Решение:

class Solution {
    fun mergeTwoLists(list1: ListNode?, list2: ListNode?): ListNode? {
        if (list1 == null && list2 == null) {
            return null
        }
        if (list1 == null) {
            return list2
        }
        if (list2 == null) {
            return list1
        }
        if (list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2)
            return list1
        }
        list2.next = mergeTwoLists(list2.next, list1)
        return list2
    }
}

Пояснение:
Проверка на null:

Первые три условия в методе обрабатывают случаи, когда один из входных списков (list1 или list2) равен null. Если оба списка пусты, метод возвращает null.
Если один из списков пуст, возвращается другой список, так как объединение с пустым списком невозможно.
Рекурсивное слияние:

Метод работает путем сравнения значений текущих узлов list1 и list2.
Если значение в list1 меньше значения в list2, текущий узел list1 становится частью результирующего списка, и метод рекурсивно вызывается для объединения следующего узла list1 с list2.
Если значение в list2 меньше или равно значению в list1, аналогично текущий узел list2 становится частью результирующего списка, и метод рекурсивно вызывается для объединения list1 с следующим узлом list2.
Возвращение результата:

После каждого рекурсивного вызова текущий узел (выбранный на основе сравнения) присоединяется к результирующему списку, и метод возвращает текущий узел.
Рекурсивные вызовы продолжаются, пока не будут объединены все узлы из обоих списков.
Временная сложность:
Время: O(n)
Память: O(1)

Задача: 22. Generate Parentheses #medium
Условие:

Учитывая n пар круглых скобок, напишите функцию, которая генерирует все комбинации правильных круглых скобок.

Решение:

class Solution {
fun generateParenthesis(n: Int): List<String> {
    val list = ArrayList<String>()
    x(charArrayOf(),n,n,list)


return list
}

fun x(str:CharArray, left:Int, right:Int,list:ArrayList<String>){
    if (left==0 && right==0) {
        list.add(String(str))
    }
    else {
        if (left <= right && left!=0) x(str.plus('('), left - 1, right,list)
        if (right!=0) x(str.plus(')'), left, right - 1,list)
    }
}
}

Пояснение:
Данный код на языке Kotlin реализует функцию `generateParenthesis`, которая генерирует все возможные комбинации правильных скобочных последовательностей длины `n`. Функция использует рекурсивный подход для создания этих комбинаций.

В функции `generateParenthesis` создается список `list`, в который будут добавлены все сгенерированные комбинации. Затем вызывается функция `x` с пустым массивом символов, начальными значениями `n` для левых и правых скобок и самим списком, в который будут добавляться результаты.

Функция `x` рекурсивно генерирует все комбинации скобок. Если количество оставшихся левых и правых скобок равно 0, то текущая комбинация считается правильной и добавляется в список. В противном случае рекурсивно вызываются два варианта: добавление открывающей скобки '(' и уменьшение количества оставшихся левых скобок или добавление закрывающей скобки ')' и уменьшение количества оставшихся правых скобок.

Этот код позволяет сгенерировать все правильные скобочные последовательности длины `n` и представить их в виде списка строк.

Задача: 23. Merge k Sorted Lists #hard
Условие:

Вам дан массив из k списков связанных списков, каждый связанный список отсортирован в порядке возрастания.

Объедините все связанные списки в один отсортированный связанный список и верните его.

Решение:

class Solution {
  fun mergeKLists(lists: Array<ListNode?>): ListNode? {
    val pq = PriorityQueue<ListNode>() { a, b -> a.`val` - b.`val` }
    lists.filter { it != null }.forEach { pq.add(it) }
    val res = ListNode(-1)
    var tail = res
    while (pq.isNotEmpty()) {
      val head = pq.poll()
      tail.next = head
      tail = tail.next!!
      if (head.next != null)
        pq.add(head.next)
    }
    return res.next
  }
}

Пояснение:
Данный код на языке Kotlin реализует функцию `mergeKLists`, которая объединяет K упорядоченных связанных списков (где K представлены в виде массива `lists`) в один упорядоченный связанный список. В данном случае, используется очередь с приоритетом (PriorityQueue) для упорядочивания узлов списка по значению.

1. Создается приоритетная очередь `pq`, которая будет хранить узлы списка в порядке возрастания их значений.
2. Итерируемся по массиву `lists`, фильтруем `null` значения, и добавляем все ненулевые узлы в приоритетную очередь `pq`.
3. Создается новый узел `res` со значением -1 как заголовочный узел нового связанного списка.
4. Инициализируется переменная `tail` ссылающаяся на заголовочный узел `res`.
5. Пока приоритетная очередь `pq` не пуста, выполняем следующие действия:
- Извлекаем из очереди `pq` узел с наименьшим значением (головной узел).
- Присоединяем головной узел к концу нового списка, увеличиваем `tail` и переходим к следующему узлу.
- Если у узла головы списка есть следующий элемент, добавляем его в приоритетную очередь для дальнейшего учета.
6. Возвращаем следующий узел после заголовочного узла `res` в итоговом связанном списке.

Данный код позволяет объединить K упорядоченных связанных списков в один упорядоченный список и возвращает указатель на начало этого объединенного списка.

Задача: 24. Swap Nodes in Pairs #medium
Условие:

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

Решение:

class Solution {
  fun swapPairs(head: ListNode?): ListNode? {
    val dummy = ListNode(-1)
    var head = head
    var cur: ListNode? = dummy
    while (head != null) {
      val A = head
      head = head.next
      val B = head
      head = head?.next
      if (B == null) {
        cur!!.next = A
      } else {
        B.next = A
        A.next = null
        cur!!.next = B
        cur = A
      }
    }
    return dummy.next
  }
}

Пояснение:
Данный код реализует функцию `swapPairs`, которая меняет местами каждые два соседних узла в связанном списке, начиная с головного узла. Используется итеративный подход для этой задачи.

1. Создается новый узел `dummy` с значением -1 в качестве заглушки для нового связанного списка.
2. Инициализируются переменные `head` и `cur`, которые указывают на голову и на текущий узел (начиная с заглушки) соответственно.
3. Пока `head` не равен `null`, выполняем следующие действия:
- Создаем узлы `A` и `B` для текущей пары узлов для обмена и переходим к следующей паре узлов.
- Если второй узел `B` отсутствует, просто присоединяем узел `A` к текущему узлу `cur`.
- В противном случае, меняем местами узлы `A` и `B`, обновляем их ссылки на следующие узлы и присоединяем узел `B` к текущему узлу `cur`, затем переходим к узлу `A` для следующей итерации.
4. Возвращаем следующий узел после заглушки `dummy` в итоговом связанном списке, который будет содержать узлы, поменявшиеся местами парами.

Этот код решает задачу обмена местами каждых двух соседних узлов в связанном списке и возвращает указатель на начало измененного списка.

Задача: 25. Reverse Nodes in k-Group #hard
Условие:

Учитывая заголовок связанного списка, поменяйте местами узлы списка k за раз и верните измененный список.

k — целое положительное число, меньшее или равное длине связанного списка. Если количество узлов не кратно k, то пропущенные узлы в конечном итоге должны остаться такими, какие они есть.

Вы не можете изменять значения в узлах списка, можно изменять только сами узлы.

Решение:

import java.util.Stack
class Solution {
    fun reverseKGroup(head: ListNode?, k: Int): ListNode? {
        if (head == null) return null

        var num = k
        var first = head
        var last = head


        while (--num > 0 && last != null) {
            last = last.next
        }

        if (last != null) {
            var nextHead = last.next
            val stack = Stack<ListNode>()
            while (first != last) {
                stack.push(first)
                first = first!!.next
            }

            while (!stack.empty()) {
                last!!.next = stack.pop()
                last = last!!.next
            }

            last!!.next = reverseKGroup(nextHead, k)
        }

        return first
    }
}

Пояснение:
Данный код на языке Kotlin реализует функцию `reverseKGroup`, которая разворачивает связанный список группами по `k` элементов. Для этого используется рекурсивный подход и стек для обращения групп узлов.

1. Если головной узел `head` равен `null`, то функция вернет `null` (базовый случай для рекурсии).
2. Инициализируются переменные `num` (количество узлов в текущей группе), `first` (указатель на первый узел текущей группы), и `last` (указатель на последний узел текущей группы).
3. Пока `num` не равен 0 и `last` не равен `null`, сдвигаем указатель `last` на `k` узлов.
4. Если `last` не равен `null`, выполним следующие действия:
- Инициализируются переменная `nextHead` (указатель на начало следующей группы), и стек `Stack<ListNode>`.
- Пока `first` не равен `last`, помещаем узлы текущей группы в стек.
- Извлекаем узлы из стека и связываем их в обратном порядке с узлом `last`.
- Рекурсивно вызываем `reverseKGroup` для следующей группы, указывая начало новой группы и `k`.
5. Возвращаем указатель на головной узел первой группы после обращения.

Этот код позволяет развернуть связанный список группами по `k` элементов и вернуть указатель на голову списка после обращения по группам.

Задача: 26. Remove Duplicates from Sorted Array #easy
Условие:
Учитывая целочисленный массив чисел, отсортированный в неубывающем порядке, удалите дубликаты на месте так, чтобы каждый уникальный элемент появлялся только один раз. Относительный порядок элементов должен оставаться неизменным. Затем верните количество уникальных элементов в числах.

Считайте, что количество уникальных элементов чисел равно k. Чтобы вас приняли, вам нужно сделать следующее:

Измените массив nums так, чтобы первые k элементов nums содержали уникальные элементы в том порядке, в котором они присутствовали в nums изначально. Остальные элементы nums не важны, как и размер nums.
Вернуть К.
Решение:

fun removeDuplicates(nums: IntArray): Int {

    if (nums.isEmpty()) return 0

    var lastIdx = 1
    var curVal = nums[0]

    nums.forEachIndexed { i, _ ->
        if (nums[i] > curVal) {
            curVal = nums[i]
            nums[lastIdx] = nums[i]
            lastIdx++
        }
    }

    return lastIdx
}`

Пояснение:
Код, который был представлен, решает задачу удаления дубликатов из массива `nums`. При этом он оставляет только уникальные элементы и возвращает количество этих уникальных элементов.

Алгоритм работает следующим образом:
1. Если массив `nums` пустой (`.isEmpty()`), то функция возвращает 0, так как в пустом массиве нет дубликатов.
2. Инициализируются переменные `lastIdx` (индекс для записи уникальных чисел) и `curVal` (текущее значение для сравнения), первый уникальный элемент - `nums[0]`.
3. Проходим по всем элементам массива `nums`, используя `forEachIndexed`. Если текущий элемент больше `curVal`, то:
- Обновляем `curVal` на текущее значение элемента.
- Записываем это уникальное значение в массив `nums` на позицию `lastIdx` и увеличиваем `lastIdx` на 1.

Таким образом, после выполнения функции, массив `nums` будет содержать только уникальные элементы до позиции `lastIdx`, а функция вернет количество уникальных элементов.

Задача: 27. Remove Element #easy
Условие:

Учитывая целочисленный массив nums и целочисленное значение, удалите все вхождения val в nums на месте. Порядок элементов может быть изменен. Затем верните количество элементов в виде чисел, которые не равны val.

Учитывайте количество элементов в nums, которые не равны val be k. Чтобы вас приняли, вам необходимо сделать следующее:

Измените массив nums так, чтобы первые k элементов nums содержали элементы, не равные val. Остальные элементы nums не важны, как и размер nums.
Вернуть К.

Решение:

  fun removeElement(nums: IntArray, `val`: Int): Int {
        val c = nums.filter { it != `val` }
        for ((a, b) in c.withIndex()) { nums[a] = b }
        return c.size
    }

Пояснение:
Данный код на языке Kotlin реализует функцию `removeElement`, которая удаляет все вхождения определенного значения `val` из массива `nums`. Алгоритм работы функции следующий:
1. С помощью функции `filter` создается новый массив `c`, в который включаются все элементы массива `nums`, кроме тех, которые равны значению `val`.
2. Затем происходит обновление исходного массива `nums` путем замены элементов на значения из массива `c` с помощью итерации по парам элементов массива `c` с использованием `withIndex()`.
3. Функция возвращает размер нового массива `c`, который содержит все элементы, кроме удаленных элементов со значением `val`.

Этот код позволяет эффективно удалять все вхождения определенного значения из массива и возвращает количество элементов после удаления.

Задача: 28. Find the Index of the First Occurrence in a String #easy
Условие:

Учитывая две строки, игла и стог сена, верните индекс первого вхождения иглы в стоге сена или -1, если игла не является частью стога сена.

Решение:

class Solution {
    fun strStr(haystack: String, needle: String): Int {
        return haystack.indexOf(needle)
    }
}

Пояснение:
Данный код представляет собой решение задачи нахождения подстроки `needle` в строке `haystack` с использованием встроенной функции Kotlin `indexOf`.

В данном случае, метод `indexOf` вызывается на строке `haystack`, и передается подстрока `needle` в качестве аргумента. Если подстрока `needle` содержится в строке `haystack`, метод вернет индекс первого вхождения данной подстроки в строке. В случае, если подстрока не найдена, метод вернет -1.

Задача: 29. Divide Two Integers #medium
Условие:

Учитывая два целых числа: делимое и делитель, разделите два целых числа, не используя операторы умножения, деления и модификатора.

Целочисленное деление должно сокращаться до нуля, что означает потерю дробной части. Например, 8,345 будет сокращено до 8, а -2,7335 будет сокращено до -2.

Возвращает частное после деления делимого на делитель.

Примечание. Предположим, мы имеем дело со средой, которая может хранить целые числа только в пределах 32-битного целого диапазона со знаком: [−2^31, 2^31 − 1]. В этой задаче, если частное строго больше 2^31 - 1, верните 2^31 - 1, а если частное строго меньше -2^31, верните -2^31.

Решение:

class Solution {
  fun divide(dividend: Int, divisor: Int): Int {

    var isNegtive = (dividend > 0 && divisor < 0 || dividend < 0 && divisor > 0)
    var dividendLong = Math.abs(dividend.toLong())
    var divisorLong = Math.abs(divisor.toLong())

    var i = 0
    while ((divisorLong shl  i) <= dividendLong) {
      i ++
    }

    var res = 0L
    (i - 1 downTo 0)
        .forEach {
          val cur = (divisorLong shl  it)
          if (dividendLong >= cur) {
            res += (1L shl  it)
            dividendLong -= cur
          }
        }

    return if (isNegtive) {
      -res.toInt()
    } else {
      Math.min(Int.MAX_VALUE.toLong(), res).toInt()
    }
  }
}

Пояснение:
Данный код представляет собой реализацию функции `divide`, которая выполняет деление двух чисел `dividend` на `divisor`. Алгоритм реализации деления использует битовые операции и циклы для нахождения результата деления без использования оператора деления `/`.

Вот как работает данный код:
1. Определяется знак результата деления `isNegtive` на основе знаков исходных чисел `dividend` и `divisor`.
2. Преобразуются исходные числа `dividend` и `divisor` в тип `Long`, что позволяет работать с числами большей длины и исключить возможность переполнения.
3. Выполняется цикл, в котором находится максимальное значение `i`, такое что `divisorLong shl i` не превышает `dividendLong`. Это позволяет определить первую часть результата деления.
4. Затем, начиная с максимального `i`, определяется каждый бит в результате деления путем проверки, можно ли вычесть соответствующее кратное `divisorLong` из `dividendLong`.
5. Итоговый результат деления возвращается с учетом знака и ограничений на диапазон.

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

Задача: 30. Substring with Concatenation of All Words #hard
Условие:

Вам дана строка s и массив строк-слов. Все строки слов имеют одинаковую длину.

Объединенная строка — это строка, которая в точности содержит все строки любой перестановки объединенных слов.

Например, если слова = ["ab", "cd", "ef"], то "abcdef", "abefcd", "cdabef", "cdefab", "efabcd" и "efcdab" являются объединенными строками. «acdbef» не является объединенной строкой, поскольку не является объединением какой-либо перестановки слов.
Возвращает массив начальных индексов всех объединенных подстрок в s. Вы можете вернуть ответ в любом порядке.

Решение:

class Solution {
    fun findSubstring(s: String, words: Array<String>): List<Int> {
        val ml = mutableListOf<Int>()
        if (s == ""){
            return ml
        }
        if (words.size == 0){
            return ml
        }
        val w = words.sorted().groupingBy{it}.eachCount()
        val ws = words[0].length * words.size
        for (i in 0 until s.length - ws + 1){
            if (s
                    .substring(i until i+ws)
                    .chunked(words[0].length)
                    .sorted()
                    .groupingBy{it}
                    .eachCount()
                    .equals(w)){
                ml.add(i)
            }
        }
        return ml
    }
}

Пояснение:
Код был разработан для нахождения всех подстрок в строке `s`, которые содержат в себе все слова из массива `words`. Алгоритм предполагает создание пустого списка `ml`, который будет содержать индексы начала каждой подстроки, удовлетворяющей условиям задачи. Затем проводятся проверки базовых случаев: если строка `s` пустая или массив `words` пустой, функция возвращает пустой список.

Для каждой возможной подстроки в строке `s` проверяется, содержит ли она все слова из массива `words`. Для этого выполняются следующие шаги:
1. Подстрока длиной `ws` (суммарной длиной всех слов из `words`) начиная с текущего индекса `i`, делится на слова равной длины из `words[0]` с помощью метода `chunked`, сохраняется порядок слов.
2. Слова в подстроке сортируются.
3. Подсчитывается количество вхождений каждого слова сгруппированных слов в подстроке.
4. Результат обработки сравнивается с результатом группировки и подсчёта слов из `words`. Если совпадает, то индекс начала подстроки `i` добавляется в список `ml`.

В итоге, функция `findSubstring` возвращает список индексов начала всех подстрок в строке `s`, которые содержат все слова из массива `words`. Необходимо тестировать данный код на различных входных данных, чтобы убедиться, что он работает корректно во всех сценариях использования.