Задача: 189. Rotate Array
Сложность: medium

Для целочисленного массива nums, поверните массив вправо на k шагов, где k — неотрицательное число.

Пример:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

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

1⃣Создаем дополнительный массив, в который будем помещать каждый элемент исходного массива на его новую позицию. Элемент на позиции i в исходном массиве будет размещен на индексе (i+k) % длина массива.

2⃣Копируем элементы из нового массива в исходный массив, сохраняя новый порядок элементов.

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

😎 Решение:

class Solution {
    func rotate(_ nums: inout [Int], _ k: Int) {
        let n = nums.count
        var a = Array(repeating: 0, count: n)
        for i in 0..<n {
            a[(i + k) % n] = nums[i]
        }
        for i in 0..<n {
            nums[i] = a[i]
        }
    }
}

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

Задача: 413. Arithmetic Slices
Сложность: medium

Целочисленный массив называется арифметическим, если он состоит не менее чем из трех элементов и если разность между любыми двумя последовательными элементами одинакова. Например, [1,3,5,7,9], [7,7,7] и [3,-1,-5,-9] являются арифметическими последовательностями. Если задан целочисленный массив nums, верните количество арифметических подмассивов массива nums. Подмассив - это непрерывная подпоследовательность массива.

Пример:

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

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

1⃣Пройдите по массиву, инициализируя два указателя: начальный и текущий. Начните с первой пары элементов.

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

3⃣Суммируйте количество найденных арифметических подмассивов, учитывая, что для каждого арифметического подмассива длины len, количество таких подмассивов равно (len - 2).

😎 Решение:

func numberOfArithmeticSlices(_ nums: [Int]) -> Int {
    guard nums.count >= 3 else { return 0 }
    var count = 0
    var currentLength = 0
    for i in 2..<nums.count {
        if nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2] {
            currentLength += 1
            count += currentLength
        } else {
            currentLength = 0
        }
    }
    return count
}

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

Задача: 835. Image Overlap
Сложность: medium

Вам даны два изображения, img1 и img2, представленные как бинарные квадратные матрицы размером n x n. Бинарная матрица содержит только 0 и 1 в качестве значений.
Мы можем сдвигать одно изображение как угодно, перемещая все биты 1 влево, вправо, вверх и/или вниз на любое количество единиц. Затем мы помещаем его поверх другого изображения. После этого мы можем вычислить перекрытие, подсчитав количество позиций, на которых в обоих изображениях есть 1.

Также обратите внимание, что при сдвиге не допускается никакое вращение. Любые биты 1, которые перемещаются за пределы границ матрицы, стираются.

Верните максимальное возможное перекрытие.

Пример:

Input: img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]
Output: 3
Explanation: We translate img1 to right by 1 unit and down by 1 unit.

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

1⃣Определите функцию shiftAndCount(xShift, yShift, M, R), которая смещает матрицу M относительно матрицы R на координаты (xShift, yShift) и подсчитывает количество единиц в зоне перекрытия.

2⃣Организуйте цикл по всем возможным комбинациям координат смещения (xShift, yShift).

3⃣На каждой итерации вызывайте функцию shiftAndCount() дважды для обоих направлений смещения и обновляйте максимальное количество перекрытий.

😎 Решение:

class Solution {
    func shiftAndCount(_ xShift: Int, _ yShift: Int, _ M: [[Int]], _ R: [[Int]]) -> Int {
        var leftShiftCount = 0, rightShiftCount = 0
        var rRow = 0
        for mRow in yShift..<M.count {
            var rCol = 0
            for mCol in xShift..<M.count {
                if M[mRow][mCol] == 1 && M[mRow][mCol] == R[rRow][rCol] {
                    leftShiftCount += 1
                }
                if M[mRow][rCol] == 1 && M[mRow][rCol] == R[rRow][mCol] {
                    rightShiftCount += 1
                }
                rCol += 1
            }
            rRow += 1
        }
        return max(leftShiftCount, rightShiftCount)
    }

    func largestOverlap(_ A: [[Int]], _ B: [[Int]]) -> Int {
        var maxOverlaps = 0
        for yShift in 0..<A.count {
            for xShift in 0..<A.count {
                maxOverlaps = max(maxOverlaps, shiftAndCount(xShift, yShift, A, B))
                maxOverlaps = max(maxOverlaps, shiftAndCount(xShift, yShift, B, A))
            }
        }
        return maxOverlaps
    }
}

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

