Java | LeetCode

#easy Задача: 70. Climbing Stairs Ты поднимаешься по лестнице. Чтобы добраться до вершины, нужно преодолеть n ступенек. Каждый раз ты можешь подняться на 1 или 2 ступеньки. Сколькими различными способами ты можешь добраться до вершины? Пример:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

👨‍💻 Алгоритм: 1️⃣В этом методе грубой силы мы рассматриваем все возможные комбинации шагов, то есть 1 и 2, на каждом шаге. 2️⃣На каждом шаге мы вызываем функцию climbStairs для шага 1 и шага 2, и возвращаем сумму возвращаемых значений обеих функций. 3️⃣Формула вызова функции: climbStairs(i, n) = climbStairs(i+1, n) + climbStairs(i+2, n), где i определяет текущий шаг, а n — целевой шаг. 😎 Решение:

public class Solution {
    public int climbStairs(int n) {
        return climb_Stairs(0, n);
    }

    public int climb_Stairs(int i, int n) {
        if (i > n) {
            return 0;
        }
        if (i == n) {
            return 1;
        }
        return climb_Stairs(i + 1, n) + climb_Stairs(i + 2, n);
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Почему тебя не зовут на интервью? Исправь это в своем резюме… Получить приглашение на интервью сейчас сложнее, чем с нуля обучиться разработке. И к сожалению, это не шутка. Скорее всего только 1-2% работодателей сейчас позовут тебя на интервью. Это статистика, которую мы собирали по 10.000 откликам. Но над этой цифрой можно и нужно работать. Если правильно оформить свое резюме, и поменять свою стратегию с откликами, то конверсию можно увеличить до 10%. Т.е почти в 10 раз! Как это сделать? 1. Проверить свое резюме по нашему чек листу, и внести в него то, чего будет не хватать. 2. Поменять свой подход к поиску работы, ведь одними откликами на hh.ru сыт не будешь. 16 июля, в 18:00 по москве, мы вместе с Максом из CodeReview проведем вебинар на тему эффективного поиска работы в 2024 году. На нем Макс покажет как сейчас нужно искать работу. В прямом эфире. А также раскроет что именно нужно писать в свое резюме, чтобы оно ПРОДАВАЛО. Получить чек лист по составлению резюме, а также зарегистрироваться на вебинар можно по этой ссылке. Регистрируйся сейчас и увидимся 16 июля, в 18:00 по мск. 👉 Зарегистрироваться и получить чек-лист по резюме.

#easy Задача: 69. Sqrt(x) Дано неотрицательное целое число x. Верните квадратный корень из x, округлённый вниз до ближайшего целого числа. Возвращаемое целое число также должно быть неотрицательным. Вы не должны использовать встроенные функции или операторы для возведения в степень. Например, не следует использовать pow(x, 0.5) в C++ или x ** 0.5 в Python. Пример:

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.

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

class Solution {
    public int mySqrt(int x) {
        if (x < 2) return x;

        long num;
        int pivot, left = 2, right = x / 2;
        while (left <= right) {
            pivot = left + (right - left) / 2;
            num = (long) pivot * pivot;
            if (num > x) right = pivot - 1;
            else if (num < x) left = pivot + 1;
            else return pivot;
        }

        return right;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

👩‍💻 Программирование теперь в телеграм! Вот обширная база материалов, которая ежедневно обновляется, выбирай своё направление: Обучение Java с нуля Обучение Python с нуля Обучение JavaScript с нуля Обучение HTML/CSS с нуля Обучение C/С++ с нуля Обучение С# с нуля Обучение SQL/GO/PHP с нуля Обучение Kotlin/Swift с нуля ⛓ Архив на 1789ГБ: Курсы, книги, шпаргалки, статьи, видео ресурсы — всё собрано в одном месте: @roadmap_ready

#hard Задача: 68. Text Justification Дан массив строк words и ширина maxWidth. Необходимо отформатировать текст таким образом, чтобы каждая строка содержала ровно maxWidth символов и была полностью (слева и справа) выровнена. Слова следует упаковывать жадным способом; то есть стараться поместить как можно больше слов в каждую строку. Дополнительные пробелы ' ' следует добавлять по мере необходимости, чтобы каждая строка имела ровно maxWidth символов. Дополнительные пробелы между словами должны распределяться как можно более равномерно. Если количество пробелов в строке не делится поровну между словами, то пустые места слева будут содержать больше пробелов, чем места справа. Для последней строки текста выравнивание должно быть по левому краю, и между словами не добавляются дополнительные пробелы. Примечание: Слово определяется как последовательность символов, не содержащих пробелы. Длина каждого слова гарантированно больше 0 и не превышает maxWidth. Входной массив words содержит хотя бы одно слово. Пример:

Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
Output:
[
   "This    is    an",
   "example  of text",
   "justification.  "
]

👨‍💻 Алгоритм: 1️⃣Создайте два вспомогательных метода getWords и createLine, описанные выше. 2️⃣Инициализируйте список ответов ans и целочисленную переменную i для итерации по входным данным. Используйте цикл while для перебора входных данных. Каждая итерация в цикле while будет обрабатывать одну строку в ответе. 3️⃣Пока i < words.length, выполните следующие шаги: Получите слова, которые должны быть в текущей строке, как currentLine = getWords(i). Увеличьте i на currentLine.length. Создайте строку, вызвав createLine(line, i), и добавьте её в ans. Верните ans. 😎 Решение:

class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> ans = new ArrayList<>();
        int i = 0;

        while (i < words.length) {
            List<String> currentLine = getWords(i, words, maxWidth);
            i += currentLine.size();
            ans.add(createLine(currentLine, i, words, maxWidth));
        }

        return ans;
    }

    private List<String> getWords(int i, String[] words, int maxWidth) {
        List<String> currentLine = new ArrayList<>();
        int currLength = 0;

        while (i < words.length && currLength + words[i].length() <= maxWidth) {
            currentLine.add(words[i]);
            currLength += words[i].length() + 1;
            i++;
        }

        return currentLine;
    }

    private String createLine(
        List<String> line,
        int i,
        String[] words,
        int maxWidth
    ) {
        int baseLength = -1;
        for (String word : line) {
            baseLength += word.length() + 1;
        }

        int extraSpaces = maxWidth - baseLength;

        if (line.size() == 1 || i == words.length) {
            return String.join(" ", line) + " ".repeat(extraSpaces);
        }

        int wordCount = line.size() - 1;
        int spacesPerWord = extraSpaces / wordCount;
        int needsExtraSpace = extraSpaces % wordCount;

        for (int j = 0; j < needsExtraSpace; j++) {
            line.set(j, line.get(j) + " ");
        }

        for (int j = 0; j < wordCount; j++) {
            line.set(j, line.get(j) + " ".repeat(spacesPerWord));
        }

        return String.join(" ", line);
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Привет! Ты сейчас ищешь работу? Если да, то у меня для тебя классные новости. Мы с Максом решили провести вебинар на тему поиска работы и того, как быстрее получить оффер. Зачем? Да потому что найти работу просто откликаясь на вакансии теперь практически нереально. На Junior вакансии откликаются по 1500 кандидатов. 1500 человек, Карл... Вопрос: Как искать работу в таких условиях? Ответ: Нужно менять подходы, и использовать новые способы поиска работы. А вот какие способы, и как искать работу в 2024 году, расскажет мой товарищ - Макс, который помогает разработчикам с трудоустройством. Он расскажет тебе как ПРАВИЛЬНО откликаться на вакансии, на что смотрят рекрутеры, и как ты должен быть упакован, чтобы получить работу в это непростое время. 🗓 Когда? Во вторник – 16 июля, в 18:00 по мск. 🎁 После регистрации он также обещал прислать: 1) Анализ рынка труда. 2) Разбор кейсов тех, кто сейчас находит работу. 3) Пошаговый план, что нужно делать, чтобы прийти к оферу. 👉 Записаться на вебинар по поиску работы.

#easy Задача: 67. Add Binary Даны две двоичные строки a и b. Верните их сумму в виде двоичной строки. Пример:

Input: a = "11", b = "1"
Output: "100"

👨‍💻 Алгоритм: 1️⃣Начните с переноса carry = 0. Если в числе a наименьший бит равен 1, добавьте 1 к carry. То же самое относится к числу b: если в числе b наименьший бит равен 1, добавьте 1 к carry. В этот момент carry для наименьшего бита может быть равен 0 (00), 1 (01) или 2 (10). 2️⃣Теперь добавьте наименьший бит carry к ответу и перенесите старший бит carry на следующий порядковый бит. 3️⃣Повторяйте те же шаги снова и снова, пока не будут использованы все биты в a и b. Если остаётся ненулевой carry, добавьте его. Теперь переверните строку ответа, и задача выполнена. 😎 Решение:

class Solution {
    public String addBinary(String a, String b) {
        int n = a.length(), m = b.length();
        if (n < m) return addBinary(b, a);

        StringBuilder sb = new StringBuilder();
        int carry = 0, j = m - 1;
        for (int i = n - 1; i > -1; --i) {
            if (a.charAt(i) == '1') ++carry;
            if (j > -1 && b.charAt(j--) == '1') ++carry;

            if (carry % 2 == 1) sb.append('1');
            else sb.append('0');

            carry /= 2;
        }
        if (carry == 1) sb.append('1');
        sb.reverse();

        return sb.toString();
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#easy Задача: 66. Plus One Вам дано большое число, представленное в виде массива целых чисел digits, где каждый элемент digits[i] — это i-я цифра числа. Цифры расположены в порядке от старшей к младшей слева направо. Большое число не содержит ведущих нулей. Увеличьте большое число на один и верните результирующий массив цифр. Пример:

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1,2,4].

👨‍💻 Алгоритм: 1️⃣Проходим по входному массиву, начиная с конца массива. 2️⃣Устанавливаем все девятки на конце массива в ноль. Если мы встречаем цифру, не равную девяти, увеличиваем её на один. Работа выполнена — возвращаем массив цифр. 3️⃣Мы здесь, потому что все цифры были равны девяти. Теперь они все установлены в ноль. Затем мы добавляем цифру 1 в начало остальных цифр и возвращаем результат. 😎 Решение:

class Solution {
    public int[] plusOne(int[] digits) {
        int n = digits.length;

        for (int idx = n - 1; idx >= 0; --idx) {
            if (digits[idx] == 9) {
                digits[idx] = 0;
            } else {
                digits[idx]++;
                return digits;
            }
        }

        digits = new int[n + 1];
        digits[0] = 1;
        return digits;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Как джуну без опыта составить себе крутое резюме? Просто скачай наш гайд с 5 примерами реальных резюмешек ребят, которые недавно нашли работу. В этом гайде рассказали как: 1. Оформить свой опыт, даже если его нет. 2. Добавили 5 крутых примеров настоящих резюме junior разработчиков без опыта, которые нашли работу. А писала этот гайд команда, которая трудоустроила уже больше 150 джунов! Меняем его на подписку на канал 😊 👉 Скачать можно бесплатно по этой ссылочке.

#hard Задача: 65. Valid Number Учитывая строку s, определите, является ли s валидным числом. Например, все следующие строки являются действительными числами: "2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789". В то время как следующие строки не являются валидными числами: "abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53". Формально, валидное число определяется с использованием одного из следующих определений: Целое число с необязательным показателем степени. Десятичное число с необязательным показателем степени. Целое число определяется необязательным знаком '-' или '+' за которым следуют цифры. Десятичное число определяется необязательным знаком '-' или '+' и одним из следующих определений: Цифры, за которыми следует точка '.'. Цифры, за которыми следует точка '.', за которой следуют цифры. Точка '.', за которой следуют цифры. Показатель степени определяется с помощью обозначения показателя степени 'e' или 'E', за которым следует целое число. Цифры определяются как одна или более цифр. Пример:

Input: s = "0"

Output: true

👨‍💻 Алгоритм: 1️⃣Объявите три переменные: seenDigit, seenExponent и seenDot, установив их все в false. Перебирайте символы входной строки. Если символ является цифрой, установите seenDigit в true. 2️⃣Если символ является знаком (+ или -), проверьте, является ли он первым символом ввода или предшествует ли он показателю степени (экспоненте). Если нет, верните false. Если символ является экспонентой (e или E), сначала проверьте, была ли уже видна экспонента или еще не было увидено ни одной цифры. Если что-то из этого верно, верните false. В противном случае установите seenExponent в true и сбросьте seenDigit, потому что после экспоненты должно следовать новое целое число. 3️⃣Если символ — точка (.), проверьте, были ли уже видны точка или экспонента. Если да, верните false. Иначе установите seenDot в true. Если символ чему-то иначе, верните false. В конце верните значение seenDigit, потому что, например, ввод вида "21e" должен быть признан недействительным, если после e не следуют цифры. 😎 Решение:

class Solution {
    public boolean isNumber(String s) {
        boolean seenDigit = false;
        boolean seenExponent = false;
        boolean seenDot = false;

        for (int i = 0; i < s.length(); i++) {
            char curr = s.charAt(i);
            if (Character.isDigit(curr)) {
                seenDigit = true;
            } else if (curr == '+' || curr == '-') {
                if (i > 0 && s.charAt(i - 1) != 'e' && s.charAt(i - 1) != 'E') {
                    return false;
                }
            } else if (curr == 'e' || curr == 'E') {
                if (seenExponent || !seenDigit) {
                    return false;
                }
                seenExponent = true;
                seenDigit = false;
            } else if (curr == '.') {
                if (seenDot || seenExponent) {
                    return false;
                }
                seenDot = true;
            } else {
                return false;
            }
        }

        return seenDigit;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#medium Задача: 64. Minimum Path Sum На сетке размером m на n, заполненной неотрицательными числами, найдите путь от верхнего левого угла до нижнего правого, который минимизирует сумму всех чисел вдоль своего пути. Примечание: Вы можете перемещаться только вниз или вправо в любой момент времени. Пример:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

👨‍💻 Алгоритм: 1️⃣Инициализация дополнительной матрицы dp такого же размера, как и исходная матрица. В этой матрице dp(i, j) представляет минимальную сумму пути от индекса (i, j) до самого правого нижнего элемента. Начинаем с инициализации самого правого нижнего элемента dp как последнего элемента заданной матрицы. 2️⃣Для каждого элемента, начиная с правого нижнего угла, мы обходим матрицу в обратном порядке и заполняем её требуемыми минимальными суммами. Важно отметить, что на каждом элементе мы можем перемещаться либо вправо, либо вниз. 3️⃣Для заполнения минимальной суммы используется уравнение: dp(i, j) = grid(i, j) + min(dp(i+1, j), dp(i, j+1)), с учётом граничных условий. 😎 Решение:

public class Solution {
    public int minPathSum(int[][] grid) {
        int[][] dp = new int[grid.length][grid[0].length];
        for (int i = grid.length - 1; i >= 0; i--) {
            for (int j = grid[0].length - 1; j >= 0; j--) {
                if (i == grid.length - 1 && j != grid[0].length - 1) dp[i][j] =
                    grid[i][j] + dp[i][j + 1];
                else if (
                    j == grid[0].length - 1 && i != grid.length - 1
                ) dp[i][j] = grid[i][j] + dp[i + 1][j];
                else if (
                    j != grid[0].length - 1 && i != grid.length - 1
                ) dp[i][j] = grid[i][j] + Math.min(dp[i + 1][j], dp[i][j + 1]);
                else dp[i][j] = grid[i][j];
            }
        }
        return dp[0][0];
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#medium Задача: 63. Unique Paths II Вам дана матрица размером m на n, содержащая целые числа. Робот находится в начальный момент в верхнем левом углу (то есть в ячейке grid[0][0]). Робот пытается добраться до нижнего правого угла (то есть в ячейку grid[m - 1][n - 1]). Робот может двигаться только вниз или вправо в любой момент времени. Препятствия и свободные пространства отмечены в матрице как 1 и 0 соответственно. Путь, который проходит робот, не может включать клетки, которые являются препятствиями. Верните количество возможных уникальных путей, по которым робот может добраться до нижнего правого угла. Тестовые примеры сгенерированы таким образом, что ответ будет не более 2 * 10^9. Пример:

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

👨‍💻 Алгоритм: 1️⃣Если первая ячейка, то есть obstacleGrid[0,0], содержит 1, это означает, что в первой ячейке есть препятствие. Следовательно, робот не сможет сделать ни одного хода, и мы должны вернуть количество возможных путей как 0. Если же obstacleGrid[0,0] изначально равно 0, мы устанавливаем его равным 1 и продолжаем. 2️⃣Итерация по первой строке. Если ячейка изначально содержит 1, это означает, что текущая ячейка имеет препятствие и не должна учитываться в каком-либо пути. Следовательно, значение этой ячейки устанавливается равным 0. В противном случае, устанавливаем его равным значению предыдущей ячейки, то есть obstacleGrid[i,j] = obstacleGrid[i,j-1]. Повторяем аналогичные действия для первого столбца. 3️⃣Далее, итерация по массиву начиная с ячейки obstacleGrid[1,1]. Если ячейка изначально не содержит препятствий, то количество способов добраться до этой ячейки будет равно сумме количества способов добраться до ячейки над ней и количества способов добраться до ячейки слева от неё, то есть obstacleGrid[i,j] = obstacleGrid[i-1,j] + obstacleGrid[i,j-1]. Если в ячейке есть препятствие, устанавливаем её значение равным 0 и продолжаем. Это делается для того, чтобы она не учитывалась в других путях. 😎 Решение:

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int R = obstacleGrid.length;
        int C = obstacleGrid[0].length;

        if (obstacleGrid[0][0] == 1) {
            return 0;
        }

        obstacleGrid[0][0] = 1;

        for (int i = 1; i < R; i++) {
            obstacleGrid[i][0] = (obstacleGrid[i][0] == 0 && obstacleGrid[i - 1][0] == 1) ? 1 : 0;
        }

        for (int i = 1; i < C; i++) {
            obstacleGrid[0][i] = (obstacleGrid[0][i] == 0 && obstacleGrid[0][i - 1] == 1) ? 1 : 0;
        }

        for (int i = 1; i < R; i++) {
            for (int j = 1; j < C; j++) {
                if (obstacleGrid[i][j] == 0) {
                    obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
                } else {
                    obstacleGrid[i][j] = 0;
                }
            }
        }

        return obstacleGrid[R - 1][C - 1];
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#medium Задача: 62. Unique Paths На сетке размером m на n находится робот. Изначально робот расположен в верхнем левом углу (то есть, в клетке grid[0][0]). Робот пытается добраться до нижнего правого угла (то есть, в клетку grid[m - 1][n - 1]). Робот может двигаться только вниз или вправо в любой момент времени. Даны два целых числа m и n, верните количество возможных уникальных путей, которые робот может пройти, чтобы достичь нижнего правого угла. Тестовые случаи сгенерированы таким образом, что ответ будет меньше или равен 2 * 10^9. Пример:

Input: m = 3, n = 7
Output: 28

👨‍💻 Алгоритм: 1️⃣Инициализировать двумерный массив d[m][n] = количество путей. Сначала установить количество путей равным 1 для первой строки и первого столбца. Для упрощения можно инициализировать весь двумерный массив единицами. 2️⃣Проитерировать по всем "внутренним" ячейкам: d[col][row] = d[col - 1][row] + d[col][row - 1]. 3️⃣Вернуть d[m - 1][n - 1]. 😎 Решение:

class Solution {
    public int uniquePaths(int m, int n) {
        if (m == 1 || n == 1) {
            return 1;
        }
        return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
    }
}

🪙 1715 вопроса вопроса на Java разработчика 🔒 База собесов | 🔒 База тестовых

🔥 Погрузитесь в мир искусственного интеллекта с каналом AI Odyssey! 🔥 Оброзы и мануалы на нейросети 🔥 Новости из мира ИИ 🔥 Научные статьи простым языком Тут ты найдешь полезные нейронки, коротые запросто и с пользой можно применять в работе и в повседневной жизни Поднимайся на борт и стань частью невероятного путешествия в мир искусственного интеллекта! 🚀

#medium Задача: 61. Rotate List Дан указатель на начало связного списка, поверните список вправо на k позиций. Пример:

Input: head = [0,1,2], k = 4
Output: [2,0,1]

👨‍💻 Алгоритм: 1️⃣Найдите старый хвост и соедините его с головой (old_tail.next = head), чтобы замкнуть кольцо. Одновременно вычислите длину списка n. 2️⃣Найдите новый хвост, который находится на позиции (n - k % n - 1) от головы, и новую голову, которая находится на позиции (n - k % n). 3️⃣Разорвите кольцо (new_tail.next = None) и верните new_head. 😎 Решение:

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null) return null;
        if (head.next == null) return head;

        ListNode old_tail = head;
        int n;
        for (n = 1; old_tail.next != null; n++) old_tail = old_tail.next;
        old_tail.next = head;

        ListNode new_tail = head;
        for (int i = 0; i < n - (k % n) - 1; i++) new_tail = new_tail.next;
        ListNode new_head = new_tail.next;

        new_tail.next = null;

        return new_head;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Сливаем вам 2 архива на 500 курсов! ➤ Backend и языки программирования: - Python - REST - Java - PHP - Go - SQL - NoSQL - C# - C++ - Rust - JavaScript - Другое ➤ Frontend и Web-дизайн: - JavaScript - Figma - Web-Дизайн - HTML/CSS - Верстка - UI/UX - Другое

#hard Задача: 60. Permutation Sequence Множество [1, 2, 3, ..., n] содержит в общей сложности n! уникальных перестановок. Списком и маркировкой всех перестановок по порядку, мы получаем следующую последовательность для n = 3: "123" "132" "213" "231" "312" "321" Дано n и k, верните k-ю перестановку последовательности. Пример:

Input: n = 3, k = 3
Output: "213"

👨‍💻 Алгоритм: 1️⃣Сгенерируйте входной массив nums чисел от 1 до N. 2️⃣Вычислите все факториальные основы от 0 до (N−1)!. 3️⃣Уменьшите k на 1, чтобы значение попало в интервал (0, N!−1). Используйте коэффициенты факториалов для построения перестановки. Верните строку перестановки. 😎 Решение:

class Solution {
    public String getPermutation(int n, int k) {
        int[] factorials = new int[n];
        List<Integer> nums = new ArrayList() {{
            add(1);
        }};
        
        factorials[0] = 1;
        for (int i = 1; i < n; ++i) {
            factorials[i] = factorials[i - 1] * i;
            nums.add(i + 1);
        }

        --k;

        StringBuilder sb = new StringBuilder();
        for (int i = n - 1; i > -1; --i) {
            int idx = k / factorials[i];
            k -= idx * factorials[i];

            sb.append(nums.get(idx));
            nums.remove(idx);
        }
        return sb.toString();
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#medium Задача: 59. Spiral Matrix II Дано положительное целое число n. Сгенерируйте матрицу n на n, заполненную элементами от 1 до n^2 в спиральном порядке. Пример:

Input: n = 3
Output: [[1,2,3],[8,9,4],[7,6,5]]

👨‍💻 Алгоритм: 1️⃣Определение направлений движения: Для обхода матрицы используются четыре направления, формирующие слои. Создается массив dir, который хранит изменения координат x и y для каждого направления. Например, при движении слева направо (направление №1) координата x остается неизменной, а y увеличивается (x=0, y=1). При движении справа налево (направление №3) x остается неизменным, а y уменьшается (x=0, y=-1). 2️⃣Перемещение по матрице: Переменные row и col представляют текущие координаты x и y соответственно. Они обновляются в зависимости от направления движения. Применяется предварительно определенный массив dir с изменениями координат x и y для каждого из четырех направлений. 3️⃣Изменение направления: Направление изменяется, когда следующая строка или столбец в определенном направлении имеют ненулевое значение, что указывает на то, что они уже были пройдены. Переменная d представляет текущий индекс направления. Переход к следующему направлению в массиве dir осуществляется с использованием формулы (d+1)%4. Это позволяет вернуться к направлению 1 после завершения одного полного круга от направления 1 до направления 4. 😎 Решение:

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] result = new int[n][n];
        int cnt = 1;
        int dir[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
        int d = 0;
        int row = 0;
        int col = 0;
        while (cnt <= n * n) {
            result[row][col] = cnt++;
            int r = Math.floorMod(row + dir[d][0], n);
            int c = Math.floorMod(col + dir[d][1], n);

            if (result[r][c] != 0) d = (d + 1) % 4;

            row += dir[d][0];
            col += dir[d][1];
        }
        return result;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

– Помощь с pet-проектом – Составление roadmap – Проведение код-ревью и mock-собеседования – Помощь с трудоустройством Все это и многое другое может Ментор. Он обеспечит вам необходимый boost, ускорит и упростит вход в IT. 🔥 Здесь размещен список менторов, и многие из них предлагают бесплатную первую консультацию

#easy Задача: 58. Length of Last Word Дана строка s, состоящая из слов и пробелов. Верните длину последнего слова в строке. Слово — это максимальная подстрока, состоящая только из символов, не являющихся пробелами. Пример:

Input: s = "Hello World"
Output: 5
Explanation: The last word is "World" with length 5.

👨‍💻 Алгоритм: 1️⃣Поиск последнего слова: Сначала мы пытаемся найти последнее слово, начиная с конца строки. Итерируем строку в обратном порядке, пропуская пробелы. Когда мы встречаем первый непробельный символ, мы знаем, что нашли последний символ последнего слова. 2️⃣Определение длины последнего слова: После того как последнее слово найдено, мы подсчитываем его длину, начиная с его последнего символа. Здесь также можно использовать цикл. 3️⃣Итог: Используя обратную итерацию и пропуск пробелов, определяется начало и конец последнего слова в строке для вычисления его длины. 😎 Решение:

class Solution {
    public int lengthOfLastWord(String s) {
        int p = s.length() - 1;
        while (p >= 0 && s.charAt(p) == ' ') {
            p--;
        }

        int length = 0;
        while (p >= 0 && s.charAt(p) != ' ') {
            p--;
            length++;
        }
        return length;
    }
}

🪙 1715 вопроса вопроса на Java разработчика 🔒 База собесов | 🔒 База тестовых