Java | LeetCode

#medium Задача: 379. Design Phone Directory Создайте телефонный справочник, который изначально имеет maxNumbers пустых слотов для хранения номеров. Справочник должен хранить номера, проверять, пуст ли определенный слот, и освобождать данный слот. Реализуйте класс PhoneDirectory: PhoneDirectory(int maxNumbers) Инициализирует телефонный справочник с количеством доступных слотов maxNumbers. int get() Предоставляет номер, который никому не назначен. Возвращает -1, если номера недоступны. bool check(int number) Возвращает true, если слот доступен, и false в противном случае. void release(int number) Перераспределяет или освобождает номер слота. Пример:

Input
["PhoneDirectory", "get", "get", "check", "get", "check", "release", "check"]
[[3], [], [], [2], [], [2], [2], [2]]
Output
[null, 0, 1, true, 2, false, null, true]

👨‍💻 Алгоритм: 1⃣Инициализировать массив isSlotAvailable размером maxNumbers, установив значение true во всех индексах. 2⃣Метод get(): Проходить по массиву isSlotAvailable. Если найдется true на каком-либо индексе, установить isSlotAvailable[i] = false и вернуть i. Если доступных слотов нет, вернуть -1. Метод check(number): Вернуть значение isSlotAvailable[number]. 3⃣Метод release(number): Установить isSlotAvailable[number] = true. 😎 Решение:

public class PhoneDirectory {
    private boolean[] isSlotAvailable;

    public PhoneDirectory(int maxNumbers) {
        isSlotAvailable = new boolean[maxNumbers];
        for (int i = 0; i < maxNumbers; i++) {
            isSlotAvailable[i] = true;
        }
    }

    public int get() {
        for (int i = 0; i < isSlotAvailable.length; i++) {
            if (isSlotAvailable[i]) {
                isSlotAvailable[i] = false;
                return i;
            }
        }
        return -1;
    }

    public boolean check(int number) {
        return isSlotAvailable[number];
    }

    public void release(int number) {
        isSlotAvailable[number] = true;
    }
}

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

#medium Задача: 235. Lowest Common Ancestor of a Binary Search Tree Дано бинарное дерево поиска (BST). Найдите наименьший общий предок (LCA) двух заданных узлов в BST. Согласно определению LCA на Википедии: "Наименьший общий предок определяется между двумя узлами p и q как наименьший узел в дереве T, который имеет как p, так и q в качестве потомков (где мы допускаем, что узел может быть потомком самого себя)." Пример:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

👨‍💻 Алгоритм: 1⃣Начало обхода дерева с корня: Начните обход дерева с корневого узла. Проверьте, находятся ли узлы p и q в правом или левом поддереве текущего узла. 2⃣Продолжение поиска в поддереве: Если оба узла p и q находятся в правом поддереве текущего узла, продолжайте поиск в правом поддереве, начиная с шага 1. Если оба узла p и q находятся в левом поддереве текущего узла, продолжайте поиск в левом поддереве, начиная с шага 1. 3⃣Нахождение LCA: Если узлы p и q находятся в разных поддеревьях относительно текущего узла или один из узлов равен текущему узлу, то текущий узел является наименьшим общим предком (LCA). Верните этот узел как результат. 😎 Решение:

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        int parentVal = root.val;
        int pVal = p.val;
        int qVal = q.val;

        if (pVal > parentVal && qVal > parentVal) {
            return lowestCommonAncestor(root.right, p, q);
        } else if (pVal < parentVal && qVal < parentVal) {
            return lowestCommonAncestor(root.left, p, q);
        } else {
            return root;
        }
    }
}

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

Хотите создавать приложения для миллионов пользователей, но пугают базы данных, JDBC и Hibernate? Если вы пишете на Java, то рано или поздно столкнетесь с задачей хранения данных: профили пользователей, каталоги товаров или финансы. Можно, конечно, нагромоздить код для прямой работы с базой, но в какой-то момент обычный SQL просто перестанет справляться. Вместо ручного написания сложного SQL-кода используйте Hibernate. Он берёт на себя всю рутину и делает работу с данными проще и удобнее. Чтобы разобраться с принципами работы фреймворка, приходите на вебинар от FAANG School: – зачем нужен и как применять Hibernate в своих Java-проектах – как создавать связи между Java-объектами и таблицами в базе данных – лучшие практики Hibernate для создания топ-приложений – как просто работать со связями one-to-one, one-to-many и many-to-many и многое другое Занимайте место и уже после вебинара сможете забрать пару фич к себе в проект!

