Java | LeetCode

Задача: 425. Word Squares
Сложность: hard

Дан массив уникальных строк words, верните все квадраты слов, которые можно построить из этих слов. Одно и то же слово из words можно использовать несколько раз. Вы можете вернуть ответ в любом порядке.

Последовательность строк образует допустимый квадрат слов, если k-я строка и k-й столбец читаются одинаково, где 0 <= k < max(количество строк, количество столбцов).

Например, последовательность слов ["ball", "area", "lead", "lady"] образует квадрат слов, потому что каждое слово читается одинаково как по горизонтали, так и по вертикали.

Пример:

Input: words = ["area","lead","wall","lady","ball"]
Output: [["ball","area","lead","lady"],["wall","area","lead","lady"]]
Explanation:
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).

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

1⃣Постройте хеш-таблицу из входных слов. Функция buildPrefixHashTable(words) создает хеш-таблицу, где ключами являются префиксы, а значениями - списки слов, начинающихся с этих префиксов.

2⃣При помощи функции getWordsWithPrefix(prefix) осуществляйте запросы к хеш-таблице для получения всех слов, обладающих данным префиксом. Это ускоряет поиск подходящих слов для построения квадрата слов.

3⃣Используйте алгоритм с возвратом для построения квадрата слов. В каждый момент времени проверьте, совпадают ли строки и столбцы. Если они совпадают, продолжайте добавлять слова; если нет, вернитесь к предыдущему состоянию и попробуйте другое слово.

😎 Решение:

class Solution {
    int N = 0;
    String[] words = null;
    HashMap<String, List<String>> prefixHashTable = null;

    public List<List<String>> wordSquares(String[] words) {
        this.words = words;
        this.N = words[0].length();

        List<List<String>> results = new ArrayList<>();
        this.buildPrefixHashTable(words);

        for (String word : words) {
            LinkedList<String> wordSquares = new LinkedList<>();
            wordSquares.addLast(word);
            this.backtracking(1, wordSquares, results);
        }
        return results;
    }

    protected void backtracking(int step, LinkedList<String> wordSquares, List<List<String>> results) {
        if (step == N) {
            results.add(new ArrayList<>(wordSquares));
            return;
        }

        StringBuilder prefix = new StringBuilder();
        for (String word : wordSquares) {
            prefix.append(word.charAt(step));
        }

        for (String candidate : this.getWordsWithPrefix(prefix.toString())) {
            wordSquares.addLast(candidate);
            this.backtracking(step + 1, wordSquares, results);
            wordSquares.removeLast();
        }
    }

    protected void buildPrefixHashTable(String[] words) {
        this.prefixHashTable = new HashMap<>();

        for (String word : words) {
            for (int i = 1; i < this.N; ++i) {
                String prefix = word.substring(0, i);
                List<String> wordList = this.prefixHashTable.get(prefix);
                if (wordList == null) {
                    wordList = new ArrayList<>();
                    wordList.add(word);
                    this.prefixHashTable.put(prefix, wordList);
                } else {
                    wordList.add(word);
                }
            }
        }
    }

    protected List<String> getWordsWithPrefix(String prefix) {
        List<String> wordList = this.prefixHashTable.get(prefix);
        return (wordList != null ? wordList : new ArrayList<>());
    }
}

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

Задача: 165. Compare Version Numbers
Сложность: medium

Даны две строки версий, version1 и version2. Сравните их. Строка версии состоит из ревизий, разделенных точками '.'. Значение ревизии — это её целочисленное преобразование с игнорированием ведущих нулей.

Для сравнения строк версий сравнивайте их значения ревизий в порядке слева направо. Если одна из строк версий имеет меньше ревизий, то отсутствующие значения ревизий следует считать равными 0.

Верните следующее:

- Если version1 < version2, верните -1.
- Если version1 > version2, верните 1.
- В противном случае верните 0.

Пример:

Input: version1 = "1.2", version2 = "1.10"
Output: -1
Explanation:
version1's second revision is "2" and version2's second revision is "10": 2 < 10, so version1 < version2.

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

1⃣Разделение строк: Разделите обе строки по символу точки на два массива.

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

3⃣Определение результатов сравнения:
Если два сегмента не равны, верните 1 или -1 в зависимости от того, какой сегмент больше.
Если все сегменты равны после завершения цикла, версии считаются равными. Верните 0

😎 Решение:

class Solution {
    public int compareVersion(String version1, String version2) {
        String[] nums1 = version1.split("\\.");
        String[] nums2 = version2.split("\\.");
        int n1 = nums1.length, n2 = nums2.length;

        int i1, i2;
        for (int i = 0; i < Math.max(n1, n2); ++i) {
            i1 = i < n1 ? Integer.parseInt(nums1[i]) : 0;
            i2 = i < n2 ? Integer.parseInt(nums2[i]) : 0;
            if (i1 != i2) {
                return i1 > i2 ? 1 : -1;
            }
        }
        return 0;
    }
}

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

Задача: 164. Maximum Gap
Сложность: easy

Дан массив целых чисел nums. Верните максимальную разницу между двумя последовательными элементами в его отсортированной форме. Если массив содержит менее двух элементов, верните 0.

Необходимо написать алгоритм, который работает за линейное время и использует линейное дополнительное пространство.

Пример:

Input: nums = [3,6,9,1]
Output: 3
Explanation: The sorted form of the array is [1,3,6,9], either (3,6) or (6,9) has the maximum difference 3.

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

1⃣Инициализация:
Определите минимальное и максимальное значения в массиве для расчета возможного максимального интервала (разрыва) между элементами в идеально распределенном массиве.
Вычислите размер ведра (bucket size), необходимый для размещения всех элементов массива так, чтобы если массив был равномерно распределен, каждый ведер должен содержать хотя бы один элемент. Размер ведра = (max_value - min_value) / (количество элементов - 1).

