Same solution with BFS, python pass while Java MLE, still cannot figure out what's wrong


  • 0
    H
    import math
    class Solution(object):
        def numSquares(self, n):
    
           queue = [n]
            step = 0
            while queue:
                next = []
                while queue:
                    start = queue.pop(0)
                    for i in range(int(math.sqrt(start)), 0, -1):
                        var = i * i
                        if var == start:
                            return step + 1
                        next.append(start - var)
                step += 1
                queue = next
    
    
    public class Solution {
        public int numSquares(int n) {
            int step = 0;
            Deque<Integer> queue = new LinkedList<>();
            queue.offer(n);
            Deque<Integer> next = new LinkedList<>();
            while (!queue.isEmpty()) {
                next.clear();
                while (!queue.isEmpty()) {
                    int tmp = queue.poll();
                    for (int i = (int) Math.sqrt(tmp); i > 0; i--) {
                        if (tmp == i * i) return step + 1;
                        next.offer(tmp - i * i);
                    }
                }
                step++;
                queue = new LinkedList<>(next);
            }
            return 0;
        }
    }

Log in to reply
 

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