Вопрос о LeetCode 279. Идеальные квадраты - PullRequest
Новая
       8

Вопрос о LeetCode 279. Идеальные квадраты

0 голосов
/ 01 января 2019

Если задано положительное целое число n, найдите наименьшее число совершенных чисел (например, 1, 4, 9, 16, ...), сумма которых равна n.

Пример 1:

Вход: n = 12 Выход: 3 Объяснение: 12 = 4 + 4 + 4.

Пример 2:

Вход: n = 13 Выход: 2 Объяснение: 13 = 4 + 9. 

import java.util.*;

public class Solution {
    public int numSquares(int n) {
        int i = 1;
        int ret = Integer.MAX_VALUE;
        while(i * i < (n / 2)) {
            int start = i * i;
            int step = BFS(start,n);
            if(step < ret)
                ret = step;         
            i++;
      }

        return ret;
    }

    public int BFS(int start, int n) {
        int step = 0;
        LinkedList<Integer> queue = new LinkedList<Integer>();
        queue.offer(start);
        while(!queue.isEmpty()){
             int node = queue.poll();
             step++;
             if(node == n)
                 break;
             for(int k=1;k*k <= n;k++){
                 if(k*k <= n)
                 queue.offer(k * k + node); 
                 if(node + k*k == n)
                     return step + 1;
             }          
        }
        return step;
    }


}

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

1 Ответ

0 голосов
/ 01 января 2019

ИМХО, я попытаюсь обновить значение step, обнаружив некоторые marker между различными levels в процедуре BFS, которые могут сказать нам, что мы достигли конца предыдущего уровня и собираемсяна следующий уровень.Я обычно использую элемент null как этот marker.

См. Мой код с комментариями, который был принят: 

public class Solution {
    public int numSquares(int n) {
        Queue<Integer> queue=new LinkedList();
        queue.add(n);
        queue.add(null);//a null element to show the gap between two levels,i.e., the step
        int res=1;
        while(true){
            Integer i=queue.element();

            if(queue.size()!=1&&i==null){// we are hitting the marker
                queue.remove();
                res++;//i.e., step+1
                queue.add(null);//think about why we need add an additional marker here.
            }else{
                Integer sqrt=(int)Math.round(Math.sqrt(i));
                if(sqrt*sqrt==i){
                    break;
                }else{
                    queue.remove();
                    for(int j=sqrt;1<=j;j--){
                        if(0<i-j*j)
                            queue.add(i-j*j);
                    }
                }
            }
        }
        return res;
    }
}

PS, как указано:

Большинство стандартных библиотечных заголовков уже включены автоматически для вашего удобства.

Поэтому мы не делаем import java.util.* и код может компилироваться.

...