Java | LeetCode

🐍💩👩‍💻👩‍💻🧑‍💻🧑‍💻🐧👩‍💻🧑‍💻👩‍💻👩‍💻 В сети начали массово сливать курсы и книги известных онлайн школ по айти Вот отсортированная база с тонной материала (постепенно пополняется): (363 видео, 87 книги) — Python (415 видео, 68 книги) — Frontend (143 видео, 33 книги) — ИБ/Хакинг (352 видео, 89 книги) — С/С++/C# (343 видео, 87 книги) — Java/QA (176 видео, 32 книги) — Git/Linux (174 видео, 91 книги) — DevOps (167 видео, 53 книги) — PHP/1С (227 видео, 83 книги) — SQL/БД (114 видео, 77 книги) — Сисадмин (107 видео, 43 книги) — BA/SA (181 видео, 32 книги) — Go/Rust (167 видео, 43 книги) — Kotlin/Swift (112 видео, 24 книги) — Flutter (137 видео, 93 книги) — DS/ML (113 видео, 82 книги) — GameDev (183 видео, 37 книги) — Дизайн (136 видео, 33 книги) — PM/HR Скачивать ничего не нужно — все выложили в Telegram

Такси для бизнеса. Яндекс Go Оптимизируйте свои расходы и повысьте эффективность бизнеса с Яндекс Go Узнать больше #реклама business.go.yandex О рекламодателе Реклама на Яндексе

Задача: 922. Sort Array By Parity II Сложность: medium Дан массив целых чисел nums, половина целых чисел в нем нечетные, а другая половина - четные. Отсортируйте массив так, чтобы во всех случаях, когда nums[i] нечетный, i был нечетным, а во всех случаях, когда nums[i] четный, i был четным. Верните любой массив ответов, удовлетворяющий этому условию. Пример:

Input: nums = [4,2,5,7]
Output: [4,5,2,7]

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

class Solution {
    public int[] sortArrayByParityII(int[] nums) {
        int[] result = new int[nums.length];
        int evenIdx = 0;
        int oddIdx = 1;
        
        for (int num : nums) {
            if (num % 2 == 0) {
                result[evenIdx] = num;
                evenIdx += 2;
            } else {
                result[oddIdx] = num;
                oddIdx += 2;
            }
        }
        
        return result;
    }
}

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

Задача: 849. Maximize Distance to Closest Person Сложность: medium Вам дан массив, представляющий ряд сидений, где seats[i] = 1 означает, что на i-м месте сидит человек, а seats[i] = 0 означает, что i-е место пусто (индексация с нуля). Есть по крайней мере одно пустое место и по крайней мере один человек, сидящий на месте. Алекс хочет сесть на такое место, чтобы расстояние между ним и ближайшим к нему человеком было максимальным. Верните это максимальное расстояние до ближайшего человека. Пример:

Input: seats = [1,0,0,0,1,0,1]
Output: 2
Explanation: 
If Alex sits in the second open seat (i.e. seats[2]), then the closest person has distance 2.
If Alex sits in any other open seat, the closest person has distance 1.
Thus, the maximum distance to the closest person is 2.

👨‍💻 Алгоритм: 1⃣Следите за prev, занятым местом слева или на текущей позиции i, и future, занятым местом справа или на текущей позиции i. 2⃣Для каждого пустого места i определите ближайшее занятие места как min(i - prev, future - i), с учетом, что i - prev считается бесконечностью, если слева нет занятого места, и future - i считается бесконечностью, если справа нет занятого места. 3⃣Найдите и верните максимальное расстояние до ближайшего занятого места. 😎 Решение:

class Solution {
    public int maxDistToClosest(int[] seats) {
        int N = seats.length;
        int prev = -1, future = 0;
        int ans = 0;

        for (int i = 0; i < N; ++i) {
            if (seats[i] == 1) {
                prev = i;
            } else {
                while (future < N && seats[future] == 0 || future < i)
                    future++;

                int left = prev == -1 ? N : i - prev;
                int right = future == N ? N : future - i;
                ans = Math.max(ans, Math.min(left, right));
            }
        }

        return ans;
    }
}

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

Получи грант до 1,2 млн руб. на обучение в магистратуре 4 офлайн программы, онлайн-магистратура по ML. Гранты до 1,2 млн руб. Стажировки, диплом гос. образца и фокус на твоей карьере в ЦУ Подать заявку #реклама 16+ apply.centraluniversity.ru О рекламодателе

