Задача: 666. Path Sum IV
Сложность: medium

Если глубина дерева меньше 5, то это дерево можно представить в виде массива трехзначных чисел. Для каждого числа в этом массиве:

Сотни представляют глубину d этого узла, где 1 <= d <= 4.
Десятки представляют позицию p этого узла на уровне, которому он принадлежит, где 1 <= p <= 8. Позиция соответствует позиции в полном бинарном дереве.
Единицы представляют значение v этого узла, где 0 <= v <= 9.
Дан массив возрастающих трехзначных чисел nums, представляющих бинарное дерево с глубиной меньше 5. Верните сумму всех путей от корня к листьям.

Гарантируется, что данный массив представляет собой валидное связанное бинарное дерево.

Пример:

Input: nums = [113,215,221]
Output: 12
Explanation: The tree that the list represents is shown.
The path sum is (3 + 5) + (3 + 1) = 12.

👨‍💻 Алгоритм:

1⃣Создание структуры дерева:
Пройдите по массиву nums и для каждого элемента создайте узел дерева.
Сохраните узлы в словаре для удобного доступа по их позиции.

2⃣Связывание узлов:
Пройдите по массиву и свяжите узлы друг с другом, исходя из их позиции и глубины.
Найдите левого и правого ребенка для каждого узла и установите соответствующие связи.

3⃣Подсчет суммы путей:
Выполните обход дерева (например, используя DFS) и подсчитайте сумму всех путей от корня к листьям.

😎 Решение:

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int pathSum(int[] nums) {
        Map<Integer, Integer> tree = new HashMap<>();
        
        for (int num : nums) {
            int depth = num / 100;
            int pos = (num / 10) % 10;
            int val = num % 10;
            tree.put(depth * 10 + pos, val);
        }
        
        return dfs(tree, 1, 1, 0);
    }
    
    private int dfs(Map<Integer, Integer> tree, int depth, int pos, int currentSum) {
        int key = depth * 10 + pos;
        if (!tree.containsKey(key)) {
            return 0;
        }
        currentSum += tree.get(key);
        int leftChild = (depth + 1) * 10 + 2 * pos - 1;
        int rightChild = (depth + 1) * 10 + 2 * pos;
        if (!tree.containsKey(leftChild) && !tree.containsKey(rightChild)) {
            return currentSum;
        }
        return dfs(tree, depth + 1, 2 * pos - 1, currentSum) + dfs(tree, depth + 1, 2 * pos, currentSum);
    }
}

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

Задача: 395. Longest Substring with At Least K Repeating Characters
Сложность: medium

Дана строка 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;
    }
}

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

Задача: №22. Generate Parentheses
Сложность: medium

Учитывая n пар круглых скобок, напишите функцию, которая генерирует все возможные комбинации правильных (валидных) круглых скобок.

Пример:

Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"]

👨‍💻 Алгоритм:

1⃣Если n == 1, возвращаем базовый набор: ["()"].

2⃣Для n > 1 вызываем рекурсивную функцию, которая для n - 1 генерирует все предыдущие комбинации и вставляет "()" в каждую возможную позицию каждой строки.

3⃣Используем Set, чтобы избежать дубликатов, так как одна и та же комбинация может получиться при вставке "()" в разные позиции.

😎 Решение:

public List<String> generateParenthesis(int n) {
    Set<String> ans = new HashSet<>();
    ans = createParenthesis(n, ans);
    return new ArrayList<>(ans);
}

private static Set<String> createParenthesis(int n, Set<String> currentList) {
    Set<String> temp = new HashSet<>();
    if (n <= 0) return new HashSet<>();
    if (n == 1) {
        temp.add("()");
        return temp;
    }
    currentList = createParenthesis(n - 1, currentList);
    for (String parenthesis : currentList) {
        for (int i = 0; i <= parenthesis.length(); i++) {
            String newStr = parenthesis.substring(0, i) + "()" + parenthesis.substring(i);
            temp.add(newStr);
        }
    }
    return temp;
}

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

Задача: 1243. Array Transformation
Сложность: easy

Если задан исходный массив arr, то каждый день вы создаете новый массив, используя массив предыдущего дня. В i-й день вы выполняете следующие операции над массивом дня i-1, чтобы получить массив дня i: если элемент меньше своего левого и правого соседа, то этот элемент увеличивается. Если элемент больше своего левого и правого соседа, то этот элемент уменьшается. Первый и последний элементы никогда не меняются. Через несколько дней массив не меняется. Верните этот окончательный массив.

