Java | LeetCode

Задача: 590. N-ary Tree Postorder Traversal Сложность: easy Дано корневое дерево с n-арной структурой, верните обход дерева в постфиксном порядке для значений его узлов. Сериализация входных данных n-арного дерева представлена в обходе уровней. Каждая группа детей разделяется значением null (см. примеры). Пример:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [2,6,14,11,7,3,12,8,4,13,9,10,5,1]

👨‍💻 Алгоритм: 1⃣Инициализируйте стек для хранения узлов и список для хранения значений узлов в обратном порядке. 2⃣Начните с корневого узла и добавьте его в стек. Пока стек не пуст, извлекайте узлы из стека, добавляя их значения в начало списка, и добавляйте всех его детей в стек. 3⃣В конце верните список значений узлов. 😎 Решение:

class Solution {
    public List<Integer> postorder(Node root) {
        LinkedList<Node> stack = new LinkedList<>();
        LinkedList<Integer> output = new LinkedList<>();
        if (root == null) {
            return output;
        }

        stack.add(root);
        while (!stack.isEmpty()) {
            Node node = stack.pollLast();
            output.addFirst(node.val);
            for (Node item : node.children) {
                if (item != null) {
                    stack.add(item);
                }
            }
        }
        return output;
    }
    class Node {
        public int val;
        public List<Node> children;

        public Node() {}

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    }
}

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

Задача: 1279. Traffic Light Controlled Intersection Сложность: easy Здесь есть пересечение двух дорог. Первая дорога - это дорога A, по которой автомобили движутся с севера на юг в направлении 1 и с юга на север в направлении 2. Вторая дорога - дорога B, по которой машины едут с запада на восток в направлении 3 и с востока на запад в направлении 4. На каждой дороге перед перекрестком есть светофор. Зеленый означает, что автомобили могут пересекать перекресток в обоих направлениях. Красный означает, что автомобили в обоих направлениях не могут пересекать перекресток и должны ждать, пока загорится зеленый свет. Светофор не может гореть зеленым одновременно на обеих дорогах. Это значит, что когда на дороге А горит зеленый свет, на дороге Б он красный, а когда на дороге Б горит зеленый свет, на дороге А он красный. Изначально на дороге A горит зеленый сигнал светофора, а на дороге B - красный. Когда на одной дороге горит зеленый свет, все автомобили могут пересекать перекресток в обоих направлениях, пока на другой дороге не загорится зеленый.Два автомобиля, движущиеся по разным дорогам, не должны пересекать перекресток одновременно. Разработайте систему управления светофором на этом перекрестке без тупиков. Реализуйте функцию void carArrived(carId, roadId, direction, turnGreen, crossCar), где: carId - идентификатор автомобиля, который приехал. roadId - идентификатор дороги, по которой едет автомобиль. direction - направление движения автомобиля. turnGreen - функция, которую можно вызвать, чтобы переключить светофор на зеленый свет на текущей дороге. crossCar - функция, которую можно вызвать, чтобы позволить текущему автомобилю пересечь перекресток. Ваш ответ считается правильным, если он позволяет избежать тупика на перекрестке.Переключение светофора на зеленый свет на дороге, где он уже был зеленым, считается неправильным ответом. Пример:

Input: cars = [1,2,3,4,5], directions = [2,4,3,3,1], arrivalTimes = [10,20,30,40,40]
Output: [
"Car 1 Has Passed Road A In Direction 2",    // Traffic light on road A is green, car 1 can cross the intersection.
"Traffic Light On Road B Is Green",          // Car 2 requests green light for road B.
"Car 2 Has Passed Road B In Direction 4",    // Car 2 crosses as the light is green on road B now.
"Car 3 Has Passed Road B In Direction 3",    // Car 3 crosses as the light is green on road B now.
"Traffic Light On Road A Is Green",          // Car 5 requests green light for road A.
"Car 5 Has Passed Road A In Direction 1",    // Car 5 crosses as the light is green on road A now.
"Traffic Light On Road B Is Green",          // Car 4 requests green light for road B. Car 4 blocked until car 5 crosses and then traffic light is green on road B.
"Car 4 Has Passed Road B In Direction 3"     // Car 4 crosses as the light is green on road B now.
]

