华为od机试题8 真题

• • 20.输出最小步骤数量
  • 21.最优组合策略
  • 22.从多个数组中按顺序取出固定长度的内容组成新数组
  • 25.绝对值最小值
  • 26.最少颜色种数
  • 27.元素十进制最低位排序
  • 28.最大N个数和最小N个数的和
  • 29.单词联想

以下题目附带Java解法，是我个人写的，不一定是标准答案，没有真正的测试数据，只能说是我自己认为通过率100%，也不一定是最优解。如果有错误或是有更好的解法，请评论告诉我！！！

 一个正整数数组 设为nums
 最大为100个成员
 求从第一个成员开始正好走到数组最后一个成员所使用的最小步骤数
 3 5 9 4 2 6 8 3 5 4 3 9
 要求：
 1. 第一步 必须从第一元素起  且 1<=第一步步长 
// 输出最小步骤数量
    // 解题思路：遍历符合条件的第一步，拿到第二步的值，判断是否符合要求，不符合则继续，拿到最小的值
    public static void test020(){
        Scanner sc = new Scanner(System.in);
        String[] split = sc.nextLine().split(" ");
        List list = new ArrayList<>();
        for (int i = 0; i < split.length; i++){
            list.add(Integer.parseInt(split[i]));
        }

        // 结果
        int res = Integer.MAX_VALUE;
        // 条件：必须从第一元素起  且 1<=第一步步长
            int count = 1;
            // 第一步所在位置的值
            Integer nextNum = list.get(i);
            while (true){
                // i + nextNum 是第一次走的长度加当前位置的长度
                // 如果是终点则结束
                if (i + nextNum == list.size() - 1) {
                    count++;
                    break;
                } else if (i + nextNum <= list.size() / 2) { // 第一次后没有过数组一半，肯定不是最优解
                    count = Integer.MAX_VALUE;
                    break;
                } else if (i + nextNum < list.size() - 1) { // 超过数组一半且不到终点
                    // 还没到终点则在向前走当前位置的步数
                    nextNum = nextNum + list.get(i + nextNum);
                    count++;
                } else { // 超过终点则结束
                    count = Integer.MAX_VALUE;
                    break;
                }
            }
            // 取最小值
            res = Math.min(res, count);
        }
        if (res == Integer.MAX_VALUE){
            System.out.println(-1);
        } else {
            System.out.println(res);
        }
    }
 
21.最优组合策略 
 在通信系统中有一个常见的问题是对用户进行不同策略的调度
 会得到不同系统消耗的性能
 假设由N个待串行用户，每个用户可以使用A/B/C三种不同的调度策略
 不同的策略会消耗不同的系统资源
 请你根据如下规则进行用户调度
 并返回总的消耗资源数
 规则是：相邻的用户不能使用相同的调度策略
 例如：
 第一个用户使用A策略 则第二个用户只能使用B和C策略
 对单的用户而言，不同的调度策略对系统资源的消耗可以规划后抽象为数值
 例如
 某用户分别使用ABC策略的系统消耗，分别为15 8 17
 每个用户依次选择当前所能选择的对系统资源消耗最少的策略,局部最优
 如果有多个满足要求的策略，选最后一个

 输入描述：
 第一行表示用户个数N
 接下来表示每一行表示一个用户分别使用三个策略的资源消耗
 resA resB resC

 输出描述：
 最优策略组合下的总的系统消耗资源数

 示例一：
 输入：
 3
 15 8 17
 12 20 9
 11 7 5
 输出：
 24
 说明:
 1号用户使用B策略
 2号用户使用C策略
 3号用户使用B策略
 系统资源消耗8+9+7
 
    // 最优组合策略
    // 解题思路：遍历每一个数组，找到最小值，记录最小值的索引，相邻的数组不使用上次记录的索引所在的值
    public static void test021(){
        Scanner sc = new Scanner(System.in);
        int num = Integer.parseInt(sc.nextLine());
        List list = new ArrayList<>();
        for (int i = 0; i < num; i++){
            list.add(sc.nextLine());
        }
        // 结果
        int sum = 0;
        // 存储最终最小值的索引
        int minIndex = 1111;
        for (int i = 0; i < num; i++){
            String[] split = list.get(i).split(" ");
            // 用来存储临时的最小值的索引
            int tempIndex = 9999;
            // 默认最小值
            int minNum = Integer.MAX_VALUE;
            for (int j = 0; j < split.length; j++){
                int temp = Integer.parseInt(split[j]);
                // 最小的 且 不与相邻的用户使用相同的调度策略
                if (temp <= minNum && j != minIndex) {
                    minNum = temp;
                    tempIndex = j;
                }
            }
            sum += minNum;
            // 上一个数组最小值的位置
            minIndex = tempIndex;
        }
        System.out.println(sum);
    }
 
