Блог

Проблема заключается в следующем:

Наш вход-это массив из 14 чисел, а наш вывод-является ли это выигрышной комбинацией. Чтобы рука была выигрышной, ее номера должны быть разделены на группы по следующим правилам:

1. Каждая группа из 3 человек должна состоять из одинаковых чисел или прямой (111 или 123).
2. Нам разрешено иметь только 1 пару одинаковых чисел (22-это нормально, но 45-нет).

Например:

 [1,1,1,2,2,2,3,3,3,4,4,4,5,5]: True
[1,1,1,2,2,2,3,3,3,4,4,4,5,6]: False
[1,1,2,2,3,3,4,4,4,6,6,6,8,8]: True
 

Я написал следующее решение проблемы, используя метод обратного отслеживания:

Примечание: Игнорируйте все случаи seen , когда это является частью запоминания второй части моего вопроса ниже.

 def is_winning_hand(hand):
  hand.sort()
  seen = set()
  return is_winning_hand_step(hand, True, seen)
  
def is_winning_hand_step(hand, can_take_two, seen):
  if len(hand) == 0:
    return True
    
  if len(hand) == 1:
    return False
    
  if str(hand) str(can_take_two) in seen:
    return False
    
  if can_take_two:
    valid, new_hand = take_two(hand)
    if valid:
      if is_winning_hand_step(new_hand, False, seen):
        return True
    
  if len(hand) >= 3:
    valid, new_hand = take_three(hand)
    if valid:
      if is_winning_hand_step(new_hand, can_take_two, seen):
        return True
          
    valid, new_hand = take_straight(hand)
    if valid:
      if is_winning_hand_step(new_hand, can_take_two, seen):
        return True
        
  seen.add(str(new_hand) str(can_take_two))
  return False

def take_two(hand):
  if hand[0] == hand[1]:
    return True, hand[2:]
  else:
    return False, None
    
def take_three(hand):
  if hand[0] == hand[1] and hand[1] == hand[2]:
    return True, hand[3:]
  else:
    return False, None

def take_straight(hand):
  cnt = 1
  last_val = hand[0]
  indices = set([0])
  
  for i in xrange(1, len(hand)):
    if hand[i] == last_val:
      continue
    elif hand[i] == last_val   1:
      cnt  = 1
      indices.add(i)
      last_val = hand[i]
      if cnt == 3:
        return True, [x for j, x in enumerate(hand) if j not in indices]
    else:
      return False, None
      
  return False, None
 

Теперь я пытаюсь выяснить, какова временная сложность этой проблемы.
Давайте предположим, что входные данные уже отсортированы для нас, так что оставьте это в стороне O(N log N) .

Я предполагаю, что, поскольку на каждом шаге у меня есть потенциальное разделение на 3 ветви, сложность заключается O(3^N) в том, что N должно быть длиной входного массива. В нашем случае это всегда массив длиной 14, но я говорю об общем случае. Я прав?

На следующем шаге я добавил запоминание к своему решению. Что мы можем сказать о сложности времени сейчас? Благодаря запоминанию я избегаю снова и снова решать одни и те же подзадачи, так что это делает это O(N) решением?