Задача: 1042. Flower Planting With No Adjacent Сложность: medium У вас есть n садов, помеченных от 1 до n, и массив paths, где paths[i] = [xi, yi] описывает двунаправленный путь между садом xi и садом yi. В каждом саду вы хотите посадить один из 4 типов цветов. Все сады имеют не более 3 путей, входящих и выходящих из него. Ваша задача - выбрать тип цветка для каждого сада так, чтобы для любых двух садов, соединенных путем, они имели разные типы цветов. Верните любой такой выбор в виде массива answer, где answer[i] - тип цветка, посаженного в (i+1)-м саду. Типы цветов обозначаются 1, 2, 3 или 4. Ответ гарантированно существует. Пример:

Input: n = 3, paths = [[1,2],[2,3],[3,1]]
Output: [1,2,3]

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

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

public class Solution {
    public int[] gardenNoAdj(int n, int[][] paths) {
        List<Integer>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] path : paths) {
            graph[path[0] - 1].add(path[1] - 1);
            graph[path[1] - 1].add(path[0] - 1);
        }
        
        int[] answer = new int[n];
        for (int garden = 0; garden < n; garden++) {
            boolean[] used = new boolean[5];
            for (int neighbor : graph[garden]) {
                used[answer[neighbor]] = true;
            }
            for (int flower = 1; flower <= 4; flower++) {
                if (!used[flower]) {
                    answer[garden] = flower;
                    break;
                }
            }
        }
        
        return answer;
    }
}

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

Автомобили Б/У в автосалоне на любой кошелек. Выгодно! Пониженная ставка на автокредит при покупке подержанного автомобиля! Выбирайте машину на сайте среди 3200 марок и покупайте со скидкой до 125 000₽. 🚗 Скидки и подарки — 2-й комплект шин в подарок! Сервисное ТО. Индивидуальные условия кредитования. Доступные цены на Б/У автомобили. — Быстрое оформление кредита — Первоначальный взнос от 12% — Длительный срок кредитования — Высокая вероятность одобрения — Нужны только паспорт и права На все авто действует гарантия 12 месяцев. Успевайте купить! ⚡ Посмотреть каталог Изучите все условия кредита (займа) на сайте в соответствующем разделе. Оценивайте свои финансовые возможности и риски. Финансовые услуги оказывает: АО АЛЬФА-БАНК, ПАО Банк ВТБ, ПАО "Совкомбанк". #реклама omsk.autohouse24.ru О рекламодателе

Задача: 247. Strobogrammatic Number II Сложность: medium Дано целое число n, верните все стробограмматические числа длины n. Ответ можно возвращать в любом порядке. Стробограмматическое число — это число, которое выглядит одинаково при повороте на 180 градусов (если посмотреть вверх ногами). Пример:

Input: n = 2
Output: ["11","69","88","96"]

👨‍💻 Алгоритм: 1⃣Инициализируйте структуру данных reversiblePairs, которая содержит все пары обратимых цифр. Вызовите и верните результат рекурсивной функции generateStroboNumbers(n, finalLength), где первый аргумент указывает, что текущий вызов создаст все стробограмматические числа длиной n, а второй аргумент указывает длину конечных стробограмматических чисел, которые мы будем генерировать, и будет использоваться для проверки возможности добавления '0' в начало и конец числа. 2⃣Создайте функцию generateStroboNumbers(n, finalLength), которая вернет все стробограмматические числа длиной n: Проверьте базовые случаи: если n == 0, верните массив с пустой строкой [""]; если n == 1, верните ["0", "1", "8"]. Вызовите generateStroboNumbers(n - 2, finalLength), чтобы получить все стробограмматические числа длиной (n-2), и сохраните их в subAns. Инициализируйте пустой массив currStroboNums для хранения стробограмматических чисел длиной n. 3⃣Для каждого числа в subAns добавьте все reversiblePairs в начало и конец, за исключением случая, когда текущая пара '00' и n == finalLength (потому что нельзя добавить '0' в начало числа), и добавьте это новое число в currStroboNums. В конце функции верните все стробограмматические числа, т.е. currStroboNums. 😎 Решение:

import java.util.*;

class Solution {
    List<List<Character>> reversiblePairs = Arrays.asList(
        Arrays.asList('0', '0'), Arrays.asList('1', '1'), 
        Arrays.asList('6', '9'), Arrays.asList('8', '8'), Arrays.asList('9', '6')
    );
    
