Java | LeetCode
الذهاب إلى القناة على Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
إظهار المزيد
6 373
المشتركون
لا توجد بيانات24 ساعات
-187 أيام
-7830 أيام
أرشيف المشاركات
6 373
⚡️ IT-обучение теперь в Telegram!
В cвязи с недавнем замедлением Ютуба — лучшие обучающие каналы переехали в Telegram
Вот каналы для айтишников:
👩💻 Java: @Java
👩💻 Моб. разработка: @MobDev
📱 GitHub: @GitHub
⚙️ Backend: @Backend
🤓 Общее айти: @portalToIT
👩💻 Python: @Python
👩💻 Frontend: @Frontend
👩💻 C#: @Csharp
👩💻 С/С++: @Cpp
🖥 Базы Данных & SQL: @SQL
👩💻 Golang: @Golang
👩💻 PHP: @PHP
👩💻 Разработка игр: @GameDev
👩💻 DevOps: @DevOps
🖥 Data Science: @DataScience
🤔 Хакинг & ИБ: @InfoSec
🐞 Тестирование: @QA
📱 Маркетинг: @Marketing
🖥 Дизайн: @Design
➡️ Сохраняйте себе, чтобы не потерять
6 373
#medium
Задача: 281. Zigzag Iterator
Даны два вектора целых чисел v1 и v2, реализуйте итератор, который возвращает их элементы поочередно.
Реализуйте класс ZigzagIterator:
ZigzagIterator(List<int> v1, List<int> v2) инициализирует объект с двумя векторами v1 и v2.
boolean hasNext() возвращает true, если в итераторе еще есть элементы, и false в противном случае.
int next() возвращает текущий элемент итератора и перемещает итератор к следующему элементу.
Пример:
Input: v1 = [1,2], v2 = [3,4,5,6] Output: [1,3,2,4,5,6] Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,3,2,4,5,6].👨💻 Алгоритм: 1⃣Инициализация объекта: Создайте класс ZigzagIterator с двумя списками v1 и v2. Сохраните эти списки в структуре vectors. Инициализируйте очередь queue, содержащую пары индексов: индекс списка и индекс элемента в этом списке, если список не пуст. 2⃣Метод next: Удалите первую пару индексов из очереди. Извлеките элемент из соответствующего списка по указанным индексам. Если в текущем списке есть еще элементы, добавьте новую пару индексов (тот же список, следующий элемент) в конец очереди. Верните извлеченный элемент. 3⃣Метод hasNext: Проверьте, пуста ли очередь. Верните true, если в очереди есть элементы, и false в противном случае. 😎 Решение:
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import javafx.util.Pair;
public class ZigzagIterator {
private List<List<Integer>> vectors = new ArrayList<>();
private LinkedList<Pair<Integer, Integer>> queue = new LinkedList<>();
public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
this.vectors.add(v1);
this.vectors.add(v2);
int index = 0;
for (List<Integer> vec : this.vectors) {
if (vec.size() > 0)
this.queue.add(new Pair<>(index, 0));
index++;
}
}
public int next() {
Pair<Integer, Integer> pointer = this.queue.removeFirst();
Integer vecIndex = pointer.getKey();
Integer elemIndex = pointer.getValue();
Integer nextElemIndex = elemIndex + 1;
if (nextElemIndex < this.vectors.get(vecIndex).size())
this.queue.addLast(new Pair<>(vecIndex, nextElemIndex));
return this.vectors.get(vecIndex).get(elemIndex);
}
public boolean hasNext() {
return !this.queue.isEmpty();
}
}6 373
#medium
Задача: 300. Longest Increasing Subsequence
Дан массив целых чисел nums, верните длину самой длинной строго возрастающей подпоследовательности.
Пример:
Input: nums = [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.👨💻 Алгоритм: 1⃣Инициализируйте массив dp длиной nums.length, все элементы которого равны 1. dp[i] представляет длину самой длинной возрастающей подпоследовательности, которая заканчивается элементом с индексом i. 2⃣Итерируйтесь от i = 1 до i = nums.length - 1. В каждой итерации используйте второй цикл for для итерации от j = 0 до j = i - 1 (все элементы перед i). Для каждого элемента перед i, проверьте, меньше ли этот элемент, чем nums[i]. Если да, установите dp[i] = max(dp[i], dp[j] + 1). 3⃣Верните максимальное значение из dp. 😎 Решение:
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) return 0;
int[] dp = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
dp[i] = 1;
}
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
int maxLength = 0;
for (int length : dp) {
maxLength = Math.max(maxLength, length);
}
return maxLength;
}6 373
+4
Senior-разработчик создал крутейший канал про SQL
Благодаря простым картинкам даже новичок научится разрабатывать приложения с использованием баз данных.
Присоединяйтесь: @SQL
6 373
#medium
Задача: 395. Longest Substring with At Least K Repeating Characters
Дана строка s и целое число k, верните длину самой длинной подстроки строки s, такая что частота каждого символа в этой подстроке больше или равна k.
Если такой подстроки не существует, верните 0.
Пример:
Input: s = "aaabb", k = 3 Output: 3 Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.👨💻 Алгоритм: 1⃣Генерируйте подстроки из строки s, начиная с индекса start и заканчивая индексом end. Используйте массив countMap для хранения частоты каждого символа в подстроке. 2⃣Метод isValid использует countMap для проверки, что каждый символ в подстроке встречается как минимум k раз. Если условие выполняется, текущая подстрока считается допустимой. 3⃣Отслеживайте максимальную длину допустимой подстроки, обновляя её, когда найдена более длинная подстрока, удовлетворяющая условиям. В конце возвращайте длину самой длинной подстроки. 😎 Решение:
class Solution {
public int longestSubstring(String s, int k) {
if (s.length() == 0 || k > s.length()) {
return 0;
}
int[] countMap = new int[26];
int n = s.length();
int result = 0;
for (int start = 0; start < n; start++) {
Arrays.fill(countMap, 0);
for (int end = start; end < n; end++) {
countMap[s.charAt(end) - 'a']++;
if (isValid(countMap, k)) {
result = Math.max(result, end - start + 1);
}
}
}
return result;
}
private boolean isValid(int[] countMap, int k) {
int countLetters = 0, countAtLeastK = 0;
for (int count : countMap) {
if (count > 0) countLetters++;
if (count >= k) countAtLeastK++;
}
return countLetters == countAtLeastK;
}
}6 373
🔥 Ресурсы для подготовки к работе в IT! 🔥
1️⃣ База собеседований IT – это уникальная коллекция собеседований от реальных топовых компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и многие другие! 🏢 Мы собрали 150+ собеседований, чтобы ты мог подготовиться к интервью с уверенностью и успехом.
2️⃣ База тестовых заданий – твоё секретное оружие для успешного прохождения этапов отбора! 📋 Здесь ты найдёшь 121+ тестовых заданий от тех же топовых компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries. Решай реальные задачи и набирайся опыта для будущих собеседований!
🎯 Присоединяйся к базам и прокачай свои шансы на успешное трудоустройство!
6 373
#hard
Задача: 301. Remove Invalid Parentheses
Дана строка s, содержащая скобки и буквы. Удалите минимальное количество неверных скобок, чтобы сделать строку допустимой.
Верните список уникальных строк, которые являются допустимыми с минимальным количеством удалений. Вы можете вернуть ответ в любом порядке.
Пример:
Input: s = "()())()" Output: ["(())()","()()()"]👨💻 Алгоритм: 1⃣Инициализация: Инициализируйте массив, который будет хранить все допустимые выражения. Начните рекурсию с самой левой скобки в последовательности и двигайтесь вправо. Определите состояние рекурсии переменной index, представляющей текущий обрабатываемый индекс в исходном выражении. Также используйте переменные left_count и right_count для отслеживания количества добавленных левых и правых скобок соответственно. 2⃣Обработка текущего символа: Если текущий символ (S[i]) не является скобкой, добавьте его к окончательному решению для текущей рекурсии. Если текущий символ является скобкой (S[i] == '(' или S[i] == ')'), у вас есть два варианта: либо отбросить этот символ как недопустимый, либо рассмотреть эту скобку как часть окончательного выражения. 3⃣Завершение рекурсии и проверка: Когда все скобки в исходном выражении обработаны, проверьте, является ли текущее выражение допустимым, проверяя значения left_count и right_count (должны быть равны). Если выражение допустимо, проверьте количество удалений (rem_count) и сравните его с минимальным количеством удалений, необходимых для получения допустимого выражения до сих пор. Если текущее значение rem_count меньше, обновите глобальный минимум и добавьте новое выражение в массив допустимых выражений. 😎 Решение:
import java.util.HashSet;
import java.util.Set;
class Solution {
private Set<String> validExpressions = new HashSet<>();
private int minimumRemoved = Integer.MAX_VALUE;
private void reset() {
validExpressions.clear();
minimumRemoved = Integer.MAX_VALUE;
}
private void recurse(String s, int index, int leftCount, int rightCount, StringBuilder expression, int removedCount) {
if (index == s.length()) {
if (leftCount == rightCount) {
if (removedCount <= minimumRemoved) {
String possibleAnswer = expression.toString();
if (removedCount < minimumRemoved) {
validExpressions.clear();
minimumRemoved = removedCount;
}
validExpressions.add(possibleAnswer);
}
}
return;
}
char currentCharacter = s.charAt(index);
int length = expression.length();
if (currentCharacter != '(' && currentCharacter != ')') {
expression.append(currentCharacter);
recurse(s, index + 1, leftCount, rightCount, expression, removedCount);
expression.deleteCharAt(length);
} else {
recurse(s, index + 1, leftCount, rightCount, expression, removedCount + 1);
expression.append(currentCharacter);
if (currentCharacter == '(') {
recurse(s, index + 1, leftCount + 1, rightCount, expression, removedCount);
} else if (rightCount < leftCount) {
recurse(s, index + 1, leftCount, rightCount + 1, expression, removedCount);
}
expression.deleteCharAt(length);
}
}
public List<String> removeInvalidParentheses(String s) {
reset();
recurse(s, 0, 0, 0, new StringBuilder(), 0);
return new ArrayList<>(validExpressions);
}6 373
CodHub теперь в Telegram!
Бесплатные обучающие материалы, которые лучше платных — книги, ресурсы, статьи и курсы топовых вузов страны тут:
👩💻 Материалы по Python
👩💻 Материалы по Frontend
👩💻 Материалы по Java
👩💻 Материалы по С#
👩💻 Материалы по C/C++
👩💻 Материалы по Хакингу
🖥 Материалы по SQL
👩💻 Материалы по Kotlin/Swift
👩💻 Материалы по Linux
🐞 Материалы по QA
👩💻 Материалы по Go
👩💻 Материалы по PHP
Подписываетесь: @CodHub_tg
6 373
#medium
Задача: 280. Wiggle Sort
Дан целочисленный массив nums, упорядочьте его так, чтобы nums[0] <= nums[1] >= nums[2] <= nums[3]....
Вы можете считать, что входной массив всегда имеет допустимый ответ.
Пример:
Input: nums = [3,5,2,1,6,4] Output: [3,5,1,6,2,4] Explanation: [1,6,2,5,3,4] is also accepted.👨💻 Алгоритм: 1⃣Итерируйтесь по каждому элементу с индексом i в массиве nums, начиная с 0 и до nums.length - 2, так как последний элемент не имеет следующего элемента для обмена. 2⃣Проверьте, является ли i четным и nums[i] > nums[i + 1]. Если это так, поменяйте местами nums[i] и nums[i + 1]. 3⃣Проверьте, является ли i нечетным и nums[i] < nums[i + 1]. Если это так, поменяйте местами nums[i] и nums[i + 1]. 😎 Решение:
class Solution {
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public void wiggleSort(int[] nums) {
for (int i = 0; i < nums.length - 1; i++) {
if (((i % 2 == 0) && nums[i] > nums[i + 1])
|| ((i % 2 == 1) && nums[i] < nums[i + 1])) {
swap(nums, i, i + 1);
}
}
}
}6 373
#medium
Задача: 394. Decode String
Дана закодированная строка, вернуть её декодированную версию.
Правило кодирования следующее: k[закодированная_строка], где закодированная_строка внутри квадратных скобок повторяется ровно k раз. Обратите внимание, что k гарантированно является положительным целым числом.
Можно предположить, что входная строка всегда допустима; нет лишних пробелов, квадратные скобки корректно сформированы и т.д. Более того, можно предположить, что исходные данные не содержат никаких цифр, и что цифры используются только для обозначения количества повторений, k. Например, не будет таких входных данных, как 3a или 2[4].
Тестовые случаи сгенерированы так, что длина выходной строки никогда не превысит 105.
Пример:
Input: s = "3[a]2[bc]" Output: "aaabcbc"👨💻 Алгоритм: 1⃣Проходите по строке s и обрабатывайте каждый символ. Если текущий символ не является закрывающей скобкой ], поместите его в стек. 2⃣Если текущий символ является закрывающей скобкой ], начните декодировать последнюю пройденную строку. Извлекайте из стека символы, пока следующий символ не станет открывающей скобкой [, и добавляйте каждый символ (a-z) к decodedString. Затем извлеките открывающую скобку [ из стека и извлекайте символы, пока следующий символ является цифрой (0-9), чтобы собрать число k. 3⃣Декодируйте шаблон k[decodedString], помещая decodedString в стек k раз. После того как вся строка будет пройдена, извлеките результат из стека и верните его. 😎 Решение:
class Solution {
public String decodeString(String s) {
Stack<Character> stack = new Stack<>();
for (char ch : s.toCharArray()) {
if (ch == ']') {
StringBuilder decodedString = new StringBuilder();
while (stack.peek() != '[') {
decodedString.insert(0, stack.pop());
}
stack.pop();
int k = 0;
int base = 1;
while (!stack.isEmpty() && Character.isDigit(stack.peek())) {
k = k + (stack.pop() - '0') * base;
base *= 10;
}
for (int i = 0; i < k; i++) {
for (char c : decodedString.toString().toCharArray()) {
stack.push(c);
}
}
} else {
stack.push(ch);
}
}
StringBuilder result = new StringBuilder();
for (char ch : stack) {
result.append(ch);
}
return result.toString();
}
}6 373
👩💻 Программирование уже в Telegram!
Вот 10 обучающих каналов по самым востребованным направлениям в IT.
Выбирай своё направление:
👩💻 Python: @python_ready
👩💻 Java: @java_ready
👩💻 C/C++: @cpp_ready
👩💻 C#: @csharp_ready
👩💻 Backend: @backend_ready
👩💻 Frontend: @code_ready
🖥 Базы Данных & SQL: @sql_ready
👩💻 Весь IT: @roadmap_ready
📖 IT Архив: @archive_ready
🖥 Design: @time_design
📌 Ресурсы, гайды, шпаргалки, книги и задачи для каждого языка программирования.
6 373
#medium
Задача: 393. UTF-8 Validation
Дан целочисленный массив data, представляющий данные, верните, является ли это допустимой UTF-8 кодировкой (т.е. переводится в последовательность допустимых UTF-8 закодированных символов).
Символ в UTF-8 может быть от 1 до 4 байтов в длину, при этом соблюдаются следующие правила:
Для 1-байтового символа первый бит — 0, за которым следует его Unicode код.
Для n-байтового символа первые n битов — все единицы, (n + 1)-й бит — 0, за которыми следуют n - 1 байт с наиболее значимыми 2 битами, равными 10.
Это работает следующим образом:
Количество байтов | UTF-8 Октетная последовательность
| (бинарная)
--------------------+-----------------------------------------
1 | 0xxxxxxx
2 | 110xxxxx 10xxxxxx
3 | 1110xxxx 10xxxxxx 10xxxxxx
4 | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
x обозначает бит в бинарной форме байта, который может быть как 0, так и 1.
Примечание: Вход представляет собой массив целых чисел. Используются только 8 младших значимых битов каждого целого числа. Это означает, что каждое целое число представляет только 1 байт данных.
Пример:
Input: data = [197,130,1] Output: true Explanation: data represents the octet sequence: 11000101 10000010 00000001. It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.👨💻 Алгоритм: 1⃣Начните обработку целых чисел в данном массиве одно за другим. Для каждого целого числа получите его двоичное представление в виде строки. Поскольку целые числа могут быть очень большими, следует учитывать только 8 младших значимых битов данных и отбросить остальные, как указано в условии задачи. После этого шага у вас должно быть 8-битное или 1-байтовое строковое представление целого числа. Назовем эту строку bin_rep. 2⃣Далее нужно рассмотреть два сценария. Первый — мы находимся в процессе обработки некоторого UTF-8 закодированного символа. В этом случае нужно просто проверить первые два бита строки и посмотреть, равны ли они "10", т.е. наиболее значимые два бита целого числа равны 1 и 0. bin_rep[:2] == "10". Второй сценарий — мы уже обработали несколько допустимых UTF-8 символов и должны начать обработку нового UTF-8 символа. В этом случае нужно посмотреть на префикс строкового представления и посчитать количество единиц, которые мы встречаем до первой нули. Это скажет нам, каков размер следующего UTF-8 символа. 3⃣Продолжайте обрабатывать целые числа массива таким образом, пока не обработаете их все или не обнаружите недопустимый сценарий. Теперь давайте перейдем к реализации этого алгоритма. 😎 Решение:
public class Main {
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.validUtf8(new int[]{197, 130, 1})); // true
System.out.println(solution.validUtf8(new int[]{235, 140, 4})); // false
}
}
class Solution {
public boolean validUtf8(int[] data) {
int nBytes =6 373
#easy
Задача: 392. Is Subsequence
Даны две строки s и t. Верните true, если s является подпоследовательностью t, иначе верните false.
Подпоследовательность строки — это новая строка, которая формируется из исходной строки путем удаления некоторых (возможно, ни одного) символов без нарушения относительных позиций оставшихся символов. (например, "ace" является подпоследовательностью "abcde", тогда как "aec" не является).
Пример:
Input: s = "abc", t = "ahbgdc" Output: true👨💻 Алгоритм: 1⃣Назначьте два указателя: левый для исходной строки и правый для целевой строки. Эти указатели будут использоваться для итерации по строкам и сравнения их символов. 2⃣Перемещайте указатели в зависимости от совпадения символов. Если символы на текущих позициях указателей совпадают, переместите оба указателя на один шаг вперед. Если символы не совпадают, переместите только правый указатель целевой строки. 3⃣Итерация завершается, когда один из указателей выходит за пределы своей строки. Если в конце итерации все символы исходной строки были найдены в целевой строке, исходная строка является подпоследовательностью целевой строки. 😎 Решение:
class Solution {
public boolean isSubsequence(String s, String t) {
int leftBound = s.length(), rightBound = t.length();
int pLeft = 0, pRight = 0;
while (pLeft < leftBound && pRight < rightBound) {
if (s.charAt(pLeft) == t.charAt(pRight)) {
pLeft += 1;
}
pRight += 1;
}
return pLeft == leftBound;
}
}6 373
❗️Страх обосраться это нормально❗️
Я уже устал.. долго учу Java, но так и не начал ходить по собесамУзнаешь себя? Наш знакомый эксперт в Java - Павел Сорокин, разобрал самые частые вопросы с которыми к нему обращаются люди на консультациях👇 1️⃣ Постоянно кажется, что я не готов. Процесс обучения длится уже больше 1.5 года, начинаю забывать основы, которые учил в начале. При обучении одна из самых больших ошибок - это распыление фокуса. Определяешь просто частые технологии и вопросы, которые задают на собесах и идешь строго по ним, не распыляясь писал об этом тут. Первые собесы - тренировочные. Можете от них вообще не ожидать никаких результатов, не надеятся - это ТРЕНИРОВКА. Страх будет всегда, его просто нужно принять и идти дальше. Страх возникает из-за неизвестности, неодобрения со стороны других. Даже если вы провалите собес, что самое плохое случится? Вас не убьют, ничего с вами не сделают, вы и также будете сидеть в своем уютном доме. Любой страх уничтожается действием. 2️⃣ Не понимаю насколько глубоко нужно изучать технологию Каждую технологию необходимо понимать ровно настолько, насколько она необходима тебе. Если работаешь с БД и нет каких-то больших нагрузок, то нет смысла углубляться устройство БД. Не нужно знать как Spring устроен под капотом для того, чтобы найти работу. Рациональный подход - просто учить минимальный достаточный набор и улучшать его по пути. 3️⃣ Конкуренция большая, на собеседования невозможно пробиться Конкуренции на самом деле не существует. Если ты обходишь своих конкурентов по резюме/софт-скиллам/хард-скиллам, то для тебя нет конкуренции, когда ты лучше всех. Единственное, что остается - обойти всех. О двух действенных способах пройти на собес рассказал в полной версии поста ‼️ В своем канале Паша дает много информации по вкату и развитию в Java, можно начать ознакомление с его каналом с этого поста с разбором базовых вопросов на собеседованиях. Также у Паши есть отличные бесплатные видео-материалы - полный гайд по Java Core и Многопоточке и реальное успешное собеседование на Junior Java. Можете забрать их в его боте.
6 373
Тестовое собеседование на Middle Java-разработчика в среду
Заходи 9 октября, в среду в 19:00 по мск на открытое онлайн-собеседование от ШОРТКАТ, чтобы узнать:
● Чего ждут от кандидатов на Middle позиции в Java-разработке
● Какие вопросы задают на интервью и зачем
● Как подготовиться к собесу, чтобы получить оффер
Интервью проведёт Роман Половинцев, ex. TeamLead в Сбере.
Чтобы записаться на эфир, переходи в бот → @shortcut_sh_bot
Реклама. ООО "ШОРТКАТ", ИНН: 9731139396, erid: 2VtzqvcFxoL
6 373
#easy
Задача: 389. Find the Difference
Даны две строки s и t.
Строка t генерируется путем случайного перемешивания строки s с добавлением еще одной буквы в случайную позицию.
Верните букву, которая была добавлена в t.
Пример:
Input: s = "abcd", t = "abcde" Output: "e" Explanation: 'e' is the letter that was added.👨💻 Алгоритм: 1⃣Отсортируйте строки s и t. 2⃣Итерируйте по длине строк и сравнивайте их посимвольно. Это позволяет проверить, присутствует ли текущий символ строки t в строке s. 3⃣Как только встретится символ, который есть в строке t, но отсутствует в строке s, мы найдем лишний символ, который скрывала строка t все это время. 😎 Решение:
class Solution {
public char findTheDifference(String s, String t) {
char[] sortedS = s.toCharArray();
char[] sortedT = t.toCharArray();
Arrays.sort(sortedS);
Arrays.sort(sortedT);
int i = 0;
while (i < s.length()) {
if (sortedS[i] != sortedT[i]) {
return sortedT[i];
}
i += 1;
}
return sortedT[i];
}
}6 373
#hard
Задача: 369. Plus One Linked List
Дано неотрицательное целое число, представленное в виде связного списка цифр. Добавить к этому числу единицу.
Цифры хранятся таким образом, что самая значимая цифра находится в начале списка.
Пример:
Input: head = [1,2,3] Output: [1,2,4]👨💻 Алгоритм: 1⃣Инициализируйте стражевой узел как ListNode(0) и установите его как новую голову списка: sentinel.next = head. Найдите крайний правый элемент, не равный девяти. 2⃣Увеличьте найденную цифру на единицу и установите все следующие девятки в ноль. 3⃣Верните sentinel, если его значение было установлено на 1, иначе верните head (sentinel.next). 😎 Решение:
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
class Solution {
public ListNode plusOne(ListNode head) {
ListNode sentinel = new ListNode(0);
sentinel.next = head;
ListNode notNine = sentinel;
ListNode current = head;
while (current != null) {
if (current.val != 9) {
notNine = current;
}
current = current.next;
}
notNine.val += 1;
notNine = notNine.next;
while (notNine != null) {
notNine.val = 0;
notNine = notNine.next;
}
return sentinel.val == 0 ? sentinel.next : sentinel;
}
}6 373
Бесплатный интенсив: Java-разработчик: старт в профессии с нуля.
📆 Когда: 15-16 октября в 19:00 по мск.
За два дня интенсива в прямом эфире, под руководством опытного Java-разработчика, вы сможете:
✔️ Познакомиться с синтаксисом и основными конструкциями языка Java.
✔️ Написать свой первый проект и определить, подходит ли вам профессия разработчика.
✔️ Создать Telegram-бота с нуля.
✔️ Узнать ответы интересующие вас вопросы.
✔️ Получить доступ к закрытому профессиональному сообществу.
🎁 Подарки для участниковинтенсива: гайд «Как заговорить на сленге IT-специалистов», карта компетенций начинающего Java-разработчика и доступ в закрытое сообщество «Старт в Java» от Хекслета!
6 373
#easy
Задача: 387. First Unique Character in a String
Дана строка s, найдите первый неповторяющийся символ в ней и верните его индекс. Если такого символа не существует, верните -1.
Пример:
Input: s = "leetcode" Output: 0👨💻 Алгоритм: 1⃣Постройте хеш-таблицу, где ключами являются символы строки, а значениями — количество их появлений. Для этого пройдите по строке и для каждого символа увеличивайте его счетчик в хеш-таблице. 2⃣Пройдите по строке снова и проверьте для каждого символа, является ли его количество появлений в хеш-таблице равным 1. 3⃣Если найдется символ с количеством появлений, равным 1, верните его индекс. Если такой символ не найден, верните -1. 😎 Решение:
import java.util.Random;
public class Solution {
private int[] original;
private int[] array;
private Random rand = new Random();
public Solution(int[] nums) {
array = nums.clone();
original = nums.clone();
}
public int[] reset() {
array = original.clone();
return original;
}
public int[] shuffle() {
for (int i = 0; i < array.length; i++) {
int randIndex = rand.nextInt(array.length - i) + i;
int temp = array[i];
array[i] = array[randIndex];
array[randIndex] = temp;
}
return array;
}
}6 373
#medium
Задача: 368. Largest Divisible Subset
Дан набор различных положительных целых чисел nums. Вернуть наибольшее подмножество answer, такое что каждая пара (answer[i], answer[j]) элементов в этом подмножестве удовлетворяет условию:
answer[i] % answer[j] == 0, или
answer[j] % answer[i] == 0
Если существует несколько решений, вернуть любое из них.
Пример:
Input: nums = [1,2,3] Output: [1,2] Explanation: [1,3] is also accepted.👨💻 Алгоритм: 1⃣Если число 8 может быть разделено на элемент X_i, то добавив число 8 к EDS(X_i), мы получим еще одно делимое подмножество, которое заканчивается на 8, согласно нашему следствию I. И это новое подмножество является потенциальным значением для EDS(8). Например, поскольку 8 % 2 == 0, то {2,8} может быть конечным значением для EDS(8), и аналогично для подмножества {2,4,8}, полученного из EDS(4). 2⃣Если число 8 не может быть разделено на элемент X_i, то можно быть уверенным, что значение EDS(X_i) не повлияет на EDS(8), согласно определению делимого подмножества. Например, подмножество EDS(7)={7} не имеет влияния на EDS(8). 3⃣Затем мы выбираем наибольшие новые подмножества, которые мы формируем с помощью EDS(X_i). В частности, подмножество {8} является допустимым кандидатом для EDS(8). И в гипотетическом случае, когда 8 не может быть разделено ни на один из предыдущих элементов, мы бы имели EDS(8)={8}. 😎 Решение:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
int n = nums.length;
if (n == 0) return new ArrayList<>();
Arrays.sort(nums);
List<List<Integer>> EDS = new ArrayList<>();
for (int i = 0; i < n; i++) {
EDS.add(new ArrayList<>());
}
for (int i = 0; i < n; i++) {
List<Integer> maxSubset = new ArrayList<>();
for (int k = 0; k < i; k++) {
if (nums[i] % nums[k] == 0 && maxSubset.size() < EDS.get(k).size()) {
maxSubset = EDS.get(k);
}
}
EDS.get(i).addAll(maxSubset);
EDS.get(i).add(nums[i]);
}
List<Integer> ret = new ArrayList<>();
for (List<Integer> subset : EDS) {
if (ret.size() < subset.size()) {
ret = subset;
}
}
return ret;
}
}