Задача: 1013. Partition Array Into Three Parts With Equal Sum
Сложность: easy

Если задан массив целых чисел arr, верните true, если мы можем разбить массив на три непустые части с равными суммами. Формально, мы можем разбить массив, если можем найти индексы i + 1 < j с (arr[0] + arr[1] + ... + arr[i] == arr[i + 1] + arr[i + 2] + ... + arr[j - 1] == arr[j] + arr[j + 1] + ... + arr[arr.length - 1])

Пример:

Input: arr = [0,2,1,-6,6,-7,9,1,2,0,1]
Output: true

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

1⃣Вычисление общей суммы:
Вычислите общую сумму всех элементов массива. Если эта сумма не делится на 3 без остатка, вернуть false, так как невозможно разбить массив на три части с равной суммой.

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

3⃣Проверка третьей части:
Убедитесь, что оставшаяся часть массива также имеет ту же сумму, что и две найденные части. Если да, вернуть true, иначе false.

😎 Решение:

class Solution {
    func canThreePartsEqualSum(_ arr: [Int]) -> Bool {
        let totalSum = arr.reduce(0, +)
        if totalSum % 3 != 0 {
            return false
        }
        
        let target = totalSum / 3
        var partSum = 0
        var count = 0
        let n = arr.count
        
        for i in 0..<n {
            partSum += arr[i]
            if partSum == target {
                count += 1
                partSum = 0
                if count == 2 && i < n - 1 {
                    return true
                }
            }
        }
        
        return false
    }
}

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

Задача: 967. Numbers With Same Consecutive Differences
Сложность: medium

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

Учтите, что целые числа не должны начинаться с нулей. Целые числа, такие как 02 и 043, не допускаются.

Пример:

Input: n = 3, k = 7
Output: [181,292,707,818,929]
Explanation: Note that 070 is not a valid number, because it has leading zeroes.

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

1⃣Если n равно 1, верните массив от 0 до 9, так как все однозначные числа являются допустимыми.

2⃣Инициализируйте список очередей начальными цифрами от 1 до 9.

3⃣Для каждого уровня (от 1 до n-1) создайте новый список очередей, добавляя к каждому числу в текущей очереди допустимые цифры, которые удовлетворяют условию разницы k.

😎 Решение:

class Solution {
    func numsSameConsecDiff(_ N: Int, _ K: Int) -> [Int] {
        if N == 1 { return Array(0...9) }
        
        var queue = Array(1...9)
        for _ in 1..<N {
            var nextQueue = [Int]()
            for num in queue {
                let tailDigit = num % 10
                let nextDigits = [tailDigit + K, tailDigit - K]
                
                for nextDigit in nextDigits where 0 <= nextDigit && nextDigit < 10 {
                    nextQueue.append(num * 10 + nextDigit)
                }
            }
            queue = nextQueue
        }
        
        return queue
    }
}

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

Задача: 944. Delete Columns to Make Sorted
Сложность: easy

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

Пример:

Input: strs = ["cba","daf","ghi"]
Output: 1

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

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

2⃣Пройти по каждому столбцу от 0 до длины строки.
Для каждого столбца проверить, отсортированы ли символы лексикографически.
Если столбец не отсортирован, увеличить count.

3⃣Вернуть count.

😎 Решение:

class Solution {
    func minDeletionSize(_ strs: [String]) -> Int {
        var count = 0
        let strs = strs.map { Array($0) }
        for col in 0..<strs[0].count {
            for row in 1..<strs.count {
                if strs[row][col] < strs[row - 1][col] {
                    count += 1
                    break
                }
            }
        }
        return count
    }
}

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

Задача: №44. Wildcard Matching
Сложность: hard

Учитывая входную строку s и шаблон p, реализуйте сопоставление с поддержкой ? и *, где:
- ? соответствует любому отдельному символу.
- * соответствует любой последовательности символов (включая пустую).
Соответствие должно охватывать всю строку s (не частичное).

Пример:

