BFS beat 93% 60ms


  • 0
    F
    public class Point{
            int val;
            int remaining;
            Point(int val, int remaining) {
                this.val = val;
                this.remaining = remaining;
            }
        }
        public int numSquaresBfs(int n) {
            if (n < 2) return 1;
            Queue<Point> queue = new LinkedList<>();
            int layer = 1;
            for (int i = 1; i*i <= n; i++) {
                if (n == i*i) return layer;
                queue.offer(new Point(i, n-i*i));
            }
            
            Point p = null;
            while (!queue.isEmpty()) {
                layer++;
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    p = queue.poll();
                    for (int j = p.val; j*j <= p.remaining; j++) {
                        if (j*j == p.remaining) return layer++;
                        queue.offer(new Point(j, p.remaining-j*j));
                    }
                }
            }
            return layer++;
        }

Log in to reply
 

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