2⃣Размещение элементов в ведрах:
Создайте ведра для хранения минимальных и максимальных значений каждого ведра. Используйте формулу для распределения каждого элемента в соответствующем ведре на основе его значения.
Игнорируйте пустые ведра при расчете максимального интервала.

3⃣Вычисление максимального интервала:
Пройдите через ведра и вычислите максимальный интервал, сравнивая минимальное значение текущего непустого ведра с максимальным значением предыдущего непустого ведра.
Максимальный интервал будет наибольшей разницей между "минимальными" и "максимальными" значениями последовательных непустых ведер.

😎 Решение:

public class Solution {
    public int maximumGap(int[] nums) {
        if (
            nums == null || nums.length < 2
        ) return 0; 
        Arrays.sort(nums);

        int maxGap = 0;

        for (int i = 0; i < nums.length - 1; i++) maxGap = Math.max(
            nums[i + 1] - nums[i],
            maxGap
        );

        return maxGap;
    }
}

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

Задача: 1274. Number of Ships in a Rectangle
Сложность: hard

(Эта задача является интерактивной.) Каждый корабль находится в целочисленной точке моря, представленной картезианской плоскостью, и каждая целочисленная точка может содержать не более 1 корабля. У вас есть функция Sea.hasShips(topRight, bottomLeft), которая принимает две точки в качестве аргументов и возвращает true, если в прямоугольнике, представленном этими двумя точками, есть хотя бы один корабль, включая на границе. Учитывая две точки: правый верхний и левый нижний углы прямоугольника, верните количество кораблей в этом прямоугольнике. Гарантируется, что в прямоугольнике находится не более 10 кораблей. Решения, содержащие более 400 обращений к hasShips, будут оцениваться как "Неправильный ответ". Кроме того, любые решения, пытающиеся обойти судью, приведут к дисквалификации.

Пример:

Input: 
ships = [[1,1],[2,2],[3,3],[5,5]], topRight = [4,4], bottomLeft = [0,0]
Output: 3

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

1⃣Разделите текущий прямоугольник на четыре меньших прямоугольника

2⃣Рекурсивно проверьте наличие кораблей в каждом из четырех подпрямоугольников, используя функцию hasShips

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

😎 Решение:

public class Solution {
    public int countShips(Sea sea, Point topRight, Point bottomLeft) {
        if (!sea.hasShips(topRight, bottomLeft)) {
            return 0;
        }
        if (topRight.x == bottomLeft.x && topRight.y == bottomLeft.y) {
            return 1;
        }
        int midX = (topRight.x + bottomLeft.x) / 2;
        int midY = (topRight.y + bottomLeft.y) / 2;
        return countShips(sea, new Point(midX, midY), bottomLeft) +
               countShips(sea, topRight, new Point(midX + 1, midY + 1)) +
               countShips(sea, new Point(midX, topRight.y), new Point(bottomLeft.x, midY + 1)) +
               countShips(sea, new Point(topRight.x, midY), new Point(midX + 1, bottomLeft.y));
    }
}

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

Задача: 97. Interleaving String
Сложность: medium

Даны строки s1, s2 и s3. Необходимо определить, может ли строка s3 быть сформирована путем чередования строк s1 и s2.

Чередование двух строк s и t — это конфигурация, при которой s и t делятся на n и m подстрок соответственно так, что:

s = s1 + s2 + ... + sn
t = t1 + t2 + ... + tm
|n - m| ≤ 1
Чередование может быть таким: s1 + t1 + s2 + t2 + s3 + t3 + ... или t1 + s1 + t2 + s2 + t3 + s3 + ...
Примечание: a + b означает конкатенацию строк a и b.

Пример:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Explanation: One way to obtain s3 is:
Split s1 into s1 = "aa" + "bc" + "c", and s2 into s2 = "dbbc" + "a".
Interleaving the two splits, we get "aa" + "dbbc" + "bc" + "a" + "c" = "aadbbcbcac".

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

1⃣В рекурсивном подходе, описанном выше, рассматривается каждая возможная строка, образованная путем чередования двух заданных строк. Однако возникают случаи, когда та же часть s1 и s2 уже была обработана, но в разных порядках (перестановках). Независимо от порядка обработки, если результирующая строка до этого момента совпадает с требуемой строкой (s3), окончательный результат зависит только от оставшихся частей s1 и s2, а не от уже обработанной части. Таким образом, рекурсивный подход приводит к избыточным вычислениям.

2⃣Эту избыточность можно устранить, используя мемоизацию вместе с рекурсией. Для этого мы поддерживаем три указателя i, j, k, которые соответствуют индексу текущего символа s1, s2, s3 соответственно. Также мы поддерживаем двумерный массив memo для отслеживания обработанных до сих пор подстрок. memo[i][j] хранит 1/0 или -1 в зависимости от того, была ли текущая часть строк, то есть до i-го индекса для s1 и до j-го индекса для s2, уже оценена. Мы начинаем с выбора текущего символа s1 (на который указывает i). Если он совпадает с текущим символом s3 (на который указывает k), мы включаем его в обработанную строку и вызываем ту же функцию рекурсивно как: is_Interleave(s1, i+1, s2, j, s3, k+1, memo).

