华为OD机试（B卷）

华为OD机试（B卷）

有幸接到了华为OD的机试邀请，三道算法题。比较幸运的是，最后一题，也相对来说不算太难，没有抽到动态规划，还是花了大约90分钟，三道题都通过了，最终拿到了满分；第一题第二题都相对来说比较基础，由于平时也没有刷题的习惯，用自己的常规思路都能解决；第三题，也算中规中矩，直接构建对象，递归就解决了。

1 第一题

给定一个元素类型为小写字符串的数组 请计算两个没有相同字符的元素长度乘积的最大值 如果没有符合条件的两个元素返回0
输入描述 输入为一个半角逗号分割的小写字符串数组 2<= 数组长度 <=100 0< 字符串长度 <=50 输出描述 两个没有相同字符的元素长度乘积的最大值
示例一 输入 iwdvpbn,hk,iuop,iikd,kadgpf 输出 14 说明 数组中有5个元组 第一个和第二个元素没有相同字符 满足条件 输出7*2=14

public class Demo1 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()) {
            String str = scanner.nextLine();
            List<Integer> result = new ArrayList<>();
            String[] list = str.split(",");
            for (int i = 0; i < list.length; i++) {
                for (int j = i + 1; j < list.length; j++) {
                    if (check(list[i], list[j])) {
                        result.add(list[i].length() * list[j].length());
                    }
                }
            }
            if (result.isEmpty()) {
                System.out.println(0);
            } else {
                Collections.sort(result);
                System.out.println(result.get(result.size() - 1));
            }
        }
    }

    public static boolean check(String s1, String s2) {
        char[] chars1 = s1.toCharArray();
        char[] chars2 = s2.toCharArray();
        for (char c1 : chars1) {
            for (char c2 : chars2) {
                if (c1 == c2) {
                    return false;
                }
            }
        }
        return true;
    }
}
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

2 第二题

输入一个英文文章片段，
翻转指定区域的单词顺序，
标点符号和普通字母一样处理，
例如输入字符串
I am a developer.
[0,3]
则输出
developer. a am I

输入描述
使用换行隔开3个参数
第一个参数为文章内容 即英文字符串
第二个参数为翻转起始单词下标，下标从0开始
第三个参数为结束单词下标
输出描述
翻转后英文文章片段每个单词之间以一个半角空格分割输出

public class Demo2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String englishStr = scanner.nextLine();
        int begin = scanner.nextInt();
        int end = scanner.nextInt();
        List<String> englishList = Arrays.asList(englishStr.split(" "));
        if (begin < 0) {
            begin = 0;
        }
        if (end >= englishList.size()) {
            end = englishList.size() - 1;
        }
        if (end <= 0 || begin > end) {
            System.out.println(englishStr);
            return;
        }
        List<String> subList = englishList.subList(begin, end + 1);
        Collections.reverse(subList);
        List<String> result = new ArrayList<>(englishList.subList(0, begin));
        result.addAll(subList);
        result.addAll(englishList.subList(end + 1, englishList.size()));
        System.out.println(String.join(" ", result));
    }
}
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

3 第三题

某文件系统中有N个目录，每个目录都一个独一无二的ID。每个目录只有一个父目录，但每个父目录下可以有零个或者多个子目录，目录结构呈树状结构。
假设，根目录的ID为0，且根目录没有父目录，其他所有目录的ID用唯一的正整数表示，并统一编号。
现给定目录ID和其父目录ID的对应父子关系表[子目录ID，父目录ID]，以及一个待删除的目录ID，请计算并返回一个ID序列，表示因为删除指定目录后剩下的所有目录，返回的ID序列以递增序输出。
注意：
1、被删除的目录或文件编号一定在输入的ID序列中；
2、当一个目录删除时，它所有的子目录都会被删除。
输入描述: 输入的第一行为父子关系表的长度m；接下来的m行为m个父子关系对；最后一行为待删除的ID。序列中的元素以空格分割，参见样例。
输出描述: 输出一个序列，表示因为删除指定目录后，剩余的目录ID。
示例1
输入
5
8 6
10 8
6 0
20 8
2 6
8
输出
2 6

public class Demo3 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<Node> list = new ArrayList<>();
        int length = scanner.nextInt();
        for (int i = 0; i < length; i++) {
            Node node = new Node();
            node.setId(scanner.next());
            node.setParentId(scanner.next());
            list.add(node);
        }
        String delEle = scanner.next();
        List<Node> result = new ArrayList<>();
        del(list, delEle, result);
        list.removeAll(result);
        List<Integer> output = new ArrayList<>();
        for (Node node : list) {
            if (!Objects.equals(node.getId(), delEle))
                output.add(Integer.parseInt(node.getId()));
        }
        Collections.sort(output);
        for (int i = 0; i < output.size(); i++) {
            if (i != output.size() - 1) {
                System.out.print(output.get(i) + " ");
            } else {
                System.out.println(output.get(i));
            }
        }
    }

    public static void del(List<Node> list, String ele, List<Node> result) {
        list.stream()
                .filter(l -> Objects.equals(l.getParentId(), ele))
                .forEach(l -> {
                    result.add(l);
                    del(list, l.getId(), result);
                });
    }
}

class Node {
    String id;
    String parentId;

    public String getId() {
        return id;
    }

    public void setId(String id) {
        this.id = id;
    }

    public String getParentId() {
        return parentId;
    }

    public void setParentId(String parentId) {
        this.parentId = parentId;
    }
}

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