Пример:

Input: arr = [6,2,3,4]
Output: [6,3,3,4]

👨‍💻 Алгоритм:

1⃣Инициализация нового массива с такими же значениями, как у исходного массива.
Циклически изменяем массив в соответствии с правилами, пока он не перестанет меняться.

2⃣Для каждого элемента массива проверяем, изменяется ли он в зависимости от его левого и правого соседей.
Если элемент меньше своего левого и правого соседей, увеличиваем его.
Если элемент больше своего левого и правого соседей, уменьшаем его.

3⃣Первый и последний элементы массива остаются неизменными.

😎 Решение:

import java.util.Arrays;

public class Solution {
    public int[] transformArray(int[] arr) {
        boolean changed;
        do {
            changed = false;
            int[] newArr = arr.clone();
            for (int i = 1; i < arr.length - 1; i++) {
                if (arr[i] < arr[i - 1] && arr[i] < arr[i + 1]) {
                    newArr[i]++;
                    changed = true;
                } else if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) {
                    newArr[i]--;
                    changed = true;
                }
            }

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

Задача: 659. Split Array into Consecutive Subsequences
Сложность: medium

Вам дан отсортированный в неубывающем порядке массив целых чисел nums.

Определите, можно ли разделить nums на одну или несколько подпоследовательностей так, чтобы выполнялись оба следующих условия:

Каждая подпоследовательность является последовательностью последовательных возрастающих чисел (то есть каждое целое число на 1 больше предыдущего).
Все подпоследовательности имеют длину 3 или более.
Верните true, если можно разделить nums согласно вышеуказанным условиям, или false в противном случае.

Подпоследовательность массива — это новый массив, который формируется из исходного массива путем удаления некоторых (может быть, ни одного) элементов без нарушения относительных позиций оставшихся элементов. (например, [1,3,5] является подпоследовательностью [1,2,3,4,5], тогда как [1,3,2] не является).

Пример:

Input: nums = [1,2,3,3,4,5]
Output: true

👨‍💻 Алгоритм:

1⃣Подсчет частоты элементов:
Создайте хеш-таблицу для подсчета количества вхождений каждого элемента в массиве nums.

2⃣Создание подпоследовательностей:
Создайте хеш-таблицу для отслеживания количества подпоследовательностей, которые могут быть продолжены для каждого элемента.
Пройдите по каждому элементу в массиве и выполните следующие действия:
Если элемент можно добавить к существующей подпоследовательности (проверяя хеш-таблицу подпоследовательностей), добавьте его и обновите хеш-таблицу.
Если элемент нельзя добавить к существующей подпоследовательности, начните новую последовательность длиной 3 или более элементов.
Если ни одно из условий не выполнено, верните false.

3⃣Проверка результата:
Верните true, если все элементы успешно распределены по подпоследовательностям.

😎 Решение:

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public boolean isPossible(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>();
        Map<Integer, Integer> need = new HashMap<>();
        
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        
        for (int num : nums) {
            if (freq.get(num) == 0) continue;
            if (need.getOrDefault(num, 0) > 0) {
                need.put(num, need.get(num) - 1);
                need.put(num + 1, need.getOrDefault(num + 1, 0) + 1);
            } else if (freq.getOrDefault(num + 1, 0) > 0 && freq.getOrDefault(num + 2, 0) > 0) {
                freq.put(num + 1, freq.get(num + 1) - 1);
                freq.put(num + 2, freq.get(num + 2) - 1);
                need.put(num + 3, need.getOrDefault(num + 3, 0) + 1);
            } else {
                return false;
            }
            freq.put(num, freq.get(num) - 1);
        }
        
        return true;
    }
}

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

Задача: 732. My Calendar III
Сложность: hard

k-бронирование происходит, когда k событий имеют некоторое непустое пересечение (т.е, дано некоторое время, общее для всех k событий). Даны некоторые события [startTime, endTime), после каждого данного события верните целое число k, представляющее максимальное k-бронирование между всеми предыдущими событиями. Реализация класса MyCalendarThree: MyCalendarThree() Инициализирует объект. int book(int startTime, int endTime) Возвращает целое число k, представляющее наибольшее целое число, при котором в календаре существует k-бронирование.

Пример:

Input
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, 1, 1, 2, 3, 3, 3]

👨‍💻 Алгоритм:

1⃣Создайте два словаря для хранения изменений времени бронирования: один для начала событий, другой для конца событий.

2⃣Для каждого нового события обновите словари начала и конца событий.

3⃣Поддерживайте текущее количество активных бронирований и обновляйте максимальное количество активных бронирований по мере добавления новых событий.

😎 Решение:

import java.util.Map;
import java.util.TreeMap;

public class MyCalendarThree {
    private TreeMap<Integer, Integer> events;

    public MyCalendarThree() {
        events = new TreeMap<>();
    }

    public int book(int startTime, int endTime) {
        events.put(startTime, events.getOrDefault(startTime, 0) + 1);
        events.put(endTime, events.getOrDefault(endTime, 0) - 1);
        
        int active = 0;
        int maxActive = 0;
        for (Map.Entry<Integer, Integer> entry : events.entrySet()) {
            active += entry.getValue();
            maxActive = Math.max(maxActive, active);
        }
        
        return maxActive;
    }
}

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

Задача: 316. Remove Duplicate Letters
Сложность: medium

Дана строка s, удалите повторяющиеся буквы так, чтобы каждая буква появилась один раз и только один раз. Вы должны сделать так, чтобы результат был наименьшим в лексикографическом порядке среди всех возможных результатов.

Пример:

Input: s = "bcabc"
Output: "abc"

👨‍💻 Алгоритм:

1⃣Инициализация стека
Создайте стек, который будет хранить результат, построенный по мере итерации строки.

2⃣Итерация по строке
На каждой итерации добавляйте текущий символ в стек, если он еще не был использован. Перед добавлением текущего символа удаляйте как можно больше символов из вершины стека, если это возможно и улучшает лексикографический порядок.

3⃣Удаление символов
Удаляйте символы с вершины стека при выполнении следующих условий: Символ на вершине стека больше текущего символа. Символ может быть удален, так как он встречается позже в строке. На каждом этапе итерации по строке жадно минимизируйте содержимое стека.

😎 Решение:

import java.util.*;

class Solution {
    public String removeDuplicateLetters(String s) {
        Stack<Character> stack = new Stack<>();
        Set<Character> seen = new HashSet<>();
        Map<Character, Integer> lastOccurrence = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            lastOccurrence.put(s.charAt(i), i);
        }

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!seen.contains(c)) {
                while (!stack.isEmpty() && c < stack.peek() && i < lastOccurrence.get(stack.peek())) {
                    seen.remove(stack.pop());
                }
                seen.add(c);
                stack.push(c);
            }
        }
        StringBuilder result = new StringBuilder();
        for (char c : stack) {
            result.append(c);
        }
        return result.toString();
    }
}

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

Задача: 1103. Distribute Candies to People
Сложность: easy

Мы распределяем некоторое количество конфет ряду из n = num_people человек следующим образом:
Сначала даем 1 конфету первому человеку, 2 конфеты второму человеку и так далее, пока не дадим n конфет последнему человеку.
Затем мы возвращаемся к началу ряда, давая n + 1 конфету первому человеку, n + 2 конфеты второму человеку и так далее, пока не дадим 2 * n конфет последнему человеку.

Этот процесс повторяется (мы каждый раз даем на одну конфету больше и возвращаемся к началу ряда после достижения конца), пока у нас не закончатся конфеты. Последний человек получит все оставшиеся конфеты (не обязательно на одну больше, чем в предыдущий раз).

Верните массив (длиной num_people и суммой candies), который представляет собой окончательное распределение конфет.

Пример:

Input: candies = 7, num_people = 4
Output: [1,2,3,1]
Explanation:
On the first turn, ans[0] += 1, and the array is [1,0,0,0].
On the second turn, ans[1] += 2, and the array is [1,2,0,0].
On the third turn, ans[2] += 3, and the array is [1,2,3,0].
On the fourth turn, ans[3] += 1 (because there is only one candy left), and the final array is [1,2,3,1].

👨‍💻 Алгоритм:

1⃣Вычислите количество людей, получивших полные подарки, и оставшиеся конфеты:
p = floor(sqrt(2C+0.25)-0.5)
remainig = C - p(p+1)/2

