Java | LeetCode

Задача: 600. Non-negative Integers without Consecutive Ones Сложность: hard Дано положительное целое число n, верните количество чисел в диапазоне [0, n], бинарные представления которых не содержат последовательных единиц. Пример:

Input: n = 5
Output: 5
Explanation:
Here are the non-negative integers <= 5 with their corresponding binary representations:
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule. 

👨‍💻 Алгоритм: 1⃣Простой метод заключается в переборе всех чисел от 1 до num. Для каждого текущего выбранного числа проверяем все соседние позиции, чтобы выяснить, содержит ли число две последовательные единицы. Если не содержит, увеличиваем количество чисел без последовательных единиц. 2⃣Чтобы проверить, существует ли 1 на позиции x (считая от младшего значащего бита), в текущем числе n, поступаем следующим образом. Сдвигаем двоичную 1 x−1 раз влево, чтобы получить число y, которое имеет 1 только на x-й позиции. Логическое И числа n и y даст результат 1 только если n содержит 1 на позиции x. 3⃣В конце подсчитываем и возвращаем количество чисел в диапазоне [0, n], не содержащих последовательных единиц. 😎 Решение:

public class Solution {
    public int findIntegers(int num) {
        int count = 0;
        for (int i = 0; i <= num; i++) {
            if (check(i)) {
                count++;
            }
        }
        return count;
    }

    public boolean check(int n) {
        int i = 31;
        while (i > 0) {
            if ((n & (1 << i)) != 0 && (n & (1 << (i - 1))) != 0) {
                return false;
            }
            i--;
        }
        return true;
    }
}

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

Задача: №44. Wildcard Matching Сложность: hard Учитывая входную строку s и шаблон p, реализуйте сопоставление шаблонов с подстановочными знаками с поддержкой: - '?' — соответствует любому одному символу - '*' — соответствует любой последовательности символов (включая пустую) Сопоставление должно охватывать всю строку s. Пример:

Input: s = "adceb", p = "*a*b" Output: true

👨‍💻 Алгоритм: 1⃣Создать двумерный булев массив dp размером (s.length + 1) × (p.length + 1), где dp[i][j] — true, если s[0..i-1] соответствует p[0..j-1]. 2⃣Инициализировать базовые случаи: - dp[0][0] = true - dp[0][j] = true, если p[0..j-1] состоит только из * (иначе — false) 3⃣Заполнить таблицу: - Если p[j-1] == s[i-1] или p[j-1] == '?' → dp[i][j] = dp[i-1][j-1] - Если p[j-1] == '*' → dp[i][j] = dp[i][j-1] || dp[i-1][j] - Иначе → dp[i][j] = false 😎 Решение:

class Solution {
    public boolean isMatch(String s, String p) {
        int n = s.length();
        int m = p.length();
        boolean[][] dp = new boolean[n + 1][m + 1];
        dp[0][0] = true;

        for (int i = 1; i <= m; i++) {
            if (p.charAt(i - 1) == '*') {
                dp[0][i] = dp[0][i - 1];
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                } else {
                    dp[i][j] = false;
                }
            }
        }

        return dp[n][m];
    }
}

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

Задача: 863. All Nodes Distance K in Binary Tree Сложность: medium Дан корень бинарного дерева, значение целевого узла target и целое число k. Верните массив значений всех узлов, которые находятся на расстоянии k от целевого узла. Ответ можно вернуть в любом порядке. Пример:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
Output: [7,4,1]
Explanation: The nodes that are a distance 2 from the target node (with value 5) have values 7, 4, and 1.

