Сообщения

Показаны сообщения с ярлыком "динамическое программирование"

Подстрока с наибольшей вариацией

Изображение
Источник: https://leetcode.com/problems/substring-with-largest-variance/ Вариация строки - это разность между максимально встречающейся буквой и минимально встречающейся буквой в строке. Если строка содержит последовательность одной и той же буквы, то вариация = 0. Дана строка s содержащая нижнестрочные буквы латинского алфавита только. Вернуть наибольшую вариацию среди всех подстрок строки s . Подстрока - это непрерывная последовательность букв в строке. Пример 1: Дано: s = "aababbb" Результат: 3 Объяснение: Все возможные вариации среди соответствующих подстрок перечислены ниже: - Вариация 0 для подстрок "a", "aa", "ab", "abab", "aababb", "ba", "b", "bb", и "bbb". - Вариация 1 для подстрок "aab", "aba", "abb", "aabab", "ababb", "aababbb", и "bab". - Вариация 2 для подстрок "aaba", "ababbb...

Максимальная сумма по подмассиву с одним удалением

Источник: https://leetcode.com/problems/maximum-subarray-sum-with-one-deletion/ Дан массив целых чисел, вернуть сумму по не пустому подмассиву (состоит из смежных элементов исходного массива), который можно получить удалением не более одного элемента массива. Другими словами, можно выбрать подмассив и опционально удалить из него один элемент, чтобы получить подмассив с максимальной суммой элементов. Пример 1: Дано: arr = [1,-2,0,3] Результат: 4 Пояснение: Мы можем взять весь иходный массив [1, -2, 0, 3] и удалить из него -2, и таким образом получим подмассив [1, 0, 3], сумма элементов которого даст максимум по всем возможным подмассивам. Пример 2: Дано: arr = [1,-2,-2,3] Результат: 3 Пояснение: Мы просто берем подмассив [3] и он даст максимально возможную сумму по всем подмассивам даже с удалением одного элемента. Пример 3: Дано : arr = [-1,-1,-1,-1] Результат: -1 Пояснение:  Результата не существует. Мы можем выбрать подмассив [-1] и удалить из него -1, и мы получим тогда...

Максимальная сумма в k-конкатенации массива

Источник: https://leetcode.com/problems/k-concatenation-maximum-sum/ Дан целочисленный массив arr и целое число k . Сделайте конкатенацию массива k раз . Например, если arr = [1, 2] и k = 3 , то новый массив будет [1, 2, 1, 2, 1, 2] . Надо посчитать максимальную сумму, которую можно получить из какого-либо подмассива этого нового массива. Заметьте, что подмассив может быть нулевой длинны, и тогда сумма его элементов будет рана 0. Ответ сфоррмировать по модулю 10 9   + 7 . Пример 1: Дано: arr = [1,2], k = 3 Результат: 9 (все элементы нового массива) Пример 2: Дано: arr = [1,-2,1], k = 5 Результат: 2 (две подряд идущие 1) Пример 3: Дано: arr = [-1,-2], k = 7 Результат: 0 (все элементы отрицательные, значит максимальную сумму даст пустой подмассив). Ограничения: 1 <= arr.length <= 10 5 1 <= k <= 10 5 -10 4   <= arr[i] <= 10 4 Идея решения Мы можем выделить несколько случаев: Case 1 : когда k == 1 , тогда нам нужно найти только подмассив с максимал...

Ход конем на телефонной клавиатуре

Изображение
Источник: https://leetcode.com/problems/knight-dialer/ Шахматный конь ходит буквой Г: две клетки в любом направлении по вертикали/горизонтали, и ещё одна клетка в перпендикулярном направлении по горизонтали/вертикали. Все возможные ходы показаны на диаграмме: Допустим, конь ходит по телефонной клавиатуре, только по кнопкам с цифрами (синие кнопки на диаграмме ниже): Дано целое число n , подсчитать, сколько различных номеров можно набрать за n ходов. Ответ можно вернуть по модулю 10 9   + 7 . Пример 1: Дано: n = 1 Результат: 10 Пояснение: Нам нужно набрать номер длинной 1, поэтому нужно расположить коня в каждой из 10 кнопок - и это и будет результат. Пример 2: Дано : n = 2 Результат : 20 Пояснение : Мы можем набрать: [04, 06, 16, 18, 27, 29, 34, 38, 40, 43, 49, 60, 61, 67, 72, 76, 81, 83, 92, 94] Пример 3: Дано : n = 3 Результат : 46 Пример 4: Дано : n = 4 Результат : 104 Пример 5: Дано : n = 3131 Результат : 136006598 Пояснение : Принимаем во внимание результат ...

Удалить и заработать

Источник: https://leetcode.com/problems/delete-and-earn/ Дан массив nums целых чисел. Из массива можно удалить эемент nums[i] и заработать nums[i] очков . После чего нужно удалить все элементы равные nums[i] - 1 или nums[i] + 1 . Перед проведением операци йдаления у вас 0 очков. Вернуть максимальное значение очков, которые можно заработать, применяя операцию "удалить и заработать", описанную выше. Пример 1: Дано: nums = [3,4,2] Результат: 6 Пояснение: Удялем и зарабатываем 4, затем 3 тоже удаляем, поскольку 3=4-1. Остается [2]. Удаляем 2 и зарабатываем +2. Итого 4+2=6. Пример 2: Дано : nums = [2,2,3,3,3,4] Результат : 9 Пояснение : Удаляем и зарабатываем 3. 2=3-1 и 4=3+1 - удаляем ВСЕ 2 и 4. Остается [3,3]. Удаляем и зарабатываем +3, но больше нет соседних значений (2 и 4). Остается [3]. Удалеям и зарабатываем ещё раз +3. Итого 3+3+3=9. Огранияения: 1 <= nums.length <= 2 * 10 4 1 <= nums[i] <= 10 4 Идея решения Заметим, что если в массиве есть дубл...

Прыгающая лягушка

Изображение
Источник: https://leetcode.com/problems/frog-jump/ Лягушка переберитается через реку. Река разделена на участки, в каждом участке есть камни (но их также может и не быть), по которым прыгает лягушка. Оягушке нельзя упасть в воду. Дан список stones позиций (на участках), отсортированных в возрастающем порядке. Определить, может ли лягушка перейти реку, приземлившись на поседний камень. В начальной позиции лягука на первом камне и может прыгнуть вперед на 1 участок (ход). Если предыдущий прыжок лягушки был на k ходов, ее следующий прыжко может быть на k - 1 ,   k , или k + 1 ходов . Прыгать можно только вперед. Пример 1: Дано: stones = [0,1,3,5,6,8,12,17] Результат: true Пояснение: Лягушка может допрыгнуть до последнего камня так:  1. на k=1 ход до 2-го камня (=1). 2. на k=2 хода до 3-го камня (=3). 2. на k=2 хода до 4-го камня (=5). 2. на k=3 хода до 6-го камня (=8). 2. на k=4 хода до 7-го камня (=12). 2. на k=5 хода до 8-го камня (=17). Пример 2: Дано : stones = [0,1,2,...