    public List<String> generateStroboNumbers(int n, int finalLength) {
        if (n == 0) {
            return Arrays.asList("");
        }
        
        if (n == 1) {
            return Arrays.asList("0", "1", "8");
        }
        
        List<String> prevStroboNums = generateStroboNumbers(n - 2, finalLength);
        List<String> currStroboNums = new ArrayList<>();
        
        for (String prevStroboNum : prevStroboNums) {
            for (List<Character> pair : reversiblePairs) {
                if (pair.get(0) != '0' || n != finalLength) {
                    currStroboNums.add(pair.get(0) + prevStroboNum + pair.get(1));
                }
            }
        }
        
        return currStroboNums;
    }
    
    public List<String> findStrobogrammatic(int n) {
        return generateStroboNumbers(n, n);
    }
}

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

Дарим подписку на Яндекс Музыку Ответьте на 1 вопрос и Яндекс Музыка ваша для вас и 3-х ваших близких. Кинопоиск и Яндекс Книги тоже в подписке. Попробуйте бесплатно❤️ Попробовать #реклама 18+ music.yandex.ru О рекламодателе Реклама на Яндексе

Задача: 433. Minimum Genetic Mutation Сложность: medium Генетическая строка может быть представлена строкой длиной 8 символов, содержащей символы 'A', 'C', 'G' и 'T'. Предположим, нам нужно исследовать мутацию от генетической строки startGene до генетической строки endGene, где одна мутация определяется как изменение одного символа в генетической строке. Например, "AACCGGTT" --> "AACCGGTA" является одной мутацией. Также существует генетический банк bank, который содержит все допустимые генетические мутации. Генетическая строка должна быть в банке, чтобы считаться допустимой. Даны две генетические строки startGene и endGene и генетический банк bank, верните минимальное количество мутаций, необходимых для мутации от startGene до endGene. Если такой мутации не существует, верните -1. Обратите внимание, что начальная строка считается допустимой, поэтому она может не быть включена в банк. Пример:

Input: startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]
Output: 1

👨‍💻 Алгоритм: 1⃣Инициализируйте очередь и множество seen. Очередь будет использоваться для выполнения BFS, а множество seen будет использоваться для предотвращения повторного посещения одного и того же узла. Изначально в очередь и множество должен быть помещен startGene. 2⃣Выполняйте BFS. На каждом узле, если node == endGene, верните количество шагов, пройденных до этого момента. В противном случае, итеративно заменяйте каждый символ в строке на один из "A", "C", "G", "T" для нахождения соседей. Для каждого соседа, если он еще не был посещен и находится в bank, добавьте его в очередь и в множество seen. 3⃣Если BFS завершился и endGene не был найден, задача невыполнима. Верните -1. 😎 Решение:

class Solution {
    public int minMutation(String start, String end, String[] bank) {
        Queue<String> queue = new LinkedList<>();
        Set<String> seen = new HashSet<>();
        queue.add(start);
        seen.add(start);
        
        int steps = 0;
        
        while (!queue.isEmpty()) {
            int nodesInQueue = queue.size();
            for (int j = 0; j < nodesInQueue; j++) {
                String node = queue.remove();
                if (node.equals(end)) {
                    return steps;
                }

                for (char c: new char[] {'A', 'C', 'G', 'T'}) {
                    for (int i = 0; i < node.length(); i++) {
                        String neighbor = node.substring(0, i) + c + node.substring(i + 1);
                        if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {
                            queue.add(neighbor);
                            seen.add(neighbor);
                        }
                    }
                }
            }
            
            steps++;
        }
        
        return -1;
    }
}

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

Онлайн-магистратура с IT специальностями от Яндекса Совместно с ИТМО, МИФИ, МФТИ. Онлайн-магистратура с актуальными программами и гибким графиком обучения. Получите высокооплачиваемую IT профессию, официальный диплом и практические знания. Господдержка оплаты. Совмещение с работой! Подать заявку #реклама 16+ practicum.yandex.ru О рекламодателе

Задача: 1394. Find Lucky Integer in an Array Сложность: easy Дан массив целых чисел arr. Счастливое число — это число, частота которого в массиве равна его значению. Верните наибольшее счастливое число в массиве. Если счастливого числа нет, верните -1. Пример:

Input: arr = [1,2,2,3,3,3]
Output: 3
Explanation: 1, 2 and 3 are all lucky numbers, return the largest of them.

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