👨‍💻 Алгоритм: 1⃣Определите рекурсивную функцию add_parent(cur, parent), чтобы рекурсивно добавлять указатель на родителя к узлу cur. Если cur не пустой, добавьте указатель на parent: cur.parent = parent. Затем рекурсивно вызовите add_parent для левого и правого детей cur: add_parent(cur.left, cur) и add_parent(cur.right, cur). Вызовите add_parent(root, None), чтобы добавить все указатели на родителей (корневой узел не имеет родителя). 2⃣Инициализируйте пустой массив answer и пустое множество visited. Определите рекурсивную функцию dfs(cur, distance) для поиска всех узлов на расстоянии k от узла target. Если cur пустой или уже был посещён, вернитесь. Добавьте cur в visited, чтобы его не посещали повторно. Если distance = k, добавьте cur в answer и вернитесь. 3⃣Рекурсивно вызовите dfs для детей и родителя cur. Вызовите dfs(target, 0), чтобы найти все узлы на расстоянии k. Верните answer после завершения DFS. 😎 Решение:

class Solution {
    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        addParent(root, null);
        
        List<Integer> answer = new ArrayList<>();
        Set<TreeNode> visited = new HashSet<>();
        
        dfs(target, k, visited, answer);
        return answer;
    }
    
    private void addParent(TreeNode cur, TreeNode parent) {
        if (cur != null) {
            cur.parent = parent;
            addParent(cur.left, cur);
            addParent(cur.right, cur);
        }
    }
    
    private void dfs(TreeNode cur, int distance, Set<TreeNode> visited, List<Integer> answer) {
        if (cur == null || visited.contains(cur)) return;
        visited.add(cur);
        if (distance == 0) {
            answer.add(cur.val);
            return;
        }
        dfs(cur.parent, distance - 1, visited, answer);
        dfs(cur.left, distance - 1, visited, answer);
        dfs(cur.right, distance - 1, visited, answer);
    }
}

class TreeNode {
    int val;
    TreeNode left, right, parent;
    TreeNode(int x) { val = x; }
}

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

Задача: 1229. Meeting Scheduler Сложность: medium Даны массивы доступных временных слотов slots1 и slots2 для двух человек и продолжительность встречи duration, верните самый ранний временной слот, который подходит обоим и имеет продолжительность duration. Если нет общего временного слота, который удовлетворяет требованиям, верните пустой массив. Формат временного слота — это массив из двух элементов [start, end], представляющий инклюзивный временной диапазон от start до end. Гарантируется, что никакие два доступных временных слота одного и того же человека не пересекаются друг с другом. То есть для любых двух временных слотов [start1, end1] и [start2, end2] одного и того же человека либо start1 > end2, либо start2 > end1. Пример:

Input: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 8
Output: [60,68]

👨‍💻 Алгоритм: 1⃣Отсортируйте оба массива slots1 и slots2 по времени начала. 2⃣Инициализируйте два указателя, указывающие на начало slots1 и slots2 соответственно. 3⃣Перебирайте, пока указатель1 не достигнет конца slots1 или указатель2 не достигнет конца slots2: Найдите общий слот между slots1[pointer1] и slots2[pointer2]. Если общий слот больше или равен duration, верните результат. В противном случае найдите слот, который заканчивается раньше, и передвиньте указатель. Если общий слот не найден, верните пустой массив. 😎 Решение:

class Solution {
    public List<Integer> minAvailableDuration(int[][] slots1, int[][] slots2, int duration) {
        Arrays.sort(slots1, (a, b) -> a[0] - b[0]);
        Arrays.sort(slots2, (a, b) -> a[0] - b[0]);

        int pointer1 = 0, pointer2 = 0;

        while (pointer1 < slots1.length && pointer2 < slots2.length) {
            int intersectLeft = Math.max(slots1[pointer1][0], slots2[pointer2][0]);
            int intersectRight = Math.min(slots1[pointer1][1], slots2[pointer2][1]);
            if (intersectRight - intersectLeft >= duration) {
                return new ArrayList<Integer>(Arrays.asList(intersectLeft, intersectLeft + duration));
            }
            if (slots1[pointer1][1] < slots2[pointer2][1]) {
                pointer1++;
            } else {
                pointer2++;
            }
        }
        return new ArrayList<Integer>();
    }
}

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

REKONFA Live 6 ноября приглашаем всех, кто имеет отношение к маркетингу и рекламным технологиям, обсудить рынок, тренды, вызовы и их решения. С докладами на актуальные темы выступят лидеры индустрии и медийные спикеры. Принять участие можно офлайн и онлайн. Мероприятие бесплатное, нужно только зарегистрироваться. Зарегистрироваться #реклама 18+ ya.rekonfa.ru О рекламодателе

