一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 1648|回复: 1
收起左侧

google foobar level3

[复制链接] |试试Instant~ |关注本帖
wujingzhishui 发表于 2016-9-28 11:05:15 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@ - Other - 在线笔试 |Other其他

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

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

x
google foobar level3最后一题, 做了很久都超时,看看地里小伙伴有没有比较好的solution Write a function which takes a positive integer as a string and returns the minimum number of operations needed to transform the number to 1. The number is up to 309 digits long, so there won't too many character than you can express in that many digits. The transform process is limited to three operations: 1. Add 1 2. Subtract 1 3. Divide the number by 2 (only even number allow here)
我是用dfs走一遍,然后用memorization剪枝优化,在我自己电脑上优化后速度提升了几十倍,但是无奈还是time exceed,有没有更佳优化的方法呢?我贴下我的code看看大家可不可以优化更好:
  1. <div>public static int answer(String n) { </div><div>.鏈枃鍘熷垱鑷1point3acres璁哄潧
  2. </div><div>        // Your code goes here.</div><div>        return dfs(n, 0, new HashMap<String, Integer>());</div><div>    } </div><div>      private static int dfs(String num, int step,Map<String,Integer> memory){</div><div>        if(num.equals("1")){</div><div>            return step;</div><div>        }</div><div>
  3. </div><div>        Integer size = memory.get(num);</div><div>        if(size != null && size < step){</div><div>            return Integer.MAX_VALUE;</div><div>        }</div><div>        memory.put(num, step);</div><div>        int min = Integer.MAX_VALUE;</div><div>        int lastDigit = num.charAt(num.length() - 1) - '0';</div><div>        if(lastDigit % 2 == 0){</div><div>            min = Math.min(min,dfs(divideBy2(num), step + 1, memory));</div><div>        }else{</div><div>             min = Math.min(min, dfs(divideBy2(num), step + 2, memory));           </div><div>            min = Math.min(min, dfs(divideBy2(plusOne(num)), step + 2, memory));</div><div>        }</div><div>        return min;</div><div>    }</div><div>    private static String plusOne(String num){</div><div>        StringBuilder sb = new StringBuilder();</div><div>        int carry = 1;</div><div>        int i = 0;</div><div>        for(i = num.length() - 1; i >=0; i--){</div><div>            if(carry == 0){</div><div>                break;</div><div>            }</div><div>            int d = (carry + num.charAt(i) - '0') % 10;</div><div>            carry = (carry + num.charAt(i) - '0') / 10;</div><div>            sb.insert(0, d);</div><div>        }</div><div>        if(carry ==0){</div><div>            sb.insert(0, num.substring(0, i + 1));</div><div>        }</div><div>        if(carry == 1){</div><div>            sb.insert(0, carry);</div><div>        }</div><div>        return sb.toString();</div><div>    }</div><div>    private static String divideBy2(String num){</div><div>        StringBuilder sb = new StringBuilder();</div><div>        int x = 0;</div><div>        for(int i = 0; i < num.length(); i++){</div><div>            int d = (x * 10 + num.charAt(i) - '0') / 2 ;</div><div>            x = (num.charAt(i) - '0') % 2 ;</div><div>            if( i > 0 || (i == 0 && d != 0))</div><div>                sb.append(d);</div><div>        }</div><div>    </div><div>        return sb.toString();</div><div>    }</div>
复制代码



补充内容 (2016-9-28 11:07):.鏈枃鍘熷垱鑷1point3acres璁哄潧
不知道为啥圈了代码变成这样了,版主能帮忙把代码删了么,我再添加
 楼主| wujingzhishui 发表于 2016-9-28 11:07:15 | 显示全部楼层
public static int answer(String n) {

        // Your code goes here.
        return dfs(n, 0, new HashMap<String, Integer>());. more info on 1point3acres.com
    }
      private static int dfs(String num, int step,Map<String,Integer> memory){. 鍥磋鎴戜滑@1point 3 acres
        if(num.equals("1")){
            return step;
        }

        Integer size = memory.get(num);
        if(size != null && size < step){
            return Integer.MAX_VALUE;
        }
        memory.put(num, step);
        int min = Integer.MAX_VALUE;. visit 1point3acres.com for more.
        int lastDigit = num.charAt(num.length() - 1) - '0';
        if(lastDigit % 2 == 0){
            min = Math.min(min,dfs(divideBy2(num), step + 1, memory));
        }else{
             min = Math.min(min, dfs(divideBy2(num), step + 2, memory));           
            min = Math.min(min, dfs(divideBy2(plusOne(num)), step + 2, memory));. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        }.鐣欏璁哄潧-涓浜-涓夊垎鍦
        return min;
    }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    private static String plusOne(String num){
        StringBuilder sb = new StringBuilder();
        int carry = 1;
        int i = 0;
        for(i = num.length() - 1; i >=0; i--){. 鍥磋鎴戜滑@1point 3 acres
            if(carry == 0){
                break;
            }.鐣欏璁哄潧-涓浜-涓夊垎鍦
            int d = (carry + num.charAt(i) - '0') % 10;
            carry = (carry + num.charAt(i) - '0') / 10;
            sb.insert(0, d);
        }
        if(carry ==0){
            sb.insert(0, num.substring(0, i + 1));
        }
        if(carry == 1){
            sb.insert(0, carry);
        }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        return sb.toString();
    }
    private static String divideBy2(String num){
        StringBuilder sb = new StringBuilder();. from: 1point3acres.com/bbs
        int x = 0;
        for(int i = 0; i < num.length(); i++){
            int d = (x * 10 + num.charAt(i) - '0') / 2 ;
            x = (num.charAt(i) - '0') % 2 ;
            if( i > 0 || (i == 0 && d != 0))
                sb.append(d);
        }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    . From 1point 3acres bbs
        return sb.toString();. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    }
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-12-15 12:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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