Задача: 465. Optimal Account Balancing
Сложность: medium

Дан массив транзакций transactions, где transactions[i] = [fromi, toi, amounti] указывает на то, что человек с ID = fromi дал сумму amounti долларов человеку с ID = toi.

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

Пример:

Input: transactions = [[0,1,10],[2,0,5]]
Output: 2

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

1⃣Создать хеш-таблицу для хранения чистого баланса каждого человека.

2⃣Собрать все ненулевые чистые балансы в массив balance_list.

3⃣Определить рекурсивную функцию dfs(cur) для очистки всех балансов в диапазоне balance_list[0 ~ cur]:
Игнорировать cur, если баланс уже равен 0. Пока balance_list[cur] = 0, переходить к следующему человеку, увеличивая cur на 1.
Если cur = n, вернуть 0.
В противном случае установить cost на большое значение, например, inf.
Пройтись по индексу nxt от cur + 1, если balance_list[nxt] * balance_list[cur] < 0,
Добавить баланс balance_list[cur] к balance_list[nxt]: balance_list[nxt] += balance_list[cur].
Рекурсивно вызвать dfs(cur + 1) как dfs(cur) = 1 + dfs(cur + 1).
Убрать ранее переданный баланс от cur: balance_list[nxt] -= balance_list[cur] (откат).
Повторить с шага 5 и отслеживать минимальное количество операций cost = min(cost, 1 + dfs(cur + 1)), найденных в итерации.
Вернуть cost, когда итерация завершена. Вернуть dfs(0).

😎 Решение:

package main

func minTransfers(transactions [][]int) int {
    creditMap := make(map[int]int)
    for _, t := range transactions {
        creditMap[t[0]] += t[2]
        creditMap[t[1]] -= t[2]
    }
    
    creditList := []int{}
    for _, amount := range creditMap {
        if amount != 0 {
            creditList = append(creditList, amount)
        }
    }
    
    n := len(creditList)
    var dfs func(int) int
    dfs = func(cur int) int {
        for cur < n && creditList[cur] == 0 {
            cur++
        }
        if cur == n {
            return 0
        }
        cost := int(^uint(0) >> 1)
        for nxt := cur + 1; nxt < n; nxt++ {
            if creditList[nxt] * creditList[cur] < 0 {
                creditList[nxt] += creditList[cur]
                cost = min(cost, 1 + dfs(cur + 1))
                creditList[nxt] -= creditList[cur]
            }
        }
        return cost
    }
    
    return dfs(0)
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

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

Задача: 1272. Remove Interval
Сложность: medium

Множество вещественных чисел можно представить как объединение нескольких несовпадающих интервалов, где каждый интервал имеет вид [a, b). Вещественное число x входит в множество, если один из его интервалов [a, b) содержит x (то есть a <= x < b). Вам дан отсортированный список непересекающихся интервалов, представляющих множество вещественных чисел, как описано выше, где intervals[i] = [ai, bi] представляет интервал [ai, bi). Вам также дан еще один интервал toBeRemoved. Верните набор вещественных чисел с интервалом toBeRemoved, удаленным из intervals. Другими словами, верните набор вещественных чисел, каждый x в котором находится в интервале, но не в toBeRemoved. Вашим ответом должен быть отсортированный список непересекающихся интервалов, как описано выше.

Пример:
Input: intervals = [[0,2],[3,4],[5,7]], toBeRemoved = [1,6]
Output: [[0,1],[6,7]]

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

1⃣Итерируйтесь по каждому интервалу в списке intervals.

2⃣Для каждого интервала, проверяйте пересечения с toBeRemoved и обновляйте список результатов.

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

😎 Решение:

func removeInterval(intervals [][]float64, toBeRemoved []float64) [][]float64 {
    result := [][]float64{}
    for _, interval := range intervals {
        if interval[0] < toBeRemoved[0] {
            result = append(result, []float64{interval[0], math.Min(interval[1], toBeRemoved[0])})
        }
        if interval[1] > toBeRemoved[1] {
            result = append(result, []float64{math.Max(interval[0], toBeRemoved[1]), interval[1]})
        }
    }
    return result
}

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

Задача: 1041. Robot Bounded In Circle
Сложность: medium

На бесконечной плоскости робот изначально стоит в точке (0, 0) и обращен лицом на север. Обратите внимание, что: северное направление - это положительное направление оси y. южное направление - это отрицательное направление оси y. восточное направление - это положительное направление оси x. западное направление - это отрицательное направление оси x. робот может получить одну из трех команд: "G": идти прямо 1 единицу. "L": повернуть на 90 градусов влево (т.е, "R": повернуть на 90 градусов вправо (т. е. по часовой стрелке). Робот выполняет данные инструкции по порядку и повторяет их до бесконечности. Возвращается true тогда и только тогда, когда в плоскости существует окружность, такая, что робот никогда не покидает ее.

Пример:

Input: instructions = "GGLLGG"
Output: true

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

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

2⃣Изменение направления:
Робот может двигаться на север (0), восток (1), юг (2), или запад (3). Эти направления можно моделировать с помощью векторов (dx, dy): север (0, 1), восток (1, 0), юг (0, -1), запад (-1, 0).

3⃣Обработка команд:
Пройдите по всем командам и обновите позицию робота и направление, в котором он движется.
Проверка состояния робота:
После выполнения всех команд проверьте, вернулся ли робот в начальную точку (0, 0) или изменил направление. Если одно из этих условий выполнено, робот будет двигаться по замкнутой траектории.

😎 Решение:

func isRobotBounded(instructions string) bool {
    directions := [][2]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}
    x, y, direction := 0, 0, 0
    
    for _, instruction := range instructions {
        switch instruction {
        case 'G':
            x += directions[direction][0]
            y += directions[direction][1]
        case 'L':
            direction = (direction + 3) % 4
        case 'R':
            direction = (direction + 1) % 4
        }
    }
    
    return (x == 0 && y == 0) || direction != 0
}

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

Задача: 1286. Iterator for Combination
Сложность: medium

Создайте класс CombinationIterator:

CombinationIterator(string characters, int combinationLength) Инициализирует объект строкой characters, содержащей отсортированные различные строчные буквы английского алфавита, и числом combinationLength в качестве аргументов.
next() Возвращает следующую комбинацию длины combinationLength в лексикографическом порядке.
hasNext() Возвращает true, если и только если существует следующая комбинация.

Пример:
Input
["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[["abc", 2], [], [], [], [], [], []]
Output
[null, "ab", true, "ac", true, "bc", false]

Explanation
CombinationIterator itr = new CombinationIterator("abc", 2);
itr.next();    // return "ab"
itr.hasNext(); // return True
itr.next();    // return "ac"
itr.hasNext(); // return True
itr.next();    // return "bc"
itr.hasNext(); // return False

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

1⃣Сгенерируйте все возможные бинарные битовые маски длины n: от 0 до 2^n - 1.

2⃣Используйте битовые маски с k установленными битами для генерации комбинаций из k элементов. Если n - 1 - j-й бит установлен в битовой маске, это указывает на присутствие символа characters[j] в комбинации и наоборот.

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

😎 Решение:

package main

import (
    "fmt"
    "strings"
)

type CombinationIterator struct {
    combinations []string
}

func Constructor(characters string, combinationLength int) CombinationIterator {
    var combinations []string
    n, k := len(characters), combinationLength
    for bitmask := 0; bitmask < (1 << n); bitmask++ {
        if bits.OnesCount(uint(bitmask)) == k {
            var curr strings.Builder
            for j := 0; j < n; j++ {
                if bitmask&(1<<(n-j-1)) != 0 {
                    curr.WriteByte(characters[j])
                }
            }
            combinations = append(combinations, curr.String())
        }
    }
    return CombinationIterator{combinations}
}

func (this *CombinationIterator) Next() string {
    n := len(this.combinations)
    res := this.combinations[n-1]
    this.combinations = this.combinations[:n-1]
    return res
}

func (this *CombinationIterator) HasNext() bool {
    return len(this.combinations) > 0
}

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

Задача: 299. Bulls and Cows
Сложность: medium

Вы играете в игру "Быки и коровы" со своим другом.

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

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

Подсказка должна быть в формате "xAyB", где x — количество быков, а y — количество коров. Обратите внимание, что и secret, и guess могут содержать повторяющиеся цифры.

Пример:

Input: secret = "1807", guess = "7810"
Output: "1A3B"
Explanation: Bulls are connected with a '|' and cows are underlined:
"1807"
  |
"7810"

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

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


2⃣Обход строки guess:
Для каждого символа ch в строке guess:
Если ch присутствует в строке secret:
Если текущий символ ch совпадает с символом на той же позиции в secret (ch == secret[idx]):
Увеличьте количество быков: bulls += 1.
Обновите количество коров, если количество текущего символа в хеш-таблице отрицательное или равно нулю (то есть этот символ уже использовался для коров): cows -= int(h[ch] <= 0).
Если текущий символ ch не совпадает с символом на той же позиции в secret (ch != secret[idx]):
Увеличьте количество коров, если количество текущего символа в хеш-таблице больше нуля: cows += int(h[ch] > 0).
Обновите хеш-таблицу, помечая текущий символ как использованный: h[ch] -= 1.


3⃣Возврат результата:
Верните количество быков и коров в формате "xAyB".

😎 Решение:

package main

import (
    "fmt"
    "strconv"
)

func getHint(secret string, guess string) string {
    h := make(map[rune]int)
    for _, ch := range secret {
        h[ch]++
    }

    bulls, cows := 0, 0
    n := len(guess)
    secretArray := []rune(secret)
    guessArray := []rune(guess)

    for idx := 0; idx < n; idx++ {
        ch := guessArray[idx]
        if count, ok := h[ch]; ok {
            if ch == secretArray[idx] {
                bulls++
                if count <= 0 {
                    cows--
                }
            } else {
                if count > 0 {
                    cows++
                }
            }
            h[ch]--
        }
    }

    return strconv.Itoa(bulls) + "A" + strconv.Itoa(cows) + "B"
}

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

Задача: №45. Jump Game II
Сложность: medium

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

Пример:

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

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

1⃣Использовать переменные maxReach, end, jumps для отслеживания дальности прыжка, границы текущего шага и количества прыжков.

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

3⃣Повторять процесс, пока не достигнем последнего индекса.

😎 Решение:

func jump(nums []int) int {
    jumps, end, maxReach := 0, 0, 0

    for i := 0; i < len(nums)-1; i++ {
        maxReach = max(maxReach, i+nums[i])

        if i == end {
            jumps++
            end = maxReach
        }
    }

    return jumps
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

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

Задача: 942. DI String Match
Сложность: easy

Перестановка perm из n + 1 целых чисел всех целых чисел в диапазоне [0, n] может быть представлена в виде строки s длины n, где: s[i] == 'I', если perm[i] < perm[i + 1], и s[i] == 'D', если perm[i] > perm[i + 1]. Получив строку s, восстановите перестановку perm и верните ее. Если существует несколько допустимых перестановок perm, верните любую из них.

Пример:

Input: s = "IDID"
Output: [0,4,1,3,2]

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

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

2⃣Создать массив perm длиной n + 1.
Пройти по строке s:
Если текущий символ равен 'I', добавить low в текущую позицию perm и увеличить low.
Если текущий символ равен 'D', добавить high в текущую позицию perm и уменьшить high.
Добавить оставшееся значение (low или high, так как они будут равны) в последнюю позицию perm.

3⃣Вернуть массив perm.

😎 Решение:

package main

func diStringMatch(s string) []int {
    n := len(s)
    low, high := 0, n
    perm := make([]int, n+1)
    
    for i := 0; i < n; i++ {
        if s[i] == 'I' {
            perm[i] = low
            low++
        } else {
            perm[i] = high
            high--
        }
    }
    
    perm[n] = low
    return perm
}

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

Задача: 1262. Greatest Sum Divisible by Three
Сложность: medium

Если задан целочисленный массив nums, верните максимально возможную сумму элементов массива, которая делится на три.

Пример:
Input: nums = [3,6,5,1,8]
Output: 18

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

1⃣Найдите сумму всех элементов массива.

2⃣Если сумма делится на 3, то она и есть ответ.

3⃣Если сумма при делении на 3 дает остаток 1, удалите один элемент с остатком 1 или два элемента с остатком 2 (если их сумма равна 2).
Если сумма при делении на 3 дает остаток 2, удалите один элемент с остатком 2 или два элемента с остатком 1 (если их сумма равна 2).

😎 Решение:

import (
    "sort"
)

func maxSumDivThree(nums []int) int {
    totalSum := 0
    for _, num := range nums {
        totalSum += num
    }
    if totalSum % 3 == 0 {
        return totalSum
    }
    
    mod1 := []int{}
    mod2 := []int{}
    
    for _, num := range nums {
        if num % 3 == 1 {
            mod1 = append(mod1, num)
        } else if num % 3 == 2 {
            mod2 = append(mod2, num)
        }
    }
    
    sort.Ints(mod1)
    sort.Ints(mod2)
    
    if totalSum % 3 == 1 {
        remove1 := int(^uint(0) >> 1) // maximum int
        if len(mod1) > 0 {
            remove1 = mod1[0]
        }
        remove2 := int(^uint(0) >> 1)
        if len(mod2) >= 2 {
            remove2 = mod2[0] + mod2[1]
        }
        if remove1 < remove2 {
            return totalSum - remove1
        } else {
            return totalSum - remove2
        }
    } else {
        remove2 := int(^uint(0) >> 1)
        if len(mod2) > 0 {
            remove2 = mod2[0]
        }
        remove1 := int(^uint(0) >> 1)
        if len(mod1) >= 2 {
            remove1 = mod1[0] + mod1[1]
        }
        if remove2 < remove1 {
            return totalSum - remove2
        } else {
            return totalSum - remove1
        }
    }
}

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

Задача: 914. X of a Kind in a Deck of Cards
Сложность: easy

Вам дан целочисленный массив deck, где deck[i] - число, написанное на i-й карте. Разделите карты на одну или несколько групп так, чтобы: в каждой группе было ровно x карт, где x > 1, и на всех картах в одной группе было написано одно и то же целое число. Верните true, если такое разделение возможно, или false в противном случае.

Пример:

Input: deck = [1,2,3,4,4,3,2,1]
Output: true

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

1⃣Создать словарь для подсчета частоты каждого числа в массиве deck.

2⃣Найти наибольший общий делитель (НОД) всех частот.

3⃣Проверить, больше ли НОД 1, чтобы определить, можно ли разделить карты на группы.

😎 Решение:

package main

func hasGroupsSizeX(deck []int) bool {
    count := map[int]int{}
    for _, num := range deck {
        count[num]++
    }

    gcd := func(a, b int) int {
        for b != 0 {
            a, b = b, a%b
        }
        return a
    }

    g := 0
    for _, freq := range count {
        g = gcd(g, freq)
    }

    return g > 1
}

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

Задача: №26. Remove Duplicates from Sorted Array
Сложность: easy

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

Пример:

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

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

1⃣Использовать два указателя: i для отслеживания позиции последнего уникального элемента и j для итерации по массиву.

2⃣Если nums[j] не равен nums[i], записать nums[j] на nums[i+1] и сдвинуть i.

3⃣По завершении вернуть i+1 как количество уникальных элементов.

😎 Решение:

func removeDuplicates(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    
    i := 0
    for j := 1; j < len(nums); j++ {
        if nums[j] != nums[i] {
            i++
            nums[i] = nums[j]
        }
    }
    return i + 1
}

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

Задача: 849. Maximize Distance to Closest Person
Сложность: medium

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

Верните это максимальное расстояние до ближайшего человека.

Пример:

Input: seats = [1,0,0,0,1,0,1]
Output: 2
Explanation: 
If Alex sits in the second open seat (i.e. seats[2]), then the closest person has distance 2.
If Alex sits in any other open seat, the closest person has distance 1.
Thus, the maximum distance to the closest person is 2.

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

1⃣Следите за prev, занятым местом слева или на текущей позиции i, и future, занятым местом справа или на текущей позиции i.

2⃣Для каждого пустого места i определите ближайшее занятие места как min(i - prev, future - i), с учетом, что i - prev считается бесконечностью, если слева нет занятого места, и future - i считается бесконечностью, если справа нет занятого места.

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

😎 Решение:

func maxDistToClosest(seats []int) int {
    n := len(seats)
    prev := -1
    future := 0
    ans := 0

    for i := 0; i < n; i++ {
        if seats[i] == 1 {
            prev = i
        } else {
            for future < n && (seats[future] == 0 || future < i) {
                future++
            }
            left := n
            if prev != -1 {
                left = i - prev
            }
            right := n
            if future != n {
                right = future - i
            }
            ans = max(ans, min(left, right))
        }
    }

    return ans
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

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

Задача: 917. Reverse Only Letters
Сложность: easy

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

Пример:

Input: s = "ab-cd"
Output: "dc-ba"

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

1⃣Создать массив для хранения только английских букв из строки s.

2⃣Перевернуть массив с английскими буквами.
Пройти по строке s и заменить каждую английскую букву на соответствующую из перевернутого массива.

3⃣Вернуть результат.

😎 Решение:

package main

func reverseOnlyLetters(s string) string {
    letters := []rune{}
    for _, c := range s {
        if isLetter(c) {
            letters = append(letters, c)
        }
    }
    reverseRunes(letters)
    result := []rune{}
    idx := 0
    for _, c := range s {
        if isLetter(c) {
            result = append(result, letters[idx])
            idx++
        } else {
            result = append(result, c)
        }
    }
    return string(result)
}

func isLetter(c rune) bool {
    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')
}

func reverseRunes(runes []rune) {
    for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
        runes[i], runes[j] = runes[j], runes[i]
    }
}

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