Input: s = "aa", p = "a*"  
Output: true  

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

1⃣Использовать два указателя sdx и pdx для строки s и шаблона p.

2⃣Если символы совпадают или ?, двигаем оба указателя.

3⃣Если встречаем *, запоминаем позиции в s и p, продолжаем проверку.

😎 Решение:

class Solution {
    typealias C = Character
    
    func isMatch(_ s: String, _ p: String) -> Bool {
        var sArray = Array(s)
        var pArray = Array(p)
        
        var sdx = 0, pdx = 0
        var starPDx = -1, starSDx = -1
        
        while sdx < sArray.count {
            if pdx < pArray.count && (sArray[sdx] == pArray[pdx] || pArray[pdx] == C("?")) {
                sdx += 1
                pdx += 1
            } else if pdx < pArray.count && pArray[pdx] == C("*") {
                starPDx = pdx
                starSDx = sdx
                pdx += 1
            } else if starPDx == -1 {
                return false
            } else {
                sdx = starSDx + 1
                pdx = starPDx + 1
                starSDx = sdx
            }
        }
        
        return pdx < pArray.count ? !pArray[pdx...].contains(where: { $0 != C("*") }) : true
    }
}

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

Задача: 952. Largest Component Size by Common Factor
Сложность: hard

Для бинарного дерева T мы можем определить операцию переворота следующим образом: выбираем любой узел и меняем местами левое и правое дочерние поддеревья. Бинарное дерево X эквивалентно бинарному дереву Y тогда и только тогда, когда мы можем сделать X равным Y после некоторого количества операций переворота. Учитывая корни двух бинарных деревьев root1 и root2, верните true, если эти два дерева эквивалентны перевороту, или false в противном случае.

Пример:

Input: nums = [4,6,15,35]
Output: 4

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

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

2⃣Использовать алгоритм Union-Find для объединения узлов в связные компоненты.
Для каждого числа в массиве nums найти его простые делители и использовать их для объединения узлов.

3⃣Найти размер наибольшей связной компоненты.

😎 Решение:

class Solution {
    func largestComponentSize(_ nums: [Int]) -> Int {
        var parent = [Int: Int]()
        var rank = [Int: Int]()
        
        for num in nums {
            parent[num] = num
            rank[num] = 0
        }
        
        func find(_ x: Int) -> Int {
            if parent[x] != x {
                parent[x] = find(parent[x]!)
            }
            return parent[x]!
        }
        
        func union(_ x: Int, _ y: Int) {
            let rootX = find(x)
            let rootY = find(y)
            if rootX != rootY {
                if rank[rootX]! > rank[rootY]! {
                    parent[rootY] = rootX
                } else if rank[rootX]! < rank[rootY]! {
                    parent[rootX] = rootY
                } else {
                    parent[rootY] = rootX
                    rank[rootX]! += 1
                }
            }
        }
        
        func primeFactors(_ n: Int) -> Set<Int> {
            var factors = Set<Int>()
            var d = 2
            var n = n
            while d * d <= n {
                while n % d == 0 {
                    factors.insert(d)
                    n /= d
                }
                d += 1
            }
            if n > 1 {
                factors.insert(n)
            }
            return factors
        }
        
        var primeToIndex = [Int: [Int]]()
        for num in nums {
            let primes = primeFactors(num)
            for prime in primes {
                primeToIndex[prime, default: []].append(num)
            }
        }
        
        for primes in primeToIndex.values {
            for i in 1..<primes.count {
                union(primes[0], primes[i])
            }
        }
        
        var size = [Int: Int]()
        for num in nums {
            let root = find(num)
            size[root, default: 0] += 1
        }
        
        return size.values.max()!
    }
}

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

Задача: 906. Super Palindromes
Сложность: hard

Если задан целочисленный массив nums, переместите все четные числа в начало массива, а затем все нечетные. Верните любой массив, удовлетворяющий этому условию.

Пример:

Input: left = "4", right = "1000"
Output: 4

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

