Swift | LeetCode

Задача: 1503. Last Moment Before All Ants Fall Out of a Plank
Сложность: medium

У нас есть деревянная доска длиной n единиц. Некоторые муравьи ходят по доске, каждый муравей движется со скоростью 1 единица в секунду. Некоторые муравьи движутся влево, другие движутся вправо.

Когда два муравья, движущиеся в разных направлениях, встречаются в какой-то точке, они меняют свои направления и продолжают двигаться дальше. Предполагается, что изменение направлений не занимает дополнительного времени.

Когда муравей достигает одного из концов доски в момент времени t, он сразу же падает с доски.

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

Пример:

Input: n = 4, left = [4,3], right = [0,1]
Output: 4
Explanation: In the image above:
-The ant at index 0 is named A and going to the right.
-The ant at index 1 is named B and going to the right.
-The ant at index 3 is named C and going to the left.
-The ant at index 4 is named D and going to the left.
The last moment when an ant was on the plank is t = 4 seconds. After that, it falls immediately out of the plank. (i.e., We can say that at t = 4.0000000001, there are no ants on the plank).

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

1⃣Инициализируйте переменную ans значением 0.

2⃣Итерация по массиву left и обновление ans значением num, если оно больше текущего значения ans.

3⃣Итерация по массиву right и обновление ans значением n - num, если оно больше текущего значения ans. Верните значение ans.

😎 Решение

class Solution {
    func getLastMoment(_ n: Int, _ left: [Int], _ right: [Int]) -> Int {
        var ans = 0
        for num in left {
            ans = max(ans, num)
        }
        for num in right {
            ans = max(ans, n - num)
        }
        return ans
    }
}

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

Задача: 737. Sentence Similarity II
Сложность: medium

Мы можем представить предложение в виде массива слов, например, предложение "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","good"],["fine","good"],["drama","acting"],["skills","talent"]]
Output: true

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

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

2⃣Построить граф схожести слов с использованием словаря.

3⃣Использовать поиск в глубину (DFS) для проверки транзитивной схожести слов в предложениях.

😎 Решение:

func areSentencesSimilar(_ sentence1: [String], _ sentence2: [String], _ similarPairs: [[String]]) -> Bool {
    if sentence1.count != sentence2.count {
        return false
    }
    
    var graph = [String: [String]]()
    for pair in similarPairs {
        let (x, y) = (pair[0], pair[1])
        graph[x, default: []].append(y)
        graph[y, default: []].append(x)
    }
    
    func dfs(_ word1: String, _ word2: String, _ visited: inout Set<String>) -> Bool {
        if word1 == word2 {
            return true
        }
        visited.insert(word1)
        for neighbor in graph[word1, default: []] {
            if !visited.contains(neighbor) && dfs(neighbor, word2, &visited) {
                return true
            }
        }
        return false
    }
    
    for (w1, w2) in zip(sentence1, sentence2) {
        if w1 != w2 {
            var visited = Set<String>()
            if !dfs(w1, w2, &visited) {
                return false
            }
        }
    }
    
    return true
}

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

Задача: 1208. Get Equal Substrings Within Budget
Сложность: medium

Вам даны две строки s и t одинаковой длины и целое число maxCost.
Вы хотите преобразовать s в t. Изменение i-го символа строки s на i-й символ строки t стоит |s[i] - t[i]| (т.е. абсолютная разница между значениями ASCII символов).

Верните максимальную длину подстроки s, которую можно изменить, чтобы она соответствовала соответствующей подстроке t с затратами, не превышающими maxCost. Если нет подстроки из s, которую можно изменить на соответствующую подстроку из t, верните 0.

Пример:

Input: s = "abcd", t = "bcdf", maxCost = 3
Output: 3
Explanation: "abc" of s can change to "bcd".
That costs 3, so the maximum length is 3.

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

1⃣Инициализация переменных:
maxLen для хранения максимальной длины подстроки с затратами, не превышающими maxCost.
start для хранения начального индекса текущей подстроки.
currCost для хранения текущих затрат на преобразование подстроки s в t.

2⃣Итерация по индексам от 0 до N-1:
Добавить текущие затраты на преобразование символа s[i] в t[i] к currCost.
Удалять элементы с левого конца, уменьшая затраты до тех пор, пока currCost не станет меньше или равным maxCost.
Обновить maxLen длиной текущей подстроки.

3⃣Возврат maxLen как результата.

