Java | LeetCode

Задача: 83. Remove Duplicates from Sorted List Сложность: easy Дана голова отсортированного связного списка. Удалите все дубликаты таким образом, чтобы каждый элемент появлялся только один раз. Верните также отсортированный связный список. Пример:

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

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

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode current = head;
        while (current != null && current.next != null) {
            if (current.next.val == current.val) {
                current.next = current.next.next;
            } else {
                current = current.next;
            }
        }
        return head;
    }
}

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

WARMMET - официальный сайт производителя радиаторов! Из мира громоздких батарей к современным решениям! Рассказываем, по каким критериям выбирать дизайн-радиатор: Материал Рекомендуем стальные радиаторы. Они подходят для частных и многоквартирных домов. За счёт прочности их срок службы свыше 30 лет. Основные габариты Высота радиатора и расстояние между трубами тоже важно при выборе. Так вы сможете оценить не только внешний вид, но и возможность установить их в вашем помещении. Размещение Радиатор должен находиться от пола на расстоянии от 70 до 120 мм. Зазор до подоконника составлять не менее 80 мм. Прибор должен греть воздух, а не примыкающие к нему предметы. Пусть специалисты компании WARMMET будут вашими проводниками в мир красивых и современных водяных систем отопления! Перейти на сайт #реклама warmmet.ru О рекламодателе

Задача: 115. Distinct Subsequences Сложность: hard "Даны две строки s и t. Верните количество различных подпоследовательностей строки s, которые равны строке t. Тестовые примеры сгенерированы таким образом, что ответ укладывается в 32-битное целое число со знаком." Пример:

Input: s = "rabbbit", t = "rabbit"
Output: 3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from s.
rabbbit
rabbbit
rabbbit

👨‍💻 Алгоритм: 1⃣Определите функцию с названием recurse, которая принимает два целочисленных значения i и j. Первое значение представляет текущий обрабатываемый символ в строке S, а второе - текущий символ в строке T. Инициализируйте словарь под названием memo, который будет кэшировать результаты различных вызовов рекурсии.** 2⃣Проверьте базовый случай. Если одна из строк закончилась, возвращается 0 или 1 в зависимости от того, удалось ли обработать всю строку T или нет. Есть ещё один базовый случай, который следует рассмотреть. Если оставшаяся длина строки S меньше, чем у строки T, то сoвпадение невозможно. Если это обнаруживается, то рекурсия также обрезается и возвращается 0.** 3⃣Затем проверяем, существует ли текущая пара индексов в нашем словаре. Если да, то просто возвращаем сохранённое/кэшированное значение. Если нет, то продолжаем обычную обработку. Сравниваем символы s[i] и t[j]. Сохраняем результат вызова recurse(i + 1, j) в переменную. Как упоминалось ранее, результат этой рекурсии необходим, независимо от совпадения символов. Если символы совпадают, добавляем к переменной результат вызова recurse(i + 1, j + 1). Наконец, сохраняем значение этой переменной в словаре с ключом (i, j) и возвращаем это значение в качестве ответа.** 😎 Решение:

class Solution {
    private HashMap<Pair<Integer, Integer>, Integer> memo;

    private int recurse(String s, String t, int i, int j) {
        int M = s.length();
        int N = t.length();

        if (i == M || j == N || M - i < N - j) {
            return j == t.length() ? 1 : 0;
        }

        Pair<Integer, Integer> key = new Pair<Integer, Integer>(i, j);

        if (this.memo.containsKey(key)) {
            return this.memo.get(key);
        }

        int ans = this.recurse(s, t, i + 1, j);

        if (s.charAt(i) == t.charAt(j)) {
            ans += this.recurse(s, t, i + 1, j + 1);
        }

        this.memo.put(key, ans);
        return ans;
    }

    public int numDistinct(String s, String t) {
        this.memo = new HashMap<Pair<Integer, Integer>, Integer>();
        return this.recurse(s, t, 0, 0);
    }
}

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

Профессия «Аналитик данных». Рассрочка 0% Освойте высокооплачиваемую IT-профессию с нуля за 6 месяцев. Выдаём диплом, помогаем с трудоустройством. Excel, SQL, PowerBI, Python. Преимущества обучения в Академии Eduson: 🎓 официальный государственный диплом 🎓если после курса не найдёте работу — мы возвращаем деньги и это зафиксировано в договоре 🎓 рассрочка 0% на 24 мес., то есть без переплаты 🎓 бессрочный доступ к лекциям и материалам, которые продолжают обновляться 🎓 личный куратор с Вами на связи Начните обучаться онлайн и получать стабильный доход уже во время обучения! Узнать больше Финансовые услуги оказывает: ПАО "Сбербанк", АО "Тинькофф Банк" и др.. #реклама 16+ eduson.academy О рекламодателе

Задача: 1203. Sort Items by Groups Respecting Dependencies Сложность: hard Есть n предметов, каждый из которых принадлежит нулевой или одной из m групп, где group[i] — это группа, к которой принадлежит i-й предмет, и равно -1, если i-й предмет не принадлежит никакой группе. Предметы и группы имеют индексацию с нуля. Группа может не иметь ни одного предмета. Верните отсортированный список предметов таким образом: Предметы, принадлежащие одной группе, расположены рядом друг с другом в отсортированном списке. Существуют некоторые отношения между этими предметами, где beforeItems[i] — это список, содержащий все предметы, которые должны быть перед i-м предметом в отсортированном массиве (слева от i-го предмета). Верните любое решение, если существует более одного решения, и верните пустой список, если решения не существует. Пример:

Input: n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]
Output: [6,3,4,1,5,2,0,7]

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

class Solution {
    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        int groupId = m;
        for (int i = 0; i < n; i++) if (group[i] == -1) group[i] = groupId++;

        Map<Integer, List<Integer>> itemGraph = new HashMap<>();
        Map<Integer, List<Integer>> groupGraph = new HashMap<>();
        int[] itemIndegree = new int[n], groupIndegree = new int[groupId];
        for (int i = 0; i < n; i++) itemGraph.put(i, new ArrayList<>());
        for (int i = 0; i < groupId; i++) groupGraph.put(i, new ArrayList<>());

        for (int curr = 0; curr < n; curr++) {
            for (int prev : beforeItems.get(curr)) {
                itemGraph.get(prev).add(curr);
                itemIndegree[curr]++;
                if (group[curr] != group[prev]) {
                    groupGraph.get(group[prev]).add(group[curr]);
                    groupIndegree[group[curr]]++;
                }
            }
        }

        List<Integer> itemOrder = topologicalSort(itemGraph, itemIndegree);
        List<Integer> groupOrder = topologicalSort(groupGraph, groupIndegree);
        if (itemOrder.isEmpty() || groupOrder.isEmpty()) return new int[0];

        Map<Integer, List<Integer>> orderedGroups = new HashMap<>();
        for (int item : itemOrder) orderedGroups.computeIfAbsent(group[item], k -> new ArrayList<>()).add(item);

        List<Integer> answerList = new ArrayList<>();
        for (int groupIndex : groupOrder) answerList.addAll(orderedGroups.getOrDefault(groupIndex, new ArrayList<>()));

        return answerList.stream().mapToInt(Integer::intValue).toArray();
    }

    private List<Integer> topologicalSort(Map<Integer, List<Integer>> graph, int[] indegree) {
        List<Integer> visited = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        for (int key : graph.keySet()) if (indegree[key] == 0) stack.add(key);

        while (!stack.isEmpty()) {
            int curr = stack.pop();
            visited.add(curr);
            for (int next : graph.get(curr)) if (--indegree[next] == 0) stack.add(next);
        }

        return visited.size() == graph.size() ? visited : new ArrayList<>();
    }
}

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

Открытые онлайн-уроки в Центральном университете 🎓 Тебя ждут лекции от ведущих преподавателей Центрального университета, а также возможность попасть на буткемп, сертификат о прохождении и тиражный мерч. 💻 Последняя лекция 9 июля — можно подключиться в любой момент Не упусти шанс — регистрируйся уже сейчас! Записаться онлайн #реклама 16+ event.centraluniversity.ru О рекламодателе

Задача: 527. Word Abbreviation Сложность: hard Дано массив уникальных строк words, верните минимально возможные сокращения для каждого слова. Правила сокращения строки следующие: Первоначальное сокращение для каждого слова: первый символ, затем количество символов между первым и последним символом, затем последний символ. Если более одного слова имеют одинаковое сокращение, выполните следующее: Увеличьте префикс (символы в первой части) каждого из их сокращений на 1. Например, начнем с слов ["abcdef", "abndef"], оба изначально сокращены как "a4f". Последовательность операций будет следующей: ["a4f", "a4f"] -> ["ab3f", "ab3f"] -> ["abc2f", "abn2f"]. Эта операция повторяется до тех пор, пока каждое сокращение не станет уникальным. В конце, если сокращение не сделало слово короче, оставьте его в исходном виде. Пример:

Input: words = ["like","god","internal","me","internet","interval","intension","face","intrusion"]
Output: ["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]

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

class Solution {
    public List<String> wordsAbbreviation(List<String> words) {
        int N = words.size();
        String[] ans = new String[N];
        int[] prefix = new int[N];

        for (int i = 0; i < N; ++i)
            ans[i] = abbrev(words.get(i), 0);

        for (int i = 0; i < N; ++i) {
            while (true) {
                Set<Integer> dupes = new HashSet();
                for (int j = i+1; j < N; ++j)
                    if (ans[i].equals(ans[j]))
                        dupes.add(j);

                if (dupes.isEmpty()) break;
                dupes.add(i);
                for (int k: dupes)
                    ans[k] = abbrev(words.get(k), ++prefix[k]);
            }
        }

        return Arrays.asList(ans);
    }

    public String abbrev(String word, int i) {
        int N = word.length();
        if (N - i <= 3) return word;
        return word.substring(0, i+1) + (N - i - 2) + word.charAt(N-1);
    }
}

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

Задача: 1267. Count Servers that Communicate Сложность: medium На двумерной плоскости имеется n точек с целочисленными координатами points[i] = [xi, yi]. Верните минимальное время в секундах для посещения всех точек в порядке, заданном точками. Вы можете перемещаться по следующим правилам: за 1 секунду вы можете либо: переместиться по вертикали на одну единицу, по горизонтали на одну единицу, либо по диагонали sqrt(2) единиц (другими словами, переместиться на одну единицу по вертикали и на одну единицу по горизонтали за 1 секунду). Вы должны посетить точки в том же порядке, в котором они появляются в массиве. Вы можете проходить через точки, которые появляются позже в порядке, но они не считаются за посещение. Пример:

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

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

public class Solution {
    public int countServers(int[][] grid) {
        int[] rows = new int[grid.length];
        int[] cols = new int[grid[0].length];

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    rows[i]++;
                    cols[j]++;
                }
            }
        }

        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1 && (rows[i] > 1 || cols[j] > 1)) {
                    count++;
                }
            }
        }

        return count;
    }
}

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

Задача: 790. Domino and Tromino Tiling Сложность: medium У вас есть два типа плиток: домино размером 2 x 1 и тромино. Вы можете вращать эти фигуры. Дано целое число n. Верните количество способов выложить плитками доску размером 2 x n. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7. При укладке каждая клетка должна быть покрыта плиткой. Две укладки считаются разными, если и только если есть две 4-направленно смежные клетки на доске, такие, что в одной укладке обе клетки заняты плиткой, а в другой - нет. Пример:

Input: n = 3
Output: 5
Explanation: The five different ways are show above.

👨‍💻 Алгоритм: 1⃣Начнем с f(n) и далее спустимся до базовых случаев, f(1), f(2) и p(2). Используйте те же определения для f и p из раздела Обзор. f(k): количество способов полностью покрыть доску шириной k. p(k): количество способов частично покрыть доску шириной k. Рекурсивные вызовы будут использовать результаты подзадач и базовых случаев, чтобы помочь нам получить окончательный результат, f(n). 2⃣Условие остановки для рекурсивных вызовов - когда k достигает базового случая (т.е. k <= 2). Значения для базовых случаев будут возвращены напрямую, вместо того чтобы делать дополнительные рекурсивные вызовы. f(1)=1, f(2)=2, p(2)=1. Чтобы избежать повторных вычислений, мы будем использовать 2 хэшмапы (f_cache и p_cache) для хранения рассчитанных значений для f и p. В Python встроенный декоратор @cache автоматически поддерживает эти хэшмапы для нас. 3⃣Если k больше 2, мы будем делать рекурсивные вызовы к f и p в соответствии с переходной функцией: f(k) = f(k−1) + f(k−2) + 2 * p(k−1), p(k) = p(k−1) + f(k−2). f(n) будет возвращено, как только все рекурсивные вызовы завершатся. 😎 Решение:

import java.util.HashMap;
import java.util.Map;

class Solution {
    private static final int MOD = 1_000_000_007;
    private Map<Integer, Integer> fCache = new HashMap<>();
    private Map<Integer, Integer> pCache = new HashMap<>();

