#easy
Задача: 441. Arranging Coins

У вас есть n монет, и вы хотите построить лестницу из этих монет. Лестница состоит из k рядов, где i-й ряд содержит ровно i монет. Последний ряд лестницы может быть неполным.

Дано целое число n, верните количество полных рядов лестницы, которые вы сможете построить.

Пример:

Input: n = 5
Output: 2
Explanation: Because the 3rd row is incomplete, we return 2.

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

1⃣Если мы глубже посмотрим на формулу задачи, мы можем решить её с помощью математики, без использования итераций.

2⃣Напомним, что условие задачи можно выразить следующим образом: k(k + 1) ≤ 2N.

3⃣Это можно решить методом выделения полного квадрата, (k + 1/2)² - 1/4 ≤ 2N. Что приводит к следующему ответу: k = [sqrt(2N + 1/4) - 1/2].

😎 Решение:

class Solution {
    public int arrangeCoins(int n) {
        return (int)(Math.sqrt(2 * (long)n + 0.25) - 0.5);
    }
}

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

#medium
Задача: 362. Design Hit Counter

Дана матрица размером m x n, где каждая ячейка является либо стеной 'W', либо врагом 'E', либо пустой '0'. Верните максимальное количество врагов, которых можно уничтожить, используя одну бомбу. Вы можете разместить бомбу только в пустой ячейке.

Бомба уничтожает всех врагов в той же строке и столбце от точки установки до тех пор, пока не встретит стену, так как она слишком сильна, чтобы быть разрушенной.

Пример:

Input
["HitCounter", "hit", "hit", "hit", "getHits", "hit", "getHits", "getHits"]
[[], [1], [2], [3], [4], [300], [300], [301]]
Output
[null, null, null, null, 3, null, 4, 3]

Explanation
HitCounter hitCounter = new HitCounter();
hitCounter.hit(1);       // hit at timestamp 1.
hitCounter.hit(2);       // hit at timestamp 2.
hitCounter.hit(3);       // hit at timestamp 3.
hitCounter.getHits(4);   // get hits at timestamp 4, return 3.
hitCounter.hit(300);     // hit at timestamp 300.
hitCounter.getHits(300); // get hits at timestamp 300, return 4.
hitCounter.getHits(301); // get hits at timestamp 301, return 3.

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

1⃣При вызове метода hit(int timestamp), добавьте временную метку в очередь.

2⃣ При вызове метода getHits(int timestamp), удалите все временные метки из очереди, которые старше 300 секунд от текущей временной метки.

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

😎 Решение:

class HitCounter {
    private Queue<Integer> hits; 

    public HitCounter() {
        this.hits = new LinkedList<Integer>();
    }
    
    public void hit(int timestamp) {
        this.hits.add(timestamp);
    }
    
    public int getHits(int timestamp) {
        while (!this.hits.isEmpty()) {
            int diff = timestamp - this.hits.peek();
            if (diff >= 300) this.hits.remove();
            else break;
        }
        return this.hits.size();
    }
}

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

#medium
Задача: 442. Find All Duplicates in an Array


Дан целочисленный массив nums длины n, где все целые числа nums находятся в диапазоне [1, n], и каждое число появляется один или два раза. Верните массив всех чисел, которые появляются дважды.

Вы должны написать алгоритм, который работает за время O(n) и использует только постоянное дополнительное пространство.

Пример:

Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]

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

1⃣Когда мы итерируемся по элементам входного массива, мы можем просто искать любое другое вхождение текущего элемента в оставшейся части массива.

2⃣Поскольку элемент может появляться только один или два раза, нам не нужно беспокоиться о получении дубликатов элементов, которые появляются дважды: Случай I: Если элемент встречается в массиве только один раз, при поиске его в остальной части массива ничего не найдется. Случай II: Если элемент встречается дважды, вы найдете второе вхождение элемента в оставшейся части массива. Когда вы наткнетесь на второе вхождение в более поздней итерации, это будет аналогично случаю I (поскольку больше вхождений этого элемента в оставшейся части массива не будет).

3⃣Таким образом, можно эффективно определить все элементы, которые встречаются дважды, и добавить их в результирующий массив, проходя по каждому элементу массива и проверяя наличие его второго вхождения в оставшейся части массива.

😎 Решение:

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> ans = new ArrayList<>();
        
        for (int i = 0; i < nums.length; i++)
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] == nums[i]) {
                    ans.add(nums[i]);
                    break;
                }
            }
        
        return ans;
    }
}

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

#medium
Задача: 443. String Compression


Дан массив символов chars, сжать его, используя следующий алгоритм:

Начните с пустой строки s. Для каждой группы последовательных повторяющихся символов в chars:

Если длина группы равна 1, добавьте символ к строке s.
В противном случае добавьте символ, а за ним длину группы.
Сжатая строка s не должна возвращаться отдельно, а вместо этого должна быть сохранена в входном массиве символов chars. Обратите внимание, что длины групп, которые равны 10 или более, будут разделены на несколько символов в chars.

После того как вы закончите модификацию входного массива, верните новую длину массива.

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

Пример:

Input: chars = ["a","a","b","b","c","c","c"]
Output: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]
Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".

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

1⃣Объявите переменные i – первый индекс текущей группы, и res – длина ответа (сжатой строки). Инициализируйте i = 0, res = 0.

2⃣Пока i меньше длины chars: Найдите длину текущей группы последовательных повторяющихся символов groupLength. Добавьте chars[i] к ответу (chars[res++] = chars[i]). Если groupLength > 1, добавьте строковое представление groupLength к ответу и увеличьте res соответственно. Увеличьте i на groupLength и перейдите к следующей группе.

3⃣Верните res.

😎 Решение:

class Solution {
    public int compress(char[] chars) {
        int i = 0;
        int res = 0;
        while (i < chars.length) {
            int groupLength = 1;
            while (i + groupLength < chars.length && chars[i + groupLength] == chars[i]) {
                groupLength++;
            }
            chars[res++] = chars[i];
            if (groupLength > 1) {
                String strRepr = Integer.toString(groupLength);
                for (char ch : strRepr.toCharArray()) {
                    chars[res++] = ch;
                }
            }
            i += groupLength;
        }
        return res;
    }
}

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

#hard
Задача: 363. Max Sum of Rectangle No Larger Than K

Дана матрица размером m x n и целое число k, вернуть максимальную сумму прямоугольника в матрице, такая что его сумма не превышает k.

Гарантируется, что будет прямоугольник с суммой, не превышающей k.

Пример:

Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Output: 2
Explanation: Because the sum of the blue rectangle [[0, 1], [-2, 3]] is 2, and 2 is the max number no larger than k (k = 2).

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

1⃣Создать вспомогательную функцию updateResult, которая будет находить максимальную сумму подмассива в одномерном массиве, не превышающую k.

2⃣Преобразовать каждую подматрицу в одномерный массив и применить к ней функцию updateResult.

3⃣Вернуть максимальную найденную сумму.

😎 Решение:

class Solution {
    int result = Integer.MIN_VALUE;
    void updateResult(int[] nums, int k) {
        int sum = 0;

        TreeSet<Integer> sortedSum = new TreeSet<>();

        sortedSum.add(0);
        for (int num : nums) {
            sum += num;

            Integer x = sortedSum.ceiling(sum - k);

            if (x != null)
                result = Math.max(result, sum - x);

            sortedSum.add(sum);
        }
    }
    public int maxSumSubmatrix(int[][] matrix, int k) {
        int[] rowSum = new int[matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            Arrays.fill(rowSum, 0);
            for (int row = i; row < matrix.length; row++) {
                for (int col = 0; col < matrix[0].length; col++)
                    rowSum[col] += matrix[row][col];

                updateResult(rowSum, k);

                if (result == k)
                    return result;
            }
        }
        return result;
    }
}

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

#medium
Задача: 445. Add Two Numbers II


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

Вы можете предположить, что оба числа не содержат начальных нулей, за исключением самого числа 0.

Пример:

Input: l1 = [7,2,4,3], l2 = [5,6,4]
Output: [7,8,0,7]

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

1⃣Создайте два связанных списка r1 и r2, чтобы хранить перевернутые связанные списки l1 и l2 соответственно. Создайте два целых числа totalSum и carry для хранения суммы и переноса текущих цифр. Создайте новый ListNode, ans, который будет хранить сумму текущих цифр. Мы будем складывать два числа, используя перевернутый список, добавляя цифры по одной. Продолжаем, пока не пройдем все узлы в r1 и r2.

2⃣Если r1 не равен null, добавляем r1.val к totalSum. Если r2 не равен null, добавляем r2.val к totalSum. Устанавливаем ans.val = totalSum % 10. Сохраняем перенос как totalSum / 10. Создаем новый ListNode, newNode, который будет иметь значение как перенос. Устанавливаем next для newNode как ans. Обновляем ans = newNode, чтобы использовать ту же переменную ans для следующей итерации. Обновляем totalSum = carry.

3⃣Если carry == 0, это означает, что newNode, созданный в финальной итерации цикла while, имеет значение 0. Поскольку мы выполняем ans = newNode в конце каждой итерации цикла while, чтобы избежать возврата связанного списка с головой, равной 0 (начальный ноль), возвращаем следующий элемент, т.е. возвращаем ans.next. В противном случае, если перенос не равен 0, значение ans не равно нулю. Следовательно, просто возвращаем ans.

