几道和「广度优先搜索」有关的算法面试题

雨点打透心脏的1/2处 2022-02-25 15:38 218阅读 0赞

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

前言

广度优先遍历（BFS）是搜索图的算法，它的基本思想和操作方法就是：

1、从图中某个顶点 V0 出发，并访问此顶点；

2、从 V0 出发，访问 V0 的各个 **未被访问** 的邻接点 W1， W2，…， Wk ；然后依次从 W1， W2，…， Wk 出发访问各自未被访问的邻接点；

3、重复步骤 2 ，直到全部顶点都被访问为止。

## 1 二叉树的层次遍历 ##

二叉树的层次遍历是最直接了当的使用广度优先遍历就能解决的一题。

### 动画演示 ###

### 代码实现 ###

public List<List<Integer>> levelOrder(TreeNode root) {
        
        if(root == null)
            return new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while(!queue.isEmpty()){
        
            int count = queue.size();
            List<Integer> list = new ArrayList<Integer>();
            while(count > 0){
        
                TreeNode node = queue.poll();
                list.add(node.val);
                if(node.left != null)
                    queue.add(node.left);
                if(node.right != null)
                    queue.add(node.right);
                count--;
            }
            res.add(list);
        }
        return res;
    }

## 2 完全平方数 ##

题目来源于 LeetCode 第 279 号问题：完全平方数。

### 题目描述 ###

给定正整数 **n**，找到若干个完全平方数（比如 `1, 4, 9, 16, ...`）使得它们的和等于 **n**。你需要让组成和的完全平方数的个数最少。

### 题目解析 ###

这道题目很有意思。

大部分文章给出的答案都是依托于一个定理：**四平方定理**。

四平方定理讲的就是任何一个正整数都可以表示成不超过四个整数的平方之和。也就是说，这道题的答案只有 1，2 ，3，4 这四种可能。

同时，还有一个非常重要的推论满足四数平方和定理的数n（这里要满足由四个数构成，小于四个不行），必定满足 n = 4a \* (8b + 7)。

根据这个重要的推论来解决此题，首先将输入的`n`迅速缩小。然后再判断，这个缩小后的数是否可以通过`两个平方数的和或一个平方数`组成，不能的话我们返回`3`，能的话我们返回`平方数的个数`。

所以代码很简洁，如下：

public int numSquares(int n) {
        
            while (n % 4 == 0){
        
                n /= 4;
            }
            if ( n % 8 == 7){
        
                return 4;
            }
            int a = 0;
            while ( (a * a) <= n){
        
                int b = (int)Math.pow((n - a * a),0.5);
                 if(a * a + b * b == n) {
        
                //如果可以 在这里返回
                if(a != 0 && b != 0) {
        
                    return 2;
                } else{
        
                    return 1;
                }
            }
            a++;
         }
            return 3;
    }

但因为本章是「广度优先遍历」的专栏，因此再补充一个图的广度优先遍历的答案：

使用广度优先搜索方法，将 n 依次减去比 n 小的所有平方数，直至 n = 0 ，此时的层数即为最后的结果。

### 动画演示 ###

![640?wx\_fmt=gif][640_wx_fmt_gif]

### 代码实现 ###

import java.util.LinkedList;
    import javafx.util.Pair;
    class Solution {
        
        public int numSquares(int n) {
        
             if(n == 0)
                return 0;
    
            LinkedList<Pair<Integer, Integer>> queue = new LinkedList<Pair<Integer, Integer>>();
            queue.addLast(new Pair<Integer, Integer>(n, 0));
    
            boolean[] visited = new boolean[n+1];
            visited[n] = true;
    
            while(!queue.isEmpty()){
        
                Pair<Integer, Integer> front = queue.removeFirst();
                int num = front.getKey();
                int step = front.getValue();
    
                if(num == 0)
                    return step;
    
                for(int i = 1 ; num - i*i >= 0 ; i ++){
        
                    int a = num - i*i;
                    if(!visited[a]){
        
                        if(a == 0) return step + 1;
                        queue.addLast(new Pair(num - i * i, step + 1));
                        visited[num - i * i] = true;
                    }
                }
            }
            return 0;
        }
    }

## 3 员工的重要性 ##

题目来源于 LeetCode 第 690 号问题：员工的重要性。

### 题目描述 ###

给定一个保存员工信息的数据结构，它包含了员工**唯一的id**，**重要度** 和 **直系下属的id**。

