LeetCode запись решения 2536. Увеличение подматриц на единицу

RedDeveloper
03.02.2023 08:15
LeetCode запись решения 2536. Увеличение подматриц на единицу

Увеличение подматриц на единицу - 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
Типы данных JavaScript

27.03.2023 13:18

В JavaScript существует несколько типов данных, включая примитивные типы данных и ссылочные типы данных. Вот краткое объяснение различных типов данных в JavaScript с примерами:

Как сделать движок для футбольного матча? (простой вариант)
Как сделать движок для футбольного матча? (простой вариант)

27.03.2023 12:01

Футбол. Для многих людей, живущих на земле, эта игра - больше, чем просто спорт. И эти люди всегда мечтают стать футболистом или менеджером. Но, к сожалению, большинство из них не могут подняться по лестнице успеха, и эти идеи застревают на стадии мечты. В этот момент на помощь приходят футбольные...

Знайте свои исключения!
Знайте свои исключения!

27.03.2023 11:58

В Java исключение - это событие, возникающее во время выполнения программы, которое нарушает нормальный ход выполнения инструкций программы. Когда возникает исключение, программа прекращает нормальное выполнение и "бросает" объект исключения, который содержит информацию о возникшей ошибке. Это может...

CSS Flex: что должен знать каждый разработчик
CSS Flex: что должен знать каждый разработчик

27.03.2023 11:55

CSS Flex: что должен знать каждый разработчик Модуль flexbox, также известный как гибкий модуль разметки box, помогает эффективно проектировать и создавать отзывчивые веб-страницы без использования множества свойств позиционирования и float. По умолчанию в flex-контейнере есть только одна...

Введение в раздел &quot;Заголовок&quot; в HTML
Введение в раздел "Заголовок" в HTML

26.03.2023 13:40

Говорят, что лучшее о человеке можно увидеть только изнутри, и это относится и к веб-страницам HTML! Причина, по которой некоторые веб-страницы не видны в поисковых системах, заключается в том, что им не хватает функций, обеспечивающих их видимость.