    private int p(int n) {
        if (pCache.containsKey(n)) {
            return pCache.get(n);
        }
        if (n == 2) {
            return 1;
        }
        int result = (p(n - 1) + f(n - 2)) % MOD;
        pCache.put(n, result);
        return result;
    }

    private int f(int n) {
        if (fCache.containsKey(n)) {
            return fCache.get(n);
        }
        if (n <= 2) {
            return n;
        }
        int result = (f(n - 1) + f(n - 2) + 2 * p(n - 1)) % MOD;
        fCache.put(n, result);
        return result;
    }

    public int numTilings(int n) {
        return f(n);
    }
}

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

🔍Тестовое собеседование с Java-разработчиком из Т1 Иннотех уже завтра 4 июня(уже завтра!) в 19:00 по мск приходи онлайн на открытое собеседование, чтобы посмотреть на настоящее интервью на Middle Java-разработчика. Как это будет: 📂 Илья Аров, старший разработчик в Т1, будет задавать реальные вопросы и задачи разработчику-добровольцу 📂 Илья будет комментировать каждый ответ респондента, чтобы дать понять чего от вас ожидает собеседующий на интервью 📂 В конце можно будет задать любой вопрос Илье Это бесплатно. Эфир проходит в рамках менторской программы от ШОРТКАТ для Java-разработчиков, которые хотят повысить свой грейд, ЗП и прокачать скиллы. Переходи в нашего бота, чтобы получить ссылку на эфир → @shortcut_sh_bot Реклама. ООО "ШОРТКАТ", ИНН: 9731139396, erid: 2VtzqwiSNow

Задача: 774. Minimize Max Distance to Gas Station Сложность: hard Вам дан массив целых чисел stations, который представляет позиции автозаправочных станций на оси x. Вам также дано целое число k. Вы должны добавить k новых автозаправочных станций. Вы можете добавлять станции в любое место на оси x, необязательно в целочисленную позицию. Определим penalty() как максимальное расстояние между соседними автозаправочными станциями после добавления k новых станций. Верните наименьшее возможное значение penalty(). Ответы, отличающиеся от фактического ответа не более чем на 10^-6, будут приняты. Пример:

Input: stations = [1,2,3,4,5,6,7,8,9,10], k = 9
Output: 0.50000

👨‍💻 Алгоритм: 1⃣Пусть i-й интервал равен deltas[i] = stations[i+1] - stations[i]. Мы хотим найти dp[n+1][k] как рекурсию. Мы можем поставить x автозаправочных станций в интервал n+1 с наилучшим расстоянием deltas[n+1] / (x+1), затем оставшиеся интервалы можно решить с ответом dp[n][k-x]. Ответ — это минимум среди всех x. 2⃣Из этой рекурсии мы можем разработать решение с использованием динамического программирования. Инициализируем двумерный массив dp, где dp[i][j] будет хранить минимальное возможное значение penalty при добавлении j автозаправочных станций на первые i интервалов. 3⃣Заполняем dp таблицу начиная с базового случая, когда нет добавленных станций. Затем для каждого интервала и количества добавленных станций вычисляем минимальное значение penalty, используя вышеописанную рекурсию. Итоговый ответ будет находиться в dp[n][k], где n — количество интервалов, а k — количество добавляемых станций. 😎 Решение:

class Solution {
    public double minmaxGasDist(int[] stations, int K) {
        int N = stations.length;
        double[] deltas = new double[N-1];
        for (int i = 0; i < N-1; ++i)
            deltas[i] = stations[i+1] - stations[i];

        double[][] dp = new double[N-1][K+1];
        for (int i = 0; i <= K; ++i)
            dp[0][i] = deltas[0] / (i+1);

        for (int p = 1; p < N-1; ++p)
            for (int k = 0; k <= K; ++k) {
                double bns = Double.MAX_VALUE;
                for (int x = 0; x <= k; ++x)
                    bns = Math.min(bns, Math.max(deltas[p] / (x+1), dp[p-1][k-x]));
                dp[p][k] = bns;
            }

        return dp[N-2][K];
    }
}

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

Крупнейший университет искусственного интеллекта Приглашаем на бесплатный курс по искусственному интеллекту! Мы подготовили для тебя 5 занятий по теме «Разработка нейро-сотрудников на GPT». Пройди регистрацию для получения полного бесплатного доступа к курсу. ✨ 8 000+ студентов со всего мира ✨ 600+ AI-проектов, созданных студентами ✨ Сборная Университета — победители крупнейших AI-хакатонов России ✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие) ✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие) Будем рады видеть тебя в наших рядах! Узнать больше #реклама 16+ neural-university.ru О рекламодателе