#medium Задача: 378. Kth Smallest Element in a Sorted Matrix Дана матрица размером n x n, где каждая строка и каждый столбец отсортированы в порядке возрастания. Верните k-й наименьший элемент в матрице. Заметьте, что это k-й наименьший элемент в отсортированном порядке, а не k-й уникальный элемент. Вы должны найти решение с использованием памяти лучше, чем O(n²). Пример:

Input: matrix = [[-5]], k = 1
Output: -5

👨‍💻 Алгоритм: 1⃣Инициализировать мин-кучу H. В нашем решении мы будем рассматривать каждую строку как отдельный список. Поскольку столбцы также отсортированы, мы можем рассматривать каждый столбец как отдельный список. 2⃣Взять первые элементы из min(N, K) строк, где N представляет количество строк, и добавить каждый из этих элементов в кучу. Важно знать, к какой строке и столбцу принадлежит элемент, чтобы в дальнейшем перемещаться по соответствующему списку. 3⃣Мин-куча будет содержать тройки информации (значение, строка, столбец). Куча будет упорядочена по значениям, и мы будем использовать номера строк и столбцов для добавления следующего элемента, если текущий элемент будет удален из кучи. 😎 Решение:

import java.util.Comparator;
import java.util.PriorityQueue;

class MyHeapNode {
    int row;
    int column;
    int value;

    public MyHeapNode(int v, int r, int c) {
        this.value = v;
        this.row = r;
        this.column = c;
    }

    public int getValue() {
        return this.value;
    }

    public int getRow() {
        return this.row;
    }

    public int getColumn() {
        return this.column;
    }
}

class MyHeapComparator implements Comparator<MyHeapNode> {
    public int compare(MyHeapNode x, MyHeapNode y) {
        return x.value - y.value;
    }
}

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int N = matrix.length;

        PriorityQueue<MyHeapNode> minHeap = new PriorityQueue<>(Math.min(N, k), new MyHeapComparator());

        for (int r = 0; r < Math.min(N, k); r++) {
            minHeap.offer(new MyHeapNode(matrix[r][0], r, 0));
        }

        MyHeapNode element = minHeap.peek();
        while (k-- > 0) {
            element = minHeap.poll();
            int r = element.getRow(), c = element.getColumn();

            if (c < N - 1) {
                minHeap.offer(new MyHeapNode(matrix[r][c + 1], r, c + 1));
            }
        }

        return element.getValue();
    }
}

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

#medium Задача: 378. Kth Smallest Element in a Sorted Matrix Дана матрица размером n x n, где каждая строка и каждый столбец отсортированы в порядке возрастания. Верните k-й наименьший элемент в матрице. Заметьте, что это k-й наименьший элемент в отсортированном порядке, а не k-й уникальный элемент. Вы должны найти решение с использованием памяти лучше, чем O(n²). Пример:

Input: matrix = [[-5]], k = 1
Output: -5

👨‍💻 Алгоритм: 1⃣Инициализировать мин-кучу H. В нашем решении мы будем рассматривать каждую строку как отдельный список. Поскольку столбцы также отсортированы, мы можем рассматривать каждый столбец как отдельный список. 2⃣Взять первые элементы из min(N, K) строк, где N представляет количество строк, и добавить каждый из этих элементов в кучу. Важно знать, к какой строке и столбцу принадлежит элемент, чтобы в дальнейшем перемещаться по соответствующему списку. 3⃣Мин-куча будет содержать тройки информации (значение, строка, столбец). Куча будет упорядочена по значениям, и мы будем использовать номера строк и столбцов для добавления следующего элемента, если текущий элемент будет удален из кучи. 😎 Решение:

class MyHeapNode {

  int row;
  int column;
  int value;

  public MyHeapNode(int v, int r, int c) {
    this.value = v;
    this.row = r;
    this.column = c;
  }

