一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 4523|回复: 40
收起左侧

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

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

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

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

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

x
发个电面fail电面面经

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




.1point3acres缃
补充内容 (2016-11-13 03:47):
aaabcbc 压缩成 3[a]2[bc] 这个例子举的不好,压缩后比压缩前还长,这种情况就不用压缩了,所以,好难好难

评分

1

查看全部评分

本帖被以下淘专辑推荐:

yydcool 发表于 2016-11-15 11:03:31 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
scoi2003原题
回复 支持 1 反对 0

使用道具 举报

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

使用道具 举报

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

使用道具 举报

sccnju 发表于 2016-11-13 02:39:27 | 显示全部楼层
搬个板凳等待大神解答第二问。。。
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

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. more info on 1point3acres.com
为何会fail, 你第一问做出来了吗?
. Waral 鍗氬鏈夋洿澶氭枃绔,
第一问做出来,第二问,真的不会
回复 支持 反对

使用道具 举报

 楼主| 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) {
        if (str == null || str.length() == 0) {. From 1point 3acres bbs
            return "";
        }
        
        int i = 0;
        int j = 0;. Waral 鍗氬鏈夋洿澶氭枃绔,
        String pattern = null;
        StringBuilder builder = new StringBuilder();
        while (i < str.length()) {
            j = 0;.鏈枃鍘熷垱鑷1point3acres璁哄潧
            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))) {
                        if (cur + len > j) {
                            j = cur + len;
                            pattern = str.substring(cur, cur + len);
                        }
                        cur = cur + len;
                    } else {
                        break;
                    }
                }
            }
            if (j == 0) {
                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(']');. visit 1point3acres.com for more.
                }
                i = j;-google 1point3acres
            }
        }
跟之前说的算法的一样,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
. From 1point 3acres bbs
或者. From 1point 3acres bbs

3[a]bca2[bc]

长度都是12. 你是不是被黑了?. more info on 1point3acres.com

补充内容 (2016-11-14 13:02):
如果觉得比原字符串长,可以在原字符串前加重复的字母.
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

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

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-2-27 15:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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