首页 > 华为机试9.1(通信/射频算法岗)
头像
贝贝贝啊
发布于 2021-09-02 10:33
+ 关注

华为机试9.1(通信/射频算法岗) 内部员工回复

从7月份开始围观牛客大佬们的面经,收获很大。昨天考完机试,记录一下题目。

第一题:模糊搜索【不会&没时间做】
输入描述:
第一行是搜索词,第二行是目标文本,包含了多个目标词的一行文本。
输入的约束:1.搜索词和目标词是一个单词 2.单词定义:长度为[0,100]之间的字符串,仅有大写字母,小写字母,数字和中横线-组成。

第一题把样例中的答案输出一个能过5%

第2题:BFS求最短路径问题
题目描述:
小明从矩阵的左上角开始走到矩阵右下角所需要的最小的次数。
矩阵:有0和1组成,1是陆地(可以走路的)0是水面(不能走路的)
其他条件:(1)每次可以从上下左右四个方向走(2)小明每次走路喜欢1 2 1 2 1 2...交替走:即第一次走1步,第2次走2步,第3次走1步,第4次走2步...

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * @Description
 * 思路:从起点到终点
 * 1.BFS
 * 2.加一个判断当前层数的变量count:
 *      若count为奇数:走一步
 *      若count为偶数,走两步
 */
public class Main {
    //走一步
    private static int[][] Direction1 = new int[][]{{-1,0},{0,1},{1,0},{0,-1}};
    //走两步
    private static int[][] Direction2 = new int[][]{{-2,0},{0,2},{2,0},{0,-2}};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int M = sc.nextInt();//写入矩阵的行
        int N = sc.nextInt();//写入矩阵的列
        int[][] nums = new int[M][N];
        for(int i=0;i<M;i++){
            for(int j=0;j<N;j++){
                nums[i][j] = sc.nextInt();//输入矩阵
            }
        }

        int res = solution(nums);
        System.out.println(res);


    }

    public static int solution(int[][] nums){
        int row = nums.length;
        int col = nums[0].length;

        boolean[][] visited = new boolean[row][col];
        Queue<int[]> queue = new LinkedList<>();//队列来记录矩阵的索引,有数组表示[i,j]
        queue.offer(new int[]{0,0});//队列的初始化,将起点(0,0)放进去
        int count=0;//记录层数

        while(!queue.isEmpty()){
            int size = queue.size();
            count ++;

            for(int i=0;i<size;i++){
                int[] tmp = queue.poll();

                //count为奇数时,走一步
                if(count % 2 != 0){
                    for(int[] edge : Direction1){
                        int newx = edge[0] + tmp[0];
                        int newy = edge[1] + tmp[1];

                        if(isValid(newx,newy,nums) && !visited[newx][newy] && nums[newx][newy] == 1){
                            if(newx == row-1 && newy == col-1){
                                return count;
                            }
                            visited[newx][newy] = true;
                            queue.offer(new int[]{newx,newy});
                        }
                    }
                }
                
                //count为奇数时,走一步
                if(count % 2 == 0){
                    for(int[] edge : Direction2){
                        int newx = edge[0] + tmp[0];
                        int newy = edge[1] + tmp[1];

                        if(isValid(newx,newy,nums) && !visited[newx][newy] && nums[newx][newy] == 1){
                            if(newx == row-1 && newy == col-1){
                                return count;
                            }
                            visited[newx][newy] = true;
                            queue.offer(new int[]{newx,newy});
                        }
                    }
                }
            }


        }

        return 0;


    }

    static boolean isValid(int i,int j,int[][] nums){
        int row = nums.length;
        int col = nums[0].length;

        if(i<0 || i>=row || j<0 || j>=col) return false;
        else return true;

    }
}
//这种写法过了75%,不知道哪里出了问题🤤
第三题:给了一大堆文字描述,提炼出来,就是求一个无向图有几个连通分量的问题,力扣上这种题很多。DFS就能100%
import java.util.*;

/**
 * @Description 求连通的个数
 * 输入描述:
 * 第一个数为顶点与顶点之间的连接关系数N
 * 接下来输入N行,表示两顶点之间相连
 *
 * 输出:有几个连通图
 *
 * 输入:
 * 6
 * [0 1]
 * [0 2]
 * [0 3]
 * [0 4]
 * [4 5]
 * [6 7]
 *
 * 输出:
 * 2
 * //不知道顶点个数,而且顶点是无序的,并非为0~n-1这样的,
 * 所以构造图时采用HashMap,同时记录顶点和对应的邻接表
 * @creat 2021-09-01
 */
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        HashMap<Integer, Set<Integer>> adj = new HashMap<>();
        HashMap<Integer, Boolean> visited = new HashMap<>();//标记顶点是否被访问
        //构建无向图
        //1.构建顶点:
        Set<Integer> set = new HashSet<>();//去重操作
        List<Integer> list = new LinkedList<>();//存放顶点的list
        int[][] edges = new int[N][2];//获取输入数据
        
        for(int i=0;i<N;i++){
            edges[i][0] = sc.nextInt();
            edges[i][1] = sc.nextInt();

            if(!set.contains(edges[i][0])){
                list.add(edges[i][0]);
                set.add(edges[i][0]);
            }
            if(!set.contains(edges[i][1])){
                list.add(edges[i][1]);
                set.add(edges[i][1]);
            }

        }

        //对每个顶点构建邻接表(初始化):
        for(Integer g : list){
            adj.put(g,new HashSet<>());
            visited.put(g,false);
        }

        //添加顶点间的指向
        for(int[] edge : edges){
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }


        //对每个顶点进行DFS遍历
        //访问当前节点标记为true

        int count=0;//记录连通图数量
        for(Integer i : list){
            if(!visited.get(i)){
                dfs(i,adj,visited);
                count++;
            }
        }

        System.out.println(count);
    }

    static void dfs(int i, HashMap<Integer, Set<Integer>> adj ,HashMap<Integer, Boolean> visited){
        visited.put(i,true);
        Set<Integer> temp = adj.get(i);//当前顶点的邻接表

        for(Integer g : temp){
            if(!visited.get(g)){
                dfs(g,adj,visited);
            }
        }

    }
}


PS:通信/射频算法机试题确实比软开的简单😅

全部评论

(8) 回帖
加载中...
话题 回帖

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