Задача: 689. Maximum Sum of 3 Non-Overlapping Subarrays Сложность: hard Дан целочисленный массив nums и целое число k. Найдите три непересекающихся подмассива длины k с максимальной суммой и верните их. Верните результат в виде списка индексов, представляющих начальную позицию каждого интервала (нумерация с 0). Если существует несколько ответов, верните лексикографически наименьший. Пример:

Input: nums = [1,2,1,2,6,7,5,1], k = 2
Output: [0,3,5]
Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5].
We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger.

👨‍💻 Алгоритм: 1⃣Предположим, что фиксирован j. Нам нужно узнать на интервалах i∈[0,j−k] и l∈[j+k,len(W)−1], где наибольшее значение W[i] (и соответственно W[l]) встречается первым (то есть, с наименьшим индексом). 2⃣Мы можем решить эту задачу с помощью динамического программирования. Например, если мы знаем, что i - это место, где наибольшее значение W[i] встречается первым на [0,5], то на [0,6] первое появление наибольшего W[i] должно быть либо i, либо 6. Если, скажем, 6 лучше, тогда мы устанавливаем best = 6. В конце left[z] будет первым вхождением наибольшего значения W[i] на интервале i∈[0,z], а right[z] будет таким же, но на интервале i∈[z,len(W)−1]. 3⃣Это означает, что для некоторого выбора j, кандидат на ответ должен быть (left[j - k], j, right[j + k]). Мы выбираем кандидата, который дает максимальное значение W[i] + W[j] + W[l]. 😎 Решение:

class Solution {
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int[] W = new int[nums.length - k + 1];
        int currSum = 0;
        for (int i = 0; i < nums.length; i++) {
            currSum += nums[i];
            if (i >= k) {
                currSum -= nums[i - k];
            }
            if (i >= k - 1) {
                W[i - k + 1] = currSum;
            }
        }

        int[] left = new int[W.length];
        int best = 0;
        for (int i = 0; i < W.length; i++) {
            if (W[i] > W[best]) best = i;
            left[i] = best;
        }

        int[] right = new int[W.length];
        best = W.length - 1;
        for (int i = W.length - 1; i >= 0; i--) {
            if (W[i] >= W[best]) {
                best = i;
            }
            right[i] = best;
        }
        
        int[] ans = new int[]{-1, -1, -1};
        for (int j = k; j < W.length - k; j++) {
            int i = left[j - k], l = right[j + k];
            if (ans[0] == -1 || W[i] + W[j] + W[l] > W[ans[0]] + W[ans[1]] + W[ans[2]]) {
                ans[0] = i;
                ans[1] = j;
                ans[2] = l;
            }
        }
        return ans;
    }
}

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

Устали от продакшн-огня, но не хотите уходить из IT? ❤️‍🔥 В автоматизации тестирования не горит и обычно не падает в пятницу вечером. Зато кодить всё ещё нужно. Приходите на вебинар «Автотест на Java и карьера QA-автоматизатора» — в четверг, 5 июня. ▶️▶️ Занять место ▶️ Занятие проводят инженеры QA.GURU, создатели авторской программы по обучению автоматизации. Что будет? — узнаете, чем отличается Manual от Automation QA; — разберетесь, куда двигается рынок, и почему автоматизаторы нужны всем. А еще на занятии вы: — напишете свой автотест на Java: логин, поиск в Google шаг за шагом; — подключите Web, Mobile и API в одном проекте. Спикер, Станислав Васенков — QA-инженер, 10+ лет в автоматизации, ex-Head of QAA pflb.ru и автор библиотеки allure-notifications, спикер QA-митапов. Победитель хакатона по автоматизации тестирования от Epam. На нашей встрече Стас покажет, как специалисту с бэкграундом в разработке стартовать в автоматизации. 🎯 Будет интересно,если вы: — Java-разработчик, который хочет уйти от багфиксов, но остаться в IT; — ищете менее выгорающий трек с хорошей техбазой; — хотите понять, как устроена современная автоматизация и где вы в ней можете быть полезны. Участие бесплатное, но нужна регистрация. ▶️ Занять место можно до четверга. Реклама. Рекламодатель: ИП Васенков Станислав Олегович, ИНН 774335827403, erid: 2VtzqxNhbPT

