2015-02-27 6 views
1

Я работаю над проблемой с Крекинг кодирвоание интервью, проблема +9,6 страница 110.Как построить футляр для n = 3 с использованием рекурсии снизу вверх?

Вот проблема:
Реализовать алгоритм для печати корректными (например, надлежащим образом открывались и закрывались комбинации п-пар . скобки Примеры
б (1) - "()"
б (2) - "(()),()()"
б (3) - «((())), (()())(),() (()),()()() «
Я пытаюсь использовать подход« снизу вверх », который автор обсуждает на стр. 107 -« Начнем с зная, как решить проблему для простого случая, например список с o один элемент и выяснить, как решить проблему для двух элементов, затем для трех элементов и т. д. Ключевым моментом здесь является, чтобы думать о том, как вы можете создать решение для одного случая от предыдущего случая»

Вот код, который я до сих пор

static void print(int n) { 
    print(n, new HashSet<String>(), "", ""); 
} 

static void print(int n, Set<String> combs, String start, String end) { 
    if(n == 0) { 
     if(!combs.contains(start + end)) { 
      System.out.print(start + end); 
      combs.add(start + end); 
     } 
    } else { 
     print(n-1, combs, "(" + start, end +")"); 
     System.out.print(", "); 
     print(n-1, combs, start, end + "()"); 
     System.out.print(", "); 
     print(n-1, combs, "()" + start, end); 
    } 
} 

Чтобы получить этот код, я работал от (1), b (1), b (1) « Этот код действительно работает для первых двух случаев. Я действительно борется с в третьем случае. Может ли кто-нибудь дать мне подсказку (не весь ответ, может быть обращен к задней части книги для этого), о том, как перейти от случая 2 к делу 3 или, другими словами, использовать случай 2, чтобы добраться до case 3? Как, как бы вы перешли от (()),()() до
((())), (()()), (())(),() (()),()()()? Не могли бы вы отказаться от шаблона, который вы видели от b (1) до b (2), потому что он не работает для b (2) - b (3)?

ответ

2

Спасибо Khanna111 за то, что я указал в своем первоначальном ответе, который был неполным и недочитал строковые шаблоны. В результате я обновил свой ответ соответственно.

Пожалуйста, подумайте о том, чтобы дать кредит Pham Trung за его ответ с правильной рекурсивной формулой. Мой ответ по существу тот же, что и у него, с небольшим разницей в том, как я формулирую построение шаблонов из более мелких суб-проблем (поскольку мне легче объяснить детали в моем подходе).

=================================================================================================================================================== ==========================

Решение Update

Для любого действительного шаблона s размера n, s падает точно один из следующих случаев:

  • Случай 1: sне может быть разделена на два действительных моделей меньший размер
  • Случай 2: sможет быть разделена на два действительных шаблонов меньшего размера

В случае 1, s должен иметь вид (_____), где _____ является допустимым шаблоном размера n - 1.Таким образом, в данном случае, для каждого действительного шаблона t размера n - 1, мы просто построить шаблон s путем конкатенации t с ( и ) в качестве префикса и суффикса, соответственно (т.е. s = (t)).

Для случая 2, мы можем разделить s в uv, где u и v оба являются действительными модели меньшего размера. В этом случае мы должны рассмотреть все возможные шаблоны u и v, где u может быть любым допустимым шаблоном размера i = 1, 2, ..., n - 1, а v может быть любым допустимым шаблоном размера n - i.

Когда n = 0, очевидно, что только пустая строка является допустимым шрифтом, поэтому у нас есть dp(0) = { "" } в качестве базового чехла. Полная реализация с кэшированием, чтобы улучшить производительность приводится ниже:

import java.util.HashMap; 
import java.util.HashSet; 
import java.util.Map; 
import java.util.Set; 

public class BalancingBrackets { 

    private static Map<Integer, Set<String>> dp = new HashMap<>(); 

    public static void main(String[] args) { 
     Set<String> result = compute(4); 

     boolean isFirst = true; 
     for (String s : result) { 
      if (isFirst) { 
       isFirst = false; 
       System.out.print(s); 
      } else { 
       System.out.print(", " + s); 
      } 
     } 
    } 

    private static Set<String> compute(Integer n) { 
     // Return the cached result if available 
     if (dp.containsKey(n)) { 
      return dp.get(n); 
     } 

     Set<String> set = new HashSet<>(); 

     if (n == 0) { 
      // This is the base case with n = 0, which consists only of the 
      // empty string 
      set.add(""); 
     } else if (n > 0) { 
      // For generating patterns in case 1 
      for (String s : compute(n - 1)) { 
       set.add("(" + s + ")"); 
      } 

      // For generating patterns in case 2 
      for (int i = 1; i < n; i++) { 
       Set<String> leftPatterns = compute(i); 
       Set<String> rightPatterns = compute(n - i); 

       for (String l : leftPatterns) { 
        for (String r : rightPatterns) { 
         set.add(l + r); 
        } 
       } 
      } 
     } else { 
      // Input cannot be negative 
      throw new IllegalArgumentException("Input cannot be negative."); 
     } 

     // Cache the solution to save time for computing large size problems 
     dp.put(n, set); 

     return set; 
    } 

} 
+0

С вашим алгоритмом как бы вы вынесете избыточность? – committedandroider

+0

. Один из подходов состоит в том, чтобы иметь внутренний хэшсет, который хранит строковый шаблон, который вы сгенерировали до сих пор, всякий раз, когда вы создаете новую строку шаблона, вы должны проверить, присутствует ли такая строка шаблона в hashset, отбросить ее, если необходимо – chiwangc

+0

Будет ли хороший Подход к вызову вашего перегруженного метода из моего в случае, если n> 1? Причина, по которой клиенту не нужно передавать эти данные. – committedandroider

3

Мы можем генерировать из Ь (п) б (п + 1), используя эту рекурсивную формулу:

  • (B (п - х)) Ь (х) с 0 = < < х = п

Таким образом, вы можете иметь все ваши комбинации перебирая всех x.

Код:

public static ArrayList<String> cal(int num){ 

    if(num == 0){ 
     ArrayList<String> list = new ArrayList(); 
     list.add(""); 
     return list; 
    }else{ 
     ArrayList<String>result = new ArrayList(); 
     for(int i = 0; i <= num - 1; i++){ 
      ArrayList<String> a = cal(i); 
      ArrayList<String> b = cal(num - 1 - i); 
      for(String x : a){ 
       for(String y : b){ 
        result.add("(" + x + ")" + y); 
       } 
      } 
     } 
     return result; 
    } 
} 

Входной сигнал: 3 Выход: ()()(),()(()), (())(), (()()), ((()))

Входной сигнал: 4 Выход: ()()()(),()()(()),()(())(),()(()()),()((())), (())()(), (())(()), (()())(), ((()))(), (()()()), (()(())), ((())()), ((()())), (((())))

+0

Что означает x? – committedandroider

+0

@committedandroider, например, если у нас есть 'n = 5',' x' может быть от 0 до 4, поэтому мы можем разделить 'n' на две части' x' и 'n - x', посмотреть код для больше информации, в коде 'x' есть' i' цикла for –

+0

Я запускал этот код для тестовых примеров 1, 2, 3, и он работал, но я до сих пор не понимаю, как у вас есть интуиция для этого. Скажем n = 2, тогда x может быть от 0 до 1. Тогда у вас есть комбинации (x, n-x) (0,2) и (1,1). Каково значение (0,2) и (1,1)? – committedandroider