Java | LeetCode

Задача: 118. Pascal's Triangle
Сложность: easy

Дано целое число numRows. Верните первые numRows строк треугольника Паскаля.

В треугольнике Паскаля каждое число является суммой двух чисел, непосредственно расположенных над ним, как показано:

Пример:

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

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

1⃣Инициализируем список triangle, в который добавим первую строку [1].

2⃣Для каждой новой строки берём предыдущую строку и создаём новую, начиная и заканчивая единицей. Все промежуточные элементы считаем как сумму двух элементов сверху: prevRow[j - 1] + prevRow[j].

3⃣Добавляем полученную строку в треугольник. Повторяем процесс, пока не соберём все numRows.

😎 Решение:

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> triangle = new ArrayList<List<Integer>>();
        triangle.add(new ArrayList<>());
        triangle.get(0).add(1);

        for (int rowNum = 1; rowNum < numRows; rowNum++) {
            List<Integer> row = new ArrayList<>();
            List<Integer> prevRow = triangle.get(rowNum - 1);
            row.add(1);

            for (int j = 1; j < rowNum; j++) {
                row.add(prevRow.get(j - 1) + prevRow.get(j));
            }

            row.add(1);
            triangle.add(row);
        }

        return triangle;
    }
}

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

Задача: 405. Convert a Number to Hexadecimal
Сложность: easy

Если задано целое число num, верните строку, представляющую его шестнадцатеричное представление. Для отрицательных целых чисел используется метод дополнения до двух. Все буквы в строке ответа должны быть строчными, и в ответе не должно быть никаких ведущих нулей, кроме самого нуля. Примечание: Вам не разрешается использовать какие-либо встроенные библиотечные методы для непосредственного решения этой задачи.

Пример:

Input: num = 26
Output: "1a"

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

1⃣Определите, является ли число отрицательным. Если да, преобразуйте его в положительное число с помощью метода дополнения до двух. Для этого прибавьте к числу 2^32 и используйте битовую операцию И с маской 0xFFFFFFFF.

2⃣Создайте строку с шестнадцатеричными символами. Последовательно делите число на 16 и добавляйте соответствующий символ к результату, пока число не станет равным нулю.

3⃣Переверните строку результата и удалите ведущие нули, если они есть. Если строка пустая, верните "0".

😎 Решение:

public class Solution {
    public String toHex(int num) {
        if (num == 0) return "0";
        char[] hexChars = "0123456789abcdef".toCharArray();
        long n = num;
        if (num < 0) n += 1L << 32;
        StringBuilder result = new StringBuilder();
        while (n > 0) {
            result.append(hexChars[(int)(n % 16)]);
            n /= 16;
        }
        return result.reverse().toString();
    }
}

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

Задача: 146. LRU Cache
Сложность: medium

Реализуйте класс LRUCache:
LRUCache(int capacity) - инициализирует LRU-кэш с положительным размером capacity.
int get(int key) - возвращает значение по ключу, если ключ существует, в противном случае возвращает -1.
void put(int key, int value) - обновляет значение по ключу, если ключ существует. В противном случае добавляет пару ключ-значение в кэш. Если количество ключей превышает установленную емкость после этой операции, удаляет наименее недавно использованный ключ.

Функции get и put должны выполняться за среднее время O(1).

Пример:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

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

1⃣Метод добавления узла в конец связного списка (add):
Получите текущий узел в конце списка, это "реальный" хвост: tail.prev, обозначим его как previousEnd.
Вставьте node после previousEnd, установив previousEnd.next = node.
Настройте указатели узла: node.prev = previousEnd и node.next = tail.
Обновите tail.prev = node, делая node новым "реальным" хвостом списка.

2⃣Метод удаления узла из связного списка (remove):
Узел node должен быть удален из списка. Для этого определите узлы nextNode = node.next и prevNode = node.prev.
Чтобы удалить node, переназначьте prevNode.next = nextNode и nextNode.prev = prevNode, эффективно исключая node из списка.
Это превратит, например, последовательность A <-> B <-> C в A <-> C, где prevNode = A и nextNode = C.

3⃣Методы get и put:
get(int key): Проверьте, существует ли ключ в хэш-карте. Если нет, верните -1. Иначе, получите узел, связанный с ключом, переместите его в конец списка с помощью remove(node) и add(node). Верните node.val.
put(int key, int value): Если ключ уже существует, найдите соответствующий узел и удалите его методом remove. Создайте новый узел с key и value, добавьте его в хэш-карту и в конец списка методом add(node). Если размер кэша превышает установленную емкость после добавления, удалите самый редко используемый узел (который находится в голове списка после фиктивного узла head), затем удалите соответствующий ключ из хэш-карты.

😎 Решение:

class ListNode {
    int key;
    int val;
    ListNode next;
    ListNode prev;

