Google全职电面1.20

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

这个题感觉就用bfs层序遍历就可以了吧

1. class ConvertInteger {
   
2.         public static int convertAtoB(int a, int b){
   
3.                 Queue<Integer> q = new LinkedList<>();
   
4.                 q.offer(a);
   
5.                
   
6.                 Set<Integer> visited = new HashSet<>();
   
7.                 visited.add(a);
   
8.                
   
9.                 int count = 0;
   
10.                 while(!q.isEmpty()){
    
11.                         int size = q.size();
    
12.                        
    
13.                         for(int i = 0; i < size; i++){
    
14.                                 int cur = q.poll();
    
15.                                 if(cur == b){
    
16.                                         return count;
    
17.                                 }
    
18.                                
    
19.                                 if(!visited.contains(cur + 1)){
    
20.                                         q.offer(cur + 1);
    
21.                                         visited.add(cur + 1);
    
22.                                 }
    
23.                                
    
24.                                 if(!visited.contains(cur - 1)){
    
25.                                         q.offer(cur - 1);
    
26.                                         visited.add(cur - 1);
    
27.                                 }
    
28.                                
    
29.                                 if(!visited.contains(cur * 2)){
    
30.                                         q.offer(cur * 2);
    
31.                                         visited.add(cur * 2);
    
32.                                 }
    
33.                                
    
34.                         }
    
35.                        
    
36.                         count++;
    
37.                 }
    
38.                
    
39.                 return count;
    
40.         }
    
41.        
    
42.         public static void main(String[] args) {
    
43.                 int res = convertAtoB(10, 18);
    
44.                 System.out.println(res);
    
45.         }
    
46. }

复制代码

用了hashset之后时间复杂度应该也不是o(3 ^ k)吧

dsdgjhbxewj1121 发表于 2017-2-8 08:21
这个题感觉就用bfs层序遍历就可以了吧

你的意思是从a开始建一个tree 每层添加做一步操作 然后产生的node 第一个出现b的 返回高度么。

dxdeidara 发表于 2017-2-8 08:28
你的意思是从a开始建一个tree 每层添加做一步操作 然后产生的node 第一个出现b的 返回高度么。

嗯嗯我是这么想的

dietpepsi 发表于 2017-2-8 07:21
是的呀 字数字数字数字数

拜大神。。。。。。。。竟然见到本尊

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies