面试遇到的一道coding题

前言

最近突然想去一线城市，所以又开始准备起面试啦。一场面试过程中遇到一道coding题，算不上算法题，有点偏实际业务又有点偏数据结构考察。LeetCode上类似的题都是easy，因为面试过程中我使用java8的stream方法把它AC的，最近又因为最近在写java8函数式编程的文章，所以特意记录一下。

上题

字符串压缩-把字符串出现的次数压缩
例如 aabbcd -> a2b2c1d1
例如 abcbc -> a1b1c2d1
假设字符串中只会出现，大小写字母

常规解法-哈希计数

常规解法的话就是一道很常见的哈希计数，纯体力活，当然啦这是面试的第一道开胃小菜。思路很简单，构建一个map利用map来去重，每次相同key就把map的value进行自步进为1的自增， 常规解法我就直接贴代码。

@Test
void strCompress() {
    String text = "aabcdsdsa";
    Map<Character, Integer> map = new HashMap<>(text.length());
    for (char c : text.toCharArray()) {
        Integer count = map.getOrDefault(c, 0);
        map.put(c, ++count);
    }
    StringBuilder builder = new StringBuilder(text.length());
    map.forEach((k, v) -> builder.append(k).append(v));
    System.out.println(builder.toString());
}

output: a3b1c1s2d2

值得注意三个点

1. 这里使用map原生的getOrDefault()方法来获取值，可以省略一次当冷启动时map里面不存在值的情况，统一了++count操作。
2. 拼接的时候使用的StringBuilder，如果使用使用“”+“”给面试官的影响会不太好，毕竟你不知道有多少个字符，在for循环里面进行拼接对GC不太友好。如果使用StringBuffer给面试官影响也不太好，因为代码中并不是多线程环境，没有竞态条件使用StringBuffer的性能不如StringBuilder好。一小段代码体现的细节还是很重要的，毕竟出这么简单的题目，不应该就是干一个体力活，还是要有更多的考量。
3. 遍历map的时候，可以直接使用forEach()。当然使用迭代器或者entrySet也不能说错，只是代码会没那么简洁。java8以后多了default的forEach方法，里面可以传入一个BiConsumer通过副作用做到拼接。

java8-stream进行分组解法

因为给的是一个String，美名其曰是压缩，但是其实就是把所有的char进行归类然后计数。如果这是sql，抬手就是select char, count(1) as count from table group by char。

但在java8的stream中也可以达到类似的功能，别怪我啰嗦，我分点来写这个代码(大佬请直接看代码)

1. 首要问题就是怎么把String变成流，这里我推荐使用String在jdk8新加的一个default方法-chars()，这个可以让字符串里面的char变成int然后装到IntStream中。
2. 我们拿到的是IntStream里面都是char对应的ascii，我们分组计数的对象本质还是char所以我们利用IntStream的mapToObj()，里面的Function就是把每个元素变成char型(其实会自动装箱Character), mapToObj(e -> (char) e)
3. 最后就是收集然后分组了，收集自然是collect()，里面是传入一个Collector接口，在Collectors中有一个groupingBy()的方法可以返回一个Collector接口。groupingBy()做的事情就是帮你分组，它的入参有两个，(第一个是Function接口，Function接口的入参是你流里面的元素，返回值是通过这个结果来分组)， (第二个又是一个Collector接口， 这个接口代表相同的分组元素聚在一起以后进行什么操作， 依然还是还是用Collectors静态类里面提供的方法，counting(), 这个方法可以把分组后的元素进行累加)。这一段比较绕，希望大家多读两遍，我尽力写了。最终collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));其中Function.identity()·等价于 e -> e，因为可能这个太频繁了，jdk单独做了一个静态方法。

最终代码如下

@Test
void strCompress() {
    String text = "aabcdsdsa";
    Map<Character, Long> map = text.chars()
            .mapToObj(e -> (char) e)
            .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
    StringBuilder builder = new StringBuilder(text.length());
    map.forEach((k, v) -> builder.append(k).append(v));
    System.out.println(builder.toString());
}

output: a3b1s2c1d2

最后再提一嘴，Collectors.groupingBy()的两个参数，第一个入参一个转换函数，题中是直接e -> e不转换所以用的是Function.identity()来简化， 第二个入参是Collector的接口(注意Collectors和Collector，前者是静态工具类)，一般我们都使用Collectors静态工具类的库函数，常用的有toList()把数据收集成list，counting()统计数据个数，summingInt()把数据累加成int

END