Задача: 560. Subarray Sum Equals K
Сложность: medium

Дан массив целых чисел nums и целое число k, вернуть общее количество подмассивов, сумма которых равна k.

Подмассив - это непрерывная непустая последовательность элементов внутри массива.

Пример:

Input: nums = [1,1,1], k = 2
Output: 2

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

1⃣Самый простой метод - рассмотреть каждый возможный подмассив данного массива nums.

2⃣Найти сумму элементов каждого из этих подмассивов и проверить равенство полученной суммы с заданным k.

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

😎 Решение:

class Solution {
    func subarraySum(_ nums: [Int], _ k: Int) -> Int {
        var count = 0
        for start in 0..<nums.count {
            for end in (start + 1)...nums.count {
                var sum = 0
                for i in start..<end {
                    sum += nums[i]
                }
                if sum == k {
                    count += 1
                }
            }
        }
        return count
    }
}

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

Задача: 369. Plus One Linked List
Сложность: hard

Дано неотрицательное целое число, представленное в виде связного списка цифр. Добавить к этому числу единицу.

Цифры хранятся таким образом, что самая значимая цифра находится в начале списка.

Пример:

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

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

1⃣Инициализируйте стражевой узел как ListNode(0) и установите его как новую голову списка: sentinel.next = head. Найдите крайний правый элемент, не равный девяти.

2⃣Увеличьте найденную цифру на единицу и установите все следующие девятки в ноль.

3⃣Верните sentinel, если его значение было установлено на 1, иначе верните head (sentinel.next).

😎 Решение:

class ListNode {
    var val: Int
    var next: ListNode?
    init(_ val: Int) { self.val = val; self.next = nil }
}

class Solution {
    func plusOne(_ head: ListNode?) -> ListNode? {
        let sentinel = ListNode(0)
        sentinel.next = head
        var notNine = sentinel

        var current = head
        while current != nil {
            if current!.val != 9 {
                notNine = current!
            }
            current = current!.next
        }

        notNine.val += 1
        notNine = notNine.next

        while notNine != nil {
            notNine!.val = 0
            notNine = notNine!.next
        }

        return sentinel.val == 0 ? sentinel.next : sentinel
    }
}

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

Задача: 1376. Time Needed to Inform All Employees
Сложность: medium

В компании работает n сотрудников, каждому из которых присвоен уникальный идентификатор от 0 до n - 1. Руководитель компании имеет идентификатор headID.

У каждого сотрудника есть один непосредственный начальник, указанный в массиве manager, где manager[i] — это непосредственный начальник i-го сотрудника, manager[headID] = -1. Также гарантируется, что отношения подчинения образуют древовидную структуру.

Руководитель компании хочет сообщить всем сотрудникам компании срочную новость. Он сообщит своим непосредственным подчиненным, а они сообщат своим подчиненным и так далее, пока все сотрудники не узнают о срочной новости.

i-й сотрудник нуждается в informTime[i] минутах, чтобы сообщить всем своим непосредственным подчиненным (т.е. через informTime[i] минут все его непосредственные подчиненные могут начать распространять новость).

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

Пример:

Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
Output: 1
Explanation: The head of the company with id = 2 is the direct manager of all the employees in the company and needs 1 minute to inform them all.
The tree structure of the employees in the company is shown.

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

1⃣Создайте список смежности adjList; индекс i будет хранить смежные узлы для сотрудника с идентификатором i.

2⃣Итерируйте по сотрудникам от 0 до N - 1, и для каждого сотрудника i добавляйте ребро manager[i] -> i, если manager[i] не равен -1.

3⃣Начните выполнение DFS с узла headID и временем 0 для каждого узла как curr. Обновите максимальное время maxTime, сравнив его с текущим временем. Итерируйте по смежным узлам curr и для каждого смежного узла выполните DFS с временем time + informTime[curr]. Когда DFS завершится, верните maxTime.

😎 Решение:

class Solution {
    var maxTime = Int.min
    
    func DFS(_ adjList: [[Int]], _ informTime: [Int], _ curr: Int, _ time: Int) {
        maxTime = max(maxTime, time)
        for adjacent in adjList[curr] {
            DFS(adjList, informTime, adjacent, time + informTime[curr])
        }
    }
    
    func numOfMinutes(_ n: Int, _ headID: Int, _ manager: [Int], _ informTime: [Int]) -> Int {
        var adjList = Array(repeating: [Int](), count: n)
        for i in 0..<n {
            if manager[i] != -1 {
                adjList[manager[i]].append(i)
            }
        }
        DFS(adjList, informTime, headID, 0)
        return maxTime
    }
}

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

Задача: 358. Rearrange String k Distance Apart
Сложность: hard

Дана строка s и целое число k, переставьте символы в s так, чтобы одинаковые символы находились на расстоянии не менее k друг от друга. Если невозможно переставить строку, верните пустую строку "".

Пример:

Input: s = "aabbcc", k = 3
Output: "abcabc"
Explanation: The same letters are at least a distance of 3 from each other.

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

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

2⃣Разделите символы на группы по частоте и создайте сегменты для размещения символов.

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

😎 Решение:

class Solution {
    func rearrangeString(_ s: String, _ k: Int) -> String {
        var freqs = [Character: Int]()
        var maxFreq = 0
        
        for char in s {
            freqs[char, default: 0] += 1
            maxFreq = max(maxFreq, freqs[char]!)
        }

        var mostChars = Set<Character>()
        var secondChars = Set<Character>()
        
        for (char, freq) in freqs {
            if freq == maxFreq {
                mostChars.insert(char)
            } else if freq == maxFreq - 1 {
                secondChars.insert(char)
            }
        }

        var segments = [String](repeating: "", count: maxFreq)

        for char in mostChars {
            for i in 0..<maxFreq {
                segments[i].append(char)
            }
        }
        for char in secondChars {
            for i in 0..<maxFreq-1 {
                segments[i].append(char)
            }
        }

        var segmentId = 0
        for (char, freq) in freqs {
            if mostChars.contains(char) || secondChars.contains(char) {
                continue
            }
            for _ in 0..<freq {
                segments[segmentId].append(char)
                segmentId = (segmentId + 1) % (maxFreq - 1)
            }
        }

        for i in 0..<maxFreq-1 {
            if segments[i].count < k {
                return ""
            }
        }

        return segments.joined()
    }
}

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

Задача: 645. Set Mismatch
Сложность: easy

У вас есть набор целых чисел s, который изначально содержит все числа от 1 до n. К сожалению, из-за какой-то ошибки одно из чисел в s продублировалось в другое число в наборе, что привело к повторению одного числа и потере другого. Вам дан целочисленный массив nums, представляющий состояние данных в этом наборе после ошибки. Найдите число, которое встречается дважды, и число, которое отсутствует, и верните их в виде массива.

Пример:

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

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

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

2⃣Определите отсутствующее число, используя сумму чисел от 1 до n и текущую сумму массива.

3⃣Верните дублированное и отсутствующее числа в виде массива.

😎 Решение:

func findErrorNums(_ nums: [Int]) -> [Int] {
    var numSet = Set<Int>()
    var duplicate = -1
    let n = nums.count
    for num in nums {
        if numSet.contains(num) {
            duplicate = num
        }
        numSet.insert(num)
    }
    let missing = (n * (n + 1)) / 2 - numSet.reduce(0, +)
    return [duplicate, missing]
}

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

Задача: 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
    }
}

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