华为研发编程测试题（四）试题及答案参考_华为开发评测题

本次在线测试包含两道题目，难度跟通知时说明的一样，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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

备注：用了一种十分愚蠢的办法，不管时间复杂度多高，三七二十一来个遍历，所有问题都可以遍历到。我也是考试时没办法了，我在考虑用这个性质的时候，打印的结果总是不满足第二条，只通过了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;
}
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

这边还有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]);
        });

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

好了，第一题就算结束了。

No.2 磁盘大小比较

题目描述：
磁盘的容量单位有M、G、T，其关系为 1T = 1000G、1G = 1000M，如样例所示先输入磁盘的个数，再依次输入磁盘的容量大小，然后按照从小到大的顺序对磁盘容量进行排序并输出。

输入样例：

3
20M
1T
3G
1
2
3
4

输出样例：

20M
3G
1T
1
2
3

这个代码我忘了保存，后来的程序如下：

#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

同样地，我也找了拉格朗宇的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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

推荐阅读：

[1] 数据结构与算法 | 你知道快速排序，那你知道它的衍生应用吗？Partition函数

[2] 数据结构与算法 | 数据结构中到底有多少种“树”？一文告诉你

[3] 数据结构与算法 | 二分查找：剑指offer53 在排序数组中查找数字

[4] 2020字节跳动秋招笔试题解析与代码分享（持续更新中）

关注微信公众号：迈微电子研发社，回复获取更多精彩内容。

△微信扫一扫关注「迈微电子研发社」公众号

知识星球：社群旨在分享AI算法岗的秋招/春招准备攻略（含刷题）、面经和内推机会、学习路线、知识题库等。

△扫码加入「迈微电子研发社」学习辅导群