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)

Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?

20.08.2023 18:21

Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в 2023-2024 годах? Или это полная лажа?".

Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией

20.08.2023 17:46

В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.

Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox

19.08.2023 18:39

Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в частности, магию поплавков и гибкость flexbox.

Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest

19.08.2023 17:22

В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для чтения благодаря своей простоте. Кроме того, мы всегда хотим проверить самые последние возможности в наших проектах!

Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️

18.08.2023 20:33

Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий их языку и культуре.

Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL

14.08.2023 14:49

Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип предназначен для представления неделимого значения.