    public ListNode(int key, int val) {
        this.key = key;
        this.val = val;
    }
}

class LRUCache {
    int capacity;
    Map<Integer, ListNode> dic;
    ListNode head;
    ListNode tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        dic = new HashMap<>();
        head = new ListNode(-1, -1);
        tail = new ListNode(-1, -1);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (!dic.containsKey(key)) {
            return -1;
        }

        ListNode node = dic.get(key);
        remove(node);
        add(node);
        return node.val;
    }

    public void put(int key, int value) {
        if (dic.containsKey(key)) {
            ListNode oldNode = dic.get(key);
            remove(oldNode);
        }

        ListNode node = new ListNode(key, value);
        dic.put(key, node);
        add(node);

        if (dic.size() > capacity) {
            ListNode nodeToDelete = head.next;
            remove(nodeToDelete);
            dic.remove(nodeToDelete.key);
        }
    }

    public void add(ListNode node) {
        ListNode previousEnd = tail.prev;
        previousEnd.next = node;
        node.prev = previousEnd;
        node.next = tail;
        tail.prev = node;
    }

    public void remove(ListNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
}

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

Задача: 1672. Richest Customer Wealth
Сложность: easy

Вам дан целочисленный массив размером m x n под названием accounts, где accounts[i][j] — это сумма денег, которую i-й клиент имеет в j-м банке. Верните богатство самого богатого клиента.

Богатство клиента — это сумма денег, которую он имеет во всех своих банковских счетах. Самый богатый клиент — это клиент, который имеет максимальное богатство.

Пример:

Input: accounts = [[1,2,3],[3,2,1]]
Output: 6
Explanation:
1st customer has wealth = 1 + 2 + 3 = 6
2nd customer has wealth = 3 + 2 + 1 = 6
Both customers are considered the richest with a wealth of 6 each, so return 6.

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

1⃣Пройдите по всем клиентам в массиве accounts.

2⃣Для каждого клиента вычислите сумму денег на всех его банковских счетах и сравните её с максимальным богатством, найденным до этого момента.

3⃣Если текущее богатство больше максимального, обновите максимальное значение. Верните максимальное богатство.

😎 Решение:

class Solution {
    public int maximumWealth(int[][] accounts) {
        int maxWealthSoFar = 0;
        
        for (int[] account : accounts) {
            int currCustomerWealth = 0;
            for (int money : account) {
                currCustomerWealth += money;
            }
            maxWealthSoFar = Math.max(maxWealthSoFar, currCustomerWealth);
        }
        
        return maxWealthSoFar;
    }
}

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

Задача: 382. Linked List Random Node
Сложность: medium

Дан односвязный список, вернуть значение случайного узла из списка. Каждый узел должен иметь одинаковую вероятность быть выбранным.

Реализуйте класс Solution:

Solution(ListNode head) Инициализирует объект с головой односвязного списка head.
int getRandom() Выбирает узел случайным образом из списка и возвращает его значение. Все узлы списка должны иметь равные шансы быть выбранными.

Пример:

Input
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 3, 2, 2, 3]

Explanation
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // return 1
solution.getRandom(); // return 3
solution.getRandom(); // return 2
solution.getRandom(); // return 2
solution.getRandom(); // return 3
// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.

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

1⃣Реализуйте интерфейс init(head), который будет вызываться при создании объекта. Преобразуйте связанный список в массив для дальнейшего использования.

2⃣В интерфейсе init(head) преобразуйте переданный связанный список в массив, чтобы его можно было использовать позже.

3⃣Реализуйте функцию getRandom(), которая будет выбирать случайный элемент из массива, созданного на первом этапе.

😎 Решение:

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

class Solution {
    private List<Integer> range = new ArrayList<>();
    private Random random = new Random();

    public Solution(ListNode head) {
        while (head != null) {
            range.add(head.val);
            head = head.next;
        }
    }

    public int getRandom() {
        int pick = random.nextInt(range.size());
        return range.get(pick);
    }
}

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

Задача: 473. Matchsticks to Square
Сложность: medium

Дано целочисленный массив спичек, где matchsticks[i] — это длина i-й спички. Необходимо использовать все спички для создания одного квадрата. Нельзя ломать никакую спичку, но можно соединять их, при этом каждая спичка должна быть использована ровно один раз.

Вернуть true, если можно составить квадрат, и false в противном случае.

Пример:

Input: matchsticks = [1,1,2,2,2]
Output: true
Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.

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

1⃣Определяем рекурсивную функцию, которая принимает текущий индекс обрабатываемой спички и количество сторон квадрата, которые уже полностью сформированы. Базовый случай для рекурсии: если все спички использованы и сформировано 4 стороны, возвращаем True.

2⃣Для текущей спички рассматриваем 4 варианта: она может быть частью любой из сторон квадрата. Пробуем каждый из 4 вариантов, вызывая рекурсию для них.

