Java | LeetCode

#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();
    }
}

Ставь 👍 и забирай 📚 Базу знаний

👩‍💻 Программирование уже в 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 📌 Ресурсы, гайды, шпаргалки, книги и задачи для каждого языка программирования.

#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 =

Ставь 👍 и забирай 📚 Базу знаний

#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;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

❗️Страх обосраться это нормально❗️

Я уже устал.. долго учу Java, но так и не начал ходить по собесам

Узнаешь себя? Наш знакомый эксперт в Java - Павел Сорокин, разобрал самые частые вопросы с которыми к нему обращаются люди на консультациях👇 1️⃣ Постоянно кажется, что я не готов. Процесс обучения длится уже больше 1.5 года, начинаю забывать основы, которые учил в начале. При обучении одна из самых больших ошибок - это распыление фокуса. Определяешь просто частые технологии и вопросы, которые задают на собесах и идешь строго по ним, не распыляясь писал об этом тут. Первые собесы - тренировочные. Можете от них вообще не ожидать никаких результатов, не надеятся - это ТРЕНИРОВКА. Страх будет всегда, его просто нужно принять и идти дальше. Страх возникает из-за неизвестности, неодобрения со стороны других. Даже если вы провалите собес, что самое плохое случится? Вас не убьют, ничего с вами не сделают, вы и также будете сидеть в своем уютном доме. Любой страх уничтожается действием. 2️⃣ Не понимаю насколько глубоко нужно изучать технологию Каждую технологию необходимо понимать ровно настолько, насколько она необходима тебе. Если работаешь с БД и нет каких-то больших нагрузок, то нет смысла углубляться устройство БД. Не нужно знать как Spring устроен под капотом для того, чтобы найти работу. Рациональный подход - просто учить минимальный достаточный набор и улучшать его по пути. 3️⃣ Конкуренция большая, на собеседования невозможно пробиться Конкуренции на самом деле не существует. Если ты обходишь своих конкурентов по резюме/софт-скиллам/хард-скиллам, то для тебя нет конкуренции, когда ты лучше всех. Единственное, что остается - обойти всех. О двух действенных способах пройти на собес рассказал в полной версии поста ‼️ В своем канале Паша дает много информации по вкату и развитию в Java, можно начать ознакомление с его каналом с этого поста с разбором базовых вопросов на собеседованиях. Также у Паши есть отличные бесплатные видео-материалы - полный гайд по Java Core и Многопоточке и реальное успешное собеседование на Junior Java. Можете забрать их в его боте.

Тестовое собеседование на Middle Java-разработчика в среду Заходи 9 октября, в среду в 19:00 по мск на открытое онлайн-собеседование от ШОРТКАТ, чтобы узнать: ● Чего ждут от кандидатов на Middle позиции в Java-разработке ● Какие вопросы задают на интервью и зачем ● Как подготовиться к собесу, чтобы получить оффер Интервью проведёт Роман Половинцев, ex. TeamLead в Сбере. Чтобы записаться на эфир, переходи в бот → @shortcut_sh_bot Реклама. ООО "ШОРТКАТ", ИНН: 9731139396, erid: 2VtzqvcFxoL

#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];
    }
}

Ставь 👍 и забирай 📚 Базу знаний

#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;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Бесплатный интенсив: Java-разработчик: старт в профессии с нуля. 📆 Когда: 15-16 октября в 19:00 по мск. За два дня интенсива в прямом эфире, под руководством опытного Java-разработчика, вы сможете: ✔️ Познакомиться с синтаксисом и основными конструкциями языка Java. ✔️ Написать свой первый проект и определить, подходит ли вам профессия разработчика. ✔️ Создать Telegram-бота с нуля. ✔️ Узнать ответы интересующие вас вопросы. ✔️ Получить доступ к закрытому профессиональному сообществу. 🎁 Подарки для участниковинтенсива: гайд «Как заговорить на сленге IT-специалистов», карта компетенций начинающего Java-разработчика и доступ в закрытое сообщество «Старт в Java» от Хекслета!

#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;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

#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;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

#medium Задача: 384. Shuffle an Array Дан целочисленный массив nums. Разработайте алгоритм для случайного перемешивания массива. Все перестановки массива должны быть равновероятны в результате перемешивания. Реализуйте класс Solution: Solution(int[] nums): Инициализирует объект целочисленным массивом nums. int[] reset(): Сбрасывает массив в его исходную конфигурацию и возвращает его. int[] shuffle(): Возвращает случайное перемешивание массива. Пример:

Input: ransomNote = "a", magazine = "b"
Output: false

