#easy
Задача: 541. Reverse String II

Дана строка s и целое число k, переверните первые k символов для каждых 2k символов, начиная с начала строки.

Если осталось меньше k символов, переверните все. Если осталось меньше 2k, но больше или равно k символов, переверните первые k символов и оставьте остальные как есть.

Пример:

Input: s = "abcdefg", k = 2
Output: "bacdfeg"

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

1⃣Разворачиваем каждый блок из 2k символов непосредственно. Каждый блок начинается с кратного 2k: например, 0, 2k, 4k, 6k и так далее.

2⃣Будьте внимательны, если символов недостаточно, блок может не быть перевернут.

3⃣Для разворота блока символов с позиции i до j, меняем местами символы на позициях i++ и j--.

😎 Решение:

class Solution {
    func reverseStr(_ s: String, _ k: Int) -> String {
        var a = Array(s)
        var start = 0
        while start < a.count {
            var i = start
            var j = min(start + k - 1, a.count - 1)
            while i < j {
                a.swapAt(i, j)
                i += 1
                j -= 1
            }
            start += 2 * k
        }
        return String(a)
    }
}

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

#medium
Задача: 531. Lonely Pixel I

Дано изображение размером m x n, состоящее из чёрных ('B') и белых ('W') пикселей. Верните количество чёрных одиночных пикселей.

Чёрный одиночный пиксель — это символ 'B', расположенный в такой позиции, где в той же строке и в том же столбце нет других чёрных пикселей.

Пример:

Input: picture = [["W","W","B"],["W","B","W"],["B","W","W"]]
Output: 3
Explanation: All the three 'B's are black lonely pixels.

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

1⃣ Подсчёт количества чёрных пикселей в строках и столбцах:
Пройдите по всей матрице picture, для каждой чёрной клетки (x, y) увеличивайте rowCount[x] и colCount[y] на 1.

2⃣ Поиск одиночных чёрных пикселей:
Снова пройдите по всей матрице и для каждой чёрной клетки (x, y) проверьте значения rowCount[x] и colCount[y]. Если оба значения равны 1, увеличьте переменную answer на 1.

3⃣ Возврат результата:
Верните answer.

😎 Решение:

class Solution {
    func findLonelyPixel(_ picture: [[Character]]) -> Int {
        let n = picture.count
        let m = picture[0].count
        
        var rowCount = [Int](repeating: 0, count: n)
        var columnCount = [Int](repeating: 0, count: m)
        
        for i in 0..<n {
            for j in 0..<m {
                if picture[i][j] == "B" {
                    rowCount[i] += 1
                    columnCount[j] += 1
                }
            }
        }
        
        var answer = 0
        for i in 0..<n {
            for j in 0..<m {
                if picture[i][j] == "B" && rowCount[i] == 1 && columnCount[j] == 1 {
                    answer += 1
                }
            }
        }
        
        return answer
    }
}

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

#hard
Задача: 302. Smallest Rectangle Enclosing Black Pixels

Вам дана бинарная матрица размером m x n, где 0 представляет собой белый пиксель, а 1 представляет собой черный пиксель.
Черные пиксели соединены (то есть существует только одна черная область). Пиксели соединены по горизонтали и вертикали.
Даны два целых числа x и y, которые представляют местоположение одного из черных пикселей. Верните площадь наименьшего (выравненного по осям) прямоугольника, который охватывает все черные пиксели.
Вы должны написать алгоритм со сложностью менее O(mn).

Пример:

Input: image = [["0","0","1","0"],["0","1","1","0"],["0","1","0","0"]], x = 0, y = 2
Output: 6

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

1⃣Инициализация границ прямоугольника: Инициализируйте переменные left, right, top и bottom. left и top задаются значениями координат (x, y), right и bottom - значениями x + 1 и y + 1 соответственно.

2⃣Обход всех пикселей: Пройдите по всем координатам (x, y) матрицы. Если текущий пиксель является черным (image[x][y] == 1), обновите границы прямоугольника:
left = min(left, x)
right = max(right, x + 1)
top = min(top, y)
bottom = max(bottom, y + 1)

3⃣Вычисление и возврат площади: После завершения обхода матрицы, верните площадь прямоугольника, используя формулу (right - left) * (bottom - top).

😎 Решение:

class Solution {
    func minArea(_ image: [[Character]], _ x: Int, _ y: Int) -> Int {
        let m = image.count, n = image[0].count
        let left = searchColumns(image, 0, y, 0, m, true)
        let right = searchColumns(image, y + 1, n, 0, m, false)
        let top = searchRows(image, 0, x, left, right, true)
        let bottom = searchRows(image, x + 1, m, left, right, false)
        return (right - left) * (bottom - top)
    }

    private func searchColumns(_ image: [[Character]], _ i: Int, _ j: Int, _ top: Int, _ bottom: Int, _ whiteToBlack: Bool) -> Int {
        var i = i, j = j
        while i != j {
            var k = top
            let mid = (i + j) / 2
            while k < bottom && image[k][mid] == "0" { k += 1 }
            if (k < bottom) == whiteToBlack {
                j = mid
            } else {
                i = mid + 1
            }
        }
        return i
    }