public int findLucky(int[] arr) {
        
    Map<Integer, Integer> counts = new HashMap<>();
    for (Integer num : arr) {
        counts.put(num, counts.getOrDefault(num, 0) + 1);
    }
    
    int largestLuckyNumber = -1;
    for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
        if (entry.getKey().equals(entry.getValue())) {
            largestLuckyNumber = Math.max(largestLuckyNumber, entry.getKey());
        }
    }
    
    return largestLuckyNumber;
}

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

Задача: 588. Design In-Memory File System Сложность: medium Спроектируйте структуру данных, которая симулирует файловую систему в памяти. Реализуйте класс FileSystem: FileSystem() Инициализирует объект системы. List<String> ls(String path) Если path является путем к файлу, возвращает список, содержащий только имя этого файла. Если path является путем к директории, возвращает список имен файлов и директорий в этой директории. Ответ должен быть в лексикографическом порядке. void mkdir(String path) Создает новую директорию согласно заданному пути. Заданная директория не существует. Если промежуточные директории в пути не существуют, вы также должны создать их. void addContentToFile(String filePath, String content) Если filePath не существует, создает файл, содержащий заданный контент. Если filePath уже существует, добавляет заданный контент к исходному содержимому. String readContentFromFile(String filePath) Возвращает содержимое файла по пути filePath. Пример:

Input
["FileSystem", "ls", "mkdir", "addContentToFile", "ls", "readContentFromFile"]
[[], ["/"], ["/a/b/c"], ["/a/b/c/d", "hello"], ["/"], ["/a/b/c/d"]]
Output
[null, [], null, null, ["a"], "hello"]

Explanation
FileSystem fileSystem = new FileSystem();
fileSystem.ls("/");                         // return []
fileSystem.mkdir("/a/b/c");
fileSystem.addContentToFile("/a/b/c/d", "hello");
fileSystem.ls("/");                         // return ["a"]
fileSystem.readContentFromFile("/a/b/c/d"); // return "hello"

👨‍💻 Алгоритм: 1⃣ Инициализация файловой системы: Создайте класс FileSystem, который будет содержать вложенный класс File. Класс File будет представлять либо файл, либо директорию, содержать флаг isfile, словарь files и строку content. 2⃣ Обработка команд: Реализуйте метод ls, который возвращает список файлов и директорий в указанном пути, либо имя файла, если указанный путь является файлом. Реализуйте метод mkdir, который создаёт директории по указанному пути. Если промежуточные директории не существуют, создайте их. Реализуйте метод addContentToFile, который добавляет содержимое в файл по указанному пути. Если файл не существует, создайте его. Реализуйте метод readContentFromFile, который возвращает содержимое файла по указанному пути. 3⃣ Обработка путей и работа с файлами/директориями: Используйте метод split для разделения пути на составляющие и навигации по дереву директорий и файлов. Для каждой команды выполняйте соответствующие операции по созданию, чтению или записи содержимого файлов и директорий. 😎 Решение:

public class FileSystem {
    class File {
        boolean isFile = false;
        HashMap<String, File> files = new HashMap<>();
        String content = "";
    }
    
    File root = new File();

    public List<String> ls(String path) {
        File t = navigate(path);
        if (t.isFile) return Arrays.asList(path.substring(path.lastIndexOf("/") + 1));
        List<String> res = new ArrayList<>(t.files.keySet());
        Collections.sort(res);
        return res;
    }

    public void mkdir(String path) {
        navigate(path);
    }

    public void addContentToFile(String filePath, String content) {
        File t = navigate(filePath);
        t.isFile = true;
        t.content += content;
    }

    public String readContentFromFile(String filePath) {
        return navigate(filePath).content;
    }

    private File navigate(String path) {
        File t = root;
        if (!path.equals("/")) {
            for (String dir : path.split("/")) {
                if (!dir.isEmpty()) {
                    t.files.putIfAbsent(dir, new File());
                    t = t.files.get(dir);
                }
            }
        }
        return t;
    }
}

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

Задача: 87. Scramble String Сложность: hard Мы можем перемешать строку s, чтобы получить строку t, используя следующий алгоритм: 1. Если длина строки равна 1, остановиться. 2. Если длина строки больше 1, выполнить следующее: - Разделить строку на две непустые подстроки в случайном индексе, например, если строка это s, разделить её на x и y, где s = x + y. - Случайным образом решить, поменять ли местами две подстроки или оставить их в том же порядке. То есть после этого шага s может стать s = x + y или s = y + x. - Применить шаг 1 рекурсивно к каждой из двух подстрок x и y. Для двух строк s1 и s2 одинаковой длины вернуть true, если s2 является перемешанной строкой s1, в противном случае вернуть false. Пример:

Input: s1 = "great", s2 = "rgeat"
Output: true
Explanation: One possible scenario applied on s1 is:
"great" --> "gr/eat" // divide at random index.
"gr/eat" --> "gr/eat" // random decision is not to swap the two substrings and keep them in order.
"gr/eat" --> "g/r / e/at" // apply the same algorithm recursively on both substrings. divide at random index each of them.
"g/r / e/at" --> "r/g / e/at" // random decision was to swap the first substring and to keep the second substring in the same order.
"r/g / e/at" --> "r/g / e/ a/t" // again apply the algorithm recursively, divide "at" to "a/t".
"r/g / e/ a/t" --> "r/g / e/ a/t" // random decision is to keep both substrings in the same order.
The algorithm stops now, and the result string is "rgeat" which is s2.
As one possible scenario led s1 to be scrambled to s2, we return true.

👨‍💻 Алгоритм: 1⃣Итерируйте i от 0 до n-1. - Итерируйте j от 0 до n-1. - Установите dp[1][i][j] в булево значение s1[i] == s2[j]. (Базовый случай динамического программирования). 2⃣Итерируйте length от 2 до n. - Итерируйте i от 0 до n + 1 - length. - Итерируйте j от 0 до n + 1 - length. 3⃣Итерируйте newLength от 1 до length - 1. - Если dp[newLength][i][j] && dp[length-newLength][i+newLength][j+newLength]) || (dp[newLength][i][j+length-newLength] && dp[length-newLength][i+newLength][j]) верно, установите dp[length][i][j] в true. - Верните dp[n][0][0]. 😎 Решение:

class Solution {
    public boolean isScramble(String s1, String s2) {
        int n = s1.length();
        boolean dp[][][] = new boolean[n + 1][n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[1][i][j] = s1.charAt(i) == s2.charAt(j);
            }
        }
        for (int length = 2; length <= n; length++) {
            for (int i = 0; i < n + 1 - length; i++) {
                for (int j = 0; j < n + 1 - length; j++) {
                    for (int newLength = 1; newLength < length; newLength++) {
                        boolean dp1[] = dp[newLength][i];
                        boolean dp2[] = dp[length - newLength][i + newLength];
                        dp[length][i][j] |= dp1[j] && dp2[j + newLength];
                        dp[length][i][j] |=
                        dp1[j + length - newLength] && dp2[j];
                    }
                }
            }
        }
        return dp[n][0][0];
    }
}

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

Задача: 1219. Path with Maximum Gold Сложность: medium В золотом руднике размером m x n каждая ячейка содержит целое число, представляющее количество золота в этой ячейке, или 0, если она пуста. Верните максимальное количество золота, которое вы можете собрать при следующих условиях: - Каждый раз, когда вы находитесь в ячейке, вы собираете всё золото из этой ячейки. - Из вашей позиции вы можете сделать один шаг влево, вправо, вверх или вниз. - Вы не можете посещать одну и ту же ячейку более одного раза. - Никогда не посещайте ячейку с 0 золотом. - Вы можете начинать и прекращать сбор золота с любой позиции в сетке, которая содержит золото. Пример:

Input: grid = [[0,6,0],[5,8,7],[0,9,0]]
Output: 24
Explanation:
[[0,6,0],
 [5,8,7],
 [0,9,0]]
Path to get the maximum gold, 9 -> 8 -> 7.

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

class Solution {
    private final int[] DIRECTIONS = new int[] { 0, 1, 0, -1, 0 };

    public int getMaximumGold(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        int maxGold = 0;

        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                maxGold = Math.max(maxGold, dfsBacktrack(grid, rows, cols, row, col));
            }
        }
        return maxGold;
    }

    private int dfsBacktrack(int[][] grid, int rows, int cols, int row, int col) {
        if (row < 0 || col < 0 || row == rows

19. Path with Maxim

grid[row][col] == 0) {
            return 0;
        }
        int maxGold = 0;

        int originalVal = grid[row][col];
        grid[row][col] = 0;

        for (int direction = 0; direction < 4; direction++) {
            maxGold = Math.max(maxGold,
                    dfsBacktrack(grid, rows, cols, DIRECTIONS[direction] + row,
                            DIRECTIONS[direction + 1] + col));
        }

        grid[row][col] = originalVal;
        return maxGold + originalVal;
    }
}

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