22.从多个数组中按顺序取出固定长度的内容组成新数组 
 现在有多组整数数组
 需要将他们合并成一个新的数组
 合并规则从每个数组里按顺序取出固定长度的内容
 合并到新的数组
 取完的内容会删除掉
 如果该行不足固定长度，或者已经为空
 则直接取出剩余部分的内容放到新的数组中继续下一行

 输入描述
 第一 行每次读取的固定长度
 长度0 
    // 从多个数组中按顺序取出固定长度的内容组成新数组
    // 解题思路：在循环内遍历每个数组，将符合长度要求的数放进新数组，当新数组长度 == 多个数组长度之和时，循环结束
    public static void test022(){
        Scanner sc = new Scanner(System.in);
        // 每次切割长度
        int num = Integer.parseInt(sc.nextLine());
        // 数组数量
        int acount = Integer.parseInt(sc.nextLine());
        List> list = new ArrayList<>();
        // 全部数组总长度
        int sumLen = 0;
        for (int i = 0; i < acount; i++) {
            List e = Arrays.asList(sc.nextLine().split(","));
            sumLen += e.size();
            list.add(e);
        }
        // 存放结果
        List resList = new ArrayList<>();
        int index = 0;
        // 当结果数组长度 大于等于 全部数组总长度 时，运算结束退出循环
        while (resList.size() < sumLen) {
            // 遍历每个数组
            for (int i = 0; i < acount; i++) {
                List list1 = list.get(i);
                if (index > list1.size()) { // 数组用完了，退出此次循环
                    continue;
                } else if (index + num < list1.size()){ // 数组元素还充足
                    for (int j = index; j < index + num; j++) {
                        resList.add(list1.get(j));
                    }
                } else { // 来到最后，取数组剩余元素
                    for (int j = index; j < list1.size(); j++) {
                        resList.add(list1.get(j));
                    }
                }
            }
            // 更换起点
            index += num;
        }
        for (int i = 0; i < resList.size(); i++){
            if (i == resList.size() - 1) {
                System.out.print(resList.get(i));
            }else {
                System.out.print(resList.get(i) + ",");
            }
        }
    }
 
25.绝对值最小值 
 给定一个随机的整数数组(可能存在正整数和负整数)nums,
 请你在该数组中找出两个数，其和的绝对值(|nums[x]+nums[y]|)为最小值
 并返回这两个数(按从小到大返回)以及绝对值。
 每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
 

 输入描述：
 一个通过空格空格分割的有序整数序列字符串，最多1000个整数，
 且整数数值范围是[-65535,65535]
 

 输出描述：
 两个数和两数之和绝对值
 

 示例一：
 输入
 -1 -3 7 5 11 15
 输出
 -3 5 2
 

 说明：
 因为|nums[0]+nums[2]|=|-3+5|=2最小，
 所以返回-3 5 2
 
    // 绝对值最小值
    // 解题思路：双层for循环，遍历出所有组合，记录最小值
    public static void test025(){
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        String[] split = line.split(" ");
        List list = new ArrayList<>();
        for (int i = 0; i < split.length; i++) {
            int parseInt = Integer.parseInt(split[i]);
            // 数组中同一个元素不能使用两遍
            if (!list.contains(parseInt)) {
                list.add(parseInt);
            }
        }

        int res = Integer.MAX_VALUE;
        int a = 0;
        int b = 0;
        for (int i = 0; i < list.size(); i++){
            for (int j = i + 1; j < list.size(); j++){
                int sum = Math.abs(list.get(i) + list.get(j));
                if (sum < res) {
                    a = list.get(i);
                    b = list.get(j);
                    res = sum;
                }
            }
        }
        if (a < b) {
            System.out.println(a + " " + b + " " + res);
        } else {
            System.out.println(b + " " + a + " " + res);
        }
    }
 
