04 Explore00_Queen and BFS_Perfect Squares_Chapter02

Keywords: BFS Conclusion: BFS deep understanding: always think BFS as a graph from near node to far node. BFS, as the name, vivid。Breath First， (from near to far), so BFS is good at solving computative or evolution from basic base (ex: 0, 1)

Perfect Squares with C++ implement Notice： use perfect_squares twice (for(1,n){1->n}) to construct the graph

# Perfect Squares using BFS 
class Solution
{
public:
int NumSquares(int n)  {
    if (n <= 0)
        return 0;

    // perfect_squares contain all perfect square numbers whic
    // are small than or equal to name
    vector<int> perfect_squares;
    // cnt_perfect_squares[i - 1] = the least number of perfect
    // square numbers which sum to i.
    vector<int> cnt_perfect_squares(n);

    // get all the perfect squares numbers which are small than or equal to n.
    for (int i = 1; i * i <= n; i++)  {
        perfect_squares.push_back(i * i);
        cnt_perfect_squares[i*i - 1] = 1; 
    }

    // if n is a perfect square numbers. return 1 immediately
    if (perfect_squares.back() == n)  {
        return 1;
    }

    // Consider a graph which consists of number 0, 1,...,n as
    // its nodes. Node j is connected to node i via an edge if  
    // and only if either j = i + (a perfect square number) or 
    // i = j + (a perfect square number). Starting from node 0, 
    // do the breadth-first search. If we reach node n at step 
    // m, then the least number of perfect square numbers which 
    // sum to n is m. Here since we have already obtained the 
    // perfect square numbers, we have actually finished the 
    // search at step 1.
    queue<int> search_queue;
    for (auto& i: perfect_squares)  {
        search_queue.push(i);
    }

    int cur_cnt_perfect_squares = 1;
    while(!search_queue.empty())  {
        cur_cnt_perfect_squares++;

        int search_queue_size = search_queue.size();
        for(int i = 0; i < search_queue_size; i++)  {
            // start from 1(the smallest squares )
            int tmp = search_queue.front();
            // check the neighbors of node tmp which are the sum
            // of tmp and a perfect square number.
            for(auto& j: perfect_squares)  {
                if(tmp + j == n)  {
                    // we have reach node n.
                    return cur_cnt_perfect_squares;
                }
                else if((tmp + j < n) && (cnt_perfect_squares[tmp + j -1] == 0))  {
                    // if cnt_perfect_squares[tmp + j - 1] > 0, it means this is 
                    // not the first time that we visit this node and we should skip it 
                    cnt_perfect_squares[tmp + j - 1] = cur_cnt_perfect_squares;
                    search_queue.push(tmp + j);
                }
                else if(tmp + j > n)  {
                    // we don't need to consider the nodes whcih are greater than n
                    break;
                }
            } 
            search_queue.pop();
        }
    }

    return 0; 
}
};

Don't to reinvent the wheels, refer to leetcode_discussion/Summary of 4 different solutions (BFS, DP, static DP and mathematics)

zwkcoding / 100Days-Of-Leetcode

04 Explore00_Queen and BFS_Perfect Squares_Chapter02 #6