Фотокамеры в двоичном дереве

-

Дано двоичное дерево, нам нужно установить в его узлах фотокамеры.

Камера в каждом узле мониторит сам узел, его родителя и его непосредственных детей.

Вычислить минимальное колчиество камер, которыми можно промониторить всё дерево.

Пример 1:

Дано: [0,0,null,0,0]
Результат: 1
Пояснение: Одной камеры достаточно, чтобы промониторить все узлы дерева, если установить её так, как показано на рисунке.

Пример 2:

Дано: [0,0,null,0,null,0,null,null,0]
Результат: 2
Пояснение: По крайней мере 2 камеры нужны, чтобы мониторить всё дерево. На рисунке показана однеа из конфигураций расположения камер.


Примечания:

  1. Число узлов в дереве варбируется в интервале [1, 1000].
  2. Все узлы дерева имеют значение 0.

Идея решения 

Рассмотрим "внутренний" (не корневой и не листовой) узел в дереве. Он может мониториться камерой в родителе, в себе, в своих 2 детях. Итого: 4 узла задействованы.

Рассмотрим корневой узел дерева.. Он монтирится двумя детьми и собой. Итого: 3 узла задействованы.

Расммотрим листовой узел дерева. Он мониторится собой или своим родителем. Итого: 2 узла задействовано.
  1. Если мы расположим камеру в листе, то задействуем 2 узла (лист и его родитель).
  2. Если мы расположим камеру не в листе, а в его родителе, то она мониторит сам узел, его родителя и двух детей (могут быть листья).


Мы види м, что второй план действий лучше, чем первый. И таким образом, нам нужно устанавливать камеру в родителях листьев.

Жадное решение:

  • Установить камеры в листьях родителей и исключить из рассмотрения все промониторенные узлы (листья, их родители и родители родителей).
  • Повторить предыдущий шаг, пока все узлы не будут промониторены.

Алгоритмически: применим DFS. 

Типы узлов:

  • 0 (NOT_MONITORED), если узел - это лист, поэтому может мониториться сверху вниз от родителя. Узел может быть и не листом, но снизу до него не "долетает" мониторинг, поэтому мы считаем его листом.
  • 1 (MINITORED_WITHCAM), узел с камерой внутри, мониторит детей (узлы типа 0) и родителя (узел типа 2)
  • 2 (MONITORED_NOCAM), если узел мониторится камерой снизу вверх, установленной в узле-ребенке.

Для каждого узла:

  • если узлу нужна камера (у него есть дети, которые не мониторятся), то увеличиваем счётчик необходимых камер и возвращаем 1.
  • если уже мониторится снизу вверх, то возвращаем 2.
  • в противном случае (узел будет мониторится снизу вверх) возвращаем 0.

Имплементация

    class Solution {
    private int NOT_MONITORED = 0;
    private int MONITORED_WITHCAM = 1;
    private int MONITORED_NOCAM = 2;
    private int cameras = 0;
	
    public int minCameraCover(TreeNode root) {
        if (root == null) return 0;
        int top = dfs(root);
        return cameras + (top == NOT_MONITORED ? 1 : 0);
    }
    
    private int dfs(TreeNode root) {
        if (root == null) return MONITORED_NOCAM;
        int left = dfs(root.left);
        int right = dfs(root.right);

        if (left == MONITORED_NOCAM && right == MONITORED_NOCAM) {
// и слева и вправа дети мониторятся снизу вверх, занчит до текущего
// узла мониторинг не "долетает", значит он никак не мониторится
            return NOT_MONITORED;
        } else if (left == NOT_MONITORED || right == NOT_MONITORED) {
// слева или справа есть дети, которые не мониторятся, значит
// устанавливаем камеру в сам узел, увеличиваем счётчик камер
            cameras++;
            return MONITORED_WITHCAM;
        } else {
// наконец, сам узел мониторится камерой в одном из детей
             return MONITORED_NOCAM;
        }
    }
}


 

Комментарии

Отправить комментарий

Популярные сообщения из этого блога

Разбиение числа на сумму с максимальным произведнием слагаемых

-
Источник: https://leetcode.com/problems/integer-break/ Дано целое число n , нужно представить его в виде суммы k положительных целых чисел , где k >= 2 , и произведение этих чисел максимально. Вернуть максимальное произведение. Пример 1: Дано: n = 2 Результат: 1 Пояснение: 2 = 1 + 1, 1 × 1 = 1. Пример 2: Дано: n = 10 Результат: 36 Пояснение: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36. Ограничения: 2 <= n <= 58 Идея решения Допустим мы представили число n в виде суммы, и произведение слагаемых этой суммы обозначим P = p1 * p2 * ...   pk. Рассмотрим некое слагаемое pi uи представим его в виде суммы pi-2 и 2. Если 2 (pi-2) > pi, то у нас получится ещё большее произведение, и это имеет место при pi > 4. Рассмотрим сумму pi-3 и 3, тогда 3*(pi-3) > pi при pi > 4.5. Если pi= 4, то (4-2)*2=4, а (4-3)*3=3. То есть Таким образом, нам нужно разбить исходное число на сумму двоек и троек, чтобы получить максимальное произведение.  В итоге нам нужно представить n = a 3 + ...
Далее...

Число подмассивов, в которых сумма элементов равна k

-
Дан целочисленный массив и целое число k . Найти количество непрерывных подмассивов таких, что сумма их элементов равна k . Пример 1: Дано: nums = [1,1,1], k = 2 Результат: 2 Условия: Длинна массива находится в диапазоне [1, 20,000]. Элементы массива находятся в диапазоне [-1000, 1000], число k - в диапазоне [-1e7, 1e7]. Идея решения Если кумулятивная сумма (пусть s u m [ i ] - это сумма с нулевого до i^{th} i t h индекса ) одинакова для индексов i и j, значит, сумма между этими двумя индексами равна нулю. А если суммы в индексах i i и  j j таковы, что sum[i] - sum[j] = k s u m [ i ] − s u m [ j ] = k , значит, сумма элементов между индексами i i   and   j j равна k k . Создадим хэшмап map m a p , чтобы хранить кумулятивные суммы для всех индексов, вместе с количеством того, сколько раз мы посчитали эту сумму . То есть это пары (sum_i, no. of occurences of sum_i) ( s u m i ​ , n o . o f o c c u r e n c e s o f s u m i ​ ) . Каждый раз, когда мы встречаем ...
Далее...

Сложить два числа, которые представлены списком

-
Даны 2 непустых списка, в которых закодированы, соответственно, два неотрицательных чила. Цифры каждого числа хранятся в обратном порядке. В каждоя ячейке списка находится одна цифра. Сложить эти два числа и вернуть их в виде списка. Можно предположить, что заданные числа не начинаются с нуля, за исключением если они и есть 0. Пример: Дано: (2 -> 4 -> 3) + (5 -> 6 -> 4) Резальтат: 7 -> 0 -> 8 Пояснение: 342 + 465 = 807. Идея решения. В начале каждого списка установим указатель, они будут смещаться одновременно складывая числа ячеек: a+b по правилам сложения в столбик. Имплементация. public ListNode addTwoNumbers(ListNode l1, ListNode l2) {     ListNode dummyHead = new ListNode(0); // запоминаем начало результирующего списка     ListNode p = l1, q = l2, curr = dummyHead;     int carry = 0;     while (p != null || q != null) {         int x = (p != null) ? p.v...
Далее...