26.最少颜色种数 
 疫情过后希望小学终于又重新开学了
 3年2班开学第一天的任务是
 将后面的黑板报重新制作
 黑板上已经写上了N个正整数
 同学们需要给这每个数分别上一种颜色
 为了让黑板报既美观又有学习意义
 老师要求同种颜色的所有数都可以被这个颜色中最小的那个数整除
 现在帮小朋友们算算最少需要多少种颜色，给这N个数进行上色

 输入描述
 第一行有一个正整数N
 其中 1 <= n <=100
 第二行有N个int型数，保证输入数据在[1,100]范围中
 表示黑板上各个正整数的值

 输出描述
 输出只有一个整数，为最少需要的颜色种数

 输入
 3
 2 4 6
 输出
 1
 说明：
 所有数都能被2整除

 输入
 4
 2 3 4 9
 输出
 2
 说明：
 2与4涂一种颜色，4能被2整除
 3与9涂另一种颜色，9能被3整除
 不能涂同一种颜色
 
    // 最少颜色种数
    // 解题思路：维护一个新集合，用于存储不能整除最小数的，遍历输入的数，每个数都去与新集合的每个数比较是否整除，不能整除则加入新数组
    public static void test026(){
        Scanner sc = new Scanner(System.in);
        int len = Integer.parseInt(sc.nextLine());
        String[] split = sc.nextLine().split(" ");
        List list = new ArrayList<>();
        for (int i = 0; i < len; i++){
            list.add(Integer.parseInt(split[i]));
        }
        // 对数组进行升序排序
        Collections.sort(list);
        // 存储不能整除最小数的数
        List resList = new ArrayList<>();
        // 最少需要1中颜色，所以最小的数是基数
        resList.add(list.get(0));
        for (int i = 1; i < len; i++){
            int num = list.get(i);
            for (int j = 0; j < resList.size(); j++) {
                // 符合条件，则退出
                if (num % resList.get(j) == 0) {
                    break;
                }
                // 到最后一个都不符合条件，则加入不能整除数组
                if (j == resList.size() - 1) {
                    resList.add(num);
                }
            }
        }
        System.out.println(resList.size());

    }
 
27.元素十进制最低位排序 
 给定一个非空数组(列表)
 起元素数据类型为整型
 请按照数组元素十进制最低位从小到大进行排序
 十进制最低位相同的元素，相对位置保持不变
 当数组元素为负值时，十进制最低为等同于去除符号位后对应十进制值最低位

 输入描述
 给定一个非空数组(列表)
 其元素数据类型为32位有符号整数
 数组长度为[1,1000]
 输出排序后的数组

 输入
 1,2,5,-21,22,11,55,-101,42,8,7,32
 输出
 1,-21,11,-101,2,22,42,32,5,55,7,8
 
    // 元素十进制最低位排序
    // 解题思路：取元素最后一位进行比较排序
    public static void test027(){
        Scanner sc = new Scanner(System.in);
        String[] split = sc.nextLine().split(",");
        List list = Arrays.asList(split);
        list.sort((s1, s2) -> {
            // 取元素最后一个进行比较排序
            return s1.charAt(s1.length() - 1) - s2.charAt(s2.length() - 1);
        });
        StringBuilder sb = new StringBuilder();
        for (String s : list){
            sb.append(s + ",");
        }
        System.out.println(sb.substring(0, sb.length() - 1));
    }
 