  public int getValue() {
    return this.value;
  }

  public int getRow() {
    return this.row;
  }

  public int getColumn() {
    return this.column;
  }
}

class MyHeapComparator implements Comparator<MyHeapNode> {
  public int compare(MyHeapNode x, MyHeapNode y) {
    return x.value - y.value;
  }
}

class Solution {

  public int kthSmallest(int[][] matrix, int k) {

    int N = matrix.length;

    PriorityQueue<MyHeapNode> minHeap =
        new PriorityQueue<MyHeapNode>(Math.min(N, k), new MyHeapComparator());

    // Preparing our min-heap
    for (int r = 0; r < Math.min(N, k); r++) {

      // We add triplets of information for each cell
      minHeap.offer(new MyHeapNode(matrix[r][0], r, 0));
    }

    MyHeapNode element = minHeap.peek();
    while (k-- > 0) {

      // Extract-Min
      element = minHeap.poll();
      int r = element.getRow(), c = element.getColumn();

      // If we have any new elements in the current row, add them
      if (c < N - 1) {

        minHeap.offer(new MyHeapNode(matrix[r][c + 1], r, c + 1));
      }
    }

    return element.getValue();
  }
}

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

Твое резюме на HeadHunter — ОК, если ты видишь это. HeadHunter сравнивает ключевые навыки в твоем резюме и в вакансии и в момент отклика отображает, насколько % ты соответствуешь требованиям. Специальный бейджик «Подходит по навыкам на 100%» отображается, если соответствие составляет более 60%. Если при просмотре вакансий ты видишь такой бейджик, это значит, что список навыков в твоем резюме качественно составлен. Это важный параметр, так как рекрутерам чаще показываются резюме с лучшим соответствием. О том, как правильно указывать ключевые навыки и оптимизировать свое резюме я уже рассказывал в этом видео

Станьте Java-разработчиком с нуля без оплаты за обучение и получите работу с зарплатой 140 000+ Образовательный проект EdMe начинает набор на курс Java-разработки для начинающих. Программа основана на менторстве и подходит для начинающих программистов и тех, кто хочет освоить Java с нуля. От вас нужно лишь желание учиться и готовность уделять от 15 часов в неделю на занятия. 🔹 Получение профессии: 6 месяцев до зарплаты от 140.000 руб. 🔹 Гарантия трудоустройства: 98,9% выпускников получают оффер за 34 дня. 🔹 Оплата после трудоустройства: 20% от зарплаты в течение 18 месяцев. 🔹 После обучения 86% выпускников выбирают работу онлайн. Обучение проходит онлайн: 40% самостоятельная работа, 30% — взаимодействие с ментором, 30% — в группе. Такой подход развивает быстрее обычных курсов, ментор проведёт вас по короткому пути. Он объяснит, что нужно учить и как это делать, а также чего не делать, чтобы быстрее освоить нужные навыки и достичь заветной цели – получить оффер в IT. Программа курса: ▫️ Java Core, List, JDBC, Hibernate, Spring (Core, MVC, Security), Spring Boot, Git ▫️ Работа над проектами ▫️ Подготовка к собеседованиям 🗓 Старт обучения: ноябрь 2024. Чтобы начать учиться нужно оставить заявку на сайте EdMe. Отбор включает несложное тестовое задание, которое под силу выполнить человеку без опыта, и собеседование.

#hard Задача: 472. Concatenated Words Дан массив строк words (без дубликатов). Верните все составные слова из данного списка слов. Составное слово определяется как строка, которая полностью состоит как минимум из двух более коротких слов (не обязательно различных) из данного массива. Пример:

Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]
Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats"; 
"dogcatsdog" can be concatenated by "dog", "cats" and "dog"; 
"ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".

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

import java.util.*;

public class Solution {
    private boolean dfs(String word, int length, boolean[] visited, Set<String> dictionary) {
        if (length == word.length()) {
            return true;
        }
        if (visited[length]) {
            return false;
        }
        visited[length] = true;
        for (int i = word.length() - (length == 0 ? 1 : 0); i > length; --i) {
            if (dictionary.contains(word.substring(length, i)) && dfs(word, i, visited, dictionary)) {
                return true;
            }
        }
        return false;
    }

    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        Set<String> dictionary = new HashSet<>(Arrays.asList(words));
        List<String> answer = new ArrayList<>();
        for (String word : words) {
            boolean[] visited = new boolean[word.length()];
            if (dfs(word, 0, visited, dictionary)) {
                answer.add(word);
            }
        }
        return answer;
    }
}

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

#medium Задача: 470. Implement Rand10() Using Rand7() Дано API rand7(), которое генерирует случайное целое число в диапазоне [1, 7]. Напишите функцию rand10(), которая генерирует случайное целое число в диапазоне [1, 10]. Вы можете вызывать только API rand7(), и не должны вызывать другие API. Пожалуйста, не используйте встроенные в язык функции для генерации случайных чисел. Каждый тестовый случай будет содержать один внутренний аргумент n, который указывает количество вызовов вашей реализованной функции rand10() во время тестирования. Обратите внимание, что это не аргумент, передаваемый в rand10(). Пример:

Input: n = 1
Output: [2]

😎 Решение:

class Solution {
    public int rand10() {
        int row, col, idx;
        do {
            row = rand7();
            col = rand7();
            idx = col + (row - 1) * 7;
        } while (idx > 40);
        return 1 + (idx - 1) % 10;
    }
}

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

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

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

👨‍💻 Алгоритм: 1⃣ Инициализация массива: Создайте массив ans длиной n + 1, заполненный нулями. Этот массив будет содержать количество единиц в двоичном представлении каждого числа от 0 до n. 2⃣ Итерация и вычисление: Пройдите в цикле по всем числам от 1 до n. Для каждого числа x используйте битовую операцию x & (x - 1), чтобы убрать последнюю установленную биту, и добавьте 1 к значению ans для этого результата. Это количество единиц в двоичном представлении числа x. 3⃣ Возврат результата: Верните заполненный массив ans, который содержит количество единиц для каждого числа от 0 до n. 😎 Решение:

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

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

#medium Задача: 468. Validate IP Address Допустимый IPv4-адрес — это IP в форме "x1.x2.x3.x4", где 0 <= xi <= 255 и xi не может содержать ведущие нули. Например, "192.168.1.1" и "192.168.1.0" являются допустимыми IPv4-адресами, тогда как "192.168.01.1", "192.168.1.00" и "192.168@1.1" являются недопустимыми IPv4-адресами. Допустимый IPv6-адрес — это IP в форме "x1:x2:x3:x4:x5:x6:x7 ", где: 1 <= xi.length <= 4 xi — это шестнадцатеричная строка, которая может содержать цифры, строчные английские буквы ('a' до 'f') и прописные английские буквы ('A' до 'F'). Ведущие нули в xi допускаются. Пример:

Input: queryIP = "172.16.254.1"
Output: "IPv4"
Explanation: This is a valid IPv4 address, return "IPv4".

👨‍💻 Алгоритм: 1⃣Для проверки адреса IPv4: Разделить IP на четыре части по разделителю ".". Проверить каждую подстроку: Является ли она целым числом между 0 и 255. Не содержит ли она ведущих нулей (исключение — число "0"). 2⃣Для проверки адреса IPv6: Разделить IP на восемь частей по разделителю ":". Проверить каждую подстроку: Является ли она шестнадцатеричным числом длиной от 1 до 4 символов. 3⃣Если IP не соответствует ни одному из форматов, вернуть "Neither". 😎 Решение:

class Solution {
    public String validateIPv4(String IP) {
        String[] nums = IP.split("\\.", -1);
        for (String x : nums) {
            if (x.length() == 0 || x.length() > 3) return "Neither";
            if (x.charAt(0) == '0' && x.length() != 1) return "Neither";
            for (char ch : x.toCharArray()) {
                if (!Character.isDigit(ch)) return "Neither";
            }
            if (Integer.parseInt(x) > 255) return "Neither";
        }
        return "IPv4";
    }

    public String validateIPv6(String IP) {
        String[] nums = IP.split(":", -1);
        String hexdigits = "0123456789abcdefABCDEF";
        for (String x : nums) {
            if (x.length() == 0 || x.length() > 4) return "Neither";
            for (char ch : x.toCharArray()) {
                if (hexdigits.indexOf(ch) == -1) return "Neither";
            }
        }
        return "IPv6";
    }

    public String validIPAddress(String IP) {
        if (IP.chars().filter(ch -> ch == '.').count() == 3) {
            return validateIPv4(IP);
        } else if (IP.chars().filter(ch -> ch == ':').count() == 7) {
            return validateIPv6(IP);
        } else {
            return "Neither";
        }
    }
}

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

Бесплатное IT-образование в 2024 Отобрали для вас полезные телеграм-каналы, которые помогут освоить программирование и другие IT-направления Выбирайте нужное и подписывайтесь: 👩‍💻 Python: @PythonPortal 📱 GitHub: @git_developer 👩‍💻 Frontend: @FrontendPortal 🤓 Книги айти: @portalToIT 👩‍💻 Java: @Java_Iibrary 👩‍💻 C#: @KodBlog 👩‍💻 С/С++: @Cpportal ⚙️ Backend: @BackendPortal 🐞 Тестирование: @QAPortal 👩‍💻 DevOps: @loose_code 🖥 Базы Данных & SQL: @SQL 👩‍💻 Golang: @juniorGolang 👩‍💻 PHP: @PHPortal 👩‍💻 Моб. разработка: @MobDev 👩‍💻 Разработка игр: @GameDevgx 🖥 Data Science: @DataSciencegx 🤔 Хакинг & ИБ: @cybersecinform 📱 Маркетинг: @MarketingPortal 🖥 Дизайн: @PortalToDesign ➡️ Сохраняйте себе, чтобы не потерять

#medium Задача: 337. House Robber III Вор снова нашел себе новое место для краж. В этом районе есть только один вход, который называется корнем. Кроме корня, каждый дом имеет только один родительский дом. После осмотра, умный вор понял, что все дома в этом месте образуют бинарное дерево. Полиция будет автоматически уведомлена, если два дома, напрямую связанные между собой, будут ограблены в одну ночь. Дано корневое дерево бинарного дерева, верните максимальную сумму денег, которую вор может украсть, не уведомляя полицию. Пример:

Input: root = [3,4,5,1,3,null,1]
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

👨‍💻 Алгоритм: 1⃣Инициализация и базовый случай: Создайте вспомогательную функцию helper, которая принимает узел в качестве входных данных и возвращает массив из двух элементов, где первый элемент представляет максимальную сумму денег, которую можно украсть, если не грабить этот узел, а второй элемент - если грабить этот узел. Базовый случай для вспомогательной функции - узел null, и в этом случае функция возвращает массив из двух нулей [0, 0]. 2⃣Рекурсивное исследование дерева: В функции helper вызывайте её рекурсивно для левого и правого поддеревьев текущего узла. Если грабить текущий узел, то нельзя грабить его потомков, поэтому сумма будет равна значению текущего узла плюс максимальные суммы для случаев, когда потомки не грабятся. Если не грабить текущий узел, то можно свободно выбирать, грабить потомков или нет, поэтому сумма будет равна максимальной сумме из двух вариантов для каждого потомка. 3⃣Возврат результата: В основной функции rob вызовите helper для корня дерева и верните максимальное значение из двух элементов массива, возвращенного функцией helper. 😎 Решение:

class Solution {
    public int[] helper(TreeNode node) {
        if (node == null) {
            return new int[] { 0, 0 };
        }
        int left[] = helper(node.left);
        int right[] = helper(node.right);
        int rob = node.val + left[1] + right[1];
        int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);

        return new int[] { rob, notRob };
    }

    public int rob(TreeNode root) {
        int[] answer = helper(root);
        return Math.max(answer[0], answer[1]);
    }
}

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

#medium Задача: 465. Optimal Account Balancing Дан массив транзакций 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;
    }
}

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

