Я занимаюсь решением задач на Leetcode 👩‍💻 уже два года. За это время я освоил основные подходы к решению таких задач.

В какой-то момент мне казалось, что они имеют мало общего с теми, которые я решаю на работе. Однако это впечатление оказалось ошибочным 🛑

Через несколько месяцев я заметил, что решения, которые я нахожу для повседневных задач, начинают автоматически оптимизироваться — изменился сам подход к решению.
При этом важно понимать, что оптимизация не всегда имеет решающее значение, но если несколько решений одинаковы по трудозатратам, почему бы не выбрать наиболее эффективное?
Если архитектура решения продумана, а все его части оптимизированы, то на выходе получится (если не вдаваться в детали) почти оптимальный продукт.

Сегодня я впервые решил задачу на Leetcode 👩‍💻 с использованием Swift 🗺. В ближайшее время напишу пост об этом… ✍️
#leetcode

Сегодняшняя задача: https://leetcode.com/problems/map-of-highest-peak/
1765. Map of Highest Peak - нужно построить сушу с самыми высокими холмами, где высота в каждой клетке отличается от соседних не более чем на 1. Изначально клетка = 1 обозначает воду, а клетка = 0 сушу. При ответе высота воды обозначается 0.

Решение:

class Solution {
    func highestPeak(_ isWater: [[Int]]) -> [[Int]] {
        let m = isWater.count
        let n = isWater.first!.count
        var mutableIsWater = isWater
        var queue = Deque<(Int, Int)>()
        
        for i in 0..<m {
            for j in 0..<n {
                if isWater[i][j] == 1 {
                    queue.append((i, j))
                    isWaterMutable[i][j] = 0
                } else {
                    isWaterMutable[i][j] = -1
                }
            }
        }
        
        let directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        var currentHeight = 1
        while !queue.isEmpty {
            let layerSize = queue.count
            for _ in 0..<layerSize {
                let (i, j) = queue.popFirst()!
                directions.forEach { direction in
                    let x = i + direction.0
                    let y = j + direction.1
                    if x >= 0 && x < m && y >= 0 && y < n {
                        if isWaterMutable[x][y] == -1 {
                            isWaterMutable[x][y] = currentHeight
                            queue.append((x, y))
                        }
                    }
                }
            }
            currentHeight += 1
        }
        
        return isWaterMutable
    }
}

Я использую BFS (поиск в ширину), который реализуется с помощью структуры данных Queue. При реализации я активно пользовался Google, т.к. для меня оказалось трудностью элементарное использование for цикла. Но это оказалось вполне посильным.

Некоторые интересные моменты, которые я подметил для себя:

🟢 tuple: выражение вида (i, j) и let x = i + direction.0. Это простой способ работы с парами значений, который позволяет делать код более читаемым и удобным.
🟢 if: В отличие от Kotlin, в Swift скобки не обязательны для одиночных операторов внутри if. В Kotlin я привык писать if (condition) { ... }, но в Swift можно написать if condition и это будет работать.
🟢 range: В Swift для работы с диапазонами используется синтаксис 0..<n или 0...n-1, в то время как в Kotlin аналогичный диапазон записывается как 0 until n или 0..n-1.
🟢 let: В Swift let защищает коллекции от модификации, что оказалось довольно удобным и безопасным. Это добавляет уверенности, что коллекции не будут случайно изменены. Любопытно как это реализовано 🤔

Маленькая задача, а сколько открытий! Предвкушаю, что меня ждёт дальше в изучении Swift 🥸
#leetcode

Всем привет ✌️ Сегодня порешаем leetcode 👩‍💻 используя Swift, конечно!

Задача:
Вам дана строка blocks длины n с 0-индексацией, где blocks[i] - это либо 'W', либо 'B', представляющие цвет i-го блока. Символ 'W' обозначает белый цвет, а 'B' - черный.

Также дано целое число k, которое представляет желаемое количество последовательных черных блоков.

За одну операцию можно перекрасить белый блок в черный.

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

Решение (попробуйте решить самостоятельно, перед тем как смотреть мой вариант 👇):

class Solution {
    func minimumRecolors(_ blocks: String, _ k: Int) -> Int {
        var whiteCount = 0
        var minRecolors = k
        var left = blocks.startIndex

        for (rightOffset, char) in blocks.enumerated() {
            if char == "W" { whiteCount += 1 }

            if rightOffset >= k - 1 {
                minRecolors = min(minRecolors, whiteCount)
                if blocks[left] == "W" { whiteCount -= 1 }
                left = blocks.index(after: left)
            }
        }
        return minRecolors
    }
}

https://leetcode.com/problems/minimum-recolors-to-get-k-consecutive-black-blocks
#leetcode