Крупнейший университет искусственного интеллекта Приглашаем на бесплатный однодневный интенсив по AI! Освой искусственный интеллект для профессионального роста: создавай нейросети, автоматизируй бизнес-задачи и зарабатывай на AI-решениях. ✨ 8 000+ студентов со всего мира ✨ 600+ AI-проектов, созданных студентами ✨ Сборная Университета — победители крупнейших AI-хакатонов России ✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие) ✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие) Будем рады видеть тебя в наших рядах! Узнать больше #реклама 16+ neural-university.ru О рекламодателе

Задача: 771. Jewels and Stones Сложность: medium Вам даны строки jewels, представляющие типы камней, которые являются драгоценностями, и stones, представляющие камни, которые у вас есть. Каждый символ в stones является типом камня, который у вас есть. Вы хотите узнать, сколько из камней, которые у вас есть, также являются драгоценностями. Буквы чувствительны к регистру, поэтому "a" считается другим типом камня, чем "A". Пример:

Input: jewels = "aA", stones = "aAAbbbb"
Output: 3

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

class Solution {
    public int numJewelsInStones(String J, String S) {
        int ans = 0;
        for (char s : S.toCharArray())
            for (char j : J.toCharArray())
                if (j == s) {
                    ans++;
                    break;
                }
        return ans;
    }
}

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

Крупнейший университет искусственного интеллекта Приглашаем на бесплатный курс по искусственному интеллекту! 5 занятий по теме «Промпт-инжиниринг». Регистрируйся для получения полного бесплатного доступа к курсу. ✨ 8 000+ студентов со всего мира ✨ 600+ AI-проектов, созданных студентами ✨ Сборная Университета — победители крупнейших AI-хакатонов России ✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие) ✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие) Будем рады видеть тебя в наших рядах! Узнать больше #реклама 16+ neural-university.ru О рекламодателе

Задача: 711. Number of Distinct Islands II Сложность: hard Вам дана двоичная матричная сетка 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];
    }
}

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

Теряете заявки? Сливаются лиды? Хватит сжигать бюджет! AI МОП берет первую линию продаж на себя — сам звонит живым голосом — пишет в мессенджерах — отбирает только теплых и передает менеджерам Без больничных Без текучки Без ошибок ✅ Работает 24/7 ✅ Интегрируется с вашей CRM ✅ Обучается за 30 минут Убивает человеческий фактор в продажах Экономит до 600 000 ₽ в месяц Спасает каждый лид и увеличивает конверсию 📊 AI МОП — это не сотрудник. Это оружие в продажах. 👍 Запускайте сейчас, жмите кнопку "Попробовать" Попробовать #реклама 16+ ai-mop.ru О рекламодателе

Задача: 847. Shortest Path Visiting All Nodes Сложность: hard У вас есть неориентированный связный граф из n узлов, пронумерованных от 0 до n - 1. Вам дан массив graph, где graph[i] — это список всех узлов, соединенных с узлом i ребром. Верните длину кратчайшего пути, который посещает каждый узел. Вы можете начать и закончить в любом узле, вы можете несколько раз посещать узлы и использовать ребра повторно. Пример:

Input: graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
Output: 4
Explanation: One possible path is [0,1,4,2,3]

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

class Solution {
    public int shortestPathLength(int[][] graph) {
        if (graph.length == 1) {
            return 0;
        }
        
        int n = graph.length;
        int endingMask = (1 << n) - 1;
        boolean[][] seen = new boolean[n][endingMask];
        ArrayList<int[]> queue = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            queue.add(new int[] {i, 1 << i});
            seen[i][1 << i] = true;
        }
        
        int steps = 0;
        while (!queue.isEmpty()) {
            ArrayList<int[]> nextQueue = new ArrayList<>();
            for (int i = 0; i < queue.size(); i++) {
                int[] currentPair = queue.get(i);
                int node = currentPair[0];
                int mask = currentPair[1];
                for (int neighbor : graph[node]) {
                    int nextMask = mask | (1 << neighbor);
                    if (nextMask == endingMask) {
                        return 1 + steps;
                    }
                    
                    if (!seen[neighbor][nextMask]) {
                        seen[neighbor][nextMask] = true;
                        nextQueue.add(new int[] {neighbor, nextMask});
                    }
                }
            }
            steps++;
            queue = nextQueue;
        }
        
        return -1;
    }
}

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