Задача: 934. Shortest Bridge
Сложность: medium
Вам дана двоичная матричная сетка n x n, где 1 обозначает сушу, а 0 - воду. Остров - это 4-направленно связанная группа из 1, не соединенная ни с одной другой 1. В сетке ровно два острова. Вы можете поменять 0 на 1, чтобы соединить два острова в один. Верните наименьшее количество 0, которое нужно перевернуть, чтобы соединить два острова.
Пример:
👨💻 Алгоритм:
1⃣Найти все клетки, принадлежащие первому острову, используя DFS/BFS, и добавить их в очередь для последующего расширения.
2⃣Использовать BFS для расширения из каждой клетки первого острова, чтобы найти кратчайший путь к клетке второго острова.
3⃣Вернуть длину кратчайшего пути.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Вам дана двоичная матричная сетка n x n, где 1 обозначает сушу, а 0 - воду. Остров - это 4-направленно связанная группа из 1, не соединенная ни с одной другой 1. В сетке ровно два острова. Вы можете поменять 0 на 1, чтобы соединить два острова в один. Верните наименьшее количество 0, которое нужно перевернуть, чтобы соединить два острова.
Пример:
Input: grid = [[0,1],[1,0]]
Output: 1
👨💻 Алгоритм:
1⃣Найти все клетки, принадлежащие первому острову, используя DFS/BFS, и добавить их в очередь для последующего расширения.
2⃣Использовать BFS для расширения из каждой клетки первого острова, чтобы найти кратчайший путь к клетке второго острова.
3⃣Вернуть длину кратчайшего пути.
😎 Решение:
using System;
using System.Collections.Generic;
public class Solution {
public int ShortestBridge(int[][] grid) {
int n = grid.Length;
var directions = new int[][] {
new int[] {-1, 0},
new int[] {1, 0},
new int[] {0, -1},
new int[] {0, 1}
};
var queue = new Queue<int[]>();
bool found = false;
for (int i = 0; i < n && !found; ++i) {
for (int j = 0; j < n && !found; ++j) {
if (grid[i][j] == 1) {
Dfs(grid, i, j, queue);
found = true;
}
}
}
int steps = 0;
while (queue.Count > 0) {
int size = queue.Count;
for (int i = 0; i < size; ++i) {
var point = queue.Dequeue();
int x = point[0], y = point[1];
foreach (var dir in directions) {
int nx = x + dir[0], ny = y + dir[1];
if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
if (grid[nx][ny] == 1) {
return steps;
}
if (grid[nx][ny] == 0) {
grid[nx][ny] = -1;
queue.Enqueue(new int[] {nx, ny});
}
}
}
}
steps++;
}
return -1;
}
private void Dfs(int[][] grid, int x, int y, Queue<int[]> queue) {
int n = grid.Length;
if (x < 0 || x >= n || y < 0 || y >= n || grid[x][y] != 1) {
return;
}
grid[x][y] = -1;
queue.Enqueue(new int[] {x, y});
Dfs(grid, x - 1, y, queue);
Dfs(grid, x + 1, y, queue);
Dfs(grid, x, y - 1, queue);
Dfs(grid, x, y + 1, queue);
}
}
Ставь 👍 и забирай 📚 Базу знаний
Задача: 1266. Minimum Time Visiting All Points
Сложность: easy
На двумерной плоскости имеется n точек с целочисленными координатами points[i] = [xi, yi]. Верните минимальное время в секундах для посещения всех точек в порядке, заданном точками. Вы можете перемещаться по следующим правилам: за 1 секунду вы можете либо: переместиться по вертикали на одну единицу, по горизонтали на одну единицу, либо по диагонали sqrt(2) единиц (другими словами, переместиться на одну единицу по вертикали и на одну единицу по горизонтали за 1 секунду). Вы должны посетить точки в том же порядке, в котором они появляются в массиве. Вы можете проходить через точки, которые появляются позже в порядке, но они не считаются за посещение.
Пример:
👨💻 Алгоритм:
1⃣Инициализируйте переменную для хранения минимального времени.
2⃣Последовательно проходите по всем точкам и вычисляйте минимальное время для перехода от текущей точки к следующей.
3⃣Суммируйте время переходов для получения общего минимального времени.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
На двумерной плоскости имеется n точек с целочисленными координатами points[i] = [xi, yi]. Верните минимальное время в секундах для посещения всех точек в порядке, заданном точками. Вы можете перемещаться по следующим правилам: за 1 секунду вы можете либо: переместиться по вертикали на одну единицу, по горизонтали на одну единицу, либо по диагонали sqrt(2) единиц (другими словами, переместиться на одну единицу по вертикали и на одну единицу по горизонтали за 1 секунду). Вы должны посетить точки в том же порядке, в котором они появляются в массиве. Вы можете проходить через точки, которые появляются позже в порядке, но они не считаются за посещение.
Пример:
Input: points = [[1,1],[3,4],[-1,0]]
Output: 7
👨💻 Алгоритм:
1⃣Инициализируйте переменную для хранения минимального времени.
2⃣Последовательно проходите по всем точкам и вычисляйте минимальное время для перехода от текущей точки к следующей.
3⃣Суммируйте время переходов для получения общего минимального времени.
😎 Решение:
public class Solution {
public int MinTimeToVisitAllPoints(int[][] points) {
int time = 0;
for (int i = 0; i < points.Length - 1; i++) {
time += Distance(points[i], points[i + 1]);
}
return time;
}
private int Distance(int[] p1, int[] p2) {
return Math.Max(Math.Abs(p1[0] - p2[0]), Math.Abs(p1[1] - p2[1]));
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 443. String Compression
Сложность: medium
Дан массив символов chars, сжать его, используя следующий алгоритм:
Начните с пустой строки s. Для каждой группы последовательных повторяющихся символов в chars:
Если длина группы равна 1, добавьте символ к строке s.
В противном случае добавьте символ, а за ним длину группы.
Сжатая строка s не должна возвращаться отдельно, а вместо этого должна быть сохранена в входном массиве символов chars. Обратите внимание, что длины групп, которые равны 10 или более, будут разделены на несколько символов в chars.
После того как вы закончите модификацию входного массива, верните новую длину массива.
Вы должны написать алгоритм, который использует только постоянное дополнительное пространство.
Пример:
👨💻 Алгоритм:
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.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дан массив символов 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.
😎 Решение:
public class Solution {
public int Compress(char[] chars) {
int i = 0, 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) {
foreach (char ch in groupLength.ToString()) {
chars[res++] = ch;
}
}
i += groupLength;
}
return res;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 1198. Find Smallest Common Element in All Rows
Сложность: medium
Дана матрица mat размером m x n, где каждая строка отсортирована в строго возрастающем порядке. Верните наименьший общий элемент во всех строках.
Если общего элемента нет, верните -1.
Пример:
👨💻 Алгоритм:
1⃣Инициализация переменных:
Инициализируйте массив позиций pos, переменную для текущего максимального значения cur_max и счетчик cnt нулями.
2⃣Итерация по строкам матрицы:
Для каждой строки:
- увеличивайте позицию в строке, пока значение не станет равным или больше текущего максимума.
- если достигли конца строки, возвращайте -1.
- если значение равно текущему максимуму, увеличивайте счетчик.
- в противном случае, сбросьте счетчик до 1 и обновите текущий максимум.
3⃣Проверка счетчика:
Если счетчик равен количеству строк, возвращайте текущий максимум.
Повторите шаг 2.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дана матрица mat размером m x n, где каждая строка отсортирована в строго возрастающем порядке. Верните наименьший общий элемент во всех строках.
Если общего элемента нет, верните -1.
Пример:
Input: mat = [[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11],[1,3,5,7,9]]
Output: 5
👨💻 Алгоритм:
1⃣Инициализация переменных:
Инициализируйте массив позиций pos, переменную для текущего максимального значения cur_max и счетчик cnt нулями.
2⃣Итерация по строкам матрицы:
Для каждой строки:
- увеличивайте позицию в строке, пока значение не станет равным или больше текущего максимума.
- если достигли конца строки, возвращайте -1.
- если значение равно текущему максимуму, увеличивайте счетчик.
- в противном случае, сбросьте счетчик до 1 и обновите текущий максимум.
3⃣Проверка счетчика:
Если счетчик равен количеству строк, возвращайте текущий максимум.
Повторите шаг 2.
😎 Решение:
public class Solution {
public int SmallestCommonElement(int[][] mat) {
int n = mat.Length, m = mat[0].Length;
int[] pos = new int[n];
int cur_max = 0, cnt = 0;
while (true) {
for (int i = 0; i < n; ++i) {
while (pos[i] < m && mat[i][pos[i]] < cur_max) {
++pos[i];
}
if (pos[i] >= m) {
return -1;
}
if (mat[i][pos[i]] != cur_max) {
cnt = 1;
cur_max = mat[i][pos[i]];
} else if (++cnt == n) {
return cur_max;
}
}
}
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 263. Ugly Number
Сложность: easy
Уродливое число — это положительное целое число, простые множители которого ограничены числами 2, 3 и 5.
Дано целое число n, верните true, если n является уродливым числом.
Пример:
👨💻 Алгоритм:
1⃣Если данное целое число n неположительное, верните false, так как неположительное число не может быть уродливым.
2⃣Определите функцию keepDividingWhenDivisible, которая принимает два аргумента: делимое и делитель. Эта функция будет делить делимое на делитель до тех пор, пока оно делится без остатка. Функция возвращает измененное делимое. Последовательно примените эту функцию к n с делителями 2, 3 и 5.
3⃣Если после всех делений n равно 1, верните true, иначе верните false.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Уродливое число — это положительное целое число, простые множители которого ограничены числами 2, 3 и 5.
Дано целое число n, верните true, если n является уродливым числом.
Пример:
Input: n = 6
Output: true
Explanation: 6 = 2 × 3
👨💻 Алгоритм:
1⃣Если данное целое число n неположительное, верните false, так как неположительное число не может быть уродливым.
2⃣Определите функцию keepDividingWhenDivisible, которая принимает два аргумента: делимое и делитель. Эта функция будет делить делимое на делитель до тех пор, пока оно делится без остатка. Функция возвращает измененное делимое. Последовательно примените эту функцию к n с делителями 2, 3 и 5.
3⃣Если после всех делений n равно 1, верните true, иначе верните false.
😎 Решение:
public class Solution {
public bool IsUgly(int n) {
if (n <= 0) {
return false;
}
foreach (int factor in new int[] {2, 3, 5}) {
n = KeepDividingWhenDivisible(n, factor);
}
return n == 1;
}
private int KeepDividingWhenDivisible(int dividend, int divisor) {
while (dividend % divisor == 0) {
dividend /= divisor;
}
return dividend;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 1143. Longest Common Subsequence
Сложность: medium
Даны две строки text1 и text2. Верните длину их наибольшей общей подпоследовательности. Если общей подпоследовательности нет, верните 0.
Подпоследовательность строки — это новая строка, созданная из оригинальной строки путем удаления некоторых символов (может быть ни одного) без изменения относительного порядка оставшихся символов.
Например, "ace" является подпоследовательностью "abcde".
Общая подпоследовательность двух строк — это подпоследовательность, которая является общей для обеих строк.
Пример:
👨💻 Алгоритм:
1⃣Создайте двумерный массив memo для хранения промежуточных результатов, чтобы избежать повторных вычислений. Инициализируйте массив значением -1, чтобы указать, что эти ячейки еще не были рассчитаны.
2⃣Реализуйте рекурсивную функцию memoSolve, которая принимает два указателя на текущие позиции в text1 и text2 и возвращает длину наибольшей общей подпоследовательности для этих подстрок. Если текущие символы совпадают, добавьте 1 к результату рекурсивного вызова для следующих символов. Если не совпадают, найдите максимум между рекурсивными вызовами с измененными указателями.
3⃣Возвращайте значение memoSolve(0, 0), чтобы получить результат для всей строки.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Даны две строки text1 и text2. Верните длину их наибольшей общей подпоследовательности. Если общей подпоследовательности нет, верните 0.
Подпоследовательность строки — это новая строка, созданная из оригинальной строки путем удаления некоторых символов (может быть ни одного) без изменения относительного порядка оставшихся символов.
Например, "ace" является подпоследовательностью "abcde".
Общая подпоследовательность двух строк — это подпоследовательность, которая является общей для обеих строк.
Пример:
Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.
👨💻 Алгоритм:
1⃣Создайте двумерный массив memo для хранения промежуточных результатов, чтобы избежать повторных вычислений. Инициализируйте массив значением -1, чтобы указать, что эти ячейки еще не были рассчитаны.
2⃣Реализуйте рекурсивную функцию memoSolve, которая принимает два указателя на текущие позиции в text1 и text2 и возвращает длину наибольшей общей подпоследовательности для этих подстрок. Если текущие символы совпадают, добавьте 1 к результату рекурсивного вызова для следующих символов. Если не совпадают, найдите максимум между рекурсивными вызовами с измененными указателями.
3⃣Возвращайте значение memoSolve(0, 0), чтобы получить результат для всей строки.
😎 Решение:
public class Solution {
private int[][] memo;
private string text1;
private string text2;
public int LongestCommonSubsequence(string text1, string text2) {
this.text1 = text1;
this.text2 = text2;
memo = new int[text1.Length + 1][];
for (int i = 0; i < text1.Length + 1; i++) {
memo[i] = new int[text2.Length + 1];
Array.Fill(memo[i], -1);
}
return MemoSolve(0, 0);
}
private int MemoSolve(int p1, int p2) {
if (p1 == text1.Length || p2 == text2.Length) return 0;
if (memo[p1][p2] != -1) return memo[p1][p2];
int answer;
if (text1[p1] == text2[p2]) {
answer = 1 + MemoSolve(p1 + 1, p2 + 1);
} else {
answer = Math.Max(MemoSolve(p1, p2 + 1), MemoSolve(p1 + 1, p2));
}
memo[p1][p2] = answer;
return answer;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 980. Unique Paths III
Сложность: hard
Вам дан целочисленный массив grid размером m x n, где grid[i][j] может быть:
1, представляющая начальную клетку. Существует ровно одна начальная клетка.
2, представляющая конечную клетку. Существует ровно одна конечная клетка.
0, представляющая пустые клетки, по которым можно ходить.
-1, представляющая препятствия, по которым нельзя ходить.
Верните количество 4-направленных путей от начальной клетки до конечной клетки, которые проходят по каждой непересекаемой клетке ровно один раз.
Пример:
👨💻 Алгоритм:
1⃣Как видно, метод обратного отслеживания (backtracking) является методологией для решения определенного типа задач.
2⃣Для задачи обратного отслеживания можно сказать, что существует тысяча реализаций обратного отслеживания на тысячу людей, как будет видно из дальнейшей реализации.
3⃣Здесь мы просто покажем один пример реализации, следуя псевдокоду, показанному в разделе интуиции.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: hard
Вам дан целочисленный массив grid размером m x n, где grid[i][j] может быть:
1, представляющая начальную клетку. Существует ровно одна начальная клетка.
2, представляющая конечную клетку. Существует ровно одна конечная клетка.
0, представляющая пустые клетки, по которым можно ходить.
-1, представляющая препятствия, по которым нельзя ходить.
Верните количество 4-направленных путей от начальной клетки до конечной клетки, которые проходят по каждой непересекаемой клетке ровно один раз.
Пример:
Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Explanation: We have the following two paths:
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)
👨💻 Алгоритм:
1⃣Как видно, метод обратного отслеживания (backtracking) является методологией для решения определенного типа задач.
2⃣Для задачи обратного отслеживания можно сказать, что существует тысяча реализаций обратного отслеживания на тысячу людей, как будет видно из дальнейшей реализации.
3⃣Здесь мы просто покажем один пример реализации, следуя псевдокоду, показанному в разделе интуиции.
😎 Решение:
public class Solution {
private int rows, cols;
private int[,] grid;
private int pathCount;
private void Backtrack(int row, int col, int remain) {
if (grid[row, col] == 2 && remain == 1) {
pathCount += 1;
return;
}
int temp = grid[row, col];
grid[row, col] = -4;
remain -= 1;
int[] rowOffsets = {0, 0, 1, -1};
int[] colOffsets = {1, -1, 0, 0};
for (int i = 0; i < 4; ++i) {
int nextRow = row + rowOffsets[i];
int nextCol = col + colOffsets[i];
if (0 > nextRow || nextRow >= rows || 0 > nextCol || nextCol >= cols)
continue;
if (grid[nextRow, nextCol] < 0)
continue;
Backtrack(nextRow, nextCol, remain);
}
grid[row, col] = temp;
}
public int UniquePathsIII(int[,] grid) {
int nonObstacles = 0, startRow = 0, startCol = 0;
rows = grid.GetLength(0);
cols = grid.GetLength(1);
this.grid = grid;
for (int row = 0; row < rows; ++row)
for (int col = 0; col < cols; ++col) {
int cell = grid[row, col];
if (cell >= 0)
nonObstacles += 1;
if (cell == 1) {
startRow = row;
startCol = col;
}
}
pathCount = 0;
Backtrack(startRow, startCol, nonObstacles);
return pathCount;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 253. Meeting Rooms II
Сложность: medium
Дан массив интервалов времени встреч intervals, где intervals[i] = [starti, endi]. Верните минимальное количество необходимых конференц-залов.
Пример:
👨💻 Алгоритм:
1⃣Отсортируйте встречи по времени их начала и инициализируйте мин-кучу с временем окончания первой встречи.
2⃣Для каждой последующей встречи проверьте, свободна ли комната (сравните время начала встречи с минимальным временем окончания в куче):
Если свободна, обновите время окончания этой комнаты.
Если не свободна, добавьте новое время окончания в кучу.
3⃣После обработки всех встреч размер кучи будет равен минимальному количеству необходимых комнат.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дан массив интервалов времени встреч intervals, где intervals[i] = [starti, endi]. Верните минимальное количество необходимых конференц-залов.
Пример:
Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2
👨💻 Алгоритм:
1⃣Отсортируйте встречи по времени их начала и инициализируйте мин-кучу с временем окончания первой встречи.
2⃣Для каждой последующей встречи проверьте, свободна ли комната (сравните время начала встречи с минимальным временем окончания в куче):
Если свободна, обновите время окончания этой комнаты.
Если не свободна, добавьте новое время окончания в кучу.
3⃣После обработки всех встреч размер кучи будет равен минимальному количеству необходимых комнат.
😎 Решение:
using System;
using System.Collections.Generic;
public class Solution {
public int MinMeetingRooms(int[][] intervals) {
Array.Sort(intervals, (a, b) => a[0] - b[0]);
var heap = new SortedSet<int>();
heap.Add(intervals[0][1]);
for (int i = 1; i < intervals.Length; i++) {
if (intervals[i][0] >= heap.Min) {
heap.Remove(heap.Min);
}
heap.Add(intervals[i][1]);
}
return heap.Count;
}
}
Ставь 👍 и забирай 📚 Базу знаний
Задача: 300. Longest Increasing Subsequence
Сложность: medium
Дан массив целых чисел nums, верните длину самой длинной строго возрастающей подпоследовательности.
Пример:
👨💻 Алгоритм:
1⃣Инициализируйте массив dp длиной nums.length, все элементы которого равны 1. dp[i] представляет длину самой длинной возрастающей подпоследовательности, которая заканчивается элементом с индексом i.
2⃣Итерируйтесь от i = 1 до i = nums.length - 1. В каждой итерации используйте второй цикл for для итерации от j = 0 до j = i - 1 (все элементы перед i). Для каждого элемента перед i, проверьте, меньше ли этот элемент, чем nums[i]. Если да, установите dp[i] = max(dp[i], dp[j] + 1).
3⃣Верните максимальное значение из dp.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дан массив целых чисел nums, верните длину самой длинной строго возрастающей подпоследовательности.
Пример:
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
👨💻 Алгоритм:
1⃣Инициализируйте массив dp длиной nums.length, все элементы которого равны 1. dp[i] представляет длину самой длинной возрастающей подпоследовательности, которая заканчивается элементом с индексом i.
2⃣Итерируйтесь от i = 1 до i = nums.length - 1. В каждой итерации используйте второй цикл for для итерации от j = 0 до j = i - 1 (все элементы перед i). Для каждого элемента перед i, проверьте, меньше ли этот элемент, чем nums[i]. Если да, установите dp[i] = max(dp[i], dp[j] + 1).
3⃣Верните максимальное значение из dp.
😎 Решение:
using System;
using System.Linq;
public class Solution {
public int LengthOfLIS(int[] nums) {
if (nums.Length == 0) return 0;
int[] dp = new int[nums.Length];
Array.Fill(dp, 1);
for (int i = 1; i < nums.Length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.Max(dp[i], dp[j] + 1);
}
}
}
return dp.Max();
}
Ставь 👍 и забирай 📚 Базу знаний
Задача: 821. Shortest Distance to a Character
Сложность: easy
Дана строка s и символ c, который встречается в s. Верните массив целых чисел answer, где answer.length == s.length, и answer[i] - это расстояние от индекса i до ближайшего появления символа c в строке s.
Расстояние между двумя индексами i и j равно abs(i - j), где abs - это функция абсолютного значения.
Пример:
👨💻 Алгоритм:
1⃣При проходе слева направо будем запоминать индекс prev последнего символа C, который мы видели. Тогда ответ будет i - prev.
2⃣При проходе справа налево будем запоминать индекс prev последнего символа C, который мы видели. Тогда ответ будет prev - i.
3⃣Мы берем минимальное значение из этих двух ответов для создания нашего окончательного ответа.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Дана строка s и символ c, который встречается в s. Верните массив целых чисел answer, где answer.length == s.length, и answer[i] - это расстояние от индекса i до ближайшего появления символа c в строке s.
Расстояние между двумя индексами i и j равно abs(i - j), где abs - это функция абсолютного значения.
Пример:
Input: s = "loveleetcode", c = "e"
Output: [3,2,1,0,1,0,0,1,2,2,1,0]
Explanation: The character 'e' appears at indices 3, 5, 6, and 11 (0-indexed).
The closest occurrence of 'e' for index 0 is at index 3, so the distance is abs(0 - 3) = 3.
The closest occurrence of 'e' for index 1 is at index 3, so the distance is abs(1 - 3) = 2.
For index 4, there is a tie between the 'e' at index 3 and the 'e' at index 5, but the distance is still the same: abs(4 - 3) == abs(4 - 5) = 1.
The closest occurrence of 'e' for index 8 is at index 6, so the distance is abs(8 - 6) = 2.
👨💻 Алгоритм:
1⃣При проходе слева направо будем запоминать индекс prev последнего символа C, который мы видели. Тогда ответ будет i - prev.
2⃣При проходе справа налево будем запоминать индекс prev последнего символа C, который мы видели. Тогда ответ будет prev - i.
3⃣Мы берем минимальное значение из этих двух ответов для создания нашего окончательного ответа.
😎 Решение:
public class Solution {
public int[] ShortestToChar(string S, char C) {
int N = S.Length;
int[] ans = new int[N];
int prev = -N;
for (int i = 0; i < N; ++i) {
if (S[i] == C) {
prev = i;
}
ans[i] = i - prev;
}
prev = 2 * N;
for (int i = N - 1; i >= 0; --i) {
if (S[i] == C) {
prev = i;
}
ans[i] = Math.Min(ans[i], prev - i);
}
return ans;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 1342. Number of Steps to Reduce a Number to Zero
Сложность: easy
Дано целое число num, вернуть количество шагов, необходимых для его сокращения до нуля.
На каждом шаге, если текущее число четное, его нужно разделить на 2, в противном случае, вы должны вычесть из него 1.
Пример:
👨💻 Алгоритм:
1⃣На каждом шаге проверяйте, четное ли текущее число, используя оператор остатка от деления (%). Если число четное (number % 2 == 0), разделите его на 2.
2⃣Если число нечетное (number % 2 == 1), вычтите из него 1.
3⃣После выполнения каждого из этих действий увеличивайте счетчик шагов на 1, чтобы в конце вернуть его значение.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Дано целое число num, вернуть количество шагов, необходимых для его сокращения до нуля.
На каждом шаге, если текущее число четное, его нужно разделить на 2, в противном случае, вы должны вычесть из него 1.
Пример:
Input: num = 14
Output: 6
Explanation:
Step 1) 14 is even; divide by 2 and obtain 7.
Step 2) 7 is odd; subtract 1 and obtain 6.
Step 3) 6 is even; divide by 2 and obtain 3.
Step 4) 3 is odd; subtract 1 and obtain 2.
Step 5) 2 is even; divide by 2 and obtain 1.
Step 6) 1 is odd; subtract 1 and obtain 0.
👨💻 Алгоритм:
1⃣На каждом шаге проверяйте, четное ли текущее число, используя оператор остатка от деления (%). Если число четное (number % 2 == 0), разделите его на 2.
2⃣Если число нечетное (number % 2 == 1), вычтите из него 1.
3⃣После выполнения каждого из этих действий увеличивайте счетчик шагов на 1, чтобы в конце вернуть его значение.
😎 Решение:
public int NumberOfSteps(int num) {
int steps = 0;
while (num != 0) {
if (num % 2 == 0) {
num /= 2;
} else {
num -= 1;
}
steps++;
}
return steps;
}Ставь 👍 и забирай 📚 Базу знаний
Завтра последний день!
Успей купить пожизненный easyoffer PRO - по цене 1 года
Покупаешь один раз — пользуешься всю жизнь.
👉 Акция до 31 марта: https://easyoffer.ru/pro
Успей купить пожизненный easyoffer PRO - по цене 1 года
Покупаешь один раз — пользуешься всю жизнь.
👉 Акция до 31 марта: https://easyoffer.ru/pro
Задача: 305. Number of Islands II
Сложность: hard
Дан пустой двумерный бинарный массив
Вы можете выполнить операцию "добавить землю", которая превращает воду в указанной позиции в сушу. Вам дан массив
Верните массив целых чисел
Остров окружен водой и образуется путем соединения соседних земель по горизонтали или вертикали. Вы можете считать, что все четыре края сетки окружены водой.
Пример:
👨💻 Алгоритм:
1⃣Инициализация:
Создайте массивы x[] = { -1, 1, 0, 0 } и y[] = { 0, 0, -1, 1 }, которые будут использоваться для нахождения соседей ячейки.
Создайте экземпляр UnionFind, например, dsu(m * n). Инициализируйте всех родителей значением -1. Используйте объединение по рангу, инициализируйте все ранги значением 0. Наконец, инициализируйте count = 0.
Создайте список целых чисел answer, где answer[i] будет хранить количество островов, образованных после превращения ячейки positions[i] в сушу.
2⃣Обработка позиций:
Итерация по массиву positions. Для каждой позиции в positions:
Выполните линейное отображение, чтобы преобразовать двумерную позицию ячейки в landPosition = position[0] * n + position[1].
Используйте операцию addLand(landPosition), чтобы добавить landPosition как узел в граф. Эта функция также увеличит count.
Итерация по каждому соседу позиции. Соседа можно определить с помощью neighborX = position[0] + x[i] и neighborY = position[1] + y[i], где neighborX — координата X, а neighborY — координата Y соседней ячейки. Выполните линейное отображение соседней ячейки с помощью neighborPosition = neighborX * n + neighborY. Теперь, если на neighborPosition есть суша, т.е. isLand(neighborPosition) возвращает true, выполните объединение neighborPosition и landPosition. В объединении уменьшите count на 1.
3⃣Определение количества островов:
Выполните операцию numberOfIslands, которая возвращает количество островов, образованных после превращения позиции в сушу. Добавьте это значение в answer.
Верните answer.
😎 Решение
Ставь 👍 и забирай 📚 Базу знаний
Сложность: hard
Дан пустой двумерный бинарный массив
grid размером m x n. Этот массив представляет собой карту, где 0 означает воду, а 1 — сушу. Изначально все ячейки массива — водные (т.е. все ячейки содержат 0).Вы можете выполнить операцию "добавить землю", которая превращает воду в указанной позиции в сушу. Вам дан массив
positions, где positions[i] = [ri, ci] — позиция (ri, ci), в которой следует выполнить i-ю операцию.Верните массив целых чисел
answer, где answer[i] — количество островов после превращения ячейки (ri, ci) в сушу.Остров окружен водой и образуется путем соединения соседних земель по горизонтали или вертикали. Вы можете считать, что все четыре края сетки окружены водой.
Пример:
Input: m = 1, n = 1, positions = [[0,0]]
Output: [1]
👨💻 Алгоритм:
1⃣Инициализация:
Создайте массивы x[] = { -1, 1, 0, 0 } и y[] = { 0, 0, -1, 1 }, которые будут использоваться для нахождения соседей ячейки.
Создайте экземпляр UnionFind, например, dsu(m * n). Инициализируйте всех родителей значением -1. Используйте объединение по рангу, инициализируйте все ранги значением 0. Наконец, инициализируйте count = 0.
Создайте список целых чисел answer, где answer[i] будет хранить количество островов, образованных после превращения ячейки positions[i] в сушу.
2⃣Обработка позиций:
Итерация по массиву positions. Для каждой позиции в positions:
Выполните линейное отображение, чтобы преобразовать двумерную позицию ячейки в landPosition = position[0] * n + position[1].
Используйте операцию addLand(landPosition), чтобы добавить landPosition как узел в граф. Эта функция также увеличит count.
Итерация по каждому соседу позиции. Соседа можно определить с помощью neighborX = position[0] + x[i] и neighborY = position[1] + y[i], где neighborX — координата X, а neighborY — координата Y соседней ячейки. Выполните линейное отображение соседней ячейки с помощью neighborPosition = neighborX * n + neighborY. Теперь, если на neighborPosition есть суша, т.е. isLand(neighborPosition) возвращает true, выполните объединение neighborPosition и landPosition. В объединении уменьшите count на 1.
3⃣Определение количества островов:
Выполните операцию numberOfIslands, которая возвращает количество островов, образованных после превращения позиции в сушу. Добавьте это значение в answer.
Верните answer.
😎 Решение
public class UnionFind {
private int[] parent, rank;
private int count;
public UnionFind(int size) { parent = new int[size]; rank = new int[size]; Array.Fill(parent, -1); count = 0; }
public void AddLand(int x) { if (parent[x] < 0) { parent[x] = x; count++; } }
public bool IsLand(int x) { return parent[x] >= 0; }
public int NumberOfIslands() { return count; }
public int Find(int x) { return parent[x] != x ? parent[x] = Find(parent[x]) : x; }
public void UnionSet(int x, int y) { int xset = Find(x), yset = Find(y); if (xset != yset) {
if (rank[xset] < rank[yset]) parent[xset] = yset; else { parent[yset] = xset; if (rank[xset] == rank[yset]) rank[xset]++; } count--; } }
}
public class Solution {
public IList<int> NumIslands2(int m, int n, int[][] positions) {
var dsu = new UnionFind(m * n);
int[] x = { -1, 1, 0, 0 }, y = { 0, 0, -1, 1 };
var answer = new List<int>();
foreach (var pos in positions) {
int land = pos[0] * n + pos[1];
dsu.AddLand(land);
for (int i = 0; i < 4; ++i) {
int nx = pos[0] + x[i], ny = pos[1] + y[i], neighbor = nx * n + ny;
if (nx >= 0 && nx < m && ny >= 0 && ny < n && dsu.IsLand(neighbor)) dsu.UnionSet(land, neighbor);
}
answer.Add(dsu.NumberOfIslands());
}
return answer;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 656. Coin Path
Сложность: hard
Вам дан целочисленный массив монет (1-индексированный) длины n и целое число maxJump. Вы можете перейти на любой индекс i массива coins, если coins[i] != -1 и вы должны заплатить coins[i] при посещении индекса i. Кроме того, если вы в данный момент находитесь на индексе i, вы можете перейти только на любой индекс i + k, где i + k <= n и k - значение в диапазоне [1, maxJump]. Изначально вы находитесь на индексе 1 (coins[1] не -1). Вы хотите найти путь, который достигнет индекса n с минимальной стоимостью. Верните целочисленный массив индексов, которые вы посетите в таком порядке, чтобы достичь индекса n с минимальной стоимостью. Если существует несколько путей с одинаковой стоимостью, верните лексикографически наименьший такой путь. Если невозможно достичь индекса n, возвращается пустой массив. Путь p1 = [Pa1, Pa2, ..., Pax] длины x лексикографически меньше, чем p2 = [Pb1, Pb2, ..., Pbx] длины y, если и только если при первом j, где Paj и Pbj отличаются, Paj < Pbj; если такого j нет, то x < y.
Пример:
👨💻 Алгоритм:
1⃣Используйте динамическое программирование для нахождения минимальной стоимости до каждого индекса, начиная с первого.
2⃣Храните путь до каждого индекса для отслеживания наименьшего лексикографического пути.
3⃣Используя полученную информацию, восстановите путь с минимальной стоимостью до последнего индекса.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: hard
Вам дан целочисленный массив монет (1-индексированный) длины n и целое число maxJump. Вы можете перейти на любой индекс i массива coins, если coins[i] != -1 и вы должны заплатить coins[i] при посещении индекса i. Кроме того, если вы в данный момент находитесь на индексе i, вы можете перейти только на любой индекс i + k, где i + k <= n и k - значение в диапазоне [1, maxJump]. Изначально вы находитесь на индексе 1 (coins[1] не -1). Вы хотите найти путь, который достигнет индекса n с минимальной стоимостью. Верните целочисленный массив индексов, которые вы посетите в таком порядке, чтобы достичь индекса n с минимальной стоимостью. Если существует несколько путей с одинаковой стоимостью, верните лексикографически наименьший такой путь. Если невозможно достичь индекса n, возвращается пустой массив. Путь p1 = [Pa1, Pa2, ..., Pax] длины x лексикографически меньше, чем p2 = [Pb1, Pb2, ..., Pbx] длины y, если и только если при первом j, где Paj и Pbj отличаются, Paj < Pbj; если такого j нет, то x < y.
Пример:
Input: coins = [1,2,4,-1,2], maxJump = 2
Output: [1,3,5]
👨💻 Алгоритм:
1⃣Используйте динамическое программирование для нахождения минимальной стоимости до каждого индекса, начиная с первого.
2⃣Храните путь до каждого индекса для отслеживания наименьшего лексикографического пути.
3⃣Используя полученную информацию, восстановите путь с минимальной стоимостью до последнего индекса.
😎 Решение:
using System;
using System.Collections.Generic;
public class Solution {
public List<int> MinCostPath(int[] coins, int maxJump) {
int n = coins.Length;
if (coins[0] == -1) return new List<int>();
int[] dp = new int[n];
Array.Fill(dp, int.MaxValue);
dp[0] = coins[0];
List<int>[] path = new List<int>[n];
for (int i = 0; i < n; i++) path[i] = new List<int>();
path[0].Add(1);
PriorityQueue<(int cost, int index), int> heap = new PriorityQueue<(int, int), int>();
heap.Enqueue((coins[0], 0), coins[0]);
while (heap.Count > 0) {
var (currentCost, i) = heap.Dequeue();
if (currentCost > dp[i]) continue;
for (int k = 1; k <= maxJump; k++) {
if (i + k < n && coins[i + k] != -1) {
int newCost = currentCost + coins[i + k];
if (newCost < dp[i + k] || (newCost == dp[i + k] && ComparePaths(path[i], path[i + k], i + k + 1))) {
dp[i + k] = newCost;
path[i + k] = new List<int>(path[i]);
path[i + k].Add(i + k + 1);
heap.Enqueue((newCost, i + k), newCost);
}
}
}
}
return dp[n - 1] == int.MaxValue ? new List<int>() : path[n - 1];
}
private bool ComparePaths(List<int> path1, List<int> path2, int newIndex) {
List<int> newPath1 = new List<int>(path1);
newPath1.Add(newIndex);
return string.Join(",", newPath1).CompareTo(string.Join(",", path2)) < 0;
}
public static void Main(string[] args) {
Solution solution = new Solution();
int[] coins = { 0, 2, 4, -1, 2, 5 };
int maxJump = 2;
var result = solution.MinCostPath(coins, maxJump);
}
}
Ставь 👍 и забирай 📚 Базу знаний
Задача: 537. Complex Number Multiplication
Сложность: medium
Комплексное число можно представить в виде строки в формате "real+imaginaryi", где:
real — это действительная часть и является целым числом в диапазоне [-100, 100].
imaginary — это мнимая часть и является целым числом в диапазоне [-100, 100].
i^2 == -1.
Даны два комплексных числа num1 и num2 в виде строк, верните строку комплексного числа, представляющую их произведение.
Пример:
👨💻 Алгоритм:
1⃣ Извлечение реальной и мнимой частей:
Разделите строки a и b на реальные и мнимые части, используя символы '+' и 'i'.
2⃣ Вычисление произведения:
Переведите извлечённые части в целые числа.
Используйте формулу для умножения комплексных чисел: (a+ib)×(x+iy)=ax−by+i(bx+ay).
3⃣ Формирование строки результата:
Создайте строку в требуемом формате с реальной и мнимой частями произведения и верните её.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Комплексное число можно представить в виде строки в формате "real+imaginaryi", где:
real — это действительная часть и является целым числом в диапазоне [-100, 100].
imaginary — это мнимая часть и является целым числом в диапазоне [-100, 100].
i^2 == -1.
Даны два комплексных числа num1 и num2 в виде строк, верните строку комплексного числа, представляющую их произведение.
Пример:
Input: num1 = "1+1i", num2 = "1+1i"
Output: "0+2i"
Explanation: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i, and you need convert it to the form of 0+2i.
👨💻 Алгоритм:
1⃣ Извлечение реальной и мнимой частей:
Разделите строки a и b на реальные и мнимые части, используя символы '+' и 'i'.
2⃣ Вычисление произведения:
Переведите извлечённые части в целые числа.
Используйте формулу для умножения комплексных чисел: (a+ib)×(x+iy)=ax−by+i(bx+ay).
3⃣ Формирование строки результата:
Создайте строку в требуемом формате с реальной и мнимой частями произведения и верните её.
😎 Решение:
public class Solution {
public string ComplexNumberMultiply(string a, string b) {
var x = a.Split(new char[] { '+', 'i' });
var y = b.Split(new char[] { '+', 'i' });
int a_real = int.Parse(x[0]);
int a_img = int.Parse(x[1]);
int b_real = int.Parse(y[0]);
int b_img = int.Parse(y[1]);
int realPart = a_real * b_real - a_img * b_img;
int imaginaryPart = a_real * b_img + a_img * b_real;
return realPart + "+" + imaginaryPart + "i";
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 1216. Valid Palindrome III
Сложность: hard
Дана строка s и целое число k. Верните true, если s является k-палиндромом.
Строка является k-палиндромом, если её можно преобразовать в палиндром, удалив из неё не более k символов.
Пример:
👨💻 Алгоритм:
1⃣Инициализируйте двухмерный массив memo для хранения промежуточных результатов, чтобы избежать повторных вычислений. Определите функцию isValidPalindrome, которая будет возвращать минимальное количество удалений для создания палиндрома в подстроке от индекса i до j.
2⃣Реализуйте базовые случаи для функции isValidPalindrome: если i равно j, то это уже палиндром, если i и j - соседние индексы, то возвращается 1, если символы не совпадают. Если значение для пары индексов уже рассчитано, то возвращается сохраненное значение из memo.
3⃣Реализуйте основные случаи рекурсивного вычисления: если символы на позициях i и j совпадают, продолжайте проверку для подстроки без этих символов. В противном случае, рассмотрите два варианта удаления символов и выберите минимальное количество удалений, добавив 1 за текущее удаление.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: hard
Дана строка s и целое число k. Верните true, если s является k-палиндромом.
Строка является k-палиндромом, если её можно преобразовать в палиндром, удалив из неё не более k символов.
Пример:
Input: s = "abcdeca", k = 2
Output: true
Explanation: Remove 'b' and 'e' characters.
👨💻 Алгоритм:
1⃣Инициализируйте двухмерный массив memo для хранения промежуточных результатов, чтобы избежать повторных вычислений. Определите функцию isValidPalindrome, которая будет возвращать минимальное количество удалений для создания палиндрома в подстроке от индекса i до j.
2⃣Реализуйте базовые случаи для функции isValidPalindrome: если i равно j, то это уже палиндром, если i и j - соседние индексы, то возвращается 1, если символы не совпадают. Если значение для пары индексов уже рассчитано, то возвращается сохраненное значение из memo.
3⃣Реализуйте основные случаи рекурсивного вычисления: если символы на позициях i и j совпадают, продолжайте проверку для подстроки без этих символов. В противном случае, рассмотрите два варианта удаления символов и выберите минимальное количество удалений, добавив 1 за текущее удаление.
😎 Решение:
public class Solution {
private int[,] memo;
private int IsValidPalindromeHelper(char[] s, int i, int j) {
if (i == j) return 0;
if (i == j - 1) return s[i] != s[j] ? 1 : 0;
if (memo[i, j] != -1) return memo[i, j];
if (s[i] == s[j]) {
memo[i, j] = IsValidPalindromeHelper(s, i + 1, j - 1);
} else {
memo[i, j] = 1 + Math.Min(IsValidPalindromeHelper(s, i + 1, j), IsValidPalindromeHelper(s, i, j - 1));
}
return memo[i, j];
}
public bool IsValidPalindrome(string s, int k) {
int n = s.Length;
memo = new int[n, n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
memo[i, j] = -1;
}
}
return IsValidPalindromeHelper(s.ToCharArray(), 0, n - 1) <= k;
}
}Ставь 👍 и забирай 📚 Базу знаний
👍1
Задача: 1001. Grid Illumination
Сложность: hard
Имеется двумерная сетка размером n x n, в каждой ячейке которой есть лампа, изначально выключенная. Вам дан двумерный массив позиций ламп lamps, где lamps[i] = [rowi, coli] означает, что лампа в ячейке grid[rowi][coli] включена. Даже если одна и та же лампа указана несколько раз, она включена. Когда лампа включена, она освещает свою ячейку и все остальные ячейки в той же строке, столбце или диагонали. Вам также дан другой двумерный массив queries, где queries[j] = [rowj, colj]. Для j-го запроса определите, освещена ли сетка[rowj][colj] или нет. После ответа на j-й запрос выключите лампу в сетке[rowj][colj] и 8 соседних ламп, если они существуют. Лампа является смежной, если ее ячейка имеет общую сторону или угол с сеткой[rowj][colj]. Верните массив целых чисел ans, где ans[j] должно быть 1, если ячейка в j-м запросе была освещена, или 0, если лампа не была освещена.
Пример:
👨💻 Алгоритм:
1⃣Инициализация данных:
Используйте множества для хранения включенных ламп, освещенных строк, столбцов, диагоналей и обратных диагоналей.
Инициализируйте множества и словари для отслеживания количества ламп, освещающих каждую строку, столбец, диагональ и обратную диагональ.
2⃣Обработка запросов:
Для каждого запроса проверьте, освещена ли ячейка, используя словари строк, столбцов, диагоналей и обратных диагоналей.
После ответа на запрос выключите лампу в указанной ячейке и 8 соседних ячейках, обновив множества и словари.
3⃣Обновление состояний ламп:
Обновите состояния ламп и освещенных ячеек после каждого запроса, чтобы корректно обрабатывать следующие запросы.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: hard
Имеется двумерная сетка размером n x n, в каждой ячейке которой есть лампа, изначально выключенная. Вам дан двумерный массив позиций ламп lamps, где lamps[i] = [rowi, coli] означает, что лампа в ячейке grid[rowi][coli] включена. Даже если одна и та же лампа указана несколько раз, она включена. Когда лампа включена, она освещает свою ячейку и все остальные ячейки в той же строке, столбце или диагонали. Вам также дан другой двумерный массив queries, где queries[j] = [rowj, colj]. Для j-го запроса определите, освещена ли сетка[rowj][colj] или нет. После ответа на j-й запрос выключите лампу в сетке[rowj][colj] и 8 соседних ламп, если они существуют. Лампа является смежной, если ее ячейка имеет общую сторону или угол с сеткой[rowj][colj]. Верните массив целых чисел ans, где ans[j] должно быть 1, если ячейка в j-м запросе была освещена, или 0, если лампа не была освещена.
Пример:
Input: n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
Output: [1,0]
👨💻 Алгоритм:
1⃣Инициализация данных:
Используйте множества для хранения включенных ламп, освещенных строк, столбцов, диагоналей и обратных диагоналей.
Инициализируйте множества и словари для отслеживания количества ламп, освещающих каждую строку, столбец, диагональ и обратную диагональ.
2⃣Обработка запросов:
Для каждого запроса проверьте, освещена ли ячейка, используя словари строк, столбцов, диагоналей и обратных диагоналей.
После ответа на запрос выключите лампу в указанной ячейке и 8 соседних ячейках, обновив множества и словари.
3⃣Обновление состояний ламп:
Обновите состояния ламп и освещенных ячеек после каждого запроса, чтобы корректно обрабатывать следующие запросы.
😎 Решение:
public class Solution {
public int[] GridIllumination(int n, int[][] lamps, int[][] queries) {
var lamps_on = new HashSet<(int, int)>();
var rows = new Dictionary<int, int>();
var cols = new Dictionary<int, int>();
var diag1 = new Dictionary<int, int>();
var diag2 = new Dictionary<int, int>();
foreach (var lamp in lamps) {
int r = lamp[0], c = lamp[1];
var key = (r, c);
if (lamps_on.Contains(key)) continue;
lamps_on.Add(key);
if (!rows.ContainsKey(r)) rows[r] = 0;
if (!cols.ContainsKey(c)) cols[c] = 0;
if (!diag1.ContainsKey(r - c)) diag1[r - c] = 0;
if (!diag2.ContainsKey(r + c)) diag2[r + c] = 0;
rows[r]++;
cols[c]++;
diag1[r - c]++;
diag2[r + c]++;
}
var directions = new (int, int)[] {(0, 0), (0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (-1, -1), (1, -1), (-1, 1)};
var result = new int[queries.Length];
for (int i = 0; i < queries.Length; i++) {
int r = queries[i][0], c = queries[i][1];
if (rows.ContainsKey(r) && rows[r] > 0 || cols.ContainsKey(c) && cols[c] > 0 || diag1.ContainsKey(r - c) && diag1[r - c] > 0 || diag2.ContainsKey(r + c) && diag2[r + c] > 0) {
result[i] = 1;
} else {
result[i] = 0;
}
foreach (var dir in directions) {
int nr = r + dir.Item1, nc = c + dir.Item2;
var key = (nr, nc);
if (lamps_on.Contains(key)) {
lamps_on.Remove(key);
rows[nr]--;
cols[nc]--;
diag1[nr - nc]--;
diag2[nr + nc]--;
}
}
}
return result;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 1035. Uncrossed Lines
Сложность: medium
Вам даны два целочисленных массива nums1 и nums2. Запишем целые числа nums1 и nums2 (в том порядке, в котором они даны) на двух отдельных горизонтальных линиях. Мы можем провести соединительные линии: прямую линию, соединяющую два числа nums1[i] и nums2[j] так, что: nums1[i] == nums2[j], и проведенная линия не пересекает никакую другую соединительную (негоризонтальную) линию. Обратите внимание, что соединительная линия не может пересекаться даже в конечных точках (т.е, каждое число может принадлежать только одной соединительной линии). Верните максимальное количество соединительных линий, которые мы можем нарисовать таким образом.
Пример:
👨💻 Алгоритм:
1⃣Определение задачи как задачи о нахождении наибольшей общей подпоследовательности (LCS):
Эта задача является классической задачей динамического программирования, где нам нужно найти максимальную длину наибольшей общей подпоследовательности (LCS) между nums1 и nums2.
2⃣Построение таблицы динамического программирования:
Создайте двумерный массив dp, где dp[i][j] будет представлять длину наибольшей общей подпоследовательности для подмассивов nums1[0..i-1] и nums2[0..j-1].
Инициализируйте первый ряд и первый столбец нулями, так как если один из массивов пуст, LCS также будет пустым.
3⃣Заполнение таблицы динамического программирования:
Пройдите по элементам массивов nums1 и nums2. Если текущие элементы совпадают, увеличьте значение ячейки dp[i][j] на 1 от диагонального значения dp[i-1][j-1]. Если не совпадают, установите значение ячейки dp[i][j] как максимальное из значений dp[i-1][j] и dp[i][j-1].
Результат будет находиться в ячейке dp[nums1.length][nums2.length].
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Вам даны два целочисленных массива nums1 и nums2. Запишем целые числа nums1 и nums2 (в том порядке, в котором они даны) на двух отдельных горизонтальных линиях. Мы можем провести соединительные линии: прямую линию, соединяющую два числа nums1[i] и nums2[j] так, что: nums1[i] == nums2[j], и проведенная линия не пересекает никакую другую соединительную (негоризонтальную) линию. Обратите внимание, что соединительная линия не может пересекаться даже в конечных точках (т.е, каждое число может принадлежать только одной соединительной линии). Верните максимальное количество соединительных линий, которые мы можем нарисовать таким образом.
Пример:
Input: nums1 = [1,4,2], nums2 = [1,2,4]
Output: 2
👨💻 Алгоритм:
1⃣Определение задачи как задачи о нахождении наибольшей общей подпоследовательности (LCS):
Эта задача является классической задачей динамического программирования, где нам нужно найти максимальную длину наибольшей общей подпоследовательности (LCS) между nums1 и nums2.
2⃣Построение таблицы динамического программирования:
Создайте двумерный массив dp, где dp[i][j] будет представлять длину наибольшей общей подпоследовательности для подмассивов nums1[0..i-1] и nums2[0..j-1].
Инициализируйте первый ряд и первый столбец нулями, так как если один из массивов пуст, LCS также будет пустым.
3⃣Заполнение таблицы динамического программирования:
Пройдите по элементам массивов nums1 и nums2. Если текущие элементы совпадают, увеличьте значение ячейки dp[i][j] на 1 от диагонального значения dp[i-1][j-1]. Если не совпадают, установите значение ячейки dp[i][j] как максимальное из значений dp[i-1][j] и dp[i][j-1].
Результат будет находиться в ячейке dp[nums1.length][nums2.length].
😎 Решение:
using System;
using System.Collections.Generic;
public class Solution {
public int[][] AllCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
var cells = new List<(int, int, int)>();
for (int r = 0; r < rows; ++r) {
for (int c = 0; c < cols; ++c) {
int distance = Math.Abs(r - rCenter) + Math.Abs(c - cCenter);
cells.Add((distance, r, c));
}
}
cells.Sort((a, b) => a.Item1.CompareTo(b.Item1));
var result = new List<int[]>();
foreach (var cell in cells) {
result.Add(new int[] { cell.Item2, cell.Item3 });
}
return result.ToArray();
}
}
Ставь 👍 и забирай 📚 Базу знаний
Задача: 1237. Find Positive Integer Solution for a Given Equation
Сложность: medium
Если дана вызываемая функция f(x, y) со скрытой формулой и значением z, выполните обратную разработку формулы и верните все пары целых положительных чисел x и y, в которых f(x,y) == z. Пары можно возвращать в любом порядке. Хотя точная формула скрыта, функция является монотонно возрастающей, т.е.Например: f(x, y) < f(x + 1, y) f(x, y) < f(x, y + 1) Интерфейс функции определяется следующим образом: interface CustomFunction { public: // Возвращает некоторое положительное целое число f(x, y) для двух положительных целых чисел x и y на основе формулы.
int f(int x, int y); }; Мы будем оценивать ваше решение следующим образом: у судьи есть список из 9 скрытых реализаций CustomFunction, а также способ сгенерировать ключ ответа из всех допустимых пар для определенного z. Судья получит два входа: function_id (чтобы определить, с какой реализацией тестировать ваш код) и целевое z. Судья вызовет ваш findSolution и сравнит ваши результаты с ключом ответа. Если ваши результаты совпадут с ключом ответа, ваше решение будет принято.
Пример:
👨💻 Алгоритм:
1⃣Начнем с =1 x=1 и 𝑦=1000 y=1000 (предполагаем максимальное значение y).
2⃣Перемещение указателей:
Если 𝑓(𝑥,𝑦)=𝑧
f(x,y)=z, добавляем пару (𝑥,𝑦)(x,y) в результат и увеличиваем x.
3⃣Повторяем шаги до тех пор, пока
𝑥≤1000 x≤1000 и 𝑦≥1y≥1.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Если дана вызываемая функция f(x, y) со скрытой формулой и значением z, выполните обратную разработку формулы и верните все пары целых положительных чисел x и y, в которых f(x,y) == z. Пары можно возвращать в любом порядке. Хотя точная формула скрыта, функция является монотонно возрастающей, т.е.Например: f(x, y) < f(x + 1, y) f(x, y) < f(x, y + 1) Интерфейс функции определяется следующим образом: interface CustomFunction { public: // Возвращает некоторое положительное целое число f(x, y) для двух положительных целых чисел x и y на основе формулы.
int f(int x, int y); }; Мы будем оценивать ваше решение следующим образом: у судьи есть список из 9 скрытых реализаций CustomFunction, а также способ сгенерировать ключ ответа из всех допустимых пар для определенного z. Судья получит два входа: function_id (чтобы определить, с какой реализацией тестировать ваш код) и целевое z. Судья вызовет ваш findSolution и сравнит ваши результаты с ключом ответа. Если ваши результаты совпадут с ключом ответа, ваше решение будет принято.
Пример:
Input: function_id = 1, z = 5
Output: [[1,4],[2,3],[3,2],[4,1]]
👨💻 Алгоритм:
1⃣Начнем с =1 x=1 и 𝑦=1000 y=1000 (предполагаем максимальное значение y).
2⃣Перемещение указателей:
Если 𝑓(𝑥,𝑦)=𝑧
f(x,y)=z, добавляем пару (𝑥,𝑦)(x,y) в результат и увеличиваем x.
3⃣Повторяем шаги до тех пор, пока
𝑥≤1000 x≤1000 и 𝑦≥1y≥1.
😎 Решение:
using System.Collections.Generic;
public class CustomFunction {
public int f(int x, int y) {}
}
public class Solution {
public IList<IList<int>> FindSolution(CustomFunction customfunction, int z) {
var result = new List<IList<int>>();
int x = 1;
int y = 1000;
while (x <= 1000 && y >= 1) {
int value = customfunction.f(x, y);
if (value == z) {
result.Add(new List<int> { x, y });
x++;
} else if (value < z) {
x++;
} else {
y--;
}
}
return result;
}
}
Ставь 👍 и забирай 📚 Базу знаний
Задача: 1354. Construct Target Array With Multiple Sums
Сложность: hard
Дан массив целых чисел target длины n. Начав с массива arr, состоящего из n единиц, вы можете выполнить следующую процедуру:
Пусть x будет суммой всех элементов, находящихся в вашем массиве.
Выберите индекс i так, чтобы 0 <= i < n, и установите значение arr в индексе i равным x.
Вы можете повторять эту процедуру столько раз, сколько потребуется.
Верните true, если возможно построить массив target из arr, в противном случае верните false.
Пример:
👨💻 Алгоритм:
1⃣Использование максимальной кучи (Max Heap) для отслеживания максимальных значений в target:
Сначала необходимо инициализировать кучу с максимальным приоритетом, чтобы всегда иметь доступ к наибольшему элементу в массиве target.
Вычислить сумму всех элементов в target и сохранить ее.
2⃣Повторение процесса переворота:
Извлечь наибольшее значение из кучи. Вычесть это значение из общей суммы.
Проверить несколько условий:
Если извлеченное значение равно 1 или общая сумма равна 1, вернуть true.
Если извлеченное значение меньше общей суммы, общая сумма равна 0, или извлеченное значение делится на общую сумму без остатка, вернуть false.
Остаток от деления наибольшего значения на общую сумму является новым значением, которое нужно вставить обратно в кучу. Обновить общую сумму.
3⃣Повторение цикла до достижения результата:
Повторять шаг 2 до тех пор, пока не будут выполнены условия выхода из цикла (возврат true или false).
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: hard
Дан массив целых чисел target длины n. Начав с массива arr, состоящего из n единиц, вы можете выполнить следующую процедуру:
Пусть x будет суммой всех элементов, находящихся в вашем массиве.
Выберите индекс i так, чтобы 0 <= i < n, и установите значение arr в индексе i равным x.
Вы можете повторять эту процедуру столько раз, сколько потребуется.
Верните true, если возможно построить массив target из arr, в противном случае верните false.
Пример:
Input: target = [8,5]
Output: true
👨💻 Алгоритм:
1⃣Использование максимальной кучи (Max Heap) для отслеживания максимальных значений в target:
Сначала необходимо инициализировать кучу с максимальным приоритетом, чтобы всегда иметь доступ к наибольшему элементу в массиве target.
Вычислить сумму всех элементов в target и сохранить ее.
2⃣Повторение процесса переворота:
Извлечь наибольшее значение из кучи. Вычесть это значение из общей суммы.
Проверить несколько условий:
Если извлеченное значение равно 1 или общая сумма равна 1, вернуть true.
Если извлеченное значение меньше общей суммы, общая сумма равна 0, или извлеченное значение делится на общую сумму без остатка, вернуть false.
Остаток от деления наибольшего значения на общую сумму является новым значением, которое нужно вставить обратно в кучу. Обновить общую сумму.
3⃣Повторение цикла до достижения результата:
Повторять шаг 2 до тех пор, пока не будут выполнены условия выхода из цикла (возврат true или false).
😎 Решение:
using System;
using System.Collections.Generic;
public class Solution {
public bool IsPossible(int[] target) {
var pq = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b - a));
long total = 0;
foreach (var num in target) {
total += num;
pq.Enqueue(num, num);
}
while (pq.Peek() > 1) {
int maxVal = pq.Dequeue();
total -= maxVal;
if (maxVal < total || total == 0 || maxVal % total == 0) return false;
pq.Enqueue(maxVal % total, maxVal % total);
total += pq.Peek();
}
return true;
}
}
Ставь 👍 и забирай 📚 Базу знаний
Задача: 480. Sliding Window Median
Сложность: Hard
Медиана — это среднее значение в упорядоченном списке целых чисел. Если размер списка четный, среднего значения не существует, поэтому медианой считается среднее значение двух средних чисел.
Например, если arr = [2, 3, 4], медиана равна 3.
Например, если arr = [1, 2, 3, 4], медиана равна (2 + 3) / 2 = 2.5.
Вам дан целочисленный массив nums и целое число k. Существует скользящее окно размера k, которое перемещается от самого левого края массива до самого правого. Вы можете видеть только k чисел в окне. Каждый раз скользящее окно перемещается вправо на одну позицию.
Верните массив медиан для каждого окна в исходном массиве. Ответы с точностью до 10^-5 будут приниматься.
Пример:
👨💻 Алгоритм:
1⃣Сохраняйте числа в контейнере окна размера k, выполняя следующие операции: Вставка входящего элемента. Удаление выходящего элемента.
2⃣ Отсортируйте окно, чтобы найти медианы. Вместо того чтобы каждый раз копировать и сортировать k последовательных элементов из входных данных, вставляйте и удаляйте по одному элементу при каждом сдвиге окна.
3⃣ Поддерживайте окно в отсортированном состоянии до и после операций вставки и удаления.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: Hard
Медиана — это среднее значение в упорядоченном списке целых чисел. Если размер списка четный, среднего значения не существует, поэтому медианой считается среднее значение двух средних чисел.
Например, если arr = [2, 3, 4], медиана равна 3.
Например, если arr = [1, 2, 3, 4], медиана равна (2 + 3) / 2 = 2.5.
Вам дан целочисленный массив nums и целое число k. Существует скользящее окно размера k, которое перемещается от самого левого края массива до самого правого. Вы можете видеть только k чисел в окне. Каждый раз скользящее окно перемещается вправо на одну позицию.
Верните массив медиан для каждого окна в исходном массиве. Ответы с точностью до 10^-5 будут приниматься.
Пример:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000]
Explanation:
Window position Median
--------------- -----
[1 3 -1] -3 5 3 6 7 1
1 [3 -1 -3] 5 3 6 7 -1
1 3 [-1 -3 5] 3 6 7 -1
1 3 -1 [-3 5 3] 6 7 3
1 3 -1 -3 [5 3 6] 7 5
1 3 -1 -3 5 [3 6 7] 6
👨💻 Алгоритм:
1⃣Сохраняйте числа в контейнере окна размера k, выполняя следующие операции: Вставка входящего элемента. Удаление выходящего элемента.
2⃣ Отсортируйте окно, чтобы найти медианы. Вместо того чтобы каждый раз копировать и сортировать k последовательных элементов из входных данных, вставляйте и удаляйте по одному элементу при каждом сдвиге окна.
3⃣ Поддерживайте окно в отсортированном состоянии до и после операций вставки и удаления.
😎 Решение:
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
public IList<double> MedianSlidingWindow(int[] nums, int k) {
List<double> medians = new List<double>();
for (int i = 0; i + k <= nums.Length; i++) {
int[] window = new int[k];
Array.Copy(nums, i, window, 0, k);
Array.Sort(window);
if (k % 2 == 1) {
medians.Add(window[k / 2]);
} else {
medians.Add((window[k / 2 - 1] + window[k / 2]) / 2.0);
}
}
return medians;
}
}
Ставь 👍 и забирай 📚 Базу знаний