Java | LeetCode

Задача: 1155. Number of Dice Rolls With Target Sum Сложность: medium У вас есть n кубиков, и на каждом кубике k граней, пронумерованных от 1 до k. Даны три целых числа n, k и target. Необходимо вернуть количество возможных способов (из общего количества kn способов) выбросить кубики так, чтобы сумма выпавших чисел равнялась target. Так как ответ может быть слишком большим, верните его по модулю 10^9 + 7. Пример:

Input: n = 1, k = 6, target = 3
Output: 1
Explanation: You throw one die with 6 faces.
There is only one way to get a sum of 3.

👨‍💻 Алгоритм: 1⃣Начните с: Индекс кубика diceIndex равен 0; это индекс кубика, который мы рассматриваем в данный момент. Сумма чисел на предыдущих кубиках currSum равна 0. Инициализируйте переменную ways значением 0. Итерируйтесь по значениям от 1 до k для каждого значения i. Если текущий кубик может иметь значение i, т.е. currSum после добавления i не превысит значение target, то обновите значение currSum и рекурсивно перейдите к следующему кубику. Добавьте значение, возвращенное этим рекурсивным вызовом, к ways. Иначе, если это значение невозможно, то выйдите из цикла, так как большие значения также не удовлетворят вышеуказанному условию. 2⃣Базовые случаи: Если мы перебрали все кубики, т.е. diceIndex = n, то проверьте, равна ли currSum значению target. 3⃣Верните значение ways и также сохраните его в таблице мемоизации memo, соответствующей текущему состоянию, определяемому diceIndex и currSum. 😎 Решение:

class Solution {
    private static final int MOD = 1_000_000_007;

    private int waysToTarget(int[][] memo, int diceIndex, int n, int currSum, int target, int k) {
        if (diceIndex == n) {
            return currSum == target ? 1 : 0;
        }
        if (memo[diceIndex][currSum] != -1) {
            return memo[diceIndex][currSum];
        }

        int ways = 0;
        for (int i = 1; i <= Math.min(k, target - currSum); i++) {
            ways = (ways + waysToTarget(memo, diceIndex + 1, n, currSum + i, target, k)) % MOD;
        }
        return memo[diceIndex][currSum] = ways;
    }

    public int numRollsToTarget(int n, int k, int target) {
        int[][] memo = new int[n + 1][target + 1];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return waysToTarget(memo, 0, n, 0, target, k);
    }
}

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

Задача: 1258. Synonymous Sentences Сложность: medium Вам дан список эквивалентных пар строк synonyms, где synonyms[i] = [si, ti] означает, что si и ti являются эквивалентными строками. Вам также дан текст предложения. Верните все возможные синонимичные предложения, отсортированные лексикографически. Пример:

Input: synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]], text = "I am happy today but was sad yesterday"
Output: ["I am cheerful today but was sad yesterday","I am cheerful today but was sorrow yesterday","I am happy today but was sad yesterday","I am happy today but was sorrow yesterday","I am joy today but was sad yesterday","I am joy today but was sorrow yesterday"]

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

import java.util.*;

public class Solution {
    public List<String> generateSentences(List<List<String>> synonyms, String text) {
        Map<String, Set<String>> graph = new HashMap<>();
        for (List<String> pair : synonyms) {
            graph.computeIfAbsent(pair.get(0), k -> new HashSet<>()).add(pair.get(1));
            graph.computeIfAbsent(pair.get(1), k -> new HashSet<>()).add(pair.get(0));
        }

        List<String> words = Arrays.asList(text.split(" "));
        List<List<String>> synonymGroups = new ArrayList<>();
        for (String word : words) {
            synonymGroups.add(new ArrayList<>(findSynonyms(graph, word)));
        }

        List<String> sentences = new ArrayList<>();
        generate(sentences, synonymGroups, new StringBuilder(), 0);
        Collections.sort(sentences);
        return sentences;
    }

    private Set<String> findSynonyms(Map<String, Set<String>> graph, String word) {
        Set<String> synonyms = new HashSet<>();
        Stack<String> stack = new Stack<>();
        stack.push(word);
        while (!stack.isEmpty()) {
            String w = stack.pop();
            if (synonyms.add(w)) {
                stack.addAll(graph.getOrDefault(w, Collections.emptySet()));
            }
        }
        return synonyms;
    }

