Задача: 179. Largest Number
Сложность: medium

Дан список неотрицательных целых чисел nums. Организуйте их таким образом, чтобы они составляли наибольшее число и верните его.

Поскольку результат может быть очень большим, вам необходимо вернуть строку вместо целого числа.

Пример:

Input: nums = [10,2]
Output: "210"

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

1⃣Преобразование и сортировка: Преобразовать каждое число в строку и отсортировать массив строк с использованием специального компаратора, который для двух строк 𝑎 и b сравнивает результаты конкатенации 𝑎+𝑏 и 𝑏+𝑎.

2⃣Проверка на нули: Если после сортировки первый элемент массива равен "0", вернуть "0", так как все числа в массиве нули.

3⃣Формирование результата: Конкатенировать отсортированные строки для формирования наибольшего числа и вернуть это число в виде строки.

😎 Решение:

class Solution {
    func largestNumber(_ nums: [Int]) -> String {
        let strNums = nums.map { String($0) }
        let sortedNums = strNums.sorted { $0 + $1 > $1 + $0 }
        if sortedNums[0] == "0" {
            return "0"
        }
        return sortedNums.joined()
    }
}

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

Задача: 852. Peak Index in a Mountain Array
Сложность: medium

Вам дан целочисленный массив горы arr длины n, где значения увеличиваются до пикового элемента, а затем уменьшаются.

Верните индекс пикового элемента.

Ваша задача — решить это с временной сложностью O(log(n)).

Пример:

Input: arr = [0,1,0]

Output: 1

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

1⃣Создайте целочисленную переменную i и инициализируйте её значением 0.

2⃣Используя цикл while, проверьте, если текущий элемент, на который указывает i, меньше следующего элемента на индексе i + 1. Если arr[i] < arr[i + 1], увеличьте i на 1.

3⃣В противном случае, если arr[i] > arr[i + 1], верните i.

😎 Решение:

class Solution {
    func peakIndexInMountainArray(_ arr: [Int]) -> Int {
        var i = 0
        while arr[i] < arr[i + 1] {
            i += 1
        }
        return i
    }
}

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

Задача: 1209. Remove All Adjacent Duplicates in String II
Сложность: medium

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

Пример:

Input: s = "deeedbbcccbdaa", k = 3
Output: "aa"
Explanation: 
First delete "eee" and "ccc", get "ddbbbdaa"
Then delete "bbb", get "dddaa"
Finally delete "ddd", get "aa"

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

1⃣Инициализировать медленный указатель j значением 0 и стек counts для хранения количества одинаковых символов.

2⃣Перемещать быстрый указатель i по строке s:
Копировать s[i] в s[j].
Если s[j] совпадает с s[j - 1], увеличить значение на вершине стека.
Иначе добавить 1 в стек.
Если количество символов равно k, уменьшить j на k и извлечь из стека.

3⃣Вернуть первые j символов строки.

😎 Решение:

class Solution {
    func removeDuplicates(_ s: String, _ k: Int) -> String {
        var counts = [Int]()
        var sa = Array(s)
        var j = 0
        
        for i in 0..<sa.count {
            sa[j] = sa[i]
            if j == 0 || sa[j] != sa[j - 1] {
                counts.append(1)
            } else {
                let incremented = counts.removeLast() + 1
                if incremented == k {
                    j -= k
                } else {
                    counts.append(incremented)
                }
            }
            j += 1
        }
        return String(sa[..<j])
    }
}

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

Задача: 1202. Smallest String With Swaps
Сложность: medium

Вам дана строка s и массив пар индексов в строке pairs, где pairs[i] = [a, b] указывает на 2 индекса (начиная с 0) в строке.
Вы можете менять местами символы в любой паре индексов в заданных парах любое количество раз.
Верните лексикографически наименьшую строку, которую можно получить после выполнения перестановок.

Пример:

Input: s = "dcab", pairs = [[0,3],[1,2]]
Output: "bacd"
Explaination: 
Swap s[0] and s[3], s = "bcad"
Swap s[1] and s[2], s = "bacd"

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

1⃣Создание списка смежности:
Итеративно пройдитесь по парам и создайте список смежности adj, где adj[source] содержит все смежные вершины вершины source.