Курс по Java: с нуля до middle за 6 месяцев с гарантией трудоустройства Образовательный проект EdMe начинает набор на курс Java-разработки для начинающих. Программа основана на менторстве и подходит для начинающих программистов и тех, кто хочет освоить Java с нуля. От вас нужно лишь желание учиться и готовность уделять от 15 часов в неделю на занятия. 🔹 Получение профессии: 6 месяцев до зарплаты от 140.000 руб. 🔹 Гарантия трудоустройства: 98,9% выпускников получают оффер за 34 дня. 🔹 Оплата после трудоустройства: 20% от зарплаты в течение 18 месяцев. 🔹 После обучения 86% выпускников выбирают работу онлайн. Обучение проходит онлайн: 40% самостоятельная работа, 30% — взаимодействие с ментором, 30% — в группе. Такой подход развивает быстрее обычных курсов, ментор проведёт вас по короткому пути. Он объяснит, что нужно учить и как это делать, а также чего не делать, чтобы быстрее освоить нужные навыки и достичь заветной цели – получить оффер в IT. Программа курса: ▫️ Java Core, List, JDBC, Hibernate, Spring (Core, MVC, Security), Spring Boot, Git ▫️ Работа над проектами ▫️ Подготовка к собеседованиям 🗓 Старт обучения: ноябрь 2024. Чтобы начать учиться нужно оставить заявку на сайте EdMe. Отбор включает несложное тестовое задание, которое под силу выполнить человеку без опыта, и собеседование.

#hard Задача: 336. Palindrome Pairs Вам дан массив уникальных строк words, индексируемый с 0. Пара палиндромов — это пара целых чисел (i, j), таких что: 0 <= i, j < words.length, i != j, и words[i] + words[j] (конкатенация двух строк) является палиндромом. Верните массив всех пар палиндромов из слов. Вы должны написать алгоритм с временной сложностью O(сумма длин всех слов в words). Пример:

Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["abcddcba","dcbaabcd","slls","llssssll"]

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

class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {

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

        for (int i = 0; i < words.length; i++) {
            for (int j = 0; j < words.length; j++) {
                if (i == j) continue;
                String combined = words[i].concat(words[j]);
                String reversed = new StringBuilder(combined).reverse().toString();
                if (combined.equals(reversed)) {
                    pairs.add(Arrays.asList(i, j));
                }
            }   
        }

        return pairs;
    }
}

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

#medium Задача: 377. Combination Sum IV Дан массив различных целых чисел nums и целое число target. Верните количество возможных комбинаций, которые в сумме дают target. Тестовые случаи сгенерированы так, что ответ помещается в 32-битное целое число. Пример:

Input: nums = [9], target = 3
Output: 0

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

class Solution {
    private HashMap<Integer, Integer> memo;

    public int combinationSum4(int[] nums, int target) {
        memo = new HashMap<>();
        return combs(nums, target);
    }

    private int combs(int[] nums, int remain) {
        if (remain == 0)
            return 1;
        if (memo.containsKey(remain))
            return memo.get(remain);

        int result = 0;
        for (int num : nums) {
            if (remain - num >= 0)
                result += combs(nums, remain - num);
        }
        memo.put(remain, result);
        return result;
    }
}

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

Начните свою карьеру Java-разработчика с Hexlet! Хотите стать профессионалом в Java? Пройдите обучение и за 10 месяцев освоите все ключевые навыки, от основ до продвинутого уровня. 🎁 🎃 Бонусы к Черной пятнице! Вас ждет специальное предложение - скидка до 81 000 ₽. на обучение и второй курс в подарок! Вас ждут сотни практических упражнений, реальные проекты для портфолио и поддержка опытных менторов. Освойте язык крупного бизнеса и финансовых технологий и научитесь разрабатывать веб-приложения на фреймворке Spring. А во время обучения вы также поучаствуете в Карьерном треке! Пройдите 5 бесплатных уроков и откройте для себя увлекательный процесс обучения. Поймите, насколько интересен и перспективен этот путь, и получите уникальную возможность продолжить обучение на полном курсе со скидкой!

#easy Задача: 463. Island Perimeter Дан массив размером row x col, представляющий карту, где grid[i][j] = 1 обозначает сушу, а grid[i][j] = 0 обозначает воду. Клетки сетки соединены горизонтально/вертикально (не по диагонали). Сетка полностью окружена водой, и на ней находится ровно один остров (т.е. одна или более соединённых ячеек суши). У острова нет "озёр", то есть вода внутри не соединена с водой вокруг острова. Одна ячейка - это квадрат со стороной 1. Сетка прямоугольная, ширина и высота не превышают 100. Определите периметр острова. Пример:

Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
Output: 16
Explanation: The perimeter is the 16 yellow stripes in the image above.

