Java | LeetCode
Open in Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
Show more
Network:6 507
Subscribers
+124 hours
-197 days
-5330 days
Posts Archive
6 507
#medium
Задача: 274. H-Index
Дан массив целых чисел citations, где citations[i] — количество цитирований, которое исследователь получил за свою i-ю статью. Верните h-индекс исследователя.
Согласно определению h-индекса на Википедии: h-индекс определяется как максимальное значение h, такое что данный исследователь опубликовал по крайней мере h статей, каждая из которых была процитирована как минимум h раз.
Пример:
Input: citations = [3,0,6,1,5] Output: 3 Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.👨💻 Алгоритм: 1️⃣Отсортировать массив цитирований по убыванию: Отсортировать массив citations в порядке убывания, чтобы наибольшее количество цитирований было в начале массива. 2️⃣Найти наибольшее значение i, для которого citations[i] > i: Пройтись по отсортированному массиву и найти наибольшее значение i, для которого выполняется условие citations[i] > i. Это значение будет индексом, при котором количество цитирований статьи больше индекса. 3️⃣Рассчитать h-индекс: h-индекс будет равен i + 1, где i - наибольшее значение, найденное на предыдущем шаге. 😎 Решение:
public class Solution {
public int hIndex(int[] citations) {
int n = citations.length;
int[] papers = new int[n + 1];
for (int c : citations)
papers[Math.min(n, c)]++;
int k = n;
for (int s = papers[n]; k > s; s += papers[k])
k--;
return k;
}
}6 507
#medium
Задача: 216. Combination Sum III
Найдите все допустимые комбинации k чисел, которые в сумме дают n, при условии, что:
Используются только числа от 1 до 9.
Каждое число используется не более одного раза.
Верните список всех возможных допустимых комбинаций. Список не должен содержать одинаковые комбинации, и комбинации могут возвращаться в любом порядке.
Пример:
Input: k = 3, n = 9 Output: [[1,2,6],[1,3,5],[2,3,4]] Explanation: 1 + 2 + 6 = 9 1 + 3 + 5 = 9 2 + 3 + 4 = 9 There are no other valid combinations.👨💻 Алгоритм: 1️⃣ Инициализация и запуск рекурсивной функции: Создайте вспомогательную функцию backtrack, которая принимает текущую оставшуюся сумму, размер комбинации k, текущую комбинацию, индекс следующего элемента для добавления и список результатов. Инициализируйте пустые векторы для хранения текущей комбинации и всех возможных результатов. Запустите функцию backtrack с начальными значениями: полной суммой n, размером комбинации k, пустой комбинацией, начальным индексом 0 и пустым списком результатов. 2️⃣ Рекурсивная обработка: В функции backtrack проверьте, если текущая сумма равна нулю и размер комбинации равен k, добавьте копию текущей комбинации в список результатов. Если текущая сумма меньше нуля или размер комбинации равен k, прекратите текущую ветвь обработки. Иначе, итерируйтесь по оставшимся кандидатам, начиная с текущего индекса. Для каждого кандидата добавьте его в текущую комбинацию, обновите оставшуюся сумму и вызовите backtrack с обновленными параметрами. После возвращения из рекурсивного вызова удалите последний элемент из комбинации для рассмотрения следующего кандидата. 3️⃣ Возвращение результатов: По завершении всех рекурсивных вызовов функция combinationSum3 возвращает список всех найденных комбинаций. 😎 Решение:
class Solution {
protected void backtrack(
int remain,
int k,
LinkedList<Integer> comb,
int next_start,
List<List<Integer>> results
) {
if (remain == 0 && comb.size() == k) {
results.add(new ArrayList<Integer>(comb));
return;
} else if (remain < 0 || comb.size() == k) {
return;
}
for (int i = next_start; i < 9; ++i) {
comb.add(i + 1);
this.backtrack(remain - i - 1, k, comb, i + 1, results);
comb.removeLast();
}
}
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> results = new ArrayList<List<Integer>>();
LinkedList<Integer> comb = new LinkedList<Integer>();
this.backtrack(n, k, comb, 0, results);
return results;
}
}6 507
#medium
Задача: 215. Kth Largest Element in an Array
Дан целочисленный массив nums и целое число k. Верните k-й наибольший элемент в массиве.
Обратите внимание, что это k-й наибольший элемент в отсортированном порядке, а не k-й уникальный элемент.
Пример:
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4 Output: 4👨💻 Алгоритм: 1️⃣ Отсортируйте массив в порядке убывания: Используйте стандартную функцию сортировки для сортировки элементов массива nums в порядке убывания. В этом случае самый большой элемент будет первым в массиве, второй по величине - вторым и так далее. 2️⃣ Найдите k-й по величине элемент: После сортировки просто верните элемент, который стоит на позиции k-1 (учитывая, что индексация в массиве начинается с 0). 3️⃣ Верните результат: Возвратите найденное значение как результат. 😎 Решение:
class Solution {
public String shortestPalindrome(String s) {
int n = s.length();
String rev = new StringBuilder(s).reverse().toString();
for (int i = 0; i < n; i++) {
if (s.substring(0, n - i).equals(rev.substring(i))) {
return rev.substring(0, i) + s;
}
}
return "";
}
}6 507
#hard
Задача: 273. Integer to English Words
Преобразуйте неотрицательное целое число num в его словесное представление на английском языке.
Пример:
Input: num = 123 Output: "One Hundred Twenty Three"👨💻 Алгоритм: 1️⃣Обработка чисел до 20 и кратных 10 до 90: Создать массивы или словари для чисел от 1 до 19 и для кратных 10 от 20 до 90. Если число попадает в эти диапазоны, сразу вернуть соответствующее словесное представление. 2️⃣Обработка сотен, тысяч, миллионов и миллиардов: Разделить число на группы по три цифры (единицы, тысячи, миллионы, миллиарды). Для каждой группы сформировать словесное представление с использованием рекурсивной функции для чисел от 1 до 999. 3️⃣Формирование окончательного результата: Собрать словесное представление всех групп, добавив соответствующие суффиксы (тысячи, миллионы, миллиарды). Соединить все части в одну строку, удалив лишние пробелы. 😎 Решение:
class Solution {
private final String[] belowTwenty = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
private final String[] tens = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
private final String[] thousands = {"", "Thousand", "Million", "Billion"};
public String numberToWords(int num) {
if (num == 0) return "Zero";
int i = 0;
String result = "";
while (num > 0) {
if (num % 1000 != 0) {
result = helper(num % 1000) + thousands[i] + " " + result;
}
num /= 1000;
i++;
}
return result.trim();
}
private String helper(int num) {
if (num == 0) return "";
else if (num < 20) return belowTwenty[num] + " ";
else if (num < 100) return tens[num / 10] + " " + helper(num % 10);
else return belowTwenty[num / 100] + " Hundred " + helper(num % 100);
}
}6 507
Тестовое собеседование на Middle Java-разработчика завтра
Уже завтра, 25 сентября в 19:00 по мск приходи онлайн на открытое собеседование, чтобы посмотреть на настоящее интервью на Middle Java-разработчика.
Как это будет:
1. Мария Ядерцова ведущий Java-разработчик в МТС Диджитал и ex. Сбербанк-Технологии будет задавать реальные вопросы и задачи разработчику-добровольцу
2. Мария будет комментировать каждый ответ респондента, чтобы дать понять чего от вас ожидает собеседующий на интервью
3. В конце можно будет задать любой вопрос Марии
Что узнаешь на прямом эфире от ШОРТКАТ:
· Чего ждут от кандидатов на Middle позиции в Java-разработке
· Какие вопросы задают на интервью и зачем
· Как подготовиться к собесу, чтобы получить оффер
Это бесплатно? Бесплатно
Переходи в нашего бота, чтобы получить ссылку на эфир → @shortcut_sh_bot
Реклама. ООО "ШОРТКАТ", ИНН: 9731139396, erid: 2VtzqwV17Za
6 507
#hard
Задача: 214. Shortest Palindrome
Дана строка s. Вы можете преобразовать s в палиндром, добавив символы в начало строки.
Верните самый короткий палиндром, который можно получить, выполняя это преобразование.
Пример:
Input: s = "aacecaaa" Output: "aaacecaaa"👨💻 Алгоритм: 1️⃣ Создание обратной строки: Создайте обратную строку rev от исходной строки s, чтобы использовать её для сравнения. 2️⃣ Итерация для поиска наибольшего палиндрома: Перебирайте индекс i от 0 до size(s) - 1. Для каждой итерации проверяйте, равна ли подстрока s от начала до n - i подстроке rev от i до конца строки. Если условие выполняется, это означает, что подстрока s от начала до n - i является палиндромом, так как rev является обратной строкой s. 3️⃣ Возврат результата: Как только найден наибольший палиндром, возвращайте строку, состоящую из обратной подстроки rev от начала до i + исходная строка s. 😎 Решение:
class Solution {
public String shortestPalindrome(String s) {
int n = s.length();
String rev = new StringBuilder(s).reverse().toString();
for (int i = 0; i < n; i++) {
if (s.substring(0, n - i).equals(rev.substring(i))) return (
rev.substring(0, i) + s
);
}
return "";
}
}6 507
#hard
Задача: 272. Closest Binary Search Tree Value II
Дано корень бинарного дерева поиска, целевое значение и целое число k. Верните k значений в дереве, которые ближе всего к целевому значению. Вы можете вернуть ответ в любом порядке.
Гарантируется, что в дереве есть только один уникальный набор из k значений, которые ближе всего к целевому значению.
Пример:
Input: root = [4,2,5,1,3], target = 3.714286, k = 2 Output: [4,3]👨💻 Алгоритм: 1️⃣Выполнить обход дерева в глубину (DFS) и собрать все значения в массив: Пройти по дереву в глубину, добавляя каждое значение узла в массив. 2️⃣Отсортировать массив по расстоянию от целевого значения: Использовать пользовательский компаратор, чтобы отсортировать массив по абсолютному значению разности между элементом массива и целевым значением. 3️⃣Вернуть первые k значений из отсортированного массива: Извлечь первые k элементов из отсортированного массива и вернуть их. 😎 Решение:
class Solution {
public List<Integer> closestKValues(TreeNode root, double target, int k) {
List<Integer> arr = new ArrayList<>();
dfs(root, arr);
arr.sort((o1, o2) -> Math.abs(o1 - target) <= Math.abs(o2 - target) ? -1 : 1);
return arr.subList(0, k);
}
private void dfs(TreeNode node, List<Integer> arr) {
if (node == null) {
return;
}
arr.add(node.val);
dfs(node.left, arr);
dfs(node.right, arr);
}
}6 507
#easy
Задача: 270. Closest Binary Search Tree Value
Дано корень бинарного дерева поиска и целевое значение. Верните значение в дереве, которое ближе всего к целевому. Если существует несколько ответов, выведите наименьшее.
Пример:
Input: root = [4,2,5,1,3], target = 3.714286 Output: 4👨💻 Алгоритм: 1️⃣Построить массив с помощью inorder обхода: Выполнить inorder обход дерева и собрать элементы в отсортированный массив. 2️⃣Найти ближайший элемент: Пройти по массиву и определить элемент, наиболее близкий к целевому значению. 3️⃣Выбрать наименьший из ближайших элементов: Если несколько элементов одинаково близки к целевому значению, выбрать наименьший из них. 😎 Решение:
class Solution {
public int closestValue(TreeNode root, double target) {
int closest = root.val;
while (root != null) {
if (Math.abs(root.val - target) < Math.abs(closest - target)) {
closest = root.val;
} else if (Math.abs(root.val - target) == Math.abs(closest - target)) {
closest = Math.min(root.val, closest);
}
root = target < root.val ? root.left : root.right;
}
return closest;
}
}6 507
Секрет быстрой Java-разработки
Фреймворки, а именно Spring. С ним вы сможете писать код быстрее, производительность приложений вырастет, а HR заметят ваше портфолио среди сотен других.
Ребята из FAANG School подготовили онлайн-эфир «Основы Spring для начинающих Java Junior».
На нем вы заберете архитектуру и примеры конкретных фич для собственного проекта-портфолио, а также узнаете:
– что такое Spring и почему он настолько популярен среди разработчиков
– в чем разница между Spring, Spring Boot и как их использовать
– как работают Spring Beans и как не путаться в конфигурациях
– что такое Autowiring и как автоматизировать настройку зависимостей
– как работает Dependency Injection и почему это ключ к гибким и масштабируемым приложениям
Переходите, чтобы зарегистрироваться.
Самые быстрые получат бонусы, например, мерч, другие полезные материалы, а также грант на обучение на Java Буткемп ➡️ все это здесь
6 507
#hard
Задача: 269. Alien Dictionary
Есть новый инопланетный язык, который использует английский алфавит. Однако порядок букв в нем неизвестен.
Вам дан список строк words из словаря инопланетного языка. Утверждается, что строки в words отсортированы лексикографически по правилам этого нового языка.
Если это утверждение неверно и данное расположение строк в words не может соответствовать никакому порядку букв, верните "".
В противном случае верните строку из уникальных букв нового инопланетного языка, отсортированных в лексикографическом порядке по правилам нового языка. Если существует несколько решений, верните любое из них.
Пример:
Input: words = ["wrt","wrf","er","ett","rftt"] Output: "wertf"👨💻 Алгоритм: 1️⃣Извлечение отношений порядка и создание списков смежности: Извлечь отношения порядка между буквами из слов. Вставить их в список смежности, обрабатывая случаи, когда одно слово является префиксом другого. 2️⃣Подсчет числа входящих ребер: Подсчитать количество входящих ребер (in-degree) для каждой буквы. Построить исходящий список смежности и одновременно считать входящие ребра для каждой буквы. 3️⃣Обход в ширину (BFS): Инициализировать очередь буквами с нулевым in-degree. Выполнять BFS, добавляя буквы в результат, когда их in-degree становится нулевым. Продолжать до тех пор, пока очередь не станет пустой. Проверить наличие циклов и вернуть результат. 😎 Решение:
import java.util.*;
class Solution {
public String alienOrder(String[] words) {
Map<Character, Set<Character>> adjList = new HashMap<>();
Map<Character, Integer> inDegree = new HashMap<>();
for (String word : words) {
for (char c : word.toCharArray()) {
inDegree.put(c, 0);
}
}
for (int i = 0; i < words.length - 1; i++) {
String firstWord = words[i];
String secondWord = words[i + 1];
for (int j = 0; j < Math.min(firstWord.length(), secondWord.length()); j++) {
char c = firstWord.charAt(j);
char d = secondWord.charAt(j);
if (c != d) {
if (!adjList.containsKey(c)) {
adjList.put(c, new HashSet<>());
}
if (adjList.get(c).add(d)) {
inDegree.put(d, inDegree.get(d) + 1);
}
break;
}
}
if (secondWord.length() < firstWord.length() && firstWord.startsWith(secondWord)) {
return "";
}
}
Queue<Character> queue = new LinkedList<>();
for (Map.Entry<Character, Integer> entry : inDegree.entrySet()) {
if (entry.getValue() == 0) {
queue.add(entry.getKey());
}
}
StringBuilder output = new StringBuilder();
while (!queue.isEmpty()) {
char c = queue.poll();
output.append(c);
if (adjList.containsKey(c)) {
for (char d : adjList.get(c)) {
inDegree.put(d, inDegree.get(d) - 1);
if (inDegree.get(d) == 0) {
queue.add(d);
}
}
}
}
if (output.length() < inDegree.size()) {
return "";
}
return output.toString();
}
}6 507
#easy
Задача: 268. Missing Number
Дан массив nums, содержащий n различных чисел в диапазоне [0, n]. Верните единственное число в этом диапазоне, которого нет в массиве.
Пример:
Input: nums = [3,0,1] Output: 2 Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.👨💻 Алгоритм: 1️⃣Сначала отсортируйте массив nums. 2️⃣Проверьте особые случаи: убедитесь, что число 0 находится в начале массива, а число n — в конце. 3️⃣Пройдитесь по отсортированному массиву и для каждого индекса проверьте, что число на этом индексе соответствует ожидаемому (предыдущее число плюс один). Как только вы обнаружите несоответствие, верните ожидаемое число. 😎 Решение:
class Solution {
public int missingNumber(int[] nums) {
Arrays.sort(nums);
if (nums[nums.length-1] != nums.length) {
return nums.length;
} else if (nums[0] != 0) {
return 0;
}
for (int i = 1; i < nums.length; i++) {
int expectedNum = nums[i-1] + 1;
if (nums[i] != expectedNum) {
return expectedNum;
}
}
return -1;
}
}6 507
#medium
Задача: 251. Flatten 2D Vector
Разработайте итератор для разворачивания двумерного вектора. Он должен поддерживать операции next и hasNext.
Реализуйте класс Vector2D:
Vector2D(int[][] vec) инициализирует объект двумерным вектором vec.
next() возвращает следующий элемент из двумерного вектора и перемещает указатель на один шаг вперед. Вы можете предположить, что все вызовы next допустимы.
hasNext() возвращает true, если в векторе еще остались элементы, и false в противном случае.
Пример:
Input ["Vector2D", "next", "next", "next", "hasNext", "hasNext", "next", "hasNext"] [[[[1, 2], [3], [4]]], [], [], [], [], [], [], []] Output [null, 1, 2, 3, true, true, 4, false] Explanation Vector2D vector2D = new Vector2D([[1, 2], [3], [4]]); vector2D.next(); // return 1 vector2D.next(); // return 2 vector2D.next(); // return 3 vector2D.hasNext(); // return True vector2D.hasNext(); // return True vector2D.next(); // return 4 vector2D.hasNext(); // return False👨💻 Алгоритм: 1️⃣Инициализация: Установите указатель position так, чтобы он указывал на следующий элемент массива, который должен быть возвращен методом next(). Это обеспечивает, что position всегда готов к получению следующего действительного элемента. 2️⃣Проверка доступности: Реализуйте метод hasNext(), который просто проверяет, находится ли индекс position в пределах допустимых индексов массива nums. Этот метод вернет true, если position указывает на действительный индекс, и false в противном случае. 3️⃣Получение следующего элемента: Метод next() возвращает элемент в текущей позиции position и продвигает указатель position на следующий индекс. Эта операция обеспечивает, что после вызова next(), position обновляется и указывает на следующий элемент, готовый к следующему вызову next(). 😎 Решение:
import java.util.ArrayList;
import java.util.List;
public class Vector2D {
private List<Integer> nums;
private int position;
public Vector2D(List<List<Integer>> v) {
nums = new ArrayList<>();
for (List<Integer> innerList : v) {
nums.addAll(innerList);
}
position = -1;
}
public int next() {
position++;
return nums.get(position);
}
public boolean hasNext() {
return position + 1 < nums.size();
}
}6 507
#medium
Задача: 267. Palindrome Permutation II
Дана строка s, верните все палиндромные перестановки (без дубликатов) этой строки.
Вы можете вернуть ответ в любом порядке. Если у строки s нет палиндромных перестановок, верните пустой список.
Пример:
Input: s = "aabb" Output: ["abba","baab"]👨💻 Алгоритм: 1️⃣Проверка на возможность палиндромной перестановки: Создаем хеш-таблицу, которая хранит количество вхождений каждого символа строки s. Если количество символов с нечетным количеством вхождений превышает 1, то палиндромная перестановка невозможна, и мы возвращаем пустой список. 2️⃣Генерация первой половины палиндромной строки: Создаем строку st, которая содержит все символы строки s с количеством вхождений, уменьшенным до половины от их первоначального количества. Если длина строки s нечетная, сохраняем символ, который встречается нечетное количество раз, отдельно. 3️⃣Генерация всех перестановок первой половины и создание палиндромов: Генерируем все перестановки строки st. Для каждой перестановки добавляем её обратную строку к самой себе, создавая тем самым полную палиндромную строку. Если длина строки s нечетная, добавляем сохраненный символ в середину каждого палиндрома. Чтобы избежать дубликатов, проверяем, равны ли элементы перед свапом. Если да, то пропускаем данную перестановку. 😎 Решение:
import java.util.*;
public class Solution {
private Set<String> set;
public Solution() {
set = new HashSet<>();
}
public List<String> generatePalindromes(String s) {
int[] map = new int[128];
char[] st = new char[s.length() / 2];
if (!canPermutePalindrome(s, map)) {
return new ArrayList<>();
}
char ch = '\0';
int k = 0;
for (int i = 0; i < map.length; i++) {
if (map[i] % 2 == 1) {
ch = (char) i;
}
for (int j = 0; j < map[i] / 2; j++) {
st[k++] = (char) i;
}
}
permute(st, 0, ch);
return new ArrayList<>(set);
}
private boolean canPermutePalindrome(String s, int[] map) {
int count = 0;
for (char c : s.toCharArray()) {
int index = (int) c;
map[index]++;
if (map[index] % 2 == 0) {
count--;
} else {
count++;
}
}
return count <= 1;
}
private void swap(char[]6 507
#medium
Задача: 250. Count Univalue Subtrees
Дан корень бинарного дерева, верните количество поддеревьев с одинаковыми значениями.
Поддерево с одинаковыми значениями означает, что все узлы поддерева имеют одно и то же значение.
Пример:
Input: root = [5,1,5,5,5,null,5] Output: 4👨💻 Алгоритм: 1️⃣Создайте целочисленную переменную count для подсчета количества поддеревьев с одинаковыми значениями. Инициализируйте её значением 0. 2️⃣Выполните обход в глубину (DFS) для данного бинарного дерева. Выполните dfs(root), где dfs — это рекурсивный метод, который принимает узел TreeNode в качестве параметра, от которого начинается обход. Метод возвращает логическое значение, указывающее, является ли поддерево, укоренённое в этом узле, поддеревом с одинаковыми значениями. Выполните следующие действия в этом методе: Если узел равен null, верните true. Рекурсивно проверьте, образует ли левый потомок поддерево с одинаковыми значениями. Выполните isLeftUniValue = dfs(node.left). Рекурсивно проверьте, образует ли правый потомок поддерево с одинаковыми значениями. Выполните isRightUniValue = dfs(node.right). Если оба потомка образуют поддеревья с одинаковыми значениями, т.е. isLeftUniValue && isRightUniValue равно true, сравните значения потомков узла со значением самого узла. Если левый потомок существует и node.left.val != node.val, верните false, так как значения не совпадают и мы не имеем поддерева с одинаковыми значениями. Аналогично, если правый потомок существует и node.right.val != node.val, верните false. В противном случае, увеличьте count на 1 и верните true. В противном случае, одно или оба поддерева потомков не образуют поддеревья с одинаковыми значениями, поэтому дерево, укоренённое в node, также не может быть таким поддеревом. Верните false. 3️⃣Верните count. 😎 Решение:
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
private int count = 0;
private boolean dfs(TreeNode node) {
if (node == null) {
return true;
}
boolean isLeftUniValue = dfs(node.left);
boolean isRightUniValue = dfs(node.right);
if (isLeftUniValue && isRightUniValue) {
if (node.left != null && node.left.val != node.val) {
return false;
}
if (node.right != null && node.right.val != node.val) {
return false;
}
count++;
return true;
}
return false;
}
public int countUnivalSubtrees(TreeNode root) {
dfs(root);
return count;
}
}6 507
👾 1096 вопросов собесов на Java Developer
🔒 База реальных собесов
🔒 База тестовых заданий
👾 Список менторов
👩💻 Java на каждый день
Вопросы с собеседований
Вакансии с удалёнкой
Тесты для самопроверки
Список менторов
🖥 Python на каждый день
Вакансии с удалёнкой
Решение задач LeetCode
Тесты для самопроверки
Список менторов
🖥 Frontend на каждый день
Вопросы с собеседований
Вакансии с удалёнкой
Решение задач LeetCode
Тесты для самопроверки
Список менторов
👩💻 С/С++ на каждый день
Вопросы с собеседований
Вакансии с удалёнкой
Решение задач LeetCode
Тесты для самопроверки
Список менторов
👩💻 Kotlin на каждый день
Вопросы с собеседований
Вакансии с удалёнкой
Решение задач LeetCode
Тесты для самопроверки
Список менторов
👩💻 С# на каждый день
Вопросы с собеседований
Вакансии с удалёнкой
Решение задач LeetCode
Тесты для самопроверки
Список менторов
👩💻 Swift на каждый день
Вопросы с собеседований
Вакансии с удалёнкой
Решение задач LeetCode
Тесты для самопроверки
Список менторов
👩💻 PHP на каждый день
Вопросы с собеседований
Вакансии с удалёнкой
Решение задач LeetCode
Тесты для самопроверки
Список менторов
🖥 Тестировщик на каждый день
Вопросы с собеседований
Вакансии с удалёнкой
Тесты для самопроверки
Список менторов
🖥 Data Science на каждый день
Вопросы с собеседований
Вакансии с удалёнкой
Тесты для самопроверки
Список менторов
👩💻 DevOps на каждый день
Вопросы с собеседований
Вакансии с удалёнкой
Тесты для самопроверки
Список менторов
👣 Golang на каждый день
Вопросы с собеседований
Вакансии с удалёнкой
Решение задач LeetCode
Тесты для самопроверки
Список менторов
⚙ Backend на каждый день
Вопросы с собеседований
Список менторов
6 507
#medium
Задача: 249. Group Shifted Strings
Выполните следующие операции сдвига на строке:
Правый сдвиг: замените каждую букву следующей буквой английского алфавита, где 'z' заменяется на 'a'. Например, "abc" можно сдвинуть вправо на "bcd" или "xyz" можно сдвинуть вправо на "yza".
Левый сдвиг: замените каждую букву предыдущей буквой английского алфавита, где 'a' заменяется на 'z'. Например, "bcd" можно сдвинуть влево на "abc" или "yza" можно сдвинуть влево на "xyz".
Мы можем продолжать сдвигать строку в обоих направлениях, чтобы сформировать бесконечную последовательность сдвигов.
Например, сдвиньте "abc", чтобы сформировать последовательность: ... <-> "abc" <-> "bcd" <-> ... <-> "xyz" <-> "yza" <-> .... <-> "zab" <-> "abc" <-> ...
Вам дан массив строк strings, сгруппируйте все strings[i], которые принадлежат одной и той же последовательности сдвигов. Ответ можно вернуть в любом порядке.
Пример:
Input: strings = ["abc","bcd","acef","xyz","az","ba","a","z"] Output: [["acef"],["a","z"],["abc","bcd","xyz"],["az","ba"]]👨💻 Алгоритм: 1️⃣Переберите строки, и для каждой строки найдите ее хэш-значение, сдвигая все символы так, чтобы строка начиналась с 'a'. Значение сдвига равно позиции первого символа строки, и каждый символ сдвигается на это значение с учетом модуля 26. 2️⃣Сопоставьте оригинальную строку с найденным хэш-значением в карте mapHashToList, добавляя оригинальную строку в список, соответствующий ее хэш-значению. 3️⃣Переберите mapHashToList и сохраните список для каждого ключа в карте в массив ответа groups. 😎 Решение:
class Solution {
private char shiftLetter(char letter, int shift) {
return (char) ((letter - shift + 26) % 26 + 'a');
}
private String getHash(String s) {
int shift = s.charAt(0);
StringBuilder hashKey = new StringBuilder();
for (char letter : s.toCharArray()) {
hashKey.append(shiftLetter(letter, shift));
}
return hashKey.toString();
}
public List<List<String>> groupStrings(String[] strings) {
Map<String, List<String>> mapHashToList = new HashMap<>();
for (String str : strings) {
String hashKey = getHash(str);
mapHashToList.computeIfAbsent(hashKey, k -> new ArrayList<>()).add(str);
}
return new ArrayList<>(mapHashToList.values());
}
}6 507
#medium
Задача: 247. Strobogrammatic Number II
Дано целое число n, верните все стробограмматические числа длины n. Ответ можно возвращать в любом порядке.
Стробограмматическое число — это число, которое выглядит одинаково при повороте на 180 градусов (если посмотреть вверх ногами).
Пример:
Input: n = 2 Output: ["11","69","88","96"]👨💻 Алгоритм: 1️⃣Инициализируйте структуру данных reversiblePairs, которая содержит все пары обратимых цифр. Вызовите и верните результат рекурсивной функции generateStroboNumbers(n, finalLength), где первый аргумент указывает, что текущий вызов создаст все стробограмматические числа длиной n, а второй аргумент указывает длину конечных стробограмматических чисел, которые мы будем генерировать, и будет использоваться для проверки возможности добавления '0' в начало и конец числа. 2️⃣Создайте функцию generateStroboNumbers(n, finalLength), которая вернет все стробограмматические числа длиной n: Проверьте базовые случаи: если n == 0, верните массив с пустой строкой [""]; если n == 1, верните ["0", "1", "8"]. Вызовите generateStroboNumbers(n - 2, finalLength), чтобы получить все стробограмматические числа длиной (n-2), и сохраните их в subAns. Инициализируйте пустой массив currStroboNums для хранения стробограмматических чисел длиной n. 3️⃣Для каждого числа в subAns добавьте все reversiblePairs в начало и конец, за исключением случая, когда текущая пара '00' и n == finalLength (потому что нельзя добавить '0' в начало числа), и добавьте это новое число в currStroboNums. В конце функции верните все стробограмматические числа, т.е. currStroboNums. 😎 Решение:
import java.util.*;
class Solution {
List<List<Character>> reversiblePairs = Arrays.asList(
Arrays.asList('0', '0'), Arrays.asList('1', '1'),
Arrays.asList('6', '9'), Arrays.asList('8', '8'), Arrays.asList('9', '6')
);
public List<String> generateStroboNumbers(int n, int finalLength) {
if (n == 0) {
return Arrays.asList("");
}
if (n == 1) {
return Arrays.asList("0", "1", "8");
}
List<String> prevStroboNums = generateStroboNumbers(n - 2, finalLength);
List<String> currStroboNums = new ArrayList<>();
for (String prevStroboNum : prevStroboNums) {
for (List<Character> pair : reversiblePairs) {
if (pair.get(0) != '0' || n != finalLength) {
currStroboNums.add(pair.get(0) + prevStroboNum + pair.get(1));
}
}
}
return currStroboNums;
}
public List<String> findStrobogrammatic(int n) {
return generateStroboNumbers(n, n);
}
}6 507
#easy
Задача: 266. Palindrome Permutation
Дана строка s, вернуть true, если перестановка строки может образовать палиндром, и false в противном случае.
Пример:
Input: s = "code" Output: false👨💻 Алгоритм: 1️⃣Вместо использования встроенной хеш-таблицы, используем массив в качестве хеш-таблицы. Для этого создаем массив длиной 128, где каждый индекс соответствует одному из 128 возможных ASCII-символов. 2️⃣Проходим по строке s и записываем количество вхождений каждого символа в этот массив. 3️⃣Затем определяем количество символов с нечетным числом вхождений, чтобы определить, возможна ли палиндромная перестановка строки s. 😎 Решение:
public class Solution {
public boolean canPermutePalindrome(String s) {
int[] map = new int[128];
int count = 0;
for (int i = 0; i < s.length(); i++) {
map[s.charAt(i)]++;
if (map[s.charAt(i)] % 2 == 0) {
count--;
} else {
count++;
}
}
return count <= 1;
}
}