3⃣Таким образом, мы вызвали функцию, увеличив указатели i и k, поскольку часть строк до этих индексов уже была обработана. Аналогично, мы выбираем один символ из второй строки и продолжаем. Рекурсивная функция заканчивается, когда одна из двух строк s1 или s2 полностью обработана. Если, скажем, строка s1 полностью обработана, мы напрямую сравниваем оставшуюся часть s2 с оставшейся частью s3. Когда происходит возврат из рекурсивных вызовов, мы сохраняем значение, возвращенное рекурсивными функциями, в массиве мемоизации memo соответственно, так что когда оно встречается в следующий раз, рекурсивная функция не будет вызвана, но сам массив мемоизации вернет предыдущий сгенерированный результат.

😎 Решение:

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s3.length() != s1.length() + s2.length()) {
            return false;
        }
        boolean dp[][] = new boolean[s1.length() + 1][s2.length() + 1];
        for (int i = 0; i <= s1.length(); i++) {
            for (int j = 0; j <= s2.length(); j++) {
                if (i == 0 && j == 0) {
                    dp[i][j] = true;
                } else if (i == 0) {
                    dp[i][j] = dp[i][j - 1] &&
                    s2.charAt(j - 1) == s3.charAt(i + j - 1);
                } else if (j == 0) {
                    dp[i][j] = dp[i - 1][j] &&
                    s1.charAt(i - 1) == s3.charAt(i + j - 1);
                } else {
                    dp[i][j] = (dp[i - 1][j] &&
                        s1.charAt(i - 1) == s3.charAt(i + j - 1)) ||
                    (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
                }
            }
        }
        return dp[s1.length()][s2.length()];
    }
}

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

Задача: 1470. Shuffle the Array
Сложность: easy

Дан массив nums, состоящий из 2n элементов в форме [x1, x2, ..., xn, y1, y2, ..., yn].

Верните массив в форме [x1, y1, x2, y2, ..., xn, yn].

Пример:

Input: nums = [2,5,1,3,4,7], n = 3
Output: [2,3,5,4,1,7] 
Explanation: Since x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 then the answer is [2,3,5,4,1,7].

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

1⃣Создайте массив result размером 2 * n.

2⃣Итеративно пройдите по массиву nums от 0 до n - 1:
Сохраните элемент xi+1, то есть nums[i], в индекс 2 * i массива result.
Сохраните элемент yi+1, то есть nums[i + n], в индекс 2 * i + 1 массива result.

3⃣Верните массив result.

😎 Решение:

class Solution {
    public int[] shuffle(int[] nums, int n) {
        int[] result = new int[2 * n];
        for (int i = 0; i < n; ++i) {
            result[2 * i] = nums[i];
            result[2 * i + 1] = nums[n + i];
        }
        return result;
    }
}

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

Задача: 288. Unique Word Abbreviation
Сложность: medium

Сокращение слова — это объединение его первой буквы, количества символов между первой и последней буквой и последней буквы. Если слово состоит только из двух символов, то оно является сокращением само по себе.

Например:
dog --> d1g, потому что между первой буквой 'd' и последней буквой 'g' одна буква.
internationalization --> i18n, потому что между первой буквой 'i' и последней буквой 'n' 18 букв.
it --> it, потому что любое слово из двух символов является своим собственным сокращением.
Реализуйте класс ValidWordAbbr:

ValidWordAbbr(String[] dictionary) Инициализирует объект со словарем слов.
boolean isUnique(string word) Возвращает true, если выполняется одно из следующих условий (в противном случае возвращает false):
В словаре нет слова, сокращение которого равно сокращению слова word.
Для любого слова в словаре, сокращение которого равно сокращению слова word, это слово и word одинаковы.

Пример:

Input
["ValidWordAbbr", "isUnique", "isUnique", "isUnique", "isUnique", "isUnique"]
[[["deer", "door", "cake", "card"]], ["dear"], ["cart"], ["cane"], ["make"], ["cake"]]
Output
[null, false, true, false, true, true]

Explanation
ValidWordAbbr validWordAbbr = new ValidWordAbbr(["deer", "door", "cake", "card"]);
validWordAbbr.isUnique("dear"); // return false, dictionary word "deer" and word "dear" have the same abbreviation "d2r" but are not the same.
validWordAbbr.isUnique("cart"); // return true, no words in the dictionary have the abbreviation "c2t".
validWordAbbr.isUnique("cane"); // return false, dictionary word "cake" and word "cane" have the same abbreviation  "c2e" but are not the same.
validWordAbbr.isUnique("make"); // return true, no words in the dictionary have the abbreviation "m2e".
validWordAbbr.isUnique("cake"); // return true, because "cake" is already in the dictionary and no other word in the dictionary has "c2e" abbreviation.

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

1⃣Инициализация:
Создайте словарь сокращений abbrDict, который будет хранить сокращения слов в виде ключей и булевы значения, указывающие, уникально ли сокращение.
Создайте множество dict, содержащее все слова из словаря, чтобы быстро проверять наличие слова в словаре.

2⃣Генерация сокращений:
При инициализации объекта ValidWordAbbr пройдите через каждое слово в словаре и создайте его сокращение.
Если сокращение уже существует в abbrDict, установите значение в false (не уникальное). В противном случае установите значение в true (уникальное).

3⃣Проверка уникальности:
Для метода isUnique создайте сокращение для входного слова и проверьте, есть ли это сокращение в abbrDict.
Если сокращение отсутствует в abbrDict, возвращайте true.
Если сокращение присутствует и оно уникально, проверьте, есть ли это слово в словаре. Если да, возвращайте true, в противном случае - false.

😎 Решение:

public class ValidWordAbbr {
    private final Map<String, Boolean> abbrDict = new HashMap<>();
    private final Set<String> dict;

    public ValidWordAbbr(String[] dictionary) {
        dict = new HashSet<>(Arrays.asList(dictionary));
        for (String s : dict) {
            String abbr = toAbbr(s);
            abbrDict.put(abbr, !abbrDict.containsKey(abbr));
        }
    }