28.最大N个数和最小N个数的和 
给定一个数组
 编写一个函数
 来计算他的最大N个数和最小N个数的和
 需要对数组进行去重

 说明
 第一行输入M
 M表示数组大小
 第二行输入M个数
 表示数组内容
 第三行输入N表示需要计算的最大最小N的个数

 输出描述
 输出最大N个数和最小N个数的和

 例一：
 输入
 5
 95 88 83 64 100
 2

 输出
 342

 说明
 最大2个数[100 95] 最小2个数[83 64]
 输出342

 例二
 输入
 5
 3 2 3 4 2
 2

 输出
 -1
 说明
 最大两个数是[4 3]最小2个数是[3 2]
 有重叠输出为-1
 
    // 最大N个数和最小N个数的和
    // 解题思路：对数组进行去重且排序，当满足条件时取最后两个与最前两个相加
    public static void test028(){
        Scanner sc = new Scanner(System.in);
        int len = Integer.parseInt(sc.nextLine());
        String[] split = sc.nextLine().split(" ");
        int num = Integer.parseInt(sc.nextLine());
        // 去重且排序
        Set set = new TreeSet<>();
        for (int i = 0; i < len; i++) {
            set.add(Integer.parseInt(split[i]));
        }
        // 去重后长度不是num的两倍
        if (set.size() < 2 * num) {
            System.out.println(-1);
            return;
        }
        int sum = 0;
        // 将set转为list
        List list = new ArrayList<>(set);
        for (int i = 0; i < num; i++) {
            sum += list.get(i) + list.get(list.size() - 1 - i);
        }
        System.out.println(sum);
    }
 
29.单词联想 
 主管期望你来实现英文输入法单词联想功能
 需求如下
 依据用户输入的单词前缀
 从已输入的英文语句中联想出用户想输入的单词
 按字典序输出联想到的单词序列
 如果联想不到
 请输出用户输入的单词前缀
 注意
 英文单词联想时区分大小写
 缩略形式如
 "don't" 判定为两个单词 "don"和 "t"
 输出的单词序列不能有重复单词
 且只能是英文单词，不能有标点符号

 输入描述
 输入两行
 首行输入一段由英文单词word和标点构成的语句str

 接下来一行为一个英文单词前缀pre
 0 < word.length() <= 20
 0 < str.length <= 10000
 0 < pre <=20

 输出描述
 输出符合要求的单词序列或单词前缀
 存在多个时，单词之间以单个空格分割

 示例一
 输入
 I love you
 He

 输出
 He

 说明
 用户已输入单词语句"I love you",
 中提炼出"I","love","you"三个单词
 接下来用户输入"He" ，
 从已经输入信息中无法联想到符合要求的单词
 所以输出用户输入的单词前缀

 示例二
 输入
 The furthest distance in the world,Is not between life and death,But when I stand in front or you,Yet you don't know that I love you.
 f

 输出
 front furthest
 
    // 单词联想
    // 解题思路：用正则表达式切分出每个单词，遍历字符，保存满足条件的字符
    public static void test029(){
        Scanner sc = new Scanner(System.in);
        // 正则表达式：W+ ：匹配一个或多个非字母进行切割，匹配到的非字母不缓存
        String[] split = sc.nextLine().split("\W+");
        String str = sc.nextLine();
        List list = new ArrayList<>();
        for (int i = 0; i < split.length; i++) {
            // 判断目标字符是否是输入字符开头的，且要去重
            if (split[i].startsWith(str) && !list.contains(split[i])) {
                list.add(split[i]);
            }
        }
        // 对list进行排序
        list.sort((s1, s2) -> {
            // 遍历字符串中每个字符，返回第一处不同字符的差值
            return s1.compareTo(s2);
        });

        if (list.size() > 0) {
            for (String s : list) {
                System.out.print(s + " ");
            }
        } else {
            System.out.println(str);
        }
    }

    // 单词联想
    public static void test029_2(){
        Scanner sc = new Scanner(System.in);
        //  // 正则表达式：W+ ：匹配一个或多个非字母进行切割，匹配到的非字母不缓存
        String[] split = sc.nextLine().split("\W+");
        String str = sc.nextLine();
        // TreeSet 有序的set，英文按字典降序排序
        // 使用TreeSet还可以自动去重
        Set set = new TreeSet<>();
        for (int i = 0; i < split.length; i++) {
            if (split[i].startsWith(str)) {
                set.add(split[i]);
            }
        }
        if (set.size() > 0) {
            for (String s : set) {
                System.out.print(s + " ");
            }
        } else {
            System.out.println(str);
        }
    }
 
更多华为od机试题请点这里<华为od机试题9 真题>，每篇8题，有更多的题也请告诉我啊