#medium
Задача: 754. Reach a Number

Вы стоите в позиции 0 на бесконечной числовой прямой. В позиции target находится пункт назначения. Вы можете сделать некоторое количество ходов numMoves так, чтобы: на каждом ходу вы могли пойти либо налево, либо направо. Во время i-го хода (начиная с i == 1 до i == numMoves) вы делаете i шагов в выбранном направлении. Учитывая целое число target, верните минимальное количество ходов (т.е. минимальное numMoves), необходимое для достижения пункта назначения.

Пример:

Input: target = 2
Output: 3

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

1⃣Инициализируйте переменную для текущей позиции (position) и счетчик шагов (steps).

2⃣Используйте цикл, чтобы добавлять к position текущее количество шагов и увеличивать steps.

3⃣Если position достигает или превышает target и разница между position и target четная, остановите цикл и верните steps.

😎 Решение:

fun reachTarget(target: Int): Int {
    var target = kotlin.math.abs(target)
    var position = 0
    var steps = 0
    while (position < target || (position - target) % 2 != 0) {
        steps++
        position += steps
    }
    return steps
}

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

#medium
Задача: 755. Pour Water

Вам дана карта высот, представленная в виде целочисленного массива heights, где heights[i] - высота местности в точке i. Ширина в каждой точке равна 1. Вам также даны два целых числа volume и k. Единицы объема воды будут падать в точке k. Вода сначала падает в точке k и упирается в самую высокую местность или воду в этой точке. Затем она течет по следующим правилам: если капля в конечном итоге упадет, двигаясь влево, то двигайтесь влево. Иначе, если капля в конечном итоге упадет, двигаясь вправо, то двигайтесь вправо. Иначе поднимайтесь в текущее положение. Здесь "в конечном итоге упадет" означает, что капля в конечном итоге окажется на более низком уровне, если она будет двигаться в этом направлении. Кроме того, уровень означает высоту местности плюс вода в этом столбе. Мы можем предположить, что на двух сторонах, выходящих за пределы массива, есть бесконечно высокая местность. Также не может быть частичного равномерного распределения воды более чем на один блок сетки, и каждая единица воды должна находиться ровно в одном блоке.

Пример:

Input: heights = [2,1,1,2,1,2,2], volume = 4, k = 3
Output: [2,2,2,3,2,2,2]

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

1⃣Инициализируйте цикл для добавления объема воды.

2⃣Для каждой единицы воды: Проверьте, может ли вода двигаться влево и упасть на более низкий уровень. Если нет, проверьте, может ли вода двигаться вправо и упасть на более низкий уровень. Если нет, добавьте воду в текущую позицию.

3⃣Повторите шаг 2, пока не будет добавлен весь объем воды.

😎 Решение:

fun pourWater(heights: IntArray, volume: Int, k: Int): IntArray {
    for (v in 0 until volume) {
        var dropIndex = k
        for (d in listOf(-1, 1)) {
            var i = k
            while (i + d in heights.indices && heights[i + d] <= heights[i]) {
                if (heights[i + d] < heights[i]) {
                    dropIndex = i + d
                }
                i += d
            }
            if (dropIndex != k) break
        }
        heights[dropIndex]++
    }
    return heights
}

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

#medium
Задача: 756. Pyramid Transition Matrix

Вы складываете блоки так, чтобы получилась пирамида. Каждый блок имеет цвет, который представлен одной буквой. Каждый ряд блоков содержит на один блок меньше, чем ряд под ним, и располагается по центру сверху. Чтобы пирамида выглядела эстетично, допускаются только определенные треугольные узоры. Треугольный узор состоит из одного блока, уложенного поверх двух блоков. Шаблоны задаются в виде списка допустимых трехбуквенных строк, где первые два символа шаблона представляют левый и правый нижние блоки соответственно, а третий символ - верхний блок. Например, "ABC" представляет треугольный шаблон с блоком 'C', уложенным поверх блоков 'A' (слева) и 'B' (справа). Обратите внимание, что это отличается от "BAC", где "B" находится слева внизу, а "A" - справа внизу. Вы начинаете с нижнего ряда блоков bottom, заданного в виде одной строки, который вы должны использовать в качестве основания пирамиды. Учитывая bottom и allowed, верните true, если вы можете построить пирамиду до самой вершины так, чтобы каждый треугольный узор в пирамиде был в allowed, или false в противном случае.

Пример:

Input: bottom = "BCD", allowed = ["BCC","CDE","CEA","FFF"]
Output: true

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

1⃣Создайте структуру данных для хранения допустимых треугольных узоров.

2⃣Напишите рекурсивную функцию, которая проверяет возможность построения следующего уровня пирамиды.

3⃣Начните с нижнего уровня пирамиды и используйте рекурсию для построения каждого следующего уровня, проверяя каждый треугольный узор на допустимость.

😎 Решение:

class Solution {
    fun pyramidTransition(bottom: String, allowed: List<String>): Boolean {
        val allowedDict = mutableMapOf<String, MutableList<Char>>()

        for (pattern in allowed) {
            val key = pattern.substring(0, 2)
            val value = pattern[2]
            allowedDict.computeIfAbsent(key) { mutableListOf() }.add(value)
        }

        return canBuild(bottom, allowedDict)
    }

    private fun canBuild(currentLevel: String, allowedDict: Map<String, List<Char>>): Boolean {
        if (currentLevel.length == 1) return true

        val nextLevelOptions = mutableListOf<List<Char>>()
        for (i in 0 until currentLevel.length - 1) {
            val key = currentLevel.substring(i, i + 2)
            if (!allowedDict.containsKey(key)) return false
            nextLevelOptions.add(allowedDict[key]!!)
        }

        return canBuildNextLevel(nextLevelOptions, 0, "", allowedDict)
    }

    private fun canBuildNextLevel(options: List<List<Char>>, index: Int, nextLevel: String, allowedDict: Map<String, List<Char>>): Boolean {
        if (index == options.size) return canBuild(nextLevel, allowedDict)
        for (option in options[index]) {
            if (canBuildNextLevel(options, index + 1, nextLevel + option, allowedDict)) return true
        }
        return false
    }
}

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

#medium
Задача: 758. Bold Words in String

При наличии массива ключевых слов и строки a выделите все ключевые слова [i] жирным шрифтом. Все буквы между тегами <b> и </b> выделяются жирным шрифтом.

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

Пример:

Input: words = ["ab","bc"], s = "aabcd"
Output: "a<b>abc</b>d"

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

1⃣Создайте массив для хранения флагов, указывающих, какие символы в строке a должны быть выделены жирным шрифтом.

2⃣Пройдите по каждому ключевому слову и отметьте соответствующие позиции в массиве флагов.

3⃣Постройте результирующую строку, добавляя теги <b> и </b> на основе массива флагов.

😎 Решение:

fun addBoldTags(keywords: Array<String>, s: String): String {
    val n = s.length
    val bold = BooleanArray(n)
    
    for (word in keywords) {
        var start = s.indexOf(word)
        while (start != -1) {
            for (i in start until start + word.length) {
                bold[i] = true
            }
            start = s.indexOf(word, start + 1)
        }
    }
    
    val result = StringBuilder()
    var i = 0
    while (i < n) {
        if (bold[i]) {
            result.append("<b>")
            while (i < n && bold[i]) {
                result.append(s[i])
                i++
            }
            result.append("</b>")
        } else {
            result.append(s[i])
            i++
        }
    }
    
    return result.toString()
}

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

#medium
Задача: 763. Partition Labels

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

Пример:

Input: s = "ababcbacadefegdehijhklij"
Output: [9,7,8]

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

1⃣Создайте словарь для хранения последней позиции каждой буквы в строке.

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

3⃣Когда текущая позиция совпадает с максимальной позицией, завершите часть и начните новую.

😎 Решение:

fun partitionLabels(s: String): List<Int> {
    val lastPos = IntArray(26)
    for (i in s.indices) {
        lastPos[s[i] - 'a'] = i
    }
    
    val partitions = mutableListOf<Int>()
    var j = 0
    var anchor = 0
    for (i in s.indices) {
        j = maxOf(j, lastPos[s[i] - 'a'])
        if (i == j) {
            partitions.add(i - anchor + 1)
            anchor = i + 1
        }
    }
    return partitions
}

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