3⃣Если какой-либо из рекурсивных вызовов возвращает True, возвращаем True, в противном случае возвращаем False.

😎 Решение:

import java.util.HashMap;
import java.util.Collections;

class Solution {
    public List<Integer> nums;
    public int[] sums;
    public int possibleSquareSide;

    public Solution() {
        this.sums = new int[4];
    }

    public boolean dfs(int index) {
        if (index == this.nums.size()) {
            return sums[0] == sums[1] && sums[1] == sums[2] && sums[2] == sums[3];
        }

        int element = this.nums.get(index);

        for(int i = 0; i < 4; i++) {
            if (this.sums[i] + element <= this.possibleSquareSide) {
                this.sums[i] += element;
                if (this.dfs(index + 1)) {
                    return true;
                }
                this.sums[i] -= element;
            }
        }

        return false;
    }

    public boolean makesquare(int[] nums) {
        if (nums == null || nums.length == 0) {
            return false;
        }

        int L = nums.length;
        int perimeter = 0;
        for(int i = 0; i < L; i++) {
            perimeter += nums[i];
        }

        this.possibleSquareSide =  perimeter / 4;
        if (this.possibleSquareSide * 4 != perimeter) {
            return false;
        }

        this.nums = Arrays.stream(nums).boxed().collect(Collectors.toList());
        Collections.sort(this.nums, Collections.reverseOrder());
        return this.dfs(0);
    }
}

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

Задача: 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 java.util.Arrays;

public class Solution {
    public int maxSumDivThree(int[] nums) {
        int totalSum = Arrays.stream(nums).sum();
        if (totalSum % 3 == 0) {
            return totalSum;
        }
        
        int mod1Min = Integer.MAX_VALUE;
        int mod2Min = Integer.MAX_VALUE;
        int[] mod1Min2 = new int[]{Integer.MAX_VALUE, Integer.MAX_VALUE};
        int[] mod2Min2 = new int[]{Integer.MAX_VALUE, Integer.MAX_VALUE};
        
        for (int num : nums) {
            if (num % 3 == 1) {
                if (num < mod1Min2[1]) {
                    mod1Min2[1] = num;
                    Arrays.sort(mod1Min2);
                }
            } else if (num % 3 == 2) {
                if (num < mod2Min2[1]) {
                    mod2Min2[1] = num;
                    Arrays.sort(mod2Min2);
                }
            }
        }
        
        int result = 0;
        if (totalSum % 3 == 1) {
            result = totalSum - mod1Min2[0];
            if (mod2Min2[0] != Integer.MAX_VALUE && mod2Min2[1] != Integer.MAX_VALUE) {
                result = Math.max(result, totalSum - mod2Min2[0] - mod2Min2[1]);
            }
        } else if (totalSum % 3 == 2) {
            result = totalSum - mod2Min2[0];
            if (mod1Min2[0] != Integer.MAX_VALUE && mod1Min2[1] != Integer.MAX_VALUE) {
                result = Math.max(result, totalSum - mod1Min2[0] - mod1Min2[1]);
            }
        }
        
        return result;
    }
}

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

Задача: 224. Basic Calculator
Сложность: hard

Дана строка s, представляющая собой допустимое выражение, реализуйте базовый калькулятор для его вычисления и верните результат вычисления.

Примечание: нельзя использовать встроенные функции, которые оценивают строки как математические выражения, такие как eval().

Пример:

Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23

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

1⃣Итерация строки выражения в обратном порядке:
Читаем выражение символ за символом, формируя операнды из нескольких цифр, если символ - цифра.
Сохраняем операнды в стек, как только встречаем нецифровой символ.

2⃣Обработка выражения внутри скобок:
Когда встречаем открывающую скобку '(', оцениваем выражение, удаляя операнды и операторы из стека до соответствующей закрывающей скобки.
Результат выражения помещаем обратно в стек.

3⃣Финальная оценка выражения:
Продолжаем процесс до получения финального результата.
Если стек не пуст после обработки всех символов, оцениваем оставшиеся элементы как одно финальное выражение.

😎 Решение:

class Solution {

    public int evaluateExpr(Stack<Object> stack) {
        
        if (stack.empty() || !(stack.peek() instanceof Integer)) {
            stack.push(0);
        }

        int res = (int) stack.pop();

        while (!stack.empty() && !((char) stack.peek() == ')')) {

            char sign = (char) stack.pop();

            if (sign == '+') {
                res += (int) stack.pop();
            } else {
                res -= (int) stack.pop();
            }
        }
        return res;
    }

    public int calculate(String s) {

        int operand = 0;
        int n = 0;
        Stack<Object> stack = new Stack<Object>();

        for (int i = s.length() - 1; i >= 0; i--) {

            char ch = s.charAt(i);

            if (Character.isDigit(ch)) {

                operand = (int) Math.pow(10, n) * (int) (ch - '0') + operand;
                n += 1;

            } else if (ch != ' ') {
                if (n != 0) {

                    stack.push(operand);
                    n = 0;
                    operand = 0;

                }
                if (ch == '(') {

                    int res = evaluateExpr(stack);
                    stack.pop();

                    stack.push(res);

                } else {
                    stack.push(ch);
                }
            }
        }

        if (n != 0) {
            stack.push(operand);
        }

        return evaluateExpr(stack);
    }
}

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

Задача: 480. Sliding Window Median
Сложность: hard

Медиана — это среднее значение в упорядоченном списке целых чисел. Если размер списка четный, среднего значения не существует, поэтому медианой считается среднее значение двух средних чисел.

Например, если arr = [2, 3, 4], медиана равна 3.
Например, если arr = [1, 2, 3, 4], медиана равна (2 + 3) / 2 = 2.5.

Вам дан целочисленный массив nums и целое число k. Существует скользящее окно размера k, которое перемещается от самого левого края массива до самого правого. Вы можете видеть только k чисел в окне. Каждый раз скользящее окно перемещается вправо на одну позицию.

Верните массив медиан для каждого окна в исходном массиве. Ответы с точностью до 10^-5 будут приниматься.

Пример:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000]
Explanation: 
Window position                Median
---------------                -----
[1  3  -1] -3  5  3  6  7        1
 1 [3  -1  -3] 5  3  6  7       -1
 1  3 [-1  -3  5] 3  6  7       -1
 1  3  -1 [-3  5  3] 6  7        3
 1  3  -1  -3 [5  3  6] 7        5
 1  3  -1  -3  5 [3  6  7]       6

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

1⃣Сохраняйте числа в контейнере окна размера k, выполняя следующие операции: Вставка входящего элемента. Удаление выходящего элемента.

2⃣ Отсортируйте окно, чтобы найти медианы. Вместо того чтобы каждый раз копировать и сортировать k последовательных элементов из входных данных, вставляйте и удаляйте по одному элементу при каждом сдвиге окна.

3⃣ Поддерживайте окно в отсортированном состоянии до и после операций вставки и удаления.

😎 Решение:

import java.util.*;

public class Solution {
    public double[] medianSlidingWindow(int[] nums, int k) {
        List<Double> medians = new ArrayList<>();

        for (int i = 0; i + k <= nums.length; i++) {
            int[] window = Arrays.copyOfRange(nums, i, i + k);
            Arrays.sort(window);

            if (k % 2 == 1) {
                medians.add((double) window[k / 2]);
            } else {
                medians.add((window[k / 2 - 1] + window[k / 2]) / 2.0);
            }
        }

        double[] result = new double[medians.size()];
        for (int i = 0; i < medians.size(); i++) {
            result[i] = medians.get(i);
        }

        return result;
    }
}

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

Задача: 1283. Find the Smallest Divisor Given a Threshold
Сложность: medium

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

Каждый результат деления округляется до ближайшего большего целого числа. (Например: 7/3 = 3 и 10/2 = 5).

Гарантируется, что решение существует.

Пример:

Input: nums = [1,2,5,9], threshold = 6
Output: 5
Explanation: We can get a sum to 17 (1+2+5+9) if the divisor is 1. 
If the divisor is 4 we can get a sum of 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2). 

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

1⃣Найдите максимальный элемент массива nums и сохраните его в переменной maxElement.

2⃣Итерация по всем делителям от 1 до maxElement:
Инициализируйте две переменные: sumOfDivisionResults для хранения суммы результатов деления и thresholdExceeded для указания, превышен ли порог.
Итерация по всем элементам массива nums: добавьте результат деления, округленного до ближайшего большего целого числа, в переменную sumOfDivisionResults. Если сумма превышает threshold, установите thresholdExceeded в true и прекратите итерацию по массиву nums.

3⃣Проверьте, был ли превышен порог:
Если порог не был превышен, текущий делитель является наименьшим делителем, поэтому верните его.
Если не найдено возможного делителя, верните -1.

😎 Решение:

class Solution {
    public int smallestDivisor(int[] nums, int threshold) {
        int maxElement = Arrays.stream(nums).max().getAsInt();
        
        for (int divisor = 1; divisor <= maxElement; divisor++) {
            int sumOfDivisionResults = 0;
            boolean thresholdExceeded = true;
            
            for (int num : nums) {
                sumOfDivisionResults += (int) Math.ceil((double) num / divisor);
                if (sumOfDivisionResults > threshold) {
                    thresholdExceeded = false;
                    break;
                }
            }
            
            if (thresholdExceeded) {
                return divisor;
            }
        }
        
        return -1;
    }
}

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

Задача: 485. Max Consecutive Ones
Сложность: easy

Дан бинарный массив nums, верните максимальное количество последовательных единиц в массиве.

Пример:

Input: nums = [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s. The maximum number of consecutive 1s is 3.

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

1⃣Поддерживайте счетчик для подсчета единиц и увеличивайте его на 1 при встрече единицы.

2⃣Когда встречаете ноль, используйте текущий счетчик единиц для нахождения максимального количества последовательных единиц на данный момент, затем сбросьте счетчик единиц на 0.

3⃣В конце верните максимальное значение.

😎 Решение:

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int count = 0;
        int maxCount = 0;
        for (int num : nums) {
            if (num == 1) {
                count += 1;
            } else {
                maxCount = Math.max(maxCount, count);
                count = 0;
            }
        }
        return Math.max(maxCount, count);
    }
}

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

Задача: 161. One Edit Distance
Сложность: medium

Даны две строки s и t. Верните true, если они отличаются ровно на одну операцию редактирования, иначе верните false.

Строка s считается отличающейся на одну операцию редактирования от строки t, если можно:
- Вставить ровно один символ в строку s, чтобы получить t.
- Удалить ровно один символ из строки s, чтобы получить t.
- Заменить ровно один символ в строке s на другой символ, чтобы получить t.

Пример:

Input: s = "ab", t = "acb"
Output: true
Explanation: We can insert 'c' into s to get t.

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

1⃣Проверка длины строк:
Убедитесь, что строка s короче строки t. Если это не так, поменяйте их местами и повторите проверку.
Если разница в длине между s и t больше 1, то строки невозможно привести к равенству одной операцией редактирования, верните false.

2⃣Сравнение строк посимвольно:
Проходите по строке s и сравнивайте каждый символ с соответствующим символом в строке t.
Если находите различающийся символ:
Если длины строк равны (ns == nt), проверьте, равны ли подстроки после текущего символа для обеих строк (s.substr(i + 1) == t.substr(i + 1)). Если равны, возвращайте true, иначе false.
Если длины строк различаются, проверьте, равна ли подстрока s начиная с текущего символа подстроке t начиная с следующего символа (s.substr(i) == t.substr(i + 1)). Если равны, возвращайте true, иначе false

3⃣Проверка на возможное добавление символа в конец s:
Если после посимвольного сравнения не было найдено различий на всей длине s и t длиннее s на один символ, это означает, что t можно получить добавлением одного символа в конец s. В этом случае верните true.
В противном случае верните false, так как это означает, что t либо имеет больше отличий, либо такой же размер как s без возможности привести их к равенству одной операцией редактирования.

😎 Решение:

class Solution {
    public boolean isOneEditDistance(String s, String t) {
        int ns = s.length();
        int nt = t.length();
        if (ns > nt) return isOneEditDistance(t, s);

        if (nt - ns > 1) return false;

        for (int i = 0; i < ns; i++) {
            if (s.charAt(i) != t.charAt(i)) {
                if (ns == nt) {
                    return s.substring(i + 1).equals(t.substring(i + 1));
                } else {
                    return s.substring(i).equals(t.substring(i + 1));
                }
            }
        }
        return (ns + 1 == nt);
    }
}

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

Задача: 524. Longest Word in Dictionary through Deleting
Сложность: medium

Даны строка s и массив строк dictionary. Верните самую длинную строку из dictionary, которую можно сформировать, удаляя некоторые символы из данной строки s. Если возможных результатов несколько, верните самое длинное слово с наименьшим лексикографическим порядком. Если возможного результата нет, верните пустую строку.

Пример:

Input: s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
Output: "apple"

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

1⃣Инициализируйте переменную для хранения самой длинной строки, соответствующей критериям. Пройдите по каждой строке x в неотсортированном массиве dictionary и проверьте, является ли x подпоследовательностью строки s.

2⃣Если строка x является подпоследовательностью, сравните её с текущей самой длинной строкой по длине. Если длина x больше или равна длине текущей самой длинной строки и она меньше текущей строки в лексикографическом порядке (если равны по длине), обновите текущую самую длинную строку.

3⃣После рассмотрения всех строк в dictionary, верните найденную строку. Если ни одна строка не подошла, верните пустую строку.

😎 Решение:

public class Solution {
    public boolean isSubsequence(String x, String y) {
        int j = 0;
        for (int i = 0; i < y.length() && j < x.length(); i++)
            if (x.charAt(j) == y.charAt(i))
                j++;
        return j == x.length();
    }
    public String findLongestWord(String s, List < String > d) {
        String max_str = "";
        for (String str: d) {
            if (isSubsequence(str, s)) {
                if (str.length() > max_str.length() || (str.length() == max_str.length() && str.compareTo(max_str) < 0))
                    max_str = str;
            }
        }
        return max_str;
    }
}

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

Задача: 649. Dota2 Senate
Сложность: medium

В мире Dota2 есть две партии: Radiant и Dire. Сенат Dota2 состоит из сенаторов, представляющих две партии. Теперь сенат хочет принять решение об изменении игры Dota2. Голосование за это изменение проходит в несколько раундов. В каждом раунде каждый сенатор может воспользоваться одним из двух прав: Запретить право одного сенатора: Сенатор может заставить другого сенатора потерять все свои права в этом и всех последующих раундах. Объявить о победе: Если этот сенатор обнаружил, что все сенаторы, у которых еще есть право голоса, принадлежат к одной партии, он может объявить о победе и принять решение об изменении игры. Дана строка senate, представляющая партийную принадлежность каждого сенатора. Символы "R" и "D" обозначают партию Лучезарных и партию Ужасных. Если сенаторов n, то размер данной строки будет равен n. Процедура голосования по кругу начинается от первого сенатора к последнему в заданном порядке. Эта процедура длится до конца голосования. Все сенаторы, потерявшие свои права, будут пропущены во время процедуры. Предположим, что каждый сенатор достаточно умен и будет играть по лучшей стратегии для своей партии. Предскажите, какая партия в итоге объявит о победе и изменит игру в Dota2. На выходе должно получиться "Radiant" или "Dire".

Пример:

Input: senate = "RD"
Output: "Radiant"

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

1⃣Инициализируйте две очереди для хранения индексов сенаторов от партий Radiant и Dire.

2⃣Выполните цикл, пока обе очереди не станут пустыми: Сравните индексы первых сенаторов из обеих очередей. Удалите сенатора с меньшим индексом из очереди и добавьте его с индексом, увеличенным на длину строки. Удалите сенатора с большим индексом из очереди.

3⃣Если одна из очередей опустела, объявите победу партии, чья очередь еще содержит сенаторов.

😎 Решение:

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    public String predictPartyVictory(String senate) {
        Queue<Integer> radiant = new LinkedList<>();
        Queue<Integer> dire = new LinkedList<>();
        
        for (int i = 0; i < senate.length(); i++) {
            if (senate.charAt(i) == 'R') {
                radiant.add(i);
            } else {
                dire.add(i);
            }
        }
        
        while (!radiant.isEmpty() && !dire.isEmpty()) {
            int r = radiant.poll();
            int d = dire.poll();
            if (r < d) {
                radiant.add(r + senate.length());
            } else {
                dire.add(d + senate.length());
            }
        }
        
        return radiant.isEmpty() ? "Dire" : "Radiant";
    }
}

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

Задача: 841. Keys and Rooms
Сложность: medium

Есть n комнат, пронумерованных от 0 до n - 1, и все комнаты закрыты, кроме комнаты 0. Ваша цель — посетить все комнаты. Однако вы не можете войти в закрытую комнату, не имея ключа от нее.
Когда вы посещаете комнату, вы можете найти в ней набор различных ключей. Каждый ключ имеет номер, указывающий, какую комнату он открывает, и вы можете взять их все с собой, чтобы открыть другие комнаты.

Дан массив rooms, где rooms[i] — это набор ключей, которые вы можете получить, если посетите комнату i. Верните true, если вы можете посетить все комнаты, или false в противном случае.

Пример:

Input: rooms = [[1],[2],[3],[]]
Output: true
Explanation: 
We visit room 0 and pick up key 1.
We then visit room 1 and pick up key 2.
We then visit room 2 and pick up key 3.
We then visit room 3.
Since we were able to visit every room, we return true.

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

1⃣Создайте массив seen для отслеживания посещенных комнат и стек stack для ключей, которые нужно использовать.

2⃣Поместите ключ от комнаты 0 в стек и отметьте комнату 0 как посещенную.

3⃣Пока стек не пуст, извлекайте ключи из стека и используйте их для открытия новых комнат, добавляя найденные ключи в стек. Если все комнаты посещены, верните true, иначе false.

😎 Решение:

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        boolean[] seen = new boolean[rooms.size()];
        seen[0] = true;
        Stack<Integer> stack = new Stack();
        stack.push(0);

        while (!stack.isEmpty()) {
            int node = stack.pop();
            for (int nei: rooms.get(node))
                if (!seen[nei]) {
                    seen[nei] = true;
                    stack.push(nei);
                }
        }

        for (boolean v: seen)
            if (!v) return false;
        return true;
    }
}

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

Задача: 835. Image Overlap
Сложность: medium

Вам даны два изображения, img1 и img2, представленные как бинарные квадратные матрицы размером n x n. Бинарная матрица содержит только 0 и 1 в качестве значений.
Мы можем сдвигать одно изображение как угодно, перемещая все биты 1 влево, вправо, вверх и/или вниз на любое количество единиц. Затем мы помещаем его поверх другого изображения. После этого мы можем вычислить перекрытие, подсчитав количество позиций, на которых в обоих изображениях есть 1.

