Java | LeetCode

Задача: 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 О рекламодателе

Задача: 213. House Robber II Сложность: medium Вы профессиональный грабитель, планирующий ограбить дома вдоль улицы. В каждом доме спрятано определенное количество денег. Все дома в этом месте расположены по кругу, что означает, что первый дом является соседом последнего. Между тем, в соседних домах установлена охранная система, которая автоматически свяжется с полицией, если два соседних дома будут взломаны в одну ночь. Дан массив целых чисел nums, представляющий количество денег в каждом доме, верните максимальную сумму денег, которую вы можете ограбить этой ночью, не вызвав полицию. Пример:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

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

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];

        int max1 = rob_simple(nums, 0, nums.length - 2);
        int max2 = rob_simple(nums, 1, nums.length - 1);

        return Math.max(max1, max2);
    }

    public int rob_simple(int[] nums, int start, int end) {
        int t1 = 0;
        int t2 = 0;

        for (int i = start; i <= end; i++) {
            int temp = t1;
            int current = nums[i];
            t1 = Math.max(current + t2, t1);
            t2 = temp;
        }

        return t1;
    }
}

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

📺 Уникальная база IT собеседований 456+ реальных собеседований на программиста, тестировщика, аналитика и прочие IT профы. Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д. 🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!

Задача: 1255. Maximum Score Words Formed by Letters Сложность: hard Даны список слов, список отдельных букв (могут повторяться) и оценка каждого символа. Верните максимальную оценку любого правильного набора слов, образованного с помощью заданных букв (words[i] не может быть использовано два или более раз). Не обязательно использовать все символы в буквах, каждая буква может быть использована только один раз. Оценка букв 'a', 'b', 'c', ... , 'z' задаются значениями score[0], score[1], ... , score[25] соответственно. Пример:

Input: words = ["dog","cat","dad","good"], letters = ["a","a","c","d","d","d","g","o","o"], score = [1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0]
Output: 23

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

import java.util.*;

public class Solution {
    public int maxScoreWords(String[] words, char[] letters, int[] score) {
        int maxScore = 0;
        Map<Character, Integer> letterCount = new HashMap<>();
        for (char ch : letters) {
            letterCount.put(ch, letterCount.getOrDefault(ch, 0) + 1);
        }

        for (int i = 1; i < (1 << words.length); i++) {
            int currScore = 0;
            Map<Character, Integer> usedLetters = new HashMap<>();
            boolean valid = true;
            for (int j = 0; j < words.length; j++) {
                if ((i & (1 << j)) != 0) {
                    for (char ch : words[j].toCharArray()) {
                        usedLetters.put(ch, usedLetters.getOrDefault(ch, 0) + 1);
                        if (usedLetters.get(ch) > letterCount.getOrDefault(ch, 0)) {
                            valid = false;
                            break;
                        }
                        currScore += score[ch - 'a'];
                    }
                }
                if (!valid) break;
            }
            if (valid) {
                maxScore = Math.max(maxScore, currScore);
            }
        }

        return maxScore;
    }
}

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