    private void generate(List<String> sentences, List<List<String>> groups, StringBuilder sentence, int index) {
        if (index == groups.size()) {
            sentences.add(sentence.toString().trim());
            return;
        }
        int len = sentence.length();
        for (String word : groups.get(index)) {
            sentence.append(" ").append(word);
            generate(sentences, groups, sentence, index + 1);
            sentence.setLength(len);
        }
    }
}

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

От чего зависит эффективность автотестов? От их правильного написания и поддерживаемости! В QA GURU учат приручать Java, чтобы ваши автотесты работали, как часы. Вот несколько лайфхаков, о которых мы расскажем на вводном занятии уже сегодня (20:00 Мск): 1. Используйте понятные и описательные названия тестов Названия тестов должны четко отражать их цель. Это упрощает понимание кода всеми членами команды. Например: // Хорошо

public void verifyLoginWithValidCredentials() { ... }

// Плохо

public void test1() { ... }

Описательные названия помогают быстро понять, что проверяет тест, без необходимости изучения его внутренней логики. 2. Применяйте Page Object Model (POM) Page Object Model позволяет отделить логику теста от структуры веб-страницы, что делает код более модульным и удобным для поддержки при изменениях интерфейса. Пример использования: // Класс

Page Object
public class LoginPage {
    private By usernameField = By. id("username");
    private By passwordField = By. id("password");
    private By loginButton = By. id("loginBtn");

    public void enterUsername(String username) {
        driver.findElement(usernameField).sendKeys(username);
    }

    public void enterPassword(String password) {
        driver.findElement(passwordField).sendKeys(password);
    }

    public void clickLoginButton() {
        driver.findElement(loginButton).click();
    }
}

// Тестовый сценарий

LoginPage loginPage = new LoginPage(driver);
loginPage.enterUsername("john.doe");
loginPage.enterPassword("password123");
loginPage.clickLoginButton();

POM способствует повторному использованию кода и улучшает читаемость тестов. 3. Используйте параметризацию и data-driven подход Параметризованные тесты позволяют запускать один и тот же сценарий с различными входными данными, что увеличивает охват тестирования без дублирования кода.

@ ParameterizedTest
@ CsvSource({"john.doe, password123", "jane.smith, test@123"})
public void verifyLogin(String username, String password) {
    LoginPage loginPage = new LoginPage(driver);
    loginPage.enterUsername(username);
    loginPage.enterPassword(password);
    loginPage.clickLoginButton();
}

Этот подход делает тесты более гибкими и масштабируемыми. 4. Следуйте принципу AAA (Arrange, Act, Assert) Структурируйте тесты в три этапа: Arrange: подготовка данных и окружения. Act: выполнение действия. Assert: проверка результата. Пример:

@ Test
public void testAddition() {
    // Arrange
    Calculator calculator = new Calculator();

    // Act
    int result = calculator.add(2, 3);

    // Assert
    assertEquals(5, result);
}

Этот подход делает тесты более организованными и легко читаемыми. 5. Логирование и отчетность Добавляйте логирование в тесты для диагностики проблем:

log. info("Entering username: " + username);
log. info("Clicking on the login button");

Интеграция инструментов отчетности (например, Allure) помогает визуализировать результаты тестов и быстро выявлять ошибки. 6. Регулярные ревью кода Проводите регулярные ревью автотестов для повышения качества кода. Это помогает выявить потенциальные проблемы, улучшить читаемость и обеспечить соблюдение стандартов кодирования. 7. Автоматизация и CI/CD Используйте инструменты автоматизации (Maven, Gradle) для запуска тестов в рамках CI/CD пайплайнов. Это ускоряет процесс разработки и обеспечивает стабильность приложения на всех этапах. Хотите узнать больше? Присоединяйтесь уже сегодня (20:00 Мск) к бесплатному открытому уроку! 🔗 Зарегистрируйтесь на первый открытый урок по ссылке!