2⃣Обход графа и сбор индексов и символов:
Итеративно пройдитесь по индексам от 0 до s.size() - 1. Для каждого индекса vertex:
- выполните DFS, если вершина еще не посещена (visited[vertex] = false).
- во время выполнения DFS сохраняйте vertex в список indices и символ s[vertex] в список characters.

3⃣Сортировка и построение результирующей строки:
Отсортируйте списки indices и characters.
Пройдитесь по индексам и символам, и разместите i-й символ в i-й индекс результирующей строки smallestString.
Верните smallestString.

😎 Решение:

class Solution {
    func smallestStringWithSwaps(_ s: String, _ pairs: [[Int]]) -> String {
        var adj = Array(repeating: [Int](), count: s.count)
        for pair in pairs {
            adj[pair[0]].append(pair[1])
            adj[pair[1]].append(pair[0])
        }
        
        var visited = Array(repeating: false, count: s.count)
        var sArray = Array(s)
        
        func dfs(_ node: Int, _ indices: inout [Int], _ chars: inout [Character]) {
            visited[node] = true
            indices.append(node)
            chars.append(sArray[node])
            for neighbor in adj[node] {
                if !visited[neighbor] {
                    dfs(neighbor, &indices, &chars)
                }
            }
        }
        
        for i in 0..<s.count {
            if !visited[i] {
                var indices = [Int]()
                var chars = [Character]()
                dfs(i, &indices, &chars)
                indices.sort()
                chars.sort()
                for (index, char) in zip(indices, chars) {
                    sArray[index] = char
                }
            }
        }
        
        return String(sArray)
    }
}

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

Задача: 56. Merge Intervals
Сложность: medium

Дан массив интервалов, где intervals[i] = [starti, endi]. Объедините все перекрывающиеся интервалы и верните массив неперекрывающихся интервалов, которые покрывают все интервалы во входных данных.

Пример:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

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

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

2⃣Определение компонент связности:
Для определения, в какой компоненте связности находится каждый узел, мы выполняем обходы графа от произвольных непосещенных узлов до тех пор, пока все узлы не будут посещены. Для эффективности мы храним посещенные узлы в множестве (Set), что позволяет проводить проверки на принадлежность и вставку за константное время.

3⃣Объединение интервалов внутри компонент:
Наконец, мы рассматриваем каждую связную компоненту, объединяя все её интервалы, создавая новый интервал с началом, равным минимальному началу среди всех интервалов в компоненте, и концом, равным максимальному концу.

😎 Решение:

import Foundation

class Solution {
    var graph = [Array<Int>: [[Int]]]()
    var nodesInComp = [Int: [[Int]]]()
    var visited = Set<Array<Int>>()

    func overlap(_ a: [Int], _ b: [Int]) -> Bool {
        return a[0] <= b[1] && b[0] <= a[1]
    }

    func buildGraph(_ intervals: [[Int]]) {
        for interval1 in intervals {
            for interval2 in intervals {
                if overlap(interval1, interval2) {
                    graph[interval1, default: []].append(interval2)
                    graph[interval2, default: []].append(interval1)
                }
            }
        }
    }

    func mergeNodes(_ nodes: [[Int]]) -> [Int] {
        var minStart = nodes[0][0]
        for node in nodes {
            minStart = min(minStart, node[0])
        }

        var maxEnd = nodes[0][1]
        for node in nodes {
            maxEnd = max(maxEnd, node[1])
        }

        return [minStart, maxEnd]
    }

    func markComponentDFS(_ start: [Int], _ compNumber: Int) {
        var stack = [[Int]]()
        stack.append(start)

        while !stack.isEmpty {
            let node = stack.removeLast()
            if !visited.contains(node) {
                visited.insert(node)
                nodesInComp[compNumber, default: []].append(node)

                for child in graph[node, default: []] {
                    stack.append(child)
                }
            }
        }
    }

    func buildComponents(_ intervals: [[Int]]) {
        var compNumber = 0

        for interval in intervals {
            if !visited.contains(interval) {
                markComponentDFS(interval, compNumber)
                compNumber += 1
            }
        }
    }

    func merge(_ intervals: [[Int]]) -> [[Int]] {
        buildGraph(intervals)
        buildComponents(intervals)

        var merged = [[Int]]()
        for comp in 0..<nodesInComp.count {
            if let nodes = nodesInComp[comp] {
                merged.append(mergeNodes(nodes))
            }
        }

        return merged
    }
}

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

