#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;
    }
}

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