👨‍💻 Алгоритм: 1⃣Если на дороге, по которой едет автомобиль, уже зеленый свет, вызываем функцию crossCar. 2⃣Если на дороге, по которой едет автомобиль, красный свет, вызываем функцию turnGreen, чтобы переключить свет на зеленый, и затем вызываем функцию crossCar. 3⃣Обеспечиваем, что функции turnGreen и crossCar вызываются атомарно для предотвращения гонок и тупиков. 😎 Решение:

import java.util.concurrent.locks.*;

public class TrafficLight {
    private int greenRoad = 1;
    private final Lock lock = new ReentrantLock();

    public void carArrived(
        int carId,
        int roadId,
        int direction,
        Runnable turnGreen,
        Runnable crossCar
    ) {
        lock.lock();
        try {
            if (greenRoad != roadId) {
                turnGreen.run();
                greenRoad = roadId;
            }
            crossCar.run();
        } finally {
            lock.unlock();
        }
    }
}

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

Задача: 568. Maximum Vacation Days Сложность: hard LeetCode хочет предоставить одному из своих лучших сотрудников возможность путешествовать по n городам для сбора задач по алгоритмам. Однако, как говорится, "делу время, потехе час". Вы можете брать отпуска в некоторых конкретных городах и неделях. Ваша задача — спланировать поездку, чтобы максимально увеличить количество дней отпуска, которые вы сможете взять, соблюдая при этом определенные правила и ограничения. Правила и ограничения: Вы можете путешествовать только между n городами, обозначенными индексами от 0 до n-1. Изначально вы находитесь в городе с индексом 0 в понедельник. Города связаны рейсами. Рейсы представлены матрицей n x n, называемой flights, представляющей статус авиалинии от города i до города j. Если рейса из города i в город j нет, flights[i][j] == 0; иначе flights[i][j] == 1. Также для всех i выполняется flights[i][i] == 0. У вас есть k недель (каждая неделя состоит из семи дней) для путешествий. Вы можете летать не более одного раза в день и можете летать только утром каждого понедельника. Время полета настолько короткое, что его влияние не учитывается. Для каждого города у вас есть ограниченные дни отпуска в разные недели, заданные матрицей n x k, называемой days. Значение days[i][j] представляет максимальное количество дней отпуска, которые вы можете взять в городе i на неделе j. Даны две матрицы flights и days, верните максимальное количество дней отпуска, которые вы можете взять в течение k недель. Пример:

Input: flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[6,0,3],[3,3,3]]
Output: 12
Explanation:
One of the best strategies is:
1st week : fly from city 0 to city 1 on Monday, and play 6 days and work 1 day.
(Although you start at city 0, we could also fly to and start at other cities since it is Monday.)
2nd week : fly from city 1 to city 2 on Monday, and play 3 days and work 4 days.
3rd week : stay at city 2, and play 3 days and work 4 days.
Ans = 6 + 3 + 3 = 12.

👨‍💻 Алгоритм: 1⃣Использовать функцию dfs (поиск в глубину), которая возвращает количество отпускных дней, которые можно взять, начиная с текущего города cur_city и текущей недели weekno. В каждом вызове функции проходить по всем городам и находить все города, которые связаны с текущим городом. Такой город обозначен 1 в соответствующей позиции flights[cur_city][i]. 2⃣Для текущего города можно либо остаться в нем, либо поехать в связанный город. Обозначим город, в который меняется расположение, как j. После смены города нужно найти количество отпускных дней, которые можно взять, начиная с нового города и с новой недели. Это количество отпускных дней можно представить как: days[j][weekno] + dfs(flights, days, j, weekno + 1). 3⃣Для текущего города необходимо найти максимальное количество отпускных дней, выбирая различные города в качестве следующего местоположения. Из всех вариантов отпускных дней выбираем максимальное значение, которое и будет возвращено для каждого вызова функции dfs. 😎 Решение:

public class Solution {
    public int maxVacationDays(int[][] flights, int[][] days) {
        int n = flights.length;
        int k = days[0].length;
        int[][] memo = new int[n][k];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return dfs(flights, days, memo, 0, 0);
    }
    private int dfs(int[][] flights, int[][] days, int[][] memo, int curCity, int weekNo) {
        int n = flights.length;
        int k = days[0].length;
        if (weekNo == k) return 0;
        if (memo[curCity][weekNo] != -1) return memo[curCity][weekNo];
        int maxVac = 0;
        for (int nextCity = 0; nextCity < n; nextCity++) {
            if (curCity == nextCity || flights[curCity][nextCity] == 1) {
                maxVac = Math.max(maxVac, days[nextCity][weekNo] + dfs(flights, days, memo, nextCity, weekNo + 1));
            }
        }
        memo[curCity][weekNo] = maxVac;
        return maxVac;
    }
}

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

Задача: 750. Number Of Corner Rectangles Сложность: medium Дан указатель на начало односвязного списка и два целых числа 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;
    }
}

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

Запустите рекламу в телеграм-каналах с Яндекс Директом Перфоманс-реклама теперь в телеграм-каналах ⚡ Яндекс Директ знает, как привлечь целевую аудиторию 💰👌 Попробовать

Задача: 474. Ones and Zeroes Сложность: medium Дан массив двоичных строк strs и два целых числа m и n. Верните размер наибольшего подмножества strs, такого что в подмножестве содержится не более m нулей и n единиц. Множество x является подмножеством множества y, если все элементы множества x также являются элементами множества y. Пример:

Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4
Explanation: The largest subset with at most 5 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4.
Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.
{"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3.

👨‍💻 Алгоритм: 1⃣Рассматриваем все возможные подмножества, прерывая цикл, если количество нулей превышает m или количество единиц превышает n. 2⃣Считаем количество нулей и единиц в каждом подмножестве. 3⃣Выбираем наибольшее подмножество, соответствующее условиям, и возвращаем его размер. 😎 Решение:

public class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int maxlen = 0;
        for (int i = 0; i < (1 << strs.length); i++) {
            int zeroes = 0, ones = 0, len = 0;
            for (int j = 0; j < 32; j++) {
                if ((i & (1 << j)) != 0) {
                    int[] count = countzeroesones(strs[j]);
                    zeroes += count[0];
                    ones += count[1];
                    if (zeroes > m || ones > n)
                        break;
                    len++;
                }
            }
            if (zeroes <= m && ones <= n)
                maxlen = Math.max(maxlen, len);
        }
        return maxlen;
    }

    public int[] countzeroesones(String s) {
        int[] c = new int[2];
        for (int i = 0; i < s.length(); i++) {
            c[s.charAt(i) - '0']++;
        }
        return c;
    }
}

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

Задача: 503. Next Greater Element II Сложность: medium Дан циклический массив целых чисел nums (т.е. следующий элемент после nums[nums.length - 1] это nums[0]), верните следующее большее число для каждого элемента в nums. Следующее большее число для числа x — это первое большее число, следующее за ним в порядке обхода массива, что означает, что вы можете искать циклически, чтобы найти следующее большее число. Если оно не существует, верните -1 для этого числа. Пример:

Input: nums = [1,2,1]
Output: [2,-1,2]
Explanation: The first 1's next greater number is 2; 
The number 2 can't find next greater number. 
The second 1's next greater number needs to search circularly, which is also 2.