    private func searchRows(_ image: [[Character]], _ i: Int, _ j: Int, _ left: Int, _ right: Int, _ whiteToBlack: Bool) -> Int {
        var i = i, j = j
        while i != j {
            var k = left
            let mid = (i + j) / 2
            while k < right && image[mid][k] == "0" { k += 1 }
            if (k < right) == whiteToBlack {
                j = mid
            } else {
                i = mid + 1
            }
        }
        return i
    }
}

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

#medium
Задача: 532. K-diff Pairs in an Array

Дан массив целых чисел nums и целое число k. Верните количество уникальных пар с разницей k в массиве.

Пара с разницей k — это пара целых чисел (nums[i], nums[j]), для которой выполняются следующие условия:
0 <= i, j < nums.length
i != j
|nums[i] - nums[j]| == k
Обратите внимание, что |val| обозначает абсолютное значение val.

Пример:

Input: nums = [3,1,4,1,5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.

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

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

2⃣ Для каждого ключа в хэш-словаре проверьте, можно ли найти пару, удовлетворяющую условиям:
Если k > 0, проверьте, существует ли ключ, равный x + k.
Если k == 0, проверьте, есть ли более одного вхождения x.

3⃣ Увеличьте счётчик результатов, если условие выполняется.

😎 Решение:

class Solution {
    func findPairs(_ nums: [Int], _ k: Int) -> Int {
        var counter = [Int: Int]()
        for num in nums {
            counter[num, default: 0] += 1
        }
        
        var result = 0
        for (x, val) in counter {
            if k > 0, counter[x + k] != nil {
                result += 1
            } else if k == 0, val > 1 {
                result += 1
            }
        }
        
        return result
    }
}

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

#medium
Задача: 535. Encode and Decode TinyURL

Спроектируйте класс для кодирования URL и декодирования короткого URL.
Нет ограничений на то, как ваш алгоритм кодирования/декодирования должен работать. Вам просто нужно убедиться, что URL может быть закодирован в короткий URL, а короткий URL может быть декодирован в исходный URL.

Реализуйте класс Solution:
Solution() Инициализирует объект системы.
String encode(String longUrl) Возвращает короткий URL для данного longUrl.
String decode(String shortUrl) Возвращает исходный длинный URL для данного shortUrl. Гарантируется, что данный shortUrl был закодирован тем же объектом.

Пример:

Input: url = "https://leetcode.com/problems/design-tinyurl"
Output: "https://leetcode.com/problems/design-tinyurl"

Explanation:
Solution obj = new Solution();
string tiny = obj.encode(url); // returns the encoded tiny url.
string ans = obj.decode(tiny); // returns the original url after decoding it.

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

1⃣ Инициализация:
Создайте строку, содержащую все возможные символы (цифры и буквы), которые могут быть использованы для генерации кода.
Создайте хэш-таблицу для хранения соответствий коротких и длинных URL-адресов.
Создайте объект для генерации случайных чисел.

2⃣ Кодирование:
Сгенерируйте случайный 6-символьный код.
Если такой код уже существует в хэш-таблице, повторите генерацию.
Сохраните соответствие длинного URL и сгенерированного кода в хэш-таблице.
Верните полный короткий URL.

3⃣ Декодирование:
Удалите префикс короткого URL, чтобы получить код.
Используйте код для поиска длинного URL в хэш-таблице.
Верните длинный URL.

😎 Решение:

class Codec {
    private let alphabet = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
    private var map = [String: String]()
    private var rand = SystemRandomNumberGenerator()
    
    private func getRand() -> String {
        var result = ""
        for _ in 0..<6 {
            result.append(alphabet.randomElement()!)
        }
        return result
    }
    
    func encode(_ longUrl: String) -> String {
        var key = getRand()
        while map[key] != nil {
            key = getRand()
        }
        map[key] = longUrl
        return "https://tinyurl.com/" + key
    }
    
    func decode(_ shortUrl: String) -> String {
        let key = String(shortUrl.dropFirst("https://tinyurl.com/".count))
        return map[key] ?? ""
    }
}

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

#medium
Задача: 536. Construct Binary Tree from String

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

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

Вы всегда начинаете строить левый дочерний узел родителя сначала, если он существует.

Пример:

Input: s = "4(2(3)(1))(6(5))"
Output: [4,2,6,3,1,5]

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

1⃣ Извлечение числа:
Определите функцию getNumber, которая извлекает целое число из текущей строки, начиная с указанного индекса. Учтите знак числа, если он есть.

2⃣ Построение поддерева:
Определите рекурсивную функцию str2treeInternal, которая принимает строку и текущий индекс в качестве входных данных и возвращает пару: узел TreeNode и следующий индекс для обработки.
Внутри функции извлеките значение для корневого узла текущего поддерева, создайте узел, а затем рекурсивно постройте левое и правое поддеревья, если они существуют.

3⃣ Основная функция:
Определите основную функцию str2tree, которая вызывает рекурсивную функцию str2treeInternal и возвращает построенное дерево.

😎 Решение:

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init(_ val: Int) { self.val = val; self.left = nil; self.right = nil }
}