😎 Решение:

class Solution {
    func equalSubstring(_ s: String, _ t: String, _ maxCost: Int) -> Int {
        let sArray = Array(s)
        let tArray = Array(t)
        let N = sArray.count
        
        var maxLen = 0
        var start = 0
        var currCost = 0
        
        for i in 0..<N {
            currCost += abs(Int(sArray[i].asciiValue!) - Int(tArray[i].asciiValue!))
            
            while currCost > maxCost {
                currCost -= abs(Int(sArray[start].asciiValue!) - Int(tArray[start].asciiValue!))
                start += 1
            }
            
            maxLen = max(maxLen, i - start + 1)
        }
        
        return maxLen
    }
}

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

Задача: 987. Vertical Order Traversal of a Binary Tree
Сложность: medium

Вам даны два списка закрытых интервалов, firstList и secondList, где firstList[i] = [starti, endi] и secondList[j] = [startj, endj]. Каждый список интервалов является попарно непересекающимся и отсортированным.

Верните пересечение этих двух списков интервалов.

Закрытый интервал [a, b] (где a <= b) обозначает множество действительных чисел x с a <= x <= b.

Пересечение двух закрытых интервалов - это множество действительных чисел, которые либо пусты, либо представлены как закрытый интервал. Например, пересечение [1, 3] и [2, 4] равно [2, 3].

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]

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

1⃣Инициализация указателей:
Создать словарь для хранения узлов по их координатам (col, row).
Создать очередь для обхода в ширину (BFS), содержащую начальную пару (root, (0, 0)).

2⃣Поиск пересечений:
Выполнить BFS обход дерева. Для каждого узла сохранить его значение в словаре по ключу (col, row).
Добавить левый потомок в очередь с координатами (row + 1, col - 1).
Добавить правый потомок в очередь с координатами (row + 1, col + 1).

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

😎 Решение:

class Solution {
    func verticalTraversal(_ root: TreeNode?) -> [[Int]] {
        var colTable = [Int: [(Int, Int)]]()
        var queue: [(TreeNode?, Int, Int)] = [(root, 0, 0)]
        
        while !queue.isEmpty {
            let (node, row, col) = queue.removeFirst()
            if let node = node {
                if colTable[col] != nil {
                    colTable[col]!.append((row, node.val))
                } else {
                    colTable[col] = [(row, node.val)]
                }
                queue.append((node.left, row + 1, col - 1))
                queue.append((node.right, row + 1, col + 1))
            }
        }
        
        var result = [[Int]]()
        for key in colTable.keys.sorted() {
            colTable[key]!.sort { $0 < $1 }
            result.append(colTable[key]!.map { $0.1 })
        }
        
        return result
    }
}

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

Задача: 1258. Synonymous Sentences
Сложность: medium

Вам дан список эквивалентных пар строк synonyms, где synonyms[i] = [si, ti] означает, что si и ti являются эквивалентными строками. Вам также дан текст предложения. Верните все возможные синонимичные предложения, отсортированные лексикографически.

Пример:

Input: synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]], text = "I am happy today but was sad yesterday"
Output: ["I am cheerful today but was sad yesterday","I am cheerful today but was sorrow yesterday","I am happy today but was sad yesterday","I am happy today but was sorrow yesterday","I am joy today but was sad yesterday","I am joy today but was sorrow yesterday"]

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

1⃣Построить граф синонимов, используя структуру данных, такую как Union-Find или просто с использованием DFS/BFS.

2⃣Пройти по каждому слову в предложении и найти все возможные синонимы.
Сгенерировать все возможные комбинации предложений.

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

😎 Решение:

class Solution {
    func generateSentences(_ synonyms: [[String]], _ text: String) -> [String] {
        var graph = [String: Set<String>]()

        for pair in synonyms {
            graph[pair[0], default: Set()].insert(pair[1])
            graph[pair[1], default: Set()].insert(pair[0])
        }

        let words = text.split(separator: " ").map { String($0) }
        var synonymGroups = [[String]]()
        for word in words {
            synonymGroups.append(findSynonyms(graph, word))
        }

        var sentences = [String]()
        var sentence = ""
        generate(&sentences, synonymGroups, &sentence, 0)
        return sentences.sorted()
    }