Задача: 473. Matchsticks to Square
Сложность: medium

Дано целочисленный массив спичек, где matchsticks[i] — это длина i-й спички. Необходимо использовать все спички для создания одного квадрата. Нельзя ломать никакую спичку, но можно соединять их, при этом каждая спичка должна быть использована ровно один раз.

Вернуть true, если можно составить квадрат, и false в противном случае.

Пример:

Input: matchsticks = [1,1,2,2,2]
Output: true
Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.

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

1⃣Определяем рекурсивную функцию, которая принимает текущий индекс обрабатываемой спички и количество сторон квадрата, которые уже полностью сформированы. Базовый случай для рекурсии: если все спички использованы и сформировано 4 стороны, возвращаем True.

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

3⃣Если какой-либо из рекурсивных вызовов возвращает True, возвращаем True, в противном случае возвращаем False.

😎 Решение:

class Solution {
    var nums: [Int] = []
    var sums: [Int] = [0, 0, 0, 0]
    var possibleSquareSide: Int = 0

    func dfs(_ index: Int) -> Bool {
        if index == nums.count {
            return sums[0] == sums[1] && sums[1] == sums[2] && sums[2] == sums[3]
        }

        let element = nums[index]

        for i in 0..<4 {
            if sums[i] + element <= possibleSquareSide {
                sums[i] += element
                if dfs(index + 1) {
                    return true
                }
                sums[i] -= element
            }
        }

        return false
    }

    func makesquare(_ nums: [Int]) -> Bool {
        if nums.isEmpty {
            return false
        }

        let perimeter = nums.reduce(0, +)
        possibleSquareSide = perimeter / 4
        if possibleSquareSide * 4 != perimeter {
            return false
        }

        self.nums = nums.sorted(by: >)
        return dfs(0)
    }
}

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

Задача: 441. Arranging Coins
Сложность: easy

У вас есть n монет, и вы хотите построить лестницу из этих монет. Лестница состоит из k рядов, где i-й ряд содержит ровно i монет. Последний ряд лестницы может быть неполным.

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

Пример:

Input: n = 5
Output: 2
Explanation: Because the 3rd row is incomplete, we return 2.

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

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

2⃣Напомним, что условие задачи можно выразить следующим образом: k(k + 1) ≤ 2N.

3⃣Это можно решить методом выделения полного квадрата, (k + 1/2)² - 1/4 ≤ 2N. Что приводит к следующему ответу: k = [sqrt(2N + 1/4) - 1/2].

😎 Решение:

class Solution {
    func arrangeCoins(_ n: Int) -> Int {
        return Int(sqrt(Double(2 * n) + 0.25) - 0.5)
    }
}

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

Задача: 1203. Sort Items by Groups Respecting Dependencies
Сложность: hard

Есть n предметов, каждый из которых принадлежит нулевой или одной из m групп, где group[i] — это группа, к которой принадлежит i-й предмет, и равно -1, если i-й предмет не принадлежит никакой группе. Предметы и группы имеют индексацию с нуля. Группа может не иметь ни одного предмета.

Верните отсортированный список предметов таким образом:
Предметы, принадлежащие одной группе, расположены рядом друг с другом в отсортированном списке.
Существуют некоторые отношения между этими предметами, где beforeItems[i] — это список, содержащий все предметы, которые должны быть перед i-м предметом в отсортированном массиве (слева от i-го предмета).
Верните любое решение, если существует более одного решения, и верните пустой список, если решения не существует.

Пример:

Input: n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]
Output: [6,3,4,1,5,2,0,7]

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

1⃣Инициализация и создание графов:
Присвоить уникальные идентификаторы группам для элементов без группы.
Создать два графа: item_graph для элементов и group_graph для групп. Также создать два массива для учета входящих рёбер для элементов и групп.

2⃣Построение графов:
Пройти по массиву beforeItems и добавить зависимости между элементами в item_graph, увеличивая счётчик входящих рёбер.
Если элементы принадлежат разным группам, добавить зависимость между группами в group_graph, увеличивая счётчик входящих рёбер.

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

😎 Решение:

class Solution {
    func sortItems(_ n: Int, _ m: Int, _ group: [Int], _ beforeItems: [[Int]]) -> [Int] {
        var group = group
        var groupId = m
        for i in 0..<n {
            if group[i] == -1 {
                group[i] = groupId
                groupId += 1
            }
        }

        var itemGraph = [Int: [Int]]()
        var itemIndegree = [Int](repeating: 0, count: n)
        for i in 0..<n { itemGraph[i] = [] }

        var groupGraph = [Int: [Int]]()
        var groupIndegree = [Int](repeating: 0, count: groupId)
        for i in 0..<groupId { groupGraph[i] = [] }

        for curr in 0..<n {
            for prev in beforeItems[curr] {
                itemGraph[prev]?.append(curr)
                itemIndegree[curr] += 1
                if group[curr] != group[prev] {
                    groupGraph[group[prev]]?.append(group[curr])
                    groupIndegree[group[curr]] += 1
                }
            }
        }

        let itemOrder = topologicalSort(itemGraph, itemIndegree)
        let groupOrder = topologicalSort(groupGraph, groupIndegree)
        if itemOrder.isEmpty || groupOrder.isEmpty { return [] }

        var orderedGroups = [Int: [Int]]()
        for item in itemOrder { orderedGroups[group[item], default: []].append(item) }

        var answerList = [Int]()
        for groupIndex in groupOrder { answerList.append(contentsOf: orderedGroups[groupIndex, default: []]) }

        return answerList
    }

    private func topologicalSort(_ graph: [Int: [Int]], _ indegree: [Int]) -> [Int] {
        var visited = [Int]()
        var stack = [Int]()
        for key in graph.keys { if indegree[key] == 0 { stack.append(key) } }

        while !stack.isEmpty {
            let curr = stack.removeLast()
            visited.append(curr)
            for next in graph[curr, default: []] { if --indegree[next] == 0 { stack.append(next) } }
        }

        return visited.count == graph.keys.count ? visited : []
    }
}

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

Задача: 1344. Angle Between Hands of a Clock
Сложность: medium

Даны два числа, hour и minutes. Вернуть меньший угол (в градусах), образованный часовой и минутной стрелками.

Ответы с точностью до 10^-5 от фактического значения будут считаться правильными.

Пример:

Input: hour = 12, minutes = 30
Output: 165

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

1⃣Рассчитать углы: minutes_angle = 6 * minutes и hour_angle = (hour % 12 + minutes / 60) * 30.

2⃣Найти разницу: diff = abs(hour_angle - minutes_angle).

3⃣Вернуть меньший угол: min(diff, 360 - diff).

😎 Решение:

class Solution {
    func angleClock(_ hour: Int, _ minutes: Int) -> Double {
        let oneMinAngle = 6.0
        let oneHourAngle = 30.0

        let minutesAngle = oneMinAngle * Double(minutes)
        let hourAngle = (Double(hour % 12) + Double(minutes) / 60.0) * oneHourAngle

        let diff = abs(hourAngle - minutesAngle)
        return min(diff, 360 - diff)
    }
}

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

Задача: 1182. Shortest Distance to Target Color
Сложность: medium

Дан массив colors, содержащий три цвета: 1, 2 и 3.

Также даны несколько запросов. Каждый запрос состоит из двух целых чисел i и c. Верните наименьшее расстояние между заданным индексом i и целевым цветом c. Если решения нет, верните -1.

Пример:

Input: colors = [1,1,2,1,3,2,2,3,3], queries = [[1,3],[2,2],[6,1]]
Output: [3,0,3]
Explanation: 
The nearest 3 from index 1 is at index 4 (3 steps away).
The nearest 2 from index 2 is at index 2 itself (0 steps away).
The nearest 1 from index 6 is at index 3 (3 steps away).

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

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

2⃣Для каждого запроса, содержащего i и c, если c не является одним из ключей в хэш-таблице, то colors не содержит c, поэтому верните -1. Иначе, найдите позицию i в соответствующем списке индексов indexList для поддержания упорядоченного порядка.

3⃣Если i меньше всех элементов в indexList, то i - indexList[0] является кратчайшим расстоянием. Если i больше всех элементов в indexList, то indexList[indexList.size() - 1] - i является кратчайшим расстоянием. Иначе, ближайшее появление c к i либо на индексе вставки, либо перед ним, поэтому рассчитайте расстояние от i до каждого из них и верните наименьшее.

😎 Решение

