从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) 回帖