    private func findSynonyms(_ graph: [String: Set<String>], _ word: String) -> [String] {
        var synonyms = Set<String>()
        var stack = [word]
        while !stack.isEmpty {
            let w = stack.removeLast()
            if synonyms.insert(w).inserted {
                for neighbor in graph[w] ?? [] {
                    stack.append(neighbor)
                }
            }
        }
        return Array(synonyms).sorted()
    }

    private func generate(_ sentences: inout [String], _ groups: [[String]], _ sentence: inout String, _ index: Int) {
        if index == groups.count {
            sentences.append(sentence.trimmingCharacters(in: .whitespaces))
            return
        }
        for word in groups[index] {
            let original = sentence
            sentence += " " + word
            generate(&sentences, groups, &sentence, index + 1)
            sentence = original
        }
    }
}

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

Задача: 903. Valid Permutations for DI Sequence
Сложность: hard

Вам дана строка s длины n, где s[i] либо: 'D' означает убывание, либо 'I' означает возрастание. Перестановка perm из n + 1 целых чисел всех целых чисел в диапазоне [0, n] называется допустимой, если для всех допустимых i: если s[i] == 'D', то perm[i] > perm[i + 1], а если s[i] == 'I', то perm[i] < perm[i + 1]. Верните количество допустимых перестановок perm. Поскольку ответ может быть большим, верните его по модулю 109 + 7.

Пример:

Input: s = "DID"
Output: 5

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

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

2⃣Заполнить массив dp, учитывая условия возрастания и убывания из строки s.

3⃣Вернуть сумму dp[n][j] для всех j, что даст количество допустимых перестановок длины n + 1.

😎 Решение:

class Solution {
    func numPermsDISequence(_ s: String) -> Int {
        let MOD = 1_000_000_007
        let n = s.count
        var dp = Array(repeating: Array(repeating: 0, count: n + 1), count: n + 1)
        dp[0][0] = 1
        
        let sArray = Array(s)
        for i in 1...n {
            for j in 0...i {
                if sArray[i - 1] == "D" {
                    dp[i][j] = (j..<i).reduce(0) { ($0 + dp[i - 1][$1]) % MOD }
                } else {
                    dp[i][j] = (0..<j).reduce(0) { ($0 + dp[i - 1][$1]) % MOD }
                }
            }
        }
        
        return dp[n].reduce(0) { ($0 + $1) % MOD }
    }
}

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

Задача: 897. Increasing Order Search Tree
Сложность: easy

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

Пример:

Input: root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

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

1⃣Выполнить обход дерева в порядке in-order, чтобы получить список узлов.

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

3⃣Вернуть новый корень дерева (первый элемент списка).

😎 Решение:

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

func increasingBST(_ root: TreeNode?) -> TreeNode? {
    var nodes: [TreeNode] = []
    
    func inorder(_ node: TreeNode?) {
        guard let node = node else { return }
        inorder(node.left)
        nodes.append(node)
        inorder(node.right)
    }
    
    inorder(root)
    
    for i in 0..<nodes.count - 1 {
        nodes[i].left = nil
        nodes[i].right = nodes[i + 1]
    }
    
    nodes.last?.left = nil
    nodes.last?.right = nil
    return nodes.first
}

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

Задача: 70. Climbing Stairs
Сложность: easy

Ты поднимаешься по лестнице. Чтобы добраться до вершины, нужно преодолеть n ступенек.

Каждый раз ты можешь подняться на 1 или 2 ступеньки. Сколькими различными способами ты можешь добраться до вершины?

Пример:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

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

1⃣В этом методе грубой силы мы рассматриваем все возможные комбинации шагов, то есть 1 и 2, на каждом шаге.

2⃣На каждом шаге мы вызываем функцию climbStairs для шага 1 и шага 2, и возвращаем сумму возвращаемых значений обеих функций.

3⃣Формула вызова функции: climbStairs(i, n) = climbStairs(i+1, n) + climbStairs(i+2, n), где i определяет текущий шаг, а n — целевой шаг.

😎 Решение:

func climbStairs(_ n: Int) -> Int {
    return climbStairsHelper(0, n)
}

func climbStairsHelper(_ i: Int, _ n: Int) -> Int {
    if i > n {
        return 0
    }
    if i == n {
        return 1
    }
    return climbStairsHelper(i + 1, n) + climbStairsHelper(i + 2, n)
}

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

Задача: 292. Nim Game
Сложность: easy

Вы играете в следующую игру Nim со своим другом:

Изначально на столе лежит куча камней.
Вы и ваш друг поочередно делаете ходы, и вы ходите первым.
Каждый ход игрок, чей ход, будет убирать от 1 до 3 камней из кучи.
Тот, кто убирает последний камень, становится победителем.
Дано n, количество камней в куче. Верните true, если вы можете выиграть игру, предполагая, что и вы, и ваш друг играете оптимально, иначе верните false.

Пример:

Input: n = 4
Output: false
Explanation: These are the possible outcomes:
1. You remove 1 stone. Your friend removes 3 stones, including the last stone. Your friend wins.
2. You remove 2 stones. Your friend removes 2 stones, including the last stone. Your friend wins.
3. You remove 3 stones. Your friend removes the last stone. Your friend wins.
In all outcomes, your friend wins.

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

1⃣Определите базовый случай:
Если количество камней n меньше или равно 3, вы всегда можете выиграть, убрав все камни. В этом случае верните true.

2⃣Анализ оставшихся камней:
Если количество камней n делится на 4 без остатка (n % 4 == 0), вы не можете выиграть, так как независимо от вашего хода ваш друг всегда сможет оставить вам кратное 4 количество камней. В этом случае верните false.

3⃣Выигрышная стратегия:
Если количество камней n не кратно 4 (n % 4 != 0), вы можете выиграть, оставляя вашему другу кратное 4 количество камней после вашего хода. В этом случае верните true.

😎 Решение:

class Solution {
    func canWinNim(_ n: Int) -> Bool {
        return n % 4 != 0
    }
}

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

Задача: 409. Longest Palindrome
Сложность: easy

Если задана строка s, состоящая из строчных или прописных букв, верните длину самого длинного палиндрома, который можно построить из этих букв. Буквы чувствительны к регистру, например, "Aa" не считается палиндромом.

Пример:

Input: s = "abccccdd"
Output: 7

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

1⃣Создайте словарь для подсчета количества каждого символа в строке.

2⃣Пройдитесь по словарю и добавьте четное количество каждого символа к длине палиндрома. Если встречается нечетное количество символа, добавьте (count - 1) к длине палиндрома.

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

😎 Решение:

func longestPalindrome(_ s: String) -> Int {
    var charCount = [Character: Int]()
    for char in s {
        charCount[char, default: 0] += 1
    }
    var length = 0
    var oddFound = false
    for count in charCount.values {
        if count % 2 == 0 {
            length += count
        } else {
            length += count - 1
            oddFound = true
        }
    }
    return oddFound ? length + 1 : length
}

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

Задача: 1243. Array Transformation
Сложность: easy

Если задан исходный массив arr, то каждый день вы создаете новый массив, используя массив предыдущего дня. В i-й день вы выполняете следующие операции над массивом дня i-1, чтобы получить массив дня i: если элемент меньше своего левого и правого соседа, то этот элемент увеличивается. Если элемент больше своего левого и правого соседа, то этот элемент уменьшается. Первый и последний элементы никогда не меняются. Через несколько дней массив не меняется. Верните этот окончательный массив.

Пример:

Input: arr = [6,2,3,4]
Output: [6,3,3,4]

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

1⃣Инициализация нового массива с такими же значениями, как у исходного массива.
Циклически изменяем массив в соответствии с правилами, пока он не перестанет меняться.

2⃣Для каждого элемента массива проверяем, изменяется ли он в зависимости от его левого и правого соседей.
Если элемент меньше своего левого и правого соседей, увеличиваем его.
Если элемент больше своего левого и правого соседей, уменьшаем его.

3⃣Первый и последний элементы массива остаются неизменными.

😎 Решение:

class Solution {
    func transformArray(_ arr: [Int]) -> [Int] {
        var arr = arr
        var changed = false
        repeat {
            changed = false
            var newArr = arr
            for i in 1..<arr.count - 1 {
                if arr[i] < arr[i - 1] && arr[i] < arr[i + 1] {
                    newArr[i] += 1
                    changed = true
                } else if arr[i] > arr[i - 1] && arr[i] > arr[i + 1] {
                    newArr[i] -= 1
                    changed = true
                }
            }
            arr = newArr
        } while changed
        return arr
    }
}

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

Задача: 926. Flip String to Monotone Increasing
Сложность: medium

