Задача: 1040. Moving Stones Until Consecutive II
Сложность: medium

Есть несколько камней, расположенных в разных позициях на оси X. Вам дан целочисленный массив stones - позиции камней. Назовите камень конечным, если он имеет наименьшую или наибольшую позицию. За один ход вы берете конечный камень и перемещаете его в незанятую позицию так, чтобы он перестал быть конечным. В частности, если камни находятся, скажем, в позиции stones = [1,2,5], вы не можете переместить конечный камень в позицию 5, поскольку перемещение его в любую позицию (например, 0 или 3) сохранит этот камень в качестве конечного. Игра заканчивается, когда вы не можете сделать больше ни одного хода (т.е, камни находятся в трех последовательных позициях). Возвращает целочисленный массив answer длины 2, где: answer[0] - минимальное количество ходов, которое вы можете сделать, а answer[1] - максимальное количество ходов, которое вы можете сделать.

Пример:

Input: stones = [7,4,9]
Output: [1,2]

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

1⃣Сортировка:
Сначала отсортируем массив камней.

2⃣Максимальное количество ходов:
Максимальное количество ходов равно (последняя позиция - первая позиция + 1) - количество камней, исключая случаи, когда уже имеются три последовательных камня.

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

😎 Решение:

import java.util.Arrays;

public class Solution {
    public int[] numMovesStonesII(int[] stones) {
        Arrays.sort(stones);
        int n = stones.length;
        
        int maxMoves = stones[n-1] - stones[0] + 1 - n;
        maxMoves -= Math.min(stones[1] - stones[0] - 1, stones[n-1] - stones[n-2] - 1);

        int minMoves = Integer.MAX_VALUE;
        int j = 0;

        for (int i = 0; i < n; ++i) {
            while (j < n && stones[j] - stones[i] + 1 <= n) {
                ++j;
            }
            int alreadyInWindow = j - i;
            if (alreadyInWindow == n - 1 && stones[j-1] - stones[i] + 1 == n - 1) {
                minMoves = Math.min(minMoves, 2);
            } else {
                minMoves = Math.min(minMoves, n - alreadyInWindow);
            }
        }

        return new int[] { minMoves, maxMoves };
    }
}

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

Задача: 423. Reconstruct Original Digits from English
Сложность: medium

Дана строка s, содержащая неупорядоченное английское представление цифр от 0 до 9, верните цифры в порядке возрастания.

Пример:

Input: s = "owoztneoer"
Output: "012"

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

1⃣Подсчитайте количество каждого символа в строке s с помощью хэш-таблицы или массива, чтобы определить количество каждого символа.

2⃣Используйте уникальные символы, присутствующие только в одном числе (например, 'z' для 0, 'w' для 2, 'u' для 4, 'x' для 6, 'g' для 8), чтобы определить количество этих цифр в строке. Затем определите количество остальных цифр, вычитая уже найденные цифры.

3⃣Соберите найденные цифры в строку в порядке возрастания и верните результат.

😎 Решение:

class Solution {
    public String originalDigits(String s) {
        int[] count = new char[26 + (int)'a'];
        for(char letter: s.toCharArray()) {
            count[letter]++;
        }

        int[] out = new int[10];
        out[0] = count['z'];
        out[2] = count['w'];
        out[4] = count['u'];
        out[6] = count['x'];
        out[8] = count['g'];
        out[3] = count['h'] - out[8];
        out[5] = count['f'] - out[4];
        out[7] = count['s'] - out[6];
        out[9] = count['i'] - out[5] - out[6] - out[8];
        out[1] = count['n'] - out[7] - 2 * out[9];

        StringBuilder output = new StringBuilder();
        for(int i = 0; i < 10; i++)
            for (int j = 0; j < out[i]; j++)
                output.append(i);
        return output.toString();
    }
}

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

Задача: 654. Maximum Binary Tree
Сложность: medium

Вам дан целочисленный массив nums без дубликатов. Из nums можно рекурсивно построить максимальное двоичное дерево, используя следующий алгоритм: создайте корневой узел, значение которого равно максимальному значению в nums. Рекурсивно постройте левое поддерево по префиксу подмассива слева от максимального значения. Рекурсивно постройте правое поддерево по суффиксу подмассива справа от максимального значения. Верните максимальное двоичное дерево, построенное из nums.

Пример:

Input: nums = [3,2,1,6,0,5]
Output: [6,3,5,null,2,0,null,null,1]

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

1⃣Найдите максимальное значение в текущем подмассиве и создайте узел с этим значением.

2⃣Рекурсивно постройте левое поддерево для подмассива слева от максимального значения.

3⃣Рекурсивно постройте правое поддерево для подмассива справа от максимального значения.

😎 Решение:

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return build(nums, 0, nums.length);
    }

    private TreeNode build(int[] nums, int l, int r) {
        if (l == r) return null;
        int maxIndex = max(nums, l, r);
        TreeNode root = new TreeNode(nums[maxIndex]);
        root.left = build(nums, l, maxIndex);
        root.right = build(nums, maxIndex + 1, r);
        return root;
    }

    private int max(int[] nums, int l, int r) {
        int maxIndex = l;
        for (int i = l + 1; i < r; i++) {
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            }
        }
        return maxIndex;
    }
}

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

Задача: 1257. Smallest Common Region
Сложность: medium

Вам даны списки регионов, в которых первый регион каждого списка включает все остальные регионы этого списка. Естественно, если регион x содержит другой регион y, то x больше y. Также, по определению, регион x содержит сам себя. Даны два региона: region1 и region2, верните наименьший регион, который содержит их оба. Если вам даны регионы r1, r2 и r3 такие, что r1 включает r3, то гарантированно не существует r2 такого, что r2 включает r3. Гарантированно существует наименьший регион.

Пример:

Input:
regions = [["Earth","North America","South America"],
["North America","United States","Canada"],
["United States","New York","Boston"],
["Canada","Ontario","Quebec"],
["South America","Brazil"]],
region1 = "Quebec",
region2 = "New York"
Output: "North America"

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

1⃣Построим дерево регионов, где каждый регион указывает на своего родителя.

2⃣Используя родительскую информацию, найдем путь от каждого региона до корня.

3⃣Найдем последний общий регион в путях двух заданных регионов.

😎 Решение:

import java.util.*;

public class Solution {
    public String findSmallestRegion(List<List<String>> regions, String region1, String region2) {
        Map<String, String> parent = new HashMap<>();

        for (List<String> regionList : regions) {
            for (int i = 1; i < regionList.size(); i++) {
                parent.put(regionList.get(i), regionList.get(0));
            }
        }

        Set<String> ancestors1 = new HashSet<>();
        while (region1 != null) {
            ancestors1.add(region1);
            region1 = parent.get(region1);
        }

        while (!ancestors1.contains(region2)) {
            region2 = parent.get(region2);
        }

        return region2;
    }
}

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

Задача: 1472. Design Browser History
Сложность: medium

У вас есть браузер с одной вкладкой, где вы начинаете на домашней странице и можете посетить другой URL, вернуться назад на определённое количество шагов в истории или переместиться вперёд на определённое количество шагов в истории.

Реализуйте класс BrowserHistory:
BrowserHistory(string homepage) Инициализирует объект с домашней страницей браузера.
void visit(string url) Посещает URL с текущей страницы. Это очищает всю историю вперёд.
string back(int steps) Перемещает на steps шагов назад в истории. Если вы можете вернуться только на x шагов в истории, а steps > x, вы вернётесь только на x шагов. Возвращает текущий URL после перемещения назад в истории на не более чем steps шагов.
string forward(int steps) Перемещает на steps шагов вперёд в истории. Если вы можете переместиться только на x шагов вперёд в истории, а steps > x, вы переместитесь только на x шагов. Возвращает текущий URL после перемещения вперёд в истории на не более чем steps шагов.

Пример:

Input:
["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"]
[["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]]
Output:
[null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]

Explanation:
BrowserHistory browserHistory = new BrowserHistory("leetcode.com");
browserHistory.visit("google.com");       // You are in "leetcode.com". Visit "google.com"
browserHistory.visit("facebook.com");     // You are in "google.com". Visit "facebook.com"
browserHistory.visit("youtube.com");      // You are in "facebook.com". Visit "youtube.com"
browserHistory.back(1);                   // You are in "youtube.com", move back to "facebook.com" return "facebook.com"
browserHistory.back(1);                   // You are in "facebook.com", move back to "google.com" return "google.com"
browserHistory.forward(1);                // You are in "google.com", move forward to "facebook.com" return "facebook.com"
browserHistory.visit("linkedin.com");     // You are in "facebook.com". Visit "linkedin.com"
browserHistory.forward(2);                // You are in "linkedin.com", you cannot move forward any steps.

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

1⃣Инициализация:
Создайте класс BrowserHistory с двумя стеками (history и future) и строковой переменной current для хранения текущего URL. Инициализируйте current с домашней страницей.

2⃣Посещение URL:
Метод visit(url) сохраняет текущий URL в стеке history, устанавливает url как текущий и очищает стек future.

3⃣Навигация назад и вперед:
Метод back(steps) перемещает текущий URL в стек future и извлекает URL из стека history, пока шаги не будут исчерпаны или стек history не станет пустым.
Метод forward(steps) перемещает текущий URL в стек history и извлекает URL из стека future, пока шаги не будут исчерпаны или стек future не станет пустым.

😎 Решение:

class BrowserHistory {
    private Stack<String> history, future;
    private String current;
    
    public BrowserHistory(String homepage) {
        history = new Stack<String>();
        future = new Stack<String>();
        current = homepage;
    }
    
    public void visit(String url) {
        history.push(current);
        current = url;
        future = new Stack<String>();
    }
    
    public String back(int steps) {
        while(steps > 0 && !history.empty()) {
            future.push(current);
            current = history.pop();
            steps--;
        }
        return current;
    }
    
    public String forward(int steps) 
        while(steps > 0 && !future.empty()) {
            history.push(current);
            current = future.pop();
            steps--;
        }
        return current;
    }
}

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

Задача: 1233. Remove Sub-Folders from the Filesystem
Сложность: medium

Если дан список папок folder, верните папки после удаления всех вложенных папок в этих папках. Вы можете вернуть ответ в любом порядке. Если папка[i] находится внутри другой папки[j], она называется ее вложенной папкой. Формат пути - это одна или несколько скомбинированных строк вида: '/', за которой следует одна или несколько строчных английских букв. Например, "/leetcode" и "/leetcode/problems" являются допустимыми путями, а пустая строка и "/" - нет.

Пример:

Input: folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
Output: ["/a","/c/d","/c/f"]

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

1⃣Сортировка папок:
Сначала отсортируем список путей в лексикографическом порядке. Это обеспечит, что при обходе отсортированного списка мы всегда будем проверять родительскую папку перед вложенными папками.

2⃣Фильтрация вложенных папок:
Будем использовать переменную для отслеживания текущей родительской папки.

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

😎 Решение:

import java.util.*;

public class Solution {
    public List<String> removeSubfolders(String[] folder) {
        Arrays.sort(folder);
        List<String> result = new ArrayList<>();
        String parent = "";
        
        for (String path : folder) {
            if (parent.isEmpty() || !path.startsWith(parent + "/")) {
                parent = path;
                result.add(path);
            }
        }
        
        return result;
    }
}

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

Задача: 303. Range Sum Query - Immutable
Сложность: easy

Дан целочисленный массив nums. Обработайте несколько запросов следующего типа:
Вычислите сумму элементов массива nums между индексами left и right включительно, где left <= right.
Реализуйте класс NumArray:
- NumArray(int[] nums) Инициализирует объект с целочисленным массивом nums.
- int sumRange(int left, int right) Возвращает сумму элементов массива nums между индексами left и right включительно (т.е. nums[left] + nums[left + 1] + ... + nums[right]).

Пример:

Input
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]

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

1⃣Инициализация:
Создайте массив sum длиной на один элемент больше, чем массив nums, и заполните его накопленными суммами элементов массива nums.

2⃣Предварительное вычисление сумм:
Заполните массив sum, где каждый элемент sum[i + 1] является суммой всех предыдущих элементов массива nums до индекса i включительно.

3⃣Вычисление диапазонной суммы:
Для каждого запроса суммы элементов между индексами left и right используйте разницу между sum[right + 1] и sum[left], чтобы быстро получить результат.

😎 Решение:

public class NumArray {
    private int[] sum;

    public NumArray(int[] nums) {
        sum = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            sum[i + 1] = sum[i] + nums[i];
        }
    }

    public int sumRange(int i, int j) {
        return sum[j + 1] - sum[i];
    }
}

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

Задача: 238. Product of Array Except Self
Сложность: medium

Дан массив целых чисел nums, верните массив answer такой, что answer[i] равен произведению всех элементов массива nums, кроме nums[i].

Произведение любого префикса или суффикса массива nums гарантированно помещается в 32-битное целое число.

Вы должны написать алгоритм, который работает за время O(n) и не использует операцию деления.

Пример:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

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

1⃣Инициализация массивов L и R: Инициализируйте два пустых массива L и R. Массив L будет содержать произведение всех чисел слева от i, а массив R будет содержать произведение всех чисел справа от i. Заполните массив L, установив L[0] равным 1, а для остальных элементов используйте формулу L[i] = L[i-1] * nums[i-1]. Заполните массив R, установив R[length-1] равным 1, а для остальных элементов используйте формулу R[i] = R[i+1] * nums[i+1].

2⃣Заполнение массивов L и R: Пройдите два цикла для заполнения массивов L и R. В первом цикле заполните массив L, начиная с L[0] и двигаясь вправо. Во втором цикле заполните массив R, начиная с R[length-1] и двигаясь влево.

3⃣Формирование результата: Пройдите по исходному массиву и для каждого элемента i вычислите произведение всех элементов, кроме nums[i], используя L[i] * R[i]. Сохраните результат в массиве answer и верните его.

😎 Решение:

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int length = nums.length;
        int[] L = new int[length];
        int[] R = new int[length];
        int[] answer = new int[length];

        L[0] = 1;
        for (int i = 1; i < length; i++) {
            L[i] = nums[i - 1] * L[i - 1];
        }

        R[length - 1] = 1;
        for (int i = length - 2; i >= 0; i--) {
            R[i] = nums[i + 1] * R[i + 1];
        }

        for (int i = 0; i < length; i++) {
            answer[i] = L[i] * R[i];
        }

        return answer;
    }
}

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

Задача: 315. Count of Smaller Numbers After Self
Сложность: hard

Дан целочисленный массив nums, верните целочисленный массив counts, где counts[i] - это количество элементов справа от nums[i], которые меньше nums[i].

Пример:

Input: nums = [5,2,6,1]
Output: [2,1,1,0]
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

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

1⃣Реализуйте дерево отрезков (segment tree). Поскольку дерево инициализируется нулями, нужно реализовать только операции обновления и запроса. Установите смещение offset = 10^4.

2⃣Итерация по каждому числу в nums в обратном порядке. Для каждого числа выполните следующие действия:
Смещайте число на num + offset.
Запросите количество элементов в дереве отрезков, которые меньше текущего числа.
Обновите счетчик текущего числа в дереве отрезков.

3⃣Верните результат.

😎 Решение:

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        int offset = 10000;
        int size = 2 * 10000 + 1;
        int[] tree = new int[size * 2];
        List<Integer> result = new ArrayList<Integer>();

        for (int i = nums.length - 1; i >= 0; i--) {
            int smaller_count = query(0, nums[i] + offset, tree, size);
            result.add(smaller_count);
            update(nums[i] + offset, 1, tree, size);
        }
        Collections.reverse(result);
        return result;
    }

    private void update(int index, int value, int[] tree, int size) {
        index += size;
        tree[index] += value;
        while (index > 1) {
            index /= 2;
            tree[index] = tree[index * 2] + tree[index * 2 + 1];
        }
    }

    private int query(int left, int right, int[] tree, int size) {
        int result = 0;
        left += size;
        right += size;
        while (left < right) {
            if (left % 2 == 1) {
                result += tree[left];
                left++;
            }
            left /= 2;
            if (right % 2 == 1) {
                right--;
                result += tree[right];
            }
            right /= 2;
        }
        return result;
    }
}

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

Задача: 1466. Reorder Routes to Make All Paths Lead to the City Zero
Сложность: medium

Дано n городов, пронумерованных от 0 до n - 1, и n - 1 дорог, таких, что существует только один путь между двумя различными городами (эта сеть образует дерево). В прошлом году Министерство транспорта решило направить дороги в одном направлении, потому что они слишком узкие.

Дороги представлены массивом connections, где connections[i] = [ai, bi] представляет дорогу от города ai до города bi.
В этом году в столице (город 0) будет большое событие, и многие люди хотят приехать в этот город.
Ваша задача состоит в том, чтобы переориентировать некоторые дороги так, чтобы каждый город мог посетить город 0. Верните минимальное количество изменённых дорог.

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

Пример:

Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
Output: 3
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).

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

1⃣Создайте переменную count для подсчета количества рёбер, которые необходимо изменить. Инициализируйте её нулём. Создайте список смежности adj, который содержит список пар целых чисел так, чтобы adj[node] содержал всех соседей node в форме (neighbor, sign), где neighbor - соседний узел, а sign обозначает направление ребра (оригинальное или искусственное).

2⃣Начните обход в глубину (DFS). Используйте функцию dfs для выполнения обхода. В каждом вызове передавайте параметры node, parent и adj. Начните с узла 0 и parent равным -1.

3⃣Перебирайте всех соседей узла с помощью adj[node]. Для каждого neighbor, sign в adj[node], проверьте, равен ли neighbor родителю. Если равен, не посещайте его снова. Если neighbor не равен parent, выполните count += sign и рекурсивно вызовите dfs с node = neighbor и parent = node. По завершении обхода DFS, в count будет содержаться количество рёбер, которые необходимо изменить. Верните count.

😎 Решение:

class Solution {
    int count = 0;

    public void dfs(int node, int parent, Map<Integer, List<List<Integer>>> adj) {
        if (!adj.containsKey(node)) {
            return;
        }
        for (List<Integer> nei : adj.get(node)) {
            int neighbor = nei.get(0);
            int sign = nei.get(1);
            if (neighbor != parent) {
                count += sign;
                dfs(neighbor, node, adj);
            }
        }
    }

    public int minReorder(int n, int[][] connections) {
        Map<Integer, List<List<Integer>>> adj = new HashMap<>();
        for (int[] connection : connections) {
            adj.computeIfAbsent(connection[0], k -> new ArrayList<List<Integer>>()).add(
                    Arrays.asList(connection[1], 1));
            adj.computeIfAbsent(connection[1], k -> new ArrayList<List<Integer>>()).add(
                    Arrays.asList(connection[0], 0));
        }
        dfs(0, -1, adj);
        return count;
    }
}

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

Задача: 754. Reach a Number
Сложность: medium

Вы стоите в позиции 0 на бесконечной числовой прямой. В позиции target находится пункт назначения. Вы можете сделать некоторое количество ходов numMoves так, чтобы: на каждом ходу вы могли пойти либо налево, либо направо. Во время i-го хода (начиная с i == 1 до i == numMoves) вы делаете i шагов в выбранном направлении. Учитывая целое число target, верните минимальное количество ходов (т.е. минимальное numMoves), необходимое для достижения пункта назначения.

Пример:

Input: target = 2
Output: 3

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

1⃣Инициализируйте переменную для текущей позиции (position) и счетчик шагов (steps).

2⃣Используйте цикл, чтобы добавлять к position текущее количество шагов и увеличивать steps.

3⃣Если position достигает или превышает target и разница между position и target четная, остановите цикл и верните steps.

😎 Решение:

public class Solution {
    public int reachTarget(int target) {
        target = Math.abs(target);
        int position = 0;
        int steps = 0;
        while (position < target || (position - target) % 2 != 0) {
            steps++;
            position += steps;
        }
        return steps;
    }

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

Задача: 1365. How Many Numbers Are Smaller Than the Current Number
Сложность: easy

Дан массив nums. Для каждого элемента nums[i] определите, сколько чисел в массиве меньше его. То есть, для каждого nums[i] вам нужно посчитать количество допустимых j, таких что j != i и nums[j] < nums[i].

Верните ответ в виде массива.

Пример:

Input: nums = [6,5,4,8]
Output: [2,1,0,3]

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

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

2⃣Поиск индекса каждого элемента:
Для каждого элемента nums[i] найдите его индекс в отсортированной копии массива. Этот индекс указывает количество элементов, меньших nums[i].

3⃣Формирование ответа:
Сформируйте массив ответов, где каждый элемент будет соответствовать количеству чисел, меньших текущего.

😎 Решение:

import java.util.Arrays;

public class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int[] sortedNums = nums.clone();
        Arrays.sort(sortedNums);
        int[] result = new int[nums.length];
        
        for (int i = 0; i < nums.length; i++) {
            result[i] = Arrays.binarySearch(sortedNums, nums[i]);
        }
        
        return result;
    }
}

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

Задача: 736. Parse Lisp Expression
Сложность: hard

Нам дан массив asteroids, состоящий из целых чисел, представляющих астероиды в ряд. Для каждого астероида абсолютное значение обозначает его размер, а знак - направление движения (положительное - вправо, отрицательное - влево). Каждый астероид движется с одинаковой скоростью. Определите состояние астероидов после всех столкновений. Если два астероида столкнутся, меньший из них взорвется. Если оба одинакового размера, то взорвутся оба. Два астероида, движущиеся в одном направлении, никогда не встретятся.

Пример:

Input: expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))"
Output: 14

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

1⃣Определите функцию для оценки выражений.

2⃣Используйте рекурсивный подход для обработки различных типов выражений (let, add, mult, и переменных).

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

😎 Решение:

import java.util.*;

public class Solution {
    public int evaluate(String expression) {
        return evaluate(expression, new HashMap<>());
    }
    
    private int evaluate(String expression, Map<String, Integer> env) {
        if (!expression.startsWith("(")) {
            if (Character.isDigit(expression.charAt(0)) || expression.charAt(0) == '-') {
                return Integer.parseInt(expression);
            }
            return env.get(expression);
        }
        
        List<String> tokens = tokenize(expression);
        if (tokens.get(0).equals("let")) {
            for (int i = 1; i < tokens.size() - 2; i += 2) {
                env.put(tokens.get(i), evaluate(tokens.get(i + 1), env));
            }
            return evaluate(tokens.get(tokens.size() - 1), env);
        } else if (tokens.get(0).equals("add")) {
            return evaluate(tokens.get(1), env) + evaluate(tokens.get(2), env);
        } else if (tokens.get(0).equals("mult")) {
            return evaluate(tokens.get(1), env) * evaluate(tokens.get(2), env);
        }
        return 0;
    }
    
    private List<String> tokenize(String expression) {
        List<String> tokens = new ArrayList<>();
        StringBuilder token = new StringBuilder();
        int parens = 0;
        for (char c : expression.toCharArray()) {
            if (c == '(') {
                parens++;
                if (parens == 1) continue;
            } else if (c == ')') {
                parens--;
                if (parens == 0) {
                    tokens.addAll(tokenize(token.toString()));
                    token = new StringBuilder();
                    continue;
                }
            } else if (c == ' ' && parens == 1) {
                if (token.length() > 0) {
                    tokens.add(token.toString());
                    token = new StringBuilder();
                }
                continue;
            }
            token.append(c);
        }
        if (token.length() > 0) {
            tokens.add(token.toString());
        }
        return tokens;
    }
}

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

Задача: 338. Counting Bits
Сложность: easy

Дано целое число n, верните массив ans длиной n + 1, такой что для каждого i (0 <= i <= n), ans[i] будет равняться количеству единиц в двоичном представлении числа i.

Пример:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

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

1⃣ Инициализация массива:
Создайте массив ans длиной n + 1, заполненный нулями. Этот массив будет содержать количество единиц в двоичном представлении каждого числа от 0 до n.

2⃣ Итерация и вычисление:
Пройдите в цикле по всем числам от 1 до n. Для каждого числа x используйте битовую операцию x & (x - 1), чтобы убрать последнюю установленную биту, и добавьте 1 к значению ans для этого результата. Это количество единиц в двоичном представлении числа x.

3⃣ Возврат результата:
Верните заполненный массив ans, который содержит количество единиц для каждого числа от 0 до n.

😎 Решение:

public class Solution {
    public int[] countBits(int num) {
        int[] ans = new int[num + 1];
        for (int x = 1; x <= num; ++x) {
            ans[x] = ans[x & (x - 1)] + 1;
        }
        return ans;
    }
}

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

Задача: 898. Bitwise ORs of Subarrays
Сложность: medium

Если задан целочисленный массив arr, верните количество различных побитовых ИЛИ всех непустых подмассивов arr. Побитовое ИЛИ подмассива - это побитовое ИЛИ каждого целого числа в подмассиве. Побитовым ИЛИ подмассива одного целого числа является это целое число. Подмассив - это непрерывная непустая последовательность элементов в массиве.

Пример:

Input: arr = [0]
Output: 1

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

1⃣Создать множество для хранения уникальных результатов побитового ИЛИ.

2⃣Для каждого элемента массива, вычислить побитовое ИЛИ всех подмассивов, начинающихся с этого элемента.
Добавить результат каждого вычисления в множество.

3⃣Вернуть размер множества.

😎 Решение:

import java.util.*;

class Solution {
    public int subarrayBitwiseORs(int[] arr) {
        Set<Integer> result = new HashSet<>();
        Set<Integer> current = new HashSet<>();
        for (int num : arr) {
            Set<Integer> next = new HashSet<>();
            for (int x : current) {
                next.add(x | num);
            }
            next.add(num);
            current = next;
            result.addAll(current);
        }
        return result.size();
    }
}

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

Задача: 893. Groups of Special-Equivalent Strings
Сложность: medium

Вам дан массив строк одинаковой длины words. За один ход вы можете поменять местами любые два четных или любые два нечетных символа строки words[i]. Две строки words[i] и words[j] являются специально-эквивалентными, если после любого количества ходов words[i] == words[j].

Например, words[i] = "zzxy" и words[j] = "xyzz" являются специально-эквивалентными, потому что мы можем делать ходы "zzxy" -> "xzzy" -> "xyzz". Группа специально-эквивалентных строк из слов - это непустое подмножество слов, такое, что: каждая пара строк в группе специально-эквивалентна, и группа имеет максимально возможный размер (т.е, не существует строки words[i], не входящей в группу, такой, что words[i] является специально-эквивалентной каждой строке в группе). Верните количество групп специально-эквивалентных строк из слов.

Пример:

Input: words = ["abcd","cdab","cbad","xyzz","zzxy","zzyx"]
Output: 3

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

1⃣Для каждой строки в массиве words создать два новых списка: один из символов на четных позициях, другой из символов на нечетных позициях. Отсортировать оба списка и объединить их в одну строку, которая будет представлять каноническую форму строки.

2⃣Использовать множество, чтобы хранить все уникальные канонические формы строк.

3⃣Размер множества будет равен количеству групп специально-эквивалентных строк.

😎 Решение:

import java.util.*;

class Solution {
    public int numSpecialEquivGroups(String[] words) {
        Set<String> uniqueForms = new HashSet<>();
        
        for (String word : words) {
            char[] evenChars = new char[(word.length() + 1) / 2];
            char[] oddChars = new char[word.length() / 2];
            
            for (int i = 0; i < word.length(); i++) {
                if (i % 2 == 0) {
                    evenChars[i / 2] = word.charAt(i);
                } else {
                    oddChars[i / 2] = word.charAt(i);
                }
            }
            
            Arrays.sort(evenChars);
            Arrays.sort(oddChars);
            String canonicalForm = new String(evenChars) + new String(oddChars);
            uniqueForms.add(canonicalForm);
        }
        
        return uniqueForms.size();
    }

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

Задача: 567. Permutation in String
Сложность: medium

Даны две строки s1 и s2. Верните true, если s2 содержит перестановку s1, или false в противном случае.

Другими словами, верните true, если одна из перестановок s1 является подстрокой s2.

Пример:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

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

1⃣Создать массив для подсчета символов в строке s1. Затем создать аналогичный массив для первых len(s1) символов строки s2.

2⃣Использовать скользящее окно для перемещения по строке s2. Для каждой позиции окна обновлять массив подсчета символов и сравнивать его с массивом для строки s1.

3⃣Если массивы совпадают на любом этапе, вернуть true. Если окно достигает конца строки s2 и совпадений не найдено, вернуть false.

😎 Решение:

public class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int s1Len = s1.length(), s2Len = s2.length();
        if (s1Len > s2Len) return false;

        int[] s1Count = new int[26];
        int[] s2Count = new int[26];
        
        for (int i = 0; i < s1Len; i++) {
            s1Count[s1.charAt(i) - 'a']++;
            s2Count[s2.charAt(i) - 'a']++;
        }
        
        for (int i = 0; i < s2Len - s1Len; i++) {
            if (Arrays.equals(s1Count, s2Count)) return true;
            s2Count[s2.charAt(i) - 'a']--;
            s2Count[s2.charAt(i + s1Len) - 'a']++;
        }
        
        return Arrays.equals(s1Count, s2Count);
    }
}

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

Задача: 916. Word Subsets
Сложность: medium

Вам даны два массива строк words1 и words2. Строка b является подмножеством строки a, если каждая буква в b встречается в ней, включая кратность. Например, "wrr" является подмножеством "warrior", но не является подмножеством "world". Строка a из words1 является универсальной, если для каждой строки b в words2, b является подмножеством a. Верните массив всех универсальных строк в words1. Вы можете вернуть ответ в любом порядке.

Пример:

Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"]
Output: ["facebook","google","leetcode"]

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

1⃣Подсчитать максимальное количество каждой буквы в каждом слове из words2.

2⃣Проверить каждое слово из words1, если оно содержит не менее максимального количества каждой буквы, которая встречается в словах из words2.

3⃣Вернуть массив слов из words1, которые удовлетворяют этому условию.

😎 Решение:

import java.util.*;

class Solution {
    public List<String> wordSubsets(String[] words1, String[] words2) {
        int[] maxCount = new int[26];
        for (String word : words2) {
            int[] count = getCount(word);
            for (int i = 0; i < 26; i++) {
                maxCount[i] = Math.max(maxCount[i], count[i]);
            }
        }

        List<String> result = new ArrayList<>();
        for (String word : words1) {
            int[] count = getCount(word);
            if (isUniversal(count, maxCount)) {
                result.add(word);
            }
        }
        
        return result;
    }

    private int[] getCount(String word) {
        int[] count = new int[26];
        for (char c : word.toCharArray()) {
            count[c - 'a']++;
        }
        return count;
    }

    private boolean isUniversal(int[] count, int[] maxCount) {
        for (int i = 0; i < 26; i++) {
            if (count[i] < maxCount[i]) {
                return false;
            }
        }
        return true;
    }
}

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

Задача: 989. Add to Array-Form of Integer
Сложность: easy

Массивная форма целого числа num - это массив, представляющий его цифры в порядке слева направо.

Например, для num = 1321, массивная форма - это [1, 3, 2, 1].
Дано num в массивной форме целого числа и целое число k, верните массивную форму числа num + k.

Пример:

Input: num = [1,2,0,0], k = 34
Output: [1,2,3,4]
Explanation: 1200 + 34 = 1234

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

1⃣Инициализация переменных:
Преобразуйте число k в массив его цифр и переверните оба массива (массив num и массив цифр k).
Завести переменную carry для хранения переноса и инициализировать ее нулем.
Создать пустой массив result для хранения результата.

2⃣Сложение массивов:
Пройдите по элементам массивов num и цифр k, начиная с их конца, сложите соответствующие цифры вместе с переносом (carry).
Если сумма больше 9, сохраните последнюю цифру в текущей позиции результата, а carry установите в 1.
Если сумма меньше 10, установите carry в 0.
Добавьте результат текущего сложения в массив result

3⃣Обработка оставшихся цифр и переноса:
Если один из массивов закончился раньше, продолжайте сложение оставшихся цифр другого массива с переносом.
Если после окончания всех сложений остается перенос (carry), добавьте его в начало массива result.
Переверните массив result обратно и верните его.

😎 Решение:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Solution {
    public List<Integer> addToArrayForm(int[] num, int k) {
        List<Integer> result = new ArrayList<>();
        int n = num.length;

        for (int i = n - 1; i >= 0; i--) {
            k += num[i];
            result.add(k % 10);
            k /= 10;
        }
        while (k > 0) {
            result.add(k % 10);
            k /= 10;
        }
        Collections.reverse(result);
        return result;
    }
}

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

Задача: 438. Find All Anagrams in a String
Сложность: medium

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

Анаграмма - это слово или фраза, образованные перестановкой букв другого слова или фразы, обычно с использованием всех исходных букв ровно один раз.

Пример:

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

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

1⃣Построить эталонный счетчик pCount для строки p.

2⃣Передвигать скользящее окно по строке s: Пересчитывать счетчик скользящего окна sCount на каждом шаге, добавляя одну букву справа и удаляя одну букву слева.

3⃣Если sCount == pCount, обновить выходной список. Вернуть выходной список.

😎 Решение:

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int ns = s.length(), np = p.length();
        if (ns < np) return new ArrayList<>();

        Map<Character, Integer> pCount = new HashMap<>();
        Map<Character, Integer> sCount = new HashMap<>();

        for (char ch : p.toCharArray()) {
            pCount.put(ch, pCount.getOrDefault(ch, 0) + 1);
        }

        List<Integer> output = new ArrayList<>();

        for (int i = 0; i < ns; ++i) {
            char ch = s.charAt(i);
            sCount.put(ch, sCount.getOrDefault(ch, 0) + 1);

            if (i >= np) {
                ch = s.charAt(i - np);
                if (sCount.get(ch) == 1) {
                    sCount.remove(ch);
                } else {
                    sCount.put(ch, sCount.get(ch) - 1);
                }
            }

            if (pCount.equals(sCount)) {
                output.add(i - np + 1);
            }
        }
        return output;
    }
}

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

Задача: 1328. Break a Palindrome
Сложность: medium

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

Верните получившуюся строку. Если нет способа заменить символ, чтобы строка перестала быть палиндромом, верните пустую строку.

Строка a лексикографически меньше строки b (одинаковой длины), если в первой позиции, где они отличаются, у строки a символ строго меньше соответствующего символа в строке b. Например, "abcc" лексикографически меньше "abcd", потому что первой различающейся позицией является четвертая, и 'c' меньше, чем 'd'.

Пример:

Input: palindrome = "abccba"
Output: "aaccba"
Explanation: There are many ways to make "abccba" not a palindrome, such as "zbccba", "aaccba", and "abacba".
Of all the ways, "aaccba" is the lexicographically smallest.

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

1⃣Если длина строки равна 1, верните пустую строку, так как невозможно создать непалиндромическую строку в этом случае.

2⃣Итерируйтесь по строке слева до середины строки: если символ не равен 'a', измените его на 'a' и верните строку.

3⃣Если вы прошли всю левую часть строки и все еще не получили непалиндромическую строку, это означает, что строка состоит только из 'a'. Следовательно, измените последний символ на 'b' и верните полученную строку.

😎 Решение:

class Solution {
    public String breakPalindrome(String palindrome) {
        int length = palindrome.length();
        
        if (length == 1) {
            return "";
        }
        
        char[] palindromeArray = palindrome.toCharArray();
        for (int i = 0; i < length / 2; i++) {
            if (palindromeArray[i] != 'a') {
                palindromeArray[i] = 'a';
                return new String(palindromeArray);
            }
        }
        
        palindromeArray[length - 1] = 'b';
        return new String(palindromeArray);
    }
}

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