class Solution {
    func shortestDistanceColor(_ colors: [Int], _ queries: [[Int]]) -> [Int] {
        var queryResults = [Int]()
        var hashmap = [Int: [Int]]()

        for i in 0..<colors.count {
            hashmap[colors[i], default: [Int]()].append(i)
        }

        for query in queries {
            let target = query[0]
            let color = query[1]
            guard let indexList = hashmap[color] else {
                queryResults.append(-1)
                continue
            }

            let insert = indexList.binarySearch(target)

            if insert < 0 {
                let insertPos = -(insert + 1)
                if insertPos == 0 {
                    queryResults.append(indexList[insertPos] - target)
                } else if insertPos == indexList.count {
                    queryResults.append(target - indexList[insertPos - 1])
                } else {
                    let leftNearest = target - indexList[insertPos - 1]
                    let rightNearest = indexList[insertPos] - target
                    queryResults.append(min(leftNearest, rightNearest))
                }
            } else {
                queryResults.append(0)
            }
        }

        return queryResults
    }
}

extension Array where Element: Comparable {
    func binarySearch(_ value: Element) -> Int {
        var left = 0
        var right = self.count - 1

        while left <= right {
            let mid = (left + right) / 2
            if self[mid] == value {
                return mid
            } else if self[mid] < value {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        return -(left + 1)
    }
}

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

Задача: 734. Sentence Similarity
Сложность: easy

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

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

Пример:

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

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

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

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

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

😎 Решение:

func areSentencesSimilar(_ sentence1: [String], _ sentence2: [String], _ similarPairs: [[String]]) -> Bool {
    if sentence1.count != sentence2.count {
        return false
    }
    
    var similar = [String: Set<String>]()
    for pair in similarPairs {
        let (x, y) = (pair[0], pair[1])
        if similar[x] == nil {
            similar[x] = Set<String>()
        }
        if similar[y] == nil {
            similar[y] = Set<String>()
        }
        similar[x]!.insert(y)
        similar[y]!.insert(x)
    }
    
    for (w1, w2) in zip(sentence1, sentence2) {
        if w1 != w2 && (similar[w1] == nil || !similar[w1]!.contains(w2)) {
            return false
        }
    }
    
    return true
}

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

Задача: 644. Maximum Average Subarray II
Сложность: hard

Вам дан целочисленный массив nums, состоящий из n элементов, и целое число k. Найдите смежный подмассив, длина которого больше или равна k и который имеет максимальное среднее значение, и верните это значение. Принимается любой ответ с погрешностью вычислений менее 10-5.

Пример:

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000

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

1⃣Используйте скользящее окно длины k для нахождения начального среднего значения.

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

3⃣Следите за максимальным средним значением и верните его после проверки всех возможных окон.

😎 Решение:

func findMaxAverage(_ nums: [Int], _ k: Int) -> Double {
    var currSum = nums[0..<k].reduce(0, +)
    var maxSum = currSum
    for i in k..<nums.count {
        currSum += nums[i] - nums[i - k]
        if currSum > maxSum {
            maxSum = currSum
        }
    }
    return Double(maxSum) / Double(k)
}

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

Задача: 766. Toeplitz Matrix
Сложность: easy

Дана матрица размером m x n. Вернуть true, если матрица является Тёплицевой. В противном случае вернуть false.

Матрица является Тёплицевой, если все диагонали, идущие от верхнего левого к нижнему правому углу, содержат одинаковые элементы.

Пример:

Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Output: true
Explanation:
In the above grid, the diagonals are:
"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]".
In each diagonal all elements are the same, so the answer is True.

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

1⃣Что отличает две координаты (r1, c1) и (r2, c2) на одной диагонали? Оказывается, две координаты находятся на одной диагонали тогда и только тогда, когда r1 - c1 == r2 - c2.м

2⃣Это приводит к следующей идее: запоминайте значение этой диагонали как groups[r - c]. Если обнаружено несоответствие, то матрица не является Тёплицевой; в противном случае, она является таковой.

3⃣Таким образом, для каждой ячейки матрицы сохраняйте значение диагонали в словаре groups с ключом r - c. Проходите по всем ячейкам матрицы и проверяйте, совпадает ли текущее значение с сохранённым в groups. Если где-то обнаруживается несоответствие, верните false. Если все элементы соответствуют, верните true.

😎 Решение:

class Solution {
    func isToeplitzMatrix(_ matrix: [[Int]]) -> Bool {
        var groups = [Int: Int]()
        for r in 0..<matrix.count {
            for c in 0..<matrix[0].count {
                if groups[r - c] == nil {
                    groups[r - c] = matrix[r][c]
                } else if groups[r - c] != matrix[r][c] {
                    return false
                }
            }
        }
        return true
    }
}

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

Задача: 1021. Remove Outermost Parentheses
Сложность: easy

Например, "", "()", "(" + A + ")" или A + B, где A и B - допустимые строки со скобками, а + означает объединение строк. Все допустимые строки со скобками - "", "()", "(())()" и "(()(())".
Допустимая строка со скобками s является примитивной, если она непустая и не существует способа разбить ее на s = A + B, причем A и B - непустые допустимые строки со скобками. Если дана допустимая строка со скобками s, рассмотрим ее примитивное разложение: s = P1 + P2 + ... + Pk, где Pi - примитивные допустимые строки со скобками. Верните s после удаления крайних скобок из каждой примитивной строки в примитивном разложении s.

Пример:

Input: s = "(()())(())"
Output: "()()()"

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

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

2⃣Обработка строки:
Итерируйте по каждому символу строки.
Если встречаете (, увеличивайте счетчик уровня вложенности. Если уровень вложенности больше 1, добавьте ( в результат.
Если встречаете ), уменьшайте счетчик уровня вложенности. Если уровень вложенности больше 0 перед уменьшением, добавьте ) в результат.

3⃣Возврат результата:
Верните результат, содержащий строку без крайних скобок из каждой примитивной строки.

😎 Решение:

class Solution {
    func removeOuterParentheses(_ s: String) -> String {
        var result = ""
        var level = 0
        
        for char in s {
            if char == "(" {
                if level > 0 {
                    result.append(char)
                }
                level += 1
            } else {
                level -= 1
                if level > 0 {
                    result.append(char)
                }
            }
        }
        
        return result
    }
}

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

Задача: 955. Delete Columns to Make Sorted II
Сложность: medium

Вам дан массив из n строк одинаковой длины. Мы можем выбрать любые индексы удаления и удалить все символы в этих индексах для каждой строки.

Например, если у нас есть strs = ["abcdef", "uvwxyz"] и индексы удаления {0, 2, 3}, то конечный массив после удаления будет ["bef", "vyz"]. Предположим, что мы выбрали набор индексов удаления answer таким образом, что после удаления конечный массив имеет элементы в лексикографическом порядке (т.е, strs[0] <= strs[1] <= strs[2] <= ... <= strs[n - 1]). Возвращает минимально возможное значение answer.length.

Пример:

Input: strs = ["ca","bb","ac"]
Output: 1

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

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

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

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

😎 Решение:

class Solution {
    func minDeletionSize(_ strs: [String]) -> Int {
        let n = strs.count
        let m = strs[0].count
        var deleteCount = [Bool](repeating: false, count: m)
        
        func isSorted() -> Bool {
            for i in 0..<n - 1 {
                for j in 0..<m {
                    if deleteCount[j] { continue }
                    if strs[i][strs[i].index(strs[i].startIndex, offsetBy: j)] >
                       strs[i + 1][strs[i + 1].index(strs[i + 1].startIndex, offsetBy: j)] {
                        return false
                    }
                    if strs[i][strs[i].index(strs[i].startIndex, offsetBy: j)] <
                       strs[i + 1][strs[i + 1].index(strs[i + 1].startIndex, offsetBy: j)] {
                        break
                    }
                }
            }
            return true
        }
        
        while !isSorted() {
            for j in 0..<m {
                if deleteCount[j] { continue }
                for i in 0..<n - 1 {
                    if strs[i][strs[i].index(strs[i].startIndex, offsetBy: j)] >
                       strs[i + 1][strs[i + 1].index(strs[i + 1].startIndex, offsetBy: j)] {
                        deleteCount[j] = true
                        break
                    }
                }
                if deleteCount[j] { break }
            }
        }
        
        return deleteCount.filter { $0 }.count
    }
}

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

Задача: 278. First Bad Version
Сложность: easy

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

Предположим, у вас есть n версий [1, 2, ..., n], и вы хотите выяснить первую плохую версию, которая вызывает все последующие версии быть плохими.

Вам предоставлен API bool isBadVersion(version), который возвращает, является ли версия плохой. Реализуйте функцию для нахождения первой плохой версии. Вы должны минимизировать количество вызовов API.

Пример:

Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.

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

1⃣Инициализация границ поиска:
Устанавливаем начальные значения левой и правой границ поиска: left = 1 и right = n.

2⃣Бинарный поиск:
Пока левая граница меньше правой, находим среднюю точку mid и проверяем, является ли она плохой версией с помощью isBadVersion(mid).
Если текущая версия mid плохая, смещаем правую границу к mid, иначе смещаем левую границу на mid + 1.

3⃣Возврат результата:
Когда левая граница станет равной правой, возвращаем left как индекс первой плохой версии.

😎 Решение:

class Solution {
    func firstBadVersion(_ n: Int) -> Int {
        var left = 1
        var right = n
        while left < right {
            let mid = left + (right - left) / 2
            if isBadVersion(mid) {
                right = mid
            } else {
                left = mid + 1
            }
        }
        return left
    }
}

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

Задача: 1236. Web Crawler
Сложность: medium

Учитывая url startUrl и интерфейс HtmlParser, реализуйте веб-краулер для просмотра всех ссылок, которые находятся под тем же именем хоста, что и startUrl.Верните все ссылки, полученные вашим краулером, в любом порядке. Ваш краулер должен: Начинать со страницы: startUrl Вызывать HtmlParser.getUrls(url), чтобы получить все ссылки с веб-страницы с заданным url. Не просматривайте одну и ту же ссылку дважды. Исследуйте только те ссылки, которые находятся под тем же именем хоста, что и startUrl. Как показано в примере url выше, имя хоста - example.org. Для простоты можно считать, что все урлы используют протокол http без указания порта. Например, урлы https://leetcode.com/problems и https://leetcode.com/contest находятся под одним и тем же именем хоста, а урлы https://example.org/test и https://example.com/abc не находятся под одним и тем же именем хоста.

Пример:

Input:
urls = [
  "https://news.yahoo.com",
  "https://news.yahoo.com/news",
  "https://news.yahoo.com/news/topics/",
  "https://news.google.com",
  "https://news.yahoo.com/us"
]
edges = [[2,0],[2,1],[3,2],[3,1],[0,4]]
startUrl = "https://news.yahoo.com/news/topics/"
Output: [
  "https://news.yahoo.com",
  "https://news.yahoo.com/news",
  "https://news.yahoo.com/news/topics/",
  "https://news.yahoo.com/us"
]

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

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

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

3⃣Если да, и если мы еще не посещали эту ссылку, добавляем ее в очередь и отмечаем как посещенную.

😎 Решение:

class HtmlParser {
    func getUrls(_ url: String) -> [String] {
        return []
    }
}

func extractHostname(_ url: String) -> String {
    if let host = URL(string: url)?.host {
        return host
    }
    return ""
}

func crawl(_ startUrl: String, _ htmlParser: HtmlParser) -> [String] {
    let hostname = extractHostname(startUrl)
    var visited = Set<String>()
    var queue = [startUrl]
    visited.insert(startUrl)
    
    while !queue.isEmpty {
        let url = queue.removeFirst()
        for nextUrl in htmlParser.getUrls(url) {
            if !visited.contains(nextUrl) && extractHostname(nextUrl) == hostname {
                visited.insert(nextUrl)
                queue.append(nextUrl)
            }
        }
    }
    
    return Array(visited)
}

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

Задача: 305. Number of Islands II
Сложность: hard

Дан пустой двумерный бинарный массив 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
    }
}

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

