近期论坛无法登录的解决方案


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

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

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

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
发个电面fail电面面经

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


.鏈枃鍘熷垱鑷1point3acres璁哄潧


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

评分

1

查看全部评分

本帖被以下淘专辑推荐:

Frankluo 发表于 2016-11-25 18:26:41 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地

  1. class Solution{
  2.         public static boolean checkRepeating(String s, int l, int r, int start, int end){
  3.                 if( (end-start) % (r-l) != 0 ){
  4.                         return false;
  5.                 }
  6.                 int len = r-l;. more info on 1point3acres.com
  7.                 String pattern = s.substring(l, r);
  8.                 for(int i = start; i +len <= end; i+=len){
  9.                         if(!pattern.equals(s.substring(i, i+len))){
  10.                                 return false;
  11.                         }
  12.                 }
  13.                 return true;
  14.         }
  15. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  16.         public static int getLength(int plen, int slen){
  17.                 return (int)(Math.log10(slen/plen)+1);
  18.         }. 1point3acres.com/bbs

  19.         public static String shortestEncodeString(String s){
  20.                 int len = s.length();
  21.                 int[][] dp = new int[len+1][len+1];
  22.                 for(int i = 1; i <= len; ++i){
  23.                         for(int j = 0; j < i; ++j){
  24.                                 dp[j][i] = i-j;
  25.                         }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  26.                 }

  27.                 Map<String, String> dpMap = new HashMap<>();. From 1point 3acres bbs

  28.                 for(int i = 1; i <= len; ++i){
  29.                         for(int j = i-1; j >= 0; --j){
  30.                                 String temp = s.substring(j, i);
  31.                                 if(dpMap.containsKey(temp)){. 1point 3acres 璁哄潧
  32.                                         dp[j][i] = dpMap.get(temp).length();
  33.                                         continue;
  34.                                 }
  35.                                 String ans = temp;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  36.                                 for(int k = j+1; k <= i; ++k){
  37.                                         String leftStr = s.substring(j, k);
  38.                                         String rightStr = s.substring(k, i);
  39.                                         if(dp[j][i] > dp[j][k] + dp[k][i]){
  40.                                                 dp[j][i] = dp[j][k] + dp[k][i];
  41.                                                 ans = dpMap.get(leftStr) + dpMap.get(rightStr);
  42.                                         }
  43.                                         if( checkRepeating(s, j, k, k, i)
  44.                                                 && ( 2 + getLength(k-j, i-j) + dp[j][k] < dp[j][i]) ){
  45.                                                 dp[j][i] = 2 + getLength(k-j, i-j) + dp[j][k];
  46.                                                 ans = String.valueOf((i-j)/(k-j)) +"["+ dpMap.get(leftStr) +"]";
  47.                                         }
  48.                                 }
  49.                                 dpMap.put(temp,ans);
  50.                         }
  51.                 }
  52.                 return dpMap.get(s);
  53.         }

  54.         public static void main(String[] arg){
  55.                 System.out.println( sortestEncodeString(arg[0]) );
  56.         }
  57. }
复制代码
回复 支持 1 反对 0

使用道具 举报

yydcool 发表于 2016-11-15 11:03:31 | 显示全部楼层
关注一亩三分地微博:
Warald
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, 你第一问做出来了吗?
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第一问做出来,第二问,真的不会
回复 支持 反对

使用道具 举报

 楼主| 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) {
            return "";
        }. 鍥磋鎴戜滑@1point 3 acres
        
        int i = 0;
        int j = 0;
        String pattern = null;
        StringBuilder builder = new StringBuilder();. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        while (i < str.length()) {.1point3acres缃
            j = 0;. 鍥磋鎴戜滑@1point 3 acres
            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()) {. more info on 1point3acres.com
                    if (p.equals(str.substring(cur, cur + len))) {
                        if (cur + len > j) {
                            j = cur + len;
                            pattern = str.substring(cur, cur + len);. 1point 3acres 璁哄潧
                        }
                        cur = cur + len;
                    } else {
                        break;
                    }
                }
            }
            if (j == 0) {
                builder.append(str.substring(i, i + 1));
                i = i + 1;. 鍥磋鎴戜滑@1point 3 acres
            } else {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                int count = (j - i) / pattern.length();
                if (count == 1) {
                    builder.append(encode(pattern));
                } else {
                    builder.append(count).append('[').append(encode(pattern)).append(']');
                }
                i = j;
            }
        }
跟之前说的算法的一样,i表示需要encode的字符串的起始位置,j表示结束位置。
. 1point3acres.com/bbs当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
-google 1point3acres
或者

3[a]bca2[bc]

长度都是12. 你是不是被黑了?
. 鍥磋鎴戜滑@1point 3 acres
补充内容 (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,输出的答案不对吧?
.1point3acres缃
哦哦,是我自己看错了...无视我
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-6-27 10:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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