Задача: №16. 3Sum Closest #medium

Условие:

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

Решение:

class Solution {
    func threeSumClosest(_ nums: [Int], _ target: Int) -> Int {
        
        let sorted = nums.sorted()
        let length = sorted.count
        
        var diff: Int = .max
        var result = 0
        
        for i in 0..<length - 2 {
            var n = i + 1, q = length - 1
            while n < q {
                let sum = sorted[i] + sorted[n] + sorted[q]
                
                sum > target ? (q -= 1) : (n += 1)
                
                let value =  abs(sum - target)
                
                if value < diff {
                    diff = value
                    result = sum
                }
            }
        }
        return result
    }
}

Пояснение:
Сортировка массива: Массив nums сначала сортируется. Это упрощает процесс поиска, так как позволяет легко управлять индексами и использовать двоичный поиск.

Инициализация переменных: diff инициализируется как максимальное значение типа Int, что позволит найти минимальное различие между суммой трёх чисел и целевым значением. result инициализируется нулем и будет хранить результат – сумму, наиболее близкую к целевому значению.

Основной цикл: Внешний цикл проходит по элементам массива до предпоследнего (так как нам нужно как минимум три элемента для вычисления суммы).

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

Внутри цикла while происходит вычисление суммы элементов sorted[i], sorted[n], и sorted[q].
Если сумма больше целевого значения, q уменьшается, чтобы уменьшить сумму. Если сумма меньше, n увеличивается, чтобы увеличить сумму.
Рассчитывается абсолютное значение разницы между суммой и целевым значением. Если это значение меньше текущего diff, обновляются переменные diff и result.
Возвращение результата: Как только все комбинации трёх элементов проверены, возвращается сумма, наиболее близкая к целевому значению.

Задача: №17. Letter Combinations of a Phone Number #medium

Условие:

Учитывая строку, содержащую цифры от 2 до 9 включительно, верните все возможные комбинации букв, которые может представлять число. Верните ответ в любом порядке. Соответствие цифр буквам (как на кнопках телефона) приведено ниже. Обратите внимание, что 1 не соответствует никаким буквам.

Решение:

class Solution {
    private let mat = ["2":["a","b","c"],
                       "3":["d","e","f"],
                       "4":["g","h","i"],
                       "5":["j","k","l"],
                       "6":["m","n","o"],
                       "7":["p","q","r","s"],
                       "8":["t","u","v"],
                       "9":["w","x","y","z"]]
    func letterCombinations(_ digits: String) -> [String] {
        var res = [String]()
        for d in digits.map({ $0.lowercased() }) {
            guard let keys = mat[d] else { break }
            if res.isEmpty {
                keys.forEach { res.append($0) }
                continue
            }
            let arr = res.map { _ in res.removeFirst() }
            for ch in keys { res += arr.map({$0 + ch}) }
        }
        return res
    }
}

Пояснение:
Определение карты символов: mat представляет собой словарь, где ключами являются цифры от "2" до "9", а значениями являются массивы символов, соответствующих каждой цифре на стандартной телефонной клавиатуре. Например, для "2" соответствуют символы "a", "b", "c".

Метод letterCombinations: Этот метод принимает строку digits как вход, представляющую последовательность цифр.

Инициализация списка результатов: res используется для хранения всех возможных комбинаций строк, которые будут сформированы на основе входных цифр.

Проверка каждой цифры: Для каждой цифры в строке digits осуществляется нижний регистр (используется для стандартизации ввода, например, "1" и "I" должны обрабатываться одинаково).

Проверка наличия соответствующих символов: Для каждой цифры проверяется, существуют ли символы, соответствующие этой цифре, в словаре mat. Если для цифры нет соответствующих символов, функция прекращает выполнение (break).

Обработка начального состояния: Если результат ещё не содержит комбинаций (res.isEmpty), инициализируется массивом всех символов, соответствующих текущей цифре.

Формирование новых комбинаций: Для каждой последующей цифры, если результат не пуст, создаются новые строки. Для этого текущие символы, находящиеся в res, объединяются с каждым символом, соответствующим текущей цифре. Для каждой комбинации символов в предыдущем результате создаётся новая строка, добавляющая текущий символ.

Возврат результата: После обработки всех цифр возвращается список всех возможных комбинаций строк.

Задача: №18. 4Sum #medium

Условие:

Учитывая массив nums из n целых чисел, верните массив всех уникальных четверок [nums[a], nums[b], nums[c], nums[d]] таких, что:
0 <= a, b, c, d < n
a, b, c и d различны.
nums[a] + nums[b] + nums[c] + nums[d] == цель
Вы можете вернуть ответ в любом порядке.

Решение:

class Solution {
    func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {
        let len = nums.count
        guard len >= 4 else { return [] }
        
        var result = [[Int]]()
        let sort = nums.sorted()
        
        for a in 0..<(len - 1) where a == 0 || sort[a] != sort[a-1] {
            for b in (a + 1)..<len where b == a + 1 || sort[b] != sort[b-1] {
                var c = b + 1, d = len - 1
                while c < d {
                    let val = (a: sort[a], b: sort[b], c: sort[c], d: sort[d])
                    let sum = (val.a + val.b + val.c + val.d)
                    if sum == target { result.append([val.a,val.b,val.c,val.d]) }
                    if sum < target {
                        while sort[c] == val.c, c < d { c += 1 }
                    } else {
                        while sort[d] == val.d, d > b { d -= 1 }
                    }
                }
            }
        }
        return result
    }
}

Пояснение:
Проверка длины массива: Сначала проверяется длина массива nums. Если в массиве меньше четырех элементов, функция сразу возвращает пустой массив, так как невозможно выбрать четыре числа.

Сортировка массива: Массив nums сортируется. Это позволяет использовать два указателя для упрощения поиска нужных комбинаций и избегать повторений при прохождении по элементам массива.

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

a == 0 || sort[a] != sort[a-1] используется для пропуска повторяющихся значений первого элемента комбинации, чтобы избежать дублирования в результатах.
Второй цикл для второй переменной: Внутренний цикл (b) начинает с элемента после текущего элемента a и также идет до предпоследнего элемента, обеспечивая выбор второго элемента комбинации.

b == a + 1 || sort[b] != sort[b-1] пропускает повторяющиеся значения второго элемента комбинации.
Два указателя для третьего и четвертого элементов: Инициализируются два указателя, c и d. c начинается сразу после b, а d — с конца массива. Эти указатели используются для нахождения пары, которая вместе с элементами a и b составит сумму, равную target.

Поиск подходящих пар с помощью двух указателей: Внутренний цикл выполняется, пока c не встретится с d. На каждой итерации:

Вычисляется сумма четырех чисел, sum = sort[a] + sort[b] + sort[c] + sort[d].
Если сумма равна target, текущая комбинация добавляется в результат.
Если сумма меньше target, увеличивается указатель c, чтобы увеличить сумму.
Если сумма больше target, уменьшается указатель d, чтобы уменьшить сумму.
Внутренние циклы while используются для пропуска одинаковых значений на указателях c и d, чтобы избежать повторяющихся комбинаций в результатах.
Возврат результата: После завершения всех итераций возвращается список всех уникальных комбинаций, сумма которых равна target.

Задача: №19. Remove Nth Node From End of List #medium

Условие:

Учитывая заголовок связанного списка, удалите n-й узел из конца списка и верните его заголовок.

Решение:

class Solution {
    func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        let dummy = ListNode(0)
        dummy.next = head
        
        var prev: ListNode? = dummy
        var post: ListNode? = dummy
        
        for _ in 0..<n {
            post = post?.next
        }
        
        while post?.next != nil {
            prev = prev?.next
            post = post?.next
        }
        
        prev!.next = prev!.next!.next
        
        return dummy.next
    }
}

Пояснение:
Создание поддельного узла: Функция начинает с создания поддельного узла (dummy), который указывает на начало списка. Это упрощает обработку случаев, когда удаляемый узел находится на начале списка (например, когда нужно удалить первый узел).

Инициализация двух указателей: Два указателя, prev и post, инициализируются как указатели на поддельный узел. Эти два указателя будут использоваться для выполнения задачи.

Двигаем post вперед: Цикл for используется для перемещения указателя post на n шагов вперед. Это означает, что к моменту завершения цикла post будет указывать на n-й узел от начала списка.

Двигаем оба указателя одновременно: Затем используется цикл, чтобы одновременно перемещать оба указателя (prev и post) до тех пор, пока post не достигнет конца списка. На этом этапе prev будет указывать на узел, который находится перед удаляемым узлом.

Удаление узла: После завершения предыдущего цикла, указатель prev указывает на узел, перед которым находится удаляемый узел. Указатель prev.next обновляется, чтобы пропустить удаляемый узел, и теперь указывает на узел, следующий за удаляемым.

Возврат измененного списка: Наконец, функция возвращает dummy.next, что является новым началом списка, исключая поддельный узел.

Задача: №20. Valid Parentheses #easy

Условие:

Учитывая строку s, содержащую только символы '(', ')', '{', '}', '[' и ']', определите, является ли входная строка допустимой. Входная строка действительна, если: Открытые скобки должны закрываться скобками того же типа.
Открытые скобки должны закрываться в правильном порядке.
Каждой закрывающей скобке соответствует открытая скобка того же типа.

Решение:

class Solution {
    func isValid(_ s: String) -> Bool {
        
        guard s.count % 2 == 0 else { return false }
        
        var stack: [Character] = []
        
        for ch in s {
            switch ch {
            case "(": stack.append(")")
            case "[": stack.append("]")
            case "{": stack.append("}")
            default:
                if stack.isEmpty || stack.removeLast() != ch {
                    return false
                }
            }
        }
        
        return stack.isEmpty
    }
}

Пояснение:
Проверка четности количества скобок:

Первоначально код проверяет, является ли количество символов в строке четным. Если нет, функция немедленно возвращает false, так как для каждой открывающей скобки должна быть соответствующая закрывающая скобка.
Использование стека для проверки правильности скобок:

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

Цикл for перебирает каждый символ строки.
В зависимости от типа символа:
Если это открывающая скобка ((, [, {), добавляется соответствующая закрывающая скобка в стек.
Если это закрывающая скобка, происходит проверка:
Если стек пуст, это означает, что закрывающая скобка не имеет соответствующей открывающей скобки, и функция возвращает false.
Если верхний элемент стека не совпадает с текущей закрывающей скобкой, также возвращается false. Это означает, что текущая пара скобок не соответствует.
В противном случае, верхний элемент стека удаляется, подтверждая правильное закрытие соответствующей открывающей скобки.
Проверка пустоты стека после завершения цикла:

В конце, если стек пуст, это означает, что все открывающие скобки имели соответствующие закрывающие скобки, и функция возвращает true. Если стек не пуст, это означает, что не все открывающие скобки были закрыты, и функция возвращает false.

Задача: 45. Jump Game ll #medium
Условие:

Вам предоставляется массив целых чисел nums с индексом 0 и длиной n. Изначально вы располагаетесь в nums [0].
Каждый элемент nums [i] представляет максимальную длину прямого перехода от индекса i. Другими словами, если вы находитесь в nums [1], вы можете перейти к любому nums [i + j], где:
• <=j<= nums[i] и
• i+j <n
Возвращает минимальное количество переходов для достижения nums [n -
11. Тестовые примеры генерируются таким образом, чтобы вы могли достичь значений [n - 1].

Решение:

class Solution {
    func jump(_ nums: [Int]) -> Int {
        
        guard nums.count > 2 else { return nums.count - 1 }

        var dp = Array(repeating: Int.max, count: nums.count)
        dp[0] = 0

        for i in 0..<nums.count - 1
            where nums[i] > 0 {
                for j in 1 + i...min(nums.count - 1, i + nums[i]) {
                    dp[j] = min(dp[j], dp[i] + 1)
                    guard j < nums.count - 1 else { return dp[j] }
                }
            }

        return dp.last!
    }
}

Пояснение:
Этот код представляет функцию `jump`, которая находит минимальное количество прыжков, необходимых для достижения последнего индекса в массиве `nums`. Давайте разберем этот код:

1. В начале функции `guard` проверяет, что длина массива `nums` больше 2. Если это не так, то минимальное количество прыжков равно `nums.count - 1`, так как массив состоит из 2 элементов.

2. Создается массив `dp`, в котором каждый элемент инициализируется значением `Int.max`, кроме нулевого элемента, который устанавливается как 0, так как минимальное количество прыжков до самого себя равно 0.

3. Происходит итерация по массиву `nums`. Для каждого элемента `nums[i]`, если он больше 0, итерация выполняется по диапазону от `1 + i` до минимума между `nums.count - 1` и `i + nums[i]`. В этом цикле вычисляется минимальное количество прыжков до каждой позиции `j`, используя значение `dp[i] + 1`. Затем значение `dp[j]` обновляется до минимального из текущего значения и `dp[i] + 1`.

4. Если индекс `j` достигает `nums.count - 1`, то возвращается значение `dp[j]`, так как это последний индекс, который нужно достичь.

5. В конце функция возвращает последний элемент массива `dp`, содержащий минимальное количество прыжков до последнего индекса в массиве `nums`.

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

Задача: 44. Wildcard Matching #hard
Условие:

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

Решение:

class Solution {
    typealias C = Character
    
    func isMatch(_ s: String, _ p: String) -> Bool {
        var sArray = Array(s)
        var pArray = Array(p)
        
        var sdx = 0
        var pdx = 0
        
        var starPDx = -1
        var 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 ..< pArray.count].contains(where: { $0 != C("*") }) : true
    }
}

Пояснение:
Этот код представляет функцию `isMatch`, которая проверяет, соответствует ли строка `s` шаблону `p`. В данном случае, `p` может содержать символы `'?'` (соответствует одному символу) и `'*'` (соответствует нулю или более символам). Давайте разберем код:

1. В начале функции определены типы данных: `C` для символа исходной строки.

2. Входные строки `s` и `p` преобразуются в массивы символов `sArray` и `pArray` соответственно.

3. Инициализируются переменные `sdx` и `pdx` для обозначения текущих индексов в массивах `sArray` и `pArray`, а также переменные `starPDx` и `starSDx` для хранения индексов, связанных с символом `'*'`.

4. В цикле `while` происходит пошаговая проверка соответствия символов строки `s` шаблону `p`. Если символы совпадают или в шаблоне встречается символ `'?'`, индексы увеличиваются. Если встречается символ `'*'`, сохраняются индексы перед символом `'*'` для возможного возврата.

5. Если не удается сопоставить символы и индекс до символа `'*'` не определен, возвращается `false`.

6. Когда заканчивается цикл и все символы в строке `s` проверены, проверяется, остались ли еще символы в шаблоне `p`. Если остались, проверяется, что они все равны символу `'*'`. В противном случае, возвращается `true`, т.к. строка `s` была успешно сопоставлена шаблону `p`.

Этот код реализует алгоритм проверки соответствия строки шаблону, учитывая особенности символов `'?'` и `'*'`.

Задача: 43. Multiply Strings #medium
Условие:

При наличии двух неотрицательных целых чисел num1 и num, представленных в виде строк, возвращает произведение num1 и num2, также представленное в виде строки.
Примечание: Вы не должны использовать какую-либо встроенную библиотеку BigInteger или преобразовывать входные данные в integer напрямую.

Решение:

class Solution {
    func multiply(_ num1: String, _ num2: String) -> String {
        
        func sum(_ n1: [Int], _ n2: [Int]) -> [Int] {
            
            var res = [Int]()

            for i in 0..<max(n1.count, n2.count) {
                if res.count <= i { res.append(0) }
                if i < n1.count { res[i] += n1[i] }
                if i < n2.count { res[i] += n2[i] }

                if res[i] > 9 {
                    res[i] -= 10
                    res.append(1)
                }
            }

            return res
        }

        func mult(_ n: [Int], _ a: Int) -> [Int] {

            var res = [Int]()

            for i in n.indices {
                if res.count <= i { res.append(0) }
                res[i] += n[i] * a

                if res[i] > 9 {
                    res.append(0)
                    while res[i] > 9 {
                        res[i + 1] = res[i] / 10
                        res[i] %= 10
                    }
                }
            }

            return res
        }

        let n1 = num1.reversed().map { Int(String($0))! }
        let n2 = num2.reversed().map { Int(String($0))! }

        var res = [0]

        for i in n1.indices {
            let m = Array(repeating: 0, count: i) + mult(n2, n1[i])
            res = sum(res, m)

            while res.count > 1, res.last! == 0 {
                res.remove(at: res.count - 1)
            }
        }

        return res
            .reversed()
            .map(String.init)
            .joined()
    }
}

Пояснение:
Этот код представляет собой функцию `multiply`, которая умножает две числа, представленные строками `num1` и `num2`, и возвращает результат умножения в виде строки. Код итеративно умножает числа, представленные в виде массивов цифр, используя вспомогательные функции `mult` и `sum`, а затем преобразует результат обратно в строку. Вот разбор кода:

1. Функции `mult` и `sum` используются для умножения чисел разных порядков и сложения результатов, соответственно. Обе функции принимают массив цифр `n1` и `n2`, представляющие числа, и возвращают результат вычисления также в виде массива цифр `res`.

2. В основной функции `multiply`, числа `num1` и `num2` преобразуются в массивы цифр `n1` и `n2`, где каждая цифра строки преобразуется в целое число и массив переворачивается для удобства работы.

3. Происходит инициализация переменной `res` значением `[0]`, представляющим результат умножения.

4. Далее происходит итерация по цифрам массива `n1`. Для каждой цифры `n1[i]` умножается массив `n2`, с учетом порядка разряда. Произведение добавляется в переменную `m`.

5. Полученное произведение добавляется к результату с помощью функции `sum`. Затем убираются ведущие нули из результата.

6. Наконец, результат преобразуется обратно в строку путем разворота массива, преобразования каждого элемента в строку, и объединения всех элементов.

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

Задача: №21. Merge Two Sorted Lists #easy

Условие:

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

Решение:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
        // Base case
        guard let list1 = list1 else { return list2 }
        guard let list2 = list2 else { return list1 }
        // Initialize the merged list's head and tail
        var mergedHead: ListNode?
        var mergedTail: ListNode?

        // Compare the values of the current nodes of l1 and l2
        if list1.val < list2.val {
            mergedHead = list1
            mergedTail = mergeTwoLists(list1.next, list2)
        } else {
            mergedHead = list2
            mergedTail = mergeTwoLists(list1, list2.next)
        }
        // Set the mergedHead's next pointer to the mergedTail
        mergedHead?.next = mergedTail
        // Return the mergedHead
        return mergedHead
    }
}

Пояснение:
Базовый случай:

Функция начинается с проверки, не является ли один из входных списков пустым (nil). Если list1 пуст, то возвращается list2, и наоборот. Это условие базового случая, которое завершается рекурсию.
Инициализация:

Если оба списка не пусты, инициализируются переменные mergedHead и mergedTail, которые будут использоваться для отслеживания начала и конца нового объединенного списка.
Сравнение значений узлов:

Затем происходит сравнение значений текущих узлов в list1 и list2. На основе этого сравнения:
Если значение в list1 меньше значения в list2, это означает, что текущий узел list1 должен стать частью результирующего списка. Таким образом, mergedHead указывает на list1, и рекурсивно вызывается функция mergeTwoLists для слияния оставшейся части list1 и всего list2.
Если значение в list2 меньше или равно значению в list1, то в результирующий список добавляется узел из list2, и функция рекурсивно вызывается для слияния всего list1 и оставшейся части list2.
Соединение результатов:

После того как одна из рекурсий возвращает результирующий список (или его часть), mergedTail присваивается mergedHead.next. Это соединяет текущий узел с результатом рекурсивного вызова, обеспечивая корректное продолжение списка.
Возврат результата:

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

Задача:22. Generate Parentheses #Medium
Условие:

Учитывая n пар круглых скобок, напишите функцию для генерации всех комбинаций правильно сформированных круглых скобок.

Решение:

import Foundation

func generateParenthesis(_ n: Int) -> [String] {
    var result = [String]()
    generate(current: "", open: 0, close: 0, max: n, result: &result)
    return result
}

private func generate(current: String, open: Int, close: Int, max: Int, result: inout [String]) {
    if current.count == max * 2 {
        result.append(current)
        return
    }
    
    if open < max {
        generate(current: current + "(", open: open + 1, close: close, max: max, result: &result)
    }
    
    if close < open {
        generate(current: current + ")", open: open, close: close + 1, max: max, result: &result)
    }
}

// Пример использования:
let n = 3
let combinations = generateParenthesis(n)
print(combinations)
П

ояснение:

Основная идея

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

Шаги решения

1. Инициализация и запуск рекурсии:
- Функция, принимающая число пар скобок (n), создает пустой массив для хранения результатов и запускает рекурсивную функцию с начальными параметрами.

2. Рекурсивная функция:
- В этой функции проверяется текущая длина строки скобок. Если длина достигла 2 * n (две скобки на каждую пару), текущая строка добавляется в массив результатов, и рекурсия завершается для этой ветви.

3. Добавление открывающей скобки:
- Если количество открытых скобок меньше максимального (n), добавляется открывающая скобка, и рекурсивная функция вызывается снова с обновленным состоянием.

4. Добавление закрывающей скобки:
- Если количество закрытых скобок меньше количества открытых, добавляется закрывающая скобка, и рекурсивная функция вызывается снова с обновленным состоянием.

Логика работы

- Рекурсивная функция строит строку скобок шаг за шагом, добавляя либо открывающую, либо закрывающую скобку, если это возможно.
- Функция следит за тем, чтобы в любой момент времени количество закрывающих скобок не превышало количество открывающих, что гарантирует правильность формирования скобок.
- Когда строка достигает длины 2 * n, она добавляется в массив результатов.

Вывод

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

Задача: 23. Merge k Sorted Lists #medium

Условие:

Вам дан массив из k списков связанных списков, каждый связанный список отсортирован в порядке возрастания.Объедините все связанные списки в один отсортированный связанный список и верните его.

Решение:

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

func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
    var heap = [ListNode]()
    
    // Инициализируем кучу начальными значениями из всех списков
    for list in lists {
        if let node = list {
            heap.append(node)
        }
    }
    
    // Определяем компаратор для кучи
    heap.sort { $0.val < $1.val }
    
    let dummy = ListNode(0)
    var current: ListNode? = dummy
    
    while !heap.isEmpty {
        let smallest = heap.removeFirst()
        current?.next = smallest
        current = smallest
        
        if let next = smallest.next {
            var index = heap.firstIndex { $0.val > next.val } ?? heap.count
            heap.insert(next, at: index)
        }
    }
    
    return dummy.next
}

// Пример использования
let node1 = ListNode(1)
let node2 = ListNode(4)
let node3 = ListNode(5)
node1.next = node2
node2.next = node3

let node4 = ListNode(1)
let node5 = ListNode(3)
let node6 = ListNode(4)
node4.next = node5
node5.next = node6

let node7 = ListNode(2)
let node8 = ListNode(6)
node7.next = node8

let lists: [ListNode?] = [node1, node4, node7]
if let mergedList = mergeKLists(lists) {
    var current: ListNode? = mergedList
    while current != nil {
        print(current!.val, terminator: " ")
        current = current?.next
    }
}
 

Пояснение:

Основная идея

Задача состоит в объединении нескольких отсортированных связанных списков в один отсортированный связанный список. Для этого используется приоритетная очередь (min-heap) для эффективного извлечения минимального элемента среди всех текущих головных узлов списков.

Шаги решения

1. **Определение структуры
ListNode**:
- Это стандартная структура узла связанного списка, содержащая значение (val) и указатель на следующий узел (next).
Инициализация кучичи**:
- Создаем массив heap, который будет использоваться как куча для хранения текущих головных узлов всех списков.
- Заполняем кучу начальными узлами каждого списка из входного массива lists.
Сортировка кучичи**:
- Изначально сортируем кучу по значениям узлов. Это упрощает дальнейшую вставку новых элементов в отсортированном порядке.

4. Создание фиктивного узла (dummy):
- Создаем фиктивный узел, чтобы облегчить обработку головы результирующего списка.
- Используем указатель current, который будет перемещаться по новому связанному списОбработка кучиа кучи**:
- Пока куча не пуста, извлекаем минимальный элемент (первый элемент массива).
- Присоединяем этот элемент к результирующему списку.
- Если у извлеченного узла есть следующий узел, вставляем его в кучу в правильное место, чтобы сохранить сортировку.
- Для вставки нового элемента используем бинарный поиск для нахождения правильного места вставВозвращение результирующего спискасписка**:
- Возвращаем следующий элемент от фиктивного узла (dummy.next), который является головой нового отсортированного связанного списка.

Пример использования

В примере создаются три отсортированных связанных списка:
- Первый список: 1 -> 4 -> 5
- Второй список: 1 -> 3 -> 4
- Третий список: 2 -> 6

Функция mergeKLists объединяет эти списки в один отсортированный список: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6. Затем результаты выводятся в консоль.

Заключение

Этот алгоритм использует приоритетную очередь для эффективного объединения нескольких отсортированных связанных списков в один отсортированный список. Время выполнения оптимизировано за счет использования кучи для извлечения минимальных элементов и вставки новых элементов в правильном порядке.

Задача: 24. Swap Nodes in Pairs #medium

Условие:

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

Решение:

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

func swapPairs(_ head: ListNode?) -> ListNode? {
    let dummy = ListNode(0)
    dummy.next = head
    var current: ListNode? = dummy
    
    while current?.next != nil && current?.next?.next != nil {
        let first = current?.next
        let second = current?.next?.next
        
        first?.next = second?.next
        second?.next = first
        current?.next = second
        
        current = first
    }
    
    return dummy.next
}

// Пример использования
let node1 = ListNode(1)
let node2 = ListNode(2)
let node3 = ListNode(3)
let node4 = ListNode(4)
node1.next = node2
node2.next = node3
node3.next = node4

if let swappedList = swapPairs(node1) {
    var current: ListNode? = swappedList
    while current != nil {
        print(current!.val, terminator: " ")
        current = current?.next
    }
}

Пояснение:
1. Определение структуры
ListNode:
- Создается класс ListNode для представления узла связанного списка. У каждого узла есть значение (val) и указатель на следующий узел (next).

2. Инициализация фиктивного узла (dummy):
- Создаем фиктивный узел, который упрощает обработку головы списка.
- dummy.next указывает на текущую голову спис
Перестановка узлов узлов:
- Используем указатель current, начинающийся с фиктивного узла.
- В цикле проверяем, что есть по крайней мере два узла для перестановки (current?.next и current?.next?.next).
- Указываем переменные first и second для двух узлов, которые будут меняться местами.
- Меняем местами first и second путем обновления указателей:
- first?.next указывает на узел, следующий за second.
- second?.next указывает на first.
- current?.next указывает на second, делая second новым начальным узлом пары.
- Обновляем current, чтобы перейти к следующей паре узл
Возвращение головы нового спискасписка:
- Возвращаем dummy.next, которая теперь указывает на новую голову списка после всех перестановок.

Пример использования

В примере создается связанный список 1 -> 2 -> 3 -> 4. После вызова функции swapPairs, узлы будут переставлены парами: 2 -> 1 -> 4 -> 3. Результат выводится в консоль.

Задача: 25. Reverse Nodes in k-Group #hard

Условие:

Учитывая заголовок связанного списка, поменяйте местами узлы списка k за раз и верните измененный список.

k — целое положительное число, меньшее или равное длине связанного списка. Если количество узлов не кратно k, то пропущенные узлы в конечном итоге должны остаться такими, какие они есть.

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

Решение:

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

func reverseKGroup(_ head: ListNode?, _ k: Int) -> ListNode? {
    if head == nil || k == 1 {
        return head
    }
    
    let dummy = ListNode(0)
    dummy.next = head
    var current: ListNode? = dummy
    var next: ListNode?
    var prev: ListNode? = dummy
    
    // Определяем длину списка
    var count = 0
    while current?.next != nil {
        current = current?.next
        count += 1
    }
    
    while count >= k {
        current = prev?.next
        next = current?.next
        for _ in 1..<k {
            current?.next = next?.next
            next?.next = prev?.next
            prev?.next = next
            next = current?.next
        }
        prev = current
        count -= k
    }
    
    return dummy.next
}

// Пример использования
let node1 = ListNode(1)
let node2 = ListNode(2)
let node3 = ListNode(3)
let node4 = ListNode(4)
let node5 = ListNode(5)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

if let reversedList = reverseKGroup(node1, 3) {
    var current: ListNode? = reversedList
    while current != nil {
        print(current!.val, terminator: " ")
        current = current?.next
    }
}

Пояснение:
1. Определение структуры ListNode:
   - Класс ListNode представляет узел связанного списка с полями для значения (val) и указателя на следующий узел (next).

2. Инициализация фиктивного узла (dummy):
   - Создаем фиктивный узел для упрощения обработки головы списка и устанавливаем его next на текущую голову спис
Определение длины спискасписка:
   - Сначала определяем длину списка, чтобы знать, сколько полных групп по k узлов можно переставить.

4. Перестановка узлов по k за раз:
   - Пока оставшихся узлов хватает для полной группы по k узлов:
     - Устанавливаем current на первый узел текущей группы, а next на второй узел.
     - Перемещаем узлы в группе, изменяя указатели так, чтобы узлы были переставлены в обратном порядке.
     - После перестановки обновляем prev для перехода к следующей группе.
     - Уменьшаем count на k, так как мы уже обработали одну Возвращение головы нового спискаого списка:
   - Возвращаем dummy.next, который теперь указывает на новую голову списка после всех перестановок.

Пример использования

В примере создается связанный список 1 -> 2 -> 3 -> 4 -> 5. После вызова функции reverseKGroup с k = 3, узлы будут переставлены группами по три: 3 -> 2 -> 1 -> 4 -> 5. Результат выводится в консоль..

Задача: 25. Reverse Nodes in k-Group #hard

Условие:

Учитывая заголовок связанного списка, поменяйте местами узлы списка k за раз и верните измененный список.

k — целое положительное число, меньшее или равное длине связанного списка. Если количество узлов не кратно k, то пропущенные узлы в конечном итоге должны остаться такими, какие они есть.

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

Решение:

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

func reverseKGroup(_ head: ListNode?, _ k: Int) -> ListNode? {
    if head == nil || k == 1 {
        return head
    }
    
    let dummy = ListNode(0)
    dummy.next = head
    var current: ListNode? = dummy
    var next: ListNode?
    var prev: ListNode? = dummy
    
    // Определяем длину списка
    var count = 0
    while current?.next != nil {
        current = current?.next
        count += 1
    }
    
    while count >= k {
        current = prev?.next
        next = current?.next
        for _ in 1..<k {
            current?.next = next?.next
            next?.next = prev?.next
            prev?.next = next
            next = current?.next
        }
        prev = current
        count -= k
    }
    
    return dummy.next
}

// Пример использования
let node1 = ListNode(1)
let node2 = ListNode(2)
let node3 = ListNode(3)
let node4 = ListNode(4)
let node5 = ListNode(5)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

if let reversedList = reverseKGroup(node1, 3) {
    var current: ListNode? = reversedList
    while current != nil {
        print(current!.val, terminator: " ")
        current = current?.next
    }
}

Пояснение:

1. Определение структуры ListNode:
   - Класс ListNode представляет узел связанного списка с полями для значения (val) и указателя на следующий узел (next).

2. Инициализация фиктивного узла (dummy):
   - Создаем фиктивный узел для упрощения обработки головы списка и устанавливаем его next на текущую голову спис
Определение длины спискасписка:
   - Сначала определяем длину списка, чтобы знать, сколько полных групп по k узлов можно переставить.

4. Перестановка узлов по k за раз:
   - Пока оставшихся узлов хватает для полной группы по k узлов:
     - Устанавливаем current на первый узел текущей группы, а next на второй узел.
     - Перемещаем узлы в группе, изменяя указатели так, чтобы узлы были переставлены в обратном порядке.
     - После перестановки обновляем prev для перехода к следующей группе.
     - Уменьшаем count на k, так как мы уже обработали одну Возвращение головы нового спискаого списка:
   - Возвращаем dummy.next, который теперь указывает на новую голову списка после всех перестановок.

Пример использования

В примере создается связанный список 1 -> 2 -> 3 -> 4 -> 5. После вызова функции reverseKGroup с k = 3, узлы будут переставлены группами по три: 3 -> 2 -> 1 -> 4 -> 5. Результат выводится в консоль..

Задача: 26. Remove Duplicates from Sorted Array #easy

Условие:

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

Считайте, что количество уникальных элементов чисел равно k. Чтобы вас приняли, вам нужно сделать следующее:

Измените массив nums так, чтобы первые k элементов nums содержали уникальные элементы в том порядке, в котором они присутствовали в nums изначально. Остальные элементы nums не важны, как и размер nums.
Вернуть К.

Решение:

func removeDuplicates(_ nums: inout [Int]) -> Int {
    if nums.isEmpty { return 0 }
    
    var k = 1 // Индекс для уникальных элементов
    
    for i in 1..<nums.count {
        if nums[i] != nums[k - 1] {
            nums[k] = nums[i]
            k += 1
        }
    }
    
    return k
}

// Пример использования
var nums = [1, 1, 2, 2, 2, 3, 4, 4, 5]
let k = removeDuplicates(&nums)
print("Количество уникальных элементов:", k) // Вывод: Количество уникальных элементов: 5
print("Массив с уникальными элементами:", nums.prefix(k)) // Вывод: Массив с уникальными элементами: [1, 2, 3, 4, 5]

Пояснение:
- В функции removeDuplicates используется переменная k для отслеживания текущей позиции для уникальных элементов.
- Мы проходим по массиву, начиная с индекса 1, и сравниваем текущий элемент с предыдущим (на позиции k-1).
- Если текущий элемент отличается от предыдущего, мы помещаем его на позицию k и увеличиваем k.
- В конце функции возвращаем k, который содержит количество уникальных элементов.
- Пример использования показывает, как после удаления дубликатов в массиве nums получается массив с уникальными элементами и выводится их количество.

Задача: 27. Remove Element #easy

Условие:

Учитывая целочисленный массив nums и целочисленное значение, удалите все вхождения val в nums на месте. Порядок элементов может быть изменен. Затем верните количество элементов в виде чисел, которые не равны val.

Учитывайте количество элементов в nums, которые не равны val be k. Чтобы вас приняли, вам необходимо сделать следующее:

Измените массив nums так, чтобы первые k элементов nums содержали элементы, не равные val. Остальные элементы nums не важны, как и размер nums.
Вернуть К.

Решение:

func removeElement(_ nums: inout [Int], _ val: Int) -> Int {
    var k = 0 // Индекс для элементов, не равных val
    
    for i in 0..<nums.count {
        if nums[i] != val {
            nums[k] = nums[i]
            k += 1
        }
    }
    
    return k
}

// Пример использования
var nums = [3, 2, 2, 3]
let val = 3
let k = removeElement(&nums, val)
print("Количество элементов, не равных \(val):", k) // Вывод: Количество элементов, не равных 3: 2
print("Массив с элементами, не равными \(val):", nums.prefix(k)) // Вывод: Массив с элементами, не равными 3: [2, 2]

Пояснение:
1. Функция removeElement:
- Принимает массив nums и значение val, которое нужно удалить.
- Инициализирует переменную k для отслеживания индекса элементов, которые не равны val.
- Проходит по массиву nums и для каждого элемента, который не равен val, помещает его на позицию k и увеличивает k.
- Возвращает k, который представляет количество элементов, не равных val.

2. Пример использования:
- Создается массив nums с элементами [3, 2, 2, 3] и значение val = 3.
- Функция вызывается с этими параметрами, и результат (количество элементов, не равных val и измененный массив nums) выводится на экран.

Этот код эффективно решает задачу удаления всех вхождений значения val из массива nums на месте и возвращает количество элементов, которые не равны val, что соответствует требованиям задачи.

Задача: 26. Remove Duplicates from Sorted Array #easy

Условие:

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

Считайте, что количество уникальных элементов чисел равно k. Чтобы вас приняли, вам нужно сделать следующее:

Измените массив nums так, чтобы первые k элементов nums содержали уникальные элементы в том порядке, в котором они присутствовали в nums изначально. Остальные элементы nums не важны, как и размер nums.
Вернуть К.

Решение:

func removeDuplicates(_ nums: inout [Int]) -> Int {
    if nums.isEmpty { return 0 }
    
    var k = 1 // Индекс для уникальных элементов
    
    for i in 1..<nums.count {
        if nums[i] != nums[k - 1] {
            nums[k] = nums[i]
            k += 1
        }
    }
    
    return k
}

// Пример использования
var nums = [1, 1, 2, 2, 2, 3, 4, 4, 5]
let k = removeDuplicates(&nums)
print("Количество уникальных элементов:", k) // Вывод: Количество уникальных элементов: 5
print("Массив с уникальными элементами:", nums.prefix(k)) // Вывод: Массив с уникальными элементами: [1, 2, 3, 4, 5]

Пояснение:

- В функции removeDuplicates используется переменная k для отслеживания текущей позиции для уникальных элементов.
- Мы проходим по массиву, начиная с индекса 1, и сравниваем текущий элемент с предыдущим (на позиции k-1).
- Если текущий элемент отличается от предыдущего, мы помещаем его на позицию k и увеличиваем k.
- В конце функции возвращаем k, который содержит количество уникальных элементов.
- Пример использования показывает, как после удаления дубликатов в массиве nums получается массив с уникальными элементами и выводится их количество.

Задача: 28. Find the Index of the First Occurrence in a String #easy

Условие:

Учитывая две строки, игла и стог сена, верните индекс первого вхождения иглы в стоге сена или -1, если игла не является частью стога сена.

Решение:

func findNeedleInHaystack(_ haystack: String, _ needle: String) -> Int {
    if let range = haystack.range(of: needle) {
        return haystack.distance(from: haystack.startIndex, to: range.lowerBound)
    } else {
        return -1
    }
}

// Пример использования
let haystack = "стог сена"
let needle = "игла"
let index = findNeedleInHaystack(haystack, needle)
print("Индекс первого вхождения иглы в стог сена:", index)

Пояснение:
1. Функция findNeedleInHaystack:
- Принимает две строки: haystack (стог сена) и needle (игла).
- Использует метод range(of:) для поиска первого вхождения подстроки needle в строке haystack.
- Если подстрока найдена (range не равен nil), вычисляется индекс первого символа подстроки needle в строке haystack с помощью метода distance(from:to:).
- Возвращается найденный индекс.
- Если подстрока не найдена, возвращается -1.
Пример использованияия:
- Создается строка haystack с текстом "стог сена".
- Создается строка needle с текстом "игла".
- Функция вызывается с этими строками, и результат (индекс или -1) выводится на экран.

Этот код эффективно находит первое вхождение подстроки в строке, сохраняя относительный порядок символов и возвращая соответствующий индекс или -1, если подстрока не найдена.

Задача: 29. Divide Two Integers #medium

Условие:

Учитывая два целых числа: делимое и делитель, разделите два целых числа, не используя операторы умножения, деления и модификатора.

Целочисленное деление должно сокращаться до нуля, что означает потерю дробной части. Например, 8,345 будет сокращено до 8, а -2,7335 будет сокращено до -2.

Возвращает частное после деления делимого на делитель.

Примечание. Предположим, мы имеем дело со средой, которая может хранить целые числа только в пределах 32-битного целого диапазона со знаком: [−2^31, 2^31 − 1]. В этой задаче, если частное строго больше 2^31 - 1, верните 2^31 - 1, а если частное строго меньше -2^31, верните -2^31.

Решение:

func divide(_ dividend: Int, _ divisor: Int) -> Int {
    // Особые случаи: деление на ноль или делитель равен нулю
    if divisor == 0 || (dividend == Int.min && divisor == -1) {
        return Int.max
    }
    
    // Определение знака результата
    let isNegative = (dividend < 0) != (divisor < 0)
    
    // Приведение чисел к абсолютным значениям и приведение их к типу Int64,
    // чтобы избежать переполнения при работе с Int32.
    var absDividend = abs(Int64(dividend))
    let absDivisor = abs(Int64(divisor))
    
    // Инициализация результата
    var result: Int64 = 0
    
    // Выполнение деления путем вычитания
    while absDividend >= absDivisor {
        var tempDivisor = absDivisor
        var multiple: Int64 = 1
        
        // Увеличиваем делитель в два раза, пока он не станет больше чем делимое
        while absDividend >= (tempDivisor << 1) {
            tempDivisor <<= 1
            multiple <<= 1
        }
        
        // Вычитаем делитель из делимого и обновляем результат
        absDividend -= tempDivisor
        result += multiple
    }
    
    // Применяем знак к результату и проверяем на переполнение
    if isNegative {
        result = -result
    }
    
    if result > Int64(Int32.max) {
        return Int(Int32.max)
    } else if result < Int64(Int32.min) {
        return Int(Int32.min)
    } else {
        return Int(result)
    }
}

// Пример использования
let dividend = 10
let divisor = 3
let quotient = divide(dividend, divisor)
print("Частное деления \(dividend) на \(divisor) равно \(quotient)") 

Пояснение:
1. Особые случаи:
- Проверяем случаи деления на ноль или когда делимое равно Int.min, а делитель равен -1, что приведет к переполнению. В таких случаях возвращаем максимальное значение Int.

2. Определение знака результата:
- Определяем знак результата деления на основе знаков делимого и делителя.

3. Приведение к абсолютным значениям:
- Приводим числа к абсолютным значениям для удобства работы и чтобы избежать проблем с переполнением.

4. Цикл деления путем вычитания:
- Используем цикл, в котором делимое вычитается наибольшими возможными кратными значениями делителя, умноженными на степень двойки (tempDivisor <<= 1).

5. Применение знака и проверка на переполнение:
- Применяем знак к результату, затем проверяем, не превышает ли результат допустимый диапазон Int32. Если превышает, возвращаем максимальное или минимальное значение Int32.

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

Задача: 27. Remove Element #easy

Условие:

Учитывая целочисленный массив nums и целочисленное значение, удалите все вхождения val в nums на месте. Порядок элементов может быть изменен. Затем верните количество элементов в виде чисел, которые не равны val.

Учитывайте количество элементов в nums, которые не равны val be k. Чтобы вас приняли, вам необходимо сделать следующее:

Измените массив nums так, чтобы первые k элементов nums содержали элементы, не равные val. Остальные элементы nums не важны, как и размер nums.
Вернуть К.

Решение:

func removeElement(_ nums: inout [Int], _ val: Int) -> Int {
    var k = 0 // Индекс для элементов, не равных val
    
    for i in 0..<nums.count {
        if nums[i] != val {
            nums[k] = nums[i]
            k += 1
        }
    }
    
    return k
}

// Пример использования
var nums = [3, 2, 2, 3]
let val = 3
let k = removeElement(&nums, val)
print("Количество элементов, не равных \(val):", k) // Вывод: Количество элементов, не равных 3: 2
print("Массив с элементами, не равными \(val):", nums.prefix(k)) // Вывод: Массив с элементами, не равными 3: [2, 2]

Пояснение:

1. Функция removeElement:
- Принимает массив nums и значение val, которое нужно удалить.
- Инициализирует переменную k для отслеживания индекса элементов, которые не равны val.
- Проходит по массиву nums и для каждого элемента, который не равен val, помещает его на позицию k и увеличивает k.
- Возвращает k, который представляет количество элементов, не равных val.

2. Пример использования:
- Создается массив nums с элементами [3, 2, 2, 3] и значение val = 3.
- Функция вызывается с этими параметрами, и результат (количество элементов, не равных val и измененный массив nums) выводится на экран.

Этот код эффективно решает задачу удаления всех вхождений значения val из массива nums на месте и возвращает количество элементов, которые не равны val, что соответствует требованиям задачи.

Задача: 30. Substring with Concatenation of All Words #hard
Условие:

Вам дана строка s и массив строк-слов. Все строки слов имеют одинаковую длину.

Объединенная строка — это строка, которая в точности содержит все строки любой перестановки объединенных слов.

Например, если слова = ["ab", "cd", "ef"], то "abcdef", "abefcd", "cdabef", "cdefab", "efabcd" и "efcdab" являются объединенными строками. «acdbef» не является объединенной строкой, поскольку не является объединением какой-либо перестановки слов.
Возвращает массив начальных индексов всех объединенных подстрок в s. Вы можете вернуть ответ в любом порядке.

Решение:

class Solution {
    func findSubstring(_ s: String, _ words: [String]) -> [Int] {

        let len = words.first!.count
        let cnt = words.count

        guard s.count >= cnt * len else { return [] }
        
        let s = Array(s)
        let words = words.map(Array.init)
        let wf = words.reduce(into: [[Character]: Int]()) { $0[$1, default: 0] += 1 }
        let ws = Set(words)
        var res = [Int]()

        for i in 0...(s.count - cnt * len) {

            var sf = [[Character]: Int]()
            var j = i

            for _ in 0..<cnt {

                let w = Array(s[j..<j + len])
                guard ws.contains(w) else { break }

                let old = sf[w, default: 0]
                guard old + 1 <= wf[w]! else { break }

                sf[w] = old + 1
                j += len
            }

            guard j == i + cnt * len, sf == wf else { continue }
            res.append(i)
        }

        return res
    }
}

Пояснение:
Данный код реализует функцию `findSubstring`, которая ищет все подстроки в строке `s`, которые содержат все слова из массива `words`. Каждое слово из массива `words` имеет фиксированную длину, которая определяется длиной первого слова в массиве.

Основные шаги алгоритма:
1. Проверяется, что длина строки `s` больше или равна произведению длины слова на количество слов в массиве `words`. Если это не так, возвращается пустой массив.
2. Входная строка `s` и массив слов `words` преобразуются в массивы символов, чтобы облегчить обращение к символам.
3. Создается словарь `wf`, который содержит количество вхождений каждого слова из массива `words`.
4. Создается множество `ws`, содержащее все слова из массива `words`.
5. Для каждой позиции `i` в строке `s`, начиная с 0 и до `s.count - cnt * len`:
- Сначала создается пустой словарь `sf`, который будет хранить количество вхождений каждого слова на текущей позиции.
- Устанавливается переменная `j` равной `i`.
- Далее, для каждого слова в массиве `words`:
- Извлекается подстрока длиной `len` начиная с позиции `j`.
- Проверяется, содержится ли данное слово в множестве `ws`. Если нет, происходит выход из цикла.
- Проверяется, что количество вхождений данного слова не больше, чем его общее количество в `wf`. Если условие не выполняется, происходит выход из цикла.
- Увеличивается количество вхождений данного слова в словаре `sf`.
- Переменная `j` увеличивается на длину слова.
- Если переменная `j` стала равной `i + cnt * len` и словарь `sf` равен словарю `wf`, то индекс `i` добавляется в массив результатов.
6. Возвращается массив результатов `res`.

Этот алгоритм эффективно находит все подстроки в строке `s`, содержащие все слова из массива `words`. Сложность алгоритма зависит от длины строки `s`, длины слова, числа слов в массиве `words` и общего числа символов в `s`.