class Solution {
    func str2tree(_ s: String) -> TreeNode? {
        return str2treeInternal(Array(s), 0).node
    }
    
    func getNumber(_ s: [Character], _ index: Int) -> (value: Int, index: Int) {
        var idx = index
        var isNegative = false
        if s[idx] == "-" {
            isNegative = true
            idx += 1
        }
        var number = 0
        while idx < s.count, let digit = s[idx].wholeNumberValue {
            number = number * 10 + digit
            idx += 1
        }
        return (isNegative ? -number : number, idx)
    }
    
    func str2treeInternal(_ s: [Character], _ index: Int) -> (node: TreeNode?, nextIndex: Int) {
        if index >= s.count {
            return (nil, index)
        }
        
        let numberData = getNumber(s, index)
        let value = numberData.value
        var idx = numberData.index
        
        let node = TreeNode(value)
        
        if idx < s.count && s[idx] == "(" {
            let leftData = str2treeInternal(s, idx + 1)
            node.left = leftData.node
            idx = leftData.nextIndex
        }
        
        if idx < s.count && s[idx] == "(" {
            let rightData = str2treeInternal(s, idx + 1)
            node.right = rightData.node
            idx = rightData.nextIndex
        }
        
        return (node, idx < s.count && s[idx] == ")" ? idx + 1 : idx)
    }
}

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

#easy
Задача: 303. Range Sum Query - Immutable

Дан целочисленный массив nums. Обработайте несколько запросов следующего типа:
Вычислите сумму элементов массива nums между индексами left и right включительно, где left <= right.
Реализуйте класс NumArray:
- NumArray(int[] nums) Инициализирует объект с целочисленным массивом nums.
- int sumRange(int left, int right) Возвращает сумму элементов массива nums между индексами left и right включительно (т.е. nums[left] + nums[left + 1] + ... + nums[right]).

Пример:

Input
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]

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

1⃣Инициализация:
Создайте массив sum длиной на один элемент больше, чем массив nums, и заполните его накопленными суммами элементов массива nums.

2⃣Предварительное вычисление сумм:
Заполните массив sum, где каждый элемент sum[i + 1] является суммой всех предыдущих элементов массива nums до индекса i включительно.

3⃣Вычисление диапазонной суммы:
Для каждого запроса суммы элементов между индексами left и right используйте разницу между sum[right + 1] и sum[left], чтобы быстро получить результат.

😎 Решение:

class NumArray {
    private var sum: [Int]

    init(_ nums: [Int]) {
        sum = [Int](repeating: 0, count: nums.count + 1)
        for i in 0..<nums.count {
            sum[i + 1] = sum[i] + nums[i]
        }
    }

    func sumRange(_ i: Int, _ j: Int) -> Int {
        return sum[j + 1] - sum[i]
    }
}

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

#medium
Задача: 537. Complex Number Multiplication

Комплексное число можно представить в виде строки в формате "real+imaginaryi", где:
real — это действительная часть и является целым числом в диапазоне [-100, 100].
imaginary — это мнимая часть и является целым числом в диапазоне [-100, 100].
i^2 == -1.
Даны два комплексных числа num1 и num2 в виде строк, верните строку комплексного числа, представляющую их произведение.

Пример:

Input: num1 = "1+1i", num2 = "1+1i"
Output: "0+2i"
Explanation: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i, and you need convert it to the form of 0+2i.

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

1⃣ Извлечение реальной и мнимой частей:
Разделите строки a и b на реальные и мнимые части, используя символы '+' и 'i'.

2⃣ Вычисление произведения:
Переведите извлечённые части в целые числа.
Используйте формулу для умножения комплексных чисел: (a+ib)×(x+iy)=ax−by+i(bx+ay).

3⃣ Формирование строки результата:
Создайте строку в требуемом формате с реальной и мнимой частями произведения и верните её.

😎 Решение:

class Solution {
    func complexNumberMultiply(_ a: String, _ b: String) -> String {
        let x = a.split(separator: "+")
        let y = b.split(separator: "+")
        let a_real = Int(x[0])!
        let a_img = Int(x[1].dropLast())!
        let b_real = Int(y[0])!
        let b_img = Int(y[1].dropLast())!
        let realPart = a_real * b_real - a_img * b_img
        let imaginaryPart = a_real * b_img + a_img * b_real
        return "\(realPart)+\(imaginaryPart)i"
    }
}

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

#medium
Задача: 583. Delete Operation for Two Strings

Даны две строки word1 и word2, вернуть минимальное количество шагов, необходимых для того, чтобы сделать word1 и word2 одинаковыми.

На одном шаге можно удалить ровно один символ в любой строке.

Пример:

Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

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

1⃣ Инициализация массива:
Создайте одномерный массив dp для хранения минимального количества удалений, необходимых для уравнивания строк word1 и word2.

2⃣ Заполнение массива:
Используйте временный массив temp для обновления значений dp, представляющих текущую строку. Обновите temp с использованием значений dp предыдущей строки.

