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

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

Задача: 136. Single Number
Сложность: easy

Дан непустой массив целых чисел nums, в котором каждый элемент встречается дважды, кроме одного. Найдите этот единственный элемент.

Вы должны реализовать решение с линейной сложностью выполнения и использовать только постоянное дополнительное пространство.

Пример:

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

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

1⃣Переберите все элементы в массиве nums.

2⃣Если какое-то число в nums новое для массива, добавьте его.

3⃣Если какое-то число уже есть в массиве, удалите его.

😎 Решение:

func singleNumber(nums []int) int {
    no_duplicate_list := []int{}
    for _, i := range nums {
        found := false
        for j, x := range no_duplicate_list {
            if i == x {
                found = true
                no_duplicate_list = append(
                    no_duplicate_list[:j],
                    no_duplicate_list[j+1:]...)
                break
            }
        }
        if !found {
            no_duplicate_list = append(no_duplicate_list, i)
        }
    }
    return no_duplicate_list[0]
}

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

📺 База 1000+ реальных собеседований

На программиста, тестировщика, аналитика, проджекта и другие IT профы.

Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д.

🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!

Задача: 711. Number of Distinct Islands II
Сложность: hard

Вам дана бинарная матрица grid. Нужно вернуть количество уникальных островов (групп 1), учитывая вращения и отражения как одинаковую форму.

Пример:

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

Пояснение: острова в левом верхнем и правом нижнем углу — одинаковые по форме (с учётом поворота).

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

1⃣DFS для поиска формы острова
Для каждой клетки 1 вызываем DFS, сохраняем относительные координаты точек острова в массив shape. Помечаем посещённые ячейки как 0.

2⃣Нормализация формы
Для каждой формы создаём 8 возможных трансформаций:
- 4 поворота: (x,y), (-x,y), (x,-y), (-x,-y)
- 4 отражения по диагоналям: (y,x), (-y,x), (y,-x), (-y,-x)
Сортируем координаты каждой трансформации, затем приводим к строке и выбираем лексикографически минимальную — она будет "канонической" формой острова.

3⃣Подсчёт уникальных форм
Храним все канонические формы в map[string]struct{}. Размер map — это количество уникальных островов.

😎 Решение:

package main

import (
  "sort"
  "strconv"
  "strings"
)

func numDistinctIslands2(grid [][]int) int {
  uniqueIslands := make(map[string]struct{})

  for i := 0; i < len(grid); i++ {
    for j := 0; j < len(grid[0]); j++ {
      if grid[i][j] == 1 {
        shape := [][]int{}
        dfs(grid, i, j, i, j, &shape)
        uniqueIslands[normalize(shape)] = struct{}{}
      }
    }
  }

  return len(uniqueIslands)
}

func dfs(grid [][]int, i, j, baseI, baseJ int, shape *[][]int) {
  if i < 0 || i >= len(grid) || j < 0 || j >= len(grid[0]) || grid[i][j] == 0 {
    return
  }
  grid[i][j] = 0
  *shape = append(*shape, []int{i - baseI, j - baseJ})
  dfs(grid, i+1, j, baseI, baseJ, shape)
  dfs(grid, i-1, j, baseI, baseJ, shape)
  dfs(grid, i, j+1, baseI, baseJ, shape)
  dfs(grid, i, j-1, baseI, baseJ, shape)
}

func normalize(shape [][]int) string {
  shapes := make([][][]int, 8)
  for i := range shapes {
    shapes[i] = [][]int{}
  }

  for _, p := range shape {
    x, y := p[0], p[1]
    shapes[0] = append(shapes[0], []int{x, y})
    shapes[1] = append(shapes[1], []int{x, -y})
    shapes[2] = append(shapes[2], []int{-x, y})
    shapes[3] = append(shapes[3], []int{-x, -y})
    shapes[4] = append(shapes[4], []int{y, x})
    shapes[5] = append(shapes[5], []int{y, -x})
    shapes[6] = append(shapes[6], []int{-y, x})
    shapes[7] = append(shapes[7], []int{-y, -x})
  }

  for i := range shapes {
    sort.Slice(shapes[i], func(a, b int) bool {
      if shapes[i][a][0] == shapes[i][b][0] {
        return shapes[i][a][1] < shapes[i][b][1]
      }
      return shapes[i][a][0] < shapes[i][b][0]
    })
  }

  minShape := shapeToString(shapes[0])
  for _, s := range shapes {
    shapeStr := shapeToString(s)
    if shapeStr < minShape {
      minShape = shapeStr
    }
  }

  return minShape
}

func shapeToString(shape [][]int) string {
  var sb strings.Builder
  for _, p := range shape {
    sb.WriteString(strconv.Itoa(p[0]))
    sb.WriteString(",")
    sb.WriteString(strconv.Itoa(p[1]))
    sb.WriteString(";")
  }
  return sb.String()
}

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