工商银行笔试编程题思路

我晕了，要求从小到大输出，我从大到小输出了

先从可以容纳的最大平方数开始，然后递减遍历。

跟楼上一样，从最大递减

开个跟取整再开跟取整

暴力写法写到一半时间到了，凉凉😂

leetcode279，要是知道四平方定理就好了

大概什么时候出笔试 结果啊

public class Main {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int n = sc.nextInt();         // 若n自身就是一个完全平方数         int tempNum = (int)(Math.sqrt(n));         if (tempNum * tempNum == n) {             System.out.println(n);             return ;         }         // 键盘输入的n不是完全平方数         // 布尔变量flag标识n可否由若干个(不重复的)完全平方数相加得到         boolean flag = false;         Set<Integer> set = new HashSet<>();         while (n >= 1) {             // 对n开方             int temp = (int)(Math.sqrt(n));             if (temp * temp == n) {                 // 构成n的若干完全平方数，是不允许重复的。否则也就不可能输出NA了.                 // 比如n，如果允许完全平方数重复，它肯定可以由n个1相加得到，不可能输出NA                 if (set.contains(n)) {                     break;                 }                          flag = true;             }             set.add(temp * temp);             n -= temp * temp;         }         if (flag) {             List<Integer> list = new ArrayList<>(set);             // 排序             Collections.sort(list);             for (int i = 0; i < list.size(); i++) {                 if (i != list.size() - 1) {                     System.out.print(list.get(i) + " ");                 } else {                     System.out.println(list.get(i));                 }             }         }         if (!flag) {             System.out.println("NA");         }     } } 楼主可以参考下我的代码，写得不一定优雅、简洁，但我自己测试的时候，能通过绝大多数样例。 存在问题：样例输入41，我的输出是1 4 36，正确输出应该是16 25 。 我正在review代码，寻求将这个问题解决，如果有老哥看出问题所在，请指点一下，谢谢。

我不知道有没有人和我想法一样，就是开方取余，对余数再开方，就一直循环到余数为0😂😂😂

虽然给了NA的输出，但是题干里没说完全平方数不能重复啊。。

#include<set> #include<iostream> #include<vector> using namespace std; int numSquares(int n)  {//找出n所组成的最小的完全平方个数 while(n%4==0) n/=4;     if(n%8 == 7) return 4;     for(int a = sqrt(n); a > 0; --a)     {         int b = sqrt(n-a*a);         if(a*a+b*b == n) return !b? 1 : 2;     }     return 3; } set<int> get_data(int n){//获取每个完全平方数 set<int> data; for(int i = 0; i<n; ++i){ data.insert(i*i); } return data; } vector<int> get_out(set<int> data, int n, int m){//遍历，找出符合要求的完全平方数 set<int> ::iterator it = data.begin(); it = data.lower_bound(n); vector<int> out_o; int p = m; while(p--){ --it; out_o.clear(); set<int> ::iterator it1 = it; int a,s = 0,s1=0; while(it1!=data.begin()){ a = *it1; s += a; if(s<n){ out_o.push_back(a); --it1; } else if (s>n) { s -= a; --it1; } else{ out_o.push_back(a); break; } if(out_o.size()>m) break; } int len = out_o.size(); for(int i = 0; i<len; ++i) s1 += out_o[i]; if(s1==n && len==m) break; } return out_o; } int main() { int n; while(cin>>n){ set<int> data; data = get_data(n);//集合中存放每个与下标对应的完全平方数 int m = numSquares(n);//获取其和为n的最小的完全平方数的个数 int s = 0; vector<int> out_o = get_out(data, n, m);//得到所求的完全平方数 for(int i = out_o.size()-1; i>=0; --i){ s += out_o[i]; } if(s==n){ for(int i = out_o.size()-1; i>=0; --i) cout<<out_o[i]<<" "; } else cout<<"NA"; cout<<endl; } return 0; } 我用了另外一种思路，这种方法既能保证从小到大又能是输出的个数最小，但是方法不是很简便，欢迎有更好思路的小伙伴可以留言评论。