Двоичная строка является монотонно возрастающей, если она состоит из некоторого количества 0 (возможно, ни одного), за которым следует некоторое количество 1 (также возможно, ни одного). Вам дана двоичная строка s. Вы можете перевернуть s[i], изменив ее значение с 0 на 1 или с 1 на 0.

Пример:

Input: s = "00110"
Output: 1

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

1⃣Создать массив left для подсчета количества операций, чтобы сделать подстроку до текущего индекса монотонной (только 0).

2⃣Создать массив right для подсчета количества операций, чтобы сделать подстроку после текущего индекса монотонной (только 1).
Пройти по строке и заполнить массивы left и right.

3⃣Пройти по строке и найти минимальное количество операций, чтобы сделать всю строку монотонной.

😎 Решение:

class Solution {
    func minFlipsMonoIncr(_ s: String) -> Int {
        let n = s.count
        var left = [Int](repeating: 0, count: n + 1)
        var right = [Int](repeating: 0, count: n + 1)
        let sArray = Array(s)
        
        for i in 0..<n {
            left[i + 1] = left[i] + (sArray[i] == "1" ? 1 : 0)
        }
        
        for i in (0..<n).reversed() {
            right[i] = right[i + 1] + (sArray[i] == "0" ? 1 : 0)
        }
        
        var result = Int.max
        for i in 0...n {
            result = min(result, left[i] + right[i])
        }
        return result
    }
}

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

Задача: 268. Missing Number
Сложность: easy

Дан массив nums, содержащий n различных чисел в диапазоне [0, n]. Верните единственное число в этом диапазоне, которого нет в массиве.

Пример:

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

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

1⃣Сначала отсортируйте массив nums.

2⃣Проверьте особые случаи: убедитесь, что число 0 находится в начале массива, а число n — в конце.

3⃣Пройдитесь по отсортированному массиву и для каждого индекса проверьте, что число на этом индексе соответствует ожидаемому (предыдущее число плюс один). Как только вы обнаружите несоответствие, верните ожидаемое число.

😎 Решение:

class Solution {
    func missingNumber(_ nums: [Int]) -> Int {
        let sortedNums = nums.sorted()
        if sortedNums.last != sortedNums.count {
            return sortedNums.count
        } else if sortedNums.first != 0 {
            return 0
        }
        for i in 1..<sortedNums.count {
            let expectedNum = sortedNums[i - 1] + 1
            if sortedNums[i] != expectedNum {
                return expectedNum
            }
        }
        return -1
    }
}

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

Задача: 1273. Delete Tree Nodes
Сложность: medium

Дерево, укорененное в узле 0, задано следующим образом: количество узлов - nodes; значение i-го узла - value[i]; родитель i-го узла - parent[i]. Удалите все поддеревья, сумма значений узлов которых равна нулю. Верните количество оставшихся узлов в дереве.

Пример:

Input: nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-1]
Output: 2

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

1⃣Постройте дерево из заданных узлов, значений и родителей.

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

3⃣Удалите отмеченные узлы и их поддеревья и верните количество оставшихся узлов.

😎 Решение:

class Solution {
    func deleteTreeNodes(_ nodes: Int, _ parent: [Int], _ value: [Int]) -> Int {
        var tree = [Int: [Int]]()
        for i in 0..<nodes {
            tree[parent[i], default: []].append(i)
        }

        func dfs(_ node: Int) -> (Int, Int) {
            var totalSum = value[node]
            var totalCount = 1
            if let children = tree[node] {
                for child in children {
                    let (childSum, childCount) = dfs(child)
                    totalSum += childSum
                    totalCount += childCount
                }
            }
            return totalSum == 0 ? (0, 0) : (totalSum, totalCount)
        }

        return dfs(0).1
    }
}

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

Задача: 640. Solve the Equation
Сложность: medium

Решите заданное уравнение и верните значение 'x' в виде строки "x=#value". Уравнение содержит только операции '+', '-', переменную 'x' и ее коэффициент. Вы должны вернуть "No solution", если для уравнения нет решения, или "Infinite solutions", если для уравнения существует бесконечное количество решений. Если для уравнения существует ровно одно решение, мы убеждаемся, что значение 'x' является целым числом.

Пример:

Input: s = "*"
Output: 9

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

1⃣Разделение уравнения: Разделите уравнение на левую и правую части относительно знака равенства '='.

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

3⃣Решение уравнения: Используйте уравнение вида ax + b = cx + d, чтобы решить для 'x'. Если коэффициенты 'x' равны и числовые значения равны, уравнение имеет бесконечное количество решений. Если коэффициенты 'x' равны, но числовые значения различны, решения нет. В противном случае вычислите значение 'x'.

