Java | LeetCode

Задача: 1425. Constrained Subsequence Sum Сложность: hard Дан целочисленный массив nums и целое число k, верните максимальную сумму непустой подпоследовательности этого массива, такую, что для любых двух последовательных целых чисел в подпоследовательности nums[i] и nums[j], где i < j, выполняется условие j - i <= k. Подпоследовательность массива получается путем удаления некоторого количества элементов (может быть ноль) из массива, оставляя оставшиеся элементы в их исходном порядке. Пример:

    
        Input: nums = [10,2,-10,5,20], k = 2
Output: 37
Explanation: The subsequence is [10, 2, 5, 20].{}
    

👨‍💻 Алгоритм: 1⃣Инициализируйте очередь queue и массив dp той же длины, что и nums. 2⃣Итерируйте i по индексам nums: Если i минус первый элемент queue больше k, удалите элемент из начала queue. Установите dp[i] как dp[queue.front()] + nums[i]. Если queue пуст, используйте 0 вместо dp[queue.front()]. Пока dp[queue.back()] меньше dp[i], удаляйте элементы с конца queue. Если dp[i] > 0, добавьте i в конец queue. 3⃣Верните максимальное значение в массиве dp. 😎 Решение:

    
        class Solution {
    public int constrainedSubsetSum(int[] nums, int k) {
        Deque<Integer> queue = new ArrayDeque<>();
        int dp[] = new int[nums.length];
        
        for (int i = 0; i < nums.length; i++) {
            if (!queue.isEmpty() && i - queue.peek() > k) {
                queue.poll();
            }
            
            dp[i] = (!queue.isEmpty() ? dp[queue.peek()] : 0) + nums[i];
            while (!queue.isEmpty() && dp[queue.peekLast()] < dp[i]) {
                queue.pollLast();
            }
            
            if (dp[i] > 0) {
                queue.offer(i);
            }
        }
        
        int ans = Integer.MIN_VALUE;
        for (int num : dp) {
            ans = Math.max(ans, num);
        }
        
        return ans;
    }
}{}
    

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

Задача: 420. Strong Password Checker Сложность: hard Пароль считается надежным, если выполняются следующие условия: в нем не менее 6 и не более 20 символов. он содержит не менее одной строчной буквы, не менее одной заглавной буквы и не менее одной цифры. он не содержит трех повторяющихся символов подряд (например, "Baaabb0" - слабый, а "Baaba0" - сильный). Учитывая строку пароля, верните минимальное количество шагов, необходимых для того, чтобы сделать пароль сильным. Если пароль уже сильный, верните 0. За один шаг можно: вставить один символ в пароль, удалить один символ из пароля или заменить один символ пароля другим символом. Пример:

    
        Input: password = "a"
Output: 5{}
    

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

    
        public class Solution {
    public int strongPasswordChecker(String s) {
        int n = s.length();
        boolean hasLower = false, hasUpper = false, hasDigit = false;
        int repeatCount = 0;
        
        for (int i = 0; i < n;) {
            if (Character.isLowerCase(s.charAt(i))) hasLower = true;
            if (Character.isUpperCase(s.charAt(i))) hasUpper = true;
            if (Character.isDigit(s.charAt(i))) hasDigit = true;
            
            int start = i;
            while (i < n && s.charAt(i) == s.charAt(start)) {
                i++;
            }
            repeatCount += (i - start) / 3;
        }
        
        int missingTypes = (hasLower ? 0 : 1) + (hasUpper ? 0 : 1) + (hasDigit ? 0 : 1);
        
        if (n < 6) {
            return Math.max(missingTypes, 6 - n);
        } else if (n <= 20) {
            return Math.max(missingTypes, repeatCount);
        } else {
            int excessChars = n - 20;
            int overLenReduction = 0;
            for (int i = 2; i < n && excessChars > 0; i++) {
                if (i % 3 == 2 && s.charAt(i) == s.charAt(i - 1) && s.charAt(i) == s.charAt(i - 2)) {
                    overLenReduction++;
                    excessChars--;
                }
            }
            repeatCount -= overLenReduction;
            return (n - 20) + Math.max(missingTypes, repeatCount);
        }
    }
}{}
    

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