1⃣Найти все палиндромы до корня из right.

2⃣Проверить, являются ли квадраты этих палиндромов палиндромами и лежат ли в диапазоне [left, right].

3⃣Подсчитать количество таких суперпалиндромов.

😎 Решение:

class Solution {
    func isPalindrome(_ x: Int) -> Bool {
        let s = String(x)
        return s == String(s.reversed())
    }
    
    func superpalindromesInRange(_ left: String, _ right: String) -> Int {
        let left = Int(left)!
        let right = Int(right)!
        var count = 0

        for i in 1...100000 {
            let s = String(i)
            let palin1 = Int(s + String(s.reversed()))!
            let palin2 = Int(s + String(s.dropLast().reversed()))!

            if palin1 * palin1 > right {
                break
            }
            if palin1 * palin1 >= left && isPalindrome(palin1 * palin1) {
                count += 1
            }
            if palin2 * palin2 >= left && palin2 * palin2 <= right && isPalindrome(palin2 * palin2) {
                count += 1
            }
        }

        return count
    }
}

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

Задача: 206. Reverse Linked List
Сложность: easy

Дан односвязный список, разверните этот список и верните развернутый список.

Пример:

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

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

1⃣Инициализируйте две переменные: prev как nullptr и curr как head списка. Эти переменные будут использоваться для отслеживания предыдущего и текущего узлов в процессе разворота списка.

2⃣Пройдитесь по списку с помощью цикла:
Сохраните ссылку на следующий узел curr в переменную nextTemp.
Измените ссылку next текущего узла curr на prev, чтобы развернуть направление ссылки.
Переместите prev на текущий узел curr и переместите curr на следующий узел nextTemp.

3⃣После завершения цикла верните prev как новую голову развернутого списка.

😎 Решение:

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

class Solution {
    func reverseList(_ head: ListNode?) -> ListNode? {
        var prev: ListNode? = nil
        var curr = head
        while curr != nil {
            let nextTemp = curr?.next
            curr?.next = prev
            prev = curr
            curr = nextTemp
        }
        return prev
    }
}

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

Задача: 304. Range Sum Query 2D - Immutable
Сложность: medium

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

Задача: 869. Reordered Power of 2
Сложность: medium

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

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

Пример:

Input: n = 1
Output: true

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

1⃣Сгенерируйте все перестановки цифр числа, размещая любую цифру на первой позиции (start = 0), затем любую из оставшихся цифр на второй позиции (start = 1) и так далее. В Python можно использовать встроенную функцию itertools.permutations.

2⃣Проверьте, что перестановка представляет собой степень двойки, убедившись, что в перестановке нет ведущего нуля, и удаляя все множители 2. Если результат равен 1 (то есть, он не содержал других множителей, кроме 2), то это была степень двойки. В Python можно использовать проверку bin(N).count('1') == 1.

3⃣Верните true, если хотя бы одна перестановка является степенью двойки, иначе верните false.

😎 Решение:

class Solution {
    func reorderedPowerOf2(_ N: Int) -> Bool {
        let A = Array(String(N)).map { Int(String($0))! }
        return permutations(A, 0)
    }

    private func isPowerOfTwo(_ A: [Int]) -> Bool {
        if A[0] == 0 { return false }
        var N = A.reduce(0) { $0 * 10 + $1 }
        while N > 0 && (N & 1) == 0 { N >>= 1 }
        return N == 1
    }

    private func permutations(_ A: [Int], _ start: Int) -> Bool {
        var A = A
        if start == A.count { return isPowerOfTwo(A) }
        for i in start..<A.count {
            A.swapAt(start, i)
            if permutations(A, start + 1) { return true }
            A.swapAt(start, i)
        }
        return false
    }
}

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

Ура, друзья! Изиоффер переходит в публичное бета-тестирование!

