Задача: 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]
    }
}

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

Задача: 1063. Number of Valid Subarrays
Сложность: hard

Дан целочисленный массив nums. Вернуть количество непустых подмассивов, в которых левый элемент не больше других элементов подмассива.

Подмассив — это непрерывная часть массива.

Пример:

Input: nums = [1,4,2,5,3]
Output: 11
Explanation: There are 11 valid subarrays: [1],[4],[2],[5],[3],[1,4],[2,5],[1,4,2],[2,5,3],[1,4,2,5],[1,4,2,5,3].

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

1⃣Инициализируйте переменную ans значением 0. Инициализируйте пустой стек st, который будет хранить индексы элементов в стеке.

2⃣Итерируйте по элементам массива nums для каждого индекса i: продолжайте извлекать элементы из стека st, пока стек не станет пустым или элемент nums[i] не станет больше элемента на вершине стека. Для каждого извлеченного элемента добавляйте количество подмассивов как i - st.top(). Поместите текущий индекс i в стек.

3⃣Извлеките все оставшиеся элементы из стека и для каждого рассмотрите размер nums как индекс следующего меньшего элемента. Соответственно, добавьте nums.size() - st.top() к переменной ans. Верните ans.

😎 Решение:

func validSubarrays(nums []int) int {
    ans := 0
    var st []int
    
    for i := 0; i < len(nums); i++ {
        for len(st) > 0 && nums[i] < nums[st[len(st)-1]] {
            ans += i - st[len(st)-1]
            st = st[:len(st)-1]
        }
        st = append(st, i)
    }
    
    for len(st) > 0 {
        ans += len(nums) - st[len(st)-1]
        st = st[:len(st)-1]
    }
    
    return ans
}

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

Задача: 1030. Matrix Cells in Distance Order
Сложность: easy

Вам даны четыре целых числа row, cols, rCenter и cCenter. Имеется матрица rows x cols, и вы находитесь на ячейке с координатами (rCenter, cCenter). Верните координаты всех ячеек в матрице, отсортированные по их расстоянию от (rCenter, cCenter) от наименьшего расстояния до наибольшего. Вы можете вернуть ответ в любом порядке, удовлетворяющем этому условию. Расстояние между двумя ячейками (r1, c1) и (r2, c2) равно |r1 - r2| + |c1 - c2|.

Пример:

Input: rows = 1, cols = 2, rCenter = 0, cCenter = 0
Output: [[0,0],[0,1]]

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

1⃣Инициализация и вычисление расстояний:
Создайте список для хранения всех координат ячеек в матрице.
Вычислите расстояние Манхэттена от каждой ячейки до центра и добавьте пару (расстояние, координаты) в список.

2⃣Сортировка списка:
Отсортируйте список по расстоянию в порядке возрастания.

3⃣Извлечение координат:
Извлеките координаты из отсортированного списка и верните их.

😎 Решение:

import (
    "sort"
    "math"
)

func allCellsDistOrder(rows int, cols int, rCenter int, cCenter int) [][]int {
    cells := make([][3]int, 0, rows*cols)
    
    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            distance := int(math.Abs(float64(r - rCenter)) + math.Abs(float64(c - cCenter)))
            cells = append(cells, [3]int{distance, r, c})
        }
    }
    
    sort.Slice(cells, func(i, j int) bool {
        return cells[i][0] < cells[j][0]
    })
    
    result := make([][]int, len(cells))
    for i, cell := range cells {
        result[i] = []int{cell[1], cell[2]}
    }
    
    return result
}

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

Задача: 302. Smallest Rectangle Enclosing Black Pixels
Сложность: hard

Вам дана бинарная матрица размером m x n, где 0 представляет собой белый пиксель, а 1 представляет собой черный пиксель.
Черные пиксели соединены (то есть существует только одна черная область). Пиксели соединены по горизонтали и вертикали.
Даны два целых числа x и y, которые представляют местоположение одного из черных пикселей. Верните площадь наименьшего (выравненного по осям) прямоугольника, который охватывает все черные пиксели.
Вы должны написать алгоритм со сложностью менее O(mn).

Пример:

Input: image = [["0","0","1","0"],["0","1","1","0"],["0","1","0","0"]], x = 0, y = 2
Output: 6

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

1⃣Инициализация границ прямоугольника: Инициализируйте переменные left, right, top и bottom. left и top задаются значениями координат (x, y), right и bottom - значениями x + 1 и y + 1 соответственно.

2⃣Обход всех пикселей: Пройдите по всем координатам (x, y) матрицы. Если текущий пиксель является черным (image[x][y] == 1), обновите границы прямоугольника:
left = min(left, x)
right = max(right, x + 1)
top = min(top, y)
bottom = max(bottom, y + 1)

3⃣Вычисление и возврат площади: После завершения обхода матрицы, верните площадь прямоугольника, используя формулу (right - left) * (bottom - top).

😎 Решение:

package main

func minArea(image [][]byte, x int, y int) int {
    m, n := len(image), len(image[0])
    left := searchColumns(image, 0, y, 0, m, true)
    right := searchColumns(image, y+1, n, 0, m, false)
    top := searchRows(image, 0, x, left, right, true)
    bottom := searchRows(image, x+1, m, left, right, false)
    return (right - left) * (bottom - top)
}

func searchColumns(image [][]byte, i, j, top, bottom int, opt bool) int {
    for i != j {
        k := (i + j) / 2
        t := top
        for t < bottom && image[t][k] == '0' {
            t++
        }
        if (t < bottom) == opt {
            j = k
        } else {
            i = k + 1
        }
    }
    return i
}

func searchRows(image [][]byte, i, j, left, right int, opt bool) int {
    for i != j {
        k := (i + j) / 2
        l := left
        for l < right && image[k][l] == '0' {
            l++
        }
        if (l < right) == opt {
            j = k
        } else {
            i = k + 1
        }
    }
    return i
}

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

Задача: 1053. Previous Permutation With One Swap
Сложность: medium

Учитывая массив целых положительных чисел arr (не обязательно различных), верните лексикографически наибольшую перестановку, которая меньше arr и может быть сделана ровно с одной подстановкой. Если это невозможно, то верните тот же массив. Обратите внимание, что перестановка меняет местами два числа arr[i] и arr[j].

Пример:

Input: arr = [3,2,1]
Output: [3,1,2]

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

1⃣Определи общее количество покупателей, которые удовлетворены в минуты, когда владелец магазина не ворчлив.

2⃣Пройди по массиву, используя скользящее окно для учета эффекта от техники.

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

😎 Решение:

package main

func prevPermOpt1(arr []int) []int {
    n := len(arr)
    var i int
    for i = n - 2; i >= 0; i-- {
        if arr[i] > arr[i+1] {
            break
        }
    }
    if i == -1 {
        return arr
    }

    var j int
    for j = n - 1; j > i; j-- {
        if arr[j] < arr[i] && (j == n-1 || arr[j] != arr[j+1]) {
            break
        }
    }

    arr[i], arr[j] = arr[j], arr[i]
    
    return arr
}

func main() {
    arr := []int{3, 2, 1}
    result := prevPermOpt1(arr)
    fmt.Println(result)
}

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

Задача: 738. Monotone Increasing Digits
Сложность: medium

Целое число имеет монотонно возрастающие цифры тогда и только тогда, когда каждая пара соседних цифр x и y удовлетворяет x <= y. Задав целое число n, верните наибольшее число, которое меньше или равно n с монотонно возрастающими цифрами.

Пример:

Input: n = 10
Output: 9

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

1⃣Преобразуйте число в строку для удобства обработки.

2⃣Найдите позицию, где последовательность перестает быть монотонной.

3⃣Уменьшите соответствующую цифру и установите все последующие цифры в 9.

😎 Решение:

package main

import "strconv"

func monotoneIncreasingDigits(N int) int {
    digits := []byte(strconv.Itoa(N))
    marker := len(digits)
    
    for i := len(digits) - 1; i > 0; i-- {
        if digits[i] < digits[i-1] {
            marker = i
            digits[i-1]--
        }
    }
    
    for i := marker; i < len(digits); i++ {
        digits[i] = '9'
    }
    
    result, _ := strconv.Atoi(string(digits))
    return result
}

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

Задача: 1491. Average Salary Excluding the Minimum and Maximum Salary
Сложность: easy

Вам дан массив уникальных целых чисел salary, где salary[i] — это зарплата i-го сотрудника.

Верните среднюю зарплату сотрудников, исключая минимальную и максимальную зарплату. Ответы, отличающиеся не более чем на 10^-5 от фактического ответа, будут приняты.

Пример:

Input: salary = [4000,3000,1000,2000]
Output: 2500.00000
Explanation: Minimum salary and maximum salary are 1000 and 4000 respectively.
Average salary excluding minimum and maximum salary is (2000+3000) / 2 = 2500

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

1⃣Инициализация переменных:
Установить minSalary в максимально возможное значение, maxSalary в минимально возможное значение и sum в 0.

2⃣Итерация по зарплатам:
Для каждой зарплаты добавить её к переменной sum.
Обновить переменную minSalary, если текущая зарплата меньше её значения.
Обновить переменную maxSalary, если текущая зарплата больше её значения.

3⃣Вычисление среднего значения:
Вернуть значение (sum - minSalary - maxSalary) / (N - 2), предварительно преобразовав числитель и знаменатель в double для точности.

😎 Решение:

func average(salary []int) float64 {
    minSalary := int(^uint(0) >> 1)
    maxSalary := -minSalary - 1
    sum := 0

    for _, sal := range salary {
        sum += sal
        if sal < minSalary {
            minSalary = sal
        }
        if sal > maxSalary {
            maxSalary = sal
        }
    }

    return float64(sum - minSalary - maxSalary) / float64(len(salary) - 2)
}

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