Задача: 174. Dungeon Game
Сложность: hard

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

Рыцарь имеет начальный запас здоровья, представленный положительным целым числом. Если в какой-то момент его уровень здоровья упадет до 0 или ниже, он умирает мгновенно.

Некоторые комнаты охраняются демонами (представлены отрицательными числами), так что рыцарь теряет здоровье, входя в эти комнаты; другие комнаты либо пусты (обозначены как 0), либо содержат магические сферы, которые увеличивают здоровье рыцаря (представлены положительными числами).

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

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

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

Пример:

Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output: 7
Explanation: The initial health of the knight must be at least 7 if he follows the optimal path: RIGHT-> RIGHT -> DOWN -> DOWN.

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

1⃣Определение матрицы dp:
Создайте матрицу dp размером с подземелье, где элемент dp[row][col] указывает минимальное количество здоровья, необходимое рыцарю, чтобы начать путь из ячейки dungeon[row][col] и достигнуть цели (нижней правой ячейки).

2⃣Инициализация и заполнение dp:
Начните с правого нижнего угла подземелья и идите в обратном направлении — справа налево и снизу вверх. Для каждой ячейки вычислите соответствующее значение в dp:
Если возможно, шаг вправо из текущей ячейки подземелья требует right_health здоровья.
Если возможно, шаг вниз из текущей ячейки подземелья требует down_health здоровья.
Возьмите минимальное значение из right_health и down_health для dp[row][col].
Если ни один из вышеперечисленных вариантов не доступен (то есть вы находитесь в ячейке назначения), учитывайте два подслучая:
Если в ячейке магический шар, достаточно 1 единицы здоровья.
Если в ячейке демон, рыцарю необходимо иметь единицу здоровья плюс урон, который может нанести демон.

3⃣Результат вычислений:
Значение в dp[0][0] будет указывать на минимальное количество здоровья, необходимое рыцарю, чтобы начать свой путь из верхней левой ячейки подземелья и успешно спасти принцессу, учитывая все угрозы на его пути.

😎 Решение:

func calculateMinimumHP(dungeon: [[Int]]) -> Int {
    let rows = dungeon.count
    let cols = dungeon[0].count
    var dp = Array(repeating: Array(repeating: Int.max, count: cols), count: rows)

    func getMinHealth(currCell: Int, nextRow: Int, nextCol: Int) -> Int {
        guard nextRow < rows, nextCol < cols else { return Int.max }
        let nextCell = dp[nextRow][nextCol]
        return max(1, nextCell - currCell)
    }

    for row in stride(from: rows - 1, through: 0, by: -1) {
        for col in stride(from: cols - 1, through: 0, by: -1) {
            let currCell = dungeon[row][col]
            let rightHealth = getMinHealth(currCell: currCell, nextRow: row, nextCol: col + 1)
            let downHealth = getMinHealth(currCell: currCell, nextRow: row + 1, nextCol: col)
            let nextHealth = min(rightHealth, downHealth)
            let minHealth = nextHealth != Int.max ? nextHealth : (currCell >= 0 ? 1 : 1 - currCell)
            dp[row][col] = minHealth
        }
    }

    return dp[0][0]
}

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

Задача: 1002. Find Common Characters
Сложность: easy

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

Пример:

Input: words = ["bella","label","roller"]
Output: ["e","l","l"]

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

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

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

3⃣Формирование результата:
Создайте результирующий массив, добавляя каждый символ столько раз, сколько его минимальная частота.

😎 Решение:

class Solution {
    func commonChars(_ words: [String]) -> [String] {
        var min_freq = [Int](repeating: Int.max, count: 26)
        
        for word in words {
            var freq = [Int](repeating: 0, count: 26)
            for char in word {
                freq[Int(char.asciiValue! - Character("a").asciiValue!)] += 1
            }
            for i in 0..<26 {
                min_freq[i] = min(min_freq[i], freq[i])
            }
        }
        
        var result = [String]()
        for i in 0..<26 {
            for _ in 0..<min_freq[i] {
                result.append(String(UnicodeScalar(i + Int(Character("a").asciiValue!))!))
            }
        }
        return result
    }
}

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

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

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