本次在线测试包含两道题目，难度跟通知时说明的一样，LeetCode中等难度。
由于题目相对简单，我就直接放题目，然后给出参考答案，虽然测试时都AC了，但我觉得大家可能还有更好的答案。
欢迎交流，提供更多有趣的优化算法。
No.1 勾股数元祖
题目描述：
也称为 “素勾股数” ，其有以下性质：
本题需要注意的是，
多组勾股数元祖请按照按a升序，b升序，最后c升序的方式输出。
源程序：
#include <stdio.h>#include <string.h>#include <stdlib.h>#include <unistd.h>#include <iostream>using namespace std;#include <math.h> /* 判断两个数字是否互质，返回值是1时表明互质，其它值则不互质 */int is_coprime(int src1,int src2){if(0 == src2)return src1;elsereturn is_coprime(src2,src1%src2);}void printResult(int a, int b, int c){//print the three number orderedlyif(a<b && b<c)printf("%d %d %d\n",a,b,c);else if(a>b && b>c)printf("%d %d %d\n",c,b,a);else if(b<c && a>c)printf("%d %d %d\n",b,c,a);elseprintf("%d %d %d\n",b,a,c);}int funcation(int N, int M){int countor = 0;int m = 0;if(0 < N && N < M)m = sqrt(M);elsereturn -1;for(int i = N; i <= M; i++){for(int j = i+1; j <= M; j++){for(int k = j+1; k <= M; k++){if(i*i + j*j == k*k) {if(1 == is_coprime(i,j) && 1 == is_coprime(i,k) && 1 == is_coprime(j,k)){countor++;printResult(i,j,k);//printf("%d %d %d\n",a,b,c);}}}}}if(countor == 0)printf("NA");return 0;}int main(){int N=0,M=0;scanf("%d %d",&N,&M);funcation(N, M);return 0;}备注：用了一种十分愚蠢的办法，不管时间复杂度多高，三七二十一来个遍历，所有问题都可以遍历到。我也是考试时没办法了，我在考虑用这个性质的时候，打印的结果总是不满足第二条，只通过了37.5%。无奈之下，我提交了这个垃圾的程序。
另外，本题目之前有原题，只不过他只要找到小于N的素勾股数的对数，因此这个性质就十分好用。欢迎大家给我的程序提提意见， 现在忙着毕业设计也没时间继续改进。
参考题目：华为机试——素勾股数
/**************************************************************** 题目：勾股数，是由三个正整数组成的数组；能符合勾股定理 a*a + b*b = c*c ，(a, b, c) 的正整数解。* 如果 (a, b, c) 是勾股数，它们的正整数倍数，也是勾股数。* 如果 (a, b, c) 互质，它们就称为素勾股数。* 给定正整数N， 计算出小于或等于N的素勾股数个数。* 输入描述：输一个正整数* 输出描述：素勾股数* 示例输入：10* 示例输出：1***************************************************************/#include <stdio.h>#include <string.h>#include <stdlib.h>#include <unistd.h> #include <math.h> /* 判断两个数字是否互质，返回值是1时表明互质，其它值则不互质 */int is_coprime(int src1,int src2){if(0 == src2)return src1;elsereturn is_coprime(src2,src1%src2);} int main(){int input=0;int i,j;int a,b,c;int countor=0;scanf("%d",&input);if(0 < input)m = sqrt(input);elsereturn -1;for(i=1;i<=input;i++){for(j=i+1;j<=input;j++){ a = j * j - i * i; b = 2 * i * j; c = i * i + j * j;if(c <= input){if(1 == is_coprime(a,b) && 1 == is_coprime(b,c) && 1 == is_coprime(a,c)){countor++;printf("a=%d,b=%d,c=%d\n",a,b,c);}}}}printf("%d\n",countor);return 0;} 这边还有cutter_point提供的java解决办法，供小伙伴们参考。
package y2020.interview.huawei.gougushu;import java.util.ArrayList;import java.util.List;import java.util.Scanner;/** * @Auther: xiaof * @Date: 2020/3/11 10:25 * @Description:勾股数元祖 素勾股数的个数 * * 勾股数，是由三个正整数组成的数组；能符合勾股定理 a*a + b*b = c*c ，(a, b, c) 的正整数解。如果 (a, b, c) 是勾股数， * 它们的正整数倍数，也是勾股数。如果 (a, b, c) 互质，它们就称为素勾股数。给定正整数N， 计算出小于或等于N的素勾股数个数。 * */public class Main { public static List solution(int n, int m) { List res = new ArrayList(); for (int a = n; a <= m - 2; ++a) { for (int b = a + 1; b <= m - 1; ++b) { //求c double c = Math.sqrt(Math.pow(a,2) + Math.pow(b,2)); long cz = (long) c; if (c - cz == 0 && c <= m && isPrim(a,b) && isPrim(a, (int) c) && isPrim(b, (int) c)) { res.add(new int[]{a, b, (int) c}); } else if (c > m) { break; } } } return res; } //判断a,b,c互质 public static boolean isPrim(int a, int b) { if(a < b) { int tmp = a; a = b; b = tmp; } int c; //辗转相除 while((c = a % b) != 0) { a = b; b = c; } return b == 1; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int m = scanner.nextInt(); List<int[]> res = solution(n, m); res.forEach(res1 -> { System.out.println(res1[0] + " " + res1[1] + " " + res1[2]); }); }}好了，第一题就算结束了。
No.2 磁盘大小比较
题目描述：磁盘的容量单位有M、G、T，其关系为 1T = 1000G、1G = 1000M，如样例所示先输入磁盘的个数，再依次输入磁盘的容量大小，然后按照从小到大的顺序对磁盘容量进行排序并输出。
输入样例：
320M1T3G输出样例：
20M3G1T这个代码我忘了保存，后来的程序如下：
#include <iostream>#include <string>#include <vector>#include <algorithm>using namespace std;int StrToInt(string str){ if (str[str.size() - 1] == 'M') { return stoi(str.substr(0, str.size() - 1)); } else if (str[str.size() - 1] == 'G') { return stoi(str.substr(0, str.size() - 1)) * 1000; } else if (str[str.size() - 1] == 'T') { return stoi(str.substr(0, str.size() - 1)) * 1000000; } return 0;}bool Compare(const string &strA, const string &strB){ int a = StrToInt(strA); int b = StrToInt(strB); // 升序排序 return a < b;}int main(void){ int n; while (cin >> n) { string str; vector<string> vec; while (n--) { cin >> str; vec.push_back(str); } sort(vec.begin(), vec.end(), Compare); for (auto i : vec) { cout << i << endl; } } return 0;}
同样地，我也找了拉格朗宇的Java源程序供大家参考。
package Huawei;import java.util.Scanner;/** * Created by xuzhenyu on 2020/1/5. */public class Test { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); String[] strings = new String[n]; for (int i = 0; i < n; i++) { strings[i] = scanner.next(); } String[] ruslutStrs = sort(strings); for (int i = 0; i <ruslutStrs.length ; i++) { System.out.println(ruslutStrs[i]); } } private static String[] sort(String[] strs) { for (int i = 0; i < strs.length - 1; i++) { for (int j = 0; j < strs.length - i - 1; j++) { // M G T if (compare(strs[j], strs[j + 1])) { String tem = strs[j]; strs[j] = strs[j+1]; strs[j+1] = tem; } } } return strs; } private static boolean compare(String str1, String str2){ int str1M = turnString(str1); int str2M = turnString(str2); return str1M>str2M; } private static int turnString(String str){ if("M".equals(String.valueOf(str.charAt(str.length()-1)))){ return Integer.parseInt(str.substring(0,str.length()-1)); } else if ("G".equals(String.valueOf(str.charAt(str.length()-1)))){ return Integer.parseInt(str.substring(0,str.length()-1))*1000; } else if ("T".equals(String.valueOf(str.charAt(str.length()-1)))){ return Integer.parseInt(str.substring(0,str.length()-1))*1000000; } return 0; };}推荐阅读：
[1] 数据结构与算法 | 你知道快速排序，那你知道它的衍生应用吗？Partition函数
[2] 数据结构与算法 | 数据结构中到底有多少种“树”？一文告诉你
[3] 数据结构与算法 | 二分查找：剑指offer53 在排序数组中查找数字
[4] 2020字节跳动秋招笔试题解析与代码分享（持续更新中）
关注微信公众号：迈微电子研发社，回复获取更多精彩内容。
△微信扫一扫关注「迈微电子研发社」公众号
知识星球：社群旨在分享AI算法岗的秋招/春招准备攻略（含刷题）、面经和内推机会、学习路线、知识题库等。
△扫码加入「迈微电子研发社」学习辅导群
评论留言