Bdtjtk

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 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;

    }





}

I have problems updating the step value. I can't come up with a solution how to update the step value. Can anyone help?

IMHO, I will try to update the step value, by detect some marker between different levels in the BFS procedure, who can tell us that we are hitting the end of previous level and are going into the next level. I usually employ a null element as this marker.

See my code with comments, which has been accepted:

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,as stated:

Most standard library headers are already included automatically for your convenience.

So we don't do import java.util.* and the code can compile.