[Ежедневный алгоритм] Четыре решения одной проблемы: «Моделирование» и «Древовидный массив (включая оптимизацию дедупликации)» и «Дерево линейных сегментов» | Месяц тем Python

Эта статья участвует в "Месяце тем Python", подробнее см.Ссылка на мероприятие

Описание темы

Это на LeetCode1893. Проверить, покрыты ли все целые числа в диапазоне, трудность в томПростой.

Тег : "моделирование", "массив деревьев", "дерево отрезков"

Вам дан двумерный массив целых чисел и два целых числа слева и справа. Каждый ranges[i] = [starti, endi] представляет собой закрытый интервал от starti до endi.

Если каждое целое число в закрытом интервале [слева, справа] покрывается хотя бы одним интервалом в диапазонах, верните true, иначе верните false.

Учитывая диапазон ranges[i] = [starti, endi], если целое число x удовлетворяет условию starti

Пример 1:

输入：ranges = [[1,2],[3,4],[5,6]], left = 2, right = 5

输出：true

解释：2 到 5 的每个整数都被覆盖了：
- 2 被第一个区间覆盖。
- 3 和 4 被第二个区间覆盖。
- 5 被第三个区间覆盖。

Пример 2:

输入：ranges = [[1,10],[10,20]], left = 21, right = 21

输出：false

解释：21 没有被任何一个区间覆盖。

намекать:

1 <= ranges.length <= 50
1 <= starti <= endi <= 50
1 <= left <= right <= 50

моделирование

Простая идея состоит в том, чтобы смоделировать в соответствии со смыслом вопроса, проверить $[left, right]$ для каждого целого числа в $ranges$ покрывается замкнутым интервалом в , то возвращаются непосредственноFalse, все значения проходят проверку и возвращаютсяTrue.

Код:

class Solution {
    public boolean isCovered(int[][] rs, int l, int r) {
        for (int i = l; i <= r; i++) {
            boolean ok = false;
            for (int[] cur : rs) {
                int a = cur[0], b = cur[1];
                if (a <= i && i <= b) {
                    ok = true;
                    break;
                }
            }
            if (!ok) return false;
        }
        return true;
    }
}

Код Python 3:

class Solution:
    def isCovered(self, ranges: List[List[int]], left: int, right: int) -> bool:
        for i in range(left, right+1):
            ok = False
            for a, b in ranges:
                if a <= i <= b:
                    ok = True
                    break
            if not ok:
                return False
        return True

Временная сложность: пусть $[left, right]$ Количество целых чисел между $n$ , $ranges$ Длина $m$ . Общая сложность составляет $O(n * m)$
Сложность пространства: $O(1)$

массив дерева

В ответ на этот вопрос может быть интересное расширение, чтобы увеличить сложность этого вопроса до [Средний] или даже [Сложный].

Будет запрашивать $[left, right]$ Изменено на «Четверичный массив запросов» $querys$ , каждый $querys[i]$ Содержит четыре индикатора $(a,b,l,r)$ : представляет запрос $[l, r]$ Каждое число в $range$ середина $[a, b]$ Закрытый интервал перезаписывается.

Если такое расширение сделано, то нам нужно использовать «постоянный массив дерева» или «дерево председателя», чтобы взаимодействовать с «принципом включения-исключения».

Основная идея заключается в использовании $range[0,b]$ отсчетов минус $range[0, a-1]$ Случай подсчета получается $[a, b]$ считает.

Вернуться к этому вопросу, из-за небольшого диапазона данных, только $50$ , мы можем использовать «массив деревьев» для решения:

void add(int x, int u): для числовых значений $x$ количество вхождений $+u$ действовать;
int query(int x): Запрос удовлетворения $<= x$ количество значений.

Итак, очевидно, если нам нужно запросить значение $x$ Появилось ли оно, вы можете запросить по $cnt = query(x) - query(x - 1)$ выяснить.

Java-код:

class Solution {
    int n = 55;
    int[] tr = new int[n];
    int lowbit(int x) {
        return x & -x;
    }
    void add(int x, int u) {
        for (int i = x; i <= n; i += lowbit(i)) tr[i] += u;
    }
    int query(int x) {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) ans += tr[i];
        return ans;
    }
    public boolean isCovered(int[][] rs, int l, int r) {
        for (int[] cur : rs) {
            int a = cur[0], b = cur[1];
            for (int i = a; i <= b; i++) {
                add(i, 1);
            }
        }
        for (int i = l; i <= r; i++) {
            int cnt = query(i) - query(i - 1);
            if (cnt == 0) return false;
        }
        return true;
    }
}

Код Python 3:

class Solution:
    def isCovered(self, ranges: List[List[int]], left: int, right: int) -> bool:
        n = 55
        tr = [0] * n

        def lowbit(x):
            return x & -x

        def add(x, u):
            i = x
            while i <= n:
                tr[i] += u
                i += lowbit(i)
        
        def query(x):
            ans = 0
            i = x
            while i > 0:
                ans += tr[i]
                i -= lowbit(i)
            return ans
        
        for a,b in ranges:
            for i in range(a, b+1):
                add(i, 1)
        
        for i in range(left, right+1):
            cnt = query(i) - query(i-1)
            if not cnt:
                return False
        return True

Временная сложность: пусть $[left, right]$ Количество целых чисел между $n$ , $\sum_{i = 0}^{range.legth - 1}ranges[i].length$ за $sum$ ,постоянный $C$ Исправить $55$ . Сложность построения дерева $O(sum\log C)$ , сложность запроса $O(n\log{C})$ . Общая сложность составляет $O(sum\log{C} + n\log{C})$
Сложность пространства: $O(C)$

Древовидный массив (оптимизация дедупликации)

В наивном решении «дерево массива» мы не можем напрямую запрашивать $[l, r]$ Основной причиной количества перезаписанных интервалов в интервале является «значение, которое может быть повторно добавлено в массив дерева».

Итак, лучшая практика:Дедупликация выполняется при добавлении деревьев в массив деревьев, а затем передается $cnt = query(r) - query(l - 1)$ напрямую $[l, r]$ Сколько чисел было добавлено в диапазоне.

ТакойSetОперация дедупликации может сделать наш запрос более сложным. $O(n\log{C})$ Падение до $O(\log{C})$ .

Из-за небольшого диапазона значений естественно использовать вместо них массивы.SetМарк (см. P2)

Java-код:

class Solution {
    int n = 55;
    int[] tr = new int[n];
    int lowbit(int x) {
        return x & -x;
    }
    void add(int x, int u) {
        for (int i = x; i <= n; i += lowbit(i)) tr[i] += u;
    }
    int query(int x) {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) ans += tr[i];
        return ans;
    }
    public boolean isCovered(int[][] rs, int l, int r) {
        Set<Integer> set = new HashSet<>();
        for (int[] cur : rs) {
            int a = cur[0], b = cur[1];
            for (int i = a; i <= b; i++) {
                if (!set.contains(i)) {
                    add(i, 1);
                    set.add(i);
                }
            }
        }
        int tot = r - l + 1, cnt = query(r) - query(l - 1);
        return tot == cnt;
    }
}

Java-код:

class Solution {
    int n = 55;
    int[] tr = new int[n];
    boolean[] vis = new boolean[n];
    int lowbit(int x) {
        return x & -x;
    }
    void add(int x, int u) {
        for (int i = x; i <= n; i += lowbit(i)) tr[i] += u;
    }
    int query(int x) {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) ans += tr[i];
        return ans;
    }
    public boolean isCovered(int[][] rs, int l, int r) {
        for (int[] cur : rs) {
            int a = cur[0], b = cur[1];
            for (int i = a; i <= b; i++) {
                if (!vis[i]) {
                    add(i, 1);
                    vis[i] = true;
                }
            }
        }
        int tot = r - l + 1, cnt = query(r) - query(l - 1);
        return tot == cnt;
    }
}

Временная сложность: пусть $[left, right]$ Количество целых чисел между $n$ , $\sum_{i = 0}^{range.legth - 1}ranges[i].length$ за $sum$ ,постоянный $C$ исправлено как $55$ . Сложность построения дерева $O(sum\log C)$ , сложность запроса $O(\log{C})$ . Общая сложность составляет $O(sum\log{C} + \log{C})$
Сложность пространства: $O(C + \sum_{i = 0}^{range.legth - 1}ranges[i].length)$

Дерево сегментов (без «ленивых маркеров»)

Более продвинутый подход заключается в использовании "дерева отрезков линии". Подобно решению "дерево-массив (оптимизация)", дерево отрезков линии с постоянством также может использоваться для решения "онлайновых" задач.

В отличие от древовидного массива, который в основном решает «модификацию одной точки и запрос интервала», дерево сегментов линии может решить большинство проблем «модификации интервала (модификация интервала/модификация одной точки) и запроса интервала».

Для этого вопроса, поскольку диапазон данных только $55$ Таким образом, мы можем использовать одну и ту же идею, что и решение «массива дерева (оптимизация) для реализации дерева сегмента линии, которое не содержит« ленивых знаков »(поддерживает только одноточечное изменение и интервал запроса).

Java-код:

class Solution {
    // 代表 [l, r] 区间有 cnt 个数被覆盖
    class Node {
        int l, r, cnt;
        Node (int _l, int _r, int _cnt) {
            l = _l; r = _r; cnt = _cnt;
        }
    }
    int N = 55;
    Node[] tr = new Node[N * 4];
    void pushup(int u) {
        tr[u].cnt = tr[u << 1].cnt + tr[u << 1 | 1].cnt;
    }
    void build(int u, int l, int r) {
        if (l == r) {
            tr[u] = new Node(l, r, 0);
        } else {
            tr[u] = new Node(l, r, 0);
            int mid = l + r >> 1;
            build(u << 1, l, mid);
            build(u << 1 | 1, mid + 1, r);
            pushup(u);
        }
    }
    // 从 tr 数组的下标 u 开始，在数值 x 的位置进行标记
    void update(int u, int x) {
        if (tr[u].l == x && tr[u].r == x) {
            tr[u].cnt = 1;
        } else {
            int mid = tr[u].l + tr[u].r >> 1;
            if (x <= mid) update(u << 1, x);
            else update(u << 1 | 1, x);
            pushup(u);
        }
    }
    // 从 tr 数组的下标 u 开始，查询 [l,r] 范围内有多少个数值被标记
    int query(int u, int l, int r) {
        if (l <= tr[u].l && tr[u].r <= r) return tr[u].cnt;
        int mid = tr[u].l + tr[u].r >> 1;
        int ans = 0;
        if (l <= mid) ans += query(u << 1, l, r);
        if (r > mid) ans += query(u << 1 | 1, l, r);
        return ans;
    }
    public boolean isCovered(int[][] rs, int l, int r) {
        build(1, 1, N);
        for (int[] cur : rs) {
            int a = cur[0], b = cur[1];
            for (int i = a; i <= b; i++) {
                update(1, i);
            }
        }
        int tot = r - l + 1 , cnt = query(1, l, r);
        return tot == cnt;
    }
}

Код Python 3:

class Solution:
    def isCovered(self, ranges: List[List[int]], l: int, r: int) -> bool:
        def pushup(u):
            tr[u].cnt = tr[u << 1].cnt + tr[u << 1 | 1].cnt
        
        def build(u, l, r):
            tr[u] = Node(l, r, 0)
            if l != r:
                tr[u] = Node(l, r, 0)
                mid = l + r >> 1
                build(u << 1, l, mid)
                build(u << 1 | 1, mid + 1, r)
                pushup(u)
            
        # 从 tr 数组的下标 u 开始，在数值 x 的位置进行标记
        def update(u, x):
            if tr[u].l == x and tr[u].r == x:
                tr[u].cnt = 1
            else:
                mid = tr[u].l + tr[u].r >> 1
                if x <= mid:
                    update(u << 1, x)
                else:
                    update(u << 1 | 1, x)
                pushup(u)

        # 从 tr 数组的下标 u 开始，查询 [l,r] 范围内有多少个数值被标记
        def query(u, l, r):
            if l <= tr[u].l and tr[u].r <= r:
                return tr[u].cnt
            mid = tr[u].l + tr[u].r >> 1
            ans = 0
            if l <= mid:
                ans += query(u << 1, l, r)
            if r > mid:
                ans += query(u << 1 | 1, l, r)
            return ans

        N = 55
        tr = [None] * N * 4
        build(1, 1, N)
        for a,b in ranges:
            for i in range(a, b+1):
                update(1, i)
        tot = r - l + 1
        cnt = query(1, l, r)
        return tot == cnt
    

class Node:
    def __init__(self, l, r, cnt):
        self.l = l
        self.r = r
        self.cnt = cnt

Временная сложность: пусть $[left, right]$ Количество целых чисел между $n$ , $\sum_{i = 0}^{range.legth - 1}ranges[i].length$ за $sum$ ,постоянный $C$ исправлено как $55$ . Сложность построения дерева $O(sum\log C)$ , сложность запроса $O(\log{C})$ . Общая сложность составляет $O(sum\log{C} + \log{C})$
Сложность пространства: $O(C * 4)$

Наконец

Это первая статья из нашей серии «Пройдитесь по LeetCode».No.1893Серия стартует 01.01.2021.На момент старта на LeetCode 1916 вопросов, некоторые из которых заблокированы.Сначала закончим все вопросы без замков.

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

Чтобы облегчить студентам отладку и отправку кода на компьютере, я создал соответствующие склады:GitHub.com/sharing кислый….

В адресе склада можно увидеть ссылку на решение серии статей, соответствующий код серии статей, ссылку на исходный вопрос LeetCode и другие предпочтительные решения.