Java | LeetCode

«Где я пригодился»: мини-док из 5 серий от Яндекса ✨ Героями мини-сериала стали разработчики, менеджеры и инженеры Яндекса, которые выросли в маленьких городах и посёлках. В историях их детства — гаражи и огороды, шашки и футбол, Алтай и Калужская область. И всё же у героев есть кое-что общее — желание постоянно выходить за рамки, спрашивать себя: «а что, если?..». Разбираемся, как они стали именно такими людьми. Смотреть #реклама yandex.ru О рекламодателе

Задача: 836. Rectangle Overlap Сложность: easy Прямоугольник, выровненный по осям, представляется в виде списка [x1, y1, x2, y2], где (x1, y1) — координата его нижнего левого угла, а (x2, y2) — координата его верхнего правого угла. Его верхняя и нижняя грани параллельны оси X, а левая и правая грани параллельны оси Y. Два прямоугольника перекрываются, если площадь их пересечения положительна. Для ясности, два прямоугольника, которые касаются только в углу или по краям, не перекрываются. Даны два выровненных по осям прямоугольника rec1 и rec2, вернуть true, если они перекрываются, в противном случае вернуть false. Пример:

Input: rec1 = [0,0,2,2], rec2 = [1,1,3,3]
Output: true

👨‍💻 Алгоритм: 1⃣Рассчитайте ширину пересечения: пересечение по оси x положительно, если min(rec1[2], rec2[2]) > max(rec1[0], rec2[0]). 2⃣Рассчитайте высоту пересечения: пересечение по оси y положительно, если min(rec1[3], rec2[3]) > max(rec1[1], rec2[1]). 3⃣Если и ширина, и высота пересечения положительны, прямоугольники перекрываются. 😎 Решение:

class Solution {
    public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
        return (Math.min(rec1[2], rec2[2]) > Math.max(rec1[0], rec2[0]) &&
                Math.min(rec1[3], rec2[3]) > Math.max(rec1[1], rec2[1]));
    }
}

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

Чиллер отключается в жару? Адиабатическое предохлаждение: давление в норме, экономия до 30% энергии Получить консультацию #реклама coolingpad.ru О рекламодателе

Задача: 947. Most Stones Removed with Same Row or Column Сложность: medium Учитывая массив stones длины n, где stones[i] = [xi, yi] представляет местоположение i-го камня, верните наибольшее возможное количество камней, которые могут быть удалены. Пример:

Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5

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

import java.util.*;

class Solution {
    public int removeStones(int[][] stones) {
        Map<Integer, Integer> parent = new HashMap<>();
        
        int find(int x) {
            if (!parent.containsKey(x)) {
                parent.put(x, x);
            }
            if (parent.get(x) != x) {
                parent.put(x, find(parent.get(x)));
            }
            return parent.get(x);
        }
        
        void union(int x, int y) {
            parent.put(find(x), find(y));
        }
        
        for (int[] stone : stones) {
            union(stone[0], ~stone[1]);
        }
        
        Set<Integer> uniqueRoots = new HashSet<>();
        for (int key : parent.keySet()) {
            uniqueRoots.add(find(key));
        }
        
        return stones.length - uniqueRoots.size();
    }
}

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

Задача: 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;
    }
}

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

Задача: 1353. Maximum Number of Events That Can Be Attended Сложность: medium Дан массив событий, где events[i] = [startDayi, endDayi]. Каждое событие i начинается в startDayi и заканчивается в endDayi. Вы можете посетить событие i в любой день d, где startDayi <= d <= endDayi. Вы можете посещать только одно событие в любой момент времени d. Верните максимальное количество событий, которые вы можете посетить. Пример:

Input: events= [[1,2],[2,3],[3,4],[1,2]]
Output: 4

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

import java.util.*;

