问题描述

测试代码

解决思路

代码实现

代码解析

优化

总结

不依赖pinyin4j或第三方库实现取拼音首字母(Java版本)

小葵

2024-07-01

🏷

java面试题

问题描述

输入一段汉字,返回这段汉字的拼音首字母,比如输入浙江省,返回ZJS

测试代码

assertEqual(getFirstLetter("浙江省"), "ZJS", "1");
assertEqual(getFirstLetter("北京市"), "BJS", "2");
assertEqual(getFirstLetter("上海市"), "SHS", "3");
assertEqual(getFirstLetter("杭州公益中学"), "HZGYZX", "4");

解决思路

java里面没有内置的方法可以直接获取拼音首字母,一般是通过第三方的库来实现,比如pinyin4j,但是这里我们要求不依赖第三方库,所以我们需要自己实现一个函数来获取拼音首字母。 我们知道Java的字符串编码其实都是Unicode编码,很多人只了解UTF-8编码,但是汉字最开始是有一套GB2312编码,后来为了兼容更多汉字,出现了GBK编码,GBK是国标编码

UTF8中的汉字顺序并不是严格按照拼音的顺序排列的,而GBK编码中的汉字是按照拼音的顺序排列的,所以我们可以通过GBK编码来获取拼音首字母。 我们举一个栗子🌰, 汉字的的编码顺序:

  • utf8: 的编码是E5 95 8A的编码是E9 98 BF,
  • gbk: 的编码是B0 A1的编码是E0 A2

很明显utf8编码的是不连续的,而gbk编码的是连续的,所以我们只需要找到每个拼音首字母的编码范围,然后根据汉字的编码来判断汉字的拼音首字母。

代码实现

    public static class LetterRange {
        public int start;
        public int end;
        public char letter;

        public LetterRange(int start, int end, char letter) {
            this.start = start;
            this.end = end;
            this.letter = letter;
        }
    }

    public static LetterRange[] mapping = {
            new LetterRange(45217, 45252, 'A'),
            new LetterRange(45253, 45760, 'B'),
            new LetterRange(45761, 46317, 'C'),
            new LetterRange(46318, 46825, 'D'),
            new LetterRange(46826, 47009, 'E'),
            new LetterRange(47010, 47296, 'F'),
            new LetterRange(47297, 47613, 'G'),
            new LetterRange(47614, 48118, 'H'),
            new LetterRange(48119, 49061, 'J'),
            new LetterRange(49062, 49323, 'K'),
            new LetterRange(49324, 49895, 'L'),
            new LetterRange(49896, 50370, 'M'),
            new LetterRange(50371, 50613, 'N'),
            new LetterRange(50614, 50621, 'O'),
            new LetterRange(50622, 50905, 'P'),
            new LetterRange(50906, 51386, 'Q'),
            new LetterRange(51387, 51445, 'R'),
            new LetterRange(51446, 52217, 'S'),
            new LetterRange(52218, 52697, 'T'),
            new LetterRange(52698, 52979, 'W'),
            new LetterRange(52980, 53688, 'X'),
            new LetterRange(53689, 54480, 'Y'),
            new LetterRange(54481, 55289, 'Z')
    };

    public static int getGBKCode(String c) throws Exception {
        if (c.length() != 1) {
            throw new Exception("c must be a single character");
        }

        byte[] bytes = c.getBytes("GBK");
        if (bytes.length != 2) {
            throw new Exception("c must be a Chinese character");
        }
        return bytes[0] << 8 & 0xFF00 | bytes[1] & 0xFF;
    }

    public static String getFirstLetterSlow(String text) throws Exception {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < text.length(); i++) {
            String str = text.substring(i, i + 1);
            int code = getGBKCode(str);
            for (LetterRange range : mapping) {
                if (code >= range.start && code <= range.end) {
                    sb.append(range.letter);
                    break;
                }
            }
        }
        return sb.toString();
    }

代码解析

  • 首先,我们构造了一个LetterRange的类,用来存储拼音首字母的编码范围和拼音首字母,然后我们构造了一个mapping数组,用来存储所有的拼音首字母的编码范围和拼音首字母。
  • 文本的每个字符通过getGBKCode取得GBK编码,这个编码的范围肯定是在int的范围内,所以我们可以直接用int来存储
  • 通过遍历每个LetterRange获得这个汉字编码对应的拼音首字母,然后拼接到结果字符串中

优化

mapping是一个顺序的数组,我们的算法是通过遍历的方式,也就是如果要取Z的拼音,每次都需要遍历完整的mapping, 整个算法的复杂度,相当于n * m,其中n是mapping的长度,m是字符串的长度,这个算法的效率是非常低的。

所以我们引入一个最简单的优化,通过二分查找法来实现查询,这样算法的效率就提升了:

    public static char binarySearch(int code) {
        int start = 0;
        int end = mapping.length - 1;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (code >= mapping[mid].start && code <= mapping[mid].end) {
                return mapping[mid].letter;
            } else if (code < mapping[mid].start) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return '?';
    }

    public static String getFirstLetter(String text) throws Exception {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < text.length(); i++) {
            String str = text.substring(i, i + 1);
            int code = getGBKCode(str);
            char letter = binarySearch(code);
            sb.append(letter);
        }
        return sb.toString();
    }

完整代码请参考: Pinyin.java

总结

后端最基本的知识就包括了编码处理,虽然GBK的兼容性比较差,但是在一些场景中,我们仍然要学习和了解这些知识,熟悉编码的转换关系,对于我们的工作和学习都是非常有帮助的。

即便是最简单的查询需求,也是需要我们考虑效率的,我们可以通过二分查找法来提升效率,二分法在排序数组中查找元素的时间复杂度是O(logn),效率是远高于遍历的。

这个文章帮你学会了如何通过GBK编码来获取拼音首字毋,通过二分查找法来提升效率,希望对你有所帮助。

所有的后端面试常见的问题,我们每天都会在我们的编程群里面讨论和Code review, 欢迎大家加入我们的编程群,一起学习和进步。

编程交流群

欢迎大家关注 入职啦 (公众号: ruzhila) ,获取更多有趣的编程挑战题和技术干货!

友情链接:

Copyright© 2024 杭州园中葵科技有限公司 版权所有