👨‍💻 Алгоритм: 1⃣Алгоритм Фишера-Йейтса удивительно похож на решение грубой силы. На каждой итерации алгоритма мы генерируем случайное целое число между текущим индексом и последним индексом массива. 2⃣Затем мы меняем местами элементы на текущем индексе и выбранном индексе. Это симулирует выбор (и удаление) элемента из "шляпы", так как следующий диапазон, из которого мы выбираем случайный индекс, не будет включать последний обработанный элемент. 3⃣Один небольшой, но важный момент заключается в том, что возможно поменять элемент сам с собой - в противном случае некоторые перестановки массива были бы более вероятны, чем другие. 😎 Решение:

class Solution {
    private int[] array;
    private int[] original;

    Random rand = new Random();

    private int randRange(int min, int max) {
        return rand.nextInt(max - min) + min;
    }

    private void swapAt(int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public Solution(int[] nums) {
        array = nums;
        original = nums.clone();
    }
    
    public int[] reset() {
        array = original;
        original = original.clone();
        return original;
    }
    
    public int[] shuffle() {
        for (int i = 0; i < array.length; i++) {
            swapAt(i, randRange(i, array.length));
        }
        return array;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

#easy Задача: 383. Ransom Note Даны две строки ransomNote и magazine, верните true, если ransomNote можно составить, используя буквы из magazine, и false в противном случае. Каждая буква из magazine может быть использована в ransomNote только один раз. Пример:

Input: ransomNote = "a", magazine = "b"
Output: false

👨‍💻 Алгоритм: 1⃣Поскольку строки являются неизменяемым типом, их нельзя изменять, поэтому у них нет операций "вставки" и "удаления". 2⃣По этой причине необходимо заменять строку magazine новой строкой, в которой отсутствует символ, который мы хотели удалить. 3⃣Повторяйте этот процесс, пока не будут удалены все необходимые символы. 😎 Решение:

public boolean canConstruct(String ransomNote, String magazine) {
    for (char c : ransomNote.toCharArray()) {
        int index = magazine.indexOf(c);
        if (index == -1) {
            return false;
        }
        magazine = magazine.substring(0, index) + magazine.substring(index + 1);
    }
    return true;
}

Ставь 👍 и забирай 📚 Базу знаний

#medium Задача: 382. Linked List Random Node Дан односвязный список, вернуть значение случайного узла из списка. Каждый узел должен иметь одинаковую вероятность быть выбранным. Реализуйте класс Solution: Solution(ListNode head) Инициализирует объект с головой односвязного списка head. int getRandom() Выбирает узел случайным образом из списка и возвращает его значение. Все узлы списка должны иметь равные шансы быть выбранными. Пример:

Input
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 3, 2, 2, 3]

Explanation
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // return 1
solution.getRandom(); // return 3
solution.getRandom(); // return 2
solution.getRandom(); // return 2
solution.getRandom(); // return 3
// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.

👨‍💻 Алгоритм: 1⃣Реализуйте интерфейс init(head), который будет вызываться при создании объекта. Преобразуйте связанный список в массив для дальнейшего использования. 2⃣В интерфейсе init(head) преобразуйте переданный связанный список в массив, чтобы его можно было использовать позже. 3⃣Реализуйте функцию getRandom(), которая будет выбирать случайный элемент из массива, созданного на первом этапе. 😎 Решение:

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

class Solution {
    private List<Integer> range = new ArrayList<>();
    private Random random = new Random();

    public Solution(ListNode head) {
        while (head != null) {
            range.add(head.val);
            head = head.next;
        }
    }

    public int getRandom() {
        int pick = random.nextInt(range.size());
        return range.get(pick);
    }
}

Ставь 👍 и забирай 📚 Базу знаний

#medium Задача: 279. Perfect Squares Дано целое число n, верните наименьшее количество чисел, являющихся совершенными квадратами, сумма которых равна n. Совершенный квадрат — это целое число, являющееся квадратом целого числа; другими словами, это произведение некоторого целого числа на самого себя. Например, 1, 4, 9 и 16 являются совершенными квадратами, тогда как 3 и 11 не являются. Пример:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

👨‍💻 Алгоритм: 1⃣Инициализация: Создайте массив dp размером n + 1 и заполните его значениями Integer.MAX_VALUE, кроме dp[0], которое установите в 0. Предварительно вычислите все совершенные квадраты, которые меньше или равны n, и сохраните их в массиве square_nums. 2⃣Заполнение массива dp: Для каждого числа i от 1 до n: Для каждого совершенного квадрата s из массива square_nums: Если i меньше текущего совершенного квадрата s, прервите внутренний цикл. Обновите dp[i], чтобы он содержал минимальное количество чисел, сумма которых равна i. 3⃣Возврат результата: Верните значение dp[n], которое будет содержать наименьшее количество совершенных квадратов, сумма которых равна n. 😎 Решение:

class Solution {

  public int numSquares(int n) {
    int dp[] = new int[n + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;

    int max_square_index = (int) Math.sqrt(n) + 1;
    int square_nums[] = new int[max_square_index];
    for (int i = 1; i < max_square_index; ++i) {
      square_nums[i] = i * i;
    }

    for (int i = 1; i <= n; ++i) {
      for (int s = 1; s < max_square_index; ++s) {
        if (i < square_nums[s])
          break;
        dp[i] = Math.min(dp[i], dp[i - square_nums[s]] + 1);
      }
    }
    return dp[n];
  }
}

Ставь 👍 и забирай 📚 Базу знаний

😒 На одном Java уже давно не вывезешь, перспектива 2024 года - Информационная Безопасность Ловите два канала на тему ИБ и хакинга ZeroDay - Уроки по кибербезопасности и хакингу с нуля. Вирусы, взломы, OSINT, криптография и свежие новости Белый Хакер - программное обеспечение, утилиты, OSINT, инструменты, полезная литература и много другое. Совершенно новый формат непохожий на другие каналы.

#easy Задача: 278. First Bad Version Вы являетесь менеджером продукта и в настоящее время возглавляете команду по разработке нового продукта. К сожалению, последняя версия вашего продукта не прошла проверку качества. Поскольку каждая версия разрабатывается на основе предыдущей версии, все версии, вышедшие после плохой версии, также оказываются плохими. Предположим, у вас есть n версий [1, 2, ..., n], и вы хотите выяснить первую плохую версию, которая вызывает все последующие версии быть плохими. Вам предоставлен API bool isBadVersion(version), который возвращает, является ли версия плохой. Реализуйте функцию для нахождения первой плохой версии. Вы должны минимизировать количество вызовов API. Пример:

Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.

👨‍💻 Алгоритм: 1⃣Инициализация границ поиска: Устанавливаем начальные значения левой и правой границ поиска: left = 1 и right = n. 2⃣Бинарный поиск: Пока левая граница меньше правой, находим среднюю точку mid и проверяем, является ли она плохой версией с помощью isBadVersion(mid). Если текущая версия mid плохая, смещаем правую границу к mid, иначе смещаем левую границу на mid + 1. 3⃣Возврат результата: Когда левая граница станет равной правой, возвращаем left как индекс первой плохой версии. 😎 Решение:

public int firstBadVersion(int n) {
    int left = 1;
    int right = n;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (isBadVersion(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

Ставь 👍 и забирай 📚 Базу знаний

#easy Задача: 226. Invert Binary Tree Дан корень бинарного дерева, инвертируйте дерево и верните его корень. Пример:

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

👨‍💻 Алгоритм: 1⃣Рекурсивная инверсия поддеревьев: Если текущий узел (root) пустой, возвращаем null. Рекурсивно инвертируем правое поддерево и сохраняем результат в переменную right. Рекурсивно инвертируем левое поддерево и сохраняем результат в переменную left. 2⃣Обмен поддеревьев: Устанавливаем левое поддерево текущего узла равным правому поддереву. Устанавливаем правое поддерево текущего узла равным левому поддереву. 3⃣Возврат корня: Возвращаем текущий узел (root) как новый корень инвертированного дерева. 😎 Решение:

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode right = invertTree(root.right);
        TreeNode left = invertTree(root.left);
        root.left = right;
        root.right = left;
        return root;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Cамый простой способ изучить Java — залезть в голову профи Один из лучших айтишников России учит базе кодинга в Telegram. Даже гуманитарий поймёт, как создавать приложения, сайты, игры и чат-боты. Достаточно подписаться на «Секреты Java», где каждый день появляются гайды, готовые примеры кода и лучших практик. И всё это бесплатно — вместо сотен тысяч рублей за курсы. Стартовать в прибыльной профессии с нуля вы сможете гораздо проще! Теперь обучиться Java может каждый: @java_secrets

#easy Задача: 367. Valid Perfect Square Дано положительное целое число num, вернуть true, если num является идеальным квадратом, или false в противном случае. Идеальный квадрат — это целое число, являющееся квадратом целого числа. Другими словами, это произведение некоторого целого числа на само себя. Вы не должны использовать какие-либо встроенные библиотечные функции, такие как sqrt. Пример:

Input: num = 16
Output: true
Explanation: We return true because 4 * 4 = 16 and 4 is an integer.

👨‍💻 Алгоритм: 1⃣Если num < 2, вернуть True. Установить левую границу в 2, а правую границу в num / 2. 2⃣Пока left <= right, взять x = (left + right) / 2, вычислить guess_squared = x * x и сравнить его с num: Если guess_squared == num, вернуть True. Если guess_squared > num, сдвинуть правую границу right = x - 1. В противном случае сдвинуть левую границу left = x + 1. 3⃣Если вышли из цикла, вернуть False. 😎 Решение:

class Solution {
    public boolean isPerfectSquare(int num) {
        if (num < 2) {
            return true;
        }

        long x = num / 2;
        while (x * x > num) {
            x = (x + num / x) / 2;
        }
        return x * x == num;
    }
}

Ставь 👍 и забирай 📚 Базу знаний