Kotlin | LeetCode

#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 разработчика 🔒 База собесов | 🔒 База тестовых

#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 Задача: 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 разработчика 🔒 База собесов | 🔒 База тестовых

#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 Задача: 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 разработчика 🔒 База собесов | 🔒 База тестовых

#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 разработчика 🔒 База собесов | 🔒 База тестовых

#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 Задача: 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 разработчика 🔒 База собесов | 🔒 База тестовых

Задача: 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`. Необходимо тестировать данный код на различных входных данных, чтобы убедиться, что он работает корректно во всех сценариях использования.

Задача: 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. Итоговый результат деления возвращается с учетом знака и ограничений на диапазон. Этот способ выполнения деления без использования оператора деления может быть сложным для понимания на первый взгляд из-за использования битовых операций и циклов, но он позволяет эффективно и точно выполнить деление целых чисел. Важно проверять код на различных случаях и тестировать его на различных входных данных.