LeetCode запись решения 2536. Увеличение подматриц на единицу
03.02.2023 08:15
Увеличение подматриц на единицу - LeetCode
Вопрос
Учитывая число n, представляющее двумерную матрицу длины и ширины n, со всеми начальными значениями 0, и двумерный массив запросов, queries[i] = {r1, c1, r2, c2}, представляющих все координаты в столбцах r1 - r2, строках c1 - c2, все плюс 1, вернуть двумерную матрицу после выполнения запросов
Условия
- 1 ≤ n ≤ 500
- 1 ≤ длина запросов ≤ 10⁴
Смотрите
- Если каждый элемент в каждом запросе заполняется в соответствии с диапазоном, это интуитивно понятно, но TLE, худший случай - O(n²*m) m = длина запроса
- Мы можем использовать подход префиксной суммы для записи только приращения значения в каждой строке, например, {r1,c1,r2,c2} прибавить 1 к c1 в каждом столбце от r1 до r2, затем вычесть 1 из c2+1, и, наконец, вычислить префиксную сумму для каждой строки
Решение (префиксная сумма)
class Solution {
public int[][] rangeAddQueries(int n, int[][] queries) {
int ans [][] = new int [n][n];
for(int[] q:queries) {
for(int r=q[0];r<=q[2];r++) {
ans[r][q[1]] ++;
// 注意邊界
if (q[3]+1 < n)
ans[r][q[3]+1] --;
}
}
for(int r=0;r<n;r++)
for(int c=1;c<n;c++)
ans[r][c] += ans[r][c-1];
return ans;
}
}Результат
TC: O(n*m)
SC: O(n*n)
Типы данных JavaScript
27.03.2023 13:18
В JavaScript существует несколько типов данных, включая примитивные типы данных и ссылочные типы данных. Вот краткое объяснение различных типов данных в JavaScript с примерами:
Как сделать движок для футбольного матча? (простой вариант)
27.03.2023 12:01
Футбол. Для многих людей, живущих на земле, эта игра - больше, чем просто спорт. И эти люди всегда мечтают стать футболистом или менеджером. Но, к сожалению, большинство из них не могут подняться по лестнице успеха, и эти идеи застревают на стадии мечты. В этот момент на помощь приходят футбольные...
Знайте свои исключения!
27.03.2023 11:58
В Java исключение - это событие, возникающее во время выполнения программы, которое нарушает нормальный ход выполнения инструкций программы. Когда возникает исключение, программа прекращает нормальное выполнение и "бросает" объект исключения, который содержит информацию о возникшей ошибке. Это может...
CSS Flex: что должен знать каждый разработчик
27.03.2023 11:55
CSS Flex: что должен знать каждый разработчик Модуль flexbox, также известный как гибкий модуль разметки box, помогает эффективно проектировать и создавать отзывчивые веб-страницы без использования множества свойств позиционирования и float. По умолчанию в flex-контейнере есть только одна...
Введение в раздел "Заголовок" в HTML
26.03.2023 13:40
Говорят, что лучшее о человеке можно увидеть только изнутри, и это относится и к веб-страницам HTML! Причина, по которой некоторые веб-страницы не видны в поисковых системах, заключается в том, что им не хватает функций, обеспечивающих их видимость.
Что такое CommonModule в Angular
26.03.2023 10:45