华为2020年初试编程

Posted on

2020年应届生华为初试笔试编程题三道（附思路及解法）。

问题1（难度：* ）

三角形周长为p的直角三角形共有几个（边长为整数）？

思路：

  • 周长为3、4、5或者周长为4、3、5为同一三角形，枚举时设置三角形边长依次从小到大。
  • 等边直角三角形不可能存在，因为不存在直角三角形的三边长都为整数。
  • 第一条边长度i<=p/3,第二条边长度j<=(p-i)/2，第三边长度p-i-j。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;

public class Q1 {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        while (in.ready()) {
            int p = Integer.parseInt(in.readLine());
            int res = 0;  //记录直角三角形个数
            for (int i = 1; i <= p/3; i++) {
                for (int j = i; j <= (p - i)/2; j++) {
                    if (i * i + j * j == (p - i - j) * (p - i - j)) {
                        res++;
                    }
                }
            }
            System.out.println(res);
        }
        in.close();
    }
}

问题2（难度：*** ）

5*5的矩阵给6个数是否相邻（输入包含多个算例）。

思路：

  • 广度优先搜索(BFS)，记录与任一数相邻的总数是否为6

实现代码

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
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int res;
    public static void main(String[] args) throws IOException {
        res=0;
        int[][] mem = {{1, 2, 3, 4, 5}, {11, 12, 13, 14, 15}, {21, 22, 23, 24, 25}, {31, 32, 33, 34, 35}, {41, 42, 43, 44, 45}};
        //5*5的数据t_mem记录对应位置是否存在，存在为1，不存在为0
        int[][] t_mem = new int[5][5];

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        while (in.ready()) {
            String[] strings = in.readLine().split(" ");
            int[] nums = new int[6];
            for (int i = 0; i < 6; i++) {
                nums[i] = Integer.parseInt(strings[i]);
            }
            //初始化t_mem
            for (int i = 0; i < 6; i++) {
                t_mem[nums[i] / 10][nums[i] % 10 - 1] = 1;
            }
            int i_fir = 0;
            int j_fir = 0;
            //初始化第一次出现数字的位置
            for (int i = 0; i < 5; i++) {
                for (int j = 0; j < 5; j++) {
                    if (t_mem[i][j] == 1) {
                        i_fir = i;
                        j_fir = j;
                        break;
                    }
                }
            }
            //BFS遍历，记录与第一个数字相邻的数字
            bfs(i_fir, j_fir, t_mem);
            //是否共有6个数相邻
            if(res==6)
                System.out.println(1);
            else
                System.out.println(0);

        }
        in.close();
    }

    /*
    *遍历上下左右四个方向
    */
    public static void bfs(int i_fir, int j_fir, int[][] t_mem) {
        if (t_mem[i_fir][j_fir] == 1) {
            res++;
            //已经搜索过，该位置内容置0
            t_mem[i_fir][j_fir] = 0;
            if (i_fir <= 3)
                bfs(i_fir + 1, j_fir, t_mem);
            if (i_fir > 0)
                bfs(i_fir - 1, j_fir, t_mem);
            if (j_fir <= 3)
                bfs(i_fir, j_fir + 1, t_mem);
            if (j_fir > 0)
                bfs(i_fir, j_fir - 1, t_mem);
        }
    }
}

问题3（难度：** ）

两个等长字符串最少去除几个字母相同？

思路

  • dp数组，可以将问题转化为求解字符串最长字串的问题。
  • dp数组第一行字符串在某索引处出现与另一字符串第一个字母相同的情况，第一行在该索引之后全部置1，第一列同理。
  • 字符串1第第j个字母与字符串2第i个字母相同？
    dp[i][j]=dp[i-1][j-1]+1；
    否则，
    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])
  • 最长字串的长度记录在dp[count-1][count-1]
  • 返回count-dp[count-1][count-1] ，即需要删减的字母个数

实现代码

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
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder result = new StringBuilder();
        while (in.ready()) {
            int count = Integer.parseInt(in.readLine());
            String[] strings1 = in.readLine().split(" ");
            String[] strings2 = in.readLine().split(" ");
            int[] nums1 = new int[count];
            for (int i = 0; i < count; i++) {
                nums1[i] = Integer.parseInt(strings1[i]);
            }
            int[] nums2 = new int[count];
            for (int i = 0; i < count; i++) {
                nums2[i] = Integer.parseInt(strings2[i]);
            }
            int[][] res=new int[count][count];
            for (int i=0;i<count;i++){
                if(nums1[0]==nums2[i]){
                    while (i<count){
                        res[i][0]=1;
                        i++;
                    }
                    break;
                }
            }
            for (int i=0;i<count;i++){
                if(nums2[0]==nums1[i]){
                    while (i<count){
                        res[0][i]=1;
                        i++;
                    }
                    break;
                }
            }
            for (int i=1;i<count;i++){
                for (int j=1;j<count;j++){
                    if(nums1[j]==nums2[i]){
                        res[i][j]=res[i-1][j-1]+1;
                    }
                    else
                        res[i][j]=Math.max(res[i-1][j],res[i][j-1]);
                }
            }
            System.out.println(count-res[count-1][count-1]);
        }
        in.close();
    }
}