查看: 4552|回复: 14
收起左侧

[字符串] 想问一道Google 常考的压缩字符串题目

|只看干货
陈润鹏 | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   84% (16)
 
 
15% (3)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
aabbbcc 压缩成 a*2b*3c*2,再解压缩原来的字符串里可能也有数和*

我想过 把字符串里原本的* 前面加一个井号 但是 这么一加 井号可能就压缩不了了。 对于数字 比如说 2aaab 这样直接压缩的话23*ab可能就会变成23个a 在解析的时候 不知道大家有没有好思路

评分

参与人数 1大米 +5 收起 理由
pengzewen37 + 5 不错

查看全部评分


上一篇:Remove Linked List Elements简单题但是dummy对象传递这地方不明白
下一篇:暑假刷题找队友
yueliu2366 2016-4-27 07:21:17 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   96% (31)
 
 
3% (1)    👎
练习一下,补上代码:
    String compress(String s) {
        StringBuilder sb = new StringBuilder();
        if (s == null || s.length() == 0) {
            return "";
        }
        char curChar = s.charAt(0);
        sb.append(curChar).append('*');
        int curLen = 1;
        for(int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == curChar) {
                curLen++;
            } else {
                sb.append(curLen);
                curChar = s.charAt(i);
                sb.append(curChar).append('*');
                curLen = 1;
            }
        }
         sb.append(curLen);
         return sb.toString();
    }
   
    String decompress(String s) {
        StringBuilder sb = new StringBuilder();
        if (s == null || s.length() == 0) {
            return "";
        }
        for(int i = s.length() - 1; i >= 0; i--) {
            int num = 0;
            int base = 1;
            while(s.charAt(i) != '*') {
                num += Integer.parseInt(s.charAt(i)) * base;
                base *= 10;
                i--;
            }
            i--;//此时i指向要恢复的字符
            char curChar = s.charAt(i);
            for(int j = 0; j < num; j++) {
                sb.append(curChar);
            }
        }
        return sb.reverse().toString();
    }
回复

使用道具 举报

yueliu2366 2016-4-27 05:54:25 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   96% (31)
 
 
3% (1)    👎
压缩比较容易。解压的话可以倒着来,比如a*2b*3c*2, 从后往前读直到遇到第一个星号,说明有2个c,然后直到字符串首
回复

使用道具 举报

 楼主| 陈润鹏 2016-4-27 09:14:54 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   84% (16)
 
 
15% (3)    👎
yueliu2366 发表于 2016-4-27 05:54
压缩比较容易。解压的话可以倒着来,比如a*2b*3c*2, 从后往前读直到遇到第一个星号,说明有2个c,然后直到 ...

对于数字呢 比如说3aaa=33*a这样就有歧义了
回复

使用道具 举报

yueliu2366 2016-4-27 09:53:19 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (31)
 
 
3% (1)    👎
陈润鹏 发表于 2016-4-27 09:14
对于数字呢 比如说3aaa=33*a这样就有歧义了

是不是我题意理解错了? 给的例子aabbbcc 压缩成 a*2b*3c*2,是不是说源字符串压缩成 “字符*个数”这种形式的?如果是这样3aaa不是应该压缩成3*1a*3吗?
回复

使用道具 举报

 楼主| 陈润鹏 2016-4-27 10:15:11 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   84% (16)
 
 
15% (3)    👎
yueliu2366 发表于 2016-4-27 09:53
是不是我题意理解错了? 给的例子aabbbcc 压缩成 a*2b*3c*2,是不是说源字符串压缩成 “字符*个数”这种 ...

这样的压缩 有时候却起不到压缩效果  就想问 有没有更好的判断方式 比如说有一些就不压缩。 3a2*a这样要更优一点
回复

使用道具 举报

yueliu2366 2016-4-27 10:46:50 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (31)
 
 
3% (1)    👎
陈润鹏 发表于 2016-4-27 10:15
这样的压缩 有时候却起不到压缩效果  就想问 有没有更好的判断方式 比如说有一些就不压缩。 3a2*a这样要 ...

哦,你意思是题目并没有要求压缩成什么指定的格式,只要自己设计一个压缩函数,一个解压函数就可以了?
回复

使用道具 举报

 楼主| 陈润鹏 2016-4-27 11:17:22 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   84% (16)
 
 
15% (3)    👎
yueliu2366 发表于 2016-4-27 10:46
哦,你意思是题目并没有要求压缩成什么指定的格式,只要自己设计一个压缩函数,一个解压函数就可以了?

大致follow这个idea就好
回复

使用道具 举报

renli3000 2016-4-27 11:19:32 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   93% (172)
 
 
6% (12)    👎
yueliu2366 发表于 2016-4-27 09:53
是不是我题意理解错了? 给的例子aabbbcc 压缩成 a*2b*3c*2,是不是说源字符串压缩成 “字符*个数”这种 ...

3aaa 没歧义但是aaa...3有歧义吧
回复

使用道具 举报

renli3000 2016-4-27 11:25:30 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   93% (172)
 
 
6% (12)    👎
renli3000 发表于 2016-4-27 11:19
3aaa 没歧义但是aaa...3有歧义吧

没问题 是我想错了
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表