#easy
Задача: 1523. Count Odd Numbers in an Interval Range

### Условие задачи

Даны два неотрицательных целых числа low и high. Верните количество нечётных чисел между low и high (включительно).

Пример:

Input: low = 3, high = 7
Output: 3
Explanation: The odd numbers between 3 and 7 are [3,5,7].

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

1⃣Проверьте, является ли число low нечётным. Это можно легко сделать с помощью оператора %, но мы используем побитовый оператор &, так как он более эффективен.

2⃣Если low нечётное, увеличьте его на 1.

3⃣Верните (high - low) / 2 + 1. Важный момент здесь - проверить, не стало ли low больше, чем high после увеличения. Это произойдёт, если low = high, и в этом случае следует вернуть 0.

😎 Решение:

class Solution {
    func countOdds(_ low: Int, _ high: Int) -> Int {
        var low = low
        if (low & 1) == 0 {
            low += 1
        }
        return low > high ? 0 : (high - low) / 2 + 1
    }
}

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

#medium
Задача: 750. Number Of Corner Rectangles

Дан указатель на начало односвязного списка и два целых числа left и right, где left <= right. Необходимо перевернуть узлы списка, начиная с позиции left и заканчивая позицией right, и вернуть измененный список.

Пример:

Input: grid = [[1,0,0,1,0],[0,0,1,0,1],[0,0,0,1,0],[1,0,1,0,1]]
Output: 1

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

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

2⃣Подсчитайте количество таких столбцов. Если их больше одного, то они образуют прямоугольники.

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

😎 Решение:

func countCornerRectangles(_ grid: [[Int]]) -> Int {
    var count = 0
    for i in 0..<grid.count {
        for j in i+1..<grid.count {
            var numPairs = 0
            for k in 0..<grid[0].count {
                if grid[i][k] == 1 && grid[j][k] == 1 {
                    numPairs += 1
                }
            }
            if numPairs > 1 {
                count += numPairs * (numPairs - 1) / 2
            }
        }
    }
    return count
}

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

#medium
Задача: 751. IP to CIDR

Дан указатель на начало односвязного списка и два целых числа left и right, где left <= right. Необходимо перевернуть узлы списка, начиная с позиции left и заканчивая позицией right, и вернуть измененный список.

Пример:

Input: ip = "255.0.0.7", n = 10
Output: ["255.0.0.7/32","255.0.0.8/29","255.0.0.16/32"]

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

1⃣Преобразовать начальный IP-адрес в целое число.

2⃣Пока количество оставшихся IP-адресов n больше нуля: Определить наибольший блок, который начинается с текущего IP-адреса и не превышает количество оставшихся IP-адресов. Добавить этот блок к результату. Увеличить текущий IP-адрес на размер блока. Уменьшить количество оставшихся IP-адресов n.

3⃣Преобразовать блоки обратно в формат CIDR и вернуть их.

😎 Решение:

func ipToInt(_ ip: String) -> Int {
    let parts = ip.split(separator: ".").map { Int($0)! }
    return (parts[0] << 24) + (parts[1] << 16) + (parts[2] << 8) + parts[3]
}

func intToIp(_ num: Int) -> String {
    return "\(num >> 24 & 255).\(num >> 16 & 255).\(num >> 8 & 255).\(num & 255)"
}

func cidr(_ ip: String, _ prefixLength: Int) -> String {
    return "\(ip)/\(prefixLength)"
}

func findCidrBlocks(_ startIp: String, _ n: Int) -> [String] {
    var start = ipToInt(startIp)
    var result = [String]()
    var n = n
    
    while n > 0 {
        var maxSize = 1
        while maxSize <= start && maxSize <= n {
            maxSize <<= 1
        }
        maxSize >>= 1
        
        while start % maxSize != 0 {
            maxSize >>= 1
        }
        
        result.append(cidr(intToIp(start), 32 - maxSize.bitLength + 1))
        start += maxSize
        n -= maxSize
    }
    
    return result
}

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

#medium
Задача: 752. Open the Lock

Перед вами замок с 4 круглыми колесами. Каждое колесо имеет 10 слотов: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. Колеса могут свободно вращаться и оборачиваться: например, мы можем повернуть "9" так, чтобы получился "0", или "0" так, чтобы получился "9". Каждый ход состоит из поворота одного колеса на один слот. Изначально замок начинается с '0000', строки, представляющей состояние 4 колес. Вам дан список тупиков, то есть если замок отобразит любой из этих кодов, колеса замка перестанут вращаться, и вы не сможете его открыть. Учитывая цель, представляющую значение колес, которое позволит отпереть замок, верните минимальное общее количество оборотов, необходимое для открытия замка, или -1, если это невозможно.

Пример:

Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6

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

1⃣Используйте алгоритм BFS для поиска кратчайшего пути от начального состояния '0000' до целевого состояния, избегая тупиков. Инициализируйте очередь с начальным состоянием '0000' и начальным шагом 0. Используйте множество для отслеживания посещенных состояний, чтобы избежать повторного посещения одного и того же состояния.

2⃣Для каждого состояния в очереди: Проверьте все возможные переходы на следующий шаг, вращая каждое колесо на +1 и -1. Если найденное состояние является целевым, верните количество шагов. Если найденное состояние не является тупиком и не было посещено ранее, добавьте его в очередь и отметьте как посещенное.

3⃣Если очередь пуста и целевое состояние не найдено, верните -1.

😎 Решение:

func openLock(_ deadends: [String], _ target: String) -> Int {
    func neighbors(_ node: String) -> [String] {
        var res = [String]()
        let nodeArray = Array(node)
        for i in 0..<4 {
            var nodeChars = nodeArray
            let x = Int(String(nodeChars[i]))!
            for d in [-1, 1] {
                let y = (x + d + 10) % 10
                nodeChars[i] = Character(String(y))
                res.append(String(nodeChars))
            }
        }
        return res
    }
    
    let dead = Set(deadends)
    var queue = [(String, Int)]()
    queue.append(("0000", 0))
    var visited = Set<String>()
    visited.insert("0000")
    
    while !queue.isEmpty {
        let (node, steps) = queue.removeFirst()
        if node == target {
            return steps
        }
        if dead.contains(node) {
            continue
        }
        for neighbor in neighbors(node) {
            if !visited.contains(neighbor) {
                visited.insert(neighbor)
                queue.append((neighbor, steps + 1))
            }
        }
    }
    
    return -1
}

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

#medium
Задача: 753. Cracking the Safe

Имеется сейф, защищенный паролем. Пароль представляет собой последовательность из n цифр, каждая из которых может находиться в диапазоне [0, k - 1]. Сейф имеет особый способ проверки пароля. Например, правильный пароль - "345", а вы вводите "012345": после ввода 0 последние 3 цифры - "0", что неверно. После ввода 1 последние 3 цифры - "01", что неверно. После ввода 2 последние 3 цифры - "012", что неверно.
После ввода 3 последние 3 цифры - "123", что неверно. После ввода 4 последние 3 цифры - "234", что неверно. После ввода 5 последние 3 цифры - "345", что верно, и сейф разблокируется. Верните любую строку минимальной длины, которая разблокирует сейф на определенном этапе ввода.

Пример:

Input: n = 1, k = 2
Output: "10"

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

1⃣Создайте граф, где каждая вершина представляет собой строку длины n-1, а каждое ребро между двумя вершинами представляет собой добавление одной из цифр из диапазона [0, k-1].

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

3⃣Составьте итоговую строку, которая включает начальную вершину и все добавленные цифры.

😎 Решение:

func crackSafe(_ n: Int, _ k: Int) -> String {
    var seen = Set<String>()
    var result = [Character]()

    func dfs(_ node: String) {
        for x in 0..<k {
            let neighbor = node + String(x)
            if !seen.contains(neighbor) {
                seen.insert(neighbor)
                dfs(String(neighbor.dropFirst()))
                result.append(Character(String(x)))
            }
        }
    }

    let startNode = String(repeating: "0", count: n - 1)
    dfs(startNode)
    return startNode + String(result)
}

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

#medium
Задача: 754. Reach a Number

Вы стоите в позиции 0 на бесконечной числовой прямой. В позиции target находится пункт назначения. Вы можете сделать некоторое количество ходов numMoves так, чтобы: на каждом ходу вы могли пойти либо налево, либо направо. Во время i-го хода (начиная с i == 1 до i == numMoves) вы делаете i шагов в выбранном направлении. Учитывая целое число target, верните минимальное количество ходов (т.е. минимальное numMoves), необходимое для достижения пункта назначения.

Пример:

Input: target = 2
Output: 3

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

1⃣Инициализируйте переменную для текущей позиции (position) и счетчик шагов (steps).

2⃣Используйте цикл, чтобы добавлять к position текущее количество шагов и увеличивать steps.

3⃣Если position достигает или превышает target и разница между position и target четная, остановите цикл и верните steps.

😎 Решение:

func reachTarget(_ target: Int) -> Int {
    var target = abs(target)
    var position = 0
    var steps = 0
    while position < target || (position - target) % 2 != 0 {
        steps += 1
        position += steps
    }
    return steps
}

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

На easyoffer 2.0 появится:
🎯 Тренажер "Проработка вопросов"

✅ Метод интервальных повторений и флеш-карточки
✅ Персональный подход изучения на основе ваших ответов
✅ Упор на самые частые вопросы

📌 Интервальные повторения по карточкам это научно доказанный метод эффективного обучения. Каждая карточка – это вопрос, который задают на собеседовании, вы можете выбрать "Не знаю", "Знаю", "Не спрашивать". После ответа вам показывается правильный ответ и возможность изучить вопрос подробнее (примеры ответов других людей). От ваших ответов зависит то, как часто карточки будут показываться на следующей тренировке. Трудные вопросы показываются чаще, простые – реже. Это позволяет бить в слабые места. Кроме того, изначальный порядок карточек зависит от частотности (вероятности встретить вопрос).

🚀 Благодаря этому тренажеру вы сможете очень быстро подготовиться к собеседованию, т.к. фокусируетесь отвечать на самые частые вопросы. Именно так готовился я сам, когда искал первую работу программистом.

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

‼️ Очень важно, чтобы как можно больше людей поддержали проект в первые дни, по-этому те кто окажет поддержку первыми получат еще более выгодную стоимость на годовую подписку и существенный 💎 бонус о котором я позже расскажу в этом телеграм канале. Подписывайтесь, чтобы узнать о старте проекта раньше других и воспользоваться лимитированными вознаграждениями.

#medium
Задача: 494. Target Sum

Вам дан массив целых чисел nums и целое число target.

Вы хотите создать выражение из nums, добавляя один из символов '+' или '-' перед каждым числом в nums, а затем объединяя все числа.
Например, если nums = [2, 1], вы можете добавить '+' перед 2 и '-' перед 1, а затем объединить их, чтобы получить выражение "+2-1".
Верните количество различных выражений, которые можно построить и которые оцениваются в target.

Пример:

Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3.
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

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

1⃣Инициализация и вызов рекурсивной функции
Создайте переменную для хранения количества решений (count). Вызовите рекурсивную функцию calculate с начальными параметрами (nums, начальный индекс 0, начальная сумма 0, и target).

2⃣Рекурсивная функция calculate
Если текущий индекс равен длине массива, проверьте, равна ли текущая сумма значению target. Если да, увеличьте счетчик решений. В противном случае, вызовите функцию рекурсивно дважды: добавляя и вычитая текущее значение из суммы.

3⃣Возврат результата
После завершения всех рекурсивных вызовов верните значение счетчика решений.

😎 Решение:

class Solution {
    var count = 0
    
    func findTargetSumWays(_ nums: [Int], _ S: Int) -> Int {
        calculate(nums, 0, 0, S)
        return count
    }
    
    func calculate(_ nums: [Int], _ i: Int, _ sum: Int, _ S: Int) {
        if i == nums.count {
            if sum == S {
                count += 1
            }
        } else {
            calculate(nums, i + 1, sum + nums[i], S)
            calculate(nums, i + 1, sum - nums[i], S)
        }
    }
}

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

#medium
Задача: 443. String Compression


Дан массив символов chars, сжать его, используя следующий алгоритм:

Начните с пустой строки s. Для каждой группы последовательных повторяющихся символов в chars:

Если длина группы равна 1, добавьте символ к строке s.
В противном случае добавьте символ, а за ним длину группы.
Сжатая строка s не должна возвращаться отдельно, а вместо этого должна быть сохранена в входном массиве символов chars. Обратите внимание, что длины групп, которые равны 10 или более, будут разделены на несколько символов в chars.

После того как вы закончите модификацию входного массива, верните новую длину массива.

Вы должны написать алгоритм, который использует только постоянное дополнительное пространство.

Пример:

Input: chars = ["a","a","b","b","c","c","c"]
Output: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]
Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".

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

1⃣Объявите переменные i – первый индекс текущей группы, и res – длина ответа (сжатой строки). Инициализируйте i = 0, res = 0.

2⃣Пока i меньше длины chars: Найдите длину текущей группы последовательных повторяющихся символов groupLength. Добавьте chars[i] к ответу (chars[res++] = chars[i]). Если groupLength > 1, добавьте строковое представление groupLength к ответу и увеличьте res соответственно. Увеличьте i на groupLength и перейдите к следующей группе.

3⃣Верните res.

😎 Решение:

class Solution {
    func compress(_ chars: inout [Character]) -> Int {
        var i = 0
        var res = 0
        while i < chars.count {
            var groupLength = 1
            while i + groupLength < chars.count && chars[i + groupLength] == chars[i] {
                groupLength += 1
            }
            chars[res] = chars[i]
            res += 1
            if groupLength > 1 {
                let strRepr = String(groupLength)
                for ch in strRepr {
                    chars[res] = ch
                    res += 1
                }
            }
            i += groupLength
        }
        return res
    }
}

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

#medium
Задача: 673. Number of Longest Increasing Subsequence

Дан массив целых чисел nums, верните количество самых длинных строго возрастающих подпоследовательностей.

Пример:

Input: n = 1, presses = 1
Output: 2
Explanation: Status can be:
- [off] by pressing button 1
- [on] by pressing button 2

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

1⃣Объявите два массива динамического программирования length и count, и инициализируйте их значениями length[i]=1 и count[i]=1. Итерируйте i от 0 до n−1. Для каждого i итерируйте j от 0 до i−1 и, если nums[j] < nums[i], обновите length[i] и count[i] в зависимости от значений length[j] и count[j].

2⃣Найдите максимальное значение в массиве length и сохраните его в переменной maxLength. Инициализируйте переменную result = 0.

3⃣Итерируйте i от 0 до n−1 и, если length[i] = maxLength, добавьте count[i] к result. Верните result.

😎 Решение:

class Solution {
    func findNumberOfLIS(_ nums: [Int]) -> Int {
        let n = nums.count
        var length = Array(repeating: 1, count: n)
        var count = Array(repeating: 1, count: n)
        
        for i in 0..<n {
            for j in 0..<i {
                if nums[j] < nums[i] {
                    if length[j] + 1 > length[i] {
                        length[i] = length[j] + 1
                        count[i] = 0
                    }
                    if length[j] + 1 == length[i] {
                        count[i] += count[j]
                    }
                }
            }
        }
        
        let maxLength = length.max() ?? 0
        var result = 0
        
        for i in 0..<n {
            if length[i] == maxLength {
                result += count[i]
            }
        }
        
        return result
    }
}

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

#easy
Задача: 561. Array Partition

Дан массив целых чисел nums из 2n элементов. Разделите эти числа на n пар (a1, b1), (a2, b2), ..., (an, bn) так, чтобы сумма min(ai, bi) для всех i была максимальной. Верните максимальную сумму.

Пример:

Input: nums = [1,4,3,2]
Output: 4
Explanation: All possible pairings (ignoring the ordering of elements) are:
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
So the maximum possible sum is 4.

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

1⃣Отсортируйте массив nums в неубывающем порядке.

2⃣Итерируйте через массив, выбирая каждый второй элемент (начиная с первого).

3⃣Суммируйте выбранные элементы и верните эту сумму.

😎 Решение:

class Solution {
    func arrayPairSum(_ nums: [Int]) -> Int {
        let sortedNums = nums.sorted()
        var sum = 0
        for i in stride(from: 0, to: sortedNums.count, by: 2) {
            sum += sortedNums[i]
        }
        return sum
    }
}

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

#medium
Задача: 435. Non-overlapping Intervals

Дан массив интервалов intervals, где intervals[i] = [starti, endi]. Верните минимальное количество интервалов, которые нужно удалить, чтобы остальные интервалы не пересекались.

Пример:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

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

1⃣Отсортируйте интервалы по времени окончания.

2⃣Инициализируйте переменную ответа ans = 0 и целое число k для представления самого последнего времени окончания. k следует инициализировать небольшим значением, например, INT_MIN.

3⃣Итеративно пройдитесь по интервалам. Для каждого интервала: Если время начала больше или равно k, обновите k до времени окончания текущего интервала. В противном случае увеличьте ans. Верните ans.

😎 Решение:

class Solution {
    func eraseOverlapIntervals(_ intervals: [[Int]]) -> Int {
        let sortedIntervals = intervals.sorted { $0[1] < $1[1] }
        var ans = 0
        var k = Int.min
        
        for interval in sortedIntervals {
            let x = interval[0]
            let y = interval[1]
            if x >= k {
                k = y
            } else {
                ans += 1
            }
        }
        
        return ans
    }
}

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

#medium
Задача: 621. Task Scheduler

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

Пример:

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8

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

1⃣Подсчитайте количество каждой задачи и найдите максимальное количество вхождений (maxFreq).

2⃣Вычислите количество интервалов, необходимых для задач с maxFreq: (maxFreq - 1) * (n + 1) + countMaxFreq, где countMaxFreq - количество задач, имеющих maxFreq.

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

😎 Решение:

func leastInterval(_ tasks: [Character], _ n: Int) -> Int {
    var taskCounts = [Character: Int]()
    for task in tasks {
        taskCounts[task, default: 0] += 1
    }
    
    let maxFreq = taskCounts.values.max()!
    let countMaxFreq = taskCounts.values.filter { $0 == maxFreq }.count
    
    return max(tasks.count, (maxFreq - 1) * (n + 1) + countMaxFreq)
}

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

На easyoffer 2.0 появится новый раздел:
Задачи с собеседований

🟠Задачи на Алгоритмические, Live-coding и System Design из реальных собеседований
🟠Вероятность встретить ту или иную задачу
🟠Возможность подготовиться к задачам конкретной компании

Есть много сайтов, на которых можно тренироваться решать задачи, но у них у всех одна проблема – сами задачи люди просто выдумывают. На easyoffer 2.0 вы сможете готовиться к live-coding и system design секциям на основе задач из реальных собеседований. Вы можете найдете самые частые задачи и сделаете упор на их решение.

Считаные дни остались до старта краудфандинговой кампании, чтобы ускорить разработку easyoffer 2.0. Все кто, поддержал проект на этом этапе смогу получить 1 год доступа к сайту по цене месячной подписки, а те кто поддержат проект раньше других ито дешевле + получат существенный бонус. Следите за стартом 👉 в этом телеграм канале.

Задача: 1244. Design A Leaderboard
Сложность: medium

Разработайте класс Leaderboard, который содержит 3 функции: addScore(playerId, score): Обновляет таблицу лидеров, добавляя счет к счету данного игрока. Если в таблице лидеров нет игрока с таким id, добавьте его в таблицу лидеров с заданным счетом. top(K): Возвращает сумму очков K лучших игроков. reset(playerId): Сбрасывает счет игрока с заданным идентификатором в 0 (другими словами, стирает его из таблицы лидеров). Гарантируется, что игрок был добавлен в таблицу лидеров до вызова этой функции. Изначально таблица лидеров пуста.

Пример:

Input: 
["Leaderboard","addScore","addScore","addScore","addScore","addScore","top","reset","reset","addScore","top"]
[[],[1,73],[2,56],[3,39],[4,51],[5,4],[1],[1],[2],[2,51],[3]]
Output: 
[null,null,null,null,null,null,73,null,null,null,141]

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

1⃣addScore(playerId, score):
Если игрок уже существует в таблице лидеров, добавляем к его текущему счету новое значение.
Если игрок не существует, добавляем его с заданным счетом.

2⃣top(K):
Сортируем игроков по их счету в порядке убывания.
Возвращаем сумму очков K лучших игроков.

3⃣reset(playerId):
Устанавливаем счет игрока в 0.

😎 Решение:

class Leaderboard {
    private var scores: [Int: Int]

    init() {
        scores = [Int: Int]()
    }

    func addScore(_ playerId: Int, _ score: Int) {
        scores[playerId, default: 0] += score
    }

    func top(_ K: Int) -> Int {
        return scores.values.sorted(by: >).prefix(K).reduce(0, +)
    }

    func reset(_ playerId: Int) {
        scores[playerId] = 0
    }
}

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

Задача: 81. Search in Rotated Sorted Array II
Сложность: medium

В массиве целых чисел nums, отсортированном в неубывающем порядке (не обязательно содержащем уникальные значения), произведена ротация в неизвестном индексе поворота k (0 <= k < nums.length). В результате массив принимает вид [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (нумерация с 0). Например, массив [0,1,2,4,4,4,5,6,6,7] может быть повернут в индексе 5 и превратиться в [4,5,6,6,7,0,1,2,4,4].

Для данного массива nums после ротации и целого числа target необходимо вернуть true, если target присутствует в nums, и false в противном случае.

Необходимо сократить количество операций поиска настолько, насколько это возможно.

Пример:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

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

1⃣Вспомним стандартный бинарный поиск, где мы используем два указателя (start и end), чтобы отслеживать область поиска в массиве arr. Затем мы делим пространство поиска на три части: [start, mid), [mid, mid], (mid, end]. Далее мы продолжаем искать наш целевой элемент в одной из этих зон поиска.

2⃣Определяя положение arr[mid] и target в двух частях массива F и S, мы можем сократить область поиска так же, как в стандартном бинарном поиске:
Случай 1: arr[mid] находится в F, target в S: так как S начинается после окончания F, мы знаем, что элемент находится здесь: (mid, end].
Случай 2: arr[mid] находится в S, target в F: аналогично, мы знаем, что элемент находится здесь: [start, mid).
Случай 3: Оба arr[mid] и target находятся в F: поскольку оба они находятся в той же отсортированной части массива, мы можем сравнить arr[mid] и target, чтобы решить, как сократить область поиска.
Случай 4: Оба arr[mid] и target находятся в S: так как оба они в той же отсортированной части массива, мы также можем сравнить их для решения о сокращении области поиска.

3⃣Однако, если arr[mid] равен arr[start], то мы знаем, что arr[mid] может принадлежать и F, и S, и поэтому мы не можем определить относительное положение target относительно mid. В этом случае у нас нет другого выбора, кроме как перейти к следующей области поиска итеративно. Таким образом, существуют области поиска, которые позволяют использовать бинарный поиск, и области, где это невозможно.

😎 Решение:

func search(_ nums: [Int], _ target: Int) -> Bool {
    var start = 0
    var end = nums.count - 1

    while start <= end {
        let mid = start + (end - start) / 2
        if nums[mid] == target {
            return true
        }

        if nums[start] == nums[mid] {
            start += 1
            continue
        }

        let isPivotArray = nums[start] <= nums[mid]
        let isTargetArray = nums[start] <= target
        
        if (isPivotArray != isTargetArray) {
            if isPivotArray {
                start = mid + 1
            } else {
                end = mid - 1
            }
        } else {
            if nums[mid] < target {
                start = mid + 1
            } else {
                end = mid - 1
            }
        }
    }
    return false
}

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

На easyoffer 2.0 появится:
Тренажер "Реальное собеседование"

🟠 Сценарии вопросов из реального собеседования
🟠Возможность подготовиться к собеседованию в конкретную компанию
🟠Итоговая статистика (прошёл/не прошёл)

Сценарий вопросов взят из реального собеседования. То есть вы тренируетесь на тех вопросах, которые действительно задавались в компании X.

Уже в начале следующей недели стартует краудфандинг кампания, чтобы ускорить разработку easyoffer 2.0. Все кто, поддержал проект на этом этапе смогу получить 1 год доступа к сайту по цене месячной подписки. Первые 150 донатеров получать особо-выгодную цену и бонус. Следите за стартом 👉 в этом телеграм канале, в нем информация о старте будет опубликована за 6 часов до официального начала.

Задача: 1228. Missing Number In Arithmetic Progression
Сложность: easy

В массиве arr значения находились в арифметической прогрессии: значения arr[i + 1] - arr[i] равны для всех 0 <= i < arr.length - 1.

Из массива arr было удалено значение, которое не было первым или последним значением в массиве.

Дан массив arr, вернуть удаленное значение.

Пример:

Input: arr = [5,7,11,13]
Output: 9
Explanation: The previous array was [5,7,9,11,13].

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

1⃣Рассчитать разность difference между элементами арифметической прогрессии.

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

3⃣Вернуть первое ожидаемое значение, которое не совпадает с текущим значением в массиве.

😎 Решение:

class Solution {
    func missingNumber(_ arr: [Int]) -> Int {
        let n = arr.count
        let difference = (arr[n - 1] - arr[0]) / n
        var expected = arr[0]

        for val in arr {
            if val != expected {
                return expected
            }
            expected += difference
        }
        return expected
    }
}

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

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

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

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

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

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

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

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

Пример:

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

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

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

2⃣Для расчета значений матрицы dp начинаем с правого нижнего угла подземелья и идем в порядке справа-налево и снизу-вверх. Для каждой ячейки подземелья рассчитываем соответствующее значение dp[row][col].

3⃣Значение dp[row][col] определяется следующими условиями:
Если возможно, сделав шаг вправо из текущей ячейки подземелья, рыцарь может нуждаться в right_health очках здоровья.
Если возможно, сделав шаг вниз из текущей ячейки подземелья, рыцарь может нуждаться в down_health очках здоровья.
Если существует хотя бы одна из вышеуказанных альтернатив, берём минимальное значение из них для dp[row][col].
Если ни одна из вышеуказанных альтернатив не существует, то есть мы находимся в целевой ячейке, возможны два случая:
Если текущая ячейка содержит магический шар, то достаточно одного очка здоровья.
Если текущая ячейка содержит демона, то рыцарь должен иметь одно очко здоровья плюс очки урона, которые нанесет демон.

😎 Решение:

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

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

    for row in stride(from: rows - 1, through: 0, by: -1) {
        for col in stride(from: cols - 1, through: 0, by: -1) {
            let currCell = dungeon[row][col]

            let rightHealth = getMinHealth(currCell, row, col + 1)
            let downHealth = getMinHealth(currCell, row + 1, col)
            let nextHealth = min(rightHealth, downHealth)

            let minHealth: Int
            if nextHealth != Int.max {
                minHealth = nextHealth
            } else {
                minHealth = currCell >= 0 ? 1 : 1 - currCell
            }

            dp[row][col] = minHealth
        }
    }

    return dp[0][0]
}

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

Задача: 66. Plus One
Сложность: easy

Вам дано большое число, представленное в виде массива целых чисел digits, где каждый элемент digits[i] — это i-я цифра числа. Цифры расположены в порядке от старшей к младшей слева направо. Большое число не содержит ведущих нулей.

Увеличьте большое число на один и верните результирующий массив цифр.

Пример:

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1,2,4].

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

1⃣Проходим по входному массиву, начиная с конца массива.

2⃣Устанавливаем все девятки на конце массива в ноль. Если мы встречаем цифру, не равную девяти, увеличиваем её на один. Работа выполнена — возвращаем массив цифр.

3⃣Мы здесь, потому что все цифры были равны девяти. Теперь они все установлены в ноль. Затем мы добавляем цифру 1 в начало остальных цифр и возвращаем результат.

😎 Решение:

func plusOne(_ digits: [Int]) -> [Int] {
    var digits = digits
    let n = digits.count
    for i in stride(from: n - 1, through: 0, by: -1) {
        if digits[i] == 9 {
            digits[i] = 0
        } else {
            digits[i] += 1
            return digits
        }
    }
    digits.insert(1, at: 0)
    return digits
}

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