男生找男友:我希望你至少是0.628,如果是0.942那就更好了。

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
[Google级团队]:实时大数据分析领域践行者
北京/深圳-大数据/搜索/机器学习职位
日志易机器大数据行业践行者Web/大数据/机器学习等职位-北京or深圳
把贵司招聘信息放这里
查看: 508|回复: 7
收起左侧

空气床 电面挂经

[复制链接] |试试Instant~ |关注本帖
duranneji 发表于 2018-2-24 04:08:06 | 显示全部楼层 |阅读模式

2018(1-3月) 码农类General 硕士 全职@Airbnb - 内推 - 技术电面  | Fail | 在职跳槽

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

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

x
听口音听不出来是哪儿的人 上来就说先做题 再聊简历. from: 1point3acres.com/bbs

题目是给一个转换规则来转换数字n
n是奇数 n = 3n + 1
n是偶数 n = n / 2

最后n总会经过很多次转换到1

问从一到一百万 需要转换次数最多的那个数字需要转换几次. Waral 鍗氬鏈夋洿澶氭枃绔,

乍一看是DP,但是想了半天,一紧张,总也想不出来,铁定是挂了

求教地里大神这个题怎么做

评分

1

查看全部评分

fallflame 发表于 2018-3-5 00:57:32 | 显示全部楼层
感觉我的做法比较简单

共计转换524次,最大的数字 837799
需要1G的内存,运行时间50ms
如果不用内存cache,大概1s多一点

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
public class MaxConvertTimes {


    @Test
    public void test() {

        fillArray();
        int max = 0;
        int maxi = 0;. from: 1point3acres.com/bbs
        for (int i = 1; i < 1_000_000; i++) {

            if (getTimes(i) > max) {
                max = getTimes(i);
                maxi = i;
            }
        }

        System.out.println(max);
        System.out.println(maxi);.1point3acres缃
    }

    private int[] times = new int[1_000_000];

    public void fillArray() {
        for (int i = 2; i < 1_000_000; i++) {
            getTimes(i);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        }
    }

    public int getTimes(long n) {

        if (n == 1) {
            return 0;. From 1point 3acres bbs
        }

        if (n < 1_000_000 && times[(int)n] != 0) {
            return times[(int)n];
        }

        int ans;

        if (n % 2 == 0) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
            ans = 1 + getTimes(n >> 1);
        } else {
            ans = 1 + getTimes(n * 3 + 1);. Waral 鍗氬鏈夋洿澶氭枃绔,
        }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        if (n < 1_000_000) {. visit 1point3acres.com for more.
            times[(int)n] = ans;. visit 1point3acres.com for more.
        }

. 1point 3acres 璁哄潧        return ans;
    }
}

回复 支持 2 反对 0

使用道具 举报

kinggarden2001 发表于 2018-2-24 04:52:38 | 显示全部楼层
这明明是个数学题 我在哪看到过 网上有
回复 支持 反对

使用道具 举报

nicemayi 发表于 2018-3-13 05:51:42 | 显示全部楼层
可以转化为树形问题:node当前值就是转换到的值,node有两个节点,左节点是3n + 1的反函数,右节点是n / 2的反函数,初始root的值就是1,树最终的叶子节点是不能再转换了(再转换就超过一百万了),然后看这棵树的最大深度是多少。

补充内容 (2018-3-13 06:06):
所以我猜答案是20次?(log2(1000000)= 19.93)
回复 支持 反对

使用道具 举报

nicemayi 发表于 2018-3-13 06:08:55 | 显示全部楼层
nicemayi 发表于 2018-3-13 05:51
可以转化为树形问题:node当前值就是转换到的值,node有两个节点,左节点是3n + 1的反函数,右节点是n / 2 ...

sorry没看清题目是要求最大深度而不是最小深度
回复 支持 反对

使用道具 举报

cptcpt 发表于 4 天前 | 显示全部楼层
fallflame 发表于 2018-3-5 00:57
感觉我的做法比较简单

共计转换524次,最大的数字 837799

数组可以开大一点
private int[] times = new int[3_000_000];
回复 支持 反对

使用道具 举报

stephenchen2016 发表于 3 天前 | 显示全部楼层
```
public int convert(int n) {
   int count = 0;
   while (n != 1) {
      if (n % 2 == 0) n = 2n;
      else n = 3 * n + 1;
      count++;
   }
   return count;
}. 鍥磋鎴戜滑@1point 3 acres
```.鏈枃鍘熷垱鑷1point3acres璁哄潧
回复 支持 反对

使用道具 举报

stephenchen2016 发表于 前天 00:14 | 显示全部楼层
stephenchen2016 发表于 2018-4-19 23:54
```
public int convert(int n) {. 鍥磋鎴戜滑@1point 3 acres
   int count = 0;

不好意思,表达的不是很清楚,意思是建一个dp[1_000_000 ]的array
每次下来记录一次,比如dp[1] = 0, dp[2] = 1, dp[3] = 7,  dp[4], 然后下一次循环的时候找一下之前有没有做过这个 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
再直接count + dp[n]就可以了。
  public int maxConvert() {
    int[] dp = new int[1_000_000];.鐣欏璁哄潧-涓浜-涓夊垎鍦
    int max = 0;. Waral 鍗氬鏈夋洿澶氭枃绔,
    for (int i = 1; i < 1_000_000; i++) {
      int ans = convert(i, dp);. 鍥磋鎴戜滑@1point 3 acres
      dp = ans;
      max = Math.max(ans, max);
    }
    return max;
  }

  private int convert(int n, int[] dp) {
    int count = 0;
    while (n != 1) {
      if (dp[n] != 0) return dp[n] + count;
      if (n % 2 == 0) n /= 2;
      else n = 3 * n + 1;
      count++;
    }
    return count;
  }

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴补充内容 (2018-4-20 00:18):
加一个条件(n > 0 && n < 1_000_000),防溢出
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-4-22 18:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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