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

前言

广度优先遍历(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 ,此时的层数即为最后的结果。

动画演示

代码实现

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 号问题--有效的括号很类似,这里就拿出来进行参考理解一下,区别点就在于多了遍历和哈希存储。

动画演示

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

代码实现

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;
    }
}

本文分享自微信公众号 - 五分钟学算法(CXYxiaowu)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-03-28

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏苦逼的码农

刷题打卡:在两个长度相等的排序数组中找到上中位数

给定两个有序数组arr1和arr2,已知两个数组的长度都为N,求两个数组中所有数的上中位数。要求时间复杂度O(logN),空间复杂度O(1)

8920
来自专栏未闻Code

【一日一技】揭秘字符串的两副“面孔”

现在,当你在命令行交互环境直接输入变量名再回车的时候,你看到的是'test',当你输入print(a)的时候,你看到的却是test。

8930
来自专栏lhyt前端之路

少年,你渴望元编程的力量吗?——symbol

一些时候,写各种下划线、前后缀,为了实现一个唯一值或者秘密的特殊辅助值,用来辅助业务逻辑或者说作为一个私有的东西:

12330
来自专栏吴伟祥

shell中$(( ))、$( )与${ }的区别

在bash中,$( )与` `(反引号)都是用来作命令替换的。 命令替换与变量替换差不多,都是用来重组命令行的,先完成引号里的命令行,然后将其结果替换出来,再...

11730
来自专栏华章科技

入门中文NLP必备干货:5分钟看懂“结巴”分词(Jieba)

导读:近年来,随着NLP技术的日益成熟,开源实现的分词工具越来越多,如Ansj、盘古分词等。在本文中,我们选取了Jieba进行介绍和案例展示,主要基于以下考虑:

24520
来自专栏林德熙的博客

win10 uwp 修改图片质量压缩图片

本文告诉大家如何在 UWP 通过修改图片的质量减少图片大小,这个方法只支持输出 jpg 文件

18520
来自专栏张泽旭的专栏

Spring Cloud Ribbon负载均衡策略自定义配置

实现这个类,可以改变Consts.ruleType中的值,来每次动态选择负载均衡策略,其中倍权和tag轮询策略是我更具上述的随机轮询策略编写的,Consts类中...

28930
来自专栏解Bug之路

用C语言撸了个DBProxy 顶

笔者在阅读了一大堆源码后,就会情不自禁产生造轮子的想法。于是花了数个周末的时间用C语言撸了一个DBProxy(MySQL协议)。在笔者的github中给这个DB...

28630
来自专栏未闻Code

【一日一技】破译反斜杠数量问题的密码

“大家在开发Python的过程中,一定会遇到很多反斜杠的问题,很多人被反斜杠的数量搞得头大。这期我们就来介绍一下如何处理这些让人头疼的反斜杠。”

15140
来自专栏林德熙的博客

dotnet 手动解决 json 解析中不合法字符串

如果使用 Newtonsoft Json 解析字符串,字符串里面有不清真的格式,那么默认的解析将会炸掉。如果想要自己解决字符串中的不清真格式,可以使用传入 Js...

11510

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励