[数据结构与算法] 华为od机试题9 真题

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 华为od机试题9 真题 -> 正文阅读

[数据结构与算法]华为od机试题9 真题

华为od机试题真题

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

10.输出最多类型的个数

题目描述：
 对一个数据a进行分类，
 分类方法是，此数据a(4个字节大小)的4个字节相加对一个给定值b取模，
 如果得到的结果小于一个给定的值c则数据a为有效类型，其类型为取模的值。
 如果得到的结果大于或者等于c则数据a为无效类型。

 比如一个数据a=0x01010101，b=3
 按照分类方法计算：(0x01+0x01+0x01+0x01)%3=1
 所以如果c等于2，则此a就是有效类型，其类型为1
 如果c等于1，则此a是无效类型

 又比如一个数据a=0x01010103，b=3
 按分类方法计算：(0x01+0x01+0x01+0x03)%3=0
 所以如果c=2则此a就是有效类型 其类型为0
 如果c等于0 则此a是无效类型

 输入12个数据，
 第一个数据为c，第二个数据为b，
 剩余10个数据为需要分类的数据

 请找到有效类型中包含数据最多的类型，
 并输出该类型含有多少个数据

 输入描述
 输入12个数据用空格分割，
 第一个数据为c，第二个数据为b，
 剩余10个数据为需要分类的数据。

 输出描述
 请找到有效类型中包含数据最多的类型，
 并输出该类型含有多少个数据。

 示例一
 输入
 3 4 256 257 258 259 260 261 262 263 264 265
 输出
 3
 说明
 这10个数据4个字节相加后的结果分别是
 1 2 3 4 5 6 7 8 9 10
 故对4取模的结果为
 1 2 3 0 1 2 3 0 1 2
 c是3所以012都是有效类型
 类型为1和2的有3个数据
 类型为0和3的只有两个
 示例二
 输入
 1 4 256 257 258 259 260 261 262 263 264 265
 输出
 2

// ps：这道题我的理解是把输入的转为16进制，从后往前取依次取2位，如果16进制数长度大于8，取后8位，然后转为10进制相加，与基数取模。它的案列给得不清楚，不确定题目是不是这个意思。
    // 输出最多类型的个数
    public static void test010() {
        Scanner sc = new Scanner(System.in);
        List<Integer> list = new ArrayList<>();
        String s = sc.nextLine();
        String[] strings = s.split(" ");
        // 转为int型集合
        for (int i = 0; i < strings.length; i++) {
            list.add(Integer.parseInt(strings[i]));
        }
        // map用来存储出现次数，key为取模后的值，value为次数
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 2; i < list.size(); i++) {
            // 将输入的数转为16进制
            String num16 = tenTo16(list.get(i));
            int len = num16.length();
            // 累加的和
            int allRes = 0;
            // 从后往前取依次取2位，如果16进制数长度大于8，取后8位，然后转为10进制相加
            if (len >= 8) {
                // 16进制转10进制：Integer.parseInt("ABCD", 16);
                allRes = Integer.parseInt(num16.substring(len - 8, len - 6), 16) + Integer.parseInt(num16.substring(len - 6, len - 4), 16)
                        + Integer.parseInt(num16.substring(len - 4, len - 2), 16) + Integer.parseInt(num16.substring(len - 2, len), 16);
            } else if (len == 7) {
                allRes = Integer.parseInt(num16.substring(0, 1), 16) + Integer.parseInt(num16.substring(1, 3), 16)
                        + Integer.parseInt(num16.substring(3, 5), 16) + Integer.parseInt(num16.substring(5, 7), 16);
            } else if (len == 6) {
                allRes = Integer.parseInt(num16.substring(0, 2), 16) + Integer.parseInt(num16.substring(2, 4), 16)
                        + Integer.parseInt(num16.substring(4, 6), 16);
            } else if (len == 5) {
                allRes = Integer.parseInt(num16.substring(0, 1), 16) + Integer.parseInt(num16.substring(1, 3), 16)
                        + Integer.parseInt(num16.substring(3, 5), 16);
            } else if (len == 4) {
                allRes = Integer.parseInt(num16.substring(0, 2), 16) + Integer.parseInt(num16.substring(2, 4), 16);
            } else if (len == 3) {
                allRes = Integer.parseInt(num16.substring(0, 1), 16) + Integer.parseInt(num16.substring(1, 3), 16);
            } else if (len == 2) {
                allRes = Integer.parseInt(num16.substring(0, 2), 16);
            } else if (len == 1) {
                allRes = Integer.parseInt(num16.substring(0, 1), 16);
            }
            System.out.println(allRes);
            int modeValue = allRes % list.get(1);
            System.out.println(modeValue);
            // 用map存次数
            if (modeValue < list.get(0)) {
                if (map.containsKey(modeValue)) {
                    map.put(modeValue, map.get(modeValue) + 1);
                } else {
                    map.put(modeValue, 1);
                }
            }
        }
        int maxCount = 0;
        // 找出最大的次数
        for (Integer key : map.keySet()) {
            maxCount = Math.max(map.get(key), maxCount);
        }
        System.out.println(maxCount);
    }

    /**
     * 十进制转十六进制
     *
     * @return
     */
    private static String tenTo16(int num) {
        String s = "";
        do {
            int res = num % 16;
            num = num / 16;
            if (res == 15) {
                s = "F" + s;
            } else if (res == 14) {
                s = "E" + s;
            } else if (res == 13) {
                s = "D" + s;
            } else if (res == 12) {
                s = "C" + s;
            } else if (res == 11) {
                s = "B" + s;
            } else if (res == 10) {
                s = "A" + s;
            } else {
                s = res + s;
            }
        } while (num != 0);
        return s;
    }

11.树根节点到最小的叶子节点的路径

题目描述：
 二叉树也可以用数组来存储，
 给定一个数组，树的根节点的值储存在下标1，
 对于储存在下标n的节点，他的左子节点和右子节点分别储存在下标2*n和2*n+1，
 并且我们用-1代表一个节点为空，
 给定一个数组存储的二叉树，
 试求从根节点到最小的叶子节点的路径，
 路径由节点的值组成。

 输入描述
 输入一行为数组的内容，
 数组的每个元素都是正整数，元素间用空格分割，
 注意第一个元素即为根节点的值，
 即数组的第n元素对应下标n，
 下标0在树的表示中没有使用，所以我们省略了，
 输入的树最多为7层。

 输出描述
 输出从根节点到最小叶子节点的路径上各个节点的值，
 由空格分割，
 用例保证最小叶子节点只有一个。

 示例一
 输入
 3 5 7 -1 -1 2 4
 输出
 3 7 2
 示例二
 输入
 5 9 8 -1 -1 7 -1 -1 -1 -1 -1 6
 输出
 5 8 7 6

// 解题思路：找出除了根节点的最小节点，除以2得到的整数就是它的父节点，依次除下去，直至根节点
    // 树根节点到最小的叶子节点的路径
    public static void test011(){
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        String[] s = line.split(" ");
        // 只输入一个根元素，直接返回
        if(s.length <= 1) {
            System.out.println(s[0]);
            return;
        }
        List<Integer> list = new ArrayList<>();
        // 集合第一个元素是无关元素，存个最大的整型数
        list.add(Integer.MAX_VALUE);
        for (int i = 0;i<s.length;i++) {
            list.add(Integer.parseInt(s[i]));
        }
        // 找出最小的数，-1表示该节点为空，不参与查找
        int res = Integer.MAX_VALUE;
        for (int i = 2;i<list.size();i++) {
            if (list.get(i) != -1) {
                res = Math.min(res, list.get(i));
            }
        }
        // 找不到最小的数，说明树除了根元素，其他都是-1
        if (res == Integer.MAX_VALUE) {
            System.out.println(s[0]);
            return;
        }
        // 找出最小的数所在位置
        int resKey = 0;
        for (int i = 2;i<list.size();i++) {
            if (list.get(i) == res) {
                resKey = i;
            }
        }
        // 用于储存结果
        List<Integer> resList = new ArrayList<>();
        while (resKey != 1) {
            resList.add(resKey);
            resKey = resKey / 2;
        }
        // 添加根元素
        resList.add(1);
        for (int i = resList.size() - 1; i >= 0;i--) {
            System.out.print(list.get(resList.get(i)) + " ");
        }
    }

12.货车最大载货量

 题目描述： 
 一辆运送快递的货车，
  运送的快递放在大小不等的长方体快递盒中，
  为了能够装载更多的快递同时不能让货车超载，
  需要计算最多能装多少个快递。
  注：快递的体积不受限制。
  快递数最多1000个，货车载重最大50000。
  输入描述
  第一行输入每个快递的重量
  用英文逗号隔开
  如 5,10,2,11
  第二行输入货车的载重量
  如 20
  
  输出描述
  输出最多能装多少个快递
  如 3
 
  示例一
  输入
  5,10,2,11
  20
  输出
  3

// 货车最大载货量
    public static void test012() {
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        int capacity = sc.nextInt();
        String[] split = line.split(",");
        // 将字符串数组转为Integer型集合
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < split.length; i++) {
            list.add(Integer.parseInt(split[i]));
        }
        // 对集合进行排序
        Collections.sort(list);
        int sum = 0;
        for (int i = 0; i < list.size(); i++) {
            if (sum + list.get(i) < capacity) {
                sum = sum + list.get(i);
            } else {
                System.out.println(i);
                return;
            }
        }
    }

13.太阳能板最大面积

  题目描述：
  给航天器一侧加装长方形和正方形的太阳能板(图中的斜线区域);
  需要先安装两个支柱(图中的黑色竖条);
  再在支柱的中间部分固定太阳能板;
  但航天器不同位置的支柱长度不同;
  太阳能板的安装面积受限于最短一侧的那支支柱的长度;
  现提供一组整型数组的支柱高度数据;
  假设每个支柱间的距离相等为一个单位长度;
  计算如何选择两根支柱可以使太阳能板的面积最大;
  
  输入描述
  10,9,8,7,6,5,4,3,2,1
  注释，支柱至少有两根，最多10000根，能支持的高度范围1~10^9的整数
 
  柱子的高度是无序的
  例子中的递减是巧合
  
  输出描述
  可以支持的最大太阳板面积:(10m高支柱和5m高支柱之间)
  25
 
  示例一
  输入
  10,9,8,7,6,5,4,3,2,1
  输出
  25
  备注
  10米高支柱和5米高支柱之间宽度为5，高度取小的支柱高度也是5，面积为25
  任取其他两根支柱所能获得的面积都小于25 所以最大面积为25

// 没图 题目大概的意思就是：数组两个元素的间距 乘以 两个元素中的最小值，取最大的，就是太阳能板的最大面积了
    // 太阳能板最大面积
    public static void test013() {
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        String[] split = line.split(",");
        int len = split.length;
        // 结果
        int res = 0;
        for (int i = 0; i < len - 1; i++) {
            for (int j = i + 1; j < len; j++) {
                int eare = Math.min(Integer.parseInt(split[i]), Integer.parseInt(split[j])) * (j - i);
                res = Math.max(res, eare);
            }
        }
        System.out.println(res);
    }

14.单词接龙

 题目描述：
  单词接龙的规则是:
  可用于接龙的单词,首字母必须要与前一个单词的尾字母相同；
  当存在多个首字母相同的单词时，取长度最长的单词；
  如果长度也相等，则取字典序最小的单词；
  已经参与接龙的单词不能重复使用；
  现给定一组全部由小写字母组成的单词数组，
  并指定其中一个单词为起始单词，进行单词接龙，
  请输出最长的单词串。
  单词串是单词拼接而成的，中间没有空格。
  单词个数 1 < N < 20
  单个单词的长度 1 ~ 30
  
  输入描述
  输入第一行为一个非负整数
  表示起始单词在数组中的索引k
  0 <= k < N
  输入的第二行为非负整数N
  接下来的N行分别表示单词数组中的单词
  
  输出描述
  输出一个字符串表示最终拼接的单词串
 
  示例一
  输入
  0
  6
  word
  dd
  da
  dc
  dword
  d
  输出
  worddwordda
  示例二
  输入
  4
  6
  word
  dd
  da
  dc
  dword
  d
  输出
  dwordda

 // PS：如果给出的单词中同样的单词出现两次，能用两次还是用一次？我这里是用了两次，如果只能用一次的话，可以用一个list来存储用过的单词，如果在里面，就不用
    // 单词接龙
    public static void test055_2() {
        Scanner sc = new Scanner(System.in);
        int start = Integer.parseInt(sc.nextLine());
        int len = Integer.parseInt(sc.nextLine());
        List<String> list = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            list.add(sc.nextLine());
        }
        String startWord = list.get(start);
        // 移除起始元素
        list.remove(startWord);
        list.sort((s1, s2) -> {
            int length1 = s1.length();
            int length2 = s2.length();
            if (length1 != length2) {
                return length2 - length1;
            }
            // 按照字典排序，遍历每一个字符，返回不相同字符的差值
            return s1.compareTo(s2);
        });
        String result = startWord;
        for (int i = 0; i < list.size(); i++) {
            String value = list.get(i);
            if (getStartOrEnd(startWord, 100).equals(getStartOrEnd(value, 1))) {
                result = result + value;
                // 找到的单词作为起始单词
                startWord = value;
                // 移除用过的单词
                list.remove(value);
                // 找到了归零，下一个从头开始找
                i = 0;
            }
        }
        System.out.println(result);
    }

    private static String getStartOrEnd(String key, int num) {
        // 求字符串首字母
        if (num == 1) {
            return key.substring(0, 1);
        } else { // 求字符串尾字幕
            return key.substring(key.length() - 1, key.length());
        }
    }

