题目描述:
有一根27厘米的细木杆,在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。木杆很细,不能同时通过一只蚂蚁。开始时,蚂蚁的头朝左还是朝右是任意的,它们只会朝前走或调头,但不会后退。当任意两只蚂蚁碰头时,两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。编写程序,求所有蚂蚁都离开木杆的最小时间和最大时间。
之前给出了一个递归的解法,觉得还不够好,因为效率较低,所以用了一个非递归的方法来处理。同样算法步骤都在code的注释里有。
package com.leochan;
public class DirectAntWalker {
public static int totalLength = 27;
public static void main(String[] args) {
directTest();
}
private static void directTest() {
int count = 0;
for (int d1 = -1; d1 <= 1; d1 += 2) {
for (int d2 = -1; d2 <= 1; d2 += 2) {
for (int d3 = -1; d3 <= 1; d3 += 2) {
for (int d4 = -1; d4 <= 1; d4 += 2) {
for (int d5 = -1; d5 <= 1; d5 += 2) {
count++;
// 构造蚂蚁数组
int[] ants = { 3 * d1, 7 * d2, 11 * d3, 17 * d4,
23 * d5 };
// 设置index初始取值范围
int idx1 = 0, idx2 = 4;
int totalTime = 0;
int i = 0;
while (true) {
// 如果有蚂蚁先达到边界,一定是发生在边界处
// 如果第一只蚂蚁已经达到边界,就忽略这只蚂蚁
if (ants[idx1] == 0
|| ants[idx1] == totalLength) {
idx1++;
}
// 如果最后一只蚂蚁已经达到边界,就忽略这只蚂蚁
if (ants[idx2] == 0
|| ants[idx2] == totalLength) {
idx2--;
}
// 如果当前可访问的下界超过上界,就跳出循环
if (idx1 > idx2)
break;
// 如果下届等于上界,则说明仅有一只蚂蚁还没有走出去。
else if (idx1 == idx2) {
if (ants[idx1] < 0) {
totalTime -= ants[idx1];
} else {
totalTime += (totalLength - ants[idx1]);
}
break;
}
// 对于其他情况让 所有的蚂蚁走一步,如果出现了蚂蚁位置重合,就让重合的2只蚂蚁转向
ants[idx1] = ants[idx1] + 1;
for (i = idx1 + 1; i <= idx2; i++) {
ants[i] = ants[i] + 1;
if (ants[i] + ants[i - 1] == 0) {
ants[i] *= -1;
ants[i - 1] *= -1;
}
}
// 消耗的时间递增1。
totalTime++;
}
System.out.print("count=" + count + " d1=" + d1
+ " d2=" + d2 + " d3=" + d3 + " d4=" + d4
+ " d5=" + d5);
System.out.println(" totalTime=" + totalTime);
}
}
}
}
}
}
}
欢迎各位来指正。
分享到:
相关推荐
整理了部分面试题包含了各大互联网,百度、阿里、京东、腾讯、蚂蚁金服、中国平安、商汤科技、拼多多、oppo、唯品会等,全部已整理为pdf文档 上海-拼多多-Java高级.pdf 上海-携程-Java高级.pdf 北京-京东-Java中级....
01 java面试——北京-百度-Java中级.pdf 02 java面试——北京-京东-Java中级.pdf 03 java面试——广州-唯品会-Java大数据开发工程师.pdf 04 java面试——杭州-阿里云-Java中级.pdf 05 java面试——杭州-蚂蚁金服-...
2021Java大厂面试题——大厂真题之蚂蚁金服-Java高级.pdf
【Java面试资料】-蚂蚁金服面试题总结
互联网企业面试真题 深圳-OPPO.pdf 深圳-银盛支付-Java中级.pdf 深圳-中国平安-Java中级.pdf 深圳-商汤科技.pdf 深圳-腾讯.pdf 深圳-乐信.pdf 深圳-蚂蚁金服.pdf 上海-携程.pdf 深圳-丰巢科技.pdf 厦门-中软国际-...
2021Java大厂面试题——大厂真题之蚂蚁金服-资深工程师.pdf
2018 年蚂蚁课堂(每特教育) Java工程师面试宝典-V1.0.docx。 Java高级工程师面试宝典 该面试宝典由蚂蚁课堂创始人-余胜军原创整理 内容含括了:JavaSE、JavaEE、微服务、分布式、项目等。 java
2019年蚂蚁课堂-余胜军主编Java工程师面试宝典-V1.0
2019年蚂蚁课堂-余胜军主编Java工程师面试宝典,每特教育培训总结面试,高薪宝典
一根长度为L厘米的木棍上有n只蚂蚁,每只蚂蚁要么朝左爬,要么朝右爬,速度为1厘米/秒。当两只蚂蚁相撞时,二者同时掉头(掉头时间忽略不计)。给出每只蚂蚁的初始位置和朝向,计算T秒之后每只蚂蚁的位置。 程序给出...
前端大厂最新面试题-2019蚂蚁金服前端社招面经.docx
2019蚂蚁金服Java必问面试题及答案2019蚂蚁金服Java必问面试题及答案 2019蚂蚁金服Java必问面试题及答案2019蚂蚁金服Java必问面试题及答案
上海-拼多多-Java高级,杭州-阿里云-Java实习生,北京-京东-Java实习生,深圳-腾讯-Java高级,杭州-蚂蚁金服-Java高级,深圳-丰巢科技,北京-百度-Java中级,04_并发编程_面试专题及答案
关于java的面试宝典问题,java工程师的福音来啦,里面有很多企业在招收java工程师的面试的时候问到的,去面试的java工程师可要好好的看看咯~
Java高级工程师面试宝典 该面试宝典由蚂蚁课堂创始人-余胜军原创整理 内容含括了:JavaSE、JavaEE、微服务、分布式、项目等。
基于java的开发源码-网络蚂蚁Java版.zip 基于java的开发源码-网络蚂蚁Java版.zip 基于java的开发源码-网络蚂蚁Java版.zip 基于java的开发源码-网络蚂蚁Java版.zip 基于java的开发源码-网络蚂蚁Java版.zip 基于java的...
java面试——深圳-蚂蚁金服-Java高级.zip
java面试——杭州-蚂蚁金服-Java高级.zip
Java面试题,超全的互联网大厂Java面试题和学习资料大合集,共211份。 文件太多、资料很大,解压有1个多G。内容就不一一列举了,主要内容包含: 2021 Java面试学习资料(14份) 2021最新Java面试题资料(33份) 史...