Java | LeetCode
Open in Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
Show more
Network:6 527
Subscribers
-324 hours
-177 days
-4630 days
Data loading in progress...
Similar Channels
Tags Cloud
Incoming and Outgoing Mentions
---
---
---
---
---
---
Attracting Subscribers
August '26
August '26
+25
in 0 channels
July '26
+33
in 0 channels
Get PRO
June '26
+42
in 1 channels
Get PRO
May '26
+33
in 0 channels
Get PRO
April '26
+36
in 0 channels
Get PRO
March '26
+44
in 0 channels
Get PRO
February '26
+49
in 0 channels
Get PRO
January '26
+54
in 1 channels
Get PRO
December '25
+47
in 0 channels
Get PRO
November '25
+98
in 0 channels
Get PRO
October '25
+98
in 0 channels
Get PRO
September '25
+101
in 1 channels
Get PRO
August '25
+164
in 2 channels
Get PRO
July '25
+176
in 3 channels
Get PRO
June '25
+139
in 0 channels
Get PRO
May '25
+190
in 2 channels
Get PRO
April '25
+219
in 0 channels
Get PRO
March '25
+264
in 1 channels
Get PRO
February '25
+358
in 6 channels
Get PRO
January '25
+362
in 53 channels
Get PRO
December '24
+221
in 0 channels
Get PRO
November '24
+249
in 0 channels
Get PRO
October '24
+478
in 12 channels
Get PRO
September '24
+1 577
in 330 channels
Get PRO
August '24
+291
in 0 channels
Get PRO
July '24
+1 602
in 219 channels
Get PRO
June '24
+2 260
in 232 channels
| Date | Subscriber Growth | Mentions | Channels | |
| 26 August | 0 | |||
| 25 August | +1 | |||
| 24 August | 0 | |||
| 23 August | 0 | |||
| 22 August | +1 | |||
| 21 August | +4 | |||
| 20 August | 0 | |||
| 19 August | +2 | |||
| 18 August | 0 | |||
| 17 August | +3 | |||
| 16 August | 0 | |||
| 15 August | +2 | |||
| 14 August | +1 | |||
| 13 August | +1 | |||
| 12 August | 0 | |||
| 11 August | 0 | |||
| 10 August | +2 | |||
| 09 August | +3 | |||
| 08 August | 0 | |||
| 07 August | 0 | |||
| 06 August | 0 | |||
| 05 August | +1 | |||
| 04 August | +1 | |||
| 03 August | +2 | |||
| 02 August | +1 | |||
| 01 August | 0 |
Channel Posts
Нужны 7 желающих для работы с искусственным интеллектом.
Работа из дома. График свободный.
Пришло задание — изучили — выполнили — получили свои деньги.
Деньги вы получаете в зависимости от сложности задания. Например:
За задание могут платить 500-10.000 рублей.
В зависимости от сложности.
500 рублей — это около 5-30 минут.
10 000 руб. это 5-6 часов.
Работа может быть разной: Оживить фото, создать видео, реставрировать старое фото и т.д.
💰 В среднем новичок получает до 150.000 руб в месяц. А опытный может и 300-500т.
Мы обучим вас сами:
— 3 дня уроков по 30 минут
— Домашки с проверкой
⚡ Набор заканчивается завтра.
Для регистрации жмите кнопку "Зарегистрироваться":
Зарегистрироваться
#реклама 16+
neuromachina.ru
О рекламодателе
| 2 | Задача: 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;
}
}
Ставь 👍 и забирай 📚 Базу знаний | 169 |
| 3 |  Автомобили LADA с выгодой в лизинг для таксопарков
Выгода на автомобили LADA по программе LADA Лизинг ПРО для таксопарков.
Узнать больше
#реклама
lada.ru
О рекламодателе | 262 |
| 4 | Задача: 1277. Count Square Submatrices with All Ones
Сложность: medium
Если задана матрица m * n из единиц и нулей, верните, сколько квадратных подматриц имеют все единицы.
Пример:
Input: matrix =
[
[0,1,1,1],
[1,1,1,1],
[0,1,1,1]
]
Output: 15
👨💻 Алгоритм:
1⃣Создайте вспомогательную матрицу dp таких же размеров, что и исходная матрица, для хранения размеров максимальных квадратов.
2⃣Пройдите по каждому элементу матрицы и обновите dp следующим образом: если элемент равен 1, то dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1.
3⃣Суммируйте все значения в dp, чтобы получить количество квадратных подматриц, состоящих из всех единиц.
😎 Решение:
public class Solution {
public int countSquares(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int[][] dp = new int[m][n];
int count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 1) {
if (i == 0 || j == 0) {
dp[i][j] = 1;
} else {
dp[i][j] = Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1])) + 1;
}
count += dp[i][j];
}
}
}
return count;
}
}
Ставь 👍 и забирай 📚 Базу знаний | 286 |
| 5 |  Онлайн-колледж. Обучение по специальности «Логистике»
Обучаем на Логиста. Поступление без ЕГЭ/ОГЭ и конкурса. На базе 9-11 классов.
Узнать больше
#реклама 16+
pk.i-spo.ru
О рекламодателе | 315 |
| 6 | Пожизненный PRO доступ на easyoffer — по цене одного года!
До 2 сентября вы можете купить PRO навсегда.
Покупаешь один раз — пользуешься всю жизнь.
– База вопросов и задач из собеседований
– Примеры видео-ответов на вопросы
– Записи реальных собеседований
– Тренажеры "Проработка вопросов" и "Реальное собеседование"
– Аналитика требований из вакансий
– Автоотклики на вакансии
– Агрегатор вакансий (скоро)
👉 Купить PRO со скидкой 70%: https://easyoffer.ru/pro | 306 |
| 7 | Задача: 1329. Sort the Matrix Diagonally
Сложность: medium
Диагональ матрицы — это диагональная линия ячеек, начинающаяся с какой-либо ячейки в самой верхней строке или в самом левом столбце и идущая в направлении вниз-вправо до конца матрицы. Например, диагональ матрицы, начинающаяся с mat[2][0], где mat — это матрица размером 6 x 3, включает ячейки mat[2][0], mat[3][1] и mat[4][2].
Дана матрица mat размером m x n, состоящая из целых чисел. Отсортируйте каждую диагональ матрицы по возрастанию и верните полученную матрицу.
Пример:
Input: mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
Output: [[1,1,1,1],[1,2,2,2],[1,2,3,3]]
👨💻 Алгоритм:
1⃣Сохраните размеры матрицы m и n. Создайте хеш-карту из минимальных куч для хранения элементов диагоналей.
2⃣Вставьте значения в хеш-карту, используя разность между индексами строки и столбца как ключ, чтобы собирать элементы на одной и той же диагонали.
3⃣Извлеките значения из хеш-карты и обновите матрицу, заполняя ее отсортированными значениями диагоналей. Верните отсортированную матрицу.
😎 Решение:
class Solution {
public int[][] diagonalSort(int[][] mat) {
int m = mat.length;
int n = mat[0].length;
Map<Integer, PriorityQueue<Integer>> diagonals = new HashMap<>();
for (int row = 0; row < m; row++) {
for (int col = 0; col < n; col++) {
int key = row - col;
diagonals.putIfAbsent(key, new PriorityQueue<>());
diagonals.get(key).add(mat[row][col]);
}
}
for (int row = 0; row < m; row++) {
for (int col = 0; col < n; col++) {
int key = row - col;
mat[row][col] = diagonals.get(key).poll();
}
}
return mat;
}
}
Ставь 👍 и забирай 📚 Базу знаний | 269 |
| 8 | Задача: 172. Factorial Trailing Zeroes
Сложность: medium
Дано целое число n, верните количество конечных нулей в n!.
Обратите внимание, что n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1.
Пример:
Input: n = 3
Output: 0
Explanation: 3! = 6, no trailing zero.
👨💻 Алгоритм:
1⃣Вычислите факториал n:
Инициализируйте переменную nFactorial значением 1.
Для каждого i от 2 до n включительно умножайте nFactorial на i.
2⃣Подсчитайте количество конечных нулей в nFactorial:
Инициализируйте переменную zeroCount значением 0.
Пока nFactorial делится на 10 без остатка, делите его на 10 и увеличивайте zeroCount на 1.
3⃣Верните значение zeroCount как количество конечных нулей в n!.
😎 Решение:
import java.math.BigInteger;
class Solution {
public int trailingZeroes(int n) {
BigInteger nFactorial = BigInteger.ONE;
for (int i = 2; i <= n; i++) {
nFactorial = nFactorial.multiply(BigInteger.valueOf(i));
}
int zeroCount = 0;
while (nFactorial.mod(BigInteger.TEN).equals(BigInteger.ZERO)) {
nFactorial = nFactorial.divide(BigInteger.TEN);
zeroCount++;
}
return zeroCount;
}
}
Ставь 👍 и забирай 📚 Базу знаний | 295 |
| 9 |  +3Подготовка к вступительным экзаменам в ШАД
120+ поступивших в ШАД. Преподаватели МГУ. Гарантия результата. Вы поступите в ШАД, магистратуру или мы зачислим Вас на следующий поток бесплатно
Узнать больше
#реклама 16+
shadhelper.com
О рекламодателе | 330 |
| 10 | Задача: 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;
}
}
Ставь 👍 и забирай 📚 Базу знаний | 338 |
| 11 |  Услуги коммерческого дата-центра в Москве
Размещение серверного оборудования в дата-центре.
✅ Услуги предоставляются в 4 дата-центрах в Москве.
✅ Географическое резервирование.
✅ Высокая отказоустойчивость.
✅ Гибкость при выборе площадки для размещения оборудования.
Узнать цену
#реклама
itsoft.ru
О рекламодателе | 324 |
| 12 | Задача: 826. Most Profit Assigning Work
Сложность: medium
У вас есть n заданий и m рабочих. Вам даны три массива: difficulty, profit и worker, где:
difficulty[i] и profit[i] — сложность и прибыль i-го задания,
worker[j] — способность j-го рабочего (т.е. j-й рабочий может выполнить задание со сложностью не больше worker[j]).
Каждому рабочему можно назначить не более одного задания, но одно задание может быть выполнено несколько раз.
Например, если три рабочих выполняют одно и то же задание с оплатой $1, общая прибыль составит $3. Если рабочий не может выполнить ни одно задание, его прибыль равна $0.
Верните максимальную прибыль, которую можно получить после распределения рабочих по заданиям.
Пример:
Input: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
Output: 100
Explanation: Workers are assigned jobs of difficulty [4,4,6,6] and they get a profit of [20,20,30,30] separately.
👨💻 Алгоритм:
1⃣Создание и сортировка профиля работы
Инициализируйте массив пар jobProfile с {0, 0}. Для каждого задания добавьте {difficulty[i], profit[i]} в jobProfile. Отсортируйте jobProfile по возрастанию сложности.
2⃣Обновление максимальной прибыли для каждой сложности
Обновите значение прибыли каждой сложности, чтобы оно было максимальным из текущего значения и предыдущего значения прибыли.
3⃣Вычисление максимальной прибыли
Для каждой способности рабочего используйте бинарный поиск, чтобы найти задание с наибольшей прибылью, которую может выполнить этот рабочий. Суммируйте полученную прибыль для всех рабочих и верните ее.
😎 Решение:
class Solution {
public int maxProfitAssignment(
int[] difficulty,
int[] profit,
int[] worker
) {
List<int[]> jobProfile = new ArrayList<>();
jobProfile.add(new int[] { 0, 0 });
for (int i = 0; i < difficulty.length; i++) {
jobProfile.add(new int[] { difficulty[i], profit[i] });
}
Collections.sort(jobProfile, (a, b) -> Integer.compare(a[0], b[0]));
for (int i = 0; i < jobProfile.size() - 1; i++) {
jobProfile.get(i + 1)[1] = Math.max(
jobProfile.get(i)[1],
jobProfile.get(i + 1)[1]
);
}
int netProfit = 0;
for (int i = 0; i < worker.length; i++) {
int ability = worker[i];
int l = 0, r = jobProfile.size() - 1, jobProfit = 0;
while (l <= r) {
int mid = (l + r) / 2;
if (jobProfile.get(mid)[0] <= ability) {
jobProfit = Math.max(jobProfit, jobProfile.get(mid)[1]);
l = mid + 1;
} else {
r = mid - 1;
}
}
netProfit += jobProfit;
}
return netProfit;
}
Ставь 👍 и забирай 📚 Базу знаний | 317 |
| 13 |  Скидка 25% на гели Ariel и Tide!
Скидка 25% в Любимой категории на товары брендов Ariel и Tide
Купить
#реклама
market.yandex.ru
О рекламодателе | 278 |
| 14 | Задача: 1019. Next Greater Node In Linked List
Сложность: medium
Вам дана голова связного списка с n узлами. Для каждого узла в списке найдите значение следующего большего узла. То есть для каждого узла найдите значение первого узла, который находится рядом с ним и имеет строго большее значение, чем он. Верните целочисленный массив answer, где answer[i] - это значение следующего большего узла ith-узла (с индексацией по 1). Если у узла ith нет следующего большего узла, установите answer[i] = 0.
Пример:
Input: head = [2,1,5]
Output: [5,5,0]
👨💻 Алгоритм:
1⃣Инициализация переменных:
Пройдитесь по всему списку и сохраните значения узлов в массив.
Инициализируйте стек для хранения индексов узлов, которые нужно обработать.
2⃣Поиск следующего большего элемента:
Итерируйте по массиву значений узлов.
Для каждого элемента, пока стек не пуст и текущий элемент больше, чем элемент на вершине стека, обновите массив ответов значением текущего элемента и удалите элемент из стека.
Добавьте текущий индекс в стек.
3⃣Заполнение оставшихся значений:
Для всех индексов, оставшихся в стеке, установите значение ответа равным 0, так как для них не найдено большего элемента.
😎 Решение:
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
public int[] nextLargerNodes(ListNode head) {
List<Integer> values = new ArrayList<>();
while (head != null) {
values.add(head.val);
head = head.next;
}
int[] answer = new int[values.size()];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < values.size(); i++) {
while (!stack.isEmpty() && values.get(stack.peek()) < values.get(i)) {
answer[stack.pop()] = values.get(i);
}
stack.push(i);
}
return answer;
}
}
Ставь 👍 и забирай 📚 Базу знаний | 362 |
| 15 |  Из разработчика в тимлиды: как говорить с людьми
Стать тимлидом — значит научиться говорить с людьми о сложном. Но как сказать разработчику, что код — "не очень", не обидев?
📅 16 сентября в 20:00 Александр Пряхин разберет техники обратной связи без эскалации. Узнаете, как формулировать по фактам, снижать защитную реакцию и завершать разговор договоренностями. Для разработчиков, готовящихся к лидерству.
Узнать больше
#реклама 16+
otus.ru
О рекламодателе | 332 |
| 16 | Задача: №29. Divide Two Integers
Сложность: medium
Даны два целых числа dividend и divisor.
Выполните деление без использования операторов *, /, %.
Результат должен быть усечён до целого и находиться в пределах 32-битного целого числа.
Пример:
Input: dividend = 10, divisor = 3 Output: 3
Input: dividend = 7, divisor = -3 Output: -2
👨💻 Алгоритм:
1⃣Определить знак результата и привести dividend и divisor к положительным значениям типа long, чтобы избежать переполнения и упростить работу с отрицательными числами.
2⃣Найти максимальное кратное делителя (удваивая divisor и счётчик divide), не превышающее dividend.
3⃣Рекурсивно вызвать деление для остатка dividend - sum, сложить с текущим divide и вернуть результат с учётом знака.
😎 Решение:
public class Solution {
public int divide(int dividend, int divisor) {
long result = divideLong(dividend, divisor);
return result > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int)result;
}
private long divideLong(long dividend, long divisor) {
boolean negative = dividend < 0 != divisor < 0;
dividend = Math.abs(dividend);
divisor = Math.abs(divisor);
if (dividend < divisor) return 0;
long sum = divisor;
long divide = 1;
while ((sum + sum) <= dividend) {
sum += sum;
divide += divide;
}
long remaining = divideLong(dividend - sum, divisor);
return negative ? -(divide + remaining) : (divide + remaining);
}
}
Ставь 👍 и забирай 📚 Базу знаний | 430 |
| 17 | Задача: 1220. Count Vowels Permutation
Сложность: hard
Дано целое число n, ваша задача состоит в том, чтобы посчитать, сколько строк длины n можно сформировать по следующим правилам:
Каждый символ является строчной гласной буквой ('a', 'e', 'i', 'o', 'u')
Каждая гласная 'a' может быть только перед 'e'.
Каждая гласная 'e' может быть только перед 'a' или 'i'.
Каждая гласная 'i' не может быть перед другой 'i'.
Каждая гласная 'o' может быть только перед 'i' или 'u'.
Каждая гласная 'u' может быть только перед 'a'.
Так как ответ может быть слишком большим, верните его по модулю 10^9 + 7.
Пример:
Input: n = 2
Output: 10
Explanation: All possible strings are: "ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" and "ua".
👨💻 Алгоритм:
1⃣Инициализация массивов и начальных условий:
Инициализируйте пять одномерных массивов размером n для хранения количества строк, оканчивающихся на каждую гласную.
Установите первый элемент в каждом массиве равным 1, так как для строк длиной 1 существует только одна возможная строка для каждой гласной.
2⃣Заполнение массивов в соответствии с правилами:
Проходите по длине строки от 1 до n.
Обновляйте значения массивов, следуя правилам для каждой гласной, учитывая предыдущие значения.
3⃣Суммирование и возврат результата:
Возьмите сумму последних элементов всех пяти массивов.
Верните результат по модулю 10^9 + 7.
😎 Решение:
class Solution {
public int countVowelPermutation(int n) {
long[] aVowelPermutationCount = new long[n];
long[] eVowelPermutationCount = new long[n];
long[] iVowelPermutationCount = new long[n];
long[] oVowelPermutationCount = new long[n];
long[] uVowelPermutationCount = new long[n];
aVowelPermutationCount[0] = 1L;
eVowelPermutationCount[0] = 1L;
iVowelPermutationCount[0] = 1L;
oVowelPermutationCount[0] = 1L;
uVowelPermutationCount[0] = 1L;
int MOD = 1000000007;
for (int i = 1; i < n; i++) {
aVowelPermutationCount[i] = (eVowelPermutationCount[i - 1] + iVowelPermutationCount[i - 1] + uVowelPermutationCount[i - 1]) % MOD;
eVowelPermutationCount[i] = (aVowelPermutationCount[i - 1] + iVowelPermutationCount[i - 1]) % MOD;
iVowelPermutationCount[i] = (eVowelPermutationCount[i - 1] + oVowelPermutationCount[i - 1]) % MOD;
oVowelPermutationCount[i] = iVowelPermutationCount[i - 1] % MOD;
uVowelPermutationCount[i] = (iVowelPermutationCount[i - 1] + oVowelPermutationCount[i - 1]) % MOD;
}
long result = 0L;
result = (aVowelPermutationCount[n - 1] + eVowelPermutationCount[n - 1] + iVowelPermutationCount[n - 1] + oVowelPermutationCount[n - 1] + uVowelPermutationCount[n - 1]) % MOD;
return (int)result;
}
}
Ставь 👍 и забирай 📚 Базу знаний | 359 |
| 18 |  Хотите внедрить ИИ, но не знаете с чего начать?
ГигаАкадемия запустила ИИ-менторинг — индивидуальную сессию с практикующим экспертом для собственников и бенефициаров.
Никакой теории. Только вы, эксперт и ваша задача.
Три часа фокуса на вашем запросе.
Ментор разбирает процессы, данные и ограничения и помогает определить, где ИИ быстрее всего даст бизнес-эффект и повлияет на рост выручки.
Вы уходите не с вдохновением, а с планом:
— карта вашего ИИ-кейса: задача, эффект, риски
— 3 приоритетных сценария — где ценность выше, а запуск проще
— дорожная карта пилота на 2–6 недель
Цель ментора — усилить вашу экспертизу: научить самостоятельно находить, оценивать и запускать ИИ-решения.
ИИ уже готов работать на вас. А вы готовы взять его в партнёры?
Оставьте заявку на сайте и получите консультацию.
Узнать больше
Номер реестровой записи: С502024004938.
#реклама 16+
sberuniversity.ru
О рекламодателе | 305 |
| 19 | Задача: 568. Maximum Vacation Days
Сложность: hard
LeetCode хочет предоставить одному из своих лучших сотрудников возможность путешествовать по n городам для сбора задач по алгоритмам. Однако, как говорится, "делу время, потехе час". Вы можете брать отпуска в некоторых конкретных городах и неделях. Ваша задача — спланировать поездку, чтобы максимально увеличить количество дней отпуска, которые вы сможете взять, соблюдая при этом определенные правила и ограничения.
Правила и ограничения:
Вы можете путешествовать только между n городами, обозначенными индексами от 0 до n-1. Изначально вы находитесь в городе с индексом 0 в понедельник.
Города связаны рейсами. Рейсы представлены матрицей n x n, называемой flights, представляющей статус авиалинии от города i до города j. Если рейса из города i в город j нет, flights[i][j] == 0; иначе flights[i][j] == 1. Также для всех i выполняется flights[i][i] == 0.
У вас есть k недель (каждая неделя состоит из семи дней) для путешествий. Вы можете летать не более одного раза в день и можете летать только утром каждого понедельника. Время полета настолько короткое, что его влияние не учитывается.
Для каждого города у вас есть ограниченные дни отпуска в разные недели, заданные матрицей n x k, называемой days. Значение days[i][j] представляет максимальное количество дней отпуска, которые вы можете взять в городе i на неделе j.
Даны две матрицы flights и days, верните максимальное количество дней отпуска, которые вы можете взять в течение k недель.
Пример:
Input: flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[6,0,3],[3,3,3]]
Output: 12
Explanation:
One of the best strategies is:
1st week : fly from city 0 to city 1 on Monday, and play 6 days and work 1 day.
(Although you start at city 0, we could also fly to and start at other cities since it is Monday.)
2nd week : fly from city 1 to city 2 on Monday, and play 3 days and work 4 days.
3rd week : stay at city 2, and play 3 days and work 4 days.
Ans = 6 + 3 + 3 = 12.
👨💻 Алгоритм:
1⃣Использовать функцию dfs (поиск в глубину), которая возвращает количество отпускных дней, которые можно взять, начиная с текущего города cur_city и текущей недели weekno. В каждом вызове функции проходить по всем городам и находить все города, которые связаны с текущим городом. Такой город обозначен 1 в соответствующей позиции flights[cur_city][i].
2⃣Для текущего города можно либо остаться в нем, либо поехать в связанный город. Обозначим город, в который меняется расположение, как j. После смены города нужно найти количество отпускных дней, которые можно взять, начиная с нового города и с новой недели. Это количество отпускных дней можно представить как: days[j][weekno] + dfs(flights, days, j, weekno + 1).
3⃣Для текущего города необходимо найти максимальное количество отпускных дней, выбирая различные города в качестве следующего местоположения. Из всех вариантов отпускных дней выбираем максимальное значение, которое и будет возвращено для каждого вызова функции dfs.
😎 Решение:
public class Solution {
public int maxVacationDays(int[][] flights, int[][] days) {
int n = flights.length;
int k = days[0].length;
int[][] memo = new int[n][k];
for (int[] row : memo) {
Arrays.fill(row, -1);
}
return dfs(flights, days, memo, 0, 0);
}
private int dfs(int[][] flights, int[][] days, int[][] memo, int curCity, int weekNo) {
int n = flights.length;
int k = days[0].length;
if (weekNo == k) return 0;
if (memo[curCity][weekNo] != -1) return memo[curCity][weekNo];
int maxVac = 0;
for (int nextCity = 0; nextCity < n; nextCity++) {
if (curCity == nextCity || flights[curCity][nextCity] == 1) {
maxVac = Math.max(maxVac, days[nextCity][weekNo] + dfs(flights, days, memo, nextCity, weekNo + 1));
}
}
memo[curCity][weekNo] = maxVac;
return maxVac;
}
}
Ставь 👍 и забирай 📚 Базу знаний | 344 |
| 20 | Задача: 932. Beautiful Array
Сложность: medium
Массив nums длины n красив, если: nums является перестановкой целых чисел в диапазоне [1, n]. Для каждого 0 <= i < j < n не существует индекса k с i < k < j, где 2 * nums[k] == nums[i] + nums[j]. Задано целое число n, верните любой красивый массив nums длины n. Для заданного n будет хотя бы один правильный ответ.
Пример:
Input: n = 4
Output: [2,1,4,3]
👨💻 Алгоритм:
1⃣Использовать рекурсивный метод для создания красивого массива.
2⃣Если длина массива равна 1, вернуть массив [1].
Разделить n на четные и нечетные индексы и создать массивы для них.
3⃣Объединить массивы, созданные для четных и нечетных индексов, в результирующий массив.
😎 Решение:
import java.util.ArrayList;
import java.util.List;
class Solution {
public int[] beautifulArray(int n) {
List<Integer> result = construct(n);
int[] resArray = new int[result.size()];
for (int i = 0; i < result.size(); i++) {
resArray[i] = result.get(i);
}
return resArray;
}
private List<Integer> construct(int n) {
if (n == 1) {
List<Integer> base = new ArrayList<>();
base.add(1);
return base;
}
List<Integer> odd = construct((n + 1) / 2);
List<Integer> even = construct(n / 2);
List<Integer> result = new ArrayList<>();
for (int x : odd) {
result.add(2 * x - 1);
}
for (int x : even) {
result.add(2 * x);
}
return result;
}
}
Ставь 👍 и забирай 📚 Базу знаний | 400 |