💰Олимпиада по программированию с призовым фондом 50 000 рублей! 🏃💨Для школьников от 10 до 16 лет, задачи можно решать на языках GO, Python, JavaScript, C++ 🏆Решить олимпиаду можно 23 июля (среда) с 11:00 до 19:00 🗣Регистрация закроется 20 июля в 23:55 1️⃣ место - 25 000 рублей 2️⃣ место - 15 000 рублей 3️⃣ место - 10 000 рублей 😎Регистрируйся по ссылке, участие бесплатное Олимпиада ZamaCode

Задача: 567. Permutation in String Сложность: medium Даны две строки s1 и s2. Верните true, если s2 содержит перестановку s1, или false в противном случае. Другими словами, верните true, если одна из перестановок s1 является подстрокой s2. Пример:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

👨‍💻 Алгоритм: 1⃣Создать массив для подсчета символов в строке s1. Затем создать аналогичный массив для первых len(s1) символов строки s2. 2⃣Использовать скользящее окно для перемещения по строке s2. Для каждой позиции окна обновлять массив подсчета символов и сравнивать его с массивом для строки s1. 3⃣Если массивы совпадают на любом этапе, вернуть true. Если окно достигает конца строки s2 и совпадений не найдено, вернуть false. 😎 Решение:

public class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int s1Len = s1.length(), s2Len = s2.length();
        if (s1Len > s2Len) return false;

        int[] s1Count = new int[26];
        int[] s2Count = new int[26];
        
        for (int i = 0; i < s1Len; i++) {
            s1Count[s1.charAt(i) - 'a']++;
            s2Count[s2.charAt(i) - 'a']++;
        }
        
        for (int i = 0; i < s2Len - s1Len; i++) {
            if (Arrays.equals(s1Count, s2Count)) return true;
            s2Count[s2.charAt(i) - 'a']--;
            s2Count[s2.charAt(i + s1Len) - 'a']++;
        }
        
        return Arrays.equals(s1Count, s2Count);
    }
}

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

Гайд по эффективным онлайн-встречам для отделов закупок Как специалистам по закупкам и тендерам экономить время на онлайн-совещаниях, сократить время на подготовку ТЗ и ускорить цикл закупок? Гайд МТС Линк — чек-листы, кейсы и подходы для упрощения коммуникации закупщиков с внутренними заказчиками и подрядчиками с помощью онлайн-встреч. ✅ В гайде: - Как создать постоянную ссылку на синки с коллегами или поставщиками и подключаться в 2 клика; - Как ускорить сбор требований без долгих переписок и конфликтов с юр.отделом; - Как обсуждать ТЗ и сразу фиксировать договоренности с помощью ИИ; - Как вести переговоры с подрядчиками и оперативно согласовать ключевые этапы сделки; - Как отслеживать выполнение условий контракта. Бонус внутри: 5 способов не выгореть от бесконечных синков. ✨ Скачайте гайд бесплатно по ссылке Скачать #реклама 16+ mts-link.ru О рекламодателе

Задача: 206. Reverse Linked List Сложность: easy Дан односвязный список, разверните этот список и верните развернутый список. Пример:

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

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

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

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

Задача: 1025. Divisor Game Сложность: easy Алиса и Боб играют в игру по очереди, причем Алиса начинает первой. Изначально на доске мелом написано число n. В свой ход каждый игрок делает ход, состоящий из: выбора любого x при 0 < x < n и n % x == 0. Замены числа n на доске на n - x. Также, если игрок не может сделать ход, он проигрывает игру. Возвращается true тогда и только тогда, когда Алиса выигрывает игру, предполагая, что оба игрока играют оптимально. Пример:

Input: n = 2
Output: true

👨‍💻 Алгоритм: 1⃣Определение выигрыша: Заметим, что если число n четное, Алиса всегда выигрывает, потому что она может уменьшить n на 1, и оставить Боба с нечетным числом. Если число n нечетное, Алиса всегда проигрывает, потому что Боб может уменьшить n на 1, и оставить Алису с четным числом. 2⃣Проверка четности числа: Проверяем, четное ли число n. Если n четное, возвращаем true, если нечетное, возвращаем false. 3⃣Возврат результата: Возвращаем результат в зависимости от четности числа n. 😎 Решение:

public class Solution {
    public boolean divisorGame(int n) {
        return n % 2 == 0;
    }
}

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