比如，员工 1 是员工 2 的领导，员工 2 是员工 3 的领导。他们相应的重要度为 15, 10, 5 。那么员工 1 的数据结构是\[1, 15, \[2\]\]，员工 2 的数据结构是\[2, 10, \[3\]\]，员工3的数据结构是\[3, 5, \[\]\]。注意虽然员工 3 也是员工 1 的一个下属，但是由于**并不是直系**下属，因此没有体现在员工1的数据结构中。

现在输入一个公司的所有员工信息，以及单个员工 id，返回这个员工和他所有下属的重要度之和。

**示例 1:**

*  
 *  
 *  
 *

输入: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1输出: 11解释:员工 1 自身的重要度是 5，他有两个直系下属 2 和 3 ，而且 2 和 3 的重要度均为 3 。因此员工 1 的总重要度是 5 + 3 + 3 = 11。

**注意:**

•一个员工最多有一个**直系**领导，但是可以有多个**直系**下属•员工数量不超过 2000。

### 题目解析 ###

利用哈希表来存储员工的信息，找到指定 id 的员工后，采用广度优先遍历算法来遍历编号为 id 的员工及其下属员工

### 代码实现 ###

public int getImportance(List<Employee> employees, int id) {
        
            Employee emp = null;
            //重要度
            int sum = 0;   
            //存储员工信息
            HashMap<Integer,Employee> map=new HashMap<Integer,Employee>();  /
            for(Employee e:employees) {
        
                map.put(e.id, e);
            }
            //使用广度优先遍历员工
            ArrayDeque<Employee> queue=new ArrayDeque<Employee>();
            queue.addLast(map.get(id));
            while(!queue.isEmpty()) {
        
                emp=queue.removeFirst();
                sum+=emp.importance;
                for(int i:emp.subordinates) {
        
                    queue.addLast(map.get(i));
                }
            }
            return sum;
    
        }

## 4 删除无效的括号 ##

题目来源于 LeetCode 第 301 号问题：删除无效的括号。有小伙伴后台留言说这题是中山大学计算机考研机试题。

### 题目描述 ###

删除最小数量的无效括号，使得输入的字符串有效，返回所有可能的结果。

**说明:** 输入可能包含了除 `(` 和 `)` 以外的字符。

**示例 1:**

*  
 *

输入: "()())()"输出: ["()()()", "(())()"]

**示例 2:**

*  
 *

输入: "(a)())()"输出: ["(a)()()", "(a())()"]

**示例 3:**

*  
 *

输入: ")("输出: [""]

### 题目解析 ###

所谓有效的括号，那么字符串中的左右括号数应该相同，而且每个右括号左边一定有其对应的左括号。这里很容易想到使用一个栈来模拟匹配过程，'(' 入栈，')' 出栈，若栈为空说明该串是符合题意的。

首先对括号进行删除，遍历从前往后遍历可以删除不符合的 ')' 括号，从后往前遍历可以删除不符合的'('括号，通过 BFS，不断的对队列的字符串进行 checkLeft 和 checkRight 操作，若遇到 ture，则说明当前的字符串已经是删除最少无效的括号的最优解了，接着就对队列中的其他字符串进行 check 即可。

这道题目的动画与 LeetCode 第 20 号问题--有效的括号很类似，这里就拿出来进行参考理解一下，区别点就在于多了遍历和哈希存储。

### 动画演示 ###

注：下面动画只是该题的参考动画演示，并非是完全演示。

![640?wx\_fmt=gif][640_wx_fmt_gif 1]

**代码实现**

public class Solution {
        
        public List<String> removeInvalidParentheses(String s) {
        
            queue.offer(s);
            vis.add(s);
            boolean flag=false;
            List<String> ans=new ArrayList<String>();
            while (!queue.isEmpty()){
        
                String cur=queue.poll();
                if(flag){
        
                    check(cur,ans);
                }else{
        
                    flag=checkLeft(cur,ans)||checkRight(cur,ans);
                }
            }
            if(ans.size()==0){
        
                ans.add("");
            }
            return new ArrayList<String>(ans);
        }
    
        Set<String> vis=new HashSet<String>();
        Queue<String> queue=new LinkedList<String>();
    
        public void check(String s,List<String> ans){  //查看是否正确
            Stack<Character> st=new Stack<Character>();
            for(char c:s.toCharArray()){
        
                if(c=='('){
        
                    st.push(c);
                }
                if(c==')'){
        
                    if(st.isEmpty()){
        
                        return;
                    }
                    st.pop();
                }
            }
            if(st.isEmpty()){
        
                ans.add(s);
            }
        }
    