😎 Решение:

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode temp = null;
        while (head != null) {
            temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode r1 = reverseList(l1);
        ListNode r2 = reverseList(l2);

        int totalSum = 0;
        int carry = 0;
        ListNode ans = new ListNode();
        while (r1 != null || r2 != null) {
            if (r1 != null) {
                totalSum += r1.val;
                r1 = r1.next;
            }
            if (r2 != null) {
                totalSum += r2.val;
                r2 = r2.next;
            }

            ans.val = totalSum % 10;
            carry = totalSum / 10;
            ListNode head = new ListNode(carry);
            head.next = ans;
            ans = head;
            totalSum = carry;
        }

        return carry == 0 ? ans.next : ans;
    }
}

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

#hard
Задача: 446. Arithmetic Slices II - Subsequence


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

Последовательность чисел называется арифметической, если она состоит как минимум из трех элементов и если разница между любыми двумя последовательными элементами одинаковая.

Например, [1, 3, 5, 7, 9], [7, 7, 7, 7] и [3, -1, -5, -9] являются арифметическими последовательностями.
Например, [1, 1, 2, 5, 7] не является арифметической последовательностью.
Подпоследовательность массива - это последовательность, которая может быть образована путем удаления некоторых элементов (возможно, ни одного) из массива.

Например, [2, 5, 10] является подпоследовательностью [1, 2, 1, 2, 4, 1, 5, 10].
Тестовые случаи сгенерированы таким образом, что ответ помещается в 32-битное целое число.

Пример:

Input: nums = [2,4,6,8,10]
Output: 7
Explanation: All arithmetic subsequence slices are:
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]

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

1⃣Мы можем использовать поиск в глубину (DFS) для генерации всех подпоследовательностей.

2⃣Мы можем проверить, является ли подпоследовательность арифметической, согласно ее определению.

3⃣Возвращаем количество всех арифметических подпоследовательностей.

😎 Решение:

class Solution {
    private int n;
    private int ans;

    private void dfs(int dep, int[] A, List<Long> cur) {
        if (dep == n) {
            if (cur.size() < 3) return;
            for (int i = 1; i < cur.size(); i++) {
                if (cur.get(i) - cur.get(i - 1) != cur.get(1) - cur.get(0)) return;
            }
            ans++;
            return;
        }
        dfs(dep + 1, A, cur);
        cur.add((long) A[dep]);
        dfs(dep + 1, A, cur);
        cur.remove(cur.size() - 1);
    }

    public int numberOfArithmeticSlices(int[] A) {
        n = A.length;
        ans = 0;
        dfs(0, A, new ArrayList<>());
        return ans;
    }
}

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

#medium
Задача: 364. Nested List Weight Sum II

Вам дан вложенный список целых чисел nestedList. Каждый элемент является либо целым числом, либо списком, элементы которого также могут быть целыми числами или другими списками.

Глубина целого числа — это количество списков, внутри которых оно находится. Например, вложенный список [1,[2,2],[[3],2],1] имеет значение каждого целого числа, установленное равным его глубине. Пусть maxDepth будет максимальной глубиной любого целого числа.
Вес целого числа определяется как maxDepth - (глубина целого числа) + 1.

Верните сумму каждого целого числа в nestedList, умноженную на его вес.

Пример:

Input: nestedList = [[1,1],2,[1,1]]
Output: 8
Explanation: Four 1's with a weight of 1, one 2 with a weight of 2.
1*1 + 1*1 + 2*2 + 1*1 + 1*1 = 8

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

1⃣Инициализировать первый уровень BFS-дерева, добавив все элементы из входного nestedList в очередь.

2⃣Для каждого уровня извлекать передний элемент из очереди. Если это список, то добавить его элементы в очередь. В противном случае обновить значения sumOfElements, maxDepth и sumOfProducts.

3⃣Когда очередь станет пустой, вернуть значение (maxDepth + 1) * sumOfElements - sumOfProducts.

😎 Решение:

class Solution {
    public int depthSumInverse(List<NestedInteger> nestedList) {
        Queue<NestedInteger> Q = new LinkedList<>();
        Q.addAll(nestedList);

        int depth = 1;
        int maxDepth = 0;
        int sumOfElements = 0;
        int sumOfProducts = 0;

        while (!Q.isEmpty()) {
            int size = Q.size();
            maxDepth = Math.max(maxDepth, depth);
            
            for (int i = 0; i < size; i++) {
                NestedInteger nested = Q.poll();
                
                if (nested.isInteger()) {
                    sumOfElements += nested.getInteger();
                    sumOfProducts += nested.getInteger() * depth;
                } else {
                    Q.addAll(nested.getList());
                }
            }
            depth++;
        }
        return (maxDepth + 1) * sumOfElements - sumOfProducts;
    }
}

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

