How to become an author
Search
Write a publication
Pull to refresh

Comments 8

Стек с O(1) доступом к минимальному элементу:
Заведём два стека. Один — с актуальными данными, а другой — с минимумами.
data = [] # на питоне стек дёшево делается из списка
mins = [] # инвариант: mins[i] = min(data[0:i+1])

def empty() : return not data
def gettop() : return data[~0] # идиома: ~0 = -1, а -1 - это первый с конца
def getmin() : return mins[~0]

def push(v) :
  # минимум из расширенного набора равен
  # минимуму из
  #   минимума старого набора (мы его уже знаем)
  #   и нового элемента
  m = getmin() if not empty() and getmin() < v else v
  data.append(v)
  mins.append(m)

def pop():
  mins.pop()
  return data.pop() # на тот случай, если нам надо не выбросить, а ещё и вернуть выброшенное

Если данные тяжёлые, то в стеке минимумов можно хранить не сами данные, а, например, индексы. Заодно и ссылочную уникальность соблюдём.
data = []
mins = []

def empty() : return not data
def gettop() : return data[~0]
def getmin() : return data[mins[~0]]

def push(v) :
  # индекс нового минимума - тот же или индекс нового элемента
  m = mins[~0] if not empty() and getmin() < v else len(data)
  data.append(v)
  mins.append(m)

Правда, если у нас есть несколько одинаковых минимальных элементов, то вопрос, на кого из них отдавать ссылку, остаётся открытым. (Регулируется, в частности, выбором оператора < или <=)
This comment wasn’t rated yet0
Задача про множество уникальных элементов со случайным доступом.
Понятное дело, что это хеш-таблица.
А для того, чтобы эффективно реализовать случайный доступ, будем хранить элементы в сплошном массиве.

Можно сделать такую хеш-таблицу с самого начала (на трёх массивах), но это довольно муторное занятие. (Я делал в боевом коде, когда боролся за производительность).
Или внести небольшую избыточность, используя готовые хеш-таблицы из стандартных библиотек.

V = [] # вектор данных
D = {} # хеш-таблица - значение : индекс
# инвариант: V[D[v]] = v, D[V[i]] = i

def add(v) :
  if v in D :
    return False
  D[v] = len(V)
  V.append(v)
  return True

def pop(v) :
  if v not in D :
    return False
  i = D.pop(v)
  if i == len(V)-1 : # это последний элемент, берём и выкидываем
    V.pop()
  else : # переместим последний элемент на это место
    V[i] = V.pop()
    # и обновим хеш-таблицу
    D[V[i]] = i
  return True

R = random.Random()
def randvalue() : # случайный доступ
  return V[R.randint(0, len(V)-1)]

This comment wasn’t rated yet0
Сериализация дерева.

Вот чисто для того, чтобы разнообразить подходы.

Каким способом мы можем строить дерево? Например, последовательностью команд стековой машины
— NUL — положить на стек нулевую заглушку
— NODE(«sss») — взять со стека два узла, создать корневой узел со значением «sss» и поддеревьями, положить обратно на стек

Каждая команда занимает один бит оператора плюс, если надо, операнд. Но вряд ли мы будем ужимать до битов, — то есть, каждый оператор — это целый байт. Поэтому введём больше операторов:
— B(str) — узел-лист, без поддеревьев
— L(str) — узел с левым поддеревом
— R(str) — узел с правым поддеревом
— D(str) — узел с двумя поддеревьями

Сериализация — это восходящий обход дерева (если у нас дерево двусвязное, то он делается за линейное время и с константной памятью) и выдача соответствующих команд.
Десериализация — исполнение этих команд.

#-*- encoding:utf-8

# узел дерева - это тройка (строка, левое, правое)
# на вход подаётся корневой узел
def serialize(node) :
  v, l, r = node
  # наше дерево односвязное, поэтому спускаемся рекурсивно, фиг с ним.
  if l :
    for s in serialize(l) : yield s # это питонья идиома - монада списка, если кто не узнал ;)
  if r :
    for s in serialize(r) : yield s
  # пишем команду
  c = "DRLB"[(not l)*1 + (not r)*2] # немножко колдунства ;)
  yield c + repr(v)

def serialize_tree(node) :
  for s in serialize(node) : yield s
  yield "." # команда останова

