Java | LeetCode

Задача: 245. Shortest Word Distance II Сложность: medium Дан массив строк wordsDict и две строки word1 и word2, которые уже существуют в массиве. Верните наименьшее расстояние между вхождениями этих двух слов в списке. Обратите внимание, что word1 и word2 могут быть одинаковыми. Гарантируется, что они представляют собой два отдельных слова в списке. Пример:

    
        Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"
Output: 1{}
    

👨‍💻 Алгоритм: 1⃣Переберите список wordsDict и сохраните индексы слова word1 в список indices1 и индексы слова word2 в список indices2. Инициализируйте переменную shortestDistance = INT_MAX. 2⃣Переберите индексы в списке indices1 и для каждого индекса найдите верхнюю границу в списке indices2, используя бинарный поиск, и сохраните этот индекс в переменную x. Рассмотрите индексы indices2[x] и indices2[x - 1], обновляя shortestDistance, если индексы не совпадают. 3⃣Верните значение переменной shortestDistance. 😎 Решение:

    
        import java.util.*;

class Solution {
    public int shortestWordDistance(String[] wordsDict, String word1, String word2) {
        List<Integer> indices1 = new ArrayList<>();
        List<Integer> indices2 = new ArrayList<>();
        for (int i = 0; i < wordsDict.length; i++) {
            if (wordsDict[i].equals(word1)) {
                indices1.add(i);
            }
            if (wordsDict[i].equals(word2)) {
                indices2.add(i);
            }
        }

        int shortestDistance = Integer.MAX_VALUE;
        for (int index : indices1) {
            int x = Collections.binarySearch(indices2, index);
            if (x < 0) {
                x = -x - 1;
            }
            if (x < indices2.size()) {
                shortestDistance = Math.min(shortestDistance, indices2.get(x) - index);
            }
            if (x > 0 && !indices2.get(x - 1).equals(index)) {
                shortestDistance = Math.min(shortestDistance, index - indices2.get(x - 1));
            }
        }
        return shortestDistance;
    }
}{}
    

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

Магистратура — это 2 года жизни и серьезные вложения Как не ошибиться с выбором? Приходите на день открытых дверей ИТ-магистратуры Центрального университета — разберем все важные вопросы, которые помогут принять правильное решение. О чем будем говорить: -Как создаются программы магистратуры в ЦУ, что такое продуктовый подход в высшем образовании и как это делает выпускников реально востребованными на рынке -Как университет помогает студентам строить карьеру: от менторства до трудоустройства в топовые компании -Какие направления есть в ЦУ и как выбрать то, что приведет к вашим карьерным целям -Реальные истории студентов: как они поступали, учились и куда пошли работать Спикеры — практики с опытом в Google, Яндексе, Т-Банке и Visa, которые сейчас отвечают за образовательный опыт студентов ЦУ. Зарегистрироваться #реклама 16+ r.bothelp.io О рекламодателе

Задача: 372. Super Pow Сложность: medium Ваша задача — вычислить а^b mod 1337, где a - положительное число, а b - чрезвычайно большое положительное целое число, заданное в виде массива. Пример:

    
        Input: a = 2, b = [3]
Output: 8{}
    

👨‍💻 Алгоритм: 1⃣Разделите задачу на более мелкие задачи: вычислите a^b mod 1337, используя свойства модульной арифметики и степенной функции. Разделите большой показатель b на меньшие части, чтобы обрабатывать их по очереди. 2⃣Используйте метод быстрого возведения в степень (pow) для эффективного вычисления больших степеней с модулем 1337. 3⃣Объедините результаты для каждой части показателя b, используя свойства модульной арифметики: (a^b) % 1337 = ((a^(b1)) % 1337 * (a^(b2)) % 1337 * ...) % 1337. 😎 Решение:

    
        public class Solution {
    public int getSum(int a, int b) {
        int x = Math.abs(a), y = Math.abs(b);
        if (x < y) return getSum(b, a);
        int sign = a > 0 ? 1 : -1;

        if (a * b >= 0) {
            while (y != 0) {
                int carry = (x & y) << 1;
                x ^= y;
                y = carry;
            }
        } else {
            while (y != 0) {
                int borrow = ((~x) & y) << 1;
                x ^= y;
                y = borrow;
            }
        }
        return x * sign;
    }
}{}
    

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

Реклама для бизнеса любого уровня в Яндекс Директе Создайте эффективную рекламную кампанию с алгоритмами Яндекс Директа 👌 Начните прямо сейчас ⚡ Зарегистрироваться #реклама direct.yandex.ru О рекламодателе

#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;
    }
}{}
    

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

Битрикс24 показал, каким будет будущее бизнеса Автоматизация с ИИ, больше эмоций, высокая скорость коммуникаций. ✨Теперь задачи можно ставить голосовым сообщением или записывать кружком, ИИ сам все оформит и назначит исполнителя. 😊В чатах – 40+ реакций, стикеры и даже распознавание эмоций в расшифровке голосовых. У каждого появится свой ИИ-агент, который может выполнять сложные поручения даже с внешними сервисами вроде 1С или почты. 📱В CRM нейросеть сама заполняет сделки, отсекает пустые звонки и ищет клиентов для повторных продаж. А BitrixGPT теперь можно тегнуть прямо в чате – подведет итоги и найдет нужное за секунду. Большинство новинок уже можно протестировать в Битрикс24 Зарегистрироваться #реклама 16+ space-release.bitrix24.ru О рекламодателе

Задача: 1256. Encode Number Сложность: medium Даны список слов, список отдельных букв (могут повторяться) и оценка каждого символа. Верните максимальную оценку любого правильного набора слов, образованного с помощью заданных букв (words[i] не может быть использовано два или более раз). Не обязательно использовать все символы в буквах, каждая буква может быть использована только один раз. Оценка букв 'a', 'b', 'c', ... , 'z' задаются значениями score[0], score[1], ... , score[25] соответственно. Пример:

    
        Input: num = 23
Output: "1000"{}
    

👨‍💻 Алгоритм: 1⃣На основе предоставленной таблицы можно выявить закономерность для преобразования целого числа n в строку f(n) 2⃣Из таблицы видно, что последовательность строк соответствует последовательности чисел в двоичной системе счисления за исключением начального значения n = 0. 3⃣Таким образом, можно вывести, что: Для каждого значения n > 0, функция f(n) представляет собой двоичное представление числа (n - 1). 😎 Решение:

    
        public class Solution {
    public String encode(int num) {
        if (num == 0) return "";
        return Integer.toBinaryString(num - 1);
    }
}{}
    

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

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

Задача: 938. Range Sum of BST Сложность: easy Учитывая корневой узел двоичного дерева поиска и два целых числа low и high, верните сумму значений всех узлов со значением в диапазоне [low, high]. Пример:

    
        Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32{}
    

👨‍💻 Алгоритм: 1⃣Если дерево пустое, вернуть 0. 2⃣Если значение текущего узла меньше low, рекурсивно искать в правом поддереве. Если значение текущего узла больше high, рекурсивно искать в левом поддереве. 3⃣Если значение текущего узла в диапазоне [low, high], включить значение узла в сумму и рекурсивно искать в обоих поддеревьях. 😎 Решение:

    
        public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        if (root == null) return 0;
        if (root.val < low) return rangeSumBST(root.right, low, high);
        if (root.val > high) return rangeSumBST(root.left, low, high);
        return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);
    }
}{}
    

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

Продвижение в Telegram с помощью Яндекс Директа ⚡Запустите продвижение в телеграм-каналах и привлекайте целевую аудиторию 📱 Таргетинг по тематикам, регионам и каналам в Telegram Попробовать #реклама yandex.ru О рекламодателе