🎉 Что нового:
🟢Анализ IT собеседований на основе 4500+ реальных интервью
🟢Вопросы из собеседований с вероятностью встречи
🟢Видео-примеры ответов на вопросы от Senior, Middle, Junior грейдов
🟢Пример лучшего ответа
🟢Задачи из собеседований
🟢Тестовые задания
🟢Примеры собеседований
🟢Фильтрация всего контента по грейдам, компаниям
🟢Тренажер подготовки к собеседованию на основе интервальных повторений и флеш карточек
🟡Тренажер "Реальное собеседование" с сценарием вопросов из реальных собеседований (скоро)
🟢Автоотклики на HeadHunter
🟢Закрытое сообщество easyoffer


💎 Акция в честь открытия для первых 500 покупателей:
🚀 Скидка 50% на PRO тариф на 1 год (15000₽ → 7500₽)

🔥 Акция уже стартовала! 👉 https://easyoffer.ru/pro

Задача: 524. Longest Word in Dictionary through Deleting
Сложность: medium

Даны строка s и массив строк dictionary. Верните самую длинную строку из dictionary, которую можно сформировать, удаляя некоторые символы из данной строки s. Если возможных результатов несколько, верните самое длинное слово с наименьшим лексикографическим порядком. Если возможного результата нет, верните пустую строку.

Пример:

Input: s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
Output: "apple"

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

1⃣Инициализируйте переменную для хранения самой длинной строки, соответствующей критериям. Пройдите по каждой строке x в неотсортированном массиве dictionary и проверьте, является ли x подпоследовательностью строки s.

2⃣Если строка x является подпоследовательностью, сравните её с текущей самой длинной строкой по длине. Если длина x больше или равна длине текущей самой длинной строки и она меньше текущей строки в лексикографическом порядке (если равны по длине), обновите текущую самую длинную строку.

3⃣После рассмотрения всех строк в dictionary, верните найденную строку. Если ни одна строка не подошла, верните пустую строку.

😎 Решение:

class Solution {
    func isSubsequence(_ x: String, _ y: String) -> Bool {
        var j = x.startIndex
        for i in y.indices where j < x.endIndex {
            if x[j] == y[i] {
                j = x.index(after: j)
            }
        }
        return j == x.endIndex
    }

    func findLongestWord(_ s: String, _ d: [String]) -> String {
        var maxStr = ""
        for str in d {
            if isSubsequence(str, s) {
                if str.count > maxStr.count || (str.count == maxStr.count && str < maxStr) {
                    maxStr = str
                }
            }
        }
        return maxStr
    }
}

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

Задача: №21. Merge Two Sorted Lists
Сложность: easy

Вам даны заголовки двух отсортированных связанных списков list1 и list2. Объедините два списка в один отсортированный список. Список должен быть составлен путем сращивания узлов первых двух списков. Возвращает заголовок объединенного связанного списка.

Пример:

Input: list1 = [1,2,4], list2 = [1,3,4]  
Output: [1,1,2,3,4,4]  

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

1⃣Если один из списков пуст, вернуть другой список.

2⃣Сравнивать значения узлов list1 и list2, выбирая меньший узел для объединенного списка.

3⃣Рекурсивно продолжать объединение, связывая меньший узел с результатом mergeTwoLists от оставшихся узлов.

😎 Решение:

class Solution {
    func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
        guard let list1 = list1 else { return list2 }
        guard let list2 = list2 else { return list1 }
        
        if list1.val < list2.val {
            list1.next = mergeTwoLists(list1.next, list2)
            return list1
        } else {
            list2.next = mergeTwoLists(list1, list2.next)
            return list2
        }
    }
}

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

Задача: 950. Reveal Cards In Increasing Order
Сложность: medium

