百度面试题的java实现-阿里云开发者社区

开发者社区> 开发与运维> 正文
登录阅读全文

百度面试题的java实现

简介: 本文为原创,如需转载,请注明作者和出处,谢谢!     有一根27厘米的细木杆,在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。
本文为原创,如需转载,请注明作者和出处,谢谢!

    有一根27厘米的细木杆,在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。木杆很细,不能同时通过一只蚂蚁。开始时,蚂蚁的头朝左还是朝右是任意的,它们只会朝前走或调头,但不会后退。当任意两只蚂蚁碰头时,两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。编写程序,求所有蚂蚁都离开木杆的最小时间和最大时间。

java实现代码

public class test_ant
{
    
private int[] ants = new int[5];
    
// 1:左 2:右
    private int enumDirection[][] = new int[32][5];
    
private void initDirection()
    {
        
for (int i = 16, column = 0; i > 0; i = i / 2, column++)
        {
            
int n = 1;
            
for (int j = 0; j < 32; j++)
            {
                
if((j / i) % 2 == 0)
                    enumDirection[j][column] 
= 1;
                
else
                    enumDirection[j][column] 
= 2;
            }
        }
    }
    
private boolean checkAnts()
    {
        
for (int i = 0; i < 5; i++)
        {
            
if (ants[i] > 0 && ants[i] < 28)
                
return true;
        }
        
return false;
    }
    
private void changeDirection(int row, int col)
    {
        
if (enumDirection[row][col] == 1)
            enumDirection[row][col] 
= 2;
        
else
            enumDirection[row][col] 
= 1;
    }
    
public void antClimb()
    {
        initDirection();
        
for (int n = 0; n < 32; n++)
        {
            
int seconds = 0;
            ants[
0= 3;
            ants[
1= 7;
            ants[
2= 11;
            ants[
3= 17;
            ants[
4= 23;
            
while (checkAnts())
            {
                seconds
++;
                
for (int i = 0; i < ants.length; i++)
                {
                    
if (i < ants.length - 1)
                    {
                        
// 蚂蚁相遇
                        if ((ants[i] == ants[i + 1])
                                        
&& ((enumDirection[n][i] + enumDirection[n][i + 1]) == 3))
                        {
                            changeDirection(n, i);
                            changeDirection(n, i 
+ 1);
                        }
                    }
                    
if (enumDirection[n][i] == 1)
                        ants[i]
--;
                    
else
                        ants[i]
++;
                }
            }
            
for (int j = 0; j < 5; j++)
                System.out.print(enumDirection[n][j]);
            System.out.println(
"");
            System.out.println(seconds);
        }
    }
    
public static void main(String[] args)
    {
        
new test_ant().antClimb();
    }
}


其中ants数组保存了5只蚂蚁当前在竿上的位置
enumDirection枚举了所有的32种初始化方向,1代表向左,2代表向右

最短11秒, 最大25秒

运行结果

11111
23
11112
17
11112
23
11122
11
11112
23
11122
17
11122
23
11222
17
11112
23
11122
21
11122
23
11222
21
11122
23
11222
21
11222
23
12222
21
11112
25
11122
25
11122
25
11222
25
11122
25
11222
25
11222
25
12222
25
11122
25
11222
25
11222
25
12222
25
11222
25
12222
25
12222
25
22222
25




国内最棒的Google Android技术社区(eoeandroid),欢迎访问!

《银河系列原创教程》发布

《Java Web开发速学宝典》出版,欢迎定购

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
开发与运维
使用钉钉扫一扫加入圈子
+ 订阅

集结各类场景实战经验,助你开发运维畅行无忧

其他文章
最新文章
相关文章