👨‍💻 Алгоритм: 1⃣Инициализация Создайте массив res той же длины, что и nums, и заполните его значениями -1. 2⃣Поиск следующего большего элемента Для каждого элемента nums[i], используя индекс j, ищите следующий больший элемент среди следующих (циклически) n-1 элементов. Если найден больший элемент, обновите res[i] и прервите внутренний цикл. 3⃣Возврат результата Верните массив res. 😎 Решение:

 public class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int[] res = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            res[i] = -1;
            for (int j = 1; j < nums.length; j++) {
                if (nums[(i + j) % nums.length] > nums[i]) {
                    res[i] = nums[(i + j) % nums.length];
                    break;
                }
            }
        }
        return res;
    }
}

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

Онлайн-магистратура с IT специальностями от Яндекса Совместно с ИТМО, МИФИ, МФТИ. Онлайн-магистратура с актуальными программами и гибким графиком обучения. Получите высокооплачиваемую IT профессию, официальный диплом и практические знания. Господдержка оплаты. Совмещение с работой! Подать заявку #реклама 16+ practicum.yandex.ru О рекламодателе

Задача: 150. Evaluate Reverse Polish Notation Сложность: medium Вам дан массив строк под названием tokens, который представляет арифметическое выражение в обратной польской нотации. Вычислите это выражение. Верните целое число, которое представляет значение этого выражения. Обратите внимание на следующие моменты: Допустимые операторы: '+', '-', '*' и '/'. Каждый операнд может быть целым числом или другим выражением. Деление двух целых чисел всегда округляется к нулю. Деление на ноль в выражении отсутствует. Входные данные представляют собой действительное арифметическое выражение в обратной польской нотации. Ответ и все промежуточные вычисления можно представить 32-битным целым числом. Пример:

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