17.输出连续出现次数第k多的字母的次数

给定一个字符串
 只包含大写字母
 求在包含同一字母的子串中
 长度第K长的子串
 相同字母只取最长的子串

 输入
 第一行 一个子串 1<len<=100
 只包含大写字母
 第二行为k的值

 输出
 输出连续出现次数第k多的字母的次数

 例子：
 输入
 AABAAA
 2
 输出
 1
 同一字母连续出现最多的A 3次
 第二多2次  但A出现连续3次

 输入
 AAAAHHHBBCDHHHH
 3
 输出
 2
 //如果子串中只包含同一字母的子串数小于k
 则输出-1

   // 输出连续出现次数第k多的字母的次数
    public static void test17() {
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        int num = sc.nextInt();
        char[] chars = line.toCharArray();
        Map<Character, Integer> map = new HashMap<>();
        int count = 1;
        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];
            while (i + 1 < chars.length && c == chars[i + 1]) {
                count++;
                i++;
            }
            if (map.containsKey(c)) {
                if (count > map.get(c)) {
                    map.put(c, count);
                }
            } else {
                map.put(c, count);
            }
            count = 1;
        }
        if (map.size() < num) {
            System.out.println(-1);
            return;
        }
        Object[] array = map.values().toArray();
        Arrays.sort(array, (a1, a2)->{
            return (Integer)a2 - (Integer) a1;
        });

        System.out.println(array[num - 1]);
    }

18.喊7

 喊7 是一个传统的聚会游戏
    N个人围成一圈
    按顺时针从1-7编号
    编号为1的人从1开始喊数
    下一个人喊得数字是上一个人喊得数字+1
    但是当将要喊出数字7的倍数或者含有7的话
    不能喊出 而是要喊过

    假定N个人都没有失误。
    当喊道数字k时
    可以统计每个人喊 “过"的次数

    现给定一个长度n的数组
    存储打乱的每个人喊”过"的次数
    请把它还原成正确顺序

    即数组的第i个元素存储编号i的人喊“过“的次数

       输入为1行
       空格分割的喊过的次数
       注意k并不提供

       k不超过200
       数字个数为n
       输出描述

       输出为1行
       顺序正确的喊过的次数  空格分割

       例子
       输入
         0 1 0
       输出
         1 0 0

       只有一次过
       发生在7
       按顺序编号1的人遇到7  所以100
       结束时的k不一定是7 也可以是 8 9
         喊过都是100

         例子
       输入
         0 0 0 2 1
       输出
         0 2 0 1 0
       一共三次喊过
       发生在7 14 17
       编号为2 的遇到7 17
       编号为4 的遇到14

// 喊7
    public static void test18(){
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        String[] split = line.split(" ");
        int length = split.length;
        int res = 0;
        for (int i = 0; i < length; i++) {
            res += Integer.parseInt(split[i]);
        }
        List<Integer> list = new ArrayList<>();
        // 求出所有含7以及7的倍数 (k不超过200)
        for (int i = 1; i < 200; i++) {
            String s = i+"";
            if (s.contains("7") || i % 7 == 0) {
                list.add(i);
            }
        }
        int[] array = new int[length];
        for (int i = 0; i < res; i++) {
            array[(list.get(i) % length) - 1] += 1;
        }
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
    }

19.删除出现次数最少的字符

  删除字符串中出现次数最少的字符
如果多个字符出现次数一样则都删除

例子：
输入
  abcdd
  字符串中只
 输出
  dd

输入
  aabbccdd

输出
  empty

  如果都被删除  则换为empty

//删除出现次数最少的字符
    public static void test19(){
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        if (line.length() <= 1) {
            System.out.println("empty");
            return;
        }

        char[] chars = line.toCharArray();
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];
            if (map.containsKey(c)){
                map.put(c, map.get(c) + 1);
            }else {
                map.put(c, 1);
            }
        }
        Integer[] array = new Integer[map.size()];
        Integer[] array1 = map.values().toArray(array);
        Arrays.sort(array1);
        int minLen = array1[0];
        for (Character s : map.keySet()) {
            if (map.get(s) == minLen) {
                line = line.replace(s + "", "");
            }
        }
        if (line.length() <= 0) {
            System.out.println("empty");
        } else {
            System.out.println(line);
        }
    }