public class Solution {
    public int maxEvents(int[][] events) {
        Arrays.sort(events, Comparator.comparingInt(e -> e[1]));
        Set<Integer> visitedDays = new HashSet<>();
        int count = 0;
        
        for (int[] event : events) {
            for (int day = event[0]; day <= event[1]; day++) {
                if (!visitedDays.contains(day)) {
                    visitedDays.add(day);
                    count++;
                    break;
                }
            }
        }
        return count;
    }
}

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

Домашняя школа для 5-11 классов. Онлайн-обучение! ⚡Профориентологи помогут ученикам сделать осознанный и подходящий выбор вуза и будущей профессии, исследуя истинные желания, таланты и интересы. ⚡Наши психологи поддерживают эмоциональное благополучие учеников, помогая им справляться со стрессом, трудностями в учёбе, в познании себя и мира вокруг. ⚡Родители и дети не останутся в вакууме, мы создаём пространство, где учёба сочетается с живым общением и новыми открытиями — мы всегда рядом! Узнать больше #реклама 16+ s.salebot.pro О рекламодателе

Задача: 200. Number of Islands Сложность: medium Дана двумерная бинарная сетка размером m x n, представляющая карту из '1' (земля) и '0' (вода). Верните количество островов. Остров окружён водой и образуется путём соединения соседних земель горизонтально или вертикально. Можно предположить, что все четыре края сетки окружены водой. Пример:

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

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

class Solution {
    void dfs(char[][] grid, int r, int c) {
        int nr = grid.length;
        int nc = grid[0].length;

        if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
            return;
        }

        grid[r][c] = '0';
        dfs(grid, r - 1, c);
        dfs(grid, r + 1, c);
        dfs(grid, r, c - 1);
        dfs(grid, r, c + 1);
    }

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int nr = grid.length;
        int nc = grid[0].length;
        int num_islands = 0;
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    ++num_islands;
                    dfs(grid, r, c);
                }
            }
        }

        return num_islands;
    }
}

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

Задача: 1207. Unique Number of Occurrences Сложность: easy Дан массив целых чисел arr. Верните true, если количество вхождений каждого значения в массиве уникально, или false в противном случае. Пример:

Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.

👨‍💻 Алгоритм: 1⃣Сохраните частоты элементов массива arr в хэш-таблице freq. 2⃣Итерируйтесь по хэш-таблице freq и вставьте частоты всех уникальных элементов массива arr в хэш-набор freqSet. 3⃣Верните true, если размер хэш-набора freqSet равен размеру хэш-таблицы freq, иначе верните false. 😎 Решение:

class Solution {
    public boolean uniqueOccurrences(int[] arr) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : arr) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        
        Set<Integer> freqSet = new HashSet<>(freq.values());
        
        return freq.size() == freqSet.size();
    }
}

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

Подготовка к вступительным экзаменам в ШАД 120+ поступивших в ШАД. Преподаватели МГУ. Гарантия результата. Вы поступите в ШАД, магистратуру или мы зачислим Вас на следующий поток бесплатно Узнать больше #реклама 16+ shadhelper.com О рекламодателе

Задача: 643. Maximum Average Subarray I Сложность: easy Вам дан целочисленный массив nums, состоящий из n элементов, и целое число k. Найдите смежный подмассив, длина которого равна k и который имеет максимальное среднее значение, и верните это значение. Принимается любой ответ с погрешностью вычислений менее 10-5. Пример:

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000

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

public class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int currentSum = 0;
        for (int i = 0; i < k; i++) {
            currentSum += nums[i];
        }
        int maxSum = currentSum;
        
        for (int i = k; i < nums.length; i++) {
            currentSum += nums[i] - nums[i - k];
            maxSum = Math.max(maxSum, currentSum);
        }
        
        return (double) maxSum / k;
    }
}

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

Задача: 868. Binary Gap Сложность: easy Дано положительное целое число n, найдите и верните наибольшее расстояние между любыми двумя соседними единицами в двоичном представлении числа n. Если нет двух соседних единиц, верните 0. Две единицы считаются соседними, если их разделяют только нули (возможно, никаких нулей нет). Расстояние между двумя единицами — это абсолютная разница между их позициями в битовом представлении. Например, две единицы в "1001" имеют расстояние 3. Пример:

Input: n = 22
Output: 2
Explanation: 22 in binary is "10110".
The first adjacent pair of 1's is "10110" with a distance of 2.
The second adjacent pair of 1's is "10110" with a distance of 1.
The answer is the largest of these two distances, which is 2.
Note that "10110" is not a valid pair since there is a 1 separating the two 1's underlined.

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

class Solution {
    public int binaryGap(int N) {
        int[] A = new int[32];
        int t = 0;
        for (int i = 0; i < 32; ++i)
            if (((N >> i) & 1) != 0)
                A[t++] = i;

        int ans = 0;
        for (int i = 0; i < t - 1; ++i)
            ans = Math.max(ans, A[i+1] - A[i]);
        return ans;
    }
}

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

Задача: 972. Equal Rational Numbers Сложность: hard Даны две строки s и t, каждая из которых представляет собой неотрицательное рациональное число. Вернуть true тогда и только тогда, когда они представляют одно и то же число. Строки могут использовать скобки для обозначения повторяющейся части рационального числа. Рациональное число может быть представлено с использованием до трех частей: <ЦелаяЧасть>, <НеповторяющаясяЧасть> и <ПовторяющаясяЧасть>. Число будет представлено одним из следующих трех способов: <ЦелаяЧасть> Например, 12, 0 и 123. <ЦелаяЧасть><.><НеповторяющаясяЧасть> Например, 0.5, 1., 2.12 и 123.0001. <ЦелаяЧасть><.><НеповторяющаясяЧасть><(><ПовторяющаясяЧасть><)> Например, 0.1(6), 1.(9), 123.00(1212). Повторяющаяся часть десятичного разложения обозначается в круглых скобках. Например: 1/6 = 0.16666666... = 0.1(6) = 0.1666(6) = 0.166(66). Пример:

Input: s = "0.(52)", t = "0.5(25)"
Output: true
Explanation: Because "0.(52)" represents 0.52525252..., and "0.5(25)" represents 0.52525252525..... , the strings represent the same number.

👨‍💻 Алгоритм: 1⃣Преобразование дроби. Определите и изолируйте повторяющуюся часть дроби. Преобразуйте строку, представляющую число, в выражение вида S=x/(10^k-1), где x — повторяющаяся часть, а k — её длина. 2⃣Вычисление геометрической суммы. Преобразуйте повторяющуюся часть в сумму вида S=x*(r/(1-r)), где r = 10^(-k). Найдите значение дроби для повторяющейся части, используя формулу геометрической прогрессии. 3⃣Обработка неповторяющейся части. Определите значение неповторяющейся части дроби как обычное число. Объедините результаты для повторяющейся и неповторяющейся частей для получения итогового значения. 😎 Решение:

class Employee {
    public int id;
    public int importance;
    public List<Integer> subordinates;
}

class Solution {
    Map<Integer, Employee> emap;
    
    public int getImportance(List<Employee> employees, int queryid) {
        emap = new HashMap<>();
        for (Employee e : employees) {
            emap.put(e.id, e);
        }
        return dfs(queryid);
    }
    
    public int dfs(int eid) {
        Employee employee = emap.get(eid);
        int ans = employee.importance;
        for (Integer subid : employee.subordinates) {
            ans += dfs(subid);
        }
        return ans;
    }
}

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

Задача: 1135. Connecting Cities With Minimum Cost Сложность: medium Есть n городов, пронумерованных от 1 до n. Вам даны целое число n и массив connections, где connections[i] = [xi, yi, costi] указывает, что стоимость соединения города xi и города yi (двунаправленное соединение) равна costi. Верните минимальную стоимость для соединения всех n городов так, чтобы между каждой парой городов был хотя бы один путь. Если невозможно соединить все n городов, верните -1. Стоимость - это сумма использованных стоимостей соединений. Пример:

Input: n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]
Output: 6
Explanation: Choosing any 2 edges will connect all cities so we choose the minimum 2.

👨‍💻 Алгоритм: 1⃣Сортировка рёбер: Отсортируйте все соединения (рёбра) в графе по их весам (стоимости) в порядке возрастания. 2⃣Итерация по рёбрам и объединение: Используйте структуру данных Disjoint Set (Union-Find) для проверки циклов и объединения поддеревьев. Для каждого ребра проверьте, принадлежат ли его концы разным поддеревьям, и если да, объедините их, добавив ребро в минимальное остовное дерево (MST). 3⃣Проверка соединённости: Подсчитайте количество рёбер в MST. Если оно меньше n-1, верните -1, так как соединить все города невозможно. Иначе верните суммарную стоимость рёбер в MST. 😎 Решение:

class DisjointSet {
    private int[] parents;

    public void Union(int a, int b) {
        int rootA = Find(a);
        int rootB = Find(b);
        if (rootA == rootB) return;
        this.parents[rootB] = rootA;
    }

    public int Find(int a) {
        while (a != this.parents[a]) {
            a = this.parents[a];
        }
        return a;
    }

    public boolean isInSameGroup(int a, int b) {
        return Find(a) == Find(b);
    }

    public DisjointSet(int N) {
        this.parents = new int[N + 1];
        for (int i = 1; i <= N; ++i) {
            this.parents[i] = i;
        }
    }
}

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

Создание кроссплатформенного GUI на Rust ⚡Electron тяжёл, а Rust + Tauri дают лёгкое, быстрое и безопасное десктоп-приложение для Windows, macOS и Linux. Tauri берёт HTML/CSS/JS для интерфейса и мощь Rust для бэкенда. 📅 23 сентября в 20:00 на открытом вебинаре разберём полный цикл создания GUI на Rust с Tauri: организация проекта, логика на Rust и её связь с интерфейсом, работа с данными, безопасные системные вызовы через permissions и capabilities в Tauri 2, асинхронность, сборка, отладка и лучшие практики. 💻 Вебинар не для тех, кто ждёт «скопируй-вставь». Подойдёт фронтенд-разработчикам, программистам, интересующимся Rust, и энтузиастам, уставшим от Electron. ✅ После вебинара вы сможете создавать десктоп-приложения на Rust, связывать логику с UI, настраивать безопасность и собирать готовое приложение. Записаться #реклама 16+ otus.ru О рекламодателе

Задача: 1054. Distant Barcodes Сложность: medium На складе имеется ряд штрих-кодов, где i-й штрих-код - barcodes[i]. Переставьте штрих-коды так, чтобы два соседних штрих-кода не были одинаковыми. Вы можете вернуть любой ответ, и гарантируется, что ответ существует. Пример:

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

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

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

public class Solution {
    public int[] rearrangeBarcodes(int[] barcodes) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int barcode : barcodes) {
            count.put(barcode, count.getOrDefault(barcode, 0) + 1);
        }

        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
            maxHeap.add(new int[]{entry.getValue(), entry.getKey()});
        }

        int prevFreq = 0, prevBarcode = -1;
        int[] result = new int[barcodes.length];
        int index = 0;

        while (!maxHeap.isEmpty()) {
            int[] entry = maxHeap.poll();
            int freq = entry[0], barcode = entry[1];
            result[index++] = barcode;
            if (prevFreq > 0) {
                maxHeap.add(new int[]{prevFreq, prevBarcode});
            }
            prevFreq = freq - 1;
            prevBarcode = barcode;
        }

        return result;
    }
}

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

Розыгрыш Яндекс Станции уже в боте Любимые блогеры, розыгрыши, новости и анонсы в одном боте! Узнать больше #реклама 16+ refer.id О рекламодателе

Задача: 730. Count Different Palindromic Subsequences Сложность: hard Поскольку ответ может быть очень большим, верните его по модулю 109 + 7. Подпоследовательность строки получается путем удаления из нее нуля или более символов. Последовательность является палиндромной, если она равна последовательности, обращенной назад. Две последовательности a1, a2, ... и b1, b2, ... различны, если существует некоторое i, для которого ai != bi. Пример:

Input: s = "bccb"
Output: 6

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

public class Solution {
    public int countPalindromicSubsequences(String s) {
        int MOD = 1000000007;
        int n = s.length();
        int[][] dp = new int[n][n];

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

        for (int length = 2; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                if (s.charAt(i) == s.charAt(j)) {
                    int l = i + 1, r = j - 1;
                    while (l <= r && s.charAt(l) != s.charAt(i)) l++;
                    while (l <= r && s.charAt(r) != s.charAt(j)) r--;
                    if (l > r) {
                        dp[i][j] = dp[i + 1][j - 1] * 2 + 2;
                    } else if (l == r) {
                        dp[i][j] = dp[i + 1][j - 1] * 2 + 1;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1] * 2 - dp[l + 1][r - 1];
                    }
                } else {
                    dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1];
                }
                dp[i][j] = (dp[i][j] + MOD) % MOD;
            }
        }

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

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

Задача: 815. Bus Routes Сложность: hard Дан массив routes, представляющий автобусные маршруты, где routes[i] - это автобусный маршрут, который i-й автобус повторяет бесконечно. Например, если routes[0] = [1, 5, 7], это означает, что 0-й автобус путешествует в последовательности 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... бесконечно. Вы начинаете на автобусной остановке source (вы изначально не находитесь в автобусе) и хотите добраться до автобусной остановки target. Перемещаться между автобусными остановками можно только на автобусах. Верните наименьшее количество автобусов, которые вам нужно взять, чтобы доехать от source до target. Верните -1, если это невозможно. Пример:

Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output: 2
Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.

👨‍💻 Алгоритм: 1⃣Верните 0, если source и target совпадают. Инициализируйте пустую карту adjList, чтобы хранить ребра, где ключ - это автобусная остановка, а значение - список целых чисел, обозначающих индексы маршрутов, которые имеют эту остановку. Инициализируйте пустую очередь q и неупорядоченное множество vis, чтобы отслеживать посещенные маршруты. Вставьте начальные маршруты в очередь q и отметьте их посещенными в vis. 2⃣Итерация по очереди, пока она не пуста: извлеките маршрут из очереди, итерируйтесь по остановкам в маршруте. Если остановка равна target, верните busCount. В противном случае, итерируйтесь по маршрутам для этой остановки в карте adjList, добавьте непосещенные маршруты в очередь и отметьте их посещенными. 3⃣Верните -1 после завершения обхода в ширину (BFS). 😎 Решение:

class Solution {
    public int numBusesToDestination(int[][] routes, int source, int target) {
        if (source == target) return 0;

        Map<Integer, List<Integer>> adjList = new HashMap<>();
        for (int route = 0; route < routes.length; route++) {
            for (int stop : routes[route]) {
                adjList.computeIfAbsent(stop, k -> new ArrayList<>()).add(route);
            }
        }

        Queue<Integer> q = new LinkedList<>();
        Set<Integer> vis = new HashSet<>();
        for (int route : adjList.getOrDefault(source, Collections.emptyList())) {
            q.add(route);
            vis.add(route);
        }

        int busCount = 1;
        while (!q.isEmpty()) {
            int size = q.size();

            for (int i = 0; i < size; i++) {
                int route = q.poll();

                for (int stop : routes[route]) {
                    if (stop == target) {
                        return busCount;
                    }

                    for (int nextRoute : adjList.getOrDefault(stop, Collections.emptyList())) {
                        if (!vis.contains(nextRoute)) {
                            vis.add(nextRoute);
                            q.add(nextRoute);
                        }
                    }
                }
            }
            busCount++;
        }
        return -1;
    }

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

#medium Задача: 714. Best Time to Buy and Sell Stock with Transaction Fee Сложность: medium Вам дан массив 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;
    }
}

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