Задача: 487. Max Consecutive Ones II Сложность: medium Дан бинарный массив nums, верните максимальное количество последовательных единиц в массиве, если можно перевернуть не более одного нуля. Пример:

Input: nums = [1,0,1,1,0]
Output: 4
Explanation: 
- If we flip the first zero, nums becomes [1,1,1,1,0] and we have 4 consecutive ones.
- If we flip the second zero, nums becomes [1,0,1,1,1] and we have 3 consecutive ones.
The max number of consecutive ones is 4.

👨‍💻 Алгоритм: 1⃣Для каждого возможного начала последовательности в массиве nums начните считать количество нулей. 2⃣Для каждой последовательности проверяйте, сколько нулей содержится в ней. Если количество нулей не превышает одного, обновите максимальную длину последовательности единиц. 3⃣Продолжайте проверять все возможные последовательности в массиве, и верните максимальную длину последовательности единиц, удовлетворяющую условию. 😎 Решение:

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int longestSequence = 0;
        for (int left = 0; left < nums.length; left++) {
            int numZeroes = 0;

            for (int right = left; right < nums.length; right++) {
                if (nums[right] == 0) {
                    numZeroes += 1;
                }
                if (numZeroes <= 1) {
                    longestSequence = Math.max(longestSequence, right - left + 1);
                }
            }
        }
        return longestSequence;
    }
}

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

Не дайте хакерам использовать утечки против вас Преступники активно используют слитые данные компаний, чтобы получить несанкционированный доступ. А объем таких утечек за 2024 год вырос на 64%. На вебинаре расскажем, как действовать на опережение и не допустить масштабных взломов с крупными финансовыми потерями. Подключайтесь 7 октября, чтобы узнать: Как утечки открывают хакерам двери в инфраструктуру; Как отслеживать сливы с помощью сервиса мониторинга Solar AURA; Как базы утечек могут быть использованы для пентестов. Присоединяйтесь, чтобы научиться закрывать уязвимости раньше, чем их используют хакеры. К тому же мы разыграем три билета на SOC Forum 2025 — главное событие этой осени в российском ИБ-мире. Зарегистрироваться #реклама 16+ rt-solar.ru О рекламодателе

Задача: 359. Logger Rate Limiter Сложность: easy Создайте систему логирования, которая получает поток сообщений вместе с их временными метками. Каждое уникальное сообщение должно печататься не чаще, чем раз в 10 секунд (то есть, сообщение, напечатанное во временной метке t, предотвратит печать других идентичных сообщений до временной метки t + 10). Все сообщения будут приходить в хронологическом порядке. Несколько сообщений могут поступить в одно и то же время. Реализуйте класс Logger: Logger() Инициализирует объект логгера. bool shouldPrintMessage(int timestamp, string message) Возвращает true, если сообщение должно быть напечатано в данной временной метке, в противном случае возвращает false. Пример:

Input
["Logger", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage"]
[[], [1, "foo"], [2, "bar"], [3, "foo"], [8, "bar"], [10, "foo"], [11, "foo"]]
Output
[null, true, true, false, false, false, true]

Explanation
Logger logger = new Logger();
logger.shouldPrintMessage(1, "foo");  // return true, next allowed timestamp for "foo" is 1 + 10 = 11
logger.shouldPrintMessage(2, "bar");  // return true, next allowed timestamp for "bar" is 2 + 10 = 12
logger.shouldPrintMessage(3, "foo");  // 3 < 11, return false
logger.shouldPrintMessage(8, "bar");  // 8 < 12, return false
logger.shouldPrintMessage(10, "foo"); // 10 < 11, return false
logger.shouldPrintMessage(11, "foo"); // 11 >= 11, return true, next allowed timestamp for "foo" is 11 + 10 = 21

👨‍💻 Алгоритм: 1⃣Инициализируем хеш-таблицу/словарь для хранения сообщений вместе с временной меткой. 2⃣При поступлении нового сообщения оно может быть напечатано при выполнении одного из следующих условий: Мы никогда раньше не видели это сообщение. Мы видели это сообщение ранее, и оно было напечатано более 10 секунд назад. 3⃣В обоих случаях обновляем запись, связанную с сообщением в хеш-таблице, с последней временной меткой. 😎 Решение:

class Logger {
  private HashMap<String, Integer> msgDict;

  public Logger() {
    msgDict = new HashMap<String, Integer>();
  }

  public boolean shouldPrintMessage(int timestamp, String message) {

    if (!this.msgDict.containsKey(message)) {
      this.msgDict.put(message, timestamp);
      return true;
    }

    Integer oldTimestamp = this.msgDict.get(message);
    if (timestamp - oldTimestamp >= 10) {
      this.msgDict.put(message, timestamp);
      return true;
    } else
      return false;
  }
}

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

Тариф, с которым хватит на всё 50 ГБ и безлимитные минуты за 390 ₽ в месяц, если перенесете номер в Т-Мобайл до 30 сентября Узнать больше #реклама tbank.ru О рекламодателе

Задача: 187. Repeated DNA Sequences Сложность: medium ДНК состоит из серии нуклеотидов, обозначаемых как 'A', 'C', 'G' и 'T'. Например, "ACGAATTCCG" — это последовательность ДНК. При изучении ДНК полезно определять повторяющиеся последовательности внутри молекулы ДНК. Дана строка s, представляющая последовательность ДНК. Верните все последовательности длиной 10 букв (подстроки), которые встречаются более одного раза в молекуле ДНК. Ответ можно возвращать в любом порядке. Пример:

Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC","CCCCCAAAAA"]

👨‍💻 Алгоритм: 1⃣Перебираем начальные позиции последовательности от 1 до 𝑁−𝐿, где 𝑁 — длина строки, а 𝐿 — длина подстроки (в данном случае 10): Если начальная позиция 𝑠𝑡𝑎𝑟𝑡==0, вычисляем хеш первой последовательности 𝑠[0:𝐿]. В противном случае вычисляем скользящий хеш из предыдущего значения хеша. 2⃣Проверяем хеш в хешсете: Если хеш уже существует в хешсете, значит, мы нашли повторяющуюся последовательность, и пора обновить вывод. В противном случае добавляем хеш в хешсет. 3⃣Возвращаем список вывода, содержащий все повторяющиеся последовательности. 😎 Решение:

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        int L = 10, n = s.length();
        if (n <= L) return new ArrayList();
        int a = 4, aL = (int) Math.pow(a, L);
        Map<Character, Integer> toInt = new HashMap() {
            {
                put('A', 0);
                put('C', 1);
                put('G', 2);
                put('T', 3);
            }
        };
        int[] nums = new int[n];
        for (int i = 0; i < n; ++i) nums[i] = toInt.get(s.charAt(i));

        int h = 0;
        Set<Integer> seen = new HashSet();
        Set<String> output = new HashSet();
        for (int start = 0; start < n - L + 1; ++start) {
            if (start != 0) h = h * a -
            nums[start - 1] * aL +
            nums[start + L - 1];
            else for (int i = 0; i < L; ++i) h = h * a + nums[i];
            if (seen.contains(h)) output.add(s.substring(start, start + L));
            seen.add(h);
        }
        return new ArrayList<String>(output);
    }
}

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

Международные расчёты по ставке — от 0,05% за платёж Торгуйте с Китаем и другими странами по самой выгодной ставке — от 0,05% за платёж. Важная новость для импортёров и экспортёров перед новым деловым сезоном: Альфа-Банк улучшил условия международных расчётов для бизнеса. Это значит, что сделки стали выгоднее, особенно для среднего и крупного бизнеса: чем больше будет сумма сделки — тем ниже комиссия. Например, для контрактов от 50 000 ¥ тариф составит всего 0,05% — в разы меньше среднего по рынку. Предложение подойдёт для расчётов с партнёрами из Китая, Беларуси, Вьетнама, Индии, Казахстана и других стран. А ещё Альфа-Банк обеспечит полное сопровождение сделки на всех этапах. Персональный валютный контролёр поможет избежать нарушений, а менеджер с опытом в ВЭД подскажет по любым вопросам. Перейти на сайт Финансовые услуги оказывает: АО "Альфа-Банк". #реклама alfabank.ru О рекламодателе

