Задача: №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`, используя динамическое программирование.