    public boolean isUnique(String word) {
        String abbr = toAbbr(word);
        Boolean hasAbbr = abbrDict.get(abbr);
        return hasAbbr == null || (hasAbbr && dict.contains(word));
    }

    private String toAbbr(String s) {
        int n = s.length();
        if (n <= 2) {
            return s;
        }
        return s.charAt(0) + Integer.toString(n - 2) + s.charAt(n - 1);
    }
}

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

Задача: 317. Shortest Distance from All Buildings
Сложность: hard

Дана сетка m x n, содержащая значения 0, 1 или 2, где:

каждое 0 обозначает пустую землю, по которой можно свободно проходить,
каждое 1 обозначает здание, через которое нельзя пройти,
каждое 2 обозначает препятствие, через которое нельзя пройти.
Вы хотите построить дом на пустой земле, чтобы он достиг всех зданий с минимальным суммарным расстоянием. Можно перемещаться только вверх, вниз, влево и вправо.

Верните минимальное суммарное расстояние для такого дома. Если построить такой дом невозможно согласно указанным правилам, верните -1.

Суммарное расстояние — это сумма расстояний между домами друзей и точкой встречи.

Пример:

Input: grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
Output: 7

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

1⃣Инициализация и запуск BFS
Для каждой пустой ячейки (0) в сетке grid запустите BFS, обходя все соседние ячейки в 4 направлениях, которые не заблокированы и не посещены, отслеживая расстояние от начальной ячейки.

2⃣Обработка BFS и обновление расстояний
При достижении здания (1) увеличьте счетчик достигнутых домов housesReached и суммарное расстояние distanceSum на текущее расстояние. Если housesReached равно общему количеству зданий, верните суммарное расстояние. Если BFS не может достигнуть всех домов, установите значение каждой посещенной пустой ячейки в 2, чтобы не запускать новый BFS из этих ячеек, и верните INT_MAX.

3⃣Обновление и возврат минимального расстояния
Обновите минимальное расстояние (minDistance) после каждого вызова BFS. Если возможно достигнуть все дома из любой пустой ячейки, верните найденное минимальное расстояние. В противном случае, верните -1.

😎 Решение:

import java.util.*;

class Solution {
    private int bfs(int[][] grid, int row, int col, int totalHouses) {
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int rows = grid.length, cols = grid[0].length;
        int distanceSum = 0, housesReached = 0, steps = 0;
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{row, col});
        boolean[][] vis = new boolean[rows][cols];
        vis[row][col] = true;

        while (!q.isEmpty() && housesReached != totalHouses) {
            int size = q.size();
            while (size-- > 0) {
                int[] curr = q.poll();
                int r = curr[0], c = curr[1];
                if (grid[r][c] == 1) {
                    distanceSum += steps;
                    housesReached++;
                    continue;
                }
                for (int[] dir : dirs) {
                    int nr = r + dir[0], nc = c + dir[1];
                    if (nr >= 0 && nc >= 0 && nr < rows && nc < cols && !vis[nr][nc] && grid[nr][nc] != 2) {
                        vis[nr][nc] = true;
                        q.offer(new int[]{nr, nc});
                    }
                }
            }
            steps++;
        }

        if (housesReached != totalHouses) {
            for (int r = 0; r < rows; r++) {
                for (int c = 0; c < cols; c++) {
                    if (grid[r][c] == 0 && vis[r][c]) grid[r][c] = 2;
                }
            }
            return Integer.MAX_VALUE;
        }
        return distanceSum;
    }

    public int shortestDistance(int[][] grid) {
        int minDistance = Integer.MAX_VALUE, rows = grid.length, cols = grid[0].length, totalHouses = 0;
        for (int[] row : grid) for (int cell : row) if (cell == 1) totalHouses++;
        for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) if (grid[r][c] == 0) minDistance = Math.min(minDistance, bfs(grid, r, c, totalHouses));
        return minDistance == Integer.MAX_VALUE ? -1 : minDistance;
    }
}

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

Задача: 1182. Shortest Distance to Target Color
Сложность: medium

Дан массив colors, содержащий три цвета: 1, 2 и 3.

Также даны несколько запросов. Каждый запрос состоит из двух целых чисел i и c. Верните наименьшее расстояние между заданным индексом i и целевым цветом c. Если решения нет, верните -1.

Пример:

Input: colors = [1,1,2,1,3,2,2,3,3], queries = [[1,3],[2,2],[6,1]]
Output: [3,0,3]
Explanation: 
The nearest 3 from index 1 is at index 4 (3 steps away).
The nearest 2 from index 2 is at index 2 itself (0 steps away).
The nearest 1 from index 6 is at index 3 (3 steps away).

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

1⃣Инициализируйте хэш-таблицу для отображения каждого цвета в список индексов. Итерируйте по массиву colors и добавляйте каждый индекс в соответствующий список хэш-таблицы.

2⃣Для каждого запроса, содержащего i и c, если c не является одним из ключей в хэш-таблице, то colors не содержит c, поэтому верните -1. Иначе, найдите позицию i в соответствующем списке индексов indexList для поддержания упорядоченного порядка.

3⃣Если i меньше всех элементов в indexList, то i - indexList[0] является кратчайшим расстоянием. Если i больше всех элементов в indexList, то indexList[indexList.size() - 1] - i является кратчайшим расстоянием. Иначе, ближайшее появление c к i либо на индексе вставки, либо перед ним, поэтому рассчитайте расстояние от i до каждого из них и верните наименьшее.

😎 Решение:

class Solution {
    public List<Integer> shortestDistanceColor(int[] colors, int[][] queries) {
        List<Integer> queryResults = new ArrayList<>();
        Map<Integer, List<Integer>> hashmap = new HashMap<>();

        for (int i = 0; i < colors.length; i++) {
            hashmap.putIfAbsent(colors[i], new ArrayList<Integer>());
            hashmap.get(colors[i]).add(i);
        }

        for (int[] query : queries) {
            int target = query[0], color = query[1];
            if (!hashmap.containsKey(color)) {
                queryResults.add(-1);
                continue;
            }

            List<Integer> indexList = hashmap.get(color);
            int insert = Collections.binarySearch(indexList, target);

            if (insert < 0) {
                insert = (insert + 1) * -1;
            }

            if (insert == 0) {
                queryResults.add(indexList.get(insert) - target);
            } else if (insert == indexList.size()) {
                queryResults.add(target - indexList.get(insert - 1));
            } else {
                int leftNearest = target - indexList.get(insert - 1);
                int rightNearest = indexList.get(insert) - target;
                queryResults.add(Math.min(leftNearest, rightNearest));
            }
        }
        return queryResults;
    }
}

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

Задача: 127. Word Ladder
Сложность: hard

Секвенция трансформации от слова beginWord к слову endWord с использованием словаря wordList представляет собой последовательность слов beginWord -> s1 -> s2 -> ... -> sk, при которой:

Каждая пара соседних слов отличается ровно одной буквой.
Каждый элемент si для 1 <= i <= k присутствует в wordList. Отметим, что beginWord не обязан быть в wordList.
sk равно endWord.
Для двух слов, beginWord и endWord, и словаря wordList, верните количество слов в кратчайшей секвенции трансформации от beginWord к endWord, или 0, если такая секвенция не существует.

Пример:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.

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

1⃣Препроцессинг списка слов: Осуществите препроцессинг заданного списка слов (wordList), чтобы найти все возможные промежуточные состояния слов. Сохраните эти состояния в словаре, где ключом будет промежуточное слово, а значением — список слов, имеющих то же промежуточное состояние.

2⃣Использование очереди для обхода: Поместите в очередь кортеж, содержащий beginWord и число 1, где 1 обозначает уровень узла. Вам нужно вернуть уровень узла endWord, так как он будет представлять длину кратчайшей последовательности преобразования. Используйте словарь посещений, чтобы избежать циклов.

3⃣Поиск кратчайшего пути через BFS (обход в ширину): Пока в очереди есть элементы, получите первый элемент очереди. Для каждого слова определите все промежуточные преобразования и проверьте, не являются ли эти преобразования также преобразованиями других слов из списка. Для каждого найденного слова, которое имеет общее промежуточное состояние с текущим словом, добавьте в очередь пару (слово, уровень + 1), где уровень — это уровень текущего слова. Если вы достигли искомого слова, его уровень покажет длину кратчайшей последовательности преобразования.

😎 Решение:

import java.util.*;

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int L = beginWord.length();
        Map<String, List<String>> allComboDict = new HashMap<>();

        wordList.forEach(word -> {
            for (int i = 0; i < L; i++) {
                String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);
                List<String> transformations = allComboDict.getOrDefault(newWord, new ArrayList<>());
                transformations.add(word);
                allComboDict.put(newWord, transformations);
            }
        });

        Queue<Pair<String, Integer>> Q = new LinkedList<>();
        Q.add(new Pair(beginWord, 1));

        Map<String, Boolean> visited = new HashMap<>();
        visited.put(beginWord, true);

        while (!Q.isEmpty()) {
            Pair<String, Integer> node = Q.remove();
            String word = node.getKey();
            int level = node.getValue();
            for (int i = 0; i < L; i++) {
                String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);

                for (String adjacentWord : allComboDict.getOrDefault(newWord, new ArrayList<>())) {
                    if (adjacentWord.equals(endWord)) {
                        return level + 1;
                    }
                    if (!visited.containsKey(adjacentWord)) {
                        visited.put(adjacentWord, true);
                        Q.add(new Pair(adjacentWord, level + 1));
                    }
                }
            }
        }

        return 0;
    }
}

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

Задача: 906. Super Palindromes
Сложность: hard

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

Пример:

Input: left = "4", right = "1000"
Output: 4

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

1⃣Найти все палиндромы до корня из right.

2⃣Проверить, являются ли квадраты этих палиндромов палиндромами и лежат ли в диапазоне [left, right].

3⃣Подсчитать количество таких суперпалиндромов.

😎 Решение:

class Solution {
    private boolean isPalindrome(long x) {
        String s = Long.toString(x);
        return s.equals(new StringBuilder(s).reverse().toString());
    }

    public int superpalindromesInRange(String left, String right) {
        long leftNum = Long.parseLong(left);
        long rightNum = Long.parseLong(right);
        int count = 0;

        for (int i = 1; i < 100000; i++) {
            String s = Integer.toString(i);
            long palin1 = Long.parseLong(s + new StringBuilder(s).reverse().toString());
            long palin2 = Long.parseLong(s + new StringBuilder(s.substring(0, s.length() - 1)).reverse().toString());

            if (palin1 * palin1 > rightNum) {
                break;
            }
            if (palin1 * palin1 >= leftNum && isPalindrome(palin1 * palin1)) {
                count++;
            }
            if (palin2 * palin2 >= leftNum && palin2 * palin2 <= rightNum && isPalindrome(palin2 * palin2)) {
                count++;
            }
        }

        return count;
    }
}

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

Задача: 1032. Stream of Characters
Сложность: hard

Разработайте алгоритм, который принимает поток символов и проверяет, является ли суффикс этих символов строкой заданного массива строк words. Например, если words = ["abc", "xyz"] и в поток добавлены четыре символа (один за другим) 'a', 'x', 'y' и 'z', ваш алгоритм должен определить, что суффикс "xyz" символов "axyz" соответствует "xyz" из words.