Задача: 605. Can Place Flowers Сложность: easy У вас есть длинная клумба, на которой некоторые участки засажены, а некоторые нет. Однако цветы нельзя сажать на соседних участках. Дан целочисленный массив flowerbed, содержащий 0 и 1, где 0 означает пустой участок, а 1 — занятый участок, и целое число n. Верните true, если n новых цветов можно посадить на клумбе, не нарушая правила о соседних цветах, и false в противном случае. Пример:

Input: flowerbed = [1,0,0,0,1], n = 1
Output: true

👨‍💻 Алгоритм: 1⃣Решение очень простое. Мы можем определить максимальное количество дополнительных цветов, count, которые можно посадить для данного расположения клумбы. Для этого мы проходим по всем элементам массива flowerbed и находим те элементы, которые равны 0 (означает пустую позицию). 2⃣Для каждого такого элемента проверяем, пусты ли обе его соседние позиции. Если да, мы можем посадить цветок в текущей позиции, не нарушая правило соседних цветов. Для первого и последнего элементов не нужно проверять предыдущие и следующие соседние позиции соответственно. 3⃣Если полученное количество count больше или равно n, требуемому количеству цветов для посадки, мы можем посадить n цветов на пустые места, иначе - нет. 😎 Решение:

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int count = 0;
        for (int i = 0; i < flowerbed.length; i++) {
            if (flowerbed[i] == 0) {
                boolean emptyLeft = i == 0 || flowerbed[i - 1] == 0;
                boolean emptyRight = i == flowerbed.length - 1 || flowerbed[i + 1] == 0;
                if (emptyLeft && emptyRight) {
                    flowerbed[i] = 1;
                    count++;
                }
            }
        }
        return count >= n;
    }
}

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

Задача: 384. Shuffle an Array Сложность: medium Дан целочисленный массив nums. Разработайте алгоритм для случайного перемешивания массива. Все перестановки массива должны быть равновероятны в результате перемешивания. Реализуйте класс Solution: Solution(int[] nums): Инициализирует объект целочисленным массивом nums. int[] reset(): Сбрасывает массив в его исходную конфигурацию и возвращает его. int[] shuffle(): Возвращает случайное перемешивание массива. Пример:

Input: ransomNote = "a", magazine = "b"
Output: false

👨‍💻 Алгоритм: 1⃣Алгоритм Фишера-Йейтса удивительно похож на решение грубой силы. На каждой итерации алгоритма мы генерируем случайное целое число между текущим индексом и последним индексом массива. 2⃣Затем мы меняем местами элементы на текущем индексе и выбранном индексе. Это симулирует выбор (и удаление) элемента из "шляпы", так как следующий диапазон, из которого мы выбираем случайный индекс, не будет включать последний обработанный элемент. 3⃣Один небольшой, но важный момент заключается в том, что возможно поменять элемент сам с собой - в противном случае некоторые перестановки массива были бы более вероятны, чем другие. 😎 Решение:

class Solution {
    private int[] array;
    private int[] original;

    Random rand = new Random();

    private int randRange(int min, int max) {
        return rand.nextInt(max - min) + min;
    }