Ищу работу пол года

Практически под каждым постом в этом канале я вижу комментарии от людей, которые ищут работу по полгода. Это перерастает в обсуждение того, как нужно (или не нужно) искать работу, почему процесс найма сломан и как они откликались на фейковые вакансии.

Честно говоря, искать работу полгода — это нонсенс. Очевидно, что человек делает что-то не так. Главная ошибка, которую совершают многие, — это создание иллюзии поиска работы.

То есть человек вроде бы ищет работу, но делает это неэффективно, тратя время на нецелевые действия. Например:

➖ Просматривает вакансии перед откликом.
➖ Пытается понять, подходит ли он под вакансию. Если считает, что не подходит — не откликается.
➖ Пишет сопроводительные письма (иногда даже уникальные под каждую вакансию).
➖ Заполняет анкеты, проходит тесты.

Все эти действия отнимают время, но не приводят к результату.

Почему это не работает?

HR-менеджер не может вручную отсмотреть 2000 откликов, оценить каждое резюме и прочитать сопроводительные письма. Поэтому компании используют ATS-системы (системы автоматического подбора), которые анализируют резюме и определяют процент его соответствия вакансии.

Что делать, чтобы повысить шансы?

1️⃣ Добавить ключевые навыки в резюме — и в основной текст, и в теги. Возьмите их с easyoffer.ru

2️⃣ Убрать нерелевантный опыт, оставить только подходящий.

3️⃣ Оформить опыт так, чтобы он выглядел релевантным. Если у вас его нет, укажите проекты, стажировки или другой опыт, который можно представить как работу от 1 года. Если опыт слишком большой, сузьте его до 6 лет.

4️⃣ Откликаться на все вакансии без разбору. Если вы Junior, не ищите только стажер или Junior-вакансии — пробуйте везде. Не отказывайте себе сами, пусть это решит HR

5️⃣ Сделать резюме публичным, потому что HR-менеджеры часто ищут кандидатов не только среди откликов, но и в базе резюме.

6️⃣ Используйте ИИ по минимуму – ATS-системы считывают это и помечают "сгенерировано ИИ"

‼️ Главное правило: чем больше откликов — тем выше шанс получить оффер. Делайте резюме удобным для ATS-систем, и вас заметят.

1. Посмотрите видео о том как я вывел свою резюме в Топ1 на HH
2. Посмотрите видео как я нашел первую работу
3. Прочитайте этот кейс про оптимизацию резюме

Если прям вообще тяжело.

Создайте несколько разных резюме. Создайте 2, 3 да хоть 10 резюме. Настройте авто-отлики и ждите приглашения на собесы.

Не нужно создавать иллюзию поиска работы, сделайте несколько простых и актуальных действий.

#medium
Задача: 366. Find Leaves of Binary Tree

Дан корень бинарного дерева, соберите узлы дерева следующим образом:
Соберите все листовые узлы.
Удалите все листовые узлы.
Повторяйте, пока дерево не станет пустым.

Пример:

Input: root = [1,2,3,4,5]
Output: [[4,5,3],[2],[1]]
Explanation:
[[3,5,4],[2],[1]] and [[3,4,5],[2],[1]] are also considered correct answers since per each level it does not matter the order on which elements are returned.

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

1⃣Реализовать функцию getHeight(node), которая будет вычислять высоту каждого узла в дереве с использованием рекурсивного обхода в глубину (post-order). Если узел является null, вернуть -1.

2⃣Сохранить пары (высота, значение) для всех узлов и отсортировать их по высоте.

3⃣Организовать узлы по высоте и вернуть результат.

😎 Решение:

class Solution {
    private List<Pair<Integer, Integer>> pairs;
    
    private int getHeight(TreeNode root) {
        
        if (root == null) return -1;
        
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        
        int currHeight = Math.max(leftHeight, rightHeight) + 1;

        this.pairs.add(new Pair<Integer, Integer>(currHeight, root.val));

        return currHeight;
    }
    
    public List<List<Integer>> findLeaves(TreeNode root) {
        this.pairs = new ArrayList<>();
        
        getHeight(root);
        
        Collections.sort(this.pairs, Comparator.comparing(p -> p.getKey()));
        
        int n = this.pairs.size(), height = 0, i = 0;

        List<List<Integer>> solution = new ArrayList<>();
        
        while (i < n) {
            List<Integer> nums = new ArrayList<>();
            while (i < n && this.pairs.get(i).getKey() == height) {
                nums.add(this.pairs.get(i).getValue());
                i++;
            }
            solution.add(nums);
            height++;
        }
        return solution;
    }
}

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