Задача: 1120. Maximum Average Subtree
Сложность: medium

Дан корень бинарного дерева. Верните максимальное среднее значение поддерева этого дерева. Ответы, отличающиеся от фактического ответа не более чем на 10^-5, будут приняты.

Поддерево дерева — это любой узел этого дерева плюс все его потомки.

Среднее значение дерева — это сумма его значений, деленная на количество узлов.

Пример:

Input: root = [5,6,1]
Output: 6.00000
Explanation: 
For the node with value = 5 we have an average of (5 + 6 + 1) / 3 = 4.
For the node with value = 6 we have an average of 6 / 1 = 6.
For the node with value = 1 we have an average of 1 / 1 = 1.
So the answer is 6 which is the maximum.

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

1⃣Инициализация и определение State:
Определите класс State для хранения количества узлов в поддереве, суммы значений узлов в поддереве и максимального среднего значения поддерева.

2⃣Постобход (postorder traversal):
Реализуйте функцию maxAverage, которая выполняет постобход дерева, вычисляя nodeCount, valueSum и maxAverage для каждого узла, начиная с дочерних узлов и продвигаясь к родительским узлам.

3⃣Вычисление максимального среднего значения:
Используйте значения, полученные от дочерних узлов, для вычисления среднего значения для текущего узла и обновите maxAverage, если новое среднее значение больше текущего максимума.

