Java | LeetCode

Нужны 7 желающих для работы с искусственным интеллектом. Работа из дома. График свободный. Пришло задание — изучили — выполнили — получили свои деньги. Деньги вы получаете в зависимости от сложности задания. Например: За задание могут платить 500-10.000 рублей. 500 рублей — это около 5-30 минут. 10 000 руб. это 5-6 часов. Работа может быть разной: Оживить фото, создать видео, реставрировать старое фото и т.д. 💰 В среднем новичок получает до 150.000 руб в месяц. А опытный может и 300-500т. Мы обучим вас сами: — 3 дня уроков по 30 минут — Домашки с проверкой и оплатой бонусами — Платим 10 тыс за каждую выполненную домашку ⚡ Набор заканчивается завтра. Для регистрации жмите кнопку "Зарегистрироваться": Зарегистрироваться #реклама 16+ ganstaagency.com О рекламодателе

Задача: 418. Sentence Screen Fitting Сложность: medium Если задан экран rows x cols и предложение, представленное в виде списка строк, верните количество раз, которое данное предложение может быть помещено на экран. Порядок слов в предложении должен оставаться неизменным, и слово не может быть разбито на две строки. Два последовательных слова в строке должны разделяться одним пробелом. Пример:

    
        Input: sentence = ["hello","world"], rows = 2, cols = 8
Output: 1{}
    

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

    
        public class Solution {
    public int wordsTyping(String[] sentence, int rows, int cols) {
        String sentenceStr = String.join(" ", sentence) + " ";
        int length = sentenceStr.length();
        int count = 0;
        
        for (int i = 0; i < rows; i++) {
            count += cols;
            if (sentenceStr.charAt(count % length) == ' ') {
                count++;
            } else {
                while (count > 0 && sentenceStr.charAt((count - 1) % length) != ' ') {
                    count--;
                }
            }
        }
        
        return count / length;
    }
}{}
    

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

Задача: 1257. Smallest Common Region Сложность: medium Вам даны списки регионов, в которых первый регион каждого списка включает все остальные регионы этого списка. Естественно, если регион x содержит другой регион y, то x больше y. Также, по определению, регион x содержит сам себя. Даны два региона: region1 и region2, верните наименьший регион, который содержит их оба. Если вам даны регионы r1, r2 и r3 такие, что r1 включает r3, то гарантированно не существует r2 такого, что r2 включает r3. Гарантированно существует наименьший регион. Пример:

    
        Input:
regions = [["Earth","North America","South America"],
["North America","United States","Canada"],
["United States","New York","Boston"],
["Canada","Ontario","Quebec"],
["South America","Brazil"]],
region1 = "Quebec",
region2 = "New York"
Output: "North America"{}
    

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

    
        import java.util.*;

public class Solution {
    public String findSmallestRegion(List<List<String>> regions, String region1, String region2) {
        Map<String, String> parent = new HashMap<>();

        for (List<String> regionList : regions) {
            for (int i = 1; i < regionList.size(); i++) {
                parent.put(regionList.get(i), regionList.get(0));
            }
        }

        Set<String> ancestors1 = new HashSet<>();
        while (region1 != null) {
            ancestors1.add(region1);
            region1 = parent.get(region1);
        }

        while (!ancestors1.contains(region2)) {
            region2 = parent.get(region2);
        }

        return region2;
    }
}{}
    

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

Раньше — выгоднее. Берите календарь направлений с чек-листами, получайте скидку 5 000 ₽ за раннее бронирование от 60 000 ₽ и бронируйте отпуск, пока лучшие варианты ещё доступны. Забронировать #реклама 16+ special.travel.yandex.ru О рекламодателе

Задача: 1338. Reduce Array Size to The Half Сложность: medium Дан массив целых чисел arr. Вы можете выбрать набор чисел и удалить все вхождения этих чисел из массива. Верните минимальный размер набора, чтобы было удалено не менее половины целых чисел из массива. Пример:

    
        Input: arr = [3,3,3,3,5,5,5,2,2,7]
Output: 2
Explanation: Choosing {3,7} will make the new array [5,5,5,2,2] which has size 5 (i.e equal to half of the size of the old array).
Possible sets of size 2 are {3,5},{3,2},{5,2}.
Choosing set {2,7} is not possible as it will make the new array [3,3,3,3,5,5,5] which has a size greater than half of the size of the old array.{}
    

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

    
        class Solution {
    public int minSetSize(int[] arr) {
        Arrays.sort(arr);
        List<Integer> counts = new ArrayList<>();
        int currentRun = 1;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] == arr[i - 1]) {
                currentRun += 1;
                continue;
            }
            counts.add(currentRun);
            currentRun = 1;
        }
        counts.add(currentRun);
        Collections.sort(counts);
        Collections.reverse(counts);
        int numbersRemovedFromArr = 0;
        int setSize = 0;
        for (int count : counts) {
            numbersRemovedFromArr += count;
            setSize += 1;
            if (numbersRemovedFromArr >= arr.length / 2) {
                break;
            }
        }
        return setSize;
    }
}{}
    

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

Задача: 1160. Find Words That Can Be Formed by Characters Сложность: easy Вам дан массив строк words и строка chars. Строка считается хорошей, если она может быть составлена из символов chars (каждый символ может быть использован только один раз). Верните сумму длин всех хороших строк в words. Пример:

    
        Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation: The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.{}
    

👨‍💻 Алгоритм: 1⃣Создайте хеш-таблицу counts, которая будет записывать частоту каждого символа в chars. Инициализируйте переменную ans = 0. 2⃣Итерируйте по каждому слову в words. Создайте хеш-таблицу wordCount, которая будет записывать частоту каждого символа в слове. Установите good = true. Итерируйте по каждому ключу c в wordCount. Пусть freq = wordCount[c]. Если counts[c] < freq, установите good = false и прервите цикл. 3⃣Если good = true, добавьте длину слова к ans. Верните ans. 😎 Решение:

    
        class Solution {
    public int countCharacters(String[] words, String chars) {
        Map<Character, Integer> counts = new HashMap<>();
        for (char c : chars.toCharArray()) {
            counts.put(c, counts.getOrDefault(c, 0) + 1);
        }
        
        int ans = 0;
        for (String word : words) {
            Map<Character, Integer> wordCount = new HashMap<>();
            for (char c : word.toCharArray()) {
                wordCount.put(c, wordCount.getOrDefault(c, 0) + 1);
            }
            
            boolean good = true;
            for (Map.Entry<Character, Integer> entry : wordCount.entrySet()) {
                if (counts.getOrDefault(entry.getKey(), 0) < entry.getValue()) {
                    good = false;
                    break;
                }
            }
            
            if (good) {
                ans += word.length();
            }
        }
        
        return ans;
    }
}{}
    

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