👨‍💻 Алгоритм: 1⃣Пройти через каждую ячейку сетки и, когда вы находитесь в ячейке с значением 1 (ячейка суши), проверить окружающие (СВЕРХУ, СПРАВА, СНИЗУ, СЛЕВА) ячейки. 2⃣Ячейка суши без каких-либо окружающих ячеек суши будет иметь периметр 4. Вычесть 1 за каждую окружающую ячейку суши. 3⃣Когда вы находитесь в ячейке с значением 0 (ячейка воды), ничего не делать. Просто перейти к следующей ячейке. 😎 Решение:

public class Solution {
    public int islandPerimeter(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        
        int result = 0;
        
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 1) {
                    int up = (r == 0) ? 0 : grid[r-1][c];
                    int left = (c == 0) ? 0 : grid[r][c-1];
                    int down = (r == rows-1) ? 0 : grid[r+1][c];
                    int right = (c == cols-1) ? 0 : grid[r][c+1];
                    
                    result += 4 - (up + left + right + down);
                }
            }
        }
        
        return result;
    }
}

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

#medium Задача: 376. Wiggle Subsequence Колеблющаяся последовательность — это последовательность, в которой разности между последовательными числами строго чередуются между положительными и отрицательными. Первая разность (если она существует) может быть как положительной, так и отрицательной. Последовательность с одним элементом и последовательность с двумя неравными элементами тривиально являются колеблющимися последовательностями. Например, [1, 7, 4, 9, 2, 5] — это колеблющаяся последовательность, потому что разности (6, -3, 5, -7, 3) чередуются между положительными и отрицательными. В отличие от нее, [1, 4, 7, 2, 5] и [1, 7, 4, 5, 5] не являются колеблющимися последовательностями. Первая не является, потому что первые две разности положительные, а вторая не является, потому что последняя разность равна нулю. Подпоследовательность получается путем удаления некоторых элементов (возможно, нуля) из исходной последовательности с сохранением оставшихся элементов в их первоначальном порядке. Дан целочисленный массив nums, верните длину самой длинной колеблющейся подпоследовательности из nums. Пример:

Input: nums = [1,7,4,9,2,5]
Output: 6
Explanation: The entire sequence is a wiggle sequence with differences (6, -3, 5, -7, 3).

👨‍💻 Алгоритм: 1⃣Для понимания этого подхода создайте два массива для динамического программирования, названных up и down. Эти массивы будут хранить длины наибольших колеблющихся подпоследовательностей, заканчивающихся соответственно восходящим или нисходящим колебанием. 2⃣up[i] относится к длине самой длинной колеблющейся подпоследовательности на данный момент, если рассматривать i-й элемент как последний элемент последовательности, заканчивающейся восходящим колебанием. Аналогично, down[i] относится к длине самой длинной колеблющейся подпоследовательности, если рассматривать i-й элемент как последний элемент последовательности, заканчивающейся нисходящим колебанием. 3⃣up[i] обновляется каждый раз, когда мы находим восходящее колебание, заканчивающееся на i-м элементе. Чтобы найти up[i], необходимо учесть максимальное значение всех предыдущих подпоследовательностей, заканчивающихся нисходящим колебанием, т.е. down[j], для каждого j<i и nums[i]>nums[j]. Аналогично, down[i] обновляется при нахождении нисходящего колебания. 😎 Решение:

public class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length < 2)
            return nums.length;
        int[] up = new int[nums.length];
        int[] down = new int[nums.length];
        for (int i = 1; i < nums.length; i++) {
            for(int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    up[i] = Math.max(up[i],down[j] + 1);
                } else if (nums[i] < nums[j]) {
                    down[i] = Math.max(down[i],up[j] + 1);
                }
            }
        }
        return 1 + Math.max(down[nums.length - 1], up[nums.length - 1]);
    }
}

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