Реализуйте класс StreamChecker: StreamChecker(String[] words) Инициализирует объект с массивом строк words. boolean query(char letter) Принимает новый символ из потока и возвращает true, если любой непустой суффикс из потока образует слово, которое есть в words.

Пример:

Input
["StreamChecker", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query"]
[[["cd", "f", "kl"]], ["a"], ["b"], ["c"], ["d"], ["e"], ["f"], ["g"], ["h"], ["i"], ["j"], ["k"], ["l"]]
Output
[null, false, false, false, true, false, true, false, false, false, false, false, true]

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

1⃣Построение суффиксного Trie:
Создайте суффиксный Trie (префиксное дерево) для хранения всех слов из массива words в обратном порядке. Это позволяет эффективно искать слова, которые являются суффиксами потока символов.

2⃣Проверка суффиксов:
Для каждого нового символа, проходите по текущему списку символов и проверяйте, образуют ли они какой-либо суффикс, присутствующий в Trie. Если найдено совпадение, возвращайте true, иначе продолжайте добавлять новые символы и проверять суффиксы.

3⃣Сравнение двух случаев:
Рассмотрите оба случая: подмассив длины firstLen до подмассива длины secondLen и подмассив длины secondLen до подмассива длины firstLen. Найдите максимальную сумму для каждого случая.

😎 Решение:

import java.util.*;

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEndOfWord = false;
}

public class StreamChecker {
    private TrieNode root;
    private StringBuilder stream;

    public StreamChecker(String[] words) {
        root = new TrieNode();
        stream = new StringBuilder();
        for (String word : words) {
            TrieNode node = root;
            for (int i = word.length() - 1; i >= 0; i--) {
                char ch = word.charAt(i);
                node = node.children.computeIfAbsent(ch, k -> new TrieNode());
            }
            node.isEndOfWord = true;
        }
    }

    public boolean query(char letter) {
        stream.insert(0, letter);
        TrieNode node = root;
        for (int i = 0; i < stream.length(); i++) {
            char ch = stream.charAt(i);
            if (!node.children.containsKey(ch)) return false;
            node = node.children.get(ch);
            if (node.isEndOfWord) return true;
        }
        return false;
    }
}

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

Задача: 677. Map Sum Pairs
Сложность: medium

Создайте карту, которая позволяет выполнять следующие действия:

Отображает строковый ключ на заданное значение.
Возвращает сумму значений, у которых ключ имеет префикс, равный заданной строке.
Реализуйте класс MapSum:

MapSum() Инициализирует объект MapSum.
void insert(String key, int val) Вставляет пару ключ-значение в карту. Если ключ уже существовал, исходная пара ключ-значение будет заменена на новую.
int sum(string prefix) Возвращает сумму всех значений пар, у которых ключ начинается с данного префикса.

Пример:

Input
["MapSum", "insert", "sum", "insert", "sum"]
[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
Output
[null, null, 3, null, 5]

Explanation
MapSum mapSum = new MapSum();
mapSum.insert("apple", 3);  
mapSum.sum("ap");           // return 3 (apple = 3)
mapSum.insert("app", 2);    
mapSum.sum("ap");           // return 5 (apple + app = 3 + 2 = 5)

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

1⃣Для каждого ключа в карте проверить, начинается ли этот ключ с данного префикса.

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

3⃣Вернуть полученную сумму как результат.

😎 Решение:

import java.util.HashMap;

class MapSum {
    HashMap<String, Integer> map;
    public MapSum() {
        map = new HashMap<>();
    }
    public void insert(String key, int val) {
        map.put(key, val);
    }
    public int sum(String prefix) {
        int ans = 0;
        for (String key: map.keySet()) {
            if (key.startsWith(prefix)) {
                ans += map.get(key);
            }
        }
        return ans;
    }
}

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

Задача: 171. Excel Sheet Column Number
Сложность: easy

Дана строка columnTitle, представляющая название столбца, как это отображается в Excel. Вернуть соответствующий номер столбца.

Пример:

Input: columnTitle = "A"
Output: 1

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

1⃣Создайте отображение букв алфавита и их соответствующих значений (начиная с 1).

2⃣Инициализируйте переменную-аккумулятор result.

3⃣Начиная справа налево, вычислите значение символа в
зависимости от его позиции и добавьте его к result.

😎 Решение:

class Solution {
    public int titleToNumber(String s) {
        int result = 0;

        Map<Character, Integer> alpha_map = new HashMap<>();
        for (int i = 0; i < 26; i++) {
            int c = i + 65;
            alpha_map.put((char) c, i + 1);
        }

        int n = s.length();
        for (int i = 0; i < n; i++) {
            char cur_char = s.charAt(n - 1 - i);
            result += alpha_map.get(cur_char) * Math.pow(26, i);
        }
        return result;
    }
}

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

Задача: 1236. Web Crawler
Сложность: medium

Учитывая url startUrl и интерфейс HtmlParser, реализуйте веб-краулер для просмотра всех ссылок, которые находятся под тем же именем хоста, что и startUrl.Верните все ссылки, полученные вашим краулером, в любом порядке. Ваш краулер должен: Начинать со страницы: startUrl Вызывать HtmlParser.getUrls(url), чтобы получить все ссылки с веб-страницы с заданным url. Не просматривайте одну и ту же ссылку дважды. Исследуйте только те ссылки, которые находятся под тем же именем хоста, что и startUrl. Как показано в примере url выше, имя хоста - example.org. Для простоты можно считать, что все урлы используют протокол http без указания порта. Например, урлы http://leetcode.com/problems и http://leetcode.com/contest находятся под одним и тем же именем хоста, а урлы http://example.org/test и http://example.com/abc не находятся под одним и тем же именем хоста.

Пример:

Input:
urls = [
  "http://news.yahoo.com",
  "http://news.yahoo.com/news",
  "http://news.yahoo.com/news/topics/",
  "http://news.google.com",
  "http://news.yahoo.com/us"
]
edges = [[2,0],[2,1],[3,2],[3,1],[0,4]]
startUrl = "http://news.yahoo.com/news/topics/"
Output: [
  "http://news.yahoo.com",
  "http://news.yahoo.com/news",
  "http://news.yahoo.com/news/topics/",
  "http://news.yahoo.com/us"
]

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

1⃣Извлечение имени хоста:
Сначала извлекаем имя хоста из начального URL для проверки всех последующих ссылок.

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

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

😎 Решение:

import java.util.*;

public interface HtmlParser {
    List<String> getUrls(String url);
}

public class Solution {
    private String extractHostname(String url) {
        return url.split("/")[2];
    }

    public List<String> crawl(String startUrl, HtmlParser htmlParser) {
        String hostname = extractHostname(startUrl);
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        queue.offer(startUrl);
        visited.add(startUrl);
        
        while (!queue.isEmpty()) {
            String url = queue.poll();
            for (String nextUrl : htmlParser.getUrls(url)) {
                if (!visited.contains(nextUrl) && extractHostname(nextUrl).equals(hostname)) {
                    visited.add(nextUrl);
                    queue.offer(nextUrl);
                }
            }
        }
        
        return new ArrayList<>(visited);
    }
}

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

Задача: 1287. Element Appearing More Than 25% In Sorted Array
Сложность: easy

Дан массив целых чисел, отсортированный в неубывающем порядке. В этом массиве есть ровно одно число, которое встречается более чем в 25% случаев. Верните это число.

Пример:

Input: arr = [1,2,2,6,6,6,6,7,10]
Output: 6

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

1⃣Инициализируйте хеш-таблицу counts и перебирайте каждый элемент в массиве arr, увеличивая counts[num] для каждого элемента num.

2⃣Установите target = arr.length / 4.

3⃣Перебирайте каждую пару ключ-значение в counts и, если значение > target, верните ключ. Код никогда не достигнет этой точки, так как гарантируется, что ответ существует; верните любое значение.

😎 Решение:

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

class Solution {
    public int findSpecialInteger(int[] arr) {
        Map<Integer, Integer> counts = new HashMap<>();
        int target = arr.length / 4;
        for (int num : arr) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
            if (counts.get(num) > target) {
                return num;
            }
        }
        return -1;
    }
}

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