👨‍💻 Алгоритм: 1⃣Обработка входных массивов: Для языков, таких как Java, где входные данные представлены фиксированным массивом, необходимо определить собственные методы для манипулирования массивом (например, удаление элементов). Это может включать сдвиг элементов для заполнения пробелов после удаления элемента. В качестве альтернативы, копирование массива в ArrayList могло бы упростить удаление, но за счет увеличения сложности по памяти с O(1) до O(n). 2⃣Обработка типов и деление в Python: Необходимо быть внимательным при обработке типов в Python во время обработки списка, поскольку числа могут быть представлены как строки или целые числа. Кроме того, стандартное деление в Python не округляет к нулю. Вместо этого использование int(a / b) достигает желаемого результата округления, что отличается от деления нацело int(a // b), которое является другим распространенным подходом. 3⃣Использование лямбда-функций: Лямбда-функции могут упростить реализацию арифметических операций (таких как +, -, *, /). Если вы знакомы с лямбда-функциями, они предлагают элегантное решение для динамической обработки операций. Если лямбда-функции новы или не поддерживаются в используемом языке программирования, можно использовать другие методы, а изучение лямбда-функций можно отложить на потом. 😎 Решение:

class Solution {
    private static final Map<
        String,
        BiFunction<Integer, Integer, Integer>
    > OPERATIONS = new HashMap<>();

    static {
        OPERATIONS.put("+", (a, b) -> a + b);
        OPERATIONS.put("-", (a, b) -> a - b);
        OPERATIONS.put("*", (a, b) -> a * b);
        OPERATIONS.put("/", (a, b) -> a / b);
    }

    public int evalRPN(String[] tokens) {
        int currentPosition = 0;
        int length = tokens.length; // We need to keep track of this ourselves.

        while (length > 1) {

            while (!OPERATIONS.containsKey(tokens[currentPosition])) {
                currentPosition++;
            }

            String operation = tokens[currentPosition];
            int number1 = Integer.parseInt(tokens[currentPosition - 2]);
            int number2 = Integer.parseInt(tokens[currentPosition - 1]);

            BiFunction<Integer, Integer, Integer> operator = OPERATIONS.get(
                operation
            );
            int value = operator.apply(number1, number2);
            tokens[currentPosition] = Integer.toString(value);

            delete2AtIndex(tokens, currentPosition - 2, length);
            currentPosition--;
            length -= 2;
        }

        return Integer.parseInt(tokens[0]);
    }

    private void delete2AtIndex(String[] tokens, int d, int length) {
        for (int i = d; i < length - 2; i++) {
            tokens[i] = tokens[i + 2];
        }
    }
}

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

Задача: 1010. Pairs of Songs With Total Durations Divisible by 60 Сложность: medium Вам дан список песен, в котором длительность i-й песни составляет time[i] секунд. Верните количество пар песен, для которых их общая длительность в секундах делится на 60. Формально, нам нужно количество индексов i, j таких, что i < j при (time[i] + time[j]) % 60 == 0. Пример:

Input: time = [30,20,150,100,40]
Output: 3

👨‍💻 Алгоритм: 1⃣Инициализация и вычисление остатков: Создайте массив для хранения количества остатков от деления на 60. Инициализируйте его нулями. 2⃣Подсчет пар: Пройдитесь по каждой песне в списке и для каждого элемента: Вычислите остаток от деления времени песни на 60. Если остаток равен 0, добавьте количество песен с остатком 0 к результату (поскольку (0 + 0) % 60 == 0). Иначе, добавьте количество песен с остатком (60 - текущий остаток) к результату (поскольку (текущий остаток + (60 - текущий остаток)) % 60 == 0). Обновите массив остатков, увеличивая количество песен с текущим остатком на 1. 3⃣Возврат результата: Верните общее количество пар. 😎 Решение:

public class Solution {
    public int numPairsDivisibleBy60(int[] time) {
        int[] remainders = new int[60];
        int count = 0;
        
        for (int t : time) {
            if (t % 60 == 0) {
                count += remainders[0];
            } else {
                count += remainders[60 - t % 60];
            }
            remainders[t % 60]++;
        }
        
        return count;
    }
}

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

Новые диваны по цене 1 чашки кофе в день?! ⚡Вы не поверите, но реально возможно платить за диван цену 1 чашки кофе за рабочий день! 💰Такие низкие цены возможны только в Много Мебели. Как нам удаётся держать выгодные цены для вас: 1. Диваны напрямую с завода без дополнительных наценок; 2. Возможность рассрочки без переплат; 3. Промокод MMSALE для скидки до -3000 рублей! Давайте подсчитаем: средняя стоимость стаканчика кофе составляет 200 рублей, а рабочих дней в месяце 22. Выходит около 4 400 рублей в месяц за кофе. Приобретая диван по цене за 25 000 рублей в рассрочку, вы будете платить в месяц примерно 4 167 рублей То есть, новый диван обойдётся вам даже дешевле 1 чашки кофе в рабочий день! Выгодные покупки только в Много Мебели!✅ Посмотреть каталог #реклама mnogomebeli.com О рекламодателе

Задача: 465. Optimal Account Balancing Сложность: medium Дан массив транзакций transactions, где transactions[i] = [fromi, toi, amounti] указывает на то, что человек с ID = fromi дал сумму amounti долларов человеку с ID = toi. Верните минимальное количество транзакций, необходимых для урегулирования долгов. Пример:

Input: transactions = [[0,1,10],[2,0,5]]
Output: 2

👨‍💻 Алгоритм: 1⃣Создать хеш-таблицу для хранения чистого баланса каждого человека. 2⃣Собрать все ненулевые чистые балансы в массив balance_list. 3⃣Определить рекурсивную функцию dfs(cur) для очистки всех балансов в диапазоне balance_list[0 ~ cur]: Игнорировать cur, если баланс уже равен 0. Пока balance_list[cur] = 0, переходить к следующему человеку, увеличивая cur на 1. Если cur = n, вернуть 0. В противном случае установить cost на большое значение, например, inf. Пройтись по индексу nxt от cur + 1, если balance_list[nxt] * balance_list[cur] < 0, Добавить баланс balance_list[cur] к balance_list[nxt]: balance_list[nxt] += balance_list[cur]. Рекурсивно вызвать dfs(cur + 1) как dfs(cur) = 1 + dfs(cur + 1). Убрать ранее переданный баланс от cur: balance_list[nxt] -= balance_list[cur] (откат). Повторить с шага 5 и отслеживать минимальное количество операций cost = min(cost, 1 + dfs(cur + 1)), найденных в итерации. Вернуть cost, когда итерация завершена. Вернуть dfs(0). 😎 Решение:

import java.util.*;

public class Solution {
    private List<Integer> creditList;
    
    public int minTransfers(int[][] transactions) {
        Map<Integer, Integer> creditMap = new HashMap<>();
        for (int[] t : transactions) {
            creditMap.put(t[0], creditMap.getOrDefault(t[0], 0) + t[2]);
            creditMap.put(t[1], creditMap.getOrDefault(t[1], 0) - t[2]);
        }
        
        creditList = new ArrayList<>();
        for (int amount : creditMap.values()) {
            if (amount != 0) {
                creditList.add(amount);
            }
        }
        
        int n = creditList.size();
        return dfs(0, n);
    }
    
    private int dfs(int cur, int n) {
        while (cur < n && creditList.get(cur) == 0) {
            cur++;
        }
    
        if (cur == n) {
            return 0;
        }
        
        int cost = Integer.MAX_VALUE;
        for (int nxt = cur + 1; nxt < n; nxt++) {
            if (creditList.get(nxt) * creditList.get(cur) < 0) {
                creditList.set(nxt, creditList.get(nxt) + creditList.get(cur));
                cost = Math.min(cost, 1 + dfs(cur + 1, n));
                creditList.set(nxt, creditList.get(nxt) - creditList.get(cur));
            }
        }
        
        return cost;
    }
}

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

Задача: 760. Find Anagram Mappings Сложность: easy Вам даны два целочисленных массива nums1 и nums2, где nums2 - анаграмма nums1. Оба массива могут содержать дубликаты. Верните индексное отображение массива mapping из nums1 в nums2, где mapping[i] = j означает, что i-й элемент в nums1 появляется в nums2 по индексу j. Если ответов несколько, верните любой из них. Массив a является анаграммой массива b означает, что b создается путем случайного изменения порядка элементов в a. Пример:

Input: nums1 = [12,28,46,32,50], nums2 = [50,12,32,46,28]
Output: [1,4,3,2,0]

👨‍💻 Алгоритм: 1⃣Создайте словарь для хранения индексов элементов в nums2. 2⃣Пройдите по элементам массива nums1 и для каждого элемента найдите соответствующий индекс в nums2, используя словарь. 3⃣Верните массив индексов. 😎 Решение:

import java.util.*;

public class Solution {
    public int[] anagramMapping(int[] nums1, int[] nums2) {
        Map<Integer, List<Integer>> indexMap = new HashMap<>();
        for (int i = 0; i < nums2.length; i++) {
            indexMap.computeIfAbsent(nums2[i], k -> new ArrayList<>()).add(i);
        }
        
        int[] mapping = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            mapping[i] = indexMap.get(nums1[i]).remove(indexMap.get(nums1[i]).size() - 1);
        }
        
        return mapping;
    }

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

Задача: 1260. Shift 2D Grid Сложность: easy Дана двумерная сетка размером m x n и целое число k. Требуется сдвинуть сетку k раз. За одну операцию сдвига: элемент в grid[i][j] перемещается в grid[i][j + 1]. Элемент в grid[i][n - 1] перемещается в grid[i + 1][0]. Элемент в grid[m - 1][n - 1] перемещается в grid[0][0]. Верните двумерную сетку после применения операции сдвига k раз. Пример:

Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
Output: [[9,1,2],[3,4,5],[6,7,8]]

👨‍💻 Алгоритм: 1⃣Преобразовать двумерную сетку в одномерный массив. 2⃣Выполнить сдвиг элементов в одномерном массиве. 3⃣Преобразовать одномерный массив обратно в двумерную сетку. 😎 Решение:

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

public class Solution {
    public List<List<Integer>> shiftGrid(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length;
        int total = m * n;
        k %= total;

        if (k == 0) {
            List<List<Integer>> result = new ArrayList<>();
            for (int[] row : grid) {
                List<Integer> newRow = new ArrayList<>();
                for (int val : row) {
                    newRow.add(val);
                }
                result.add(newRow);
            }
            return result;
        }

        int[] flatArray = new int[total];
        for (int i = 0; i < total; i++) {
            flatArray[i] = grid[i / n][i % n];
        }
        
        int[] newArray = new int[total];
        for (int i = 0; i < total; i++) {
            newArray[(i + k) % total] = flatArray[i];
        }

        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            List<Integer> newRow = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                newRow.add(newArray[i * n + j]);
            }
            result.add(newRow);
        }
        
        return result;
    }
}

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