😎 Решение:

class Solution {
    func solveEquation(_ equation: String) -> String {
        func parse(_ s: String) -> (Int, Int) {
            var coeff = 0
            var constPart = 0
            var sign = 1
            var num = 0
            var i = s.startIndex
            
            while i < s.endIndex {
                if s[i] == "+" {
                    sign = 1
                    i = s.index(after: i)
                } else if s[i] == "-" {
                    sign = -1
                    i = s.index(after: i)
                } else if s[i].isNumber {
                    num = 0
                    while i < s.endIndex && s[i].isNumber {
                        num = num * 10 + s[i].wholeNumberValue!
                        i = s.index(after: i)
                    }
                    if i < s.endIndex && s[i] == "x" {
                        coeff += sign * num
                        i = s.index(after: i)
                    } else {
                        constPart += sign * num
                    }
                } else if s[i] == "x" {
                    coeff += sign
                    i = s.index(after: i)
                }
            }
            return (coeff, constPart)
        }
        
        let parts = equation.split(separator: "=")
        let (leftCoeff, leftConst) = parse(String(parts[0]))
        let (rightCoeff, rightConst) = parse(String(parts[1]))
        
        let coeff = leftCoeff - rightCoeff
        let constPart = rightConst - leftConst
        
        if coeff == 0 {
            return constPart == 0 ? "Infinite solutions" : "No solution"
        }
        return "x=\(constPart / coeff)"
    }
}

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

Задача: 1265. Print Immutable Linked List in Reverse
Сложность: medium

Вам дан неизменяемый связный список, распечатайте все значения каждого узла в обратном порядке с помощью следующего интерфейса: ImmutableListNode:Интерфейс неизменяемого связанного списка, вам дана голова списка. Для доступа к связанному списку необходимо использовать следующие функции (напрямую к ImmutableListNode обращаться нельзя): ImmutableListNode.printValue(): Выводит значение текущего узла. ImmutableListNode.getNext(): Возвращает следующий узел. Входные данные даются только для внутренней инициализации связанного списка.Вы должны решить эту задачу, не изменяя связанный список. Другими словами, вы должны работать со связанным списком, используя только упомянутые API.

Пример:

Input: head = [1,2,3,4]
Output: [4,3,2,1]

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

1⃣Используйте рекурсию для достижения конца связного списка.

2⃣На обратном пути рекурсии распечатайте значение каждого узла.

3⃣Обратный порядок достигается благодаря природе рекурсии (стек вызовов).

😎 Решение:

protocol ImmutableListNode {
    func printValue()
    func getNext() -> ImmutableListNode?
}

class Solution {
    func printLinkedListInReverse(_ head: ImmutableListNode?) {
        if let next = head?.getNext() {
            printLinkedListInReverse(next)
        }
        head?.printValue()
    }
}

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

Задача: 1114. Print in Order
Сложность: easy

Предположим, у нас есть класс:

public class Foo {
  public void first() { print("first"); }
  public void second() { print("second"); }
  public void third() { print("third"); }
}

Один и тот же экземпляр Foo будет передан трем разным потокам. Поток A вызовет first(), поток B вызовет second(), и поток C вызовет third(). Спроектируйте механизм и модифицируйте программу, чтобы гарантировать, что second() выполняется после first(), а third() выполняется после second().

Примечание:
Мы не знаем, как потоки будут планироваться в операционной системе, даже если числа в вводе подразумевают порядок выполнения. Формат ввода, который вы видите, в основном предназначен для обеспечения полноты наших тестов.

Пример:

Input: nums = [1,2,3]
Output: "firstsecondthird"
Explanation: There are three threads being fired asynchronously. The input [1,2,3] means thread A calls first(), thread B calls second(), and thread C calls third(). "firstsecondthird" is the correct output.

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

1⃣Инициализация переменных:
Инициализируйте координационные переменные firstJobDone и secondJobDone, чтобы указать, что задания еще не выполнены.

2⃣Функция first():
В этой функции нет зависимости, поэтому можно сразу приступить к выполнению задания. В конце функции обновите переменную firstJobDone, чтобы указать, что первое задание выполнено.

