#medium
Задача: 31. Next Permutation

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

Например, для arr = [1,2,3] следующие являются всеми перестановками arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].
Следующая перестановка массива целых чисел — это следующая лексикографически большая перестановка его чисел. Более формально, если все перестановки массива отсортированы в одном контейнере по лексикографическому порядку, то следующая перестановка этого массива — это перестановка, следующая за ней в отсортированном контейнере. Если такое упорядочивание невозможно, массив должен быть переупорядочен в наименьший возможный порядок (то есть отсортирован по возрастанию).

Например, следующая перестановка arr = [1,2,3] — это [1,3,2].
Аналогично, следующая перестановка arr = [2,3,1] — это [3,1,2].
В то время как следующая перестановка arr = [3,2,1] — это [1,2,3], потому что [3,2,1] не имеет лексикографически большего переупорядочивания.

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

Замена должна быть выполнена на месте и использовать только постоянную дополнительную память.

Пример:

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

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

1️⃣Мы меняем местами числа a[i−1] и a[j]. Теперь у нас есть правильное число на индексе i−1. Однако текущая перестановка ещё не является той перестановкой, которую мы ищем. Нам нужна наименьшая перестановка, которая может быть сформирована с использованием чисел только справа от a[i−1]. Следовательно, нам нужно расположить эти числа в порядке возрастания, чтобы получить их наименьшую перестановку.

2️⃣Однако, вспомните, что, сканируя числа справа налево, мы просто уменьшали индекс, пока не нашли пару a[i] и a[i−1], где a[i] > a[i−1]. Таким образом, все числа справа от a[i−1] уже были отсортированы в порядке убывания. Более того, обмен местами a[i−1] и a[j] не изменил этот порядок.

3️⃣Поэтому нам просто нужно перевернуть числа, следующие за a[i−1], чтобы получить следующую наименьшую лексикографическую перестановку.

😎 Решение:

class Solution {
    fun nextPermutation(nums: IntArray) {
        var i = nums.size - 2
        while (i >= 0 && nums[i + 1] <= nums[i]) {
            i--
        }
        if (i >= 0) {
            var j = nums.size - 1
            while (nums[j] <= nums[i]) {
                j--
            }
            swap(nums, i, j)
        }
        reverse(nums, i + 1)
    }