    private void swapAt(int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public Solution(int[] nums) {
        array = nums;
        original = nums.clone();
    }
    
    public int[] reset() {
        array = original;
        original = original.clone();
        return original;
    }
    
    public int[] shuffle() {
        for (int i = 0; i < array.length; i++) {
            swapAt(i, randRange(i, array.length));
        }
        return array;
    }
}

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

⚡️ Айтишник из «VISION» скупил топовые айти-курсы и выложил гигабайты материалов к себе Каждый найдет что-то по душе: 903 ГБ — Python 812 ГБ — Frontend 978 ГБ — C, C++ 804 ГБ — Java 432 ГБ — C#, GameDev 411 ГБ — SQL & БД 309 ГБ — DevOps 998 ГБ — ИБ & Хакинг 773 ГБ — Kotlin, Swift 189 ГБ — PHP 201 ГБ — GoLang 170 ГБ — Rust 167 ГБ — QA-Тестирование 310 ГБ — 1C + Лицензии 495 ГБ — Машинное обучение 704 ГБ — Аналитика Данных 991 ГБ — Дизайн Материалы в закрепе, постоянно пополняются👆🏻

Такси для бизнеса. Яндекс Go Оптимизируйте свои расходы и повысьте эффективность бизнеса с Яндекс Go Узнать больше #реклама business.go.yandex О рекламодателе

Задача: 461. Hamming Distance Сложность: easy Расстояние Хэмминга между двумя целыми числами — это количество позиций, в которых соответствующие биты различны. Даны два целых числа x и y, верните расстояние Хэмминга между ними. Пример:

Input: x = 3, y = 1
Output: 1

👨‍💻 Алгоритм: 1⃣Во-первых, стоит упомянуть, что в большинстве (или, по крайней мере, во многих) языков программирования есть встроенные функции для подсчета битов, установленных в 1. Если вам нужно решить такую задачу в реальном проекте, то лучше использовать эти функции, чем изобретать велосипед. 2⃣Однако, поскольку это задача на LeetCode, использование встроенных функций можно сравнить с "реализацией LinkedList с использованием LinkedList". Поэтому рассмотрим также несколько интересных ручных алгоритмов для подсчета битов. 3⃣Пошаговый подсчет битов: Выполните побитовое XOR между x и y. Инициализируйте счетчик bitCount = 0. Пока число не равно нулю: Если текущий бит равен 1, увеличьте bitCount. Сдвиньте число вправо на один бит. Возвращайте bitCount. 😎 Решение:

class Solution {
    public int hammingDistance(int x, int y) {
        return Integer.bitCount(x ^ y);
    }
}

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

Задача: 1246. Palindrome Removal Сложность: hard Вам дан целочисленный массив arr. За один ход вы можете выбрать палиндромный подмассив arr[i], arr[i + 1], ..., arr[j], где i <= j, и удалить этот подмассив из данного массива. Обратите внимание, что после удаления подмассива элементы слева и справа от него перемещаются, чтобы заполнить пробел, образовавшийся в результате удаления. Верните минимальное количество ходов, необходимое для удаления всех чисел из массива. Пример:

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

👨‍💻 Алгоритм: 1⃣Базовый случай: Если подмассив состоит из одного элемента, то его удаление займет 1 ход, поэтому dp[i][i] = 1. 2⃣Рекурсивный случай: Если arr[i] == arr[j], то мы можем удалить их в одном ходе, если подмассив arr[i+1...j-1] можно удалить за dp[i+1][j-1] ходов, тогда dp[i][j] = dp[i+1][j-1] (если удалим подмассив arr[i+1...j-1] и затем удалим arr[i] и arr[j]). 3⃣В противном случае, минимальное количество ходов для удаления подмассива arr[i...j] будет равно 1 + минимум ходов для удаления каждого из подмассивов arr[i...k] и arr[k+1...j], где i <= k < j. То есть, dp[i][j] = min(dp[i][k] + dp[k+1][j]) для всех k от i до j-1. 😎 Решение:

public class Solution {
    public int minMovesToDelete(int[] arr) {
        int n = arr.length;
        int[][] dp = new int[n][n];

        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }

        for (int length = 2; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                if (arr[i] == arr[j]) {
                    dp[i][j] = length > 2 ? dp[i + 1][j - 1] : 1;
                } else {
                    dp[i][j] = Integer.MAX_VALUE;
                    for (int k = i; k < j; k++) {
                        dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j]);
                    }
                }
            }
        }

        return dp[0][n - 1];
    }
}

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

