Java | LeetCode
Open in Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
Show more
Network:6 506
Subscribers
+124 hours
-197 days
-5330 days
Posts Archive
6 506
#medium
Задача: 526. Beautiful Arrangement
Предположим, у вас есть n целых чисел, пронумерованных от 1 до n. Перестановка этих n целых чисел perm (нумерация с 1) считается красивой, если для каждого i (1 <= i <= n) выполняется одно из следующих условий:
perm[i] делится на i.
i делится на perm[i].
Дано целое число n, верните количество красивых перестановок, которые вы можете создать.
Пример:
Input: n = 2
Output: 2
Explanation:
The first beautiful arrangement is [1,2]:
- perm[1] = 1 is divisible by i = 1
- perm[2] = 2 is divisible by i = 2
The second beautiful arrangement is [2,1]:
- perm[1] = 2 is divisible by i = 1
- i = 2 is divisible by perm[2] = 1
👨💻 Алгоритм:
1⃣ Инициализация и подготовка массива:
Создайте массив чисел от 1 до N и инициализируйте счетчик красивых перестановок.
Создайте функцию для перестановки элементов массива.
2⃣ Рекурсивное создание перестановок и проверка условий:
Напишите рекурсивную функцию для создания всех возможных перестановок массива, начиная с текущей позиции l.
На каждом шаге перестановки проверяйте, удовлетворяет ли текущий элемент условиям делимости. Если условие выполняется, продолжайте создание перестановок рекурсивно для следующей позиции.
3⃣ Возврат результата:
В основной функции вызовите рекурсивную функцию с начальной позицией 0 и верните значение счетчика красивых перестановок.
😎 Решение:
public class Solution {
int count = 0;
public int countArrangement(int N) {
int[] nums = new int[N];
for (int i = 1; i <= N; i++)
nums[i - 1] = i;
permute(nums, 0);
return count;
}
public void permute(int[] nums, int l) {
if (l == nums.length) {
count++;
}
for (int i = l; i < nums.length; i++) {
swap(nums, i, l);
if (nums[l] % (l + 1) == 0 || (l + 1) % nums[l] == 0)
permute(nums, l + 1);
swap(nums, i, l);
}
}
public void swap(int[] nums, int x, int y) {
int temp = nums[x];
nums[x] = nums[y];
nums[y] = temp;
}
}6 506
#hard
Задача: 381. Insert Delete GetRandom O(1) - Duplicates allowed
RandomizedCollection — это структура данных, содержащая набор чисел, возможно с дубликатами (т.е. мультимножество). Она должна поддерживать вставку и удаление определенных элементов, а также предоставление случайного элемента.
Реализуйте класс RandomizedCollection:
RandomizedCollection(): Инициализирует пустой объект RandomizedCollection.
bool insert(int val): Вставляет элемент val в мультимножество, даже если элемент уже присутствует. Возвращает true, если элемента не было, и false в противном случае.
bool remove(int val): Удаляет элемент val из мультимножества, если он присутствует. Возвращает true, если элемент присутствовал, и false в противном случае. Если у val несколько вхождений в мультимножестве, удаляется только одно из них.
int getRandom(): Возвращает случайный элемент из текущего мультимножества. Вероятность возврата каждого элемента пропорциональна числу вхождений этого элемента в мультимножество.
Реализуйте функции класса так, чтобы каждая функция работала в среднем за O(1) времени.
Пример:
Input ["RandomizedCollection", "insert", "insert", "insert", "getRandom", "remove", "getRandom"] [[], [1], [1], [2], [], [1], []] Output [null, true, false, true, 2, true, 1]👨💻 Алгоритм: 1⃣Создать словарь для хранения значений и их индексов в списке, а также список для хранения всех элементов мультимножества. 2⃣Метод insert(val): Добавить значение в конец списка и обновить словарь, добавив индекс этого значения. Возвращать true, если значение отсутствовало ранее, и false в противном случае. Метод remove(val): Удалить одно вхождение значения из словаря и списка. Для удаления значения заменить его последним элементом списка и обновить словарь. Возвращать true, если значение присутствовало, и false в противном случае. 3⃣Метод getRandom(): Возвращать случайный элемент из списка, обеспечивая равновероятное распределение на основе количества вхождений каждого элемента. 😎 Решение:
import java.util.*;
public class RandomizedCollection {
private Map<Integer, Set<Integer>> dict;
private List<Integer> list;
private Random rand;
public RandomizedCollection() {
dict = new HashMap<>();
list = new ArrayList<>();
rand = new Random();
}
public boolean insert(int val) {
boolean exists = dict.containsKey(val);
if (!exists) {
dict.put(val, new HashSet<>());
}
dict.get(val).add(list.size());
list.add(val);
return !exists;
}
public boolean remove(int val) {
if (!dict.containsKey(val) || dict.get(val).isEmpty()) {
return false;
}
int index = dict.get(val).iterator().next();
dict.get(val).remove(index);
int lastElement = list.get(list.size() - 1);
list.set(index, lastElement);
dict.get(lastElement).add(index);
dict.get(lastElement).remove(list.size() - 1);
list.remove(list.size() - 1);
if (dict.get(val).isEmpty()) {
dict.remove(val);
}
return true;
}
public int getRandom() {
return list.get(rand.nextInt(list.size()));
}
}6 506
Т-Банк ищет Java-разработчиков уровня middle и senior
23 и 24 ноября можно пройти собеседование за выходные и получить оффер, если всем все понравится.
Вот что вас ждет в компании:
— Выстроенный процесс разработки и запуска проектов.
— Современный стек технологий — здесь быстро внедряют новое в работу.
— Разработка на актуальной версии Java.
— Баланс между использованием самописных и стандартных инструментов.
— Сильное комьюнити и обмен опытом на конференциях и митапах.
Узнайте больше и оставьте заявку до 20 ноября
6 506
#medium
Задача: 237. Delete Node in a Linked List
Дан односвязный список с головой head, и требуется удалить узел node в этом списке.
Вам дан узел node, который нужно удалить. У вас нет доступа к первому узлу head.
Все значения в односвязном списке уникальны, и гарантируется, что данный узел node не является последним узлом в списке.
Удалите данный узел. Обратите внимание, что под удалением узла мы не подразумеваем его удаление из памяти. Мы имеем в виду:
- Значение данного узла не должно существовать в односвязном списке.
- Количество узлов в односвязном списке должно уменьшиться на один.
- Все значения перед узлом должны оставаться в том же порядке.
- Все значения после узла должны оставаться в том же порядке.
Пример:
Input: head = [4,5,1,9], node = 5 Output: [4,1,9] Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.👨💻 Алгоритм: 1⃣Копирование данных: Скопируйте значение из следующего узла (node.next) в текущий узел (node). Таким образом, текущий узел будет иметь значение, которое было в следующем узле. 2⃣Обновление указателя: Обновите указатель next текущего узла, чтобы он ссылался на узел, следующий за узлом node.next. Это effectively удалит следующий узел из списка. 3⃣Удаление ссылки на следующий узел: Убедитесь, что следующий узел больше не ссылается на другие узлы, тем самым полностью исключая его из списка. 😎 Решение:
class Solution {
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
}6 506
#medium
Задача: 339. Nested List Weight Sum
Вам дан вложенный список целых чисел nestedList. Каждый элемент либо целое число, либо список, элементы которого также могут быть целыми числами или другими списками.
Глубина целого числа — это количество списков, в которых оно находится. Например, вложенный список [1,[2,2],[[3],2],1] имеет значения каждого целого числа, установленные в его глубину.
Верните сумму каждого целого числа в nestedList, умноженного на его глубину.
Пример:
Input: nestedList = [1,[4,[6]]] Output: 27 Explanation: One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3. 1*1 + 4*2 + 6*3 = 27.👨💻 Алгоритм: 1⃣ Инициализация и вызов рекурсивной функции: Создайте основную функцию, которая принимает вложенный список и вызывает вспомогательную рекурсивную функцию с начальной глубиной 1. 2⃣ Рекурсивное исследование списка: В вспомогательной функции пройдите по каждому элементу списка. Если элемент является целым числом, добавьте его значение, умноженное на текущую глубину, к общей сумме. Если элемент является списком, вызовите вспомогательную функцию рекурсивно с увеличенной глубиной. 3⃣ Возврат результата: Возвращайте общую сумму на каждом уровне рекурсии. Основная функция возвращает итоговую сумму. 😎 Решение:
class Solution {
public int depthSum(List<NestedInteger> nestedList) {
return dfs(nestedList, 1);
}
private int dfs(List<NestedInteger> list, int depth) {
int total = 0;
for (NestedInteger nested : list) {
if (nested.isInteger()) {
total += nested.getInteger() * depth;
} else {
total += dfs(nested.getList(), depth + 1);
}
}
return total;
}
}6 506
Начните свою карьеру Java-разработчика с Hexlet!
Хотите стать профессионалом в Java? Пройдите обучение и за 10 месяцев освоите все ключевые навыки, от основ до продвинутого уровня.
🎁 🎃 Бонусы к Черной пятнице! Вас ждет специальное предложение - скидка до 81 000 ₽. на обучение и второй курс в подарок!
Вас ждут сотни практических упражнений, реальные проекты для портфолио и поддержка опытных менторов. Освойте язык крупного бизнеса и финансовых технологий и научитесь разрабатывать веб-приложения на фреймворке Spring.
А во время обучения вы также поучаствуете в Карьерном треке!
Пройдите 5 бесплатных уроков и откройте для себя увлекательный процесс обучения. Поймите, насколько интересен и перспективен этот путь, и получите уникальную возможность продолжить обучение на полном курсе со скидкой!
6 506
#medium
Задача: 380. Insert Delete GetRandom O(1)
Реализуйте класс RandomizedSet:
RandomizedSet(): Инициализирует объект RandomizedSet.
bool insert(int val): Вставляет элемент val в множество, если его там нет. Возвращает true, если элемент отсутствовал, и false в противном случае.
bool remove(int val): Удаляет элемент val из множества, если он присутствует. Возвращает true, если элемент присутствовал, и false в противном случае.
int getRandom(): Возвращает случайный элемент из текущего множества элементов (гарантируется, что по крайней мере один элемент существует при вызове этого метода). Каждый элемент должен иметь равную вероятность быть возвращенным.
Вы должны реализовать функции класса таким образом, чтобы каждая функция работала в среднем за O(1) по времени.
Пример:
Input ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"] [[], [1], [2], [2], [], [1], [2], []] Output [null, true, false, true, 2, true, false, 2]👨💻 Алгоритм: 1⃣Создать словарь для хранения значений и их индексов, а также список для хранения значений. 2⃣Метод insert(val): Проверить наличие значения в словаре. Если отсутствует, добавить значение в список и обновить словарь с новым индексом. Метод remove(val): Проверить наличие значения в словаре. Если присутствует, заменить удаляемое значение последним элементом списка, обновить его индекс в словаре, удалить последний элемент из списка и удалить значение из словаря. 3⃣Метод getRandom(): Возвращать случайный элемент из списка, используя встроенную функцию генерации случайных чисел. 😎 Решение:
import java.util.*;
public class RandomizedSet {
private Map<Integer, Integer> dict;
private List<Integer> list;
private Random rand;
public RandomizedSet() {
dict = new HashMap<>();
list = new ArrayList<>();
rand = new Random();
}
public boolean insert(int val) {
if (dict.containsKey(val)) {
return false;
}
dict.put(val, list.size());
list.add(val);
return true;
}
public boolean remove(int val) {
if (!dict.containsKey(val)) {
return false;
}
int index = dict.get(val);
int lastElement = list.get(list.size() - 1);
list.set(index, lastElement);
dict.put(lastElement, index);
list.remove(list.size() - 1);
dict.remove(val);
return true;
}
public int getRandom() {
return list.get(rand.nextInt(list.size()));
}
}6 506
#medium
Задача: 236. Lowest Common Ancestor of a Binary Tree
Дано бинарное дерево. Найдите наименьший общий предок (LCA) двух заданных узлов в дереве.
Согласно определению LCA на Википедии: "Наименьший общий предок определяется между двумя узлами p и q как наименьший узел в дереве T, который имеет как p, так и q в качестве потомков (где мы допускаем, что узел может быть потомком самого себя)."
Пример:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3 Explanation: The LCA of nodes 5 and 1 is 3.👨💻 Алгоритм: 1⃣Начало обхода дерева с корня: Начните обход дерева с корневого узла. Если текущий узел является одним из узлов p или q, установите переменную mid в значение True и продолжите поиск другого узла в левой и правой ветвях. 2⃣Проверка поддеревьев: Выполните рекурсивный обход левой и правой ветвей дерева. Если какая-либо из ветвей (левая или правая) возвращает True, это означает, что один из двух узлов найден ниже по дереву. 3⃣Определение LCA: Если в любой момент обхода дерева две из трех переменных (left, right или mid) становятся True, это означает, что найден наименьший общий предок (LCA) для узлов p и q. 😎 Решение:
class Solution {
private TreeNode ans;
public Solution() {
this.ans = null;
}
private boolean recurseTree(TreeNode currentNode, TreeNode p, TreeNode q) {
if (currentNode == null) {
return false;
}
int left = this.recurseTree(currentNode.left, p, q) ? 1 : 0;
int right = this.recurseTree(currentNode.right, p, q) ? 1 : 0;
int mid = (currentNode == p || currentNode == q) ? 1 : 0;
if (mid + left + right >= 2) {
this.ans = currentNode;
}
return (mid + left + right > 0);
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
this.recurseTree(root, p, q);
return this.ans;
}
}6 506
#medium
Задача: 379. Design Phone Directory
Создайте телефонный справочник, который изначально имеет maxNumbers пустых слотов для хранения номеров. Справочник должен хранить номера, проверять, пуст ли определенный слот, и освобождать данный слот.
Реализуйте класс PhoneDirectory:
PhoneDirectory(int maxNumbers) Инициализирует телефонный справочник с количеством доступных слотов maxNumbers.
int get() Предоставляет номер, который никому не назначен. Возвращает -1, если номера недоступны.
bool check(int number) Возвращает true, если слот доступен, и false в противном случае.
void release(int number) Перераспределяет или освобождает номер слота.
Пример:
Input ["PhoneDirectory", "get", "get", "check", "get", "check", "release", "check"] [[3], [], [], [2], [], [2], [2], [2]] Output [null, 0, 1, true, 2, false, null, true]👨💻 Алгоритм: 1⃣Инициализировать массив isSlotAvailable размером maxNumbers, установив значение true во всех индексах. 2⃣Метод get(): Проходить по массиву isSlotAvailable. Если найдется true на каком-либо индексе, установить isSlotAvailable[i] = false и вернуть i. Если доступных слотов нет, вернуть -1. Метод check(number): Вернуть значение isSlotAvailable[number]. 3⃣Метод release(number): Установить isSlotAvailable[number] = true. 😎 Решение:
public class PhoneDirectory {
private boolean[] isSlotAvailable;
public PhoneDirectory(int maxNumbers) {
isSlotAvailable = new boolean[maxNumbers];
for (int i = 0; i < maxNumbers; i++) {
isSlotAvailable[i] = true;
}
}
public int get() {
for (int i = 0; i < isSlotAvailable.length; i++) {
if (isSlotAvailable[i]) {
isSlotAvailable[i] = false;
return i;
}
}
return -1;
}
public boolean check(int number) {
return isSlotAvailable[number];
}
public void release(int number) {
isSlotAvailable[number] = true;
}
}6 506
#medium
Задача: 235. Lowest Common Ancestor of a Binary Search Tree
Дано бинарное дерево поиска (BST). Найдите наименьший общий предок (LCA) двух заданных узлов в BST.
Согласно определению LCA на Википедии: "Наименьший общий предок определяется между двумя узлами p и q как наименьший узел в дереве T, который имеет как p, так и q в качестве потомков (где мы допускаем, что узел может быть потомком самого себя)."
Пример:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 Output: 6 Explanation: The LCA of nodes 2 and 8 is 6.👨💻 Алгоритм: 1⃣Начало обхода дерева с корня: Начните обход дерева с корневого узла. Проверьте, находятся ли узлы p и q в правом или левом поддереве текущего узла. 2⃣Продолжение поиска в поддереве: Если оба узла p и q находятся в правом поддереве текущего узла, продолжайте поиск в правом поддереве, начиная с шага 1. Если оба узла p и q находятся в левом поддереве текущего узла, продолжайте поиск в левом поддереве, начиная с шага 1. 3⃣Нахождение LCA: Если узлы p и q находятся в разных поддеревьях относительно текущего узла или один из узлов равен текущему узлу, то текущий узел является наименьшим общим предком (LCA). Верните этот узел как результат. 😎 Решение:
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
int parentVal = root.val;
int pVal = p.val;
int qVal = q.val;
if (pVal > parentVal && qVal > parentVal) {
return lowestCommonAncestor(root.right, p, q);
} else if (pVal < parentVal && qVal < parentVal) {
return lowestCommonAncestor(root.left, p, q);
} else {
return root;
}
}
}6 506
Хотите создавать приложения для миллионов пользователей, но пугают базы данных, JDBC и Hibernate?
Если вы пишете на Java, то рано или поздно столкнетесь с задачей хранения данных: профили пользователей, каталоги товаров или финансы. Можно, конечно, нагромоздить код для прямой работы с базой, но в какой-то момент обычный SQL просто перестанет справляться.
Вместо ручного написания сложного SQL-кода используйте Hibernate. Он берёт на себя всю рутину и делает работу с данными проще и удобнее.
Чтобы разобраться с принципами работы фреймворка, приходите на вебинар от FAANG School:
– зачем нужен и как применять Hibernate в своих Java-проектах
– как создавать связи между Java-объектами и таблицами в базе данных
– лучшие практики Hibernate для создания топ-приложений
– как просто работать со связями one-to-one, one-to-many и many-to-many и многое другое
Занимайте место и уже после вебинара сможете забрать пару фич к себе в проект!
6 506
#medium
Задача: 378. Kth Smallest Element in a Sorted Matrix
Дана матрица размером n x n, где каждая строка и каждый столбец отсортированы в порядке возрастания. Верните k-й наименьший элемент в матрице.
Заметьте, что это k-й наименьший элемент в отсортированном порядке, а не k-й уникальный элемент.
Вы должны найти решение с использованием памяти лучше, чем O(n²).
Пример:
Input: matrix = [[-5]], k = 1 Output: -5👨💻 Алгоритм: 1⃣Инициализировать мин-кучу H. В нашем решении мы будем рассматривать каждую строку как отдельный список. Поскольку столбцы также отсортированы, мы можем рассматривать каждый столбец как отдельный список. 2⃣Взять первые элементы из min(N, K) строк, где N представляет количество строк, и добавить каждый из этих элементов в кучу. Важно знать, к какой строке и столбцу принадлежит элемент, чтобы в дальнейшем перемещаться по соответствующему списку. 3⃣Мин-куча будет содержать тройки информации (значение, строка, столбец). Куча будет упорядочена по значениям, и мы будем использовать номера строк и столбцов для добавления следующего элемента, если текущий элемент будет удален из кучи. 😎 Решение:
import java.util.Comparator;
import java.util.PriorityQueue;
class MyHeapNode {
int row;
int column;
int value;
public MyHeapNode(int v, int r, int c) {
this.value = v;
this.row = r;
this.column = c;
}
public int getValue() {
return this.value;
}
public int getRow() {
return this.row;
}
public int getColumn() {
return this.column;
}
}
class MyHeapComparator implements Comparator<MyHeapNode> {
public int compare(MyHeapNode x, MyHeapNode y) {
return x.value - y.value;
}
}
class Solution {
public int kthSmallest(int[][] matrix, int k) {
int N = matrix.length;
PriorityQueue<MyHeapNode> minHeap = new PriorityQueue<>(Math.min(N, k), new MyHeapComparator());
for (int r = 0; r < Math.min(N, k); r++) {
minHeap.offer(new MyHeapNode(matrix[r][0], r, 0));
}
MyHeapNode element = minHeap.peek();
while (k-- > 0) {
element = minHeap.poll();
int r = element.getRow(), c = element.getColumn();
if (c < N - 1) {
minHeap.offer(new MyHeapNode(matrix[r][c + 1], r, c + 1));
}
}
return element.getValue();
}
}6 506
#medium
Задача: 378. Kth Smallest Element in a Sorted Matrix
Дана матрица размером n x n, где каждая строка и каждый столбец отсортированы в порядке возрастания. Верните k-й наименьший элемент в матрице.
Заметьте, что это k-й наименьший элемент в отсортированном порядке, а не k-й уникальный элемент.
Вы должны найти решение с использованием памяти лучше, чем O(n²).
Пример:
Input: matrix = [[-5]], k = 1 Output: -5👨💻 Алгоритм: 1⃣Инициализировать мин-кучу H. В нашем решении мы будем рассматривать каждую строку как отдельный список. Поскольку столбцы также отсортированы, мы можем рассматривать каждый столбец как отдельный список. 2⃣Взять первые элементы из min(N, K) строк, где N представляет количество строк, и добавить каждый из этих элементов в кучу. Важно знать, к какой строке и столбцу принадлежит элемент, чтобы в дальнейшем перемещаться по соответствующему списку. 3⃣Мин-куча будет содержать тройки информации (значение, строка, столбец). Куча будет упорядочена по значениям, и мы будем использовать номера строк и столбцов для добавления следующего элемента, если текущий элемент будет удален из кучи. 😎 Решение:
class MyHeapNode {
int row;
int column;
int value;
public MyHeapNode(int v, int r, int c) {
this.value = v;
this.row = r;
this.column = c;
}
public int getValue() {
return this.value;
}
public int getRow() {
return this.row;
}
public int getColumn() {
return this.column;
}
}
class MyHeapComparator implements Comparator<MyHeapNode> {
public int compare(MyHeapNode x, MyHeapNode y) {
return x.value - y.value;
}
}
class Solution {
public int kthSmallest(int[][] matrix, int k) {
int N = matrix.length;
PriorityQueue<MyHeapNode> minHeap =
new PriorityQueue<MyHeapNode>(Math.min(N, k), new MyHeapComparator());
// Preparing our min-heap
for (int r = 0; r < Math.min(N, k); r++) {
// We add triplets of information for each cell
minHeap.offer(new MyHeapNode(matrix[r][0], r, 0));
}
MyHeapNode element = minHeap.peek();
while (k-- > 0) {
// Extract-Min
element = minHeap.poll();
int r = element.getRow(), c = element.getColumn();
// If we have any new elements in the current row, add them
if (c < N - 1) {
minHeap.offer(new MyHeapNode(matrix[r][c + 1], r, c + 1));
}
}
return element.getValue();
}
}6 506
Repost from Идущий к IT
Твое резюме на HeadHunter — ОК, если ты видишь это.
HeadHunter сравнивает ключевые навыки в твоем резюме и в вакансии и в момент отклика отображает, насколько % ты соответствуешь требованиям.
Специальный бейджик «Подходит по навыкам на 100%» отображается, если соответствие составляет более 60%.
Если при просмотре вакансий ты видишь такой бейджик, это значит, что список навыков в твоем резюме качественно составлен.
Это важный параметр, так как рекрутерам чаще показываются резюме с лучшим соответствием.
О том, как правильно указывать ключевые навыки и оптимизировать свое резюме я уже рассказывал в этом видео
6 506
Станьте Java-разработчиком с нуля без оплаты за обучение и получите работу с зарплатой 140 000+
Образовательный проект EdMe начинает набор на курс Java-разработки для начинающих. Программа основана на менторстве и подходит для начинающих программистов и тех, кто хочет освоить Java с нуля. От вас нужно лишь желание учиться и готовность уделять от 15 часов в неделю на занятия.
🔹 Получение профессии: 6 месяцев до зарплаты от 140.000 руб.
🔹 Гарантия трудоустройства: 98,9% выпускников получают оффер за 34 дня.
🔹 Оплата после трудоустройства: 20% от зарплаты в течение 18 месяцев.
🔹 После обучения 86% выпускников выбирают работу онлайн.
Обучение проходит онлайн: 40% самостоятельная работа, 30% — взаимодействие с ментором, 30% — в группе. Такой подход развивает быстрее обычных курсов, ментор проведёт вас по короткому пути. Он объяснит, что нужно учить и как это делать, а также чего не делать, чтобы быстрее освоить нужные навыки и достичь заветной цели – получить оффер в IT.
Программа курса:
▫️ Java Core, List, JDBC, Hibernate, Spring (Core, MVC, Security), Spring Boot, Git
▫️ Работа над проектами
▫️ Подготовка к собеседованиям
🗓 Старт обучения: ноябрь 2024.
Чтобы начать учиться нужно оставить заявку на сайте EdMe. Отбор включает несложное тестовое задание, которое под силу выполнить человеку без опыта, и собеседование.
6 506
#hard
Задача: 472. Concatenated Words
Дан массив строк words (без дубликатов). Верните все составные слова из данного списка слов.
Составное слово определяется как строка, которая полностью состоит как минимум из двух более коротких слов (не обязательно различных) из данного массива.
Пример:
Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"] Output: ["catsdogcats","dogcatsdog","ratcatdogcat"] Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats"; "dogcatsdog" can be concatenated by "dog", "cats" and "dog"; "ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".👨💻 Алгоритм: 1⃣Для каждого слова в списке: Построить неявный граф, в котором узлы представляют индексы символов в слове, а ребра представляют возможность перехода от одного индекса к другому, если подстрока между ними является словом из списка. 2⃣Использовать поиск в глубину (DFS) для проверки, можно ли достигнуть узел с индексом word.length от узла с индексом 0 в графе. 3⃣Если узел word.length достижим от узла 0, добавить слово в ответ. 😎 Решение:
import java.util.*;
public class Solution {
private boolean dfs(String word, int length, boolean[] visited, Set<String> dictionary) {
if (length == word.length()) {
return true;
}
if (visited[length]) {
return false;
}
visited[length] = true;
for (int i = word.length() - (length == 0 ? 1 : 0); i > length; --i) {
if (dictionary.contains(word.substring(length, i)) && dfs(word, i, visited, dictionary)) {
return true;
}
}
return false;
}
public List<String> findAllConcatenatedWordsInADict(String[] words) {
Set<String> dictionary = new HashSet<>(Arrays.asList(words));
List<String> answer = new ArrayList<>();
for (String word : words) {
boolean[] visited = new boolean[word.length()];
if (dfs(word, 0, visited, dictionary)) {
answer.add(word);
}
}
return answer;
}
}6 506
#medium
Задача: 470. Implement Rand10() Using Rand7()
Дано API rand7(), которое генерирует случайное целое число в диапазоне [1, 7]. Напишите функцию rand10(), которая генерирует случайное целое число в диапазоне [1, 10]. Вы можете вызывать только API rand7(), и не должны вызывать другие API. Пожалуйста, не используйте встроенные в язык функции для генерации случайных чисел.
Каждый тестовый случай будет содержать один внутренний аргумент n, который указывает количество вызовов вашей реализованной функции rand10() во время тестирования. Обратите внимание, что это не аргумент, передаваемый в rand10().
Пример:
Input: n = 1 Output: [2]😎 Решение:
class Solution {
public int rand10() {
int row, col, idx;
do {
row = rand7();
col = rand7();
idx = col + (row - 1) * 7;
} while (idx > 40);
return 1 + (idx - 1) % 10;
}
}6 506
#easy
Задача: 338. Counting Bits
Дано целое число n, верните массив ans длиной n + 1, такой что для каждого i (0 <= i <= n), ans[i] будет равняться количеству единиц в двоичном представлении числа i.
Пример:
Input: n = 5 Output: [0,1,1,2,1,2] Explanation: 0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101👨💻 Алгоритм: 1⃣ Инициализация массива: Создайте массив ans длиной n + 1, заполненный нулями. Этот массив будет содержать количество единиц в двоичном представлении каждого числа от 0 до n. 2⃣ Итерация и вычисление: Пройдите в цикле по всем числам от 1 до n. Для каждого числа x используйте битовую операцию x & (x - 1), чтобы убрать последнюю установленную биту, и добавьте 1 к значению ans для этого результата. Это количество единиц в двоичном представлении числа x. 3⃣ Возврат результата: Верните заполненный массив ans, который содержит количество единиц для каждого числа от 0 до n. 😎 Решение:
public class Solution {
public int[] countBits(int num) {
int[] ans = new int[num + 1];
for (int x = 1; x <= num; ++x) {
ans[x] = ans[x & (x - 1)] + 1;
}
return ans;
}
}6 506
#medium
Задача: 468. Validate IP Address
Допустимый IPv4-адрес — это IP в форме "x1.x2.x3.x4", где 0 <= xi <= 255 и xi не может содержать ведущие нули. Например, "192.168.1.1" и "192.168.1.0" являются допустимыми IPv4-адресами, тогда как "192.168.01.1", "192.168.1.00" и "192.168@1.1" являются недопустимыми IPv4-адресами.
Допустимый IPv6-адрес — это IP в форме "x1:x2:x3:x4:x5:x6:x7
", где:
1 <= xi.length <= 4
xi — это шестнадцатеричная строка, которая может содержать цифры, строчные английские буквы ('a' до 'f') и прописные английские буквы ('A' до 'F').
Ведущие нули в xi допускаются.
Пример:
Input: queryIP = "172.16.254.1"
Output: "IPv4"
Explanation: This is a valid IPv4 address, return "IPv4".class Solution {
public String validateIPv4(String IP) {
String[] nums = IP.split("\\.", -1);
for (String x : nums) {
if (x.length() == 0 || x.length() > 3) return "Neither";
if (x.charAt(0) == '0' && x.length() != 1) return "Neither";
for (char ch : x.toCharArray()) {
if (!Character.isDigit(ch)) return "Neither";
}
if (Integer.parseInt(x) > 255) return "Neither";
}
return "IPv4";
}
public String validateIPv6(String IP) {
String[] nums = IP.split(":", -1);
String hexdigits = "0123456789abcdefABCDEF";
for (String x : nums) {
if (x.length() == 0 || x.length() > 4) return "Neither";
for (char ch : x.toCharArray()) {
if (hexdigits.indexOf(ch) == -1) return "Neither";
}
}
return "IPv6";
}
public String validIPAddress(String IP) {
if (IP.chars().filter(ch -> ch == '.').count() == 3) {
return validateIPv4(IP);
} else if (IP.chars().filter(ch -> ch == ':').count() == 7) {
return validateIPv6(IP);
} else {
return "Neither";
}
}
}6 506
Бесплатное IT-образование в 2024
Отобрали для вас полезные телеграм-каналы, которые помогут освоить программирование и другие IT-направления
Выбирайте нужное и подписывайтесь:
👩💻 Python: @PythonPortal
📱 GitHub: @git_developer
👩💻 Frontend: @FrontendPortal
🤓 Книги айти: @portalToIT
👩💻 Java: @Java_Iibrary
👩💻 C#: @KodBlog
👩💻 С/С++: @Cpportal
⚙️ Backend: @BackendPortal
🐞 Тестирование: @QAPortal
👩💻 DevOps: @loose_code
🖥 Базы Данных & SQL: @SQL
👩💻 Golang: @juniorGolang
👩💻 PHP: @PHPortal
👩💻 Моб. разработка: @MobDev
👩💻 Разработка игр: @GameDevgx
🖥 Data Science: @DataSciencegx
🤔 Хакинг & ИБ: @cybersecinform
📱 Маркетинг: @MarketingPortal
🖥 Дизайн: @PortalToDesign
➡️ Сохраняйте себе, чтобы не потерять