Задача: 1150. Check If a Number Is Majority Element in a Sorted Array Сложность: easy Дан целочисленный массив nums, отсортированный в неубывающем порядке, и целое число target. Верните true, если target является элементом большинства, или false в противном случае. Элемент большинства в массиве nums — это элемент, который встречается в массиве более чем nums.length / 2 раз. Пример:

    
        Input: nums = [2,4,5,5,5,5,5,6,6], target = 5
Output: true
Explanation: The value 5 appears 5 times and the length of the array is 9.
Thus, 5 is a majority element because 5 > 9/2 is true.{}
    

👨‍💻 Алгоритм: 1⃣Инициализация переменной count: Инициализируйте переменную count значением 0.. 2⃣Итерация по списку nums: Пройдите по каждому элементу списка nums. Если элемент num равен target, увеличьте значение переменной count. 3⃣Проверка условия мажоритарного элемента: Если count больше чем половина длины списка nums, верните true. В противном случае верните false. 😎 Решение:

    
        class Solution {
    public boolean isMajorityElement(int[] nums, int target) {
        int count = 0;
        for (int num : nums) {
            count = num == target ? count + 1 : count;
        }
        
        return count > nums.length / 2;
    }
}{}
    

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

Задача: 844. Backspace String Compare Сложность: easy Даны две строки s и t, верните true, если они равны после ввода в пустые текстовые редакторы. Символ '#' означает клавишу backspace. Обратите внимание, что после нажатия backspace на пустом тексте, текст останется пустым. Пример:

    
        Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both s and t become "ac".{}
    

👨‍💻 Алгоритм: 1⃣Пройдите по строкам s и t с конца, учитывая символы '#' как backspace и пропуская соответствующие символы. 2⃣Сравнивайте текущие символы из обеих строк, пропуская символы, которые должны быть удалены. 3⃣Если все соответствующие символы совпадают и строки эквивалентны после всех backspace операций, верните true; в противном случае верните false. 😎 Решение:

    
        class Solution {
    public boolean backspaceCompare(String S, String T) {
        int i = S.length() - 1, j = T.length() - 1;
        int skipS = 0, skipT = 0;

        while (i >= 0 || j >= 0) {
            while (i >= 0) {
                if (S.charAt(i) == '#') {skipS++; i--;}
                else if (skipS > 0) {skipS--; i--;}
                else break;
            }
            while (j >= 0) {
                if (T.charAt(j) == '#') {skipT++; j--;}
                else if (skipT > 0) {skipT--; j--;}
                else break;
            }
            if (i >= 0 && j >= 0 && S.charAt(i) != T.charAt(j))
                return false;
            if ((i >= 0) != (j >= 0))
                return false;
            i--; j--;
        }
        return true;
    }
}{}
    

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

Задача: 227. Basic Calculator II Сложность: medium Дана строка s, представляющая выражение. Вычислите это выражение и верните его значение. Целочисленное деление должно округляться к нулю. Вы можете предположить, что данное выражение всегда является допустимым. Все промежуточные результаты будут находиться в диапазоне [-2^31, 2^31 - 1]. Примечание: Запрещено использовать какие-либо встроенные функции, которые вычисляют строки как математические выражения, такие как eval(). Пример:

    
        Input: s = "3+2*2"
Output: 7{}
    

👨‍💻 Алгоритм: 1⃣Вместо использования стека, используем переменную lastNumber для отслеживания значения последнего вычисленного выражения. 2⃣Если операция сложения (+) или вычитания (-), добавляем lastNumber к результату вместо того, чтобы помещать его в стек. Текущее значение currentNumber будет обновлено на lastNumber для следующей итерации. 3⃣Если операция умножения (*) или деления (/), вычисляем выражение lastNumber * currentNumber и обновляем lastNumber с результатом выражения. Это значение будет добавлено к результату после сканирования всей строки. 😎 Решение:

    
        class Solution {
    public int calculate(String s) {
        int length = s.length();
        if (length == 0) return 0;
        int currentNumber = 0, lastNumber = 0, result = 0;
        char sign = '+';
        
        for (int i = 0; i < length; i++) {
            char currentChar = s.charAt(i);
            if (Character.isDigit(currentChar)) {
                currentNumber = (currentNumber * 10) + (currentChar - '0');
            }
            if (!Character.isDigit(currentChar) && !Character.isWhitespace(currentChar) || i == length - 1) {
                if (sign == '+' || sign == '-') {
                    result += lastNumber;
                    lastNumber = (sign == '+') ? currentNumber : -currentNumber;
                } else if (sign == '*') {
                    lastNumber = lastNumber * currentNumber;
                } else if (sign == '/') {
                    lastNumber = lastNumber / currentNumber;
                }
                sign = currentChar;
                currentNumber = 0;
            }
        }
        result += lastNumber;
        return result;  
    }
}{}
    

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