Задача: 1491. Average Salary Excluding the Minimum and Maximum Salary
Сложность: easy

Вам дан массив уникальных целых чисел salary, где salary[i] — это зарплата i-го сотрудника.

Верните среднюю зарплату сотрудников, исключая минимальную и максимальную зарплату. Ответы, отличающиеся не более чем на 10^-5 от фактического ответа, будут приняты.

Пример:

Input: salary = [4000,3000,1000,2000]
Output: 2500.00000
Explanation: Minimum salary and maximum salary are 1000 and 4000 respectively.
Average salary excluding minimum and maximum salary is (2000+3000) / 2 = 2500

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

1⃣Инициализация переменных:
Установить minSalary в максимально возможное значение, maxSalary в минимально возможное значение и sum в 0.

2⃣Итерация по зарплатам:
Для каждой зарплаты добавить её к переменной sum.
Обновить переменную minSalary, если текущая зарплата меньше её значения.
Обновить переменную maxSalary, если текущая зарплата больше её значения.

3⃣Вычисление среднего значения:
Вернуть значение (sum - minSalary - maxSalary) / (N - 2), предварительно преобразовав числитель и знаменатель в double для точности.

😎 Решение:

class Solution {
    public double average(int[] salaries) {
        int minSalary = Integer.MAX_VALUE;
        int maxSalary = Integer.MIN_VALUE;
        int sum = 0;

        for (int salary : salaries) {
            sum += salary;
            minSalary = Math.min(minSalary, salary);
            maxSalary = Math.max(maxSalary, salary);
        }

        return (double)(sum - minSalary - maxSalary) / (double)(salaries.length - 2);
    }
}

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

Задача: 909. Snakes and Ladders
Сложность: medium

Вам дана доска с целочисленной матрицей n x n, клетки которой помечены метками от 1 до n2 в стиле Бустрофедона, начиная с левого нижнего края доски (т.е. board[n - 1][0]) и чередуя направление в каждой строке. Вы начинаете на клетке 1 доски. В каждый ход, начиная с клетки curr, вы делаете следующее: выбираете клетку назначения next с меткой в диапазоне [curr + 1, min(curr + 6, n2)]. Этот выбор имитирует результат стандартного броска 6-гранного кубика: то есть всегда существует не более 6 мест назначения, независимо от размера доски. Если next имеет змейку или лестницу, вы должны двигаться к месту назначения этой змейки или лестницы. В противном случае вы переходите на следующий. Игра заканчивается, когда вы достигаете клетки n2. Клетка доски в строке r и столбце c имеет змейку или лестницу, если board[r][c] != -1. Местом назначения этой змейки или лестницы является доска[r][c]. В клетках 1 и n2 нет змейки или лестницы. Обратите внимание, что вы можете взять змейку или лестницу не более одного раза за ход. Если конечный пункт змейки или лестницы является началом другой змейки или лестницы, вы не ходите по последующей змейке или лестнице. Например, предположим, что доска имеет вид [[-1,4],[-1,3]], и на первом ходу ваш конечный квадрат - 2. Вы ходите по лестнице до квадрата 3, но не ходите по последующей лестнице до 4. Верните наименьшее количество ходов, необходимое для достижения квадрата n2. Если достичь квадрата невозможно, верните -1.

