Двоичные часы Leetcode - PullRequest
Новая
       8

Двоичные часы Leetcode

0 голосов
/ 06 мая 2018

Я пытаюсь решить проблему Binary Watch в LeetCode с помощью Backtracking.

Мой код ниже (не работает) 

public static void binaryWatchHelper(List<Integer>hours, List<Integer> mins, 
            int num , List<String> possibleTimes,int hoursSum,int minsSum) { 

        //System.out.println( num + " - " + hours + " - " + mins );

        if(num==0) {
            String m = minsSum <10?("0"+minsSum):""+minsSum; 
            possibleTimes.add(hoursSum +":"+m);
        }
        else {
            for(int i=0;i<(hours.size()+mins.size());i++) {

                if(i<hours.size()) {                        
                    int hr =hours.remove(i);
                    hoursSum+=hr;

                    if(hoursSum<=11)
                        binaryWatchHelper(hours, mins, num-1, possibleTimes, hoursSum, minsSum);

                    hours.add(i,hr);
                    hoursSum-=hr;

                } else {

                    int mi =mins.remove(i-hours.size());
                    minsSum+=mi;

                    if(minsSum<=59)
                        binaryWatchHelper(hours, mins, num-1, possibleTimes, hoursSum, minsSum);

                    mins.add(i-hours.size(),mi);
                    minsSum-=mi;                
                }
            }
        }       
    }

Я нашел приведенный ниже код (C ++) на странице обсуждения leetcode, и он работает нормально. 

void helper(vector<string>& res, pair<int, int> time, int num, int start_point) {
        if (num == 0) {
            res.push_back(to_string(time.first) +  (time.second < 10 ?  ":0" : ":") + to_string(time.second));
            return;
        }
        for (int i = start_point; i < hour.size() + minute.size(); i ++)
            if (i < hour.size()) {    
                time.first += hour[i];
                if (time.first < 12)     helper(res, time, num - 1, i + 1);     // "hour" should be less than 12.
                time.first -= hour[i];
            } else {     
                time.second += minute[i - hour.size()];
                if (time.second < 60)    helper(res, time, num - 1, i + 1);     // "minute" should be less than 60.
                time.second -= minute[i - hour.size()];
            }
    }

Вышеприведенный алгоритм c ++ очень похож на то, что я написал. Но мой код не работает. Может кто-нибудь объяснить мне, что я скучаю?

Вместо того, чтобы передавать startIndex, я удаляю элемент. Но почему мой код не работает?

Я попытался распечатать трассировку стека вызовов и, конечно, они очень разные. Кто-нибудь может указать мне, что мне не хватает?

Я получаю неправильный вывод.

Мой код Вывод для n = 2 

[3:00, 5:00, 9:00, 1:01, 1:02, 1:04, 1:08, 1:16, 1:32, 3:00, 6:00, 10:00, 2:01, 2:02, 2:04, 2:08, 2:16, 2:32, 5:00, 6:00, 4:01, 4:02, 4:04, 4:08, 4:16, 4:32, 9:00, 10:00, 8:01, 8:02, 8:04, 8:08, 8:16, 8:32, 1:01, 2:01, 4:01, 8:01, 0:03, 0:05, 0:09, 0:17, 0:33, 1:02, 2:02, 4:02, 8:02, 0:03, 0:06, 0:10, 0:18, 0:34, 1:04, 2:04, 4:04, 8:04, 0:05, 0:06, 0:12, 0:20, 0:36, 1:08, 2:08, 4:08, 8:08, 0:09, 0:10, 0:12, 0:24, 0:40, 1:16, 2:16, 4:16, 8:16, 0:17, 0:18, 0:20, 0:24, 0:48, 1:32, 2:32, 4:32, 8:32, 0:33, 0:34, 0:36, 0:40, 0:48]

Вывод кода C ++: 