Также обратите внимание, что при сдвиге не допускается никакое вращение. Любые биты 1, которые перемещаются за пределы границ матрицы, стираются.

Верните максимальное возможное перекрытие.

Пример:

Input: img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]
Output: 3
Explanation: We translate img1 to right by 1 unit and down by 1 unit.

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

1⃣Определите функцию shiftAndCount(xShift, yShift, M, R), которая смещает матрицу M относительно матрицы R на координаты (xShift, yShift) и подсчитывает количество единиц в зоне перекрытия.

2⃣Организуйте цикл по всем возможным комбинациям координат смещения (xShift, yShift).

3⃣На каждой итерации вызывайте функцию shiftAndCount() дважды для обоих направлений смещения и обновляйте максимальное количество перекрытий.

😎 Решение:

class Solution {
    protected int shiftAndCount(int xShift, int yShift, int[][] M, int[][] R) {
        int leftShiftCount = 0, rightShiftCount = 0;
        int rRow = 0;
        for (int mRow = yShift; mRow < M.length; ++mRow) {
            int rCol = 0;
            for (int mCol = xShift; mCol < M.length; ++mCol) {
                if (M[mRow][mCol] == 1 && M[mRow][mCol] == R[rRow][rCol])
                    leftShiftCount += 1;
                if (M[mRow][rCol] == 1 && M[mRow][rCol] == R[rRow][mCol])
                    rightShiftCount += 1;
                rCol += 1;
            }
            rRow += 1;
        }
        return Math.max(leftShiftCount, rightShiftCount);
    }

    public int largestOverlap(int[][] A, int[][] B) {
        int maxOverlaps = 0;

        for (int yShift = 0; yShift < A.length; ++yShift)
            for (int xShift = 0; xShift < A.length; ++xShift) {
                maxOverlaps = Math.max(maxOverlaps, shiftAndCount(xShift, yShift, A, B));
                maxOverlaps = Math.max(maxOverlaps, shiftAndCount(xShift, yShift, B, A));
            }

        return maxOverlaps;
    }

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

Задача: 328. Odd Even Linked List
Сложность: medium

Дан заголовок односвязного списка. Сгруппируйте все узлы с нечетными индексами вместе, а затем узлы с четными индексами, и верните упорядоченный список.

Первый узел считается нечетным, второй узел — четным и так далее.

Учтите, что относительный порядок внутри обеих групп (четной и нечетной) должен оставаться таким же, как в исходном списке.

Вы должны решить задачу с дополнительной сложностью по памяти O(1) и временной сложностью O(n).

Пример:

Input: head = [2,1,3,5,6,4,7]
Output: [2,3,6,7,1,5,4]

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

1⃣Инициализация указателей:
Создайте указатели odd и even для работы с нечетными и четными узлами, соответственно. Инициализируйте odd началом списка head, а even — следующим узлом head.next. Также создайте указатель evenHead для сохранения начала четного списка.

2⃣Разделение списка:
Используйте цикл для прохождения списка, перенаправляя нечетные узлы в oddList, а четные узлы в evenList. Обновляйте указатели odd и even в процессе итерации.

3⃣Соединение списков:
После окончания цикла соедините конец нечетного списка с началом четного списка, используя указатель evenHead.

😎 Решение:

public class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null) return null;
        ListNode odd = head, even = head.next, evenHead = even;
        while (even != null && even.next != null) {
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }
}

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

Задача: 851. Loud and Rich
Сложность: medium

Есть группа из n человек, пронумерованных от 0 до n - 1, где у каждого человека разное количество денег и разный уровень спокойствия.

Вам дан массив richer, где richer[i] = [ai, bi] указывает на то, что ai имеет больше денег, чем bi, и целочисленный массив quiet, где quiet[i] — это уровень спокойствия i-го человека. Все данные в richer логически корректны (т.е. данные не приведут к ситуации, где x богаче y и y богаче x одновременно).

Верните целочисленный массив answer, где answer[x] = y, если y — это самый спокойный человек (то есть человек y с наименьшим значением quiet[y]) среди всех людей, которые однозначно имеют столько же или больше денег, чем человек x.

Пример:

Input: richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]
Output: [5,5,2,5,4,5,6,7]
Explanation: 
answer[0] = 5.
Person 5 has more money than 3, which has more money than 1, which has more money than 0.
The only person who is quieter (has lower quiet[x]) is person 7, but it is not clear if they have more money than person 0.
answer[7] = 7.
Among all people that definitely have equal to or more money than person 7 (which could be persons 3, 4, 5, 6, or 7), the person who is the quietest (has lower quiet[x]) is person 7.
The other answers can be filled out with similar reasoning.

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

1⃣Постройте граф, описанный выше, и пусть dfs(person) будет самым спокойным человеком в поддереве person. Обратите внимание, что из-за логической последовательности утверждений граф должен быть DAG — ориентированным графом без циклов.

2⃣Теперь dfs(person) — это либо сам person, либо min(dfs(child) для каждого child из person). То есть, самый спокойный человек в поддереве — это либо сам person, либо самый спокойный человек в каком-то поддереве потомка person.

3⃣Мы можем кэшировать значения dfs(person) в answer[person], выполняя обход графа в пост-обходе. Таким образом, мы не повторяем работу. Этот метод уменьшает квадратичное время выполнения алгоритма до линейного.

😎 Решение:

class Solution {
    ArrayList<Integer>[] graph;
    int[] answer;
    int[] quiet;

    public int[] loudAndRich(int[][] richer, int[] quiet) {
        int N = quiet.length;
        graph = new ArrayList[N];
        answer = new int[N];
        this.quiet = quiet;

        for (int node = 0; node < N; ++node)
            graph[node] = new ArrayList<Integer>();

        for (int[] edge: richer)
            graph[edge[1]].add(edge[0]);

        Arrays.fill(answer, -1);

        for (int node = 0; node < N; ++node)
            dfs(node);
        return answer;
    }

    public int dfs(int node) {
        if (answer[node] == -1) {
            answer[node] = node;
            for (int child: graph[node]) {
                int cand = dfs(child);
                if (quiet[cand] < quiet[answer[node]])
                    answer[node] = cand;
            }
        }
        return answer[node];
    }
}

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

Задача: 1354. Construct Target Array With Multiple Sums
Сложность: hard

Дан массив целых чисел target длины n. Начав с массива arr, состоящего из n единиц, вы можете выполнить следующую процедуру:

Пусть x будет суммой всех элементов, находящихся в вашем массиве.
Выберите индекс i так, чтобы 0 <= i < n, и установите значение arr в индексе i равным x.
Вы можете повторять эту процедуру столько раз, сколько потребуется.
Верните true, если возможно построить массив target из arr, в противном случае верните false.

Пример:

Input: target = [8,5]
Output: true

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

1⃣Использование максимальной кучи (Max Heap) для отслеживания максимальных значений в target:
Сначала необходимо инициализировать кучу с максимальным приоритетом, чтобы всегда иметь доступ к наибольшему элементу в массиве target.
Вычислить сумму всех элементов в target и сохранить ее.

2⃣Повторение процесса переворота:
Извлечь наибольшее значение из кучи. Вычесть это значение из общей суммы.
Проверить несколько условий:
Если извлеченное значение равно 1 или общая сумма равна 1, вернуть true.
Если извлеченное значение меньше общей суммы, общая сумма равна 0, или извлеченное значение делится на общую сумму без остатка, вернуть false.
Остаток от деления наибольшего значения на общую сумму является новым значением, которое нужно вставить обратно в кучу. Обновить общую сумму.

3⃣Повторение цикла до достижения результата:
Повторять шаг 2 до тех пор, пока не будут выполнены условия выхода из цикла (возврат true или false).

😎 Решение:

import java.util.PriorityQueue;

public class Solution {
    public boolean isPossible(int[] target) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        long total = 0;
        for (int num : target) {
            total += num;
            pq.add(num);
        }
        
        while (pq.peek() > 1) {
            int maxVal = pq.poll();
            total -= maxVal;
            if (maxVal < total || total == 0 || maxVal % total == 0) return false;
            pq.add(maxVal % total);
            total += pq.peek();
        }
        return true;
    }
}

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

Задача: 590. N-ary Tree Postorder Traversal
Сложность: easy

Дано корневое дерево с n-арной структурой, верните обход дерева в постфиксном порядке для значений его узлов.

Сериализация входных данных n-арного дерева представлена в обходе уровней. Каждая группа детей разделяется значением null (см. примеры).

Пример:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [2,6,14,11,7,3,12,8,4,13,9,10,5,1]

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

1⃣Инициализируйте стек для хранения узлов и список для хранения значений узлов в обратном порядке.

2⃣Начните с корневого узла и добавьте его в стек. Пока стек не пуст, извлекайте узлы из стека, добавляя их значения в начало списка, и добавляйте всех его детей в стек.

3⃣В конце верните список значений узлов.

😎 Решение:

class Solution {
    public List<Integer> postorder(Node root) {
        LinkedList<Node> stack = new LinkedList<>();
        LinkedList<Integer> output = new LinkedList<>();
        if (root == null) {
            return output;
        }

        stack.add(root);
        while (!stack.isEmpty()) {
            Node node = stack.pollLast();
            output.addFirst(node.val);
            for (Node item : node.children) {
                if (item != null) {
                    stack.add(item);
                }
            }
        }
        return output;
    }
    class Node {
        public int val;
        public List<Node> children;

        public Node() {}

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    }
}

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