百词斩算法面试题--字符串压缩

题目忘了,大概是说,输入aabcccccaaa,写个算法输出a2b1c5a3

实现:

@Slf4j
public class DepressForBaiCiZhan {
    public static String doDepress(String str) {
        //字符串为空直接返回
        if ("".equals(str)) return str;
        StringBuilder buffer = new StringBuilder();
        //用第n个字符去和第n+1个字符对比
        char c = str.charAt(0);
        //记录字符出现次数,默认为1
        int repeat = 1;
        for (int i = 1; i < str.length(); i++) {
            if (c == str.charAt(i)) {
                //如果第n个字符和第n+1个字符相等,则出现次数+1
                repeat++;
            } else {
                //如果第n个字符和第n+1个字符不相等,则拼接在字符串后面
                buffer.append(c).append(repeat);
                //拼接完后重置当前字符串
                c = str.charAt(i);
                //重置字符出现次数
                repeat = 1;
            }
        }
        //最后一组在for循环里是没有拼接的,这里再来拼接
        return buffer.append(c).append(repeat).toString();
    }

    public static void main(String[] args) {
        log.info("我爱百词斩=======>{}",doDepress("我爱百词斩"));//我爱百词斩=======>我1爱1百1词1斩1
        log.info("我爱百百词词斩斩==>{}",doDepress("我爱百百词词斩斩"));//我爱百百词词斩斩==>我1爱1百2词2斩2
        log.info("aabcccccaaa===>{}",doDepress("aabcccccaaa"));//aabcccccaaa===>a2b1c5a3
    }
}

解析:


这个题最开始我理解错了,最开始是利用hashMap键的唯一性,导致输出是a5b1c5(这个算法在这里传送门),然而人家要的是a2b1c5a3,后面改了下算法,也是动态字符串拼接,需要维护一个当前对比字符,一个字符出现次数,用第n个字符去和第n+1个字符对比,相等则出现次数+1,不相等则拼接在字符串后面,注意一点就是,因为我这里是先拼接再重置当前字符串和出现次数,所以最后一组字符是没拼接的,需要在返回前单独拼接。


上一篇:乐在其中设计模式(C#) - 状态模式(State Pattern)


下一篇:Oracle后台专家解决library cache锁争用的终极武器