本次在线测试包含两道题目，难度跟通知时说明的一样，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;
else
return is_coprime(src2,src1%src2);
}
void printResult(int a, int b, int c)
{
//print the three number orderedly
if(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);
else
printf("%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);
else
return -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;
else
return 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);
else
return -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，如样例所示先输入磁盘的个数，再依次输入磁盘的容量大小，然后按照从小到大的顺序对磁盘容量进行排序并输出。
输入样例：
3
20M
1T
3G
输出样例：
20M
3G
1T
这个代码我忘了保存，后来的程序如下：
#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算法岗的秋招/春招准备攻略（含刷题）、面经和内推机会、学习路线、知识题库等。
△扫码加入「迈微电子研发社」学习辅导群