3⃣ Обновление и результат:
Скопируйте временный массив temp обратно в dp после обработки каждой строки. В конце верните значение из dp, представляющее минимальное количество удалений.

😎 Решение:

class Solution {
    func minDistance(_ word1: String, _ word2: String) -> Int {
        let m = word1.count, n = word2.count
        var dp = [Int](repeating: 0, count: n + 1)
        let s1 = Array(word1), s2 = Array(word2)

        for i in 0...m {
            var temp = [Int](repeating: 0, count: n + 1)
            for j in 0...n {
                if i == 0 || j == 0 {
                    temp[j] = i + j
                } else if s1[i - 1] == s2[j - 1] {
                    temp[j] = dp[j - 1]
                } else {
                    temp[j] = 1 + min(dp[j], temp[j - 1])
                }
            }
            dp = temp
        }
        return dp[n]
    }
}

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

#hard
Задача: 587. Erect the Fence

Вам дан массив trees, где trees[i] = [xi, yi] представляет местоположение дерева в саду.

Оградите весь сад с использованием минимальной длины веревки, так как это дорого. Сад хорошо огорожен только в том случае, если все деревья окружены.

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

Пример:

Input: trees = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
Output: [[1,1],[2,0],[4,2],[3,3],[2,4]]
Explanation: All the trees will be on the perimeter of the fence except the tree at [2, 2], which will be inside the fence.

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

1⃣ Сортировка точек и построение нижней оболочки:
Отсортируйте точки по их x-координатам, а в случае совпадения x-координат, по y-координатам.
Постройте нижнюю оболочку, добавляя точки к оболочке и удаляя последние точки, если они не образуют против часовой стрелки поворот.

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

3⃣ Удаление дублирующих элементов и возврат результата:
Используйте HashSet, чтобы удалить дублирующиеся точки из стека.
Преобразуйте результат в массив и верните его.

😎 Решение:

class Solution {
    func orientation(_ p: [Int], _ q: [Int], _ r: [Int]) -> Int {
        return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
    }

    func outerTrees(_ points: [[Int]]) -> [[Int]] {
        let sortedPoints = points.sorted { (p1, p2) -> Bool in
            return p1[0] == p2[0] ? p1[1] < p2[1] : p1[0] < p2[0]
        }

        var hull = [[Int]]()

        for point in sortedPoints {
            while hull.count >= 2 && orientation(hull[hull.count - 2], hull.last!, point) > 0 {
                hull.removeLast()
            }
            hull.append(point)
        }

        hull.removeLast()

        for point in sortedPoints.reversed() {
            while hull.count >= 2 && orientation(hull[hull.count - 2], hull.last!, point) > 0 {
                hull.removeLast()
            }
            hull.append(point)
        }

        return Array(Set(hull))
    }
}

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

#medium
Задача: 304. Range Sum Query 2D - Immutable

Дана двумерная матрица matrix. Обработайте несколько запросов следующего типа:
Вычислите сумму элементов матрицы внутри прямоугольника, определенного его верхним левым углом (row1, col1) и нижним правым углом (row2, col2).
Реализуйте класс NumMatrix:
- NumMatrix(int[][] matrix) Инициализирует объект целочисленной матрицей matrix.- int sumRegion(int row1, int col1, int row2, int col2) Возвращает сумму элементов матрицы внутри прямоугольника, определенного его верхним левым углом (row1, col1) и нижним правым углом (row2, col2).
Необходимо разработать алгоритм, где метод sumRegion работает за O(1) по времени.

Пример:

Input
["NumMatrix", "sumRegion", "sumRegion", "sumRegion"]
[[[[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]], [2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]]

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

1⃣Инициализация:
Создайте двумерный массив sums размером (m + 1) x (n + 1), где m и n — размеры исходной матрицы matrix. Заполните этот массив нулями.

2⃣Предварительное вычисление сумм:
Заполните массив sums, где каждый элемент sums[i][j] будет содержать сумму всех элементов матрицы от начала до позиции (i-1, j-1) включительно.

3⃣Вычисление диапазонной суммы:
Для каждого запроса суммы элементов внутри прямоугольника, определенного его углами (row1, col1) и (row2, col2), используйте предварительно вычисленный массив sums для получения результата за O(1) времени.

😎 Решение:

class NumMatrix {
    private var dp: [[Int]]

    init(_ matrix: [[Int]]) {
        if matrix.isEmpty || matrix[0].isEmpty {
            dp = []
            return
        }
        let m = matrix.count, n = matrix[0].count
        dp = Array(repeating: Array(repeating: 0, count: n + 1), count: m + 1)
        for r in 0..<m {
            for c in 0..<n {
                dp[r + 1][c + 1] = dp[r + 1][c] + dp[r][c + 1] + matrix[r][c] - dp[r][c]
            }
        }
    }

    func sumRegion(_ row1: Int, _ col1: Int, _ row2: Int, _ col2: Int) -> Int {
        return dp[row2 + 1][col2 + 1] - dp[row1][col2 + 1] - dp[row2 + 1][col1] + dp[row1][col1]
    }
}

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

#hard
Задача: 305. Number of Islands II

Дан пустой двумерный бинарный массив grid размером m x n. Этот массив представляет собой карту, где 0 означает воду, а 1 — сушу. Изначально все ячейки массива — водные (т.е. все ячейки содержат 0).
Вы можете выполнить операцию "добавить землю", которая превращает воду в указанной позиции в сушу. Вам дан массив positions, где positions[i] = [ri, ci] — позиция (ri, ci), в которой следует выполнить i-ю операцию.
Верните массив целых чисел answer, где answer[i] — количество островов после превращения ячейки (ri, ci) в сушу.
Остров окружен водой и образуется путем соединения соседних земель по горизонтали или вертикали. Вы можете считать, что все четыре края сетки окружены водой.

Пример:

Input: m = 1, n = 1, positions = [[0,0]]
Output: [1]

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

1⃣Инициализация:
Создайте массивы x[] = { -1, 1, 0, 0 } и y[] = { 0, 0, -1, 1 }, которые будут использоваться для нахождения соседей ячейки.
Создайте экземпляр UnionFind, например, dsu(m * n). Инициализируйте всех родителей значением -1. Используйте объединение по рангу, инициализируйте все ранги значением 0. Наконец, инициализируйте count = 0.
Создайте список целых чисел answer, где answer[i] будет хранить количество островов, образованных после превращения ячейки positions[i] в сушу.

2⃣Обработка позиций:
Итерация по массиву positions. Для каждой позиции в positions:
Выполните линейное отображение, чтобы преобразовать двумерную позицию ячейки в landPosition = position[0] * n + position[1].
Используйте операцию addLand(landPosition), чтобы добавить landPosition как узел в граф. Эта функция также увеличит count.
Итерация по каждому соседу позиции. Соседа можно определить с помощью neighborX = position[0] + x[i] и neighborY = position[1] + y[i], где neighborX — координата X, а neighborY — координата Y соседней ячейки. Выполните линейное отображение соседней ячейки с помощью neighborPosition = neighborX * n + neighborY. Теперь, если на neighborPosition есть суша, т.е. isLand(neighborPosition) возвращает true, выполните объединение neighborPosition и landPosition. В объединении уменьшите count на 1.

3⃣Определение количества островов:
Выполните операцию numberOfIslands, которая возвращает количество островов, образованных после превращения позиции в сушу. Добавьте это значение в answer.
Верните answer.

😎 Решение

class UnionFind {
    private var parent: [Int], rank: [Int], count = 0
    init(_ size: Int) { parent = Array(repeating: -1, count: size); rank = Array(repeating: 0, count: size) }
    func addLand(_ x: Int) { if parent[x] < 0 { parent[x] = x; count += 1 } }
    func isLand(_ x: Int) -> Bool { return parent[x] >= 0 }
    func find(_ x: Int) -> Int { if parent[x] != x { parent[x] = find(parent[x]) }; return parent[x] }
    func unionSet(_ x: Int, _ y: Int) { let xset = find(x), yset = find(y)
        if xset != yset { if rank[xset] < rank[yset] { parent[xset] = yset }
        else { parent[yset] = xset; if rank[xset] == rank[yset] { rank[xset] += 1 } }; count -= 1 } }
}

class Solution {
    func numIslands2(_ m: Int, _ n: Int, _ positions: [[Int]]) -> [Int] {
        let dsu = UnionFind(m * n), dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        var answer = [Int]()
        for pos in positions {
            let land = pos[0] * n + pos[1]
            dsu.addLand(land)
            for (dx, dy) in dirs {
                let x = pos[0] + dx, y = pos[1] + dy, neighbor = x * n + y
                if x >= 0 && x < m && y >= 0 && y < n && dsu.isLand(neighbor) { dsu.unionSet(land, neighbor) }
            }
            answer.append(dsu.count)
        }
        return answer
    }
}

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

#medium
Задача: 542. 01 Matrix


Дан бинарный матрица размера m x n, верните расстояние до ближайшего нуля для каждой ячейки.

Расстояние между двумя соседними ячейками равно 1.

Пример:

Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]

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

1⃣Создайте копию матрицы mat, назовем её matrix. Используйте структуру данных seen для пометки уже посещенных узлов и очередь для выполнения BFS. Поместите все узлы с 0 в очередь и отметьте их в seen.

2⃣Выполните BFS:
Пока очередь не пуста, извлекайте текущие row, col, steps из очереди.
Итеративно пройдите по четырем направлениям. Для каждой nextRow, nextCol проверьте, находятся ли они в пределах границ и не были ли они уже посещены в seen.

3⃣Если так, установите matrix[nextRow][nextCol] = steps + 1 и поместите nextRow, nextCol, steps + 1 в очередь. Также отметьте nextRow, nextCol в seen. Верните matrix.

😎 Решение:

class Solution {
    var m: Int = 0
    var n: Int = 0
    let directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    
    func updateMatrix(_ mat: [[Int]]) -> [[Int]] {
        m = mat.count
        n = mat[0].count
        var matrix = Array(repeating: Array(repeating: 0, count: n), count: m)
        var seen = Array(repeating: Array(repeating: false, count: n), count: m)
        var queue = [[Int]]()

        for row in 0..<m {
            for col in 0..<n {
                matrix[row][col] = mat[row][col]
                if matrix[row][col] == 0 {
                    queue.append([row, col, 0])
                    seen[row][col] = true
                }
            }
        }
        
        while !queue.isEmpty {
            let curr = queue.removeFirst()
            let row = curr[0], col = curr[1], steps = curr[2]
            
            for direction in directions {
                let nextRow = row + direction[0], nextCol = col + direction[1]
                if valid(nextRow, nextCol) && !seen[nextRow][nextCol] {
                    seen[nextRow][nextCol] = true
                    queue.append([nextRow, nextCol, steps + 1])
                    matrix[nextRow][nextCol] = steps + 1
                }
            }
        }
        
        return matrix
    }
    
    func valid(_ row: Int, _ col: Int) -> Bool {
        return 0 <= row && row < m && 0 <= col && col < n
    }
}

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

#hard
Задача: 588. Design In-Memory File System

Спроектируйте структуру данных, которая симулирует файловую систему в памяти.

Реализуйте класс FileSystem:
FileSystem() Инициализирует объект системы.
List<String> ls(String path)
Если path является путем к файлу, возвращает список, содержащий только имя этого файла.
Если path является путем к директории, возвращает список имен файлов и директорий в этой директории.
Ответ должен быть в лексикографическом порядке.
void mkdir(String path) Создает новую директорию согласно заданному пути. Заданная директория не существует. Если промежуточные директории в пути не существуют, вы также должны создать их.
void addContentToFile(String filePath, String content)
Если filePath не существует, создает файл, содержащий заданный контент.
Если filePath уже существует, добавляет заданный контент к исходному содержимому.
String readContentFromFile(String filePath) Возвращает содержимое файла по пути filePath.

Пример:

Input
["FileSystem", "ls", "mkdir", "addContentToFile", "ls", "readContentFromFile"]
[[], ["/"], ["/a/b/c"], ["/a/b/c/d", "hello"], ["/"], ["/a/b/c/d"]]
Output
[null, [], null, null, ["a"], "hello"]

Explanation
FileSystem fileSystem = new FileSystem();
fileSystem.ls("/");                         // return []
fileSystem.mkdir("/a/b/c");
fileSystem.addContentToFile("/a/b/c/d", "hello");
fileSystem.ls("/");                         // return ["a"]
fileSystem.readContentFromFile("/a/b/c/d"); // return "hello"

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

1⃣ Инициализация файловой системы:
Создайте класс FileSystem, который будет содержать вложенный класс File. Класс File будет представлять либо файл, либо директорию, содержать флаг isfile, словарь files и строку content.

2⃣ Обработка команд:
Реализуйте метод ls, который возвращает список файлов и директорий в указанном пути, либо имя файла, если указанный путь является файлом.
Реализуйте метод mkdir, который создаёт директории по указанному пути. Если промежуточные директории не существуют, создайте их.
Реализуйте метод addContentToFile, который добавляет содержимое в файл по указанному пути. Если файл не существует, создайте его.
Реализуйте метод readContentFromFile, который возвращает содержимое файла по указанному пути.

3⃣ Обработка путей и работа с файлами/директориями:
Используйте метод split для разделения пути на составляющие и навигации по дереву директорий и файлов.
Для каждой команды выполняйте соответствующие операции по созданию, чтению или записи содержимого файлов и директорий.

😎 Решение:

class FileSystem {
    class File {
        var isFile = false
        var files = [String: File]()
        var content = ""
    }

    private var root = File()

    private func navigate(_ path: String) -> File {
        var t = root
        if path != "/" {
            let dirs = path.split(separator: "/")
            for dir in dirs {
                if !dir.isEmpty {
                    if t.files[String(dir)] == nil {
                        t.files[String(dir)] = File()
                    }
                    t = t.files[String(dir)]!
                }
            }
        }
        return t
    }

    func ls(_ path: String) -> [String] {
        let t = navigate(path)
        if t.isFile {
            return [String(path.split(separator: "/").last!)]
        }
        return t.files.keys.sorted()
    }

    func mkdir(_ path: String) {
        _ = navigate(path)
    }

    func addContentToFile(_ filePath: String, _ content: String) {
        let t = navigate(filePath)
        t.isFile = true
        t.content += content
    }

    func readContentFromFile(_ filePath: String) -> String {
        return navigate(filePath).content
    }
}

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

#medium
Задача: 397. Integer Replacement

К положительному целому числу n можно применить одну из следующих операций: если n четное, замените n на n / 2. если n нечетное, замените n на n + 1 или n - 1. верните минимальное количество операций, необходимых для того, чтобы n стало 1.

Пример:

Input: n = 8
Output: 3
Explanation: 8 -> 4 -> 2 -> 1

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