[3:00, 5:00, 9:00, 1:01, 1:02, 1:04, 1:08, 1:16, 1:32, 6:00, 10:00, 2:01, 2:02, 2:04, 2:08, 2:16, 2:32, 4:01, 4:02, 4:04, 4:08, 4:16, 4:32, 8:01, 8:02, 8:04, 8:08, 8:16, 8:32, 0:03, 0:05, 0:09, 0:17, 0:33, 0:06, 0:10, 0:18, 0:34, 0:12, 0:20, 0:36, 0:24, 0:40, 0:48]

Моя трассировка звонка для num = 2 

2 - [1, 2, 4, 8] - [1, 2, 4, 8, 16, 32]
  1 - [2, 4, 8] - [1, 2, 4, 8, 16, 32]
    0 - [4, 8] - [1, 2, 4, 8, 16, 32]
    0 - [2, 8] - [1, 2, 4, 8, 16, 32]
    0 - [2, 4] - [1, 2, 4, 8, 16, 32]
    0 - [2, 4, 8] - [2, 4, 8, 16, 32]
    0 - [2, 4, 8] - [1, 4, 8, 16, 32]
    0 - [2, 4, 8] - [1, 2, 8, 16, 32]
    0 - [2, 4, 8] - [1, 2, 4, 16, 32]
    0 - [2, 4, 8] - [1, 2, 4, 8, 32]
    0 - [2, 4, 8] - [1, 2, 4, 8, 16]
  1 - [1, 4, 8] - [1, 2, 4, 8, 16, 32]
    0 - [4, 8] - [1, 2, 4, 8, 16, 32]
    0 - [1, 8] - [1, 2, 4, 8, 16, 32]
    0 - [1, 4] - [1, 2, 4, 8, 16, 32]
    0 - [1, 4, 8] - [2, 4, 8, 16, 32]
    0 - [1, 4, 8] - [1, 4, 8, 16, 32]
    0 - [1, 4, 8] - [1, 2, 8, 16, 32]
    0 - [1, 4, 8] - [1, 2, 4, 16, 32]
    0 - [1, 4, 8] - [1, 2, 4, 8, 32]
    0 - [1, 4, 8] - [1, 2, 4, 8, 16]
  1 - [1, 2, 8] - [1, 2, 4, 8, 16, 32]
    0 - [2, 8] - [1, 2, 4, 8, 16, 32]
    0 - [1, 8] - [1, 2, 4, 8, 16, 32]
    0 - [1, 2, 8] - [2, 4, 8, 16, 32]
    0 - [1, 2, 8] - [1, 4, 8, 16, 32]
    0 - [1, 2, 8] - [1, 2, 8, 16, 32]
    0 - [1, 2, 8] - [1, 2, 4, 16, 32]
    0 - [1, 2, 8] - [1, 2, 4, 8, 32]
    0 - [1, 2, 8] - [1, 2, 4, 8, 16]
  1 - [1, 2, 4] - [1, 2, 4, 8, 16, 32]
    0 - [2, 4] - [1, 2, 4, 8, 16, 32]
    0 - [1, 4] - [1, 2, 4, 8, 16, 32]
    0 - [1, 2, 4] - [2, 4, 8, 16, 32]
    0 - [1, 2, 4] - [1, 4, 8, 16, 32]
    0 - [1, 2, 4] - [1, 2, 8, 16, 32]
    0 - [1, 2, 4] - [1, 2, 4, 16, 32]
    0 - [1, 2, 4] - [1, 2, 4, 8, 32]
    0 - [1, 2, 4] - [1, 2, 4, 8, 16]
  1 - [1, 2, 4, 8] - [2, 4, 8, 16, 32]
    0 - [2, 4, 8] - [2, 4, 8, 16, 32]
    0 - [1, 4, 8] - [2, 4, 8, 16, 32]
    0 - [1, 2, 8] - [2, 4, 8, 16, 32]
    0 - [1, 2, 4] - [2, 4, 8, 16, 32]
    0 - [1, 2, 4, 8] - [4, 8, 16, 32]
    0 - [1, 2, 4, 8] - [2, 8, 16, 32]
    0 - [1, 2, 4, 8] - [2, 4, 16, 32]
    0 - [1, 2, 4, 8] - [2, 4, 8, 32]
    0 - [1, 2, 4, 8] - [2, 4, 8, 16]
  1 - [1, 2, 4, 8] - [1, 4, 8, 16, 32]
    0 - [2, 4, 8] - [1, 4, 8, 16, 32]
    0 - [1, 4, 8] - [1, 4, 8, 16, 32]
    0 - [1, 2, 8] - [1, 4, 8, 16, 32]
    0 - [1, 2, 4] - [1, 4, 8, 16, 32]
    0 - [1, 2, 4, 8] - [4, 8, 16, 32]
    0 - [1, 2, 4, 8] - [1, 8, 16, 32]
    0 - [1, 2, 4, 8] - [1, 4, 16, 32]
    0 - [1, 2, 4, 8] - [1, 4, 8, 32]
    0 - [1, 2, 4, 8] - [1, 4, 8, 16]
  1 - [1, 2, 4, 8] - [1, 2, 8, 16, 32]
    0 - [2, 4, 8] - [1, 2, 8, 16, 32]
    0 - [1, 4, 8] - [1, 2, 8, 16, 32]
    0 - [1, 2, 8] - [1, 2, 8, 16, 32]
    0 - [1, 2, 4] - [1, 2, 8, 16, 32]
    0 - [1, 2, 4, 8] - [2, 8, 16, 32]
    0 - [1, 2, 4, 8] - [1, 8, 16, 32]
    0 - [1, 2, 4, 8] - [1, 2, 16, 32]
    0 - [1, 2, 4, 8] - [1, 2, 8, 32]
    0 - [1, 2, 4, 8] - [1, 2, 8, 16]
  1 - [1, 2, 4, 8] - [1, 2, 4, 16, 32]
    0 - [2, 4, 8] - [1, 2, 4, 16, 32]
    0 - [1, 4, 8] - [1, 2, 4, 16, 32]
    0 - [1, 2, 8] - [1, 2, 4, 16, 32]
    0 - [1, 2, 4] - [1, 2, 4, 16, 32]
    0 - [1, 2, 4, 8] - [2, 4, 16, 32]
    0 - [1, 2, 4, 8] - [1, 4, 16, 32]
    0 - [1, 2, 4, 8] - [1, 2, 16, 32]
    0 - [1, 2, 4, 8] - [1, 2, 4, 32]
    0 - [1, 2, 4, 8] - [1, 2, 4, 16]
  1 - [1, 2, 4, 8] - [1, 2, 4, 8, 32]
    0 - [2, 4, 8] - [1, 2, 4, 8, 32]
    0 - [1, 4, 8] - [1, 2, 4, 8, 32]
    0 - [1, 2, 8] - [1, 2, 4, 8, 32]
    0 - [1, 2, 4] - [1, 2, 4, 8, 32]
    0 - [1, 2, 4, 8] - [2, 4, 8, 32]
    0 - [1, 2, 4, 8] - [1, 4, 8, 32]
    0 - [1, 2, 4, 8] - [1, 2, 8, 32]
    0 - [1, 2, 4, 8] - [1, 2, 4, 32]
    0 - [1, 2, 4, 8] - [1, 2, 4, 8]
  1 - [1, 2, 4, 8] - [1, 2, 4, 8, 16]
    0 - [2, 4, 8] - [1, 2, 4, 8, 16]
    0 - [1, 4, 8] - [1, 2, 4, 8, 16]
    0 - [1, 2, 8] - [1, 2, 4, 8, 16]
    0 - [1, 2, 4] - [1, 2, 4, 8, 16]
    0 - [1, 2, 4, 8] - [2, 4, 8, 16]
    0 - [1, 2, 4, 8] - [1, 4, 8, 16]
    0 - [1, 2, 4, 8] - [1, 2, 8, 16]
    0 - [1, 2, 4, 8] - [1, 2, 4, 16]
    0 - [1, 2, 4, 8] - [1, 2, 4, 8]