Узнать все о поступлении в магистратуру Вышки за 1 час? Это реально сделать 13 апреля! Рассказываем подробнее 👌 На вебинаре Приемная комиссия НИУ ВШЭ поделится необходимой информацией для поступления: когда подавать документы и сдавать вступительные испытания, как получить скидку на обучение, сколько выделено бюджетных мест, что такое целевое обучение и многое другое. Вы также сможете задать любые вопросы. ✨ Магистратура Вышки – это площадка для реализации ваших идей: более 190 программ по 39 направлениям подготовки от искусственного интеллекта и креативных индустрий до математики, экономики и информационной безопасности. Выбирайте подходящую программу и присоединяйтесь к вебинару! Запоминайте: 13 апреля в 12:00 мск. Обязательно зарегистрируйтесь, чтобы не пропустить такой шанс 🎓 Узнать больше #реклама 16+ master.hse.ru О рекламодателе

Задача: 1424. Diagonal Traverse II Сложность: medium Дан двумерный целочисленный массив nums, верните все элементы nums в диагональном порядке. Пример:

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

👨‍💻 Алгоритм: 1⃣Инициализируйте очередь с (0, 0) и список ответов ans. 2⃣Пока очередь не пуста: Извлеките (row, col) из очереди. Добавьте nums[row][col] в ans. Если col == 0 и row + 1 в пределах массива, добавьте (row + 1, col) в очередь. Если col + 1 в пределах текущей строки, добавьте (row, col + 1) в очередь. 3⃣Верните ans. 😎 Решение:

class Solution {
    public int[] findDiagonalOrder(List<List<Integer>> nums) {
        Queue<Pair<Integer, Integer>> queue = new LinkedList();
        queue.offer(new Pair(0, 0));
        List<Integer> ans = new ArrayList();
        
        while (!queue.isEmpty()) {
            Pair<Integer, Integer> p = queue.poll();
            int row = p.getKey();
            int col = p.getValue();
            ans.add(nums.get(row).get(col));
            
            if (col == 0 && row + 1 < nums.size()) {
                queue.offer(new Pair(row + 1, col));
            }
            
            if (col + 1 < nums.get(row).size()) {
                queue.offer(new Pair(row, col + 1));
            }
        }
        
        int[] result = new int[ans.size()];
        int i = 0;
        for (int num : ans) {
            result[i] = num;
            i++;
        }
        
        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;
    }
}

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

Получи грант на обучение в Центральном университете Получи несгораемый грант до 2 800 000 ₽ на учебу в бакалавриате Центрального университета. Грант покрывает до 100% стоимости обучения. Сумма гранта не уменьшается, а может увеличиться за дополнительные достижения и успехи в учебе. Участвуй в отборе! Для учеников 10-х и 11-х классов, колледжей. Подать заявку #реклама apply.centraluniversity.ru О рекламодателе

Задача: 1208. Get Equal Substrings Within Budget Сложность: medium Вам даны две строки s и t одинаковой длины и целое число maxCost. Вы хотите преобразовать s в t. Изменение i-го символа строки s на i-й символ строки t стоит |s[i] - t[i]| (т.е. абсолютная разница между значениями ASCII символов). Верните максимальную длину подстроки s, которую можно изменить, чтобы она соответствовала соответствующей подстроке t с затратами, не превышающими maxCost. Если нет подстроки из s, которую можно изменить на соответствующую подстроку из t, верните 0. Пример:

Input: s = "abcd", t = "bcdf", maxCost = 3
Output: 3
Explanation: "abc" of s can change to "bcd".
That costs 3, so the maximum length is 3.

👨‍💻 Алгоритм: 1⃣Инициализация переменных: maxLen для хранения максимальной длины подстроки с затратами, не превышающими maxCost. start для хранения начального индекса текущей подстроки. currCost для хранения текущих затрат на преобразование подстроки s в t. 2⃣Итерация по индексам от 0 до N-1: Добавить текущие затраты на преобразование символа s[i] в t[i] к currCost. Удалять элементы с левого конца, уменьшая затраты до тех пор, пока currCost не станет меньше или равным maxCost. Обновить maxLen длиной текущей подстроки. 3⃣Возврат maxLen как результата. 😎 Решение:

class Solution {
    public int equalSubstring(String s, String t, int maxCost) {
        int N = s.length();
        
        int maxLen = 0;
        int start = 0;
        int currCost = 0;
        
        for (int i = 0; i < N; i++) {
            currCost += Math.abs(s.charAt(i) - t.charAt(i));
            
            while (currCost > maxCost) {
                currCost -= Math.abs(s.charAt(start) - t.charAt(start));
                start++;
            }
            
            maxLen = Math.max(maxLen, i - start + 1);
        }
        
        return maxLen;
    }
}

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

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

Задача: 424. Longest Repeating Character Replacement Сложность: medium Вам дана строка s и целое число k. Вы можете выбрать любой символ строки и заменить его на любой другой заглавный английский символ. Вы можете выполнить эту операцию не более k раз. Верните длину самой длинной подстроки, содержащей одну и ту же букву, которую можно получить после выполнения вышеуказанных операций. Пример:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

👨‍💻 Алгоритм: 1⃣Определите диапазон поиска. Минимальная длина подстроки с одинаковыми символами всегда равна 1 (назовем ее min), а максимальная длина подстроки может быть равна длине данной строки (назовем ее max). Ответ будет лежать в диапазоне [min, max] (включительно). 2⃣Инициализируйте две переменные lo и hi для бинарного поиска. lo всегда указывает на длину допустимой строки, а hi - на недопустимую длину. Изначально lo равно 1, а hi равно max+1. 3⃣Выполните бинарный поиск, чтобы найти максимальное значение lo, которое представляет самую длинную допустимую подстроку. В конце lo будет содержать ответ, а hi будет на единицу больше lo. 😎 Решение:

class Solution {
    public int characterReplacement(String s, int k) {
        int lo = 1;
        int hi = s.length() + 1;

        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            if (canMakeValidSubstring(s, mid, k)) {
                lo = mid;
            } else {
                hi = mid;
            }
        }
        return lo;
    }

    private boolean canMakeValidSubstring(String s, int substringLength, int k) {
        int[] freqMap = new int[26];
        int maxFrequency = 0;
        int start = 0;
        for (int end = 0; end < s.length(); end++) {
            freqMap[s.charAt(end) - 'A']++;

            if (end + 1 - start > substringLength) {
                freqMap[s.charAt(start) - 'A']--;
                start++;
            }

            maxFrequency = Math.max(maxFrequency, freqMap[s.charAt(end) - 'A']);
            if (substringLength - maxFrequency <= k) {
                return true;
            }
        }
        return false;
    }
}

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

Онлайн-интенсив для ИТ-специалистов в Открытых школах Т1 Открытые школы — это возможность за месяц прокачать свои навыки и получить оффер в ИТ-холдинг Т1. С тебя — год опыта работы в ИТ, с нас — бесплатный онлайн-интенсив и топовые преподаватели. Что ты получишь? ✅ Уникальный рыночный опыт. Наши проекты ежегодно получают награды на ИТ-конкурсах: Global CIO, Национальной банковской премии и др. ✅ Быстрый рост в ИТ при экспертной поддержке. ✅ Материалы от HR, которые помогут прокачать резюме и подготовиться к интервью в Т1. ✅ Поддержка опытных преподавателей и уникальный карьерный фаст-трек до мидла в Т1 для выпускников интенсива. ✅ Реальный шанс получить оффер в Т1. Подавай заявку до 11 апреля и приходи учиться! Старт ИТ-интенсива уже 14 апреля. Подать заявку #реклама 16+ t1.ru О рекламодателе

Задача: 1101. The Earliest Moment When Everyone Become Friends Сложность: medium В социальной группе есть n человек, пронумерованных от 0 до n - 1. Вам дан массив logs, где logs[i] = [timestampi, xi, yi] указывает, что xi и yi станут друзьями в момент времени timestampi. Дружба является симметричной. Это означает, что если a является другом b, то b является другом a. Также человек a знаком с человеком b, если a является другом b или a является другом кого-то, кто знаком с b. Верните самое раннее время, когда каждый человек стал знаком с каждым другим человеком. Если такого времени не существует, верните -1. Пример:

Input: logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4
Output: 3
Explanation: At timestamp = 3, all the persons (i.e., 0, 1, 2, and 3) become friends.

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

class UnionFind {
    private int[] parent;
    private int[] rank;

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    public boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
            return true;
        }
        return false;
    }
}

class Solution {
    public int earliestAcq(int[][] logs, int n) {
        Arrays.sort(logs, (a, b) -> Integer.compare(a[0], b[0]));
        UnionFind uf = new UnionFind(n);
        int groupCount = n;
        
        for (int[] log : logs) {
            int timestamp = log[0];
            int friendA = log[1];
            int friendB = log[2];
            if (uf.union(friendA, friendB)) {
                groupCount--;
            }
            if (groupCount == 1) {
                return timestamp;
            }
        }
        
        return -1;
    }
}

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

Задача: 346. Moving Average from Data Stream Сложность: easy Дан поток целых чисел и размер окна, вычислите скользящее среднее всех целых чисел в скользящем окне. Реализуйте класс MovingAverage: MovingAverage(int size) Инициализирует объект с размером окна size. double next(int val) Возвращает скользящее среднее последних size значений потока. Пример:

Input
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]
Output
[null, 1.0, 5.5, 4.66667, 6.0]

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

import java.util.ArrayDeque;
import java.util.Queue;

public class MovingAverage {
    private int size;
    private Queue<Integer> queue;
    private int sum;
    
    public MovingAverage(int size) {
        this.size = size;
        this.queue = new ArrayDeque<>();
        this.sum = 0;
    }
    
    public double next(int val) {
        queue.offer(val);
        sum += val;
        if (queue.size() > size) {
            sum -= queue.poll();
        }
        return (double) sum / queue.size();
    }
}

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

Нанимаете аутсорс, подрядчиков, фрилансеров? Попробуйте Битрикс24 Коллабы – платформа для эффективной работы с подрядчиками. Тут обсуждения превращаются в задачи, а видео созвон можно собрать одной кнопкой. Любой проект можно разложить по полочкам с понятным ТЗ и обозначенными сроками. Работайте в Битрикс24 и создавайте Коллабы с подрядчиками. Начать #реклама 16+ collabs.bitrix24.ru О рекламодателе

Задача: 1040. Moving Stones Until Consecutive II Сложность: medium Есть несколько камней, расположенных в разных позициях на оси X. Вам дан целочисленный массив stones - позиции камней. Назовите камень конечным, если он имеет наименьшую или наибольшую позицию. За один ход вы берете конечный камень и перемещаете его в незанятую позицию так, чтобы он перестал быть конечным. В частности, если камни находятся, скажем, в позиции stones = [1,2,5], вы не можете переместить конечный камень в позицию 5, поскольку перемещение его в любую позицию (например, 0 или 3) сохранит этот камень в качестве конечного. Игра заканчивается, когда вы не можете сделать больше ни одного хода (т.е, камни находятся в трех последовательных позициях). Возвращает целочисленный массив answer длины 2, где: answer[0] - минимальное количество ходов, которое вы можете сделать, а answer[1] - максимальное количество ходов, которое вы можете сделать. Пример:

Input: stones = [7,4,9]
Output: [1,2]

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

import java.util.Arrays;

public class Solution {
    public int[] numMovesStonesII(int[] stones) {
        Arrays.sort(stones);
        int n = stones.length;
        
        int maxMoves = stones[n-1] - stones[0] + 1 - n;
        maxMoves -= Math.min(stones[1] - stones[0] - 1, stones[n-1] - stones[n-2] - 1);

        int minMoves = Integer.MAX_VALUE;
        int j = 0;

        for (int i = 0; i < n; ++i) {
            while (j < n && stones[j] - stones[i] + 1 <= n) {
                ++j;
            }
            int alreadyInWindow = j - i;
            if (alreadyInWindow == n - 1 && stones[j-1] - stones[i] + 1 == n - 1) {
                minMoves = Math.min(minMoves, 2);
            } else {
                minMoves = Math.min(minMoves, n - alreadyInWindow);
            }
        }

        return new int[] { minMoves, maxMoves };
    }
}

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

Запустите рекламу в телеграм-каналах с Яндекс Директом Перфоманс-реклама теперь в телеграм-каналах ⚡ Яндекс Директ знает, как привлечь целевую аудиторию 💰👌 Попробовать #реклама yandex.ru О рекламодателе

Задача: 1295. Find Numbers with Even Number of Digits Сложность: easy Дан массив чисел nums. Верните количество чисел в массиве, которые содержат четное количество цифр. Пример:

Input: nums = [12,345,2,6,7896]
Output: 2
Explanation: 
12 contains 2 digits (even number of digits). 
345 contains 3 digits (odd number of digits). 
2 contains 1 digit (odd number of digits). 
6 contains 1 digit (odd number of digits). 
7896 contains 4 digits (even number of digits). 
Therefore only 12 and 7896 contain an even number of digits.

👨‍💻 Алгоритм: 1⃣Определите вспомогательную функцию hasEvenDigits, которая принимает num в качестве входных данных и возвращает true, если количество цифр четное, иначе возвращает false. 2⃣Внутри функции hasEvenDigits. Инициализируйте переменную digitCount значением 0. Пока num не равно нулю: Увеличивайте digitCount на 1. Делите num на 10. Возвращайте digitCount & 1 == 0. 3⃣В функции findNumbers. Инициализируйте переменную evenDigitCount значением 0. Для каждого числа num в массиве nums, проверяйте, возвращает ли hasEvenDigits(num) значение true. Если да, увеличивайте evenDigitCount на 1. Возвращайте evenDigitCount. 😎 Решение:

class Solution {
    private boolean hasEvenDigits(int num) {
        int digitCount = 0;
        while (num > 0) {
            digitCount++;
            num /= 10;
        }
        return (digitCount & 1) == 0;
    }

    public int findNumbers(int[] nums) {
        int evenDigitCount = 0;
        for (int num : nums) {
            if (hasEvenDigits(num)) {
                evenDigitCount++;
            }
        }
        return evenDigitCount;
    }
}

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

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

Задача: 1345. Jump Game IV Сложность: hard Дан массив целых чисел arr, изначально вы находитесь на первом индексе массива. За один шаг вы можете прыгнуть с индекса i на индекс: - i + 1, где: i + 1 < arr.length. - i - 1, где: i - 1 >= 0. - j, где: arr[i] == arr[j] и i != j. Вернуть минимальное количество шагов, чтобы достичь последнего индекса массива. Обратите внимание, что нельзя прыгать за пределы массива в любой момент времени. Пример:

Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
Output: 3
Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.

👨‍💻 Алгоритм: 1⃣Построить граф, где ключи - значения из массива, а значения - списки индексов этих значений. Начать с первого индекса, добавив его в очередь текущего слоя и инициализировать набор посещенных индексов. 2⃣Выполнять BFS: для каждого индекса текущего слоя проверять соседние индексы (i + 1, i - 1 и все j, где arr[i] == arr[j]), добавляя непосещенные индексы в очередь следующего слоя. 3⃣Повторять шаг 2, увеличивая счетчик шагов до достижения последнего индекса или пока не закончится очередь. 😎 Решение:

class Solution {
    public int minJumps(int[] arr) {
        int n = arr.length;
        if (n <= 1) {
            return 0;
        }

        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 0; i < n; i++) {
            graph.computeIfAbsent(arr[i], v -> new LinkedList<>()).add(i);
        }

        List<Integer> curs = new LinkedList<>();
        curs.add(0);
        Set<Integer> visited = new HashSet<>();
        int step = 0;

        while (!curs.isEmpty()) {
            List<Integer> nex = new LinkedList<>();

            for (int node : curs) {
                if (node == n - 1) {
                    return step;
                }

                for (int child : graph.get(arr[node])) {
                    if (!visited.contains(child)) {
                        visited.add(child);
                        nex.add(child);
                    }
                }

                graph.get(arr[node]).clear();

                if (node + 1 < n && !visited.contains(node + 1)) {
                    visited.add(node + 1);
                    nex.add(node + 1);
                }
                if (node - 1 >= 0 && !visited.contains(node - 1)) {
                    visited.add(node - 1);
                    nex.add(node - 1);
                }
            }

            curs = nex;
            step++;
        }

        return -1;
    }
}

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

Почему вы не используете Битрикс24 CRM с AI-помощником? 1- не знал 2- забыл Рассказываем и напоминаем! ✅Битрикс24 CRM с AI помогает увеличивать продажи, работать с постоянными клиентами и сохранять все важные данные. AI-помощник CoPilot внутри сервиса расшифрует телефонные разговоры и автоматически заполнит карточки клиента в CRM. Битрикс24 можно использовать бесплатно для всех команд, независимо от их размера. ⚡Не тратьте время на рутину. Узнать больше #реклама 16+ bitrix24.ru О рекламодателе