1⃣Начните с данного числа n и выполните одну из следующих операций:
Если n четное, замените n на n / 2.
Если n нечетное, замените n на n + 1 или n - 1.

2⃣Используйте метод динамического программирования или жадный метод, чтобы найти минимальное количество операций, необходимых для достижения n = 1. Определите, какая операция (n + 1 или n - 1) является более эффективной для минимизации количества шагов.

3⃣Продолжайте выполнять выбранные операции, пока n не станет равным 1. Считайте количество выполненных операций и верните это значение как результат.

😎 Решение:

class Solution {
    func integerReplacement(_ n: Int) -> Int {
        var memo = [Int: Int]()
        return helper(n, &memo)
    }
    
    func helper(_ n: Int, _ memo: inout [Int: Int]) -> Int {
        if n == 1 { return 0 }
        if let result = memo[n] { return result }
        
        if n % 2 == 0 {
            memo[n] = 1 + helper(n / 2, &memo)
        } else {
            memo[n] = 1 + min(helper(n + 1, &memo), helper(n - 1, &memo))
        }
        
        return memo[n]!
    }
}

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

#medium
Задача: 398. Random Pick Index

Из целочисленного массива nums с возможными дубликатами случайным образом выведите индекс заданного целевого числа. Можно предположить, что заданное целевое число должно существовать в массиве. Реализация класса Solution: Solution(int[] nums) Инициализирует объект с массивом nums. int pick(int target) Выбирает случайный индекс i из nums, где nums[i] == target. Если существует несколько допустимых i, то каждый индекс должен иметь равную вероятность возврата.

Пример:

Input
["Solution", "pick", "pick", "pick"]
[[[1, 2, 3, 3, 3]], [3], [1], [3]]
Output
[null, 4, 0, 2]

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

1⃣Инициализируйте объект с массивом nums. Сохраните этот массив для дальнейшего использования.

2⃣Реализуйте метод pick(target), который выбирает случайный индекс i из массива nums, где nums[i] равен target. Если таких индексов несколько, каждый из них должен иметь равную вероятность быть выбранным.

3⃣Для реализации метода pick используйте алгоритм reservoir sampling для выбора случайного индекса.

😎 Решение:

class Solution {
    private var nums: [Int]

    init(_ nums: [Int]) {
        self.nums = nums
    }

    func pick(_ target: Int) -> Int {
        var count = 0
        var result = -1
        for (i, num) in nums.enumerated() {
            if num == target {
                count += 1
                if Int.random(in: 1...count) == count {
                    result = i
                }
            }
        }
        return result
    }
}

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

#medium
Задача: 399. Evaluate Division

Вам дан массив пар переменных equations и массив вещественных чисел values, где equations[i] = [Ai, Bi] и values[i] представляют уравнение Ai / Bi = values[i]. Каждая Ai или Bi - это строка, представляющая одну переменную. Вам также даны некоторые запросы, где queries[j] = [Cj, Dj] представляет j-й запрос, в котором вы должны найти ответ для Cj / Dj = ?. Верните ответы на все запросы. Если ни один ответ не может быть определен, верните -1.0. Замечание: входные данные всегда действительны. Можно предположить, что вычисление запросов не приведет к делению на ноль и что противоречия нет. Примечание: Переменные, которые не встречаются в списке уравнений, являются неопределенными, поэтому для них ответ не может быть определен.

Пример:

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]

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

1⃣Создание графа:
Представьте каждую переменную как узел в графе.
Используйте уравнения для создания ребер между узлами, где каждое ребро имеет вес, равный значению уравнения (Ai / Bi = values[i]).
Создайте также обратные ребра с обратным весом (Bi / Ai = 1 / values[i]).

2⃣Поиск пути:
Для каждого запроса используйте поиск в глубину (DFS) или поиск в ширину (BFS) для поиска пути от Cj до Dj.
Если путь найден, вычислите произведение весов вдоль пути, чтобы найти значение Cj / Dj.
Если путь не найден, верните -1.0.

3⃣Обработка запросов:
Пройдитесь по всем запросам и используйте граф для вычисления результатов каждого запроса.

😎 Решение:

class Solution {
    func calcEquation(_ equations: [[String]], _ values: [Double], _ queries: [[String]]) -> [Double] {
        var graph = [String: [String: Double]]()

        for (i, equation) in equations.enumerated() {
            let A = equation[0], B = equation[1]
            let value = values[i]
            graph[A, default: [String: Double]()][B] = value
            graph[B, default: [String: Double]()][A] = 1.0 / value
        }

        func bfs(_ start: String, _ end: String) -> Double {
            guard let _ = graph[start], let _ = graph[end] else { return -1.0 }
            var queue = [(start, 1.0)]
            var visited = Set<String>()
            
            while !queue.isEmpty {
                let (current, curProduct) = queue.removeFirst()
                if current == end { return curProduct }
                visited.insert(current)
                for (neighbor, value) in graph[current, default: [String: Double]()] {
                    if !visited.contains(neighbor) {
                        queue.append((neighbor, curProduct * value))
                    }
                }
            }
            return -1.0
        }

        var results = [Double]()
        for query in queries {
            let C = query[0], D = query[1]
            results.append(bfs(C, D))
        }
        return results
    }
}

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

