Двоичное дерево оптимизирует решение? - PullRequest
Новая
       31

Двоичное дерево оптимизирует решение?

0 голосов
/ 28 марта 2020

Получил эту проблему в одном из конкурсов кодирования. У тебя есть лучший подход, чем у меня. Я дал псевдокод ниже

Учитывая полное двоичное дерево с узлами значений 1 или 0, всегда выполняются следующие правила:

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

Реализуйте следующие 2 API:

  • set_bit(offset, length), установите биты в диапазоне от offset до offset+length-1 на конечных узлах
  • clear_bit(offset, length), очистите биты в диапазоне от offset до offset+length-1 на конечных узлах

т.е. дерево имеет вид: 

             0
          /     \
         0        1
       /  \      /  \
      0    1     1    1
     /\   / \   / \  / \
    0  1 1   1 1  1  1  1

Ввод будет дан в виде двумерного массива 

int arr[][] = [ [0],[0,1],[1,0,1,0],[1,1,1,0,1,1,1,1]]

нам нужно установить бит или очистить бит на листовых узлах , В приведенном выше примере, если я делаю

clear(3,5)

i.e. The tree would be like:
             0
          /     \
         0        0
       /  \      /  \
      0    0     0   0
     /\   / \   / \  / \
    0  1 1   0 0   0 0  0

Псевдокод: Мой подход

1] Go к последней строке и внутреннему l oop начинается со смещения на листовом узле (последняя строка + смещение).

2] проверяет наличие элемента со смещением, если оно равно 1

3], если родственный ноль, то предок равен нулю не дальше action else, если это один

4], запишите диапазон предка до нуля в нашем случае (предок - строка- и столбец / 2), так в нашем случае для строки 2 (диапазон - от столбца 1 до 3)

5] следующая строка итерации 2 и внутренний l oop переместится из столбца 1 в 3

6], продолжая повторять

Для заданного бита мы также может за аналогичный подход

...