3⃣Функции second() и third():
В функции second() проверьте статус firstJobDone. Если она не обновлена, подождите, иначе переходите к выполнению второго задания. В конце функции обновите переменную secondJobDone, чтобы отметить завершение второго задания.
В функции third() проверьте статус secondJobDone. Аналогично функции second(), подождите сигнала secondJobDone перед тем, как приступить к выполнению третьего задания.

😎 Решение:

import Foundation

class Foo {
    private let firstJobDone = DispatchSemaphore(value: 0)
    private let secondJobDone = DispatchSemaphore(value: 0)

    func first(_ printFirst: () -> Void) {
        printFirst()
        firstJobDone.signal()
    }

    func second(_ printSecond: () -> Void) {
        firstJobDone.wait()
        printSecond()
        secondJobDone.signal()
    }

    func third(_ printThird: () -> Void) {
        secondJobDone.wait()
        printThird()
    }
}

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

Задача: 63. Unique Paths II
Сложность: medium

Вам дана матрица размером m на n, содержащая целые числа. Робот находится в начальный момент в верхнем левом углу (то есть в ячейке grid[0][0]). Робот пытается добраться до нижнего правого угла (то есть в ячейку grid[m - 1][n - 1]). Робот может двигаться только вниз или вправо в любой момент времени.

Препятствия и свободные пространства отмечены в матрице как 1 и 0 соответственно. Путь, который проходит робот, не может включать клетки, которые являются препятствиями.

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

Тестовые примеры сгенерированы таким образом, что ответ будет не более 2 * 10^9.

Пример:

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

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

1⃣Если первая ячейка, то есть obstacleGrid[0,0], содержит 1, это означает, что в первой ячейке есть препятствие. Следовательно, робот не сможет сделать ни одного хода, и мы должны вернуть количество возможных путей как 0. Если же obstacleGrid[0,0] изначально равно 0, мы устанавливаем его равным 1 и продолжаем.

2⃣Итерация по первой строке. Если ячейка изначально содержит 1, это означает, что текущая ячейка имеет препятствие и не должна учитываться в каком-либо пути. Следовательно, значение этой ячейки устанавливается равным 0. В противном случае, устанавливаем его равным значению предыдущей ячейки, то есть obstacleGrid[i,j] = obstacleGrid[i,j-1]. Повторяем аналогичные действия для первого столбца.

3⃣Далее, итерация по массиву начиная с ячейки obstacleGrid[1,1]. Если ячейка изначально не содержит препятствий, то количество способов добраться до этой ячейки будет равно сумме количества способов добраться до ячейки над ней и количества способов добраться до ячейки слева от неё, то есть obstacleGrid[i,j] = obstacleGrid[i-1,j] + obstacleGrid[i,j-1]. Если в ячейке есть препятствие, устанавливаем её значение равным 0 и продолжаем. Это делается для того, чтобы она не учитывалась в других путях.

😎 Решение:

func uniquePathsWithObstacles(_ obstacleGrid: [[Int]]) -> Int {
    let R = obstacleGrid.count
    let C = obstacleGrid[0].count
    if obstacleGrid[0][0] == 1 {
        return 0
    }
    var grid = obstacleGrid
    grid[0][0] = 1
    for i in 1..<R {
        grid[i][0] = grid[i][0] == 0 && grid[i - 1][0] == 1 ? 1 : 0
    }
    for i in 1..<C {
        grid[0][i] = grid[0][i] == 0 && grid[0][i - 1] == 1 ? 1 : 0
    }
    for i in 1..<R {
        for j in 1..<C {
            if grid[i][j] == 0 {
                grid[i][j] = grid[i - 1][j] + grid[i][j - 1]
            } else {
                grid[i][j] = 0
            }
        }
    }
    return grid[R - 1][C - 1]
}

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

Задача: 1519. Number of Nodes in the Sub-Tree With the Same Label
Сложность: medium

Вам дано дерево (т.е. связный неориентированный граф без циклов), состоящее из n узлов, пронумерованных от 0 до n - 1, и ровно n - 1 ребра. Корнем дерева является узел 0, и каждый узел дерева имеет метку, которая является строчной буквой, указанной в строке labels (т.е. узел с номером i имеет метку labels[i]).

Массив edges дан в форме edges[i] = [ai, bi], что означает, что существует ребро между узлами ai и bi в дереве.

Верните массив размера n, где ans[i] — это количество узлов в поддереве узла i, которые имеют ту же метку, что и узел i.

