荣耀 10.8 开发笔试 笔经

我好像是卷 1

第一题： 完善字符串

输入字符串（子串数、子串，形如 2 abc 123456789），子串未满8个则填充0使其总长度达到8个字符，超过8个则分割

核心部分：

for (String part : parts) {
  // 处理每8个字符
  for (int i = 0; i < part.length(); i += 8) {
    String chunk = part.substring(i, Math.min(i + 8, part.length()));
    // 如果长度不足8，在末尾补0
    if (chunk.length() < 8) {
      // 当chunk的长度小于8时，%-8s会在chunk的末尾添加空格，使其总长度达到8个字符
      // 然后将空格替换为0
      chunk = String.format("%-8s", chunk).replace(' ', '0');
      result.add(chunk);
    }
  }
}

第二题：十进制转16位二进制补码

有点奇淫巧技了，因为计算机用二进制存的直接提出来就行

public static String convertToBinary16(int num) {
    if (num < - Math.pow(2, 15) || num > Math.pow(2, 15) - 1) {
        return  num > 0 ? "0111111111111111" : "1000000000000000";
    }

    StringBuilder binary = new StringBuilder();

    // 从最高位开始，逐位检查并添加到结果中
    for (int i = 15; i >= 0; i--) {
        // 使用位运算检查每一位
        if ((num & (1 << i)) != 0) {
            binary.append('1');
        } else {
            binary.append('0');
        }
    }

    return binary.toString();
}

第三题：蛇形字符串

想了很久没想明白，以为是DP啥的试了半天，最后发现其实什么都不用能分解问题就能写出来，主要是题目描述太复杂了，吃一堑长一智了唉。。。太难过了

题目描述

输入一个字符串（不含空格）， 请寻找输入中包含所有蛇形字符串。 蛇形字符串定义：

1.蛇形字符串由连续字符对组成，其特点如下： 1.1 字符对定义：字符对由同一字母的大写和小写组成（前大后小）。如：Aa，Dd； 1.2 蛇形字符串中包含的字符对，必须是连续字母，并按照字母顺序排序。如：AaBbCc或OoPpQqRrSs；

2.从输入中寻找字符组成蛇形字符串（字符顺序不限），符合规则： 2.1 每次寻找必须是最长的蛇形字符串； 2.2 使用过的字符不能重复使用；

详细题目请看

解法

• 我认为最重要的一点是字符串顺序不重要，这是后面一切思路的基础
• 大写字母必须紧跟小写字母，所以确保一一对应——如果3个A 2个a，那么最多组成两个Aa

所以思路大致如下：

1. 统计输入字符串中大写和小写字母的出现次数
2. 在大写字母映射中寻找同时存在于小写字母映射中的字母
3. 对这些字母进行排序，并找出最长的连续字母子串。
4. 构建一个新字符串，将最长连续字母子串中的每个大写字母与其对应的小写字母配对
5. 将构建的字符串添加到结果列表中，并减少相应字母的计数，如果个数为0，移除该字母
6. 重复

import java.util.*;

class SnackStr {
    // 主方法，处理输入字符串并返回结果列表
    public List<String> snack(String s) {
        // 用于存储大写字母及其出现次数的映射
        Map<Character, Integer> up = new HashMap<>();
        // 用于存储小写字母及其出现次数的映射
        Map<Character, Integer> low = new HashMap<>();

        // 遍历字符串中的每个字符
        for (char chr : s.toCharArray()) {
            // 如果是小写字母，更新low映射
            if ('a' <= chr && chr <= 'z') {
                low.put(chr, low.getOrDefault(chr, 0) + 1);
            }
            // 如果是大写字母，更新up映射
            if ('A' <= chr && chr <= 'Z') {
                up.put(chr, up.getOrDefault(chr, 0) + 1);
            }
        }

        // 用于存储结果的列表
        List<String> res = new ArrayList<>();
        // 当up映射不为空时，继续处理
        while (!up.isEmpty()) {
            // 获取同时存在于up和low映射中的字符
            // 仅处理这些字符（且只用保存大写形式）
            List<Character> chars = getUpLowChar(up, low);
            // 如果没有这样的字符，跳出循环
            if (chars.isEmpty()) {
                break;
            }
            // 对字符列表进行排序
            Collections.sort(chars);
            // 获取最长的连续字符子串
            String out = maxLen(chars);
            // 构建结果字符串
            StringBuilder sb = new StringBuilder();
            for (char x : out.toCharArray()) {
                sb.append(x).append(Character.toLowerCase(x));
            }
            // 将结果字符串添加到结果列表中
            res.add(sb.toString());
            // 减少up和low映射中对应字符的计数
            decrease(out, up, low);
        }
        return res;
    }

    // 获取同时存在于up和low映射中的字符
    private List<Character> getUpLowChar(Map<Character, Integer> up, Map<Character, Integer> low) {
        List<Character> res = new ArrayList<>();
        for (char key : up.keySet()) {
            if (low.containsKey(Character.toLowerCase(key))) {
                res.add(key);
            }
        }
        return res;
    }

    // 获取字符列表中最长的连续字符子串
    private String maxLen(List<Character> s) {
        // s 是排序后的字符列表
        if (s.isEmpty()) return "";
        StringBuilder maxEnd = new StringBuilder().append(s.getFirst());
        StringBuilder res = new StringBuilder().append(s.getFirst());
        for (int i = 1; i < s.size(); i++) {
            // s.get(i) - s.get(i - 1) == 1 检查当前字符是否是前一个字符的下一个字母。
            // 例如，'B' - 'A' == 1，表示它们是连续的
            if (s.get(i) - s.get(i - 1) == 1) {
                maxEnd.append(s.get(i));
            } else {
                // 不连续，从当前开始继续找
                maxEnd = new StringBuilder().append(s.get(i));
            }
            // 更新结果
            if (maxEnd.length() > res.length()) {
                res = new StringBuilder(maxEnd);
            }
        }
        return res.toString();
    }

    // 减少up和low映射中对应字符的计数
    private void decrease(String s, Map<Character, Integer> up, Map<Character, Integer> low) {
        for (char chr : s.toCharArray()) {
            up.put(chr, up.get(chr) - 1);
            if (up.get(chr) == 0) {
                up.remove(chr);
            }
            char lowerChr = Character.toLowerCase(chr);
            low.put(lowerChr, low.get(lowerChr) - 1);
            if (low.get(lowerChr) == 0) {
                low.remove(lowerChr);
            }
        }
    }

    // 主方法，用于测试
    public static void main(String[] args) {
        SnackStr solution = new SnackStr();
        String test = "SwSE$3454356DD$$E#eswsxxsssAAWDxxdderfvcRFER65645hbg^^%%^UnbnvccTRChnyvcxcvVCFR";
        for (String x : solution.snack(test)) {
            System.out.println(x);
        }
    }
}