Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
Example 1:
Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4.Example 2:
Input: n = 13 Output: 2 Explanation: 13 = 4 + 9.-----------------------------------------------------------------------------这个题可以用BFS，不过要注意排除重复的。C++代码： class Solution { public: int numSquares(int n) { if(n == 0) return 0; queue<pair<int,int> > q; q.push(make_pair(n,1)); vector<bool> vis(n+1,false); //用这个来避免把重复的数加进队列。 vis[n] = true; while(!q.empty()){ int num = q.front().first; int s = q.front().second; q.pop(); if(num == 0) return 0; for(int i = 1; num - i*i >=0 ; i++){ int ans = num - i*i; if(ans == 0) return s; if(!vis[ans]){ q.push(make_pair(ans,s+1)); vis[ans] = true; } } } return 0; } };
转载于:https://www.cnblogs.com/Weixu-Liu/p/10770472.html
相关资源：JAVA上百实例源码以及开源项目