面试题——过桥

太过爱你忘了你带给我的痛 2022-05-20 02:16 148阅读 0赞

# 面试题——过桥 #

## 题目 ##

有4个人过桥。一个要1分钟，一个要2分钟，一个要5分钟，最后一个要10分钟。桥一次只能过两个人，因为天黑了，过桥必须使用手电筒，但是只有一个手电筒。问题：如何用最少的时间让4个人过桥？

## 分析 ##

1.  采用优先级队列存储每个人过桥的时间，由于优先级队列每次取出的元素都是优先级最高的，所以可以无序存储。
2.  编写过桥和计时两个方法来完成整个过程。由于桥每次只能过两个人，所以需要取出两个元素，其次，要计算最短时间，所以需要获取过桥时间最快的人的用时。所以需要优先获取第一次元素（即过桥用时最短的），且需要记录过桥的次数，在最后一次过桥后，用时最短的人不需要再返回桥头。

## 编程实现 ##

import java.util.Arrays;
    import java.util.List;
    import java.util.PriorityQueue;
    
    public class CrossBrigeDemo { 
    
        // 计时器，表示过桥的用时
        private int totalTime = 0;
    
        /** * 过桥 * * @param priorityQueue */
        public void crossBrige(PriorityQueue<Integer> priorityQueue) {
    
            int index = 0; // 表示第几次过桥
            int lastIndex = priorityQueue.size() - 1; // 表示最后一次过桥
            int first = priorityQueue.peek(); // 获取队列中第一个元素
            while (priorityQueue.peek() != null) {
    
                if (index == 0) {
                    priorityQueue.remove();
                    index++;
                    continue;
                }
                index++;
                // 移除并获取队列中头元素
                int node = priorityQueue.remove();
    
                count(first, node, index, lastIndex);
    
            }
    
        }
    
        /** * 计时 * * @param first * @param node * @param index * @param lastIndex */
        public void count(int first, int node, int index, int lastIndex) {
    
            // 如果最后一次过桥，不需要再记录返回的时间
            int crossBrigeTime = index == lastIndex ? node : first + node;
            totalTime += crossBrigeTime;
    
        }
    
        public static void main(String[] args) {
    
            // 用于存储每个人过桥的用时，可以是无序的
            List<Integer> mins = Arrays.asList(2, 5, 10, 1);
            // 用优先级队列来存储每个人的过桥用时，并按优先级排序
            PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>();
            priorityQueue.addAll(mins);
    
            CrossBrigeDemo t = new CrossBrigeDemo();
    
            t.crossBrige(priorityQueue);
    
            System.out.println(t.totalTime);
    
        }
    
    }

源代码链接：[https://github.com/myNameIssls/javase-study/blob/master/javase-interviewcase/src/main/java/cn/tyrone/javase/interviewcase/CrossBrigeDemo.java][https_github.com_myNameIssls_javase-study_blob_master_javase-interviewcase_src_main_java_cn_tyrone_javase_interviewcase_CrossBrigeDemo.java]

[https_github.com_myNameIssls_javase-study_blob_master_javase-interviewcase_src_main_java_cn_tyrone_javase_interviewcase_CrossBrigeDemo.java]: https://github.com/myNameIssls/javase-study/blob/master/javase-interviewcase/src/main/java/cn/tyrone/javase/interviewcase/CrossBrigeDemo.java