一亩三分地论坛

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

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

狗家电面 fail,顺便问问第二题怎么做

[复制链接] |试试Instant~ |关注本帖
sunnyroom 发表于 2016-11-13 01:38:40 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Google - 猎头 - 技术电面 |Fail在职跳槽

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

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

x
发个电面fail电面面经

1. leetcode 394
2.  第一题反过来,要求压缩到最短。
     e.g  
aaabcbc 压缩成 3[a]2[bc]
axxxxaxxxxaxxxx 压缩成 3[a3[x]]    这个没做出来,现在还是不会。.鐣欏璁哄潧-涓浜-涓夊垎鍦
    求大神解答一下。




鏉ユ簮涓浜.涓夊垎鍦拌鍧.
补充内容 (2016-11-13 03:47):
aaabcbc 压缩成 3[a]2[bc] 这个例子举的不好,压缩后比压缩前还长,这种情况就不用压缩了,所以,好难好难

评分

1

查看全部评分

yydcool 发表于 2016-11-15 11:03:31 | 显示全部楼层
scoi2003原题
回复 支持 1 反对 0

使用道具 举报

qiuxuxing007 发表于 2016-11-13 02:07:07 | 显示全部楼层
为何会fail, 你第一问做出来了吗?
回复 支持 反对

使用道具 举报

神罗天征 发表于 2016-11-13 02:14:16 | 显示全部楼层
同求第二问解法……感觉考了第一题,必有follow up
回复 支持 反对

使用道具 举报

sccnju 发表于 2016-11-13 02:39:27 | 显示全部楼层
搬个板凳等待大神解答第二问。。。
回复 支持 反对

使用道具 举报

mikeyangh1992 发表于 2016-11-13 02:43:36 | 显示全部楼层
前排同关注一下follow-up
回复 支持 反对

使用道具 举报

slarkzz 发表于 2016-11-13 03:02:56 | 显示全部楼层
同求第二题解法
回复 支持 反对

使用道具 举报

helloc93 发表于 2016-11-13 03:32:28 | 显示全部楼层
关注下第二题的解法
回复 支持 反对

使用道具 举报

 楼主| sunnyroom 发表于 2016-11-13 03:45:43 | 显示全部楼层
qiuxuxing007 发表于 2016-11-13 02:07
为何会fail, 你第一问做出来了吗?
.1point3acres缃
第一问做出来,第二问,真的不会
回复 支持 反对

使用道具 举报

 楼主| sunnyroom 发表于 2016-11-13 03:46:59 | 显示全部楼层
aaabcbc 压缩成 3[a]2[bc] 这个例子举的不好,压缩后比压缩前还长,这种情况就不用压缩了,所以,好难好难
回复 支持 反对

使用道具 举报

hmy0823 发表于 2016-11-13 04:47:28 | 显示全部楼层
同求follow up问题的解决方法
回复 支持 反对

使用道具 举报

jiongjiongyoush 发表于 2016-11-13 04:57:07 | 显示全部楼层
同马克一下。。。。decode string以前刷g onsite面经有人遇到过
回复 支持 反对

使用道具 举报

a529384424 发表于 2016-11-13 12:59:54 | 显示全部楼层
mark一下,坐等大神解答
回复 支持 反对

使用道具 举报

cezheng2 发表于 2016-11-13 13:51:12 | 显示全部楼层
先寫一個不嵌套的encode的函數,然後不斷encode直到encode的output和input的字串相等可以嘛?
回复 支持 反对

使用道具 举报

xiangminxufsu 发表于 2016-11-13 17:00:15 | 显示全部楼层
坐等大神来破解 =。=
回复 支持 反对

使用道具 举报

NotAfraid2009 发表于 2016-11-14 03:04:59 | 显示全部楼层
感觉这样应该可行。
1: 从一个没折叠的位置开始,从长度为1,一直找到剩下长度的一半,找能折叠的最长的长度
2: 对能折叠的pattern进行递归,继续折叠。
3: 从下一个没有折叠的位置开始。
感觉写起来也挺麻烦的。
回复 支持 反对

使用道具 举报

NotAfraid2009 发表于 2016-11-14 04:39:47 | 显示全部楼层
    public String encode(String str) {. more info on 1point3acres.com
        if (str == null || str.length() == 0) {
            return "";
        }. 鍥磋鎴戜滑@1point 3 acres
        
        int i = 0;. visit 1point3acres.com for more.
        int j = 0;
        String pattern = null;
        StringBuilder builder = new StringBuilder();
        while (i < str.length()) {
            j = 0;
            for (int len = 1; len <= (str.length() - i) / 2 && i + len <= str.length(); len++) {
                String p = str.substring(i, i + len);
                int cur = i + len;
                while (cur + len <= str.length()) {
                    if (p.equals(str.substring(cur, cur + len))) {. Waral 鍗氬鏈夋洿澶氭枃绔,
                        if (cur + len > j) {. visit 1point3acres.com for more.
                            j = cur + len;
                            pattern = str.substring(cur, cur + len);
                        }
                        cur = cur + len;
                    } else {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                        break;
                    }
                }
            }
            if (j == 0) {. 鍥磋鎴戜滑@1point 3 acres
                builder.append(str.substring(i, i + 1));
                i = i + 1;
            } else {
                int count = (j - i) / pattern.length();
                if (count == 1) {
                    builder.append(encode(pattern));
                } else {
                    builder.append(count).append('[').append(encode(pattern)).append(']');. 1point 3acres 璁哄潧
                }
                i = j;
            }
        }
跟之前说的算法的一样,i表示需要encode的字符串的起始位置,j表示结束位置。
当j大于之前最远的位置(有点贪心的意思),记录找到的pattern。
最后根据j的位置判断如何折叠,如果j的位置为0,遍历过所有长度,说明没有可以折叠的串,i + 1;如果不为0, 就递归当前找到的pattern。
这个作为follow up如果还让完全写出代码,有点过分了,时间肯定不够 =。=
回复 支持 反对

使用道具 举报

nycowboy 发表于 2016-11-14 04:47:23 | 显示全部楼层
第二题可以用一个stack就解决了吧,不停地尝试和stack顶部的元素合并
回复 支持 反对

使用道具 举报

simonwoo 发表于 2016-11-14 12:59:15 | 显示全部楼层
注意第二个题很可能不止一个结果,比如aaabcabcbc可以被encode成:

2[a]2[abc]bc

或者

3[a]bca2[bc]
. Waral 鍗氬鏈夋洿澶氭枃绔,
长度都是12. 你是不是被黑了?
.鏈枃鍘熷垱鑷1point3acres璁哄潧
补充内容 (2016-11-14 13:02):
如果觉得比原字符串长,可以在原字符串前加重复的字母.
回复 支持 反对

使用道具 举报

Aron930130 发表于 2016-11-15 06:23:36 | 显示全部楼层
NotAfraid2009 发表于 2016-11-14 04:39
public String encode(String str) {
        if (str == null || str.length() == 0) {
            ...

这个输入如果是axxxxaxxxxaxxxx,输出的答案不对吧?
回复 支持 反对

使用道具 举报

Aron930130 发表于 2016-11-15 06:26:32 | 显示全部楼层
Aron930130 发表于 2016-11-15 06:23
这个输入如果是axxxxaxxxxaxxxx,输出的答案不对吧?

哦哦,是我自己看错了...无视我
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 17:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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