def deserialize_tree(ss) :
  #ss = iter(ss) # гарантированно превратим ss в итератор
  nodes = []
  while True :
    cs = next(ss) # команда
    c = cs[0]
    if c == '.' :
      break
    v = eval(cs[1:]) # строка
    # интерпретируем:
    l, r = None,None
    if c == 'B' :
      pass
    elif c == 'L' :
      l = nodes.pop()
    elif c == 'R' :
      r = nodes.pop()
    elif c == 'D' :
      r = nodes.pop()
      l = nodes.pop()
    else :
      assert False, "bad command %s %s" % (repr(c), repr(v))
    nodes.append((v,l,r))
  assert len(nodes) == 1
  return nodes[0]

#################################################

# тестовое дерево
T = ('1\na a a', # строки могут содержать всё, что угодно
      ('"2"',None,None),
      ("'3'",
        ('4',None,None),
        ('5',None,None)))

print 'ORIGINAL:', T

# вот так это сериализуется в поток
with open('tree.txt', 'w') as f :
  for sss in serialize_tree(T) : print >>f, sss

# а вот так - в строку
S = '\n'.join(serialize_tree(T))
print S

# вот так десериализуется из строки
T1 = deserialize_tree(iter(S.splitlines()))
print 'FROM STR:', T1

# а вот так - из потока
with open('tree.txt') as f :
  T2 = deserialize_tree((s[:~0] for s in f))
print 'FROM TXT:', T2

This comment wasn’t rated yet0
nickolaym Хэй, спасибо за активность и решения :)
Ниже будет вариант, взятый с исходного ресурса.
This comment wasn’t rated yet0
Там будет достаточно одного стека, только поле данных должно содержать два поля: основное — собственно хранящееся значение и вспомогательное поле — значение минимума, которое было до текущего значения. Тогда минимум всегда хранится в ТОПовом элементе во вспомогательном поле, а все операции со стеком будут выполняться за константное время.
This comment wasn’t rated yet0
А, ну да, стек пар изоморфен моей паре стеков :)
This comment wasn’t rated yet0
Было бы полезно для каждой задачи указывать ссылку на LeetCode и список компаний, которые спрашивают этот вопрос (Список основных вопросов крупных компаний):

Тем более что текст задач 1 в 1 совпадает.
This comment wasn’t rated yet0
Радует, что вы решаете задачи :)
Ниже публикуем по одному решению с исходного ресурса. Текст оставили на английском, чтобы избежать недопонимания.

Atention! Spoiler!

1.Решение на Java с использованием одного стека:
class MinStack {
    int min = Integer.MAX_VALUE;
    Stack<Integer> stack = new Stack<Integer>();
    public void push(int x) {
        // only push the old minimum value when the current 
        // minimum value changes after pushing the new value x
        if(x <= min){          
            stack.push(min);
            min=x;
        }
        stack.push(x);
    }

    public void pop() {
        // if pop operation could result in the changing of the current minimum value, 
        // pop twice and change the current minimum value to the last minimum value.
        if(stack.pop() == min) min=stack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return min;
    }
}


2. Простое решение на Python
We just keep track of the index of the added elements, so when we remove them, we copy the last one into it.

From Python docs (https://wiki.python.org/moin/TimeComplexity) we know that list.append() takes O(1), both average and amortized. Dictionary get and set functions take O(1) average, so we are OK.

import random

class RandomizedSet(object):

    def __init__(self):
        self.nums, self.pos = [], {}
        
    def insert(self, val):
        if val not in self.pos:
            self.nums.append(val)
            self.pos[val] = len(self.nums) - 1
            return True
        return False
        

    def remove(self, val):
        if val in self.pos:
            idx, last = self.pos[val], self.nums[-1]
            self.nums[idx], self.pos[last] = last, idx
            self.nums.pop(); self.pos.pop(val, 0)
            return True
        return False
            
    def getRandom(self):
        return self.nums[random.randint(0, len(self.nums) - 1)]

# 15 / 15 test cases passed.
# Status: Accepted
# Runtime: 144 ms


3. Решение на C++
class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (root == nullptr) return "#";
        return to_string(root->val)+","+serialize(root->left)+","+serialize(root->right);
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        return mydeserialize(data);
    }
    TreeNode* mydeserialize(string& data) {
        if (data[0]=='#') {
            if(data.size() > 1) data = data.substr(2);
            return nullptr;
        } else {
            TreeNode* node = new TreeNode(helper(data));
            node->left = mydeserialize(data);
            node->right = mydeserialize(data);
            return node;
        }
    }
private:
    int helper(string& data) {
        int pos = data.find(',');
        int val = stoi(data.substr(0,pos));
        data = data.substr(pos+1);
        return val;
    }
};`
This comment wasn’t rated yet0
Sign up to leave a comment.

Your account

Sections

Information

Services

Support
© 2006–2024, Habr