Задача: 202. Happy Number Сложность: easy Напишите алгоритм для определения, является ли число n счастливым. Счастливое число определяется следующим процессом: Начиная с любого положительного целого числа, замените число суммой квадратов его цифр. Повторяйте процесс, пока число не станет равным 1 (где оно и останется), или пока оно бесконечно не будет циклически повторяться в цикле, который не включает 1. Те числа, для которых этот процесс завершается 1, являются счастливыми. Верните true, если n является счастливым числом, и false, если нет. Пример:

    
        Input: n = 2
Output: false{}
    

👨‍💻 Алгоритм: 1⃣Для заданного числа n определите следующее число в последовательности: используйте операторы деления и взятия остатка для последовательного извлечения цифр из числа, пока не закончатся все цифры. Каждую извлеченную цифру возводите в квадрат и суммируйте полученные значения. Это техника "последовательного извлечения цифр" является полезным инструментом для решения множества задач. 2⃣Отслеживайте цепочку чисел и определяйте, не вошли ли вы в цикл, используя структуру данных HashSet. Каждый раз, генерируя следующее число в цепочке, проверяйте, присутствует ли оно уже в HashSet. 3⃣Если числа нет в HashSet, добавьте его туда. Если число уже есть в HashSet, это означает, что вы находитесь в цикле, и следует вернуть false. HashSet используется вместо Vector, List или Array, потому что проверка присутствия числа в HashSet занимает время O(1), тогда как в других структурах данных это займет время O(n). Правильный выбор структур данных является ключевым элементом решения подобных задач. 😎 Решение:

    
        class Solution {
    private int getNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            int d = n % 10;
            n = n / 10;
            totalSum += d * d;
        }
        return totalSum;
    }

    public boolean isHappy(int n) {
        Set<Integer> seen = new HashSet<>();
        while (n != 1 && !seen.contains(n)) {
            seen.add(n);
            n = getNext(n);
        }
        return n == 1;
    }
}{}
    

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

Задача: №21. Merge Two Sorted Lists Сложность: easy Вам даны заголовки двух отсортированных связанных списков list1 и list2. Объедините их в один отсортированный список, сшивая существующие узлы. Верните заголовок нового объединенного списка. Пример:

    
        Input: list1 = [1,2,4], list2 = [1,3,4] Output: [1,1,2,3,4,4]{}
    

👨‍💻 Алгоритм: 1⃣Если один из списков пуст — возвращаем второй как результат. 2⃣Сравниваем значения текущих узлов списков: выбираем меньший и рекурсивно вызываем mergeTwoLists для оставшейся части. 3⃣Связываем меньший узел с результатом рекурсивного вызова и возвращаем его как текущий. 😎 Решение:

    
        /**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                list1.next = mergeTwoLists(list1.next, list2);
                return list1;
            } else {
                list2.next = mergeTwoLists(list1, list2.next);
                return list2;
            }
        }
        return list1 != null ? list1 : list2;
    }
}{}
    

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

Задача: 41. First Missing Positive сложность: hard Дан неотсортированный массив целых чисел nums. Верните наименьшее положительное целое число, которого нет в массиве nums. Необходимо реализовать алгоритм, который работает за время O(n) и использует O(1) дополнительной памяти. Пример:

    
        Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.{}
    

👨‍💻 Алгоритм: 1⃣Инициализировать переменную n длиной массива nums. Создать массив seen размером n + 1. Отметить элементы в массиве nums как просмотренные в массиве seen. Для каждого числа num в массиве nums, если num больше 0 и меньше или равно n, установить seen[num] в значение true. 2⃣Найти наименьшее недостающее положительное число: Проитерировать от 1 до n, и если seen[i] не равно true, вернуть i как наименьшее недостающее положительное число. 3⃣Если массив seen содержит все элементы от 1 до n, вернуть n + 1 как наименьшее недостающее положительное число. 😎 Решение:

    
        class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        boolean[] seen = new boolean[n + 1];

        for (int num : nums) {
            if (num > 0 && num <= n) {
                seen[num] = true;
            }
        }

        for (int i = 1; i <= n; i++) {
            if (!seen[i]) {
                return i;
            }
        }

        return n + 1;
    }
}{}
    

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

Задача: 1406. Stone Game III Сложность: hard Алиса и Боб продолжают свои игры с кучами камней. Камни расположены в ряд, и каждый камень имеет ассоциированное значение, которое представлено целым числом в массиве stoneValue. Алиса и Боб ходят по очереди, начиная с Алисы. В свой ход каждый игрок может взять 1, 2 или 3 камня из первых оставшихся камней в ряду. Счет каждого игрока равен сумме значений взятых камней. Изначально счет каждого игрока равен 0. Цель игры — закончить с наивысшим счетом, и победителем становится игрок с наивысшим счетом, при этом возможна ничья. Игра продолжается, пока все камни не будут взяты. Предположим, что Алиса и Боб играют оптимально. Верните "Alice", если Алиса выиграет, "Bob", если выиграет Боб, или "Tie", если они закончат игру с одинаковым счетом. Пример:

    
        Input: stoneValue = [1,2,3,7]
Output: "Bob"
Explanation: Alice will always lose. Her best move will be to take three piles and the score become 6. Now the score of Bob is 7 and Bob wins.{}
    

👨‍💻 Алгоритм: 1⃣Инициализируйте массив dp размером n+1 и установите dp[n] в 0. 2⃣Итеративно обновляйте dp[i] для всех i от n-1 до 0, вычисляя максимальную разницу в баллах, которые могут получить игроки при оптимальной игре. 3⃣Определите победителя, сравнивая dp[0] с 0: если больше, победит Алиса; если меньше, победит Боб; если равно, будет ничья. 😎 Решение:

    
        class Solution {
    public String stoneGameIII(int[] stoneValue) {
        int n = stoneValue.length;
        int[] dp = new int [n + 1];
        for (int i = n - 1; i >= 0; i--) {
            dp[i] = stoneValue[i] - dp[i + 1];
            if (i + 2 <= n) {
                dp[i] = Math.max(dp[i], stoneValue[i] + stoneValue[i + 1] - dp[i + 2]);
            }
            if (i + 3 <= n) {
                dp[i] = Math.max(dp[i], stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2] - dp[i + 3]);
            }
        }
        if (dp[0] > 0) {
            return "Alice";
        }
        if (dp[0] < 0) {
            return "Bob";
        }
        return "Tie";
    }
}{}
    

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

Задача: 1305. All Elements in Two Binary Search Trees Сложность: medium Даны два бинарных дерева поиска root1 и root2. Вернуть список, содержащий все целые числа из обоих деревьев, отсортированные в порядке возрастания. Пример:

    
        Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]{}
    

👨‍💻 Алгоритм: 1⃣Выполните итеративный обход в порядке возрастания обоих деревьев параллельно. 2⃣На каждом шаге добавляйте наименьшее доступное значение в выходной список. 3⃣Верните выходной список. 😎 Решение:

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

class Solution {
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        ArrayDeque<TreeNode> stack1 = new ArrayDeque<>(), stack2 = new ArrayDeque<>();
        List<Integer> output = new ArrayList<>();

        while (root1 != null || root2 != null || !stack1.isEmpty() || !stack2.isEmpty()) {
            while (root1 != null) {
                stack1.push(root1);
                root1 = root1.left;
            }
            while (root2 != null) {
                stack2.push(root2);
                root2 = root2.left;
            }
            if (stack2.isEmpty() || (!stack1.isEmpty() && stack1.peek().val <= stack2.peek().val)) {
                root1 = stack1.pop();
                output.add(root1.val);
                root1 = root1.right;
            } else {
                root2 = stack2.pop();
                output.add(root2.val);
                root2 = root2.right;
            }
        }
        return output;
    }
}{}
    

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