我就是好奇,男生女生找工作真的有什么区别?

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 864|回复: 8
收起左侧

空气床 电面挂经

[复制链接] |试试Instant~ |关注本帖
我的人缘0
duranneji 发表于 2018-2-24 04:08:06 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (9)
 
 
0% (0)  踩

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

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

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

x
听口音听不出来是哪儿的人 上来就说先做题 再聊简历

题目是给一个转换规则来转换数字n
n是奇数 n = 3n + 1
n是偶数 n = n / 2
.1point3acres网
最后n总会经过很多次转换到1

问从一到一百万 需要转换次数最多的那个数字需要转换几次

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

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

评分

参与人数 1大米 +2 收起 理由
stingray + 2 给你点个赞!

查看全部评分


上一篇:彭博社水电面
下一篇:Blackstone 新鲜校园面
我的人缘0
fallflame 发表于 2018-3-5 00:57:32 | 显示全部楼层
本楼: 【顶】   100% (2)
 
 
0% (0)   【踩】
全局: 顶  100% (16)
 
 
0% (0)  踩
感觉我的做法比较简单

共计转换524次,最大的数字 837799
需要1G的内存,运行时间50ms. 围观我们@1point 3 acres
如果不用内存cache,大概1s多一点

来源一亩.三分地论坛.
public class MaxConvertTimes {


    @Test. Waral 博客有更多文章,
    public void test() {

        fillArray();
        int max = 0;
        int maxi = 0;. 围观我们@1point 3 acres
        for (int i = 1; i < 1_000_000; i++) {

            if (getTimes(i) > max) {
                max = getTimes(i);. 1point 3acres 论坛
                maxi = i;.本文原创自1point3acres论坛
            }
        }

        System.out.println(max);
        System.out.println(maxi);. 牛人云集,一亩三分地
    }

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

    public void fillArray() {
. Waral 博客有更多文章,        for (int i = 2; i < 1_000_000; i++) {. 牛人云集,一亩三分地
            getTimes(i);
        }
    }
. 一亩-三分-地,独家发布
    public int getTimes(long n) {. more info on 1point3acres

        if (n == 1) {.留学论坛-一亩-三分地
            return 0;
        }

        if (n < 1_000_000 && times[(int)n] != 0) {. 1point3acres
            return times[(int)n];. more info on 1point3acres
        }

        int ans;

        if (n % 2 == 0) {
            ans = 1 + getTimes(n >> 1);
. 牛人云集,一亩三分地        } else {
            ans = 1 + getTimes(n * 3 + 1);
        }
. From 1point 3acres bbs
        if (n < 1_000_000) {
            times[(int)n] = ans;. 1point3acres
        }

        return ans;
    }
}

回复

使用道具 举报

我的人缘0
chipmonk 发表于 2018-4-23 07:58:15 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (2)
 
 
0% (0)  踩
中间n可能会超过1000000吧。比如n = 999999。
回复

使用道具 举报

我的人缘0
kinggarden2001 发表于 2018-2-24 04:52:38 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  87% (28)
 
 
12% (4)  踩
这明明是个数学题 我在哪看到过 网上有
回复

使用道具 举报

我的人缘0
nicemayi 发表于 2018-3-13 05:51:42 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (21)
 
 
8% (2)  踩
可以转化为树形问题:node当前值就是转换到的值,node有两个节点,左节点是3n + 1的反函数,右节点是n / 2的反函数,初始root的值就是1,树最终的叶子节点是不能再转换了(再转换就超过一百万了),然后看这棵树的最大深度是多少。
. 牛人云集,一亩三分地
补充内容 (2018-3-13 06:06):
所以我猜答案是20次?(log2(1000000)= 19.93)
回复

使用道具 举报

我的人缘0
nicemayi 发表于 2018-3-13 06:08:55 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (21)
 
 
8% (2)  踩
nicemayi 发表于 2018-3-13 05:51
可以转化为树形问题:node当前值就是转换到的值,node有两个节点,左节点是3n + 1的反函数,右节点是n / 2 ...

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

使用道具 举报

我的人缘0
cptcpt 发表于 2018-4-18 14:15:29 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  85% (29)
 
 
14% (5)  踩
fallflame 发表于 2018-3-5 00:57
感觉我的做法比较简单

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

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

使用道具 举报

我的人缘0
stephenchen2016 发表于 2018-4-19 23:54:58 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (5)
 
 
0% (0)  踩
```
public int convert(int n) {
   int count = 0;. 1point 3acres 论坛
   while (n != 1) {
      if (n % 2 == 0) n = 2n;
      else n = 3 * n + 1;
      count++;
   }
   return count;. 留学申请论坛-一亩三分地
}
```
Mobile Apps Category (English)728x90
回复

使用道具 举报

我的人缘0
stephenchen2016 发表于 2018-4-20 00:14:09 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (5)
 
 
0% (0)  踩
stephenchen2016 发表于 2018-4-19 23:54
```
public int convert(int n) {
   int count = 0;
. visit 1point3acres for more.
不好意思,表达的不是很清楚,意思是建一个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;
    for (int i = 1; i < 1_000_000; i++) {
      int ans = convert(i, dp);
      dp = ans;
      max = Math.max(ans, max);
    }. more info on 1point3acres
    return max;
  }

. From 1point 3acres bbs  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;. more info on 1point3acres
      else n = 3 * n + 1;. Waral 博客有更多文章,
      count++;
    }
    return count;
  }. more info on 1point3acres

补充内容 (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

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

custom counter

GMT+8, 2018-7-20 22:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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