#hard
Задача: 710. Random Pick with Blacklist

Вам дано целое число n и массив уникальных целых чисел blacklist. Разработайте алгоритм выбора случайного целого числа из диапазона [0, n - 1], не входящего в черный список. Любое целое число, находящееся в указанном диапазоне и не входящее в черный список, должно с равной вероятностью быть возвращено. Оптимизируйте алгоритм так, чтобы он минимизировал количество обращений к встроенной функции random вашего языка. Реализуйте класс Solution: Solution(int n, int[] blacklist) Инициализирует объект целым числом n и целым числом из черного списка blacklist. int pick() Возвращает случайное целое число в диапазоне [0, n - 1] и не входящее в черный список.

Пример:

Input
["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"]
[[7, [2, 3, 5]], [], [], [], [], [], [], []]
Output
[null, 0, 4, 1, 6, 1, 0, 4]

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

1⃣Создайте маппинг для чисел, входящих в черный список, чтобы сопоставить их с числами из диапазона [n - len(blacklist), n - 1], которые не входят в черный список.

2⃣Создайте массив для хранения возможных чисел для выбора, исключая числа из черного списка.

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

😎 Решение:

import java.util.*;

public class Solution {
    private Map<Integer, Integer> map;
    private int bound;

    public Solution(int n, int[] blacklist) {
        map = new HashMap<>();
        bound = n - blacklist.length;
        Set<Integer> blackset = new HashSet<>();
        for (int b : blacklist) {
            blackset.add(b);
        }
        int whitelist = bound;
        for (int b : blacklist) {
            if (b < bound) {
                while (blackset.contains(whitelist)) {
                    whitelist++;
                }
                map.put(b, whitelist);
                whitelist++;
            }
        }
    }

    public int pick() {
        int r = (int) (Math.random() * bound);
        return map.getOrDefault(r, r);
    }
}

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

#hard
Задача: 765. Couples Holding Hands

Есть n пар, сидящих на 2n местах, расположенных в ряд, и они хотят держаться за руки.

Люди и места представлены массивом целых чисел row, где row[i] — это ID человека, сидящего на i-м месте. Пары пронумерованы по порядку: первая пара — (0, 1), вторая пара — (2, 3) и так далее, до последней пары — (2n - 2, 2n - 1).

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

Пример:

Input: row = [0,2,1,3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.

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

1⃣Мы могли бы предположить без доказательства, что решение, при котором мы делаем людей на каждом диване счастливыми по порядку, является оптимальным. Это предположение сильнее, чем гипотеза о жадном подходе, но кажется разумным, поскольку при каждом ходе мы делаем хотя бы одну пару счастливой.

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

3⃣Для каждого дивана с двумя возможностями (т.е. оба человека на диване несчастливы) мы попробуем первый вариант, найдем ответ как ans1, затем отменим наш ход и попробуем второй вариант, найдем связанный ответ как ans2, отменим наш ход и затем вернем наименьший ответ.

😎 Решение:

class Solution {
    int N;
    int[][] pairs;

    public int minSwapsCouples(int[] row) {
        N = row.length / 2;
        pairs = new int[N][2];
        for (int i = 0; i < N; ++i) {
            pairs[i][0] = row[2 * i] / 2;
            pairs[i][1] = row[2 * i + 1] / 2;
        }
        return solve(0);
    }

    public void swap(int a, int b, int c, int d) {
        int t = pairs[a][b];
        pairs[a][b] = pairs[c][d];
        pairs[c][d] = t;
    }

    public int solve(int i) {
        if (i == N) return 0;
        int x = pairs[i][0], y = pairs[i][1];
        if (x == y) return solve(i + 1);

        int jx = 0, kx = 0, jy = 0, ky = 0;
        for (int j = i + 1; j < N; ++j) {
            for (int k = 0; k <= 1; ++k) {
                if (pairs[j][k] == x) { jx = j; kx = k; }
                if (pairs[j][k] == y) { jy = j; ky = k; }
            }
        }

        swap(i, 1, jx, kx);
        int ans1 = 1 + solve(i + 1);
        swap(i, 1, jx, kx);

        swap(i, 0, jy, ky);
        int ans2 = 1 + solve(i + 1);
        swap(i, 0, jy, ky);

        return Math.min(ans1, ans2);
    }
}

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

#hard
Задача: 711. Number of Distinct Islands II

Вам дана двоичная матричная сетка m x n. Остров - это группа 1 (представляющая сушу), соединенных в четырех направлениях (горизонтальном или вертикальном). Можно предположить, что все четыре края сетки окружены водой. Остров считается одинаковым с другим, если они имеют одинаковую форму, или имеют одинаковую форму после поворота (только на 90, 180 или 270 градусов) или отражения (влево/вправо или вверх/вниз). Верните количество разных островов.

Пример:

Input: grid = [[1,1,0,0,0],[1,0,0,0,0],[0,0,0,0,1],[0,0,0,1,1]]
Output: 1

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

1⃣Пройдите по каждому элементу матрицы, если найдена земля (1), выполните DFS для обнаружения всех связанных с этим островом земель и сохраните форму острова.

2⃣Нормализуйте форму острова, применив все возможные повороты и отражения, чтобы найти каноническую форму.

3⃣Используйте множество для хранения всех уникальных канонических форм и верните размер этого множества.

😎 Решение:

import java.util.*;

public class Solution {
    public int numDistinctIslands2(int[][] grid) {
        Set<String> uniqueIslands = new HashSet<>();
        
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    List<int[]> shape = new ArrayList<>();
                    dfs(grid, i, j, i, j, shape);
                    uniqueIslands.add(normalize(shape));
                }
            }
        }
        
        return uniqueIslands.size();
    }
    
    private void dfs(int[][] grid, int i, int j, int baseI, int baseJ, List<int[]> shape) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0) {
            return;
        }
        grid[i][j] = 0;
        shape.add(new int[] {i - baseI, j - baseJ});
        dfs(grid, i + 1, j, baseI, baseJ, shape);
        dfs(grid, i - 1, j, baseI, baseJ, shape);
        dfs(grid, i, j + 1, baseI, baseJ, shape);
        dfs(grid, i, j - 1, baseI, baseJ, shape);
    }
    
    private String normalize(List<int[]> shape) {
        List<List<int[]>> shapes = new ArrayList<>();
        for (int i = 0; i < 8; i++) {
            shapes.add(new ArrayList<>());
        }
        for (int[] point : shape) {
            int x = point[0], y = point[1];
            shapes.get(0).add(new int[] {x, y});
            shapes.get(1).add(new int[] {x, -y});
            shapes.get(2).add(new int[] {-x, y});
            shapes.get(3).add(new int[] {-x, -y});
            shapes.get(4).add(new int[] {y, x});
            shapes.get(5).add(new int[] {y, -x});
            shapes.get(6).add(new int[] {-y, x});
            shapes.get(7).add(new int[] {-y, -x});
        }
        for (List<int[]> s : shapes) {
            s.sort((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
        }
        String[] shapesStr = new String[8];
        for (int i = 0; i < 8; i++) {
            shapesStr[i] = shapes.get(i).toString();
        }
        Arrays.sort(shapesStr);
        return shapesStr[0];
    }
}

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

#hard
Задача: 591. Tag Validator

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

Фрагмент кода считается корректным, если соблюдаются все следующие правила:
Код должен быть заключен в корректный закрытый тег. В противном случае код некорректен.
Закрытый тег (не обязательно корректный) имеет точно следующий формат: <TAG_NAME>TAG_CONTENT</TAG_NAME>. Среди них <TAG_NAME> — это начальный тег, а </TAG_NAME> — конечный тег. TAG_NAME в начальном и конечном тегах должен быть одинаковым. Закрытый тег корректен, если и только если TAG_NAME и TAG_CONTENT корректны.
Корректное TAG_NAME содержит только заглавные буквы и имеет длину в диапазоне [1, 9]. В противном случае TAG_NAME некорректен.
Корректное TAG_CONTENT может содержать другие корректные закрытые теги, cdata и любые символы (см. примечание 1), КРОМЕ неподходящих <, неподходящих начальных и конечных тегов, и неподходящих или закрытых тегов с некорректным TAG_NAME. В противном случае TAG_CONTENT некорректен.
Начальный тег неподходящий, если нет конечного тега с тем же TAG_NAME, и наоборот. Однако нужно также учитывать проблему несбалансированных тегов, когда они вложены.
< неподходящий, если не удается найти последующий >. И когда вы находите < или </, все последующие символы до следующего > должны быть разобраны как TAG_NAME (не обязательно корректный).
cdata имеет следующий формат: <![CDATA[CDATA_CONTENT]]>. Диапазон CDATA_CONTENT определяется как символы между <![CDATA[ и первым последующим ]]>.
CDATA_CONTENT может содержать любые символы. Функция cdata заключается в том, чтобы запретить валидатору разбирать CDATA_CONTENT, поэтому даже если в нем есть символы, которые могут быть разобраны как тег (корректный или некорректный), вы должны рассматривать их как обычные символы.

Пример:

Input: code = "<DIV>This is the first line <![CDATA[<div>]]></DIV>"
Output: true

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

1⃣Инициализируйте стек для отслеживания открытых тегов и флаг для определения наличия тегов. Используйте регулярное выражение для проверки корректности TAG_NAME, TAG_CONTENT и CDATA.

2⃣Пройдитесь по строке, проверяя каждый символ. Если встретите <, определите тип тега (начальный, конечный или CDATA). Обновите стек и индексы в зависимости от найденного типа.

3⃣В конце проверьте, что стек пуст (все теги корректно закрыты) и верните результат.

😎 Решение:

import java.util.regex.*;

public class Solution {
    Stack<String> stack = new Stack<>();
    boolean containsTag = false;

    public boolean isValidTagName(String s, boolean ending) {
        if (ending) {
            if (!stack.isEmpty() && stack.peek().equals(s)) stack.pop();
            else return false;
        } else {
            containsTag = true;
            stack.push(s);
        }
        return true;
    }

    public boolean isValid(String code) {
        if (!Pattern.matches("<[A-Z]{0,9}>([^<]*(<((\\/?[A-Z]{1,9}>)|(!\\[CDATA\\[(.*?)]]>)))?)*", code))
            return false;

        for (int i = 0; i < code.length(); i++) {
            boolean ending = false;
            if (stack.isEmpty() && containsTag) return false;
            if (code.charAt(i) == '<') {
                if (code.charAt(i + 1) == '!') {
                    i = code.indexOf("]]>", i + 1);
                    continue;
                }
                if (code.charAt(i + 1) == '/') {
                    i++;
                    ending = true;
                }
                int closeIndex = code.indexOf('>', i + 1);
                if (closeIndex < 0 || !isValidTagName(code.substring(i + 1, closeIndex), ending))
                    return false;
                i = closeIndex;
            }
        }
        return stack.isEmpty();
    }
}

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

#easy
Задача: 766. Toeplitz Matrix

Дана матрица размером m x n. Вернуть true, если матрица является Тёплицевой. В противном случае вернуть false.

Матрица является Тёплицевой, если все диагонали, идущие от верхнего левого к нижнему правому углу, содержат одинаковые элементы.

Пример:

Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Output: true
Explanation:
In the above grid, the diagonals are:
"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]".
In each diagonal all elements are the same, so the answer is True.

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

1⃣Что отличает две координаты (r1, c1) и (r2, c2) на одной диагонали? Оказывается, две координаты находятся на одной диагонали тогда и только тогда, когда r1 - c1 == r2 - c2.м

2⃣Это приводит к следующей идее: запоминайте значение этой диагонали как groups[r - c]. Если обнаружено несоответствие, то матрица не является Тёплицевой; в противном случае, она является таковой.

3⃣Таким образом, для каждой ячейки матрицы сохраняйте значение диагонали в словаре groups с ключом r - c. Проходите по всем ячейкам матрицы и проверяйте, совпадает ли текущее значение с сохранённым в groups. Если где-то обнаруживается несоответствие, верните false. Если все элементы соответствуют, верните true.

😎 Решение:

class Solution {
    public boolean isToeplitzMatrix(int[][] matrix) {
        Map<Integer, Integer> groups = new HashMap<>();
        for (int r = 0; r < matrix.length; ++r) {
            for (int c = 0; c < matrix[0].length; ++c) {
                if (!groups.containsKey(r - c))
                    groups.put(r - c, matrix[r][c]);
                else if (groups.get(r - c) != matrix[r][c])
                    return false;
            }
        }
        return true;
    }
}

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

#medium
Задача: 712. Minimum ASCII Delete Sum for Two Strings

Если даны две строки s1 и s2, верните наименьшую ASCII-сумму удаленных символов, чтобы сделать две строки равными.

Пример:

Input: s1 = "sea", s2 = "eat"
Output: 231

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

1⃣Создайте двумерный массив dp размером (len(s1) + 1) x (len(s2) + 1), где dp[i][j] будет хранить наименьшую ASCII-сумму удаленных символов для первых i символов s1 и первых j символов s2.

2⃣Заполните первую строку и первый столбец массива dp суммами ASCII значений символов, которые необходимо удалить для достижения пустой строки.

3⃣Заполните оставшуюся часть массива dp следующим образом: Если символы s1[i-1] и s2[j-1] равны, dp[i][j] = dp[i-1][j-1]. Иначе, dp[i][j] = min(dp[i-1][j] + ord(s1[i-1]), dp[i][j-1] + ord(s2[j-1])).

😎 Решение:

public class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];
        for (int i = 1; i <= s1.length(); i++) {
            dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1);
        }
        for (int j = 1; j <= s2.length(); j++) {
            dp[0][j] = dp[0][j - 1] + s2.charAt(j - 1);
        }
        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j] + s1.charAt(i - 1), dp[i][j - 1] + s2.charAt(j - 1));
                }
            }
        }
        return dp[s1.length()][s2.length()];
    }
}

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