😎 Решение:

class Solution {
    class State {
        var nodeCount: Int
        var valueSum: Int
        var maxAverage: Double
        
        init(_ nodes: Int, _ sum: Int, _ maxAvg: Double) {
            self.nodeCount = nodes
            self.valueSum = sum
            self.maxAverage = maxAvg
        }
    }
    
    func maximumAverageSubtree(_ root: TreeNode?) -> Double {
        return maxAverage(root).maxAverage
    }
    
    private func maxAverage(_ root: TreeNode?) -> State {
        guard let node = root else {
            return State(0, 0, 0)
        }
        
        let left = maxAverage(node.left)
        let right = maxAverage(node.right)
        
        let nodeCount = left.nodeCount + right.nodeCount + 1
        let sum = left.valueSum + right.valueSum + node.val
        let currentAverage = Double(sum) / Double(nodeCount)
        let maxAverage = max(currentAverage, max(left.maxAverage, right.maxAverage))
        
        return State(nodeCount, sum, maxAverage)
    }
}

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

Задача: 1161. Maximum Level Sum of a Binary Tree
Сложность: medium

Дано корневое дерево, уровень корня которого равен 1, уровень его детей равен 2 и так далее.

Верните наименьший уровень x, такой что сумма всех значений узлов на уровне x максимальна.

