Java | LeetCode
Open in Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
Show more
Network:6 506
Subscribers
-424 hours
-217 days
-5730 days
Posts Archive
6 505
#medium
Задача: 712. Minimum ASCII Delete Sum for Two Strings
Если даны две строки s1 и s2, верните наименьшую ASCII-сумму удаленных символов, чтобы сделать две строки равными.
Пример:
Input: s1 = "sea", s2 = "eat" Output: 231👨💻 Алгоритм: 1⃣Создайте двумерный массив dp размером (len(s1) + 1) x (len(s2) + 1), где dp[i][j] будет хранить наименьшую ASCII-сумму удаленных символов для первых i символов s1 и первых j символов s2. 2⃣Заполните первую строку и первый столбец массива dp суммами ASCII значений символов, которые необходимо удалить для достижения пустой строки. 3⃣Заполните оставшуюся часть массива dp следующим образом: Если символы s1[i-1] и s2[j-1] равны, dp[i][j] = dp[i-1][j-1]. Иначе, dp[i][j] = min(dp[i-1][j] + ord(s1[i-1]), dp[i][j-1] + ord(s2[j-1])). 😎 Решение:
public class Solution {
public int minimumDeleteSum(String s1, String s2) {
int[][] dp = new int[s1.length() + 1][s2.length() + 1];
for (int i = 1; i <= s1.length(); i++) {
dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1);
}
for (int j = 1; j <= s2.length(); j++) {
dp[0][j] = dp[0][j - 1] + s2.charAt(j - 1);
}
for (int i = 1; i <= s1.length(); i++) {
for (int j = 1; j <= s2.length(); j++) {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(dp[i - 1][j] + s1.charAt(i - 1), dp[i][j - 1] + s2.charAt(j - 1));
}
}
}
return dp[s1.length()][s2.length()];
}
}6 505
🔍 Google — В С Ё ?
В 2024 году невозможно найти что-то полезное, просто загуглив: выдача поиска забита мусором из ChatGPT, а все годные материалы не попадают в топы поиска.
Хорошо, что есть База Знаний — сеть каналов, в которой команда опытных айтишников постит лучшее из мира IT. Для вашего удобства всё отсортировано по категориям:
🖥 Python: @python_baza
👩💻 Frontend: @frontend_baza
👩💻 Backend: @backend_baza
🎨 Дизайн: @design_baza
📚 Книги: @archive_baza
👩💻 Топ GitHub: @main_it_baza
🕔 Ссылки будут активны ещё 48 часов, успейте сохранить себе, чтобы не потерять
6 505
#easy
Задача: 766. Toeplitz Matrix
Дана матрица размером m x n. Вернуть true, если матрица является Тёплицевой. В противном случае вернуть false.
Матрица является Тёплицевой, если все диагонали, идущие от верхнего левого к нижнему правому углу, содержат одинаковые элементы.
Пример:
Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Output: true
Explanation:
In the above grid, the diagonals are:
"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]".
In each diagonal all elements are the same, so the answer is True.class Solution {
public boolean isToeplitzMatrix(int[][] matrix) {
Map<Integer, Integer> groups = new HashMap<>();
for (int r = 0; r < matrix.length; ++r) {
for (int c = 0; c < matrix[0].length; ++c) {
if (!groups.containsKey(r - c))
groups.put(r - c, matrix[r][c]);
else if (groups.get(r - c) != matrix[r][c])
return false;
}
}
return true;
}
}6 505
#hard
Задача: 591. Tag Validator
Дана строка, представляющая фрагмент кода, реализуйте валидатор тегов для разбора кода и определения его корректности.
Фрагмент кода считается корректным, если соблюдаются все следующие правила:
Код должен быть заключен в корректный закрытый тег. В противном случае код некорректен.
Закрытый тег (не обязательно корректный) имеет точно следующий формат: <TAG_NAME>TAG_CONTENT</TAG_NAME>. Среди них <TAG_NAME> — это начальный тег, а </TAG_NAME> — конечный тег. TAG_NAME в начальном и конечном тегах должен быть одинаковым. Закрытый тег корректен, если и только если TAG_NAME и TAG_CONTENT корректны.
Корректное TAG_NAME содержит только заглавные буквы и имеет длину в диапазоне [1, 9]. В противном случае TAG_NAME некорректен.
Корректное TAG_CONTENT может содержать другие корректные закрытые теги, cdata и любые символы (см. примечание 1), КРОМЕ неподходящих <, неподходящих начальных и конечных тегов, и неподходящих или закрытых тегов с некорректным TAG_NAME. В противном случае TAG_CONTENT некорректен.
Начальный тег неподходящий, если нет конечного тега с тем же TAG_NAME, и наоборот. Однако нужно также учитывать проблему несбалансированных тегов, когда они вложены.
< неподходящий, если не удается найти последующий >. И когда вы находите < или </, все последующие символы до следующего > должны быть разобраны как TAG_NAME (не обязательно корректный).
cdata имеет следующий формат: <![CDATA[CDATA_CONTENT]]>. Диапазон CDATA_CONTENT определяется как символы между <![CDATA[ и первым последующим ]]>.
CDATA_CONTENT может содержать любые символы. Функция cdata заключается в том, чтобы запретить валидатору разбирать CDATA_CONTENT, поэтому даже если в нем есть символы, которые могут быть разобраны как тег (корректный или некорректный), вы должны рассматривать их как обычные символы.
Пример:
Input: code = "<DIV>This is the first line <![CDATA[<div>]]></DIV>" Output: true👨💻 Алгоритм: 1⃣Инициализируйте стек для отслеживания открытых тегов и флаг для определения наличия тегов. Используйте регулярное выражение для проверки корректности TAG_NAME, TAG_CONTENT и CDATA. 2⃣Пройдитесь по строке, проверяя каждый символ. Если встретите <, определите тип тега (начальный, конечный или CDATA). Обновите стек и индексы в зависимости от найденного типа. 3⃣В конце проверьте, что стек пуст (все теги корректно закрыты) и верните результат. 😎 Решение:
import java.util.regex.*;
public class Solution {
Stack<String> stack = new Stack<>();
boolean containsTag = false;
public boolean isValidTagName(String s, boolean ending) {
if (ending) {
if (!stack.isEmpty() && stack.peek().equals(s)) stack.pop();
else return false;
} else {
containsTag = true;
stack.push(s);
}
return true;
}
public boolean isValid(String code) {
if (!Pattern.matches("<[A-Z]{0,9}>([^<]*(<((\\/?[A-Z]{1,9}>)|(!\\[CDATA\\[(.*?)]]>)))?)*", code))
return false;
for (int i = 0; i < code.length(); i++) {
boolean ending = false;
if (stack.isEmpty() && containsTag) return false;
if (code.charAt(i) == '<') {
if (code.charAt(i + 1) == '!') {
i = code.indexOf("]]>", i + 1);
continue;
}
if (code.charAt(i + 1) == '/') {
i++;
ending = true;
}
int closeIndex = code.indexOf('>', i + 1);
if (closeIndex < 0 || !isValidTagName(code.substring(i + 1, closeIndex), ending))
return false;
i = closeIndex;
}
}
return stack.isEmpty();
}
}6 505
#hard
Задача: 711. Number of Distinct Islands II
Вам дана двоичная матричная сетка m x n. Остров - это группа 1 (представляющая сушу), соединенных в четырех направлениях (горизонтальном или вертикальном). Можно предположить, что все четыре края сетки окружены водой. Остров считается одинаковым с другим, если они имеют одинаковую форму, или имеют одинаковую форму после поворота (только на 90, 180 или 270 градусов) или отражения (влево/вправо или вверх/вниз). Верните количество разных островов.
Пример:
Input: grid = [[1,1,0,0,0],[1,0,0,0,0],[0,0,0,0,1],[0,0,0,1,1]] Output: 1👨💻 Алгоритм: 1⃣Пройдите по каждому элементу матрицы, если найдена земля (1), выполните DFS для обнаружения всех связанных с этим островом земель и сохраните форму острова. 2⃣Нормализуйте форму острова, применив все возможные повороты и отражения, чтобы найти каноническую форму. 3⃣Используйте множество для хранения всех уникальных канонических форм и верните размер этого множества. 😎 Решение:
import java.util.*;
public class Solution {
public int numDistinctIslands2(int[][] grid) {
Set<String> uniqueIslands = new HashSet<>();
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1) {
List<int[]> shape = new ArrayList<>();
dfs(grid, i, j, i, j, shape);
uniqueIslands.add(normalize(shape));
}
}
}
return uniqueIslands.size();
}
private void dfs(int[][] grid, int i, int j, int baseI, int baseJ, List<int[]> shape) {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0) {
return;
}
grid[i][j] = 0;
shape.add(new int[] {i - baseI, j - baseJ});
dfs(grid, i + 1, j, baseI, baseJ, shape);
dfs(grid, i - 1, j, baseI, baseJ, shape);
dfs(grid, i, j + 1, baseI, baseJ, shape);
dfs(grid, i, j - 1, baseI, baseJ, shape);
}
private String normalize(List<int[]> shape) {
List<List<int[]>> shapes = new ArrayList<>();
for (int i = 0; i < 8; i++) {
shapes.add(new ArrayList<>());
}
for (int[] point : shape) {
int x = point[0], y = point[1];
shapes.get(0).add(new int[] {x, y});
shapes.get(1).add(new int[] {x, -y});
shapes.get(2).add(new int[] {-x, y});
shapes.get(3).add(new int[] {-x, -y});
shapes.get(4).add(new int[] {y, x});
shapes.get(5).add(new int[] {y, -x});
shapes.get(6).add(new int[] {-y, x});
shapes.get(7).add(new int[] {-y, -x});
}
for (List<int[]> s : shapes) {
s.sort((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
}
String[] shapesStr = new String[8];
for (int i = 0; i < 8; i++) {
shapesStr[i] = shapes.get(i).toString();
}
Arrays.sort(shapesStr);
return shapesStr[0];
}
}6 505
#hard
Задача: 765. Couples Holding Hands
Есть n пар, сидящих на 2n местах, расположенных в ряд, и они хотят держаться за руки.
Люди и места представлены массивом целых чисел row, где row[i] — это ID человека, сидящего на i-м месте. Пары пронумерованы по порядку: первая пара — (0, 1), вторая пара — (2, 3) и так далее, до последней пары — (2n - 2, 2n - 1).
Верните минимальное количество перестановок, чтобы каждая пара сидела рядом. Перестановка состоит из выбора любых двух человек, которые встают и меняются местами.
Пример:
Input: row = [0,2,1,3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.class Solution {
int N;
int[][] pairs;
public int minSwapsCouples(int[] row) {
N = row.length / 2;
pairs = new int[N][2];
for (int i = 0; i < N; ++i) {
pairs[i][0] = row[2 * i] / 2;
pairs[i][1] = row[2 * i + 1] / 2;
}
return solve(0);
}
public void swap(int a, int b, int c, int d) {
int t = pairs[a][b];
pairs[a][b] = pairs[c][d];
pairs[c][d] = t;
}
public int solve(int i) {
if (i == N) return 0;
int x = pairs[i][0], y = pairs[i][1];
if (x == y) return solve(i + 1);
int jx = 0, kx = 0, jy = 0, ky = 0;
for (int j = i + 1; j < N; ++j) {
for (int k = 0; k <= 1; ++k) {
if (pairs[j][k] == x) { jx = j; kx = k; }
if (pairs[j][k] == y) { jy = j; ky = k; }
}
}
swap(i, 1, jx, kx);
int ans1 = 1 + solve(i + 1);
swap(i, 1, jx, kx);
swap(i, 0, jy, ky);
int ans2 = 1 + solve(i + 1);
swap(i, 0, jy, ky);
return Math.min(ans1, ans2);
}
}6 505
Все новости из мира программирования на этом канале @umnyiprogrammist
Подписывайтесь, чтобы не упустите ничего важного
Ставь 👍 и забирай 📚 Базу знаний
6 505
#hard
Задача: 710. Random Pick with Blacklist
Вам дано целое число n и массив уникальных целых чисел blacklist. Разработайте алгоритм выбора случайного целого числа из диапазона [0, n - 1], не входящего в черный список. Любое целое число, находящееся в указанном диапазоне и не входящее в черный список, должно с равной вероятностью быть возвращено. Оптимизируйте алгоритм так, чтобы он минимизировал количество обращений к встроенной функции random вашего языка. Реализуйте класс Solution: Solution(int n, int[] blacklist) Инициализирует объект целым числом n и целым числом из черного списка blacklist. int pick() Возвращает случайное целое число в диапазоне [0, n - 1] и не входящее в черный список.
Пример:
Input ["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"] [[7, [2, 3, 5]], [], [], [], [], [], [], []] Output [null, 0, 4, 1, 6, 1, 0, 4]👨💻 Алгоритм: 1⃣Создайте маппинг для чисел, входящих в черный список, чтобы сопоставить их с числами из диапазона [n - len(blacklist), n - 1], которые не входят в черный список. 2⃣Создайте массив для хранения возможных чисел для выбора, исключая числа из черного списка. 3⃣При каждом вызове функции pick() используйте встроенную функцию random для выбора случайного индекса из массива возможных чисел и возвращайте соответствующее значение. 😎 Решение:
import java.util.*;
public class Solution {
private Map<Integer, Integer> map;
private int bound;
public Solution(int n, int[] blacklist) {
map = new HashMap<>();
bound = n - blacklist.length;
Set<Integer> blackset = new HashSet<>();
for (int b : blacklist) {
blackset.add(b);
}
int whitelist = bound;
for (int b : blacklist) {
if (b < bound) {
while (blackset.contains(whitelist)) {
whitelist++;
}
map.put(b, whitelist);
whitelist++;
}
}
}
public int pick() {
int r = (int) (Math.random() * bound);
return map.getOrDefault(r, r);
}
}6 505
#medium
Задача: 366. Find Leaves of Binary Tree
Дан корень бинарного дерева, соберите узлы дерева следующим образом:
Соберите все листовые узлы.
Удалите все листовые узлы.
Повторяйте, пока дерево не станет пустым.
Пример:
Input: root = [1,2,3,4,5] Output: [[4,5,3],[2],[1]] Explanation: [[3,5,4],[2],[1]] and [[3,4,5],[2],[1]] are also considered correct answers since per each level it does not matter the order on which elements are returned.👨💻 Алгоритм: 1⃣Реализовать функцию getHeight(node), которая будет вычислять высоту каждого узла в дереве с использованием рекурсивного обхода в глубину (post-order). Если узел является null, вернуть -1. 2⃣Сохранить пары (высота, значение) для всех узлов и отсортировать их по высоте. 3⃣Организовать узлы по высоте и вернуть результат. 😎 Решение:
class Solution {
private List<Pair<Integer, Integer>> pairs;
private int getHeight(TreeNode root) {
if (root == null) return -1;
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
int currHeight = Math.max(leftHeight, rightHeight) + 1;
this.pairs.add(new Pair<Integer, Integer>(currHeight, root.val));
return currHeight;
}
public List<List<Integer>> findLeaves(TreeNode root) {
this.pairs = new ArrayList<>();
getHeight(root);
Collections.sort(this.pairs, Comparator.comparing(p -> p.getKey()));
int n = this.pairs.size(), height = 0, i = 0;
List<List<Integer>> solution = new ArrayList<>();
while (i < n) {
List<Integer> nums = new ArrayList<>();
while (i < n && this.pairs.get(i).getKey() == height) {
nums.add(this.pairs.get(i).getValue());
i++;
}
solution.add(nums);
height++;
}
return solution;
}
}6 505
Repost from easyoffer
Ищу работу пол года
Практически под каждым постом в этом канале я вижу комментарии от людей, которые ищут работу по полгода. Это перерастает в обсуждение того, как нужно (или не нужно) искать работу, почему процесс найма сломан и как они откликались на фейковые вакансии.
Честно говоря, искать работу полгода — это нонсенс. Очевидно, что человек делает что-то не так. Главная ошибка, которую совершают многие, — это создание иллюзии поиска работы.
То есть человек вроде бы ищет работу, но делает это неэффективно, тратя время на нецелевые действия. Например:
➖ Просматривает вакансии перед откликом.
➖ Пытается понять, подходит ли он под вакансию. Если считает, что не подходит — не откликается.
➖ Пишет сопроводительные письма (иногда даже уникальные под каждую вакансию).
➖ Заполняет анкеты, проходит тесты.
Все эти действия отнимают время, но не приводят к результату.
Почему это не работает?
HR-менеджер не может вручную отсмотреть 2000 откликов, оценить каждое резюме и прочитать сопроводительные письма. Поэтому компании используют ATS-системы (системы автоматического подбора), которые анализируют резюме и определяют процент его соответствия вакансии.
Что делать, чтобы повысить шансы?
1️⃣ Добавить ключевые навыки в резюме — и в основной текст, и в теги. Возьмите их с easyoffer.ru
2️⃣ Убрать нерелевантный опыт, оставить только подходящий.
3️⃣ Оформить опыт так, чтобы он выглядел релевантным. Если у вас его нет, укажите проекты, стажировки или другой опыт, который можно представить как работу от 1 года. Если опыт слишком большой, сузьте его до 6 лет.
4️⃣ Откликаться на все вакансии без разбору. Если вы Junior, не ищите только стажер или Junior-вакансии — пробуйте везде. Не отказывайте себе сами, пусть это решит HR
5️⃣ Сделать резюме публичным, потому что HR-менеджеры часто ищут кандидатов не только среди откликов, но и в базе резюме.
6️⃣ Используйте ИИ по минимуму – ATS-системы считывают это и помечают "сгенерировано ИИ"
‼️ Главное правило: чем больше откликов — тем выше шанс получить оффер. Делайте резюме удобным для ATS-систем, и вас заметят.
1. Посмотрите видео о том как я вывел свою резюме в Топ1 на HH
2. Посмотрите видео как я нашел первую работу
3. Прочитайте этот кейс про оптимизацию резюме
Если прям вообще тяжело.
Создайте несколько разных резюме. Создайте 2, 3 да хоть 10 резюме. Настройте авто-отлики и ждите приглашения на собесы.
Не нужно создавать иллюзию поиска работы, сделайте несколько простых и актуальных действий.
6 505
#medium
Задача: 364. Nested List Weight Sum II
Вам дан вложенный список целых чисел nestedList. Каждый элемент является либо целым числом, либо списком, элементы которого также могут быть целыми числами или другими списками.
Глубина целого числа — это количество списков, внутри которых оно находится. Например, вложенный список [1,[2,2],[[3],2],1] имеет значение каждого целого числа, установленное равным его глубине. Пусть maxDepth будет максимальной глубиной любого целого числа.
Вес целого числа определяется как maxDepth - (глубина целого числа) + 1.
Верните сумму каждого целого числа в nestedList, умноженную на его вес.
Пример:
Input: nestedList = [[1,1],2,[1,1]] Output: 8 Explanation: Four 1's with a weight of 1, one 2 with a weight of 2. 1*1 + 1*1 + 2*2 + 1*1 + 1*1 = 8👨💻 Алгоритм: 1⃣Инициализировать первый уровень BFS-дерева, добавив все элементы из входного nestedList в очередь. 2⃣Для каждого уровня извлекать передний элемент из очереди. Если это список, то добавить его элементы в очередь. В противном случае обновить значения sumOfElements, maxDepth и sumOfProducts. 3⃣Когда очередь станет пустой, вернуть значение (maxDepth + 1) * sumOfElements - sumOfProducts. 😎 Решение:
class Solution {
public int depthSumInverse(List<NestedInteger> nestedList) {
Queue<NestedInteger> Q = new LinkedList<>();
Q.addAll(nestedList);
int depth = 1;
int maxDepth = 0;
int sumOfElements = 0;
int sumOfProducts = 0;
while (!Q.isEmpty()) {
int size = Q.size();
maxDepth = Math.max(maxDepth, depth);
for (int i = 0; i < size; i++) {
NestedInteger nested = Q.poll();
if (nested.isInteger()) {
sumOfElements += nested.getInteger();
sumOfProducts += nested.getInteger() * depth;
} else {
Q.addAll(nested.getList());
}
}
depth++;
}
return (maxDepth + 1) * sumOfElements - sumOfProducts;
}
}6 505
#hard
Задача: 446. Arithmetic Slices II - Subsequence
Дан целочисленный массив nums, вернуть количество всех арифметических подпоследовательностей nums.
Последовательность чисел называется арифметической, если она состоит как минимум из трех элементов и если разница между любыми двумя последовательными элементами одинаковая.
Например, [1, 3, 5, 7, 9], [7, 7, 7, 7] и [3, -1, -5, -9] являются арифметическими последовательностями.
Например, [1, 1, 2, 5, 7] не является арифметической последовательностью.
Подпоследовательность массива - это последовательность, которая может быть образована путем удаления некоторых элементов (возможно, ни одного) из массива.
Например, [2, 5, 10] является подпоследовательностью [1, 2, 1, 2, 4, 1, 5, 10].
Тестовые случаи сгенерированы таким образом, что ответ помещается в 32-битное целое число.
Пример:
Input: nums = [2,4,6,8,10] Output: 7 Explanation: All arithmetic subsequence slices are: [2,4,6] [4,6,8] [6,8,10] [2,4,6,8] [4,6,8,10] [2,4,6,8,10] [2,6,10]👨💻 Алгоритм: 1⃣Мы можем использовать поиск в глубину (DFS) для генерации всех подпоследовательностей. 2⃣Мы можем проверить, является ли подпоследовательность арифметической, согласно ее определению. 3⃣Возвращаем количество всех арифметических подпоследовательностей. 😎 Решение:
class Solution {
private int n;
private int ans;
private void dfs(int dep, int[] A, List<Long> cur) {
if (dep == n) {
if (cur.size() < 3) return;
for (int i = 1; i < cur.size(); i++) {
if (cur.get(i) - cur.get(i - 1) != cur.get(1) - cur.get(0)) return;
}
ans++;
return;
}
dfs(dep + 1, A, cur);
cur.add((long) A[dep]);
dfs(dep + 1, A, cur);
cur.remove(cur.size() - 1);
}
public int numberOfArithmeticSlices(int[] A) {
n = A.length;
ans = 0;
dfs(0, A, new ArrayList<>());
return ans;
}
}6 505
⚡️ В сети начали массово сливать курсы и книги известных онлайн школ по айти
Вот отсортированная база с тонной материала (постепенно пополняется):
БАЗА (4687 видео/книг):
(363 видео, 87 книги) — Python
(415 видео, 68 книги) — Frontend
(143 видео, 33 книги) — ИБ/Хакинг
(352 видео, 89 книги) — С/С++
(343 видео, 87 книги) — Java
(176 видео, 32 книги) — Git
(293 видео, 63 книги) — C#
(174 видео, 91 книги) — DevOps
(167 видео, 53 книги) — PHP
(227 видео, 83 книги) — SQL/БД
(163 видео, 29 книги) — Linux
(114 видео, 77 книги) — Сисадмин
(107 видео, 43 книги) — BA/SA
(181 видео, 32 книги) — Go
(167 видео, 43 книги) — Kotlin/Swift
(112 видео, 24 книги) — Flutter
(137 видео, 93 книги) — DS/ML
(113 видео, 82 книги) — GameDev
(183 видео, 37 книги) — Дизайн
(129 видео, 73 книги) — QA
(213 видео, 63 книги) — Rust
(121 видео, 24 книги) — 1С
(136 видео, 33 книги) — PM/HR
Скачивать ничего не нужно — все выложено в Telegram
6 505
#medium
Задача: 445. Add Two Numbers II
Вам даны два непустых связанных списка, представляющих два неотрицательных целых числа. Самый значимый разряд стоит первым, и каждый из их узлов содержит одну цифру. Сложите два числа и верните сумму в виде связанного списка.
Вы можете предположить, что оба числа не содержат начальных нулей, за исключением самого числа 0.
Пример:
Input: l1 = [7,2,4,3], l2 = [5,6,4] Output: [7,8,0,7]👨💻 Алгоритм: 1⃣Создайте два связанных списка r1 и r2, чтобы хранить перевернутые связанные списки l1 и l2 соответственно. Создайте два целых числа totalSum и carry для хранения суммы и переноса текущих цифр. Создайте новый ListNode, ans, который будет хранить сумму текущих цифр. Мы будем складывать два числа, используя перевернутый список, добавляя цифры по одной. Продолжаем, пока не пройдем все узлы в r1 и r2. 2⃣Если r1 не равен null, добавляем r1.val к totalSum. Если r2 не равен null, добавляем r2.val к totalSum. Устанавливаем ans.val = totalSum % 10. Сохраняем перенос как totalSum / 10. Создаем новый ListNode, newNode, который будет иметь значение как перенос. Устанавливаем next для newNode как ans. Обновляем ans = newNode, чтобы использовать ту же переменную ans для следующей итерации. Обновляем totalSum = carry. 3⃣Если carry == 0, это означает, что newNode, созданный в финальной итерации цикла while, имеет значение 0. Поскольку мы выполняем ans = newNode в конце каждой итерации цикла while, чтобы избежать возврата связанного списка с головой, равной 0 (начальный ноль), возвращаем следующий элемент, т.е. возвращаем ans.next. В противном случае, если перенос не равен 0, значение ans не равно нулю. Следовательно, просто возвращаем ans. 😎 Решение:
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode temp = null;
while (head != null) {
temp = head.next;
head.next = prev;
prev = head;
head = temp;
}
return prev;
}
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode r1 = reverseList(l1);
ListNode r2 = reverseList(l2);
int totalSum = 0;
int carry = 0;
ListNode ans = new ListNode();
while (r1 != null || r2 != null) {
if (r1 != null) {
totalSum += r1.val;
r1 = r1.next;
}
if (r2 != null) {
totalSum += r2.val;
r2 = r2.next;
}
ans.val = totalSum % 10;
carry = totalSum / 10;
ListNode head = new ListNode(carry);
head.next = ans;
ans = head;
totalSum = carry;
}
return carry == 0 ? ans.next : ans;
}
}6 505
#hard
Задача: 363. Max Sum of Rectangle No Larger Than K
Дана матрица размером m x n и целое число k, вернуть максимальную сумму прямоугольника в матрице, такая что его сумма не превышает k.
Гарантируется, что будет прямоугольник с суммой, не превышающей k.
Пример:
Input: matrix = [[1,0,1],[0,-2,3]], k = 2 Output: 2 Explanation: Because the sum of the blue rectangle [[0, 1], [-2, 3]] is 2, and 2 is the max number no larger than k (k = 2).👨💻 Алгоритм: 1⃣Создать вспомогательную функцию updateResult, которая будет находить максимальную сумму подмассива в одномерном массиве, не превышающую k. 2⃣Преобразовать каждую подматрицу в одномерный массив и применить к ней функцию updateResult. 3⃣Вернуть максимальную найденную сумму. 😎 Решение:
class Solution {
int result = Integer.MIN_VALUE;
void updateResult(int[] nums, int k) {
int sum = 0;
TreeSet<Integer> sortedSum = new TreeSet<>();
sortedSum.add(0);
for (int num : nums) {
sum += num;
Integer x = sortedSum.ceiling(sum - k);
if (x != null)
result = Math.max(result, sum - x);
sortedSum.add(sum);
}
}
public int maxSumSubmatrix(int[][] matrix, int k) {
int[] rowSum = new int[matrix[0].length];
for (int i = 0; i < matrix.length; i++) {
Arrays.fill(rowSum, 0);
for (int row = i; row < matrix.length; row++) {
for (int col = 0; col < matrix[0].length; col++)
rowSum[col] += matrix[row][col];
updateResult(rowSum, k);
if (result == k)
return result;
}
}
return result;
}
}6 505
Repost from easyoffer
Привет, ребята!
1,5 года я учился на программиста, а сайт easyoffer.ru стал моим пет-проектом. Я создавал его, потому что:
а) нужно было добавить хоть какой-нибудь проект в резюме
б) подготовиться к прохождению собесов
И всё получилось! Благодаря еasyoffer я успешно прошёл собеседование и устроился Python Junior-разработчиком на удаленку с зарплатой 115 тысяч рублей.
Однако ещё во время разработки я понял, что у этого проекта есть потенциал. Казалось, что сайт может стать популярным и, возможно, превратиться в стартап.
По-этому я с самого начала заложил в проект минимальную бизнес-модель, на случай, если сайт начнёт набирать трафик. Я предложил пользователям полный доступ к сайту в обмен на подписку на Telegram-каналы. Это позволяло развивать аудиторию, а в будущем — зарабатывать на рекламе.
Результат превзошёл ожидания!
С момента запуска easyoffer посетило 400 тысяч человек. А когда доход с рекламы превысил мою зарплату программиста, я принял решение уйти с работы и полностью посвятить себя разработке новой версии сайта.
Вот так, зайдя в IT, через 4 месяца вышел через свой же пет-проект. Мне очень повезло
Уже год я работаю над easyoffer 2.0.
Это будет более масштабный и качественной новый проект:
– Появится тренажер
– Появятся задачи из собесов
– Фильтрация контента по грейдам
и еще очень много фич, о которых я расскажу позже.
Хочу, довести easyoffer до ума, чтобы сайт стал настоящим помощником для всех, кто готовится к собеседованиям.
По этому в ближайшее время я объявлю о старте краудфандинговой кампании, чтобы ускорить разработку и я готов щедро отблагодарить всех, кто поддержит проект.
А те, кто поддержат проект первыми, получат специальные лимитированные выгодные вознаграждения. Следите за этим телеграм каналом, если хотите стать первыми сапортерами.
6 505
#medium
Задача: 443. String Compression
Дан массив символов chars, сжать его, используя следующий алгоритм:
Начните с пустой строки s. Для каждой группы последовательных повторяющихся символов в chars:
Если длина группы равна 1, добавьте символ к строке s.
В противном случае добавьте символ, а за ним длину группы.
Сжатая строка s не должна возвращаться отдельно, а вместо этого должна быть сохранена в входном массиве символов chars. Обратите внимание, что длины групп, которые равны 10 или более, будут разделены на несколько символов в chars.
После того как вы закончите модификацию входного массива, верните новую длину массива.
Вы должны написать алгоритм, который использует только постоянное дополнительное пространство.
Пример:
Input: chars = ["a","a","b","b","c","c","c"] Output: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"] Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".👨💻 Алгоритм: 1⃣Объявите переменные i – первый индекс текущей группы, и res – длина ответа (сжатой строки). Инициализируйте i = 0, res = 0. 2⃣Пока i меньше длины chars: Найдите длину текущей группы последовательных повторяющихся символов groupLength. Добавьте chars[i] к ответу (chars[res++] = chars[i]). Если groupLength > 1, добавьте строковое представление groupLength к ответу и увеличьте res соответственно. Увеличьте i на groupLength и перейдите к следующей группе. 3⃣Верните res. 😎 Решение:
class Solution {
public int compress(char[] chars) {
int i = 0;
int res = 0;
while (i < chars.length) {
int groupLength = 1;
while (i + groupLength < chars.length && chars[i + groupLength] == chars[i]) {
groupLength++;
}
chars[res++] = chars[i];
if (groupLength > 1) {
String strRepr = Integer.toString(groupLength);
for (char ch : strRepr.toCharArray()) {
chars[res++] = ch;
}
}
i += groupLength;
}
return res;
}
}6 505
#medium
Задача: 442. Find All Duplicates in an Array
Дан целочисленный массив nums длины n, где все целые числа nums находятся в диапазоне [1, n], и каждое число появляется один или два раза. Верните массив всех чисел, которые появляются дважды.
Вы должны написать алгоритм, который работает за время O(n) и использует только постоянное дополнительное пространство.
Пример:
Input: nums = [4,3,2,7,8,2,3,1] Output: [2,3]👨💻 Алгоритм: 1⃣Когда мы итерируемся по элементам входного массива, мы можем просто искать любое другое вхождение текущего элемента в оставшейся части массива. 2⃣Поскольку элемент может появляться только один или два раза, нам не нужно беспокоиться о получении дубликатов элементов, которые появляются дважды: Случай I: Если элемент встречается в массиве только один раз, при поиске его в остальной части массива ничего не найдется. Случай II: Если элемент встречается дважды, вы найдете второе вхождение элемента в оставшейся части массива. Когда вы наткнетесь на второе вхождение в более поздней итерации, это будет аналогично случаю I (поскольку больше вхождений этого элемента в оставшейся части массива не будет). 3⃣Таким образом, можно эффективно определить все элементы, которые встречаются дважды, и добавить их в результирующий массив, проходя по каждому элементу массива и проверяя наличие его второго вхождения в оставшейся части массива. 😎 Решение:
class Solution {
public List<Integer> findDuplicates(int[] nums) {
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < nums.length; i++)
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] == nums[i]) {
ans.add(nums[i]);
break;
}
}
return ans;
}
}6 505
#medium
Задача: 362. Design Hit Counter
Дана матрица размером m x n, где каждая ячейка является либо стеной 'W', либо врагом 'E', либо пустой '0'. Верните максимальное количество врагов, которых можно уничтожить, используя одну бомбу. Вы можете разместить бомбу только в пустой ячейке.
Бомба уничтожает всех врагов в той же строке и столбце от точки установки до тех пор, пока не встретит стену, так как она слишком сильна, чтобы быть разрушенной.
Пример:
Input
["HitCounter", "hit", "hit", "hit", "getHits", "hit", "getHits", "getHits"]
[[], [1], [2], [3], [4], [300], [300], [301]]
Output
[null, null, null, null, 3, null, 4, 3]
Explanation
HitCounter hitCounter = new HitCounter();
hitCounter.hit(1); // hit at timestamp 1.
hitCounter.hit(2); // hit at timestamp 2.
hitCounter.hit(3); // hit at timestamp 3.
hitCounter.getHits(4); // get hits at timestamp 4, return 3.
hitCounter.hit(300); // hit at timestamp 300.
hitCounter.getHits(300); // get hits at timestamp 300, return 4.
hitCounter.getHits(301); // get hits at timestamp 301, return 3.class HitCounter {
private Queue<Integer> hits;
public HitCounter() {
this.hits = new LinkedList<Integer>();
}
public void hit(int timestamp) {
this.hits.add(timestamp);
}
public int getHits(int timestamp) {
while (!this.hits.isEmpty()) {
int diff = timestamp - this.hits.peek();
if (diff >= 300) this.hits.remove();
else break;
}
return this.hits.size();
}
}6 505
#easy
Задача: 441. Arranging Coins
У вас есть n монет, и вы хотите построить лестницу из этих монет. Лестница состоит из k рядов, где i-й ряд содержит ровно i монет. Последний ряд лестницы может быть неполным.
Дано целое число n, верните количество полных рядов лестницы, которые вы сможете построить.
Пример:
Input: n = 5 Output: 2 Explanation: Because the 3rd row is incomplete, we return 2.👨💻 Алгоритм: 1⃣Если мы глубже посмотрим на формулу задачи, мы можем решить её с помощью математики, без использования итераций. 2⃣Напомним, что условие задачи можно выразить следующим образом: k(k + 1) ≤ 2N. 3⃣Это можно решить методом выделения полного квадрата, (k + 1/2)² - 1/4 ≤ 2N. Что приводит к следующему ответу: k = [sqrt(2N + 1/4) - 1/2]. 😎 Решение:
class Solution {
public int arrangeCoins(int n) {
return (int)(Math.sqrt(2 * (long)n + 0.25) - 0.5);
}
}