2⃣Вычислите количество полных циклов и распределите конфеты:
rows = p // n
d[i]= i*rows + n*rows*(rows-1)/2

3⃣Добавьте конфеты за дополнительный неполный цикл и оставшиеся конфеты:
d[i]+=i+n⋅rows для первых p%n людей
d[p%n]+=remaining
Верните распределение конфет d


😎 Решение:

class Solution {
    public int[] distributeCandies(int candies, int num_people) {
        int n = num_people;
        int p = (int) (Math.sqrt(2 * candies + 0.25) - 0.5);
        int remaining = candies - (p + 1) * p / 2;
        int rows = p / n;
        int cols = p % n;
        
        int[] d = new int[n];
        for (int i = 0; i < n; i++) {
            d[i] = (i + 1) * rows + (rows * (rows - 1) / 2) * n;
            if (i < cols) {
                d[i] += i + 1 + rows * n;
            }
        }
        d[cols] += remaining
        return d;
    }
}

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

Задача: 62. Unique Paths
Сложность: medium

На сетке размером 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);
    }
}

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

Задача: 363. Max Sum of Rectangle No Larger Than K
Сложность: hard

Дана матрица размером m x n и целое число k, вернуть максимальную сумму прямоугольника в матрице, такая что его сумма не превышает k.

Гарантируется, что будет прямоугольник с суммой, не превышающей k.

Пример:

Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Output: 2
Explanation: Because the sum of the blue rectangle [[0, 1], [-2, 3]] is 2, and 2 is the max number no larger than k (k = 2).

👨‍💻 Алгоритм:

1⃣Создать вспомогательную функцию updateResult, которая будет находить максимальную сумму подмассива в одномерном массиве, не превышающую k.

2⃣Преобразовать каждую подматрицу в одномерный массив и применить к ней функцию updateResult.

3⃣Вернуть максимальную найденную сумму.

😎 Решение:

class Solution {
    int result = Integer.MIN_VALUE;
    void updateResult(int[] nums, int k) {
        int sum = 0;

        TreeSet<Integer> sortedSum = new TreeSet<>();

        sortedSum.add(0);
        for (int num : nums) {
            sum += num;

            Integer x = sortedSum.ceiling(sum - k);

            if (x != null)
                result = Math.max(result, sum - x);

            sortedSum.add(sum);
        }
    }
    public int maxSumSubmatrix(int[][] matrix, int k) {
        int[] rowSum = new int[matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            Arrays.fill(rowSum, 0);
            for (int row = i; row < matrix.length; row++) {
                for (int col = 0; col < matrix[0].length; col++)
                    rowSum[col] += matrix[row][col];

                updateResult(rowSum, k);

                if (result == k)
                    return result;
            }
        }
        return result;
    }
}

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

Задача: 1380. Lucky Numbers in a Matrix
Сложность: easy

Дана матрица m x n из различных чисел, верните все счастливые числа в матрице в любом порядке.

Счастливое число — это элемент матрицы, который является минимальным элементом в своей строке и максимальным в своем столбце.

Пример:

Input: matrix = [[3,7,8],[9,11,13],[15,16,17]]
Output: [15]
Explanation: 15 is the only lucky number since it is the minimum in its row and the maximum in its column.

👨‍💻 Алгоритм:

1⃣Сохраните минимум каждой строки в список rowMin и максимум каждого столбца в список colMax.

2⃣Итерируйте по каждому числу в матрице и проверяйте, равно ли оно rowMin[i] и colMax[j].

3⃣Если число удовлетворяет условию, добавьте его в список luckyNumbers и верните luckyNumbers.

😎 Решение:

class Solution {
    public List<Integer> luckyNumbers (int[][] matrix) {
        int N = matrix.length;
        int M = matrix[0].length;
        
        List<Integer> rowMin = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            int rMin = Integer.MAX_VALUE;
            for (int j = 0; j < M; j++) {
                rMin = Math.min(rMin, matrix[i][j]);
            }
            rowMin.add(rMin);
        }
        
        List<Integer> colMax = new ArrayList<>();
        for (int i = 0; i < M; i++) {
            int cMax = Integer.MIN_VALUE;
            for (int j = 0; j < N; j++) {
                cMax = Math.max(cMax, matrix[j][i]);
            }
            colMax.add(cMax);
        }
        
