一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1438|回复: 14
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
陈润鹏 发表于 2016-4-27 04:37:57 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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

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

评分

1

查看全部评分

yueliu2366 发表于 2016-4-27 07:21:17 | 显示全部楼层
练习一下,补上代码:
    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();
    }
回复 支持 1 反对 0

使用道具 举报

yueliu2366 发表于 2016-4-27 05:54:25 来自手机 | 显示全部楼层
压缩比较容易。解压的话可以倒着来,比如a*2b*3c*2, 从后往前读直到遇到第一个星号,说明有2个c,然后直到字符串首
回复 支持 1 反对 0

使用道具 举报

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

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

使用道具 举报

yueliu2366 发表于 2016-4-27 09:53:19 | 显示全部楼层
陈润鹏 发表于 2016-4-27 09:14
对于数字呢 比如说3aaa=33*a这样就有歧义了

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

使用道具 举报

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

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

使用道具 举报

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

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

使用道具 举报

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

大致follow这个idea就好
回复 支持 反对

使用道具 举报

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

3aaa 没歧义但是aaa...3有歧义吧
回复 支持 反对

使用道具 举报

renli3000 发表于 2016-4-27 11:25:30 | 显示全部楼层
renli3000 发表于 2016-4-27 11:19
3aaa 没歧义但是aaa...3有歧义吧

没问题 是我想错了
回复 支持 反对

使用道具 举报

yueliu2366 发表于 2016-4-29 10:03:13 | 显示全部楼层
请问楼主,你答完谷歌oa之后,多久收到约电面的通知呢
回复 支持 反对

使用道具 举报

gyzjay 发表于 2016-4-29 11:37:45 | 显示全部楼层
加括号呗。数量大于1的部分用括号包起来。
回复 支持 反对

使用道具 举报

gyzjay 发表于 2016-4-29 11:38:43 | 显示全部楼层
gyzjay 发表于 2016-4-29 11:37
加括号呗。数量大于1的部分用括号包起来。

不过这样的话。*号无论有几个都要用括号包起来。
回复 支持 反对

使用道具 举报

 楼主| 陈润鹏 发表于 2016-4-30 05:54:43 | 显示全部楼层
yueliu2366 发表于 2016-4-29 10:03
请问楼主,你答完谷歌oa之后,多久收到约电面的通知呢

一个星期
回复 支持 反对

使用道具 举报

 楼主| 陈润鹏 发表于 2016-4-30 05:55:05 | 显示全部楼层
yueliu2366 发表于 2016-4-29 10:03
请问楼主,你答完谷歌oa之后,多久收到约电面的通知呢

最囧的是 我以为自己被拒了 结果是她一直打不通我的电话
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 19:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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