Поддерево дерева T — это дерево, состоящее из узла в T и всех его дочерних узлов.

Пример:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"
Output: [2,1,1,1,1,1,1]
Explanation: Node 0 has label 'a' and its sub-tree has node 2 with label 'a' as well, thus the answer is 2. Notice that any node is part of its sub-tree.
Node 1 has a label 'b'. The sub-tree of node 1 contains nodes 1,4 and 5, as nodes 4 and 5 have different labels than node 1, the answer is just 1 (the node itself).

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

1⃣Создайте список смежности, где adj[X] содержит всех соседей узла X.

2⃣Инициализируйте массив ans, хранящий ответ для каждого узла, и заполните его нулями.

3⃣Начните обход в глубину (DFS).

😎 Решение

class Solution {
    func dfs(_ node: Int, _ parent: Int, _ adj: [Int: [Int]], _ labels: [Character], _ ans: inout [Int]) -> [Int] {
        var nodeCounts = [Int](repeating: 0, count: 26)
        nodeCounts[Int(labels[node].asciiValue! - Character("a").asciiValue!)] = 1

        guard let children = adj[node] else {
            return nodeCounts
        }

        for child in children {
            if child == parent {
                continue
            }
            let childCounts = dfs(child, node, adj, labels, &ans)
            for i in 0..<26 {
                nodeCounts[i] += childCounts[i]
            }
        }

        ans[node] = nodeCounts[Int(labels[node].asciiValue! - Character("a").asciiValue!)]
        return nodeCounts
    }

    func countSubTrees(_ n: Int, _ edges: [[Int]], _ labels: String) -> [Int] {
        var adj = [Int: [Int]]()
        for edge in edges {
            adj[edge[0], default: []].append(edge[1])
            adj[edge[1], default: []].append(edge[0])
        }

        var ans = [Int](repeating: 0, count: n)
        let labelsArray = Array(labels)
        _ = dfs(0, -1, adj, labelsArray, &ans)
        return ans
    }
}

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

Задача: 1326. Minimum Number of Taps to Open to Water a Garden
Сложность: hard


Есть одномерный сад на оси x. Сад начинается в точке 0 и заканчивается в точке n. (т.е. длина сада равна n).

В саду есть n + 1 кранов, расположенных в точках [0, 1, ..., n].

Даны целое число n и целочисленный массив ranges длиной n + 1, где ranges[i] (индексация начинается с 0) означает, что i-й кран может поливать область [i - ranges[i], i + ranges[i]], если он открыт.

Верните минимальное количество кранов, которые должны быть открыты для полива всего сада. Если сад невозможно полить, верните -1.

Пример:

Input: n = 5, ranges = [3,4,1,1,0,0]
Output: 1
Explanation: The tap at point 0 can cover the interval [-3,3]
The tap at point 1 can cover the interval [-3,5]
The tap at point 2 can cover the interval [1,3]
The tap at point 3 can cover the interval [2,4]
The tap at point 4 can cover the interval [4,4]
The tap at point 5 can cover the interval [5,5]
Opening Only the second tap will water the whole garden [0,5]

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

1⃣Объявите массив dp размера n+1. Инициализируйте его значениями бесконечности (в коде используем большое число 10^9 для представления бесконечности). Установите dp[0] в 0 (базовый случай DP).

2⃣Итерируйтесь от i до n (через каждый кран слева направо). Рассчитайте самую левую позицию, достижимую текущим краном, как tap_start=max(0,i−ranges[i]). И самую правую позицию tap_end=min(n,i+ranges[i]).

3⃣Итерируйтесь через позиции j от tap_start до tap_end (в пределах досягаемости крана). Обновите dp[tap_end] значением dp[j]+1, если оно меньше. Если dp[n] остается бесконечным, значит, полить весь сад невозможно, и мы возвращаем −1. Верните dp[n].

😎 Решение

class Solution {
    func minTaps(_ n: Int, _ ranges: [Int]) -> Int {
        let INF = Int.max
        var dp = [Int](repeating: INF, count: n + 1)
        dp[0] = 0
        
        for i in 0...n {
            let tapStart = max(0, i - ranges[i])
            let tapEnd = min(n, i + ranges[i])
            
            for j in tapStart...tapEnd {
                dp[tapEnd] = min(dp[tapEnd], dp[j] + 1)
            }
        }
        
        return dp[n] == INF ? -1 : dp[n]
    }
}

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