Открой мощь новых MSI с GeForce RTX 50 Серия NVIDIA GeForce RTX 50 в ноутбуках MSI — это квантовый скачок в мире мощности. Игры на максималках, 3D-рендер без ожиданий, монтаж видео в реальном времени и искусственный интеллект, работающий с небывалой скоростью. Эта техника создана не просто для задач — она их уничтожает. Будь в центре производительности нового поколения. MSI с RTX 50 — когда ты не хочешь ждать, а действуешь. Узнать больше #реклама msi.gm О рекламодателе

Задача: 903. Valid Permutations for DI Sequence Сложность: hard Вам дана строка s длины n, где s[i] либо: 'D' означает убывание, либо 'I' означает возрастание. Перестановка perm из n + 1 целых чисел всех целых чисел в диапазоне [0, n] называется допустимой, если для всех допустимых i: если s[i] == 'D', то perm[i] > perm[i + 1], а если s[i] == 'I', то perm[i] < perm[i + 1]. Верните количество допустимых перестановок perm. Поскольку ответ может быть большим, верните его по модулю 109 + 7. Пример:

Input: s = "DID"
Output: 5

👨‍💻 Алгоритм: 1⃣Создать двумерный массив dp, где dp[i][j] представляет количество допустимых перестановок длины i, оканчивающихся на j. 2⃣Заполнить массив dp, учитывая условия возрастания и убывания из строки s. 3⃣Вернуть сумму dp[n][j] для всех j, что даст количество допустимых перестановок длины n + 1. 😎 Решение:

class Solution {
    public int numPermsDISequence(String s) {
        int MOD = 1_000_000_007;
        int n = s.length();
        int[][] dp = new int[n + 1][n + 1];
        dp[0][0] = 1;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= i; j++) {
                if (s.charAt(i - 1) == 'D') {
                    for (int k = j; k < i; k++) {
                        dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD;
                    }
                } else {
                    for (int k = 0; k < j; k++) {
                        dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD;
                    }
                }
            }
        }
        
        int result = 0;
        for (int j = 0; j <= n; j++) {
            result = (result + dp[n][j]) % MOD;
        }
        
        return result;
    }
}

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

Задача: 491. Non-decreasing Subsequences Сложность: medium Дан массив целых чисел nums. Верните все возможные различные неубывающие подпоследовательности данного массива, содержащие как минимум два элемента. Вы можете вернуть ответ в любом порядке. Пример:

Input: nums = [4,6,7,7]
Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

👨‍💻 Алгоритм: 1⃣Инициализация и запуск функции обратного отслеживания Создайте множество для хранения результатов. Создайте список для хранения текущей последовательности. Запустите рекурсивную функцию обратного отслеживания с начальным индексом 0. 2⃣Функция обратного отслеживания Если текущий индекс равен длине массива, проверьте длину текущей последовательности и добавьте её в результат, если она содержит не менее двух элементов. Если текущая последовательность остаётся неубывающей после добавления текущего элемента массива, добавьте этот элемент, вызовите рекурсивную функцию для следующего индекса и удалите элемент из последовательности (обратное отслеживание). Всегда вызывайте рекурсивную функцию для следующего индекса без добавления текущего элемента. 3⃣Возврат результата После завершения всех рекурсивных вызовов преобразуйте множество результатов в список и верните его. 😎 Решение:

class Solution {
    private void backtrack(int[] nums, int index, List<Integer> sequence,
            Set<List<Integer>> result) {
        if (index == nums.length) {
            if (sequence.size() >= 2) {
                result.add(new ArrayList<>(sequence));
            }
            return;
        }
        if (sequence.isEmpty() ||
                sequence.get(sequence.size() - 1) <= nums[index]) {
            sequence.add(nums[index]);
            backtrack(nums, index + 1, sequence, result);
            sequence.remove(sequence.size() - 1);
        }
        backtrack(nums, index + 1, sequence, result);
    }

    public List<List<Integer>> findSubsequences(int[] nums) {
        Set<List<Integer>> result = new HashSet<List<Integer>>();
        List<Integer> sequence = new ArrayList<Integer>();
        backtrack(nums, 0, sequence, result);
        return new ArrayList(result);
    }
}

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