10月28,K神开课讲数据科学,你来吗?


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 331|回复: 4
收起左侧

彭博电面

[复制链接] |试试Instant~ |关注本帖
wadephz 发表于 5 天前 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 硕士 全职@Bloomberg - 猎头 - 技术电面 |Pass在职跳槽

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

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

x
给一个起始数和目标数,只有两个运算(*2和/3),求从起始数到目标数的最短运算步数?解法:用BFS做,把每个数看成一个图上的一个点。

评分

1

查看全部评分

fwy4231 发表于 5 天前 | 显示全部楼层
求问一下楼主,除3操作出来的是省略余数嘛?是不是还得价格判断出现0的自环情况。。。谢谢!
回复 支持 反对

使用道具 举报

zorrowei 发表于 昨天 07:01 | 显示全部楼层
你好!我写了如下BFS code, 做了简单测试都是正确结果
    public int pathBFS(int start, int target) {
        if (start == target) {
            return 0; //early termination
        } else if (start == 0) {
            return -1; // from zero, we cannot reach any non-zero number via * 2 or / 3
        } else if (start * target < 0) { // if either start or target is negative, we cannot find such a path
            return -1;
        }
        Node root = new Node(start);
        Map<Integer, Node> map = new HashMap<>();        // check if visited        map.put(start, root);        //queue to BFS traversal visit nodes
        Queue<Node> q = new LinkedList<>();
        q.offer(root);
        int countpath = 0;
        while (!q.isEmpty()) {
            
int size = q.size();
            for (int i = 0; i < size; i++) {
                Node cur = q.poll()
;                //find target
                if (cur.val == target) {
                    
return countpath;
                }                //cur.val == 0, do not move on
               
if (cur.val == 0) {
                    
continue;
                }
               
if (!map.containsKey(cur.val * 2)) {
                    map.put(cur.
val * 2, new Node(cur.val * 2));
                    q.offer(map.get(cur.val * 2));
                }
               
if (!map.containsKey(cur.val / 3)) {
                    map.put(cur.
val / 3, new Node(cur.val / 3));
                    q.offer(map.get(cur.val / 3));
                }
            }. more info on 1point3acres.com
            countpath++
;
        }
        
return countpath;
    }
}


class Node {
    int val;    // left.val = val * 2    Node left;    // right.val = val / 3;    Node right;
    public Node(int val) {
        
this.val = val;.1point3acres缃
    }
}

回复 支持 反对

使用道具 举报

agraynel 发表于 昨天 14:07 | 显示全部楼层
zorrowei 发表于 2017-9-19 07:01
你好!我写了如下BFS code, 做了简单测试都是正确结果
    public int pathBFS(int start, int target) { ...

额。。为什么不直接queue<integer>啊?直接存数字,不需要node吧 。
如果说map是为了减少重复的数字的话,用set吧
回复 支持 反对

使用道具 举报

zorrowei 发表于 2 小时前 | 显示全部楼层
agraynel 发表于 2017-9-19 14:07.鏈枃鍘熷垱鑷1point3acres璁哄潧
额。。为什么不直接queue啊?直接存数字,不需要node吧 。
如果说map是为了减少重复的数字的话,用set吧
. 鍥磋鎴戜滑@1point 3 acres
也可以。你的办法更省空间。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-20 03:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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