C ++ код вызова трассировки: 

2 - [1, 2, 4, 8] - [1, 2, 4, 8, 16, 32]
  1 - [2, 4, 8] - [1, 2, 4, 8, 16, 32]
  0 - [4, 8] - [1, 2, 4, 8, 16, 32]
  0 - [8] - [1, 2, 4, 8, 16, 32]
  0 - [] - [1, 2, 4, 8, 16, 32]
  0 - [] - [2, 4, 8, 16, 32]
  0 - [] - [4, 8, 16, 32]
  0 - [] - [8, 16, 32]
  0 - [] - [16, 32]
  0 - [] - [32]
  0 - [] - []
  1 - [4, 8] - [1, 2, 4, 8, 16, 32]
  0 - [8] - [1, 2, 4, 8, 16, 32]
  0 - [] - [1, 2, 4, 8, 16, 32]
  0 - [] - [2, 4, 8, 16, 32]
  0 - [] - [4, 8, 16, 32]
  0 - [] - [8, 16, 32]
  0 - [] - [16, 32]
  0 - [] - [32]
  0 - [] - []
  1 - [8] - [1, 2, 4, 8, 16, 32]
  0 - [] - [2, 4, 8, 16, 32]
  0 - [] - [4, 8, 16, 32]
  0 - [] - [8, 16, 32]
  0 - [] - [16, 32]
  0 - [] - [32]
  0 - [] - []
  1 - [] - [1, 2, 4, 8, 16, 32]
  0 - [] - [2, 4, 8, 16, 32]
  0 - [] - [4, 8, 16, 32]
  0 - [] - [8, 16, 32]
  0 - [] - [16, 32]
  0 - [] - [32]
  0 - [] - []
  1 - [] - [2, 4, 8, 16, 32]
  0 - [] - [4, 8, 16, 32]
  0 - [] - [8, 16, 32]
  0 - [] - [16, 32]
  0 - [] - [32]
  0 - [] - []
  1 - [] - [4, 8, 16, 32]
  0 - [] - [8, 16, 32]
  0 - [] - [16, 32]
  0 - [] - [32]
  0 - [] - []
  1 - [] - [8, 16, 32]
  0 - [] - [16, 32]
  0 - [] - [32]
  0 - [] - []
  1 - [] - [16, 32]
  0 - [] - [32]
  0 - [] - []
  1 - [] - [32]
  0 - [] - []
  1 - [] - []

Спасибо.

1 Ответ

0 голосов
/ 19 мая 2018

Подход к решению этой проблемы является излишним. Вы можете решить эту проблему с помощью некоторой техники манипуляции с битами.

Точка наблюдения

Общее количество битов, используемых для обозначения часа и минуты, должно быть равно переданному аргументу n.

Тогда у вас есть 0 - 11 часов и 0 - 59 минут. Используя два цикла for и выбирая только часы h и минуты m, для которых сумма установленных битов равна n, вы можете сделать свое решение намного элегантнее и быстрее. Цель этой проблемы также состоит в том, чтобы проверить свои навыки манипуляции с битами. 

    public List<String> readBinaryWatch(int n) {
        List<String> ret = new ArrayList<>();
        for(int h = 0; h < 12; h++) {
            for(int m = 0; m < 60; m++) {
                if(Integer.bitCount(h) + Integer.bitCount(m) == n) { // Checking whether the current h and m combination is a valid result. 
                   //If the sum of their set bits is equal to nthen the combination is a valid result and add that combination to result
                    ret.add(String.format("%d:%02d",h,m));
                }
            }
        }
        return ret;
    }
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Похожие темы

...