    private fun reverse(nums: IntArray, start: Int) {
        var i = start
        var j = nums.size - 1
        while (i < j) {
            swap(nums, i, j)
            i++
            j--
        }
    }

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

🪙 1078 вопроса вопроса на Andorid разработчика

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 32. Longest Valid Parentheses

Дана строка, содержащая только символы '(' и ')'. Верните длину самой длинной подстроки с корректными (правильно сформированными) скобками.

Пример:

Input: s = "(()"
Output: 2

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

1️⃣В этом подходе мы рассматриваем каждую возможную непустую подстроку чётной длины из заданной строки и проверяем, является ли она корректной строкой скобок. Для проверки корректности мы используем метод стека.

2️⃣Каждый раз, когда мы встречаем символ ‘(’, мы кладём его в стек. Для каждого встреченного символа ‘)’ мы извлекаем из стека символ ‘(’. Если символ ‘(’ недоступен в стеке для извлечения в любой момент или если в стеке остались элементы после обработки всей подстроки, подстрока скобок является некорректной.

3️⃣Таким образом, мы повторяем процесс для каждой возможной подстроки и продолжаем сохранять длину самой длинной найденной корректной строки.

😎 Решение:

fun isValid(s: String): Boolean {
    val stack = mutableListOf<Char>()
    for (char in s) {
        if (char == '(') {
            stack.add('(')
        } else if (stack.isNotEmpty() && stack.last() == '(') {
            stack.removeAt(stack.size - 1)
        } else {
            return false
        }
    }
    return stack.isEmpty()
}

fun longestValidParentheses(s: String): Int {
    var maxlen = 0
    for (i in 0 until s.length) {
        for (j in i + 2..s.length step 2) {
            val substring = s.substring(i, j)
            if (isValid(substring)) {
                maxlen = maxOf(maxlen, j - i)
            }
        }
    }
    return maxlen
}

🪙 1078 вопроса вопроса на Andorid разработчика

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 33. Search in Rotated Sorted Array

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

Перед передачей в вашу функцию массив nums может быть повёрнут в неизвестном индексе поворота k (1 <= k < nums.length), так что результирующий массив будет иметь вид [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (с индексацией с нуля). Например, [0,1,2,4,5,6,7] может быть повёрнут в индексе поворота 3 и стать [4,5,6,7,0,1,2].

Для данного массива nums после возможного поворота и целого числа target, верните индекс target, если он есть в массиве, или -1, если его нет в массиве.

Вы должны написать алгоритм с временной сложностью O(log n).

Пример:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

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

1️⃣Выполните двоичный поиск для определения индекса поворота, инициализируя границы области поиска значениями left = 0 и right = n - 1. Пока left < right:
Пусть mid = left + (right - left) // 2.
Если nums[mid] > nums[n - 1], это предполагает, что точка поворота находится справа от mid, следовательно, мы устанавливаем left = mid + 1. В противном случае, поворот может находиться на позиции mid или левее от mid, в этом случае мы должны установить right = mid.

2️⃣По завершении двоичного поиска мы имеем индекс поворота, обозначенный как pivot = left.
nums состоит из двух отсортированных подмассивов, nums[0 ~ left - 1] и nums[left ~ n - 1].

3️⃣Выполните двоичный поиск по подмассиву nums[0 ~ left - 1] для поиска target. Если target находится в этом подмассиве, верните его индекс.
В противном случае выполните двоичный поиск по подмассиву nums[left ~ n - 1] для поиска target. Если target находится в этом подмассиве, верните его индекс. В противном случае верните -1.

😎 Решение:

class Solution {
    fun search(nums: IntArray, target: Int): Int {
        val n = nums.size
        var left = 0
        var right = n - 1
        while (left <= right) {
            val mid = (left + right) / 2
            if (nums[mid] > nums[n - 1]) {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }

        val answer = binarySearch(nums, 0, left - 1, target)
        if (answer != -1) {
            return answer
        }

        return binarySearch(nums, left, n - 1, target)
    }

    private fun binarySearch(nums: IntArray, leftBoundary: Int, rightBoundary: Int, target: Int): Int {
        var left = leftBoundary
        var right = rightBoundary
        while (left <= right) {
            val mid = (left + right) / 2
            if (nums[mid] == target) {
                return mid
            } else if (nums[mid] > target) {
                right = mid - 1
            } else {
                left = mid + 1
            }
        }

        return -1
    }
}

🪙 1078 вопроса вопроса на Andorid разработчика

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 34. Find First and Last Position of Element in Sorted Array

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

Если целевое значение не найдено в массиве, верните [-1, -1].

Вы должны написать алгоритм со временной сложностью O(log n).

Пример:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

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

1️⃣Определите функцию под названием findBound, которая принимает три аргумента: массив, целевое значение для поиска и булевое значение isFirst, указывающее, ищем ли мы первое или последнее вхождение цели.
Мы используем 2 переменные для отслеживания подмассива, который мы сканируем. Назовем их begin и end. Изначально begin устанавливается в 0, а end — в последний индекс массива.

2️⃣Мы итерируем, пока begin не станет больше, чем end.
На каждом шаге мы вычисляем средний элемент mid = (begin + end) / 2. Мы используем значение среднего элемента, чтобы решить, какую половину массива нам нужно искать.
Если nums[mid] == target:
Если isFirst true — это означает, что мы пытаемся найти первое вхождение элемента. Если mid == begin или nums[mid - 1] != target, тогда мы возвращаем mid как первое вхождение цели. В противном случае мы обновляем end = mid - 1.
Если isFirst false — это означает, что мы пытаемся найти последнее вхождение элемента. Если mid == end или nums[mid + 1] != target, тогда мы возвращаем mid как последнее вхождение цели. В противном случае мы обновляем begin = mid + 1.

3️⃣Если nums[mid] > target — мы обновляем end = mid - 1, так как мы должны отбросить правую сторону массива, поскольку средний элемент больше цели.
Если nums[mid] < target — мы обновляем begin = mid + 1, так как мы должны отбросить левую сторону массива, поскольку средний элемент меньше цели.
В конце нашей функции мы возвращаем значение -1, что указывает на то, что цель не найдена в массиве.
В основной функции searchRange мы сначала вызываем findBound с isFirst, установленным в true. Если это значение равно -1, мы можем просто вернуть [-1, -1]. В противном случае мы вызываем findBound с isFirst, установленным в false, чтобы получить последнее вхождение, а затем возвращаем результат.

😎 Решение:

class Solution {
    fun searchRange(nums: IntArray, target: Int): IntArray {
        val firstOccurrence = findBound(nums, target, true)

        if (firstOccurrence == -1) {
            return intArrayOf(-1, -1)
        }

        val lastOccurrence = findBound(nums, target, false)

        return intArrayOf(firstOccurrence, lastOccurrence)
    }

    private fun findBound(nums: IntArray, target: Int, isFirst: Boolean): Int {
        var begin = 0
        var end = nums.size - 1

        while (begin <= end) {
            val mid = (begin + end) / 2

            if (nums[mid] == target) {
                if (isFirst) {
                    if (mid == begin || nums[mid - 1] != target) {
                        return mid
                    }
                    end = mid - 1
                } else {
                    if (mid == end || nums[mid + 1] != target) {
                        return mid
                    }
                    begin = mid + 1
                }
            } else if (nums[mid] > target) {
                end = mid - 1
            } else {
                begin = mid + 1
            }
        }

        return -1
    }
}

🪙 1078 вопроса вопроса на Andorid разработчика

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 35. Search Insert Position

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

Вы должны написать алгоритм со временной сложностью O(log n).

Пример:

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

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

1️⃣Инициализируйте указатели left и right: left = 0, right = n - 1.

2️⃣Пока left <= right:
Сравните средний элемент массива nums[pivot] с целевым значением target.
Если средний элемент является целевым, то есть target == nums[pivot]: верните pivot.
Если цель не найдена:
Если target < nums[pivot], продолжайте поиск в левом подмассиве. right = pivot - 1.
Иначе продолжайте поиск в правом подмассиве. left = pivot + 1.
3️⃣Верните left.

😎 Решение:

class Solution {
    fun searchInsert(nums: IntArray, target: Int): Int {
        var left = 0
        var right = nums.size - 1
        while (left <= right) {
            val pivot = left + (right - left) / 2
            if (nums[pivot] == target) {
                return pivot
            }
            if (target < nums[pivot]) {
                right = pivot - 1
            } else {
                left = pivot + 1
            }
        }
        return left
    }
}

🪙 1078 вопроса вопроса на Andorid разработчика

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 36. Valid Sudoku

Определите, является ли доска Судоку размером 9 на 9 валидной. Необходимо проверить только заполненные ячейки согласно следующим правилам:

Каждая строка должна содержать цифры от 1 до 9 без повторений.
Каждый столбец должен содержать цифры от 1 до 9 без повторений.
Каждая из девяти подзон размером 3 на 3 в сетке должна содержать цифры от 1 до 9 без повторений.

Пример:

Input: board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true

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

1️⃣Инициализируйте список из 9 хеш-множеств, где хеш-множество с индексом r будет использоваться для хранения ранее увиденных чисел в строке r судоку. Аналогично инициализируйте списки из 9 хеш-множеств для отслеживания столбцов и блоков.

2️⃣Итерируйтесь по каждой позиции (r, c) в судоку. На каждой итерации, если на текущей позиции есть число:
Проверьте, существует ли это число в хеш-множестве для текущей строки, столбца или блока. Если да, верните false, потому что это второе появление числа в текущей строке, столбце или блоке.

3️⃣В противном случае обновите множество, отвечающее за отслеживание ранее увиденных чисел в текущей строке, столбце и блоке. Индекс текущего блока рассчитывается как (r / 3) * 3 + (c / 3), где / означает деление нацело.
Если дубликаты не были найдены после посещения каждой позиции на доске судоку, то судоку валидно, поэтому верните true.

😎 Решение:

class Solution {
    fun isValidSudoku(board: Array<Array<Char>>): Boolean {
        val N = 9

        val rows = Array(N) { mutableSetOf<Char>() }
        val cols = Array(N) { mutableSetOf<Char>() }
        val boxes = Array(N) { mutableSetOf<Char>() }

        for (r in 0 until N) {
            for (c in 0 until N) {
                val value = board[r][c]
                if (value == '.') continue

                if (value in rows[r]) return false
                rows[r].add(value)

                if (value in cols[c]) return false
                cols[c].add(value)

                val idx = (r / 3) * 3 + (c / 3)
                if (value in boxes[idx]) return false
                boxes[idx].add(value)
            }
        }

        return true
    }
}

🪙 1078 вопроса вопроса на Andorid разработчика

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 37. Sudoku Solver

Напишите программу для решения головоломки Судоку, заполнив пустые ячейки.

Решение Судоку должно удовлетворять всем следующим правилам:

Каждая из цифр от 1 до 9 должна встречаться ровно один раз в каждой строке.
Каждая из цифр от 1 до 9 должна встречаться ровно один раз в каждом столбце.
Каждая из цифр от 1 до 9 должна встречаться ровно один раз в каждом из 9 подблоков 3x3 сетки.
Символ '.' обозначает пустые ячейки.

Пример:

Input: board = 
[["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]]
Output: 
[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]

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

1️⃣Теперь все готово для написания функции обратного поиска backtrack(row = 0, col = 0). Начните с верхней левой ячейки row = 0, col = 0. Продолжайте, пока не дойдете до первой свободной ячейки.

2️⃣Итерируйте по числам от 1 до 9 и попробуйте поставить каждое число d в ячейку (row, col).
Если число d еще не в текущей строке, столбце и блоке:
Поместите d в ячейку (row, col).
Запишите, что d теперь присутствует в текущей строке, столбце и блоке.

3️⃣Если вы на последней ячейке row == 8, col == 8:
Это означает, что судоку решено.
В противном случае продолжайте размещать дальнейшие числа.
Откат, если решение еще не найдено: удалите последнее число из ячейки (row, col).

😎 Решение:

import java.util.*

class Solution {
    fun solveSudoku(board: Array<CharArray>) {
        val n = 3
        val N = n * n
        val rows = List(N) { mutableMapOf<Char, Int>() }
        val cols = List(N) { mutableMapOf<Char, Int>() }
        val boxes = List(N) { mutableMapOf<Char, Int>() }

        fun placeOrRemove(d: Char, r: Int, c: Int, add: Boolean = true) {
            val idx = (r / n) * n + (c / n)
            rows[r][d] = rows[r].getOrDefault(d, 0) + (if (add) 1 else -1)
            cols[c][d] = cols[c].getOrDefault(d, 0) + (if (add) 1 else -1)
            boxes[idx][d] = boxes[idx].getOrDefault(d, 0) + (if (add) 1 else -1)
            board[r][c] = if (add) d else '.'
            if (rows[r][d] == 0) rows[r].remove(d)
            if (cols[c][d] == 0) cols[c].remove(d)
            if (boxes[idx][d] == 0) boxes[idx].remove(d)
        }

        fun canPlace(d: Char, r: Int, c: Int): Boolean {
            val idx = (r / n) * n + (c / n)
            return !(d in rows[r] || d in cols[c] || d in boxes[idx])
        }

        fun backtrack(r: Int = 0, c: Int = 0): Boolean {
            if (c == N) {
                r += 1; c = 0
            }
            if (r == N) return true
            if (board[r][c] == '.') {
                for (d in '1'..'9') {
                    if (canPlace(d, r, c)) {
                        placeOrRemove(d, r, c, true)
                        if (backtrack(r, c + 1)) return true
                        placeOrRemove(d, r, c, false)
                    }
                }
            } else {
                return backtrack(r, c + 1)
            }
            return false
        }

        for (r in 0 until N) {
            for (c in 0 until N) {
                if (board[r][c] != '.') {
                    placeOrRemove(board[r][c], r, c, true)
                }
            }
        }

        backtrack()
    }
}

🪙 1078 вопроса вопроса на Andorid разработчика

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 38. Count and Say

Последовательность "считай и скажи" — это последовательность строк цифр, определяемая с помощью рекурсивной формулы:

countAndSay(1) = "1"
countAndSay(n) — это кодирование длин серий из countAndSay(n - 1).
Кодирование длин серий (RLE) — это метод сжатия строк, который работает путём замены последовательных идентичных символов (повторяющихся 2 или более раз) на конкатенацию символа и числа, обозначающего количество символов (длину серии). Например, чтобы сжать строку "3322251", мы заменяем "33" на "23", "222" на "32", "5" на "15" и "1" на "11". Таким образом, сжатая строка становится "23321511".

Для заданного положительного целого числа n верните n-й элемент последовательности "считай и скажи".

Пример:

Input: n = 4

Output: "1211"

Explanation:

countAndSay(1) = "1"
countAndSay(2) = RLE of "1" = "11"
countAndSay(3) = RLE of "11" = "21"
countAndSay(4) = RLE of "21" = "1211"

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

1️⃣Мы хотим использовать шаблон, который соответствует строкам из одинаковых символов, таких как "4", "7777", "2222222".
Если у вас есть опыт работы с регулярными выражениями, вы можете обнаружить, что шаблон (.)\1* работает.

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

3️⃣*: этот квалификатор, следующий за ссылкой на группу \1, указывает, что мы хотели бы видеть повторение группы ноль или более раз.
Таким образом, шаблон соответствует строкам, которые состоят из некоторого символа, а затем ноль или более повторений этого символа после его первого появления. Это то, что нам нужно.
Мы находим все совпадения с регулярным выражением, а затем конкатенируем результаты.

😎 Решение:

class Solution {
    fun countAndSay(n: Int): String {
        var s = "1"
        for (i in 2..n) {
            var t = ""
            val regex = Regex("(.)\\1*")
            regex.findAll(s).forEach { match ->
                t += "${match.value.length}${match.value[0]}"
            }
            s = t
        }
        return s
    }
}

🪙 1078 вопроса вопроса на Andorid разработчика

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 39. Combination Sum

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

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

Тестовые случаи сгенерированы таким образом, что количество уникальных комбинаций, дающих в сумме target, меньше 150 комбинаций для данного ввода.

Пример:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

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

1️⃣Как видно, вышеописанный алгоритм обратного отслеживания разворачивается как обход дерева в глубину (DFS - Depth-First Search), который часто реализуется с помощью рекурсии.
Здесь мы определяем рекурсивную функцию backtrack(remain, comb, start) (на Python), которая заполняет комбинации, начиная с текущей комбинации (comb), оставшейся суммы для выполнения (remain) и текущего курсора (start) в списке кандидатов.
Следует отметить, что сигнатура рекурсивной функции немного отличается в Java, но идея остается той же.

2️⃣Для первого базового случая рекурсивной функции, если remain == 0, то есть мы достигаем желаемой целевой суммы, поэтому мы можем добавить текущую комбинацию в итоговый список.
Как другой базовый случай, если remain < 0, то есть мы превышаем целевое значение, мы прекращаем исследование на этом этапе.

3️⃣Помимо вышеупомянутых двух базовых случаев, мы затем продолжаем исследовать подсписок кандидатов, начиная с [start ... n].
Для каждого из кандидатов мы вызываем рекурсивную функцию саму с обновленными параметрами.
Конкретно, мы добавляем текущего кандидата в комбинацию.
С добавленным кандидатом у нас теперь меньше суммы для выполнения, то есть remain - candidate.
Для следующего исследования мы все еще начинаем с текущего курсора start.
В конце каждого исследования мы делаем откат, удаляя кандидата из комбинации.

😎 Решение:

class Solution {
    fun combinationSum(candidates: IntArray, target: Int): List<List<Int>> {
        val results = mutableListOf<List<Int>>()

        fun backtrack(remain: Int, comb: MutableList<Int>, start: Int) {
            when {
                remain == 0 -> {
                    results.add(ArrayList(comb))
                    return
                }
                remain < 0 -> return
                else -> {
                    for (i in start until candidates.size) {
                        comb.add(candidates[i])
                        backtrack(remain - candidates[i], comb, i)
                        comb.removeAt(comb.size - 1)
                    }
                }
            }
        }

        backtrack(target, mutableListOf(), 0)
        return results
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 40. Combination Sum II

Дана коллекция кандидатов (candidates) и целевое число (target). Найдите все уникальные комбинации в candidates, где числа кандидатов в сумме дают target.

Каждое число в candidates может быть использовано только один раз в комбинации.

Примечание: Набор решений не должен содержать повторяющихся комбинаций.

Пример:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: 
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

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

1️⃣Во-первых, мы создаём таблицу счётчиков из предоставленного списка чисел. Затем мы используем эту таблицу счётчиков в процессе обратного поиска, который мы определяем как функцию backtrack(comb, remain, curr, candidate_groups, results). Для сохранения состояния на каждом этапе обратного поиска мы используем несколько параметров в функции:
comb: комбинация, которую мы построили на данный момент.
remain: оставшаяся сумма, которую нам нужно заполнить, чтобы достичь целевой суммы.
curr: курсор, который указывает на текущую группу чисел, используемую из таблицы счётчиков.
counter: текущая таблица счётчиков.
results: окончательные комбинации, которые достигают целевой суммы.

2️⃣При каждом вызове функции обратного поиска мы сначала проверяем, достигли ли мы целевой суммы (то есть sum(comb) = target), и нужно ли прекратить исследование, потому что сумма текущей комбинации превышает желаемую целевую сумму.

3️⃣Если осталась сумма для заполнения, мы затем перебираем текущую таблицу счётчиков, чтобы выбрать следующего кандидата. После выбора кандидата мы продолжаем исследование, вызывая функцию backtrack() с обновлёнными состояниями. Более важно, что в конце каждого исследования нам нужно вернуть состояние, которое мы обновили ранее, чтобы начать с чистого листа для следующего исследования. Именно из-за этой операции обратного поиска алгоритм получил своё название.

😎 Решение:

class Solution {
    fun combinationSum2(candidates: IntArray, target: Int): List<List<Int>> {
        val results = mutableListOf<List<Int>>()
        val counter = candidates.groupingBy { it }.eachCount().map { it.key to it.value }.toMutableList()

        fun backtrack(comb: MutableList<Int>, remain: Int, curr: Int, counter: MutableList<Pair<Int, Int>>) {
            if (remain == 0) {
                results.add(comb.toList())
                return
            } else if (remain < 0) {
                return
            }

            for (nextCurr in curr until counter.size) {
                val (candidate, freq) = counter[nextCurr]
                if (freq <= 0) continue

                comb.add(candidate)
                counter[nextCurr] = candidate to freq - 1
                backtrack(comb, remain - candidate, nextCurr, counter)
                counter[nextCurr] = candidate to freq
                comb.removeAt(comb.lastIndex)
            }
        }

        backtrack(mutableListOf(), target, 0, counter)
        return results
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 41. First Missing Positive

Дан неотсортированный массив целых чисел nums. Верните наименьшее положительное целое число, которого нет в массиве nums.

Необходимо реализовать алгоритм, который работает за время O(n) и использует O(1) дополнительной памяти.

Пример:

Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.

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

1️⃣Инициализировать переменную n длиной массива nums. Создать массив seen размером n + 1. Отметить элементы в массиве nums как просмотренные в массиве seen.
Для каждого числа num в массиве nums, если num больше 0 и меньше или равно n, установить seen[num] в значение true.

2️⃣Найти наименьшее недостающее положительное число:
Проитерировать от 1 до n, и если seen[i] не равно true, вернуть i как наименьшее недостающее положительное число.

3️⃣Если массив seen содержит все элементы от 1 до n, вернуть n + 1 как наименьшее недостающее положительное число.

😎 Решение:

class Solution {
    fun firstMissingPositive(nums: IntArray): Int {
        val n = nums.size
        val seen = BooleanArray(n + 1)

        for (num in nums) {
            if (num > 0 && num <= n) {
                seen[num] = true
            }
        }

        for (i in 1..n) {
            if (!seen[i]) {
                return i
            }
        }

        return n + 1
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 42. Trapping Rain Water

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

Пример:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

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

1️⃣Найдите максимальную высоту столбца с левого конца до индекса i в массиве left_max.

2️⃣Найдите максимальную высоту столбца с правого конца до индекса i в массиве right_max.

3️⃣Итерируйте по массиву высот height и обновляйте ans: добавьте min(left_max[i], right_max[i]) - height[i] к ans.

😎 Решение:

class Solution {
    fun trap(height: IntArray): Int {
        if (height.isEmpty()) return 0
        var ans = 0
        val size = height.size
        val leftMax = IntArray(size)
        val rightMax = IntArray(size)
        
        leftMax[0] = height[0]
        for (i in 1 until size) {
            leftMax[i] = maxOf(height[i], leftMax[i - 1])
        }
        
        rightMax[size - 1] = height[size - 1]
        for (i in size - 2 downTo 0) {
            rightMax[i] = maxOf(height[i], rightMax[i + 1])
        }
        
        for (i in 1 until size - 1) {
            ans += minOf(leftMax[i], rightMax[i]) - height[i]
        }
        
        return ans
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 43. Multiply Strings

Даны два неотрицательных целых числа num1 и num2, представленные в виде строк. Верните произведение num1 и num2, также представленное в виде строки.

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

Пример:

Input: num1 = "2", num2 = "3"
Output: "6"

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

1️⃣Переверните оба числа. Инициализируйте массив ans с (N+M) нулями. Для каждой цифры в secondNumber:
Инициализируйте переменную carry, первоначально равную 0.
Инициализируйте массив (currentResult), который начинается с некоторого количества нулей, основываясь на позиции цифры в secondNumber.

2️⃣Для каждой цифры в firstNumber:
Умножьте цифру из secondNumber на цифру из firstNumber и добавьте предыдущий carry к умножению.
Возьмите остаток от деления умножения на 10, чтобы получить последнюю цифру.
Добавьте последнюю цифру в массив currentResult.
Разделите умножение на 10, чтобы получить новое значение для carry.

3️⃣После итерации по каждой цифре в первом числе, если carry не равен нулю, добавьте carry в currentResult.
Добавьте currentResult к ans.
Если последняя цифра в ans равна нулю, перед тем как перевернуть ans, необходимо удалить ноль из ans. В противном случае в финальном ответе будет ведущий ноль.
Переверните ans и верните его.

😎 Решение:

class Solution {
    fun multiply(num1: String, num2: String): String {
        if (num1 == "0" || num2 == "0") {
            return "0"
        }

        val firstNumber = num1.reversed()
        val secondNumber = num2.reversed()

        val N = firstNumber.length + secondNumber.length
        val answer = IntArray(N) { 0 }

        for ((index, digit) in secondNumber.withIndex()) {
            val result = multiplyOneDigit(firstNumber, digit, index)
            addStrings(result, answer)
        }

        while (answer.last() == 0 && answer.size > 1) {
            answer.dropLast(1)
        }

        answer.reverse()
        return answer.joinToString(separator = "") { it.toString() }
    }

    private fun multiplyOneDigit(firstNumber: String, digit2: Char, numZeros: Int): IntArray {
        val result = IntArray(firstNumber.length + numZeros + 1) { 0 }
        var carry = 0

        for (i in 0 until numZeros) {
            result[i] = 0
        }

        for ((i, digit1) in firstNumber.withIndex()) {
            val multiplication = Character.getNumericValue(digit1) * Character.getNumericValue(digit2) + carry
            result[i + numZeros] = multiplication % 10
            carry = multiplication / 10
        }

        if (carry != 0) {
            result[firstNumber.length + numZeros] = carry
        }
        return result
    }

    private fun addStrings(result: IntArray, answer: IntArray) {
        var carry = 0
        for (i in result.indices) {
            val sum = (if (i < answer.size) answer[i] else 0) + result[i] + carry
            if (i < answer.size) {
                answer[i] = sum % 10
            } else {
                answer[i] = sum
            }
            carry = sum / 10
        }
        var i = result.size
        while (carry != 0) {
            val sum = (if (i < answer.size) answer[i] else 0) + carry
            if (i < answer.size) {
                answer[i] = sum % 10
            } else {
                answer[i] = sum
            }
            carry = sum / 10
            i++
        }
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 55. Jump Game

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

Верните true, если вы можете достичь последнего индекса, или false в противном случае.

Пример:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

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

1️⃣ Инициализация таблицы памяти:
Изначально все элементы таблицы памяти имеют статус UNKNOWN, за исключением последнего, который является (тривиально) GOOD (может достичь сам себя).

2️⃣Модификация алгоритма обратного трассирования:
Измените алгоритм обратного трассирования таким образом, чтобы на рекурсивном шаге сначала проверялось, известен ли индекс (GOOD/BAD).
Если индекс известен, тогда возвращается True/False.

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

😎 Решение:

class Solution {
    private lateinit var memo: IntArray
    private lateinit var nums: IntArray

    private fun canJumpFromPosition(position: Int): Boolean {
        if (memo[position] != -1) {
            return memo[position] == 1
        }
        val furthestJump = minOf(position + nums[position], nums.size - 1)
        for (nextPosition in position + 1..furthestJump) {
            if (canJumpFromPosition(nextPosition)) {
                memo[position] = 1
                return true
            }
        }
        memo[position] = 0
        return false
    }

    fun canJump(nums: IntArray): Boolean {
        this.nums = nums
        memo = IntArray(nums.size) { -1 }
        memo[nums.lastIndex] = 1 // The last position is always "good"
        return canJumpFromPosition(0)
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых