Tinkoff / Тинькофф (T-Bank / Т-Банк) - Алгоритмы

Задача: В массиве А хранятся цены на N предметов. Есть K купонов, которые уменьшают цену предмета на X. Если применить купонов на предмет с ценой a, то его итоговая стоимость будет max(a - t*x, 0) (то есть купоны не могут сделать цену предмета отрицательной). Необходимо вернуть минимальное количество денег, которое придется потратить, чтобы купить все предметы go/slices-arrays

                    A = 8, 3, 10, 5, 13
K = 4
X = 7
result = 12

Задача: Есть матрица NxN, состоящая из 0 и 1, и отражающая расположения кораблей на поле для морского боя. Кораблей может быть любое количество. Условия: go/basics

• Размер кораблей - от 1х1 до 1хN;
• Корабли никак не соприкасаются друг с другом;
• Корабли располагаются горизонтально и вертикально.

                    Необходимо подсчитать количество кораблей:
Пример:
[1, 1, 0, 0, 1, 0],
[0, 0, 0, 0, 1, 0],
[1, 0, 1, 0, 1, 0],
[0, 0, 0, 0, 0, 0],
[1, 0, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 0],

func solve(field [][]int) int {
  return 0
}

func main() {
  var field = [][]int{
    {1, 1, 0, 0, 1, 0},
    {1, 0, 0, 0, 1, 0},
    {1, 0, 1, 0, 1, 0},
    {0, 0, 0, 0, 0, 0},
    {1, 0, 1, 1, 1, 1},
    {0, 0, 0, 0, 0, 0},
  }

  fmt.Println(solve(field))
}

Как решать

• Брутфорс - плохое решение; algorithms/general
• Пройтись по массиву, уменьшая цены товаров больше K на максимальное кол-во купонов. Далее отсортировать по убыванию массив и вычитать также максимум K купонов из каждой цены. Оставшийся массив сложить и вернуть в result; algorithms/general
• Закрашивание - плохое решение. То есть проверять по горизонтали и по вертикали последовательности единиц, затем считать непрерывные последовательности. Проверять клетку слева и сверху от каждой 1, если там не 1, значит мы увидели 1 корабль. algorithms/general

Задача: Есть доска размера M*N. В каждой клетке записано целое число. Надо расположить шахматную ладью так, чтобы сумма чисел на клетках, которые она бьет, была максимальной. Клетка, на которой она будет стоять, тоже учитывается в сумме. Верните эту сумму. Напоминаем, что ладья ходит на любое количество клеток по горизонтали и вертикали algorithms/general

                    maxRookSum([
  [1, 2, 3],
  [3, 4, 1],
  [3, 5, 2]
]) =>16 // максимальная сумма достигается, если ладью поставить в клетку с цифрой 5.

maxRookSum([[1,2,3,4]]) =>10

Задача: У Пети сломалась клавиатура, но заметил он это поздно. Когда он набирает «b» из набранного текста удаляется самая правая строчная (маленькая) буква, а когда набирает «B»- самая правая заглавная. Если таких нет, то нажатие игнорируется. По заданной последовательности нажатых клавиш выведите набранную строку после обработки всех нажатий. go/strings-runes

solve("YetAnotherBrokenKeyboard ") =>"YetnotherrokenKeoard "

Задача: Ваша задача: посчитать максимальное количество пользователей, одновременно смотревших игровой стрим. Каждый пользователь подключался к стриму в какой-то момент времени t_in и отключался в момент времени t_out - время измеряется в секундах (от 0 до 10^9). У каждого пользователя это время свое. Вам дан массив (неупорядоченный) из пар (t_in, t_out) - длина массива от 0 до 10^6. Требуется вывести число - максимальное количество пользователей, которые одновременно смотрели стрим. go/slices-arrays

[] ->0
[(1, 5), (5, 10)] ->1
[(1, 5), (0, 1), (4, 5)] ->2
[(1, 10), (5, 6), (2, 3), (7, 8)] ->2
[(1, 2), (1, 10), (4, 9), (8, 15), (5, 6), (8, 16)] ->4

Примеры

Задача: Maximize Distance to Closest Person https://leetcode.com/problems/maximize-distance-to-closest-person/description/ algorithms/general

Задача: Find All Numbers Disappeared in an Array (Требуется решить с O(1) дополнительной памяти) https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/description/ algorithms/general

Задача: Search a 2D Matrix https://leetcode.com/problems/search-a-2d-matrix/description/ algorithms/sorting-search

Задача: У работника есть минимальный отпуск k. Он может поставить отпуск только в дни, которые в массиве отмечены как 0. В дни со значением 1 ставить отпуск нельзя. Нужно найти сколько возможных комбинаций дней может взять работник. go/slices-arrays

k=2 [0, 0, 0, 1, 0]
ответ: 3 (ведь [0,1].[1,2],[0,1,2])

Пример

Задача: дано два массива a и b, нужно найти минимальный |a[i] - b[j]|. go/slices-arrays

[1, 10, 2], [8, 9, 15]
ответ: 1 (т.к. |10-9|=1)