#medium
Задача: 767. Reorganize String

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

Верните любую возможную перестановку строки s или верните "", если это невозможно.

Пример:

Input: s = "aab"
Output: "aba"

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

1⃣Инициализируйте пустой список ans для хранения переставленных символов. Создайте приоритетную очередь pq, используя структуру данных кучи. Каждый элемент в pq — это кортеж, содержащий количество символов и сам символ. Приоритетная очередь упорядочена так, что элементы с большим количеством имеют более высокий приоритет.

2⃣Извлеките элемент с наивысшим приоритетом из pq. Присвойте его количество и символ переменным count_first и char_first соответственно. Если ans пуст или текущий символ char_first отличается от последнего символа в ans, добавьте char_first в ans. Если количество char_first не равно нулю, уменьшите его на один. Если обновленное количество больше нуля, поместите его обратно в pq. Перейдите к следующей итерации.

3⃣В противном случае, если char_first совпадает с последним символом в ans, нужно выбрать другой символ. Если pq пуста, верните пустую строку, так как переставить символы невозможно. Извлеките следующий элемент из pq, присвоив его количество и символ переменным count_second и char_second соответственно. Добавьте char_second в ans. Если количество char_second не равно нулю, уменьшите его на один. Если обновленное количество больше нуля, поместите его обратно в pq. Наконец, поместите оригинальный char_first обратно в pq. Верните переставленные символы как строку, объединив элементы в ans.