        public boolean checkLeft(String s,List<String> ans){ //检查左边
            //delete right
            Stack<Character> st=new Stack<Character>();
            for(int i=0;i<s.length();++i){
        
                if(s.charAt(i)=='('){
        
                    st.push(s.charAt(i));
                }else if(s.charAt(i)==')'){
        
                    if(st.isEmpty()){
        
                        for(int j=i;j>=0;--j){ //删除不符合的')'  多种情况
                            if(s.charAt(j)==')'){
        
                                String s1=s.substring(0,j)+s.substring(j+1);
                                if(!vis.contains(s1)){
        
                                    vis.add(s1);
                                    queue.offer(s1);
                                }
                            }
                        }
                        return false;
                    }else{
        
                        st.pop();
                    }
                }
            }
            if(st.isEmpty()){
        
                ans.add(s);
                return true;
            }
            return false;
        }
    
        public boolean checkRight(String s,List<String> ans){ //检查右边
            //delete right
            Stack<Character> st=new Stack<Character>();
            st.clear();
            for(int i=s.length()-1;i>=0;--i){
        
                if(s.charAt(i)==')'){
        
                    st.push(s.charAt(i));
                }else if(s.charAt(i)=='('){
        
                    if(st.isEmpty()){
        
                        for(int j=i;j<s.length();++j){
        
                            if(s.charAt(j)=='('){  //删除不符合的'(' 多种情况
                                String s1=s.substring(0,j)+s.substring(j+1);
                                if(!vis.contains(s1)){
        
                                    vis.add(s1);
                                    queue.add(s1);
                                }
                            }
                        }
                        return false;
                    }else{
        
                        st.pop();
                    }
                }
            }
            if(st.isEmpty()){
        
                ans.add(s);
                return true;
            }
            return false;
        }
    }

**推荐阅读**

[拜托，面试官别问我「布隆」了][Link 1]

[昨天，终于拿到了腾讯 offer][offer]

[几道和「二叉树」有关的算法面试题][Link 2]

[几道和散列（哈希）表有关的面试题][Link 3]

[一道看完答案你会觉得很沙雕的「动态规划算法题」][Link 4]

[几道和「堆栈、队列」有关的面试算法题][Link 5]

[链表算法面试问题？看我就够了！][Link 6]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

欢迎关注![640?wx\_fmt=png][640_wx_fmt_png]

[640_wx_fmt_jpeg]: /images/20220225/5900986620144e2ea01699feffdd1df0.png
[640_wx_fmt_gif]: /images/20220225/d99c7c13e3184eb3b7cb33917ab0a1b2.png
[640_wx_fmt_gif 1]: /images/20220225/d390ee8af951465e9e17362c9bf51327.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485011&idx=1&sn=a3031a3d3ad033e44439d42d72753e16&chksm=fa0e69d2cd79e0c45b1eb017c65b60662890f67ec70ef44e92ef7f5cddfc313ea6ab353952f4&scene=21#wechat_redirect
[offer]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485001&idx=1&sn=cdcebef70aaabcafa3403c2dd51bdfb7&chksm=fa0e69c8cd79e0de12ece3a9e48430099c429aff816cc3a9e40035192dc07a864864888d1078&scene=21#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484985&idx=1&sn=93343d355abf36c77a361c9931cbe2d1&chksm=fa0e69b8cd79e0ae1e6b57665a456da5f421cc92fe6934337f1eb1e18c3fd6a3c1adc8ca88c2&scene=21#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484977&idx=1&sn=f4a6148480555e3cca83231ac1df8d02&chksm=fa0e69b0cd79e0a686e31c547fc783eb9663d9fe19cc95ecd524e9f8f7e0d4a168945f8755e5&scene=21#wechat_redirect
[Link 4]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484875&idx=1&sn=72cf66da1c970ba345e8b1ab3586c10d&chksm=fa0e6a4acd79e35c32c9201e99cc93a71d0f2a331319addf5303c76ac05738b312ab238a8304&scene=21#wechat_redirect
[Link 5]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484846&idx=2&sn=e508da06e9f7a0b3d00db5415d7ce622&chksm=fa0e6a2fcd79e3397fe8083f9493ae639f47c9448ac2a0026026494d098c47ecc6e08f1f8e28&scene=21#wechat_redirect
[Link 6]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484830&idx=1&sn=9d24fc787da4b49b82ac01c7f8de257b&chksm=fa0e6a1fcd79e309a2e7f3e09ec9913a55f1c077287c907f13528578b7785831a2effb3104e0&scene=21#wechat_redirect
[640_wx_fmt_jpeg 1]: /images/20220225/4f8d69af6df84764afd985b1247c56ee.png
[640_wx_fmt_png]: /images/20220225/cf13b1fec6c9465c875943d6d53b06a3.png