#medium
Задача: 400. Nth Digit

Дано целое число n, вернуть n-ю цифру бесконечной последовательности чисел [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...].

Пример:

Input: n = 3
Output: 3

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

1⃣Определение диапазона:
Начните с определения количества цифр в числах текущего диапазона (1-9, 10-99, 100-999 и т.д.).
Уменьшайте значение n, вычитая количество цифр в текущем диапазоне, пока не найдете диапазон, в который попадает n-я цифра.

2⃣Нахождение конкретного числа:
Когда определите диапазон, найдите точное число, содержащее n-ю цифру.
Определите индекс цифры в этом числе.

3⃣Возвращение n-й цифры:
Извлеките и верните n-ю цифру из найденного числа.

😎 Решение:

class Solution {
    func findNthDigit(_ n: Int) -> Int {
        var n = n
        var length = 1
        var count = 9
        var start = 1
        
        while n > length * count {
            n -= length * count
            length += 1
            count *= 10
            start *= 10
        }
        
        start += (n - 1) / length
        let s = String(start)
        let index = s.index(s.startIndex, offsetBy: (n - 1) % length)
        return Int(String(s[index]))!
    }
}

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

#easy
Задача: 401. Binary Watch

Бинарные часы имеют 4 светодиода сверху для представления часов (0-11) и 6 светодиодов снизу для представления минут (0-59). Каждый светодиод представляет ноль или единицу, при этом младший разряд находится справа.

Пример:

Input: turnedOn = 1
Output: ["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]

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

1⃣Генерация всех возможных комбинаций:
Переберите все возможные значения для часов и минут.
Используйте битовые операции для подсчета количества единиц в бинарном представлении числа.

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

3⃣Форматирование результата:
Если комбинация часов и минут соответствует условию, отформатируйте их в виде строки "часы:минуты" и добавьте в список результатов.

😎 Решение:

class Solution {
    func readBinaryWatch(_ turnedOn: Int) -> [String] {
        var results = [String]()
        for h in 0..<12 {
            for m in 0..<60 {
                if (h.nonzeroBitCount + m.nonzeroBitCount) == turnedOn {
                    results.append(String(format: "%d:%02d", h, m))
                }
            }
        }
        return results
    }
}

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

#medium
Задача: 402. Remove K Digits

Если задана строка num, представляющая неотрицательное целое число num, и целое число k, верните наименьшее возможное целое число после удаления k цифр из num.

Пример:

Input: num = "1432219", k = 3
Output: "1219"

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

1⃣Инициализация
Создайте стек для хранения цифр, которые будут образовывать минимальное число.

2⃣Обработка каждой цифры
Перебирайте каждую цифру в строке num.
Если текущая цифра меньше верхней цифры в стеке и у вас есть еще возможность удалить цифры (k > 0), удалите верхнюю цифру из стека.
Добавьте текущую цифру в стек.
Удаление оставшихся цифр:
Если после прохождения всей строки k еще больше нуля, удалите оставшиеся цифры из конца стека

3⃣Формирование результата
Постройте итоговое число из цифр в стеке и удалите ведущие нули.

😎 Решение:

class Solution {
    func removeKdigits(_ num: String, _ k: Int) -> String {
        var stack = [Character]()
        var k = k
        for digit in num {
            while k > 0 && !stack.isEmpty && stack.last! > digit {
                stack.removeLast()
                k -= 1
            }
            stack.append(digit)
        }
        stack = Array(stack[0..<stack.count-k])
        let result = String(stack).trimmingCharacters(in: CharacterSet(charactersIn: "0"))
        return result.isEmpty ? "0" : result
    }
}

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

#hard
Задача: 403. Frog Jump

Если задана строка num, представляющая неотрицательное целое число num, и целое число k, верните наименьшее возможное целое число после удаления k цифр из num.

Пример:

Input: stones = [0,1,3,5,6,8,12,17]
Output: true

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

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

2⃣Итерация по камням
Пройдитесь по каждому камню и для каждого возможного прыжка (k-1, k, k+1) проверьте, если он ведет на существующий камень.
Если такой камень существует, добавьте его в набор возможных прыжков.

3⃣Проверка достижения последнего камня
Если можно достичь последний камень с помощью одного из возможных прыжков, верните True.
Если после всех итераций последний камень не достигнут, верните False.Формирование результата:
Постройте итоговое число из цифр в стеке и удалите ведущие нули.

😎 Решение:

class Solution {
    func canCross(_ stones: [Int]) -> Bool {
        var dp = [Int: Set<Int>]()
        for stone in stones {
            dp[stone] = Set<Int>()
        }
        dp[0]?.insert(0)
        
        for stone in stones {
            for jump in dp[stone]! {
                for step in jump - 1...jump + 1 {
                    if step > 0, let _ = dp[stone + step] {
                        dp[stone + step]?.insert(step)
                    }
                }
            }
        }
        
        return !(dp[stones.last!]!.isEmpty)
    }
}

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