Java BDF 88 ms


  • 0
    A
    public int numSquares(int n) {
        
        int level = 0;
        
        LinkedList<Integer> current = new LinkedList<>();
        LinkedList<Integer> next = new LinkedList<>();
        
        Set<Integer> visited = new HashSet<>();
        
        current.add(n);
        
        while (!current.isEmpty()) {
            
            int carry = current.poll();
            
            int i = 0;
            if (!visited.contains(carry)) {
                while (true) {
                    int nextCarry = carry - perfectSquare(i++);
                    if (nextCarry > 0) {
                        // Add at last position in next level
                        next.addLast(nextCarry);
                    } else if (nextCarry == 0) {
                        // Found
                        return level + 1;
                    } else {
                        // Eliminated
                        break;
                    }
                }
            }
            
            visited.add(carry);
            
            if (current.isEmpty()) {
                level ++;
                current = next;
                next = new LinkedList<>();
            }
        }
        
        // No match
        return 0;
    }
    
    public int perfectSquare(int i) {
        return (1 + i) * (1 + i);
    }

  • 0

    Nice solution. I think it is the same process as dp solution after thinking a while. Better use one queue to save some space.

    public int numSquares(int n) {
    Queue<Integer> queue = new LinkedList<Integer>();
    HashSet<Integer> set = new HashSet<Integer>();
    queue.offer(n);
    int count = 1;
    while (!queue.isEmpty()) {
    int size = queue.size();
    for (int i = 0; i < size; i++) {
    int curr = queue.poll();
    if (!set.contains(curr)) {
    for (int j = 1; curr - j * j >= 0; j++) {
    int next = curr - j * j;
    if (next > 0) {
    queue.offer(next);
    } else {
    return count;
    }
    }
    }
    set.add(curr);
    }
    count++;
    }
    return 0;
    }


Log in to reply
 

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