Пример:

Input: board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]
Output: 4

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

1⃣Представить доску в виде одномерного массива, чтобы легко определить позицию следующего хода.

2⃣Использовать BFS (поиск в ширину) для минимизации количества ходов до клетки n2.
В каждом ходе проверять клетки от curr + 1 до min(curr + 6, n2) и перемещаться по змейкам и лестницам, если они существуют.

3⃣Если достижение клетки n2 невозможно, вернуть -1.

😎 Решение:

import java.util.*;

class Solution {
    public int snakesAndLadders(int[][] board) {
        int n = board.length;
        
        int[] getPos(int x) {
            int quot = (x - 1) / n;
            int rem = (x - 1) % n;
            int row = n - 1 - quot;
            int col = (row % 2 != n % 2) ? rem : n - 1 - rem;
            return new int[]{row, col};
        }
        
        Set<Integer> visited = new HashSet<>();
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{1, 0});
        
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int pos = curr[0];
            int steps = curr[1];
            for (int i = 1; i <= 6; i++) {
                int nextPos = pos + i;
                if (nextPos > n * n) continue;
                int[] rc = getPos(nextPos);
                int r = rc[0], c = rc[1];
                if (board[r][c] != -1) {
                    nextPos = board[r][c];
                }
                if (nextPos == n * n) {
                    return steps + 1;
                }
                if (!visited.contains(nextPos)) {
                    visited.add(nextPos);
                    queue.offer(new int[]{nextPos, steps + 1});
                }
            }
        }
        return -1;
    }
}

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

Задача: 852. Peak Index in a Mountain Array
Сложность: medium

Вам дан целочисленный массив горы arr длины n, где значения увеличиваются до пикового элемента, а затем уменьшаются.

Верните индекс пикового элемента.

Ваша задача — решить это с временной сложностью O(log(n)).

Пример:

Input: arr = [0,1,0]

Output: 1

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

1⃣Создайте целочисленную переменную i и инициализируйте её значением 0.

2⃣Используя цикл while, проверьте, если текущий элемент, на который указывает i, меньше следующего элемента на индексе i + 1. Если arr[i] < arr[i + 1], увеличьте i на 1.

3⃣В противном случае, если arr[i] > arr[i + 1], верните i.

😎 Решение:

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int i = 0;
        while (arr[i] < arr[i + 1]) {
            i++;
        }
        return i;
    }
}

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

Задача: 1533. Find the Index of the Large Integer
Сложность: medium

У нас есть целочисленный массив arr, в котором все элементы равны, кроме одного элемента, который больше остальных. Вам не будет предоставлен прямой доступ к массиву, вместо этого у вас будет API ArrayReader, который имеет следующие функции:

int compareSub(int l, int r, int x, int y): где 0 <= l, r, x, y < ArrayReader.length(), l <= r и x <= y. Функция сравнивает сумму подмассива arr[l..r] с суммой подмассива arr[x..y] и возвращает:
1, если arr[l] + arr[l+1] + ... + arr[r] > arr[x] + arr[x+1] + ... + arr[y].
0, если arr[l] + arr[l+1] + ... + arr[r] == arr[x] + arr[x+1] + ... + arr[y].
-1, если arr[l] + arr[l+1] + ... + arr[r] < arr[x] + arr[x+1] + ... + arr[y].

int length(): Возвращает размер массива.

Вам разрешено вызывать compareSub() не более 20 раз. Вы можете предположить, что обе функции работают за O(1) время.

Верните индекс массива arr, который содержит наибольший элемент.

Пример:

Input: arr = [7,7,7,7,10,7,7,7]
Output: 4
Explanation: The following calls to the API
reader.compareSub(0, 0, 1, 1) // returns 0 this is a query comparing the sub-array (0, 0) with the sub array (1, 1), (i.e. compares arr[0] with arr[1]).
Thus we know that arr[0] and arr[1] doesn't contain the largest element.
reader.compareSub(2, 2, 3, 3) // returns 0, we can exclude arr[2] and arr[3].
reader.compareSub(4, 4, 5, 5) // returns 1, thus for sure arr[4] is the largest element in the array.
Notice that we made only 3 calls, so the answer is valid.

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

1⃣Установите left = 0 и length = reader.length. left - это самый левый индекс нашего поискового пространства, а length - это размер нашего поискового пространства. Индекс большего числа всегда должен находиться в пределах [left, left + length).

2⃣Пока length > 1:
— Обновите length до length / 2.
— Установите cmp равным reader.compareSub(left, left + length - 1, left + length, left + length + length - 1).
— Если cmp равно 0, верните left + length + length, так как оставшийся элемент является большим числом. Это возможно только если текущее поисковое пространство имеет нечетную длину, поэтому если у нас четная длина, мы не беспокоимся об этом случае.
— Если cmp равно -1, увеличьте left на length.
— Если cmp равно 1, ничего не делайте, так как наш left остается прежним и мы уже разделили length на 2.

3⃣Верните left. Это стандартная процедура для бинарного поиска, когда если поиск завершается без возврата, то левая граница указывает на ответ.

😎 Решение:

class Solution {
    public int getIndex(ArrayReader reader) {
        int left = 0;
        int length = reader.length();
        while (length > 1) {
            length /= 2;
            int cmp = reader.compareSub(left, left + length - 1, left + length, left + 2 * length - 1);
            if (cmp == 0) {
                return left + 2 * length;
            }
            if (cmp < 0) {
                left += length;
            }
        }
        return left;
    }
}

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