        List<Integer> luckyNumbers = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (matrix[i][j] == rowMin.get(i) && matrix[i][j] == colMax.get(j)) {
                    luckyNumbers.add(matrix[i][j]);
                }
            }
        }
        
        return luckyNumbers;
    }
}

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

Задача: 955. Delete Columns to Make Sorted II
Сложность: medium

Вам дан массив из n строк одинаковой длины. Мы можем выбрать любые индексы удаления и удалить все символы в этих индексах для каждой строки.

Например, если у нас есть strs = ["abcdef", "uvwxyz"] и индексы удаления {0, 2, 3}, то конечный массив после удаления будет ["bef", "vyz"]. Предположим, что мы выбрали набор индексов удаления answer таким образом, что после удаления конечный массив имеет элементы в лексикографическом порядке (т.е, strs[0] <= strs[1] <= strs[2] <= ... <= strs[n - 1]). Возвращает минимально возможное значение answer.length.

Пример:

Input: strs = ["ca","bb","ac"]
Output: 1

👨‍💻 Алгоритм:

1⃣Определить количество строк n и длину каждой строки m.
Создать массив delete_count длиной m, который будет отслеживать количество удаляемых столбцов.

2⃣Итеративно проверить каждую пару соседних строк для всех столбцов.
Если для данной пары строк обнаружено нарушение лексикографического порядка, отметить соответствующий столбец для удаления.

3⃣Повторять процесс до тех пор, пока массив строк не станет лексикографически отсортированным.
Вернуть количество удаленных столбцов.

😎 Решение:

class Solution {
    public int minDeletionSize(String[] strs) {
        int n = strs.length;
        int m = strs[0].length();
        boolean[] deleteCount = new boolean[m];
        
        while (!isSorted(strs, deleteCount)) {
            for (int j = 0; j < m; j++) {
                if (deleteCount[j]) continue;
                for (int i = 0; i < n - 1; i++) {
                    if (strs[i].charAt(j) > strs[i + 1].charAt(j)) {
                        deleteCount[j] = true;
                        break;
                    }
                }
                if (deleteCount[j]) break;
            }
        }
        
        int count = 0;
        for (boolean del : deleteCount) {
            if (del) count++;
        }
        return count;
    }
    
    private boolean isSorted(String[] strs, boolean[] deleteCount) {
        int n = strs.length;
        int m = deleteCount.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < m; j++) {
                if (deleteCount[j]) continue;
                if (strs[i].charAt(j) > strs[i + 1].charAt(j)) return false;
                if (strs[i].charAt(j) < strs[i + 1].charAt(j)) break;
            }
        }
        return true;
    }
}

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

Зарплата 207.000р у Middle-разработчика в Яндекс

«В день уходит несколько часов на созвоны, в остальное время закрываю задачки из спринта, редко перерабатываю. У компании топовый офис, но с коллективом как-то не заладилось. Радуюсь классному ДМС и стабильной зарплате» - middle разработчик из Яндекса.

Бигтех по-русски - канал с реальными зарплатами и историями IT-специалистов российского БигТеха. Там уже опубликованы рассказы программистов Альфа-банка, Сбера и Тинькофф 🤯

Читайте: @bigtech_russia

Задача: 400. Nth Digit
Сложность: medium

Дано целое число n, вернуть n-ю цифру бесконечной последовательности чисел [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...].

Пример:

Input: n = 3
Output: 3

👨‍💻 Алгоритм:

1⃣Определение диапазона
Начните с определения количества цифр в числах текущего диапазона (1-9, 10-99, 100-999 и т.д.).
Уменьшайте значение n, вычитая количество цифр в текущем диапазоне, пока не найдете диапазон, в который попадает n-я цифра.

2⃣Нахождение конкретного числа
Когда определите диапазон, найдите точное число, содержащее n-ю цифру.
Определите индекс цифры в этом числе.

3⃣Возвращение n-й цифры
Извлеките и верните n-ю цифру из найденного числа.

😎 Решение:

class Solution {
    public int findNthDigit(int n) {
        int length = 1;
        long count = 9;
        int start = 1;
        
        while (n > length * count) {
            n -= length * count;
            length++;
            count *= 10;
            start *= 10;
        }
        
        start += (n - 1) / length;
        String s = Integer.toString(start);
        return s.charAt((n - 1) % length) - '0';
    }
}

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

Задача: 392. Is Subsequence
Сложность: easy

Даны две строки 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;
    }
}

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