Задача: 1230. Toss Strange Coins Сложность: medium У вас есть несколько монет. Вероятность выпадения орла для i-й монеты равна prob[i]. Верните вероятность того, что количество монет, на которых выпал орел, равно target, если вы подбросите каждую монету ровно один раз. Пример:

Input: prob = [0.5,0.5,0.5,0.5,0.5], target = 0
Output: 0.03125

👨‍💻 Алгоритм: 1⃣Инициализация: Создайте переменную n и инициализируйте её размером массива prob. Создайте 2D массив dp размером n + 1 строк и target + 1 столбцов, где dp[i][j] хранит вероятность получить j орлов, используя первые i монет. Установите базовый случай dp[0][0] = 1. 2⃣Итерация: Используйте два вложенных цикла для заполнения массива dp. Внешний цикл итерируется от i = 1 до n. Для каждого i установите dp[i][0], что обозначает вероятность получить 0 орлов при использовании i монет: dp[i][0] = dp[i - 1][0] * (1 - prob[i - 1]). Внутренний цикл итерируется от j = 1 до target. Для каждого j вычислите dp[i][j] по формуле: dp[i][j] = dp[i - 1][j - 1] * prob[i - 1] + dp[i - 1][j] * (1 - prob[i - 1]). 3⃣Возврат результата: Верните значение dp[n][target], которое содержит искомую вероятность. 😎 Решение:

class Solution {
    public double probabilityOfHeads(double[] prob, int target) {
        int n = prob.length;
        double[][] dp = new double[n + 1][target + 1];
        dp[0][0] = 1;

        for (int i = 1; i <= n; i++) {
            dp[i][0] = dp[i - 1][0] * (1 - prob[i - 1]);
            for (int j = 1; j <= target && j <= i; j++) {
                dp[i][j] = dp[i - 1][j - 1] * prob[i - 1] + dp[i - 1][j] * (1 - prob[i - 1]);
            }
        }

        return dp[n][target];
    }
}

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

Дарим подписку на Яндекс Музыку Ответьте на 1 вопрос и Яндекс Музыка ваша для вас и 3-х ваших близких. Кинопоиск и Яндекс Книги тоже в подписке. Попробуйте бесплатно❤️ Попробовать #реклама 18+ music.yandex.ru О рекламодателе Реклама на Яндексе

Задача: 1196. How Many Apples Can You Put into the Basket Сложность: easy У вас есть несколько яблок и корзина, которая может выдержать до 5000 единиц веса. Дан целочисленный массив weight, где weight[i] — это вес i-го яблока. Верните максимальное количество яблок, которые можно положить в корзину. Пример:

Input: weight = [100,200,150,1000]
Output: 4
Explanation: All 4 apples can be carried by the basket since their sum of weights is 1450.

