Java | LeetCode
الذهاب إلى القناة على Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
إظهار المزيد
الشبكة:6 519
المشتركون
-324 ساعات
-197 أيام
-5030 أيام
أرشيف المشاركات
6 519
Задача: 1032. Stream of Characters
Сложность: hard
Разработайте алгоритм, который принимает поток символов и проверяет, является ли суффикс этих символов строкой заданного массива строк words. Например, если words = ["abc", "xyz"] и в поток добавлены четыре символа (один за другим) 'a', 'x', 'y' и 'z', ваш алгоритм должен определить, что суффикс "xyz" символов "axyz" соответствует "xyz" из words.
Реализуйте класс StreamChecker: StreamChecker(String[] words) Инициализирует объект с массивом строк words. boolean query(char letter) Принимает новый символ из потока и возвращает true, если любой непустой суффикс из потока образует слово, которое есть в words.
Пример:
Input ["StreamChecker", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query"] [[["cd", "f", "kl"]], ["a"], ["b"], ["c"], ["d"], ["e"], ["f"], ["g"], ["h"], ["i"], ["j"], ["k"], ["l"]] Output [null, false, false, false, true, false, true, false, false, false, false, false, true]👨💻 Алгоритм: 1⃣Построение суффиксного Trie: Создайте суффиксный Trie (префиксное дерево) для хранения всех слов из массива words в обратном порядке. Это позволяет эффективно искать слова, которые являются суффиксами потока символов. 2⃣Проверка суффиксов: Для каждого нового символа, проходите по текущему списку символов и проверяйте, образуют ли они какой-либо суффикс, присутствующий в Trie. Если найдено совпадение, возвращайте true, иначе продолжайте добавлять новые символы и проверять суффиксы. 3⃣Сравнение двух случаев: Рассмотрите оба случая: подмассив длины firstLen до подмассива длины secondLen и подмассив длины secondLen до подмассива длины firstLen. Найдите максимальную сумму для каждого случая. 😎 Решение:
import java.util.*;
class TrieNode {
Map<Character, TrieNode> children = new HashMap<>();
boolean isEndOfWord = false;
}
public class StreamChecker {
private TrieNode root;
private StringBuilder stream;
public StreamChecker(String[] words) {
root = new TrieNode();
stream = new StringBuilder();
for (String word : words) {
TrieNode node = root;
for (int i = word.length() - 1; i >= 0; i--) {
char ch = word.charAt(i);
node = node.children.computeIfAbsent(ch, k -> new TrieNode());
}
node.isEndOfWord = true;
}
}
public boolean query(char letter) {
stream.insert(0, letter);
TrieNode node = root;
for (int i = 0; i < stream.length(); i++) {
char ch = stream.charAt(i);
if (!node.children.containsKey(ch)) return false;
node = node.children.get(ch);
if (node.isEndOfWord) return true;
}
return false;
}
}6 519
Задача: 677. Map Sum Pairs
Сложность: medium
Создайте карту, которая позволяет выполнять следующие действия:
Отображает строковый ключ на заданное значение.
Возвращает сумму значений, у которых ключ имеет префикс, равный заданной строке.
Реализуйте класс MapSum:
MapSum() Инициализирует объект MapSum.
void insert(String key, int val) Вставляет пару ключ-значение в карту. Если ключ уже существовал, исходная пара ключ-значение будет заменена на новую.
int sum(string prefix) Возвращает сумму всех значений пар, у которых ключ начинается с данного префикса.
Пример:
Input
["MapSum", "insert", "sum", "insert", "sum"]
[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
Output
[null, null, 3, null, 5]
Explanation
MapSum mapSum = new MapSum();
mapSum.insert("apple", 3);
mapSum.sum("ap"); // return 3 (apple = 3)
mapSum.insert("app", 2);
mapSum.sum("ap"); // return 5 (apple + app = 3 + 2 = 5)import java.util.HashMap;
class MapSum {
HashMap<String, Integer> map;
public MapSum() {
map = new HashMap<>();
}
public void insert(String key, int val) {
map.put(key, val);
}
public int sum(String prefix) {
int ans = 0;
for (String key: map.keySet()) {
if (key.startsWith(prefix)) {
ans += map.get(key);
}
}
return ans;
}
}6 519
Задача: 171. Excel Sheet Column Number
Сложность: easy
Дана строка
columnTitle, представляющая название столбца, как это отображается в Excel. Вернуть соответствующий номер столбца.
Пример:
Input: columnTitle = "A" Output: 1👨💻 Алгоритм: 1⃣Создайте отображение букв алфавита и их соответствующих значений (начиная с 1). 2⃣Инициализируйте переменную-аккумулятор result. 3⃣Начиная справа налево, вычислите значение символа в зависимости от его позиции и добавьте его к result. 😎 Решение:
class Solution {
public int titleToNumber(String s) {
int result = 0;
Map<Character, Integer> alpha_map = new HashMap<>();
for (int i = 0; i < 26; i++) {
int c = i + 65;
alpha_map.put((char) c, i + 1);
}
int n = s.length();
for (int i = 0; i < n; i++) {
char cur_char = s.charAt(n - 1 - i);
result += alpha_map.get(cur_char) * Math.pow(26, i);
}
return result;
}
}6 519
Бесплатный курс по дизайну: веб, графический и UX/UI
Научись создавать дизайн сайтов и приложений, инфографику для карточек на маркетплейсах и работать в Figma!
Студенты курса в среднем зарабатывают от 68 000 ₽ уже во время обучения💰
Этот курс для тебя, если ты:
✅ мечтаешь о новой профессии в digital, но не знаешь, с чего начать;
✅ чувствуешь, что хочешь большего — свободы, самореализации, творчества;
✅ полный новичок и хочешь систему, а не хаос;
✅ хочешь начать зарабатывать удалённо.
Зарегистрироваться
#реклама 16+
ydaev.ru
О рекламодателе
6 519
Задача: 1236. Web Crawler
Сложность: medium
Учитывая url startUrl и интерфейс HtmlParser, реализуйте веб-краулер для просмотра всех ссылок, которые находятся под тем же именем хоста, что и startUrl.Верните все ссылки, полученные вашим краулером, в любом порядке. Ваш краулер должен: Начинать со страницы: startUrl Вызывать HtmlParser.getUrls(url), чтобы получить все ссылки с веб-страницы с заданным url. Не просматривайте одну и ту же ссылку дважды. Исследуйте только те ссылки, которые находятся под тем же именем хоста, что и startUrl. Как показано в примере url выше, имя хоста - example.org. Для простоты можно считать, что все урлы используют протокол http без указания порта. Например, урлы http://leetcode.com/problems и http://leetcode.com/contest находятся под одним и тем же именем хоста, а урлы http://example.org/test и http://example.com/abc не находятся под одним и тем же именем хоста.
Пример:
Input: urls = [ "http://news.yahoo.com", "http://news.yahoo.com/news", "http://news.yahoo.com/news/topics/", "http://news.google.com", "http://news.yahoo.com/us" ] edges = [[2,0],[2,1],[3,2],[3,1],[0,4]] startUrl = "http://news.yahoo.com/news/topics/" Output: [ "http://news.yahoo.com", "http://news.yahoo.com/news", "http://news.yahoo.com/news/topics/", "http://news.yahoo.com/us" ]👨💻 Алгоритм: 1⃣Извлечение имени хоста: Сначала извлекаем имя хоста из начального URL для проверки всех последующих ссылок. 2⃣Использование очереди для BFS: Начинаем с начального URL и помещаем его в очередь. Пока очередь не пуста, извлекаем текущий URL, получаем все ссылки с этой страницы, и для каждой ссылки проверяем, принадлежит ли она тому же имени хоста. 3⃣Если да, и если мы еще не посещали эту ссылку, добавляем ее в очередь и отмечаем как посещенную. 😎 Решение:
import java.util.*;
public interface HtmlParser {
List<String> getUrls(String url);
}
public class Solution {
private String extractHostname(String url) {
return url.split("/")[2];
}
public List<String> crawl(String startUrl, HtmlParser htmlParser) {
String hostname = extractHostname(startUrl);
Set<String> visited = new HashSet<>();
Queue<String> queue = new LinkedList<>();
queue.offer(startUrl);
visited.add(startUrl);
while (!queue.isEmpty()) {
String url = queue.poll();
for (String nextUrl : htmlParser.getUrls(url)) {
if (!visited.contains(nextUrl) && extractHostname(nextUrl).equals(hostname)) {
visited.add(nextUrl);
queue.offer(nextUrl);
}
}
}
return new ArrayList<>(visited);
}
}6 519
Repost from easyoffer
⏳ Осталось 20 мест
Акция со скидкой 50% для первых 500 пользователей easyoffer подходит к концу
🔥 Узнай вопросы и задачи с собеседований в конкретных компаниях
🔥 Получи лучшие ответы и видео-примеры от middle/senior специалистов
🔥 Обходи фильтры ATS, добавив топ30 ключевых слов в свое резюме
🔥 Экономь время с помощью автоматических откликов
🔥 Подготовься идеально к интервью с тренажёрами и симуляторами
Успей забрать место по акции: 👉 https://easyoffer.ru/pro
6 519
Задача: 1287. Element Appearing More Than 25% In Sorted Array
Сложность: easy
Дан массив целых чисел, отсортированный в неубывающем порядке. В этом массиве есть ровно одно число, которое встречается более чем в 25% случаев. Верните это число.
Пример:
Input: arr = [1,2,2,6,6,6,6,7,10] Output: 6👨💻 Алгоритм: 1⃣Инициализируйте хеш-таблицу counts и перебирайте каждый элемент в массиве arr, увеличивая counts[num] для каждого элемента num. 2⃣Установите target = arr.length / 4. 3⃣Перебирайте каждую пару ключ-значение в counts и, если значение > target, верните ключ. Код никогда не достигнет этой точки, так как гарантируется, что ответ существует; верните любое значение. 😎 Решение:
import java.util.HashMap;
import java.util.Map;
class Solution {
public int findSpecialInteger(int[] arr) {
Map<Integer, Integer> counts = new HashMap<>();
int target = arr.length / 4;
for (int num : arr) {
counts.put(num, counts.getOrDefault(num, 0) + 1);
if (counts.get(num) > target) {
return num;
}
}
return -1;
}
}6 519
👩💻 Java вакансии всех грейдов: удалёнка, реклок, щедрый оффер!
Только с прямыми контактами в Telegram! Ноль автоотказов — живой диалог и быстрые объективные решения.
👩💻 Java 👩💻 Python
👩💻 Node.js 👣 Go
🤖 ML & DS 👩💻 DevOps
👩💻 C# 👩💻 Frontend
🔎 QA 🖥 SQL
👩💻 UX/UI 🖼️ PHP
👩💻 Mobile 📋 Analyst
💼 1C 👨✈️ CyberSec
👩💻 IT HR
Подпишись чтобы не упустить свой шанс получить лучший оффер!
6 519
Задача: 1491. Average Salary Excluding the Minimum and Maximum Salary
Сложность: easy
Вам дан массив уникальных целых чисел
salary, где salary[i] — это зарплата i-го сотрудника.
Верните среднюю зарплату сотрудников, исключая минимальную и максимальную зарплату. Ответы, отличающиеся не более чем на 10^-5 от фактического ответа, будут приняты.
Пример:
Input: salary = [4000,3000,1000,2000]
Output: 2500.00000
Explanation: Minimum salary and maximum salary are 1000 and 4000 respectively.
Average salary excluding minimum and maximum salary is (2000+3000) / 2 = 2500class Solution {
public double average(int[] salaries) {
int minSalary = Integer.MAX_VALUE;
int maxSalary = Integer.MIN_VALUE;
int sum = 0;
for (int salary : salaries) {
sum += salary;
minSalary = Math.min(minSalary, salary);
maxSalary = Math.max(maxSalary, salary);
}
return (double)(sum - minSalary - maxSalary) / (double)(salaries.length - 2);
}
}6 519
Задача: 909. Snakes and Ladders
Сложность: medium
Вам дана доска с целочисленной матрицей n x n, клетки которой помечены метками от 1 до n2 в стиле Бустрофедона, начиная с левого нижнего края доски (т.е. board[n - 1][0]) и чередуя направление в каждой строке. Вы начинаете на клетке 1 доски. В каждый ход, начиная с клетки curr, вы делаете следующее: выбираете клетку назначения next с меткой в диапазоне [curr + 1, min(curr + 6, n2)]. Этот выбор имитирует результат стандартного броска 6-гранного кубика: то есть всегда существует не более 6 мест назначения, независимо от размера доски. Если next имеет змейку или лестницу, вы должны двигаться к месту назначения этой змейки или лестницы. В противном случае вы переходите на следующий. Игра заканчивается, когда вы достигаете клетки n2. Клетка доски в строке r и столбце c имеет змейку или лестницу, если board[r][c] != -1. Местом назначения этой змейки или лестницы является доска[r][c]. В клетках 1 и n2 нет змейки или лестницы. Обратите внимание, что вы можете взять змейку или лестницу не более одного раза за ход. Если конечный пункт змейки или лестницы является началом другой змейки или лестницы, вы не ходите по последующей змейке или лестнице. Например, предположим, что доска имеет вид [[-1,4],[-1,3]], и на первом ходу ваш конечный квадрат - 2. Вы ходите по лестнице до квадрата 3, но не ходите по последующей лестнице до 4. Верните наименьшее количество ходов, необходимое для достижения квадрата n2. Если достичь квадрата невозможно, верните -1.
Пример:
Input: board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]] Output: 4👨💻 Алгоритм: 1⃣Представить доску в виде одномерного массива, чтобы легко определить позицию следующего хода. 2⃣Использовать BFS (поиск в ширину) для минимизации количества ходов до клетки n2. В каждом ходе проверять клетки от curr + 1 до min(curr + 6, n2) и перемещаться по змейкам и лестницам, если они существуют. 3⃣Если достижение клетки n2 невозможно, вернуть -1. 😎 Решение:
import java.util.*;
class Solution {
public int snakesAndLadders(int[][] board) {
int n = board.length;
int[] getPos(int x) {
int quot = (x - 1) / n;
int rem = (x - 1) % n;
int row = n - 1 - quot;
int col = (row % 2 != n % 2) ? rem : n - 1 - rem;
return new int[]{row, col};
}
Set<Integer> visited = new HashSet<>();
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{1, 0});
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int pos = curr[0];
int steps = curr[1];
for (int i = 1; i <= 6; i++) {
int nextPos = pos + i;
if (nextPos > n * n) continue;
int[] rc = getPos(nextPos);
int r = rc[0], c = rc[1];
if (board[r][c] != -1) {
nextPos = board[r][c];
}
if (nextPos == n * n) {
return steps + 1;
}
if (!visited.contains(nextPos)) {
visited.add(nextPos);
queue.offer(new int[]{nextPos, steps + 1});
}
}
}
return -1;
}
}6 519
Курс "Дизайн карточек для WB и Ozon". Бесплатно и с нуля
Дизайнер карточек для маркетплейсов — востребованная и доходная профессия 💰
Научись ей бесплатно!
- Бесплатный доступ
- Разбор ДЗ от наставника
- Мощные кейсы в портфолио
Узнать больше
#реклама 16+
yudaevschool24.online
О рекламодателе
6 519
Задача: 852. Peak Index in a Mountain Array
Сложность: medium
Вам дан целочисленный массив горы arr длины n, где значения увеличиваются до пикового элемента, а затем уменьшаются.
Верните индекс пикового элемента.
Ваша задача — решить это с временной сложностью O(log(n)).
Пример:
Input: arr = [0,1,0]
Output: 1class Solution {
public int peakIndexInMountainArray(int[] arr) {
int i = 0;
while (arr[i] < arr[i + 1]) {
i++;
}
return i;
}
}6 519
Repost from easyoffer
⏳ 90 акционных мест
Акция со скидкой 50% для первых 500 пользователей easyoffer подходит к концу
🔥 Узнай вопросы и задачи с собеседований в конкретных компаниях
🔥 Получи лучшие ответы и видео-примеры от middle/senior специалистов
🔥 Обходи фильтры ATS, добавив топ30 ключевых слов в свое резюме
🔥 Экономь время с помощью автоматических откликов
🔥 Подготовься идеально к интервью с тренажёрами и симуляторами
Успей забрать место по акции: 👉 https://easyoffer.ru/pro
6 519
Задача: 1533. Find the Index of the Large Integer
Сложность: medium
У нас есть целочисленный массив arr, в котором все элементы равны, кроме одного элемента, который больше остальных. Вам не будет предоставлен прямой доступ к массиву, вместо этого у вас будет API ArrayReader, который имеет следующие функции:
int compareSub(int l, int r, int x, int y): где 0 <= l, r, x, y < ArrayReader.length(), l <= r и x <= y. Функция сравнивает сумму подмассива arr[l..r] с суммой подмассива arr[x..y] и возвращает:
1, если arr[l] + arr[l+1] + ... + arr[r] > arr[x] + arr[x+1] + ... + arr[y].
0, если arr[l] + arr[l+1] + ... + arr[r] == arr[x] + arr[x+1] + ... + arr[y].
-1, если arr[l] + arr[l+1] + ... + arr[r] < arr[x] + arr[x+1] + ... + arr[y].
int length(): Возвращает размер массива.
Вам разрешено вызывать compareSub() не более 20 раз. Вы можете предположить, что обе функции работают за O(1) время.
Верните индекс массива arr, который содержит наибольший элемент.
Пример:
Input: arr = [7,7,7,7,10,7,7,7]
Output: 4
Explanation: The following calls to the API
reader.compareSub(0, 0, 1, 1) // returns 0 this is a query comparing the sub-array (0, 0) with the sub array (1, 1), (i.e. compares arr[0] with arr[1]).
Thus we know that arr[0] and arr[1] doesn't contain the largest element.
reader.compareSub(2, 2, 3, 3) // returns 0, we can exclude arr[2] and arr[3].
reader.compareSub(4, 4, 5, 5) // returns 1, thus for sure arr[4] is the largest element in the array.
Notice that we made only 3 calls, so the answer is valid.class Solution {
public int getIndex(ArrayReader reader) {
int left = 0;
int length = reader.length();
while (length > 1) {
length /= 2;
int cmp = reader.compareSub(left, left + length - 1, left + length, left + 2 * length - 1);
if (cmp == 0) {
return left + 2 * length;
}
if (cmp < 0) {
left += length;
}
}
return left;
}
}6 519
+2
Открыта регистрация на конференцию
Деловая программа конференции в первый день выставки:
Доклад: «Интенсив по медицинскому праву для специалистов косметологии» от Чернышук Николая Владимировича, практикующего юриста в сфере медицинского права.
Доклад: «Маркетинг в косметологии 2025–2026. Личный бренд врача» от Мильковской Алины Александровны, маркетолога-стратега, контент-мейкера.
В остальные дни выставки ждём вас на нашем стенде!
Зарегистрироваться
#реклама
mrqz.me
О рекламодателе
6 519
Задача: 1268. Search Suggestions System
Сложность: medium
Вам дан массив строк products и строка searchWord. Разработайте систему, которая предлагает не более трех названий продуктов после ввода каждого символа searchWord. Предлагаемые товары должны иметь общий префикс с searchWord. Если есть более трех продуктов с общим префиксом, возвращаются три лексикографически минимальных продукта. Возвращается список списков предложенных продуктов после ввода каждого символа searchWord.
Пример:
Input: products = ["havana"], searchWord = "havana" Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]👨💻 Алгоритм: 1⃣Отсортируйте массив продуктов. 2⃣Итерируйтесь по каждому символу в searchWord, находите все продукты, которые соответствуют текущему префиксу. 3⃣Сохраняйте не более трех лексикографически минимальных продуктов для каждого префикса. 😎 Решение:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
public List<List<String>> suggestedProducts(String[] products, String searchWord) {
Arrays.sort(products);
List<List<String>> result = new ArrayList<>();
String prefix = "";
for (char c : searchWord.toCharArray()) {
prefix += c;
List<String> suggestions = new ArrayList<>();
for (String product : products) {
if (product.startsWith(prefix)) {
suggestions.add(product);
if (suggestions.size() == 3) break;
}
}
result.add(suggestions);
}
return result;
}
}6 519
Задача: 1234. Replace the Substring for Balanced String
Сложность: medium
Вам дана строка s длины n, содержащая только четыре вида символов: 'Q', 'W', 'E' и 'R'. Строка считается сбалансированной, если каждый из ее символов встречается n / 4 раз, где n - длина строки. Верните минимальную длину подстроки, которую можно заменить любой другой строкой той же длины, чтобы сделать s сбалансированной. Если s уже сбалансирована, верните 0.
Пример:
Input: s = "QWER" Output: 0👨💻 Алгоритм: 1⃣Проверка баланса: Сначала проверим, сбалансирована ли строка s. Если да, то возвращаем 0. 2⃣Подсчет частоты символов: Подсчитаем количество каждого символа в строке s. 3⃣Использование скользящего окна: Используем метод двух указателей (скользящее окно) для нахождения минимальной подстроки, которую можно заменить, чтобы строка стала сбалансированной. Начнем с окна, которое захватывает всю строку, и будем постепенно уменьшать его, проверяя при каждом шаге, становится ли строка сбалансированной. 😎 Решение:
import java.util.HashMap;
import java.util.Map;
public class Solution {
public int balancedString(String s) {
int n = s.length();
Map<Character, Integer> count = new HashMap<>();
for (char c : s.toCharArray()) {
count.put(c, count.getOrDefault(c, 0) + 1);
}
int target = n / 4;
boolean isBalanced() {
return count.getOrDefault('Q', 0) <= target &&
count.getOrDefault('W', 0) <= target &&
count.getOrDefault('E', 0) <= target &&
count.getOrDefault('R', 0) <= target;
}
if (isBalanced()) return 0;
int minLength = n;
int left = 0;
for (int right = 0; right < n; right++) {
count.put(s.charAt(right), count.get(s.charAt(right)) - 1);
while (isBalanced()) {
minLength = Math.min(minLength, right - left + 1);
count.put(s.charAt(left), count.get(s.charAt(left)) + 1);
left++;
}
}
return minLength;
}
}6 519
Задача: 202. Happy Number
Сложность: easy
Напишите алгоритм для определения, является ли число n счастливым.
Счастливое число определяется следующим образом:
1. Начинаем с любого положительного числа и заменяем его на сумму квадратов его цифр.
2. Повторяем процесс до тех пор, пока число не станет равным 1 (где оно останется), или пока оно не зациклится бесконечно, не достигая 1.
3. Числа, для которых этот процесс заканчивается на 1, являются счастливыми.
4. Верните true, если n является счастливым числом, и false, если нет.
Пример:
Input: n = 19 Output: true Explanation: 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1👨💻 Алгоритм: 1⃣Определите следующее число для заданного числа n. Это можно сделать, используя операции деления и взятия по модулю, чтобы последовательно извлекать цифры из числа, пока они не закончатся, затем возводить каждую извлечённую цифру в квадрат и суммировать их. Внимательно посмотрите на код для этого, "извлечение цифр по одной" — полезная техника, которую вы будете использовать для решения множества различных задач. 2⃣Следите за цепочкой чисел и обнаруживайте, если мы вошли в цикл. Это можно сделать с помощью HashSet. Каждый раз, когда мы генерируем следующее число в цепочке, мы проверяем, есть ли оно уже в нашем HashSet. Если его нет в HashSet, мы добавляем его. Если оно уже в HashSet, это означает, что мы находимся в цикле и должны вернуть false. 3⃣Мы используем HashSet, а не Vector, List или Array, потому что мы многократно проверяем, находятся ли числа в нём. Проверка, находится ли число в HashSet, занимает время O(1), тогда как для других структур данных это занимает время O(n). Выбор правильных структур данных — важная часть решения этих задач. 😎 Решение:
class Solution {
private int getNext(int n) {
int totalSum = 0;
while (n > 0) {
int d = n % 10;
n = n / 10;
totalSum += d * d;
}
return totalSum;
}
public boolean isHappy(int n) {
Set<Integer> seen = new HashSet<>();
while (n != 1 && !seen.contains(n)) {
seen.add(n);
n = getNext(n);
}
return n == 1;
}
}6 519
Задача: 857. Minimum Cost to Hire K Workers
Сложность: hard
Есть n работников. Вам даны два целочисленных массива: quality и wage, где quality[i] — качество работы i-го работника, а wage[i] — минимальная ожидаемая заработная плата i-го работника.
Мы хотим нанять ровно k работников для формирования оплачиваемой группы. Чтобы нанять группу из k работников, мы должны оплатить их в соответствии со следующими правилами:
Каждому работнику в оплачиваемой группе должно быть выплачено как минимум его ожидаемое минимальное вознаграждение.
В группе заработная плата каждого работника должна быть прямо пропорциональна его качеству. Это означает, что если качество работы одного работника вдвое выше, чем у другого работника в группе, то ему должно быть выплачено вдвое больше.
Учитывая целое число k, верните наименьшую сумму денег, необходимую для формирования оплачиваемой группы, удовлетворяющей указанным условиям. Ответы с точностью до 10^-5 от фактического ответа будут приняты.
Пример:
Input: quality = [10,20,5], wage = [70,50,30], k = 2
Output: 105.00000
Explanation: We pay 70 to 0th worker and 35 to 2nd worker.class Solution {
public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
int n = quality.length;
double totalCost = Double.MAX_VALUE;
double currentTotalQuality = 0;
List<Pair<Double, Integer>> wageToQualityRatio = new ArrayList<>();
for (int i = 0; i < n; i++) {
wageToQualityRatio.add(new Pair<>((double) wage[i] / quality[i], quality[i]));
}
wageToQualityRatio.sort(Comparator.comparingDouble(Pair::getKey));
PriorityQueue<Integer> workers = new PriorityQueue<>(Collections.reverseOrder());
for (Pair<Double, Integer> pair : wageToQualityRatio) {
workers.add(pair.getValue());
currentTotalQuality += pair.getValue();
if (workers.size() > k) {
currentTotalQuality -= workers.poll();
}
if (workers.size() == k) {
totalCost = Math.min(totalCost, currentTotalQuality * pair.getKey());
}
}
return totalCost;
}
}6 519
Ищу желающих выполнять задачи с помощью ИИ!
Работа полностью на удаленке с зп до 150 000 рублей в месяц.
Без опыта, нужен только телефон, занятость 3-6 часов в день.
Всему обучат на бесплатном курсе и после возьму на работу:
✅ 3 дня уроков по 30 минут
✅ Домашки с проверкой и оплатой бонусами
✅ Плачу 10 тыс за каждую выполненную домашку
Все кто пройдет курс, получат сертификат от школы с образовательной лицензией.
⚡ Набор заканчивается завтра.
👍 Для регистрации жмите кнопку "Зарегистрироваться":
Зарегистрироваться
#реклама 16+
ganstaagency.com
О рекламодателе