Пример:

Input: root = [1,7,0,7,-8,null,null]
Output: 2
Explanation: 
Level 1 sum = 1.
Level 2 sum = 7 + 0 = 7.
Level 3 sum = 7 + -8 = -1.
So we return the level with the maximum sum which is level 2.

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

1⃣Создайте целочисленную переменную maxSum для отслеживания максимальной суммы значений узлов на любом уровне, начав с большого отрицательного значения. Создайте переменную ans для хранения ответа на задачу. Создайте переменную level для хранения текущего уровня, через который мы проходим, и инициализируйте её значением 0. Инициализируйте очередь q типа TreeNode и добавьте в неё корень.

2⃣Выполните обход в ширину (BFS) до тех пор, пока очередь не станет пустой: увеличьте level на 1 и инициализируйте sumAtCurrentLevel = 0 для вычисления суммы всех значений узлов на этом уровне. Проходите через все узлы на уровне, используя только q.size() количество узлов. Внутри этого внутреннего цикла извлекайте все узлы на текущем уровне один за другим, добавляя их значения к sumAtCurrentLevel и добавляя левых и правых детей (если они существуют) в очередь. Поймите, что после прохождения всех узлов на уровне в очереди остаются только узлы уровня +1.

3⃣После прохождения всех узлов на уровне проверьте, больше ли sumAtCurrentLevel, чем maxSum. Если maxSum < sumAtCurrentLevel, обновите переменную ответа на ans = level и установите maxSum = sumAtCurrentLevel. Верните ans.

😎 Решение

class Solution {
    func maxLevelSum(_ root: TreeNode?) -> Int {
        var maxSum = Int.min
        var ans = 0, level = 0
        var q = [TreeNode]()
        
        if let root = root {
            q.append(root)
        }
        
        while !q.isEmpty {
            level += 1
            var sumAtCurrentLevel = 0
            for _ in 0..<q.count {
                let node = q.removeFirst()
                sumAtCurrentLevel += node.val
                if let left = node.left {
                    q.append(left)
                }
                if let right = node.right {
                    q.append(right)
                }
            }
            
            if maxSum < sumAtCurrentLevel {
                maxSum = sumAtCurrentLevel
                ans = level
            }
        }
        
        return ans
    }
}

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