#easy
Задача: 744. Find Smallest Letter Greater Than Target

Нам дан массив символов letters, отсортированный в неубывающем порядке, и символ target. В массиве letters есть как минимум два разных символа. Возвращается наименьший символ в letters, который лексикографически больше target. Если такого символа не существует, возвращается первый символ в буквах.

Пример:

Input: letters = ["c","f","j"], target = "a"
Output: "c"

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

1⃣Использовать бинарный поиск для нахождения позиции первого символа в letters, который лексикографически больше target.

2⃣Если найденный символ существует, вернуть его.

3⃣Если такого символа не существует, вернуть первый символ в letters.

😎 Решение:

fun nextGreatestLetter(letters: CharArray, target: Char): Char {
    var left = 0
    var right = letters.size - 1
    while (left <= right) {
        val mid = (left + right) / 2
        if (letters[mid] > target) {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return letters[left % letters.size]
}

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

#easy
Задача: 746. Min Cost Climbing Stairs

Вам дан целочисленный массив cost, где cost[i] - стоимость i-й ступеньки на лестнице. После оплаты стоимости вы можете подняться на одну или две ступеньки. Вы можете начать со ступеньки с индексом 0 или со ступеньки с индексом 1. Верните минимальную стоимость достижения вершины этажа.

Пример:

Input: cost = [10,15,20]
Output: 15

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

1⃣Создать массив dp, где dp[i] хранит минимальную стоимость достижения i-й ступеньки.

2⃣Инициализировать dp[0] и dp[1] как cost[0] и cost[1] соответственно. Заполнить dp используя минимальную стоимость подъема с предыдущих ступенек.

3⃣Вернуть минимальную стоимость достижения вершины.

😎 Решение:

fun minCostClimbingStairs(cost: IntArray): Int {
    val dp = cost.copyOf()
    for (i in 2 until cost.size) {
        dp[i] += minOf(dp[i - 1], dp[i - 2])
    }
    return minOf(dp[cost.size - 1], dp[cost.size - 2])
}

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

#easy
Задача: 747. Largest Number At Least Twice of Others

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

Пример:

Input: nums = [3,6,1,0]
Output: 1

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

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

2⃣Проверьте, является ли этот максимальный элемент по крайней мере в два раза больше всех остальных элементов массива.

3⃣Если условие выполняется, верните индекс максимального элемента, иначе верните -1.

😎 Решение:

fun minCostClimbingStairs(cost: IntArray): Int {
    val dp = cost.copyOf()
    for (i in 2 until cost.size) {
        dp[i] += minOf(dp[i - 1], dp[i - 2])
    }
    return minOf(dp[cost.size - 1], dp[cost.size - 2])
}

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

#easy
Задача: 748. Shortest Completing Word

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

Пример:

Input: licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"]
Output: "steps"

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

1⃣Извлечь все буквы из licensePlate, игнорируя цифры и пробелы, и создать словарь для подсчета частоты каждой буквы.

2⃣Пройти по массиву words, проверяя каждое слово на соответствие требованиям.

3⃣Найти самое короткое завершающее слово среди подходящих.

😎 Решение:

fun shortestCompletingWord(licensePlate: String, words: Array<String>): String {
    fun getCharCount(s: String): Map<Char, Int> {
        val count = mutableMapOf<Char, Int>()
        for (char in s.toLowerCase()) {
            if (char.isLetter()) {
                count[char] = count.getOrDefault(char, 0) + 1
            }
        }
        return count
    }

    val licenseCount = getCharCount(licensePlate)

    fun isCompletingWord(word: String, licenseCount: Map<Char, Int>): Boolean {
        val wordCount = mutableMapOf<Char, Int>()
        for (char in word) {
            wordCount[char] = wordCount.getOrDefault(char, 0) + 1
        }
        for ((char, cnt) in licenseCount) {
            if (wordCount.getOrDefault(char, 0) < cnt) {
                return false
            }
        }
        return true
    }

    var result: String? = null
    for (word in words) {
        if (isCompletingWord(word, licenseCount)) {
            if (result == null || word.length < result.length) {
                result = word
            }
        }
    }
    return result!!
}

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

#easy
Задача: 1496. Path Crossing

Дана строка path, где path[i] = 'N', 'S', 'E' или 'W', каждая из которых представляет движение на одну единицу на север, юг, восток или запад соответственно. Вы начинаете с точки (0, 0) на 2D плоскости и идете по пути, указанному в path.

Верните true, если путь пересекает сам себя в какой-либо точке, то есть если вы в какой-то момент окажетесь в месте, которое уже посещали ранее. В противном случае верните false.

Пример:

Input: path = "NESWW"
Output: true
Explanation: Notice that the path visits the origin twice.

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

1⃣Инициализация переменных
Создать хэш-карту moves, которая сопоставляет символы 'N', 'S', 'E', 'W' с соответствующими значениями. Инициализировать множество visited с начальной точкой (0, 0). Установить начальные координаты x = 0 и y = 0.

2⃣Проход по строке path
Для каждого символа c в path получить значения (dx, dy) из moves[c]. Обновить координаты: добавить dx к x и dy к y. Проверить, содержится ли текущая точка (x, y) в visited. Если да, вернуть true. Добавить текущую точку (x, y) в visited.

3⃣Возврат результата
Если ни одна точка не пересекалась, вернуть false.

😎 Решение:

class Solution {
    fun isPathCrossing(path: String): Boolean {
        val moves = mapOf('N' to Pair(0, 1), 'S' to Pair(0, -1), 'E' to Pair(1, 0), 'W' to Pair(-1, 0))
        val visited = mutableSetOf(Pair(0, 0))
        var x = 0
        var y = 0

        for (c in path) {
            val (dx, dy) = moves[c]!!
            x += dx
            y += dy
            val point = Pair(x, y)
            if (point in visited) {
                return true
            }
            visited.add(point)
        }

        return false
    }
}

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

#easy
Задача: 1523. Count Odd Numbers in an Interval Range

### Условие задачи

Даны два неотрицательных целых числа low и high. Верните количество нечётных чисел между low и high (включительно).

Пример:

Input: low = 3, high = 7
Output: 3
Explanation: The odd numbers between 3 and 7 are [3,5,7].

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

1⃣Проверьте, является ли число low нечётным. Это можно легко сделать с помощью оператора %, но мы используем побитовый оператор &, так как он более эффективен.

2⃣Если low нечётное, увеличьте его на 1.

3⃣Верните (high - low) / 2 + 1. Важный момент здесь - проверить, не стало ли low больше, чем high после увеличения. Это произойдёт, если low = high, и в этом случае следует вернуть 0.

😎 Решение:

class Solution {
    fun countOdds(low: Int, high: Int): Int {
        var low = low
        if ((low and 1) == 0) {
            low++
        }
        return if (low > high) 0 else (high - low) / 2 + 1
    }
}

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

#easy
Задача: 760. Find Anagram Mappings

Вам даны два целочисленных массива nums1 и nums2, где nums2 - анаграмма nums1. Оба массива могут содержать дубликаты. Верните индексное отображение массива mapping из nums1 в nums2, где mapping[i] = j означает, что i-й элемент в nums1 появляется в nums2 по индексу j. Если ответов несколько, верните любой из них. Массив a является анаграммой массива b означает, что b создается путем случайного изменения порядка элементов в a.

Пример:

Input: nums1 = [12,28,46,32,50], nums2 = [50,12,32,46,28]
Output: [1,4,3,2,0]

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

1⃣Создайте словарь для хранения индексов элементов в nums2.

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

3⃣Верните массив индексов.

😎 Решение:

fun anagramMapping(nums1: IntArray, nums2: IntArray): IntArray {
    val indexMap = mutableMapOf<Int, MutableList<Int>>()
    for (i in nums2.indices) {
        indexMap.computeIfAbsent(nums2[i]) { mutableListOf() }.add(i)
    }
    
    val mapping = IntArray(nums1.size)
    for (i in nums1.indices) {
        mapping[i] = indexMap[nums1[i]]!!.removeAt(indexMap[nums1[i]]!!.size - 1)
    }
    
    return mapping
}

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