😎 Решение:

import java.util.*;

class Solution {
    public String reorganizeString(String s) {
        int[] charCounts = new int[26];
        for (char c : s) {
            charCounts[c - 'a']++;
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        for (int i = 0; i < 26; i++) {
            if (charCounts[i] > 0) {
                pq.add(new int[]{charCounts[i], i + 'a'});
            }
        }
        
        StringBuilder result = new StringBuilder();
        while (!pq.isEmpty()) {
            int[] first = pq.poll();
            if (result.length() == 0 || first[1] != result.charAt(result.length() - 1)) {
                result.append((char)first[1]);
                if (--first[0] > 0) {
                    pq.add(first);
                }
            } else {
                if (pq.isEmpty()) {
                    return "";
                }
                int[] second = pq.poll();
                result.append((char)second[1]);
                if (--second[0] > 0) {
                    pq.add(second);
                }
                pq.add(first);
            }
        }

        return result.toString();
    }
}

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

#medium
Задача: 713. Subarray Product Less Than K

Если задан массив целых чисел nums и целое число k, верните количество смежных подмассивов, в которых произведение всех элементов в подмассиве строго меньше k.

Пример:

Input: nums = [10,5,2,6], k = 100
Output: 8

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

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

2⃣Перемещайте правый указатель по массиву и умножайте текущий элемент на текущее произведение. Если произведение становится больше или равно k, перемещайте левый указатель, уменьшая произведение до тех пор, пока оно снова не станет меньше k.

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

😎 Решение:

public class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) return 0;
        int product = 1, count = 0, left = 0;
        for (int right = 0; right < nums.length; right++) {
            product *= nums[right];
            while (product >= k) {
                product /= nums[left];
                left++;
            }
            count += right - left + 1;
        }
        return count;
    }
}

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

#medium
Задача: 714. Best Time to Buy and Sell Stock with Transaction Fee

Вам дан массив prices, где prices[i] - это цена данной акции в i-й день, и целое число fee, представляющее собой комиссию за сделку. Найдите максимальную прибыль, которую вы можете получить. Вы можете совершить сколько угодно сделок, но за каждую сделку вам придется заплатить комиссию. Примечание: Вы не можете совершать несколько сделок одновременно (то есть вы должны продать акции, прежде чем купить их снова). Комиссия за сделку взимается только один раз за каждую покупку и продажу акций.

Пример:

Input: prices = [1,3,2,8,4,9], fee = 2
Output: 8

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

1⃣Инициализируйте две переменные: cash, представляющую максимальную прибыль без наличия акций, и hold, представляющую максимальную прибыль с наличием акций.

2⃣Пройдите по каждому элементу массива prices и обновите значения cash и hold, используя текущую цену и комиссию.

3⃣Верните значение cash, которое будет максимальной прибылью без наличия акций.

😎 Решение:

public class Solution {
    public int maxProfit(int[] prices, int fee) {
        int cash = 0, hold = -prices[0];
        for (int price : prices) {
            cash = Math.max(cash, hold + price - fee);
            hold = Math.max(hold, cash - price);
        }
        return cash;
    }
}

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