#easy
Задача: 509. Fibonacci Number

Числа Фибоначчи, обычно обозначаемые как F(n), образуют последовательность, называемую последовательностью Фибоначчи, так что каждое число является суммой двух предыдущих, начиная с 0 и 1. То есть,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), для n > 1.
Дано n, вычислите F(n).

Пример:

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

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

1⃣Проверка начального условия
Если N <= 1, вернуть N.

2⃣Инициализация переменных
Инициализируйте current значением 0. Инициализируйте prev1 значением 1, что будет представлять fib(N-1) при вычислении текущего значения. Инициализируйте prev2 значением 0, что будет представлять fib(N-2) при вычислении текущего значения.

3⃣Итерация и вычисление
Итерация от 2 до N включительно. На каждой итерации: установите current как сумму prev1 и prev2. Обновите prev2 значением prev1. Обновите prev1 значением current. Вернуть значение current после завершения итерации.

😎 Решение:

class Solution {
    fun fib(N: Int): Int {
        if (N <= 1) return N
        var current = 0
        var prev1 = 1
        var prev2 = 0

        for (i in 2..N) {
            current = prev1 + prev2
            prev2 = prev1
            prev1 = current
        }
        return current
    }
}

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

#easy
Задача: 724. Find Pivot Index

Если задан массив целых чисел nums, вычислите поворотный индекс этого массива. Поворотный индекс - это индекс, при котором сумма всех чисел строго слева от индекса равна сумме всех чисел строго справа от индекса. Если индекс находится на левом краю массива, то сумма слева равна 0, так как слева нет элементов. Это относится и к правому краю массива. Возвращается самый левый поворотный индекс. Если такого индекса не существует, возвращается -1.

Пример:

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

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

1⃣Вычислите сумму всех элементов массива.

2⃣Пройдите по массиву, вычисляя текущую сумму элементов слева и проверяя, равна ли она разности между общей суммой и текущей суммой справа.

3⃣Если текущий индекс удовлетворяет условию, верните его; если нет, продолжайте проверку. Если такой индекс не найден, верните -1.

😎 Решение:

fun pivotIndex(nums: IntArray): Int {
    val totalSum = nums.sum()
    var leftSum = 0
    for (i in nums.indices) {
        if (leftSum == totalSum - leftSum - nums[i]) {
            return i
        }
        leftSum += nums[i]
    }
    return -1
}

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

#easy
Задача: 734. Sentence Similarity

Мы можем представить предложение в виде массива слов, например, предложение "I am happy with leetcode" можно представить как arr = ["I", "am",happy", "with", "leetcode"].

Даны два предложения sentence1 и sentence2, каждое из которых представлено в виде массива строк, и массив пар строк similarPairs, где similarPairs[i] = [xi, yi] указывает, что два слова xi и yi похожи. Возвращается true, если предложения sentence1 и sentence2 похожи, или false, если они не похожи. Два предложения похожи, если: у них одинаковая длина (т.е, Заметьте, что слово всегда похоже само на себя, также обратите внимание, что отношение сходства не является транзитивным. Например, если слова a и b похожи, а слова b и c похожи, то a и c не обязательно похожи.

Пример:

Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","fine"],["drama","acting"],["skills","talent"]]
Output: true

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

1⃣Проверьте, равны ли длины предложений sentence1 и sentence2. Если нет, верните false.

2⃣Создайте словарь для хранения всех пар похожих слов.

3⃣Проверьте каждую пару слов из предложений sentence1 и sentence2 на схожесть, используя словарь и правило, что слово всегда похоже на само себя.

😎 Решение:

fun areSentencesSimilar(sentence1: Array<String>, sentence2: Array<String>, similarPairs: List<List<String>>): Boolean {
    if (sentence1.size != sentence2.size) {
        return false
    }
    
    val similar = mutableMapOf<String, MutableSet<String>>()
    for (pair in similarPairs) {
        val (x, y) = pair
        similar.computeIfAbsent(x) { mutableSetOf() }.add(y)
        similar.computeIfAbsent(y) { mutableSetOf() }.add(x)
    }
    
    for (i in sentence1.indices) {
        val w1 = sentence1[i]
        val w2 = sentence2[i]
        if (w1 != w2 && (similar[w1]?.contains(w2) != true)) {
            return false
        }
    }
    
    return true
}

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

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

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