Вам дана колода целочисленных массивов. Имеется колода карт, в которой каждая карта имеет уникальное целое число. Целое число на i-й карте - deck[i]. Вы можете упорядочить колоду в любом порядке. Изначально все карты в одной колоде лежат лицевой стороной вниз (нераскрытыми). Вы будете выполнять следующие действия несколько раз, пока все карты не будут раскрыты: возьмите верхнюю карту колоды, раскройте ее и выньте из колоды. Если в колоде еще есть карты, положите следующую верхнюю карту колоды на дно колоды. Если еще есть нераскрытые карты, вернитесь к шагу 1. В противном случае остановитесь. Верните порядок колоды, при котором карты раскрываются в порядке возрастания. Обратите внимание, что первая запись в ответе считается верхом колоды.

Пример:

Input: deck = [17,13,11,2,3,5,7]
Output: [2,13,3,11,5,17,7]

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

1⃣Создать индексы карт в порядке, в котором они будут раскрываться.

2⃣Отсортировать колоду карт по возрастанию.

3⃣Отсортировать колоду карт по возрастанию.

😎 Решение:

class Solution {
    func deckRevealedIncreasing(_ deck: [Int]) -> [Int] {
        var index = Array(deck.indices)
        var result = [Int](repeating: 0, count: deck.count)
        let sortedDeck = deck.sorted()
        
        for card in sortedDeck {
            result[index.removeFirst()] = card
            if !index.isEmpty {
                index.append(index.removeFirst())
            }
        }
        
        return result
    }
}

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

Задача: 681. Next Closest Time
Сложность: medium

Дано время, представленное в формате "ЧЧ:ММ". Сформируйте ближайшее следующее время, используя текущие цифры. Количество раз, которое можно использовать цифру, не ограничено.

Можно предположить, что заданная строка всегда корректна. Например, "01:34", "12:09" являются корректными. "1:34", "12:9" являются некорректными.

Пример:

Input: time = "19:34"
Output: "19:39"
Explanation: The next closest time choosing from digits 1, 9, 3, 4, is 19:39, which occurs 5 minutes later.
It is not 19:33, because this occurs 23 hours and 59 minutes later.

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

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

2⃣Представьте время как целое число t в диапазоне 0 <= t < 24 * 60. Тогда часы равны t / 60, минуты равны t % 60.

3⃣Найдите каждую цифру часов и минут: часы / 10, часы % 10 и т.д.

😎 Посмотреть решение

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

Задача: 789. Escape The Ghosts
Сложность: medium

Вы играете в упрощенную игру PAC-MAN на бесконечной 2D-сетке. Вы начинаете в точке [0, 0], и у вас есть конечная точка target = [xtarget, ytarget], к которой вы пытаетесь добраться. На карте находятся несколько привидений, их начальные позиции заданы в виде двумерного массива ghosts, где ghosts[i] = [xi, yi] представляет начальную позицию i-го привидения. Все входные данные являются целочисленными координатами.

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

Вы сможете сбежать, если и только если сможете достичь цели раньше, чем любое привидение достигнет вас. Если вы достигнете любой клетки (включая конечную точку) одновременно с привидением, это не считается побегом.

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

Пример:

Input: ghosts = [[1,0],[0,3]], target = [0,1]
Output: true
Explanation: You can reach the destination (0, 1) after 1 turn, while the ghosts located at (1, 0) and (0, 3) cannot catch up with you.

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

1⃣Проверьте, что наше таксическое расстояние до цели меньше, чем расстояние от любого привидения до цели.

2⃣Если это так, мы можем гарантированно добраться до цели раньше любого привидения.

3⃣Если привидение может добраться до цели раньше нас или одновременно с нами, побег невозможен.

😎 Решение:

class Solution {
    func escapeGhosts(_ ghosts: [[Int]], _ target: [Int]) -> Bool {
        func taxi(_ P: [Int], _ Q: [Int]) -> Int {
            return abs(P[0] - Q[0]) + abs(P[1] - Q[1])
        }

        let playerDistance = taxi([0, 0], target)
        return ghosts.allSatisfy { taxi($0, target) > playerDistance }
    }
}

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

Задача: 923. 3Sum With Multiplicity
Сложность: medium

Если задан целочисленный массив arr и целое число target, верните количество кортежей i, j, k, таких, что i < j < k и arr[i] + arr[j] + arr[k] == target. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7.

Пример:

Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20

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

1⃣Отсортировать массив arr.

2⃣Инициализировать счетчик для количества кортежей.
Пройти по массиву тремя указателями i, j, и k:
Для каждого i, установить j на i + 1, и k на конец массива.
Использовать двухуказательный метод для нахождения пар (j, k), таких что arr[i] + arr[j] + arr[k] == target.

3⃣Вернуть результат по модулю 10^9 + 7.

😎 Решение:

class Solution {
    func threeSumMulti(_ arr: [Int], _ target: Int) -> Int {
        let MOD = 1_000_000_007
        var count = 0
        let arr = arr.sorted()
        
        for i in 0..<arr.count {
            var j = i + 1
            var k = arr.count - 1
            
            while j < k {
                let sum = arr[i] + arr[j] + arr[k]
                if sum == target {
                    if arr[j] == arr[k] {
                        count += (k - j + 1) * (k - j) / 2
                        break
                    } else {
                        var left = 1
                        var right = 1
                        while j + 1 < k && arr[j] == arr[j + 1] {
                            left += 1
                            j += 1
                        }
                        while k - 1 > j && arr[k] == arr[k - 1] {
                            right += 1
                            k -= 1
                        }
                        count += left * right
                        j += 1
                        k -= 1
                    }
                } else if sum < target {
                    j += 1
                } else {
                    k -= 1
                }
            }
        }
        
        return count % MOD
    }
}

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

Задача: 1165. Single-Row Keyboard
Сложность: easy

Есть специальная клавиатура, на которой все клавиши расположены в один ряд.

Дана строка keyboard длиной 26, указывающая на раскладку клавиатуры (индексирована от 0 до 25). Изначально ваш палец находится на индексе 0. Чтобы напечатать символ, нужно переместить палец на индекс нужного символа. Время, затраченное на перемещение пальца с индекса i на индекс j, равно |i - j|.

Вам нужно напечатать строку word. Напишите функцию для расчета времени, необходимого для её набора одним пальцем.

Пример:

Input: keyboard = "abcdefghijklmnopqrstuvwxyz", word = "cba"
Output: 4
Explanation: The index moves from 0 to 2 to write 'c' then to 1 to write 'b' then to 0 again to write 'a'.
Total time = 2 + 1 + 1 = 4.

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

1⃣Клавиатура содержит уникальные строчные английские буквы, поэтому мы можем сопоставить её с массивом размера 26. Создадим массив размера 26, назовём его keyIndices. Сохраните индекс каждой буквы в этом массиве, проходя по строке keyboard. Инициализируйте переменную result значением 0, которая будет хранить сумму всех расстояний. Объявите переменную prev, которая будет хранить индекс предыдущей клавиши. Поскольку начальная позиция равна 0, инициализируйте её значением 0.

2⃣Проходите по строке word буква за буквой. Для каждой буквы c добавьте ∣prev−indexOf(c)∣ к result. Обновите prev до индекса c.

3⃣Повторите шаги 6 и 7 для всех букв. В конце прохода result будет содержать итоговое время, необходимое для набора слова.

😎 Решение

class Solution {
    func calculateTime(_ keyboard: String, _ word: String) -> Int {
        var keyIndices = Array(repeating: -1, count: 26)
        for (i, c) in keyboard.enumerated() {
            keyIndices[Int(c.asciiValue! - Character("a").asciiValue!)] = i
        }
        
        var prev = 0
        var result = 0
        
        for c in word {
            let index = keyIndices[Int(c.asciiValue! - Character("a").asciiValue!)]
            result += abs(prev - index)
            prev = index
        }
        return result
    }
}

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

Задача: 276. Paint Fence
Сложность: medium

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

Пример:

Input: n = 3, k = 2
Output: 6
Explanation: All the possibilities are shown.
Note that painting all the posts red or all the posts green is invalid because there cannot be three posts in a row with the same color.

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

1⃣Инициализация и определение вспомогательной функции:
Определить хеш-таблицу memo, где memo[i] представляет количество способов покрасить i столбцов.
Определить функцию totalWays, которая будет определять количество способов покрасить i столбцов.

2⃣Реализация базы и проверка кэша:
В функции totalWays проверить базовые случаи: вернуть k, если i == 1, и вернуть k * k, если i == 2.
Проверить, рассчитан ли аргумент i и сохранен ли в memo. Если да, вернуть memo[i].

3⃣Расчет с использованием рекуррентного соотношения:
В противном случае использовать рекуррентное соотношение для вычисления memo[i], сохранить результат в memo[i] и вернуть его.
Вызвать и вернуть totalWays(n).

😎 Решение:

class Solution {
    func numWays(_ n: Int, _ k: Int) -> Int {
        if n == 1 {
            return k
        }
        
        var twoPostsBack = k
        var onePostBack = k * k
        
        for _ in 3...n {
            let curr = (k - 1) * (onePostBack + twoPostsBack)
            twoPostsBack = onePostBack
            onePostBack = curr
        }
        
        return onePostBack
    }
}

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

Задача: 349. Intersection of Two Arrays
Сложность: easy

Даны два целочисленных массива nums1 и nums2. Верните массив их пересечения. Каждый элемент в результате должен быть уникальным, и вы можете вернуть результат в любом порядке.

Пример:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

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

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

2⃣Нахождение пересечения:
Найдите пересечение двух множеств.

3⃣Возврат результата:
Преобразуйте пересечение обратно в массив и верните его.

😎 Решение:

class Solution {
    func intersection(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
        let set1 = Set(nums1)
        let set2 = Set(nums2)
        return Array(set1.intersection(set2))
    }
}

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

Задача: 971. Flip Binary Tree To Match Preorder Traversal
Сложность: medium

Дано корневое дерево с n узлами, где каждому узлу уникально присвоено значение от 1 до n. Также дана последовательность из n значений voyage, которая является желаемым обходом дерева в порядке pre-order.

Любой узел в бинарном дереве можно перевернуть, поменяв местами его левое и правое поддеревья. Например, переворот узла 1 будет иметь следующий эффект:

Переверните минимальное количество узлов, чтобы обход дерева в порядке pre-order соответствовал voyage.

Верните список значений всех перевернутых узлов. Вы можете вернуть ответ в любом порядке. Если невозможно перевернуть узлы в дереве, чтобы сделать обход в порядке pre-order соответствующим voyage, верните список [-1].

Пример:

Input: root = [1,2], voyage = [2,1]
Output: [-1]
Explanation: It is impossible to flip the nodes such that the pre-order traversal matches voyage.

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

1⃣Выполните поиск в глубину. Если в каком-либо узле значение узла не соответствует значению в voyage, верните [-1].

2⃣Иначе определите, когда нужно перевернуть: если следующее ожидаемое число в voyage (voyage[i]) отличается от следующего потомка.

3⃣Переверните узел, добавьте его значение в список перевернутых узлов и продолжите обход дерева, пока весь порядок обхода pre-order не будет соответствовать voyage.

😎 Решение:

class Solution {
    var flipped = [Int]()
    var index = 0
    var voyage: [Int] = []

    func flipMatchVoyage(_ root: TreeNode?, _ voyage: [Int]) -> [Int] {
        flipped = []
        index = 0
        self.voyage = voyage

        dfs(root)
        if !flipped.isEmpty && flipped[0] == -1 {
            flipped = [-1]
        }

        return flipped
    }

    func dfs(_ node: TreeNode?) {
        if let node = node {
            if node.val != voyage[index] {
                flipped = [-1]
                return
            }
            index += 1

            if index < voyage.count && node.left != nil && node.left!.val != voyage[index] {
                flipped.append(node.val)
                dfs(node.right)
                dfs(node.left)
            } else {
                dfs(node.left)
                dfs(node.right)
            }
        }
    }
}

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