#medium
Задача: 340. Longest Substring with At Most K Distinct Characters

Дана строка s и целое число k. Верните длину самой длинной подстроки s, которая содержит не более k различных символов.

Пример:

Input: n = 27
Output: true
Explanation: 27 = 3^3

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

1⃣Инициализация
Используйте два указателя (left и right) для отслеживания текущего окна в строке. Создайте словарь для отслеживания количества каждого символа в текущем окне. Инициализируйте переменные для хранения максимальной длины подстроки (max_length).

2⃣Раздвижение окна
Перемещайте правый указатель (right) по строке и обновляйте словарь. Если количество различных символов в словаре превышает k, перемещайте левый указатель (left) вправо, уменьшая счетчик символов, пока количество различных символов снова не станет меньше или равно k.

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

😎 Решение:

public class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        int left = 0;
        int right = 0;
        Map<Character, Integer> charCount = new HashMap<>();
        int maxLength = 0;
        
        while (right < s.length()) {
            charCount.put(s.charAt(right), charCount.getOrDefault(s.charAt(right), 0) + 1);
            while (charCount.size() > k) {
                charCount.put(s.charAt(left), charCount.get(s.charAt(left)) - 1);
                if (charCount.get(s.charAt(left)) == 0) {
                    charCount.remove(s.charAt(left));
                }
                left++;
            }
            maxLength = Math.max(maxLength, right - left + 1);
            right++;
        }
        
        return maxLength;
    }
}

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

#medium
Задача: 510. Inorder Successor in BST II

Дан узел в двоичном дереве поиска, верните его последующего (in-order successor) в этом дереве. Если у узла нет последующего, верните null.

Последующий узла — это узел с наименьшим ключом, большим, чем node.val.

Вы будете иметь прямой доступ к узлу, но не к корню дерева. Каждый узел будет иметь ссылку на своего родителя. Ниже приведено определение для Node:

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}

Пример:

Input: tree = [5,3,6,2,4,null,null,1], node = 6
Output: null
Explanation: There is no in-order successor of the current node, so the answer is null.

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

1⃣Проверка правого поддерева
Если у узла есть правый потомок, перейдите к правому узлу, затем спускайтесь влево до самого нижнего узла. Этот узел будет следующим узлом в порядке in-order.

2⃣Поиск предка
Если у узла нет правого потомка, поднимайтесь по дереву до тех пор, пока узел не станет левым потомком своего родителя. Родитель этого узла будет следующим узлом в порядке in-order.

3⃣Возвращение результата
Верните найденный узел или null, если следующий узел не найден.

😎 Решение:

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}

class Solution {
  public Node inorderSuccessor(Node x) {
    if (x.right != null) {
      x = x.right;
      while (x.left != null) x = x.left;
      return x;
    }

    while (x.parent != null && x == x.parent.right) x = x.parent;
    return x.parent;
  }
}

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

#medium
Задача: 725. Split Linked List in Parts

Учитывая голову односвязного списка и целое число k, разбейте связный список на k последовательных частей связного списка. Длина каждой части должна быть как можно более одинаковой: никакие две части не должны иметь размер, отличающийся более чем на единицу. Это может привести к тому, что некоторые части будут нулевыми. Части должны располагаться в порядке появления во входном списке, и части, появившиеся раньше, всегда должны иметь размер, больший или равный частям, появившимся позже. Возвращается массив из k частей.

Пример:

Input: head = [1,2,3], k = 5
Output: [[1],[2],[3],[],[]]

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

1⃣Определите общую длину связного списка.

2⃣Вычислите базовый размер каждой части и количество частей, которые должны быть на одну единицу длиннее.

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

😎 Решение:

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    public ListNode[] splitListToParts(ListNode root, int k) {
        int length = 0;
        ListNode node = root;
        while (node != null) {
            length++;
            node = node.next;
        }

        int partLength = length / k;
        int extraParts = length % k;

        ListNode[] parts = new ListNode[k];
        node = root;
        for (int i = 0; i < k; i++) {
            ListNode partHead = node;
            int partSize = partLength + (i < extraParts ? 1 : 0);
            for (int j = 0; j < partSize - 1; j++) {
                if (node != null) node = node.next;
            }
            if (node != null) {
                ListNode nextPart = node.next;
                node.next = null;
                node = nextPart;
            }
            parts[i] = partHead;
        }

        return parts;
    }
}

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

#medium
Задача: 341. Flatten Nested List Iterator

Вам дан вложенный список целых чисел nestedList. Каждый элемент либо является целым числом, либо списком, элементы которого также могут быть целыми числами или другими списками. Реализуйте итератор для его развёртки.

Реализуйте класс NestedIterator:

NestedIterator(List<NestedInteger> nestedList) Инициализирует итератор вложенным списком nestedList.
int next() Возвращает следующий целый элемент вложенного списка.
boolean hasNext() Возвращает true, если в вложенном списке еще остались целые числа, и false в противном случае.

Пример:

Input: nestedList = [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

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

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

2⃣Метод next()
Возвращает следующий целый элемент из стека или очереди. Если текущий элемент является списком, развёртывайте его и добавляйте элементы в стек.

3⃣Метод hasNext()
Проверяет, есть ли в стеке или очереди оставшиеся целые элементы. Если на вершине стека находится список, развёртывайте его до тех пор, пока не встретится целый элемент.

😎 Решение:

public class NestedIterator implements Iterator<Integer> {
    private Stack<NestedInteger> stack;
    
    public NestedIterator(List<NestedInteger> nestedList) {
        stack = new Stack<>();
        flatten(nestedList);
    }
    
    private void flatten(List<NestedInteger> nestedList) {
        for (int i = nestedList.size() - 1; i >= 0; i--) {
            stack.push(nestedList.get(i));
        }
    }
    
    @Override
    public Integer next() {
        return stack.pop().getInteger();
    }
    
    @Override
    public boolean hasNext() {
        while (!stack.isEmpty() && !stack.peek().isInteger()) {
            flatten(stack.pop().getList());
        }
        return !stack.isEmpty();
    }
}

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

#medium
Задача: 729. My Calendar I

Вы создаете программу для использования в качестве календаря. Мы можем добавить новое событие, если его добавление не приведет к двойному бронированию. Двойное бронирование происходит, когда два события имеют некоторое непустое пересечение (т.е, Событие можно представить в виде пары целых чисел start и end, которая представляет собой бронирование на полуоткрытом интервале [start, end), диапазоне вещественных чисел x таких, что start <= x < end. Реализация класса MyCalendar: MyCalendar() Инициализирует объект календаря. boolean book(int start, int end) Возвращает true, если событие может быть успешно добавлено в календарь, не вызывая двойного бронирования. В противном случае возвращается false и событие не добавляется в календарь.

Пример:

Input
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
Output
[null, true, false, true]

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

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

2⃣Реализуйте метод book(int start, int end) для проверки пересечения нового события с уже существующими событиями.

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

😎 Решение:

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

public class MyCalendar {
    private List<int[]> events;

    public MyCalendar() {
        events = new ArrayList<>();
    }

    public boolean book(int start, int end) {
        for (int[] event : events) {
            if (start < event[1] && end > event[0]) {
                return false;
            }
        }
        events.add(new int[] {start, end});
        return true;
    }
}

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

#medium
Задача: 731. My Calendar II

Вы создаете программу для использования в качестве календаря. Мы можем добавить новое событие, если его добавление не приведет к тройному бронированию. Тройное бронирование происходит, когда три события имеют некоторое непустое пересечение (т.е, Событие можно представить в виде пары целых чисел start и end, которая представляет собой бронирование на полуоткрытом интервале [start, end), диапазоне вещественных чисел x таких, что start <= x < end. Реализация класса MyCalendarTwo: MyCalendarTwo() Инициализирует объект календаря. boolean book(int start, int end) Возвращает true, если событие может быть успешно добавлено в календарь, не вызывая тройного бронирования. В противном случае возвращается false и событие не добавляется в календарь.

Пример:

Input
["MyCalendarTwo", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, true, true, true, false, true, true]

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

1⃣Создайте два списка: один для отслеживания всех событий, второй для отслеживания пересечений. подпоследовательностей.

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

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

😎 Решение:

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

public class MyCalendarTwo {
    private List<int[]> events;
    private List<int[]> overlaps;

    public MyCalendarTwo() {
        events = new ArrayList<>();
        overlaps = new ArrayList<>();
    }

    public boolean book(int start, int end) {
        for (int[] overlap : overlaps) {
            if (start < overlap[1] && end > overlap[0]) {
                return false;
            }
        }
        for (int[] event : events) {
            if (start < event[1] && end > event[0]) {
                overlaps.add(new int[]{Math.max(start, event[0]), Math.min(end, event[1])});
            }
        }
        events.add(new int[]{start, end});
        return true;
    }
}        this.events.push([start, end]);
        return true;
    }
}

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

#medium
Задача: 735. Asteroid Collision

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

Пример:

Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","fine"],["drama","acting"],["skills","talent"]]
Output: true

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

1⃣Используйте стек для отслеживания движущихся вправо астероидов.

2⃣Пройдите по массиву астероидов: Если астероид движется вправо, добавьте его в стек. Если астероид движется влево, сравните его с последним астероидом в стеке (если он есть и движется вправо): Если движущийся вправо астероид больше, текущий взорвется. Если движущийся влево астероид больше, последний астероид в стеке взорвется, и продолжите сравнение. Если они одинакового размера, оба взорвутся.

3⃣Добавьте оставшиеся астероиды из стека и текущий астероид в результат.

😎 Решение:

import java.util.*;

public class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack<>();
        
        for (int asteroid : asteroids) {
            boolean alive = true;
            while (alive && asteroid < 0 && !stack.isEmpty() && stack.peek() > 0) {
                int last = stack.pop();
                if (last == -asteroid) {
                    alive = false;
                } else if (last > -asteroid) {
                    stack.push(last);
                    alive = false;
                }
            }
            if (alive) {
                stack.push(asteroid);
            }
        }
        
        int[] result = new int[stack.size()];
        for (int i = result.length - 1; i >= 0; i--) {
            result[i] = stack.pop();
        }
        
        return result;
    }
}

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

#medium
Задача: 737. Sentence Similarity II

Мы можем представить предложение в виде массива слов, например, предложение "I am happy with leetcode" можно представить как arr = ["I", "am",happy", "with", "leetcode"].

Даны два предложения sentence1 и sentence2, каждое из которых представлено в виде массива строк, и массив пар строк similarPairs, где similarPairs[i] = [xi, yi] указывает, что два слова xi и yi похожи. Возвращается true, если предложения sentence1 и sentence2 похожи, или false, если они не похожи. Два предложения похожи, если: у них одинаковая длина (т.е, Заметьте, что слово всегда похоже само на себя, также обратите внимание, что отношение сходства является транзитивным. Например, если слова a и b похожи, а слова b и c похожи, то a и c похожи.

Пример:

Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","good"],["fine","good"],["drama","acting"],["skills","talent"]]
Output: true

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

1⃣Проверить, одинаковой ли длины предложения sentence1 и sentence2. Если нет, вернуть false.

2⃣Построить граф схожести слов с использованием словаря.

3⃣Использовать поиск в глубину (DFS) для проверки транзитивной схожести слов в предложениях.

😎 Решение:

import java.util.*;

public class Solution {
    public boolean areSentencesSimilar(String[] sentence1, String[] sentence2, List<List<String>> similarPairs) {
        if (sentence1.length != sentence2.length) {
            return false;
        }
        
        Map<String, List<String>> graph = new HashMap<>();
        for (List<String> pair : similarPairs) {
            graph.computeIfAbsent(pair.get(0), k -> new ArrayList<>()).add(pair.get(1));
            graph.computeIfAbsent(pair.get(1), k -> new ArrayList<>()).add(pair.get(0));
        }
        
        for (int i = 0; i < sentence1.length; i++) {
            if (!sentence1[i].equals(sentence2[i]) && !dfs(sentence1[i], sentence2[i], graph, new HashSet<>())) {
                return false;
            }
        }
        
        return true;
    }
    
    private boolean dfs(String word1, String word2, Map<String, List<String>> graph, Set<String> visited) {
        if (word1.equals(word2)) {
            return true;
        }
        visited.add(word1);
        for (String neighbor : graph.getOrDefault(word1, Collections.emptyList())) {
            if (!visited.contains(neighbor) && dfs(neighbor, word2, graph, visited)) {
                return true;
            }
        }
        return false;
    }
}

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

#medium
Задача: 738. Monotone Increasing Digits

Целое число имеет монотонно возрастающие цифры тогда и только тогда, когда каждая пара соседних цифр x и y удовлетворяет x <= y. Задав целое число n, верните наибольшее число, которое меньше или равно n с монотонно возрастающими цифрами.

Пример:

Input: n = 10
Output: 9

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

1⃣Преобразуйте число в строку для удобства обработки.

2⃣Найдите позицию, где последовательность перестает быть монотонной.

3⃣Уменьшите соответствующую цифру и установите все последующие цифры в 9.

😎 Решение:

public class Solution {
    public int monotoneIncreasingDigits(int n) {
        char[] digits = Integer.toString(n).toCharArray();
        int mark = digits.length;

        for (int i = digits.length - 1; i > 0; i--) {
            if (digits[i] < digits[i - 1]) {
                mark = i;
                digits[i - 1]--;
            }
        }

        for (int i = mark; i < digits.length; i++) {
            digits[i] = '9';
        }

        return Integer.parseInt(new String(digits));
    }
}

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

#medium
Задача: 739. Daily Temperatures

Задав массив целых чисел temperature, представляющих дневные температуры, верните массив answer, такой, что answer[i] - это количество дней, которые нужно подождать после i-го дня, чтобы температура стала теплее. Если в будущем не существует дня, для которого это возможно, сохраните answer[i] == 0.

Пример:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

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

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

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

3⃣Возвращайте массив ответов.

😎 Решение:

public class Solution {
    public int[] dailyTemperatures(int[] T) {
        int n = T.length;
        int[] answer = new int[n];
        Stack<Integer> stack = new Stack<>();
        
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
                int j = stack.pop();
                answer[j] = i - j;
            }
            stack.push(i);
        }
        
        return answer;
    }
}

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

#medium
Задача: 740. Delete and Earn

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

Пример:

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

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

1⃣Подсчитайте количество каждого числа в массиве nums.

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

3⃣Для каждого числа num в nums, учитывайте два случая: не брать число или взять число и добавить его очки.

😎 Решение:

import java.util.*;

public class Solution {
    public int deleteAndEarn(int[] nums) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }
        
        int avoid = 0, using = 0, prev = -1;
        for (int num : count.keySet().stream().sorted().mapToInt(Integer::intValue).toArray()) {
            if (num - 1 != prev) {
                int newAvoid = Math.max(avoid, using);
                using = num * count.get(num) + Math.max(avoid, using);
                avoid = newAvoid;
            } else {
                int newAvoid = Math.max(avoid, using);
                using = num * count.get(num) + avoid;
                avoid = newAvoid;
            }
            prev = num;
        }
        
        return Math.max(avoid, using);
    }
}

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

#medium
Задача: 742. Closest Leaf in a Binary Tree

Если задан корень бинарного дерева, в котором каждый узел имеет уникальное значение, а также задано целое число k, верните значение ближайшего к цели k узла листа дерева. Ближайший к листу узел означает наименьшее количество ребер, пройденных бинарным деревом, чтобы достичь любого листа дерева. Кроме того, узел называется листом, если у него нет дочерних узлов.

Пример:

Input: root = [1,3,2], k = 1
Output: 2

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

1⃣Пройдите дерево, чтобы найти путь от корня до узла k и сохранить его в список.

2⃣Найдите все листья и минимальное расстояние до них, используя BFS, начиная с найденного узла k.

3⃣Верните значение ближайшего листа.

😎 Решение:

import java.util.*;

public class Solution {
    public int findClosestLeaf(TreeNode root, int k) {
        List<TreeNode> path = new ArrayList<>();
        Map<TreeNode, Integer> leaves = new HashMap<>();
        
        findPath(root, k, path);
        findLeaves(root, leaves);
        
        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        queue.add(new Pair<>(path.get(path.size() - 1), 0));
        Set<TreeNode> visited = new HashSet<>();
        
        while (!queue.isEmpty()) {
            Pair<TreeNode, Integer> pair = queue.poll();
            TreeNode node = pair.getKey();
            int dist = pair.getValue();
            if (leaves.containsKey(node)) return node.val;
            visited.add(node);
            if (node.left != null && !visited.contains(node.left)) queue.add(new Pair<>(node.left, dist + 1));
            if (node.right != null && !visited.contains(node.right)) queue.add(new Pair<>(node.right, dist + 1));
            if (path.size() > 1) queue.add(new Pair<>(path.remove(path.size() - 1), dist + 1));
        }
        return -1;
    }
    
    private boolean findPath(TreeNode node, int k, List<TreeNode> path) {
        if (node == null) return false;
        path.add(node);
        if (node.val == k) return true;
        if (findPath(node.left, k, path) || findPath(node.right, k, path)) return true;
        path.remove(path.size() - 1);
        return false;
    }
    
    private void findLeaves(TreeNode node, Map<TreeNode, Integer> leaves) {
        if (node == null) return;
        if (node.left == null && node.right == null) leaves.put(node, 0);
        findLeaves(node.left, leaves);
        findLeaves(node.right, leaves);
    }
}

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

class Pair<K, V> {
    private K key;
    private V value;
    public Pair(K key, V value) {
        this.key = key;
        this.value = value;
    }
    public K getKey() { return key; }
    public V getValue() { return value; }
}

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

#medium
Задача: 743. Network Delay Time

Дана сеть из узлов, помеченных от 1 до n. Также дано times - список времен прохождения сигнала в виде направленных ребер times[i] = (ui, vi, wi), где ui - исходный узел, vi - целевой узел, а wi - время прохождения сигнала от источника до цели. Мы пошлем сигнал из заданного узла k. Верните минимальное время, которое потребуется всем узлам, чтобы получить сигнал. Если все узлы не могут получить сигнал, верните -1.

Пример:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

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

1⃣Представьте граф в виде списка смежности.

2⃣Используйте алгоритм Дейкстры для нахождения кратчайших путей от узла k до всех других узлов.

3⃣Найдите максимальное значение среди кратчайших путей к узлам. Если какой-либо узел недостижим, верните -1.

😎 Решение:

import java.util.*;

public class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            graph.put(i, new ArrayList<>());
        }
        for (int[] time : times) {
            graph.get(time[0]).add(new int[]{time[1], time[2]});
        }

        PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        minHeap.add(new int[]{0, k});
        Map<Integer, Integer> minTime = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            minTime.put(i, Integer.MAX_VALUE);
        }
        minTime.put(k, 0);

        while (!minHeap.isEmpty()) {
            int[] top = minHeap.poll();
            int time = top[0];
            int node = top[1];
            for (int[] neighbor : graph.get(node)) {
                int newTime = time + neighbor[1];
                if (newTime < minTime.get(neighbor[0])) {
                    minTime.put(neighbor[0], newTime);
                    minHeap.add(new int[]{newTime, neighbor[0]});
                }
            }
        }

        int maxTime = Collections.max(minTime.values());
        return maxTime == Integer.MAX_VALUE ? -1 : maxTime;
    }
}

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

#medium
Задача: 750. Number Of Corner Rectangles

Дан указатель на начало односвязного списка и два целых числа left и right, где left <= right. Необходимо перевернуть узлы списка, начиная с позиции left и заканчивая позицией right, и вернуть измененный список.

Пример:

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

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

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

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

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

😎 Решение:

public class Solution {
    public int countCornerRectangles(int[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = i + 1; j < grid.length; j++) {
                int numPairs = 0;
                for (int k = 0; k < grid[0].length; k++) {
                    if (grid[i][k] == 1 && grid[j][k] == 1) {
                        numPairs++;
                    }
                }
                if (numPairs > 1) {
                    count += numPairs * (numPairs - 1) / 2;
                }
            }
        }
        return count;
    }
}

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

#medium
Задача: 751. IP to CIDR

Дан указатель на начало односвязного списка и два целых числа left и right, где left <= right. Необходимо перевернуть узлы списка, начиная с позиции left и заканчивая позицией right, и вернуть измененный список.

Пример:

Input: ip = "255.0.0.7", n = 10
Output: ["255.0.0.7/32","255.0.0.8/29","255.0.0.16/32"]

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

1⃣Преобразовать начальный IP-адрес в целое число.

2⃣Пока количество оставшихся IP-адресов n больше нуля: Определить наибольший блок, который начинается с текущего IP-адреса и не превышает количество оставшихся IP-адресов. Добавить этот блок к результату. Увеличить текущий IP-адрес на размер блока. Уменьшить количество оставшихся IP-адресов n.

3⃣Преобразовать блоки обратно в формат CIDR и вернуть их.

😎 Решение:

public class Solution {
    private int ipToInt(String ip) {
        String[] parts = ip.split("\\.");
        return (Integer.parseInt(parts[0]) << 24) + (Integer.parseInt(parts[1]) << 16) +
               (Integer.parseInt(parts[2]) << 8) + Integer.parseInt(parts[3]);
    }

    private String intToIp(int num) {
        return String.format("%d.%d.%d.%d", (num >> 24) & 255, (num >> 16) & 255, (num >> 8) & 255, num & 255);
    }

    private String cidr(String ip, int prefixLength) {
        return ip + "/" + prefixLength;
    }

    public List<String> findCidrBlocks(String startIp, int n) {
        int start = ipToInt(startIp);
        List<String> result = new ArrayList<>();
        
        while (n > 0) {
            int maxSize = 1;
            while (maxSize <= start && maxSize <= n) {
                maxSize <<= 1;
            }
            maxSize >>= 1;
            
            while (start % maxSize != 0) {
                maxSize >>= 1;
            }
            
            result.add(cidr(intToIp(start), 32 - Integer.bitCount(maxSize - 1) + 1));
            start += maxSize;
            n -= maxSize;
        }
        
        return result;
    }
}

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

#medium
Задача: 752. Open the Lock

Перед вами замок с 4 круглыми колесами. Каждое колесо имеет 10 слотов: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. Колеса могут свободно вращаться и оборачиваться: например, мы можем повернуть "9" так, чтобы получился "0", или "0" так, чтобы получился "9". Каждый ход состоит из поворота одного колеса на один слот. Изначально замок начинается с '0000', строки, представляющей состояние 4 колес. Вам дан список тупиков, то есть если замок отобразит любой из этих кодов, колеса замка перестанут вращаться, и вы не сможете его открыть. Учитывая цель, представляющую значение колес, которое позволит отпереть замок, верните минимальное общее количество оборотов, необходимое для открытия замка, или -1, если это невозможно.

Пример:

Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6

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

1⃣Используйте алгоритм BFS для поиска кратчайшего пути от начального состояния '0000' до целевого состояния, избегая тупиков. Инициализируйте очередь с начальным состоянием '0000' и начальным шагом 0. Используйте множество для отслеживания посещенных состояний, чтобы избежать повторного посещения одного и того же состояния.

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

3⃣Если очередь пуста и целевое состояние не найдено, верните -1.

😎 Решение:

import java.util.*;

public class Solution {
    public int openLock(String[] deadends, String target) {
        Set<String> dead = new HashSet<>(Arrays.asList(deadends));
        Queue<String> queue = new LinkedList<>();
        queue.offer("0000");
        Set<String> visited = new HashSet<>();
        visited.add("0000");
        int steps = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String node = queue.poll();
                if (node.equals(target)) {
                    return steps;
                }
                if (dead.contains(node)) {
                    continue;
                }
                for (String neighbor : neighbors(node)) {
                    if (!visited.contains(neighbor)) {
                        visited.add(neighbor);
                        queue.offer(neighbor);
                    }
                }
            }
            steps++;
        }
        return -1;
    }

    private List<String> neighbors(String node) {
        List<String> res = new ArrayList<>();
        char[] nodeArray = node.toCharArray();
        for (int i = 0; i < 4; i++) {
            char original = nodeArray[i];
            nodeArray[i] = original == '9' ? '0' : (char) (original + 1);
            res.add(new String(nodeArray));
            nodeArray[i] = original == '0' ? '9' : (char) (original - 1);
            res.add(new String(nodeArray));
            nodeArray[i] = original;
        }
        return res;
    }
}

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

#medium
Задача: 753. Cracking the Safe

Имеется сейф, защищенный паролем. Пароль представляет собой последовательность из n цифр, каждая из которых может находиться в диапазоне [0, k - 1]. Сейф имеет особый способ проверки пароля. Например, правильный пароль - "345", а вы вводите "012345": после ввода 0 последние 3 цифры - "0", что неверно. После ввода 1 последние 3 цифры - "01", что неверно. После ввода 2 последние 3 цифры - "012", что неверно.
После ввода 3 последние 3 цифры - "123", что неверно. После ввода 4 последние 3 цифры - "234", что неверно. После ввода 5 последние 3 цифры - "345", что верно, и сейф разблокируется. Верните любую строку минимальной длины, которая разблокирует сейф на определенном этапе ввода.

Пример:

Input: n = 1, k = 2
Output: "10"

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

1⃣Создайте граф, где каждая вершина представляет собой строку длины n-1, а каждое ребро между двумя вершинами представляет собой добавление одной из цифр из диапазона [0, k-1].

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

3⃣Составьте итоговую строку, которая включает начальную вершину и все добавленные цифры.

😎 Решение:

import java.util.HashSet;
import java.util.Set;

public class Solution {
    public String crackSafe(int n, int k) {
        Set<String> seen = new HashSet<>();
        StringBuilder result = new StringBuilder();

        String startNode = "0".repeat(n - 1);
        dfs(startNode, k, seen, result);

        result.append(startNode);
        return result.toString();
    }

    private void dfs(String node, int k, Set<String> seen, StringBuilder result) {
        for (int x = 0; x < k; x++) {
            String neighbor = node + x;
            if (!seen.contains(neighbor)) {
                seen.add(neighbor);
                dfs(neighbor.substring(1), k, seen, result);
                result.append(x);
            }
        }
    }
}

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

#medium
Задача: 754. Reach a Number

Вы стоите в позиции 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;
    }

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

#medium
Задача: 755. Pour Water

Вам дана карта высот, представленная в виде целочисленного массива heights, где heights[i] - высота местности в точке i. Ширина в каждой точке равна 1. Вам также даны два целых числа volume и k. Единицы объема воды будут падать в точке k. Вода сначала падает в точке k и упирается в самую высокую местность или воду в этой точке. Затем она течет по следующим правилам: если капля в конечном итоге упадет, двигаясь влево, то двигайтесь влево. Иначе, если капля в конечном итоге упадет, двигаясь вправо, то двигайтесь вправо. Иначе поднимайтесь в текущее положение. Здесь "в конечном итоге упадет" означает, что капля в конечном итоге окажется на более низком уровне, если она будет двигаться в этом направлении. Кроме того, уровень означает высоту местности плюс вода в этом столбе. Мы можем предположить, что на двух сторонах, выходящих за пределы массива, есть бесконечно высокая местность. Также не может быть частичного равномерного распределения воды более чем на один блок сетки, и каждая единица воды должна находиться ровно в одном блоке.

Пример:

Input: heights = [2,1,1,2,1,2,2], volume = 4, k = 3
Output: [2,2,2,3,2,2,2]

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

1⃣Инициализируйте цикл для добавления объема воды.

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

3⃣Повторите шаг 2, пока не будет добавлен весь объем воды.

😎 Решение:

public class Solution {
    public int[] pourWater(int[] heights, int volume, int k) {
        for (int v = 0; v < volume; v++) {
            int dropIndex = k;
            for (int d : new int[]{-1, 1}) {
                int i = k;
                while (i + d >= 0 && i + d < heights.length && heights[i + d] <= heights[i]) {
                    if (heights[i + d] < heights[i]) {
                        dropIndex = i + d;
                    }
                    i += d;
                }
                if (dropIndex != k) {
                    break;
                }
            }
            heights[dropIndex]++;
        }
        return heights;
    }

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

#medium
Задача: 714. Best Time to Buy and Sell Stock with Transaction Fee
Сложность: medium

Вам дан массив prices, где prices[i] - это цена данной акции в i-й день, и целое число fee, представляющее собой комиссию за сделку. Найдите максимальную прибыль, которую вы можете получить. Вы можете совершить сколько угодно сделок, но за каждую сделку вам придется заплатить комиссию. Примечание: Вы не можете совершать несколько сделок одновременно (то есть вы должны продать акции, прежде чем купить их снова). Комиссия за сделку взимается только один раз за каждую покупку и продажу акций.

Пример:

Input: prices = [1,3,2,8,4,9], fee = 2
Output: 8

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

1⃣Инициализируйте две переменные: cash, представляющую максимальную прибыль без наличия акций, и hold, представляющую максимальную прибыль с наличием акций.

2⃣Пройдите по каждому элементу массива prices и обновите значения cash и hold, используя текущую цену и комиссию.

3⃣Верните значение cash, которое будет максимальной прибылью без наличия акций.

😎 Решение:

public class Solution {
    public int maxProfit(int[] prices, int fee) {
        int cash = 0, hold = -prices[0];
        for (int price : prices) {
            cash = Math.max(cash, hold + price - fee);
            hold = Math.max(hold, cash - price);
        }
        return cash;
    }
}

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