Easiest JAVA BFS solution.


  • 0

    I know you guys have figured out different DP, DFS, static DP ways for this solution.
    Here I just want to share my easiest BFS solution

    public int numSquares(int n) {
    
        if (n <= 0) return 0;
        
        Queue<Integer> queue = new LinkedList<>();
        HashSet<Integer> set = new HashSet<>();
        queue.offer(n);
        
      
        int level = 1;
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            
            for (int j = 0; j < size; j++) {
                int curr = queue.poll();
                
                int ceiling = (int)Math.pow(curr, 0.5);
                if (ceiling * ceiling == curr) return res;
                
                for (int i = ceiling; i > 0; i--) {
                    if (set.add(curr - i * i)) {  //avoid duplicate calculation
                        queue.offer(curr - i * i);
                    }
                }
            }
            level++;
        }
        
        return res;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.