👨‍💻 Алгоритм: 1⃣Преобразование массива в мин-кучу: Преобразуйте массив weight в мин-кучу, чтобы получить минимальные элементы первым. 2⃣Инициализация переменных: Инициализируйте переменные apples для подсчета количества яблок и units для записи текущего веса корзины. 3⃣Добавление яблок в корзину: Пока текущий вес корзины меньше 5000 единиц и в куче остаются элементы: Увеличивайте apples на 1. Увеличивайте units на значение, извлеченное из кучи. 😎 Решение:

class Solution {
    public int maxNumberOfApples(int[] arr) {
        List<Integer> list = Arrays.stream(arr).boxed().collect(Collectors.toList());
        Queue<Integer> heap = new PriorityQueue<>(list);

        int apples = 0, units = 0;

        while (!heap.isEmpty() && units + heap.peek() <= 5000) {
            units += heap.remove();
            apples += 1;
        }
        return apples;
    }
}

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

Реклама для бизнеса любого уровня в Яндекс Директе Создайте эффективную рекламную кампанию с алгоритмами Яндекс Директа 👌 Начните прямо сейчас ⚡ Зарегистрироваться #реклама direct.yandex.ru О рекламодателе

Задача: 1052. Grumpy Bookstore Owner Сложность: medium Есть владелец книжного магазина, магазин которого открыт в течение n минут. Каждую минуту в магазин заходит некоторое количество покупателей. Вам дан целочисленный массив customers длины n, где customers[i] - это номер покупателя, который заходит в магазин в начале i-й минуты, а все покупатели выходят после окончания этой минуты. В некоторые минуты владелец книжного магазина ворчлив. Вам дан двоичный массив grumpy, в котором grumpy[i] равен 1, если владелец книжного магазина ворчлив в течение i-й минуты, и равен 0 в противном случае. Когда владелец книжного магазина ворчлив, покупатели в эту минуту не удовлетворены, в противном случае они удовлетворены. Владелец книжного магазина знает секретную технику, чтобы не ворчать в течение нескольких минут подряд, но может использовать ее только один раз. Верните максимальное количество покупателей, которое может быть удовлетворено в течение дня. Пример:

Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3
Output: 16

👨‍💻 Алгоритм: 1⃣Определи общее количество покупателей, которые удовлетворены в минуты, когда владелец магазина не ворчлив. 2⃣Пройди по массиву, используя скользящее окно для учета эффекта от техники. 3⃣Найди максимальное количество дополнительных удовлетворенных покупателей, которые можно получить, используя технику на k минут подряд. 😎 Решение:

public class Solution {
    public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
        int totalSatisfied = 0;
        int additionalSatisfied = 0;
        int maxAdditionalSatisfied = 0;
        
        for (int i = 0; i < customers.length; i++) {
            if (grumpy[i] == 0) {
                totalSatisfied += customers[i];
            } else {
                additionalSatisfied += customers[i];
            }
            
            if (i >= minutes) {
                if (grumpy[i - minutes] == 1) {
                    additionalSatisfied -= customers[i - minutes];
                }
            }
            
            maxAdditionalSatisfied = Math.max(maxAdditionalSatisfied, additionalSatisfied);
        }
        
        return totalSatisfied + maxAdditionalSatisfied;
    }
}

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

AI VK & Pro — камерный ивент о RecSys Привет, на связи VK! 27 августа мы собираем крутых ML-инженеров, исследователей и разработчиков. Адженда тусовки — развитие и будущее ML-систем, которые двигают контент в продуктах VK. Основная часть — доклады от ML-лидов VK. А дальше — афтепати: ответы на вопросы, нетворкинг, покер, сигары, винил и вино. Офлайн, без трансляций и галстуков. Москва 📅 27 августа Участие бесплатное, по регистрации Подать заявку #реклама 16+ team.vk.company О рекламодателе