- 1linux驱动入门须知_linux驱动工程师要把linux全了解一遍嘛
- 22、python编译器安装，安装pycharm、spyder并使用arcgis pro自带python.exe_arcgispro spyder
- 3facebook faiss的安装测试_faiss 验证安装成功
- 4centos7 安装RabbitMQ，webui管理_socat webui
- 5目标检测标注文件yolo v5格式转coco格式详解及代码实现_yolo转coco
- 6全志H616香橙派简介及登录_香橙派怎么更改日志级别
- 7Docker可视化容器管理工具（Portainer）_docker容器管理平台—portainer
- 8判断文件重复上传_判断文件是否重复上传
- 9Air780E模块休眠控制应用指南
- 10【人工智能】Transformers之Pipeline（五）：深度估计（depth-estimation）
华为OD算法题汇总_华为od 算法题库
赞
踩
3、篮球争霸-最多MVP
60、计算网络信号
题目
网络信号经过传递会逐层衰减，且遇到阻隔物无法直接穿透，在此情况下需要计算某个位置的网络信号值。注意:网络信号可以绕过阻隔物
array[m][n]，二维数组代表网格地图
array[i][j]=0，代表i行j列是空旷位置
array[i][j]= x，(x为正整数)代表i行j列是信号源，信号强度是x,
array[i][j]=-1， 代表i行j列是阻隔物
信号源只有1个，阻隔物可能有0个或多个；
网络信号袁减是上下左右相邻的网格衰减1现要求输出对应位置的网络信号值。
输入
输入为三行，
第一行为 m、n，代表输入是一个mxn 的数组,
第二行是一串 mxn 如个用空格分隔的整数每连续n个数代表一行，再往后n个代表下一行，以此类推。对应的值代表对应的网格是空矿位置，还是信号源，还是阻隔物，
第三行是ì、j，代表需要计算 array[i][j] 的网络信号值。注意:此处i和j均从 0开始，即第一行i为0；
例如：
6 5
0 0 0 -1 0 0 0 0 0 0 0 0 -1 4 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0
1 4
- 1
- 2
- 3
输出
输出对应位置的网络信号值，如果网络信号未覆盖到，也输出0。
一个网格如果可以途径不同的传播衰减路径传达，取较大的值作为其信号值。
解题思路
把信号源向上下左右四个方向扩散，并把满足条件的扩散点作为新的信号源继续扩散，直到信号值为0、或者扩散到“坐标系”边缘
6 5
0 0 0 -1 0 0 0 0 0 0 0 0 -1 4 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0
- 1
- 2
对于以上输入，得到的二维数组(可视为坐标系)为
0 0 0 -1 0
0 0 0 0 0
0 0 -1 4 0
0 0 0 0 0
0 0 0 0 -1
0 0 0 0 0
- 1
- 2
- 3
- 4
- 5
- 6
扩散后，最终为
0 0 1 -1 1
0 1 2 3 2
0 0 -1 4 3
0 1 2 3 2
0 0 1 2 -1
0 0 0 1 0
- 1
- 2
- 3
- 4
- 5
- 6
这里一定要注意，二维数组和我们上学时常用的xy轴坐标系还是有区别的，它们的原点不同，下面简化一下以上二维数组坐标系示意图
6 5
0 0 0 -1 0 0 0 0 0 0 0 0 -1 4 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0
1 4
- 1
- 2
- 3
这个输入，要求的输出array[1][4]，它的结果是2；
我一开始把二维数组和上学时的xy轴坐标系给搞混了，死活想不明白(1，4)为啥是2，而不是1？
java代码
没有作输入的合法性校验，有兴趣的可以自己补充一下；
变量名起的也比较随意，大家不要学我
import java.util.LinkedList; import java.util.Scanner; public class A60计算网络信号 { private static LinkedList<Danyuange> list = new LinkedList<>(); private static int[][] zhouweiArr = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int m = sc.nextInt(); int n = sc.nextInt(); int[][] inputArr = new int[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { int d = sc.nextInt(); inputArr[i][j] = d; if(d > 0) { Danyuange yuan = new Danyuange(); yuan.setX(i); yuan.setY(j); yuan.setD(d); list.add(yuan); } } } int queryX = sc.nextInt(); int queryY = sc.nextInt(); while (list.size() > 0) { Danyuange danyuange = list.removeFirst(); kuosanMethod(inputArr, danyuange); } System.out.println(inputArr[queryX][queryY]); } private static void kuosanMethod(int[][] inputArr, Danyuange danyuange) { int x = danyuange.getX(); int y = danyuange.getY(); int d = danyuange.getD(); for (int i = 0; i < 4; i++) { int newX = x + zhouweiArr[i][0]; int newY = y + zhouweiArr[i][1]; if(newX >= 0 && newX < inputArr.length && newY >= 0 && newY < inputArr[0].length) { if(inputArr[newX][newY] == 0) { inputArr[newX][newY] = d - 1; } if(inputArr[newX][newY] < d && inputArr[newX][newY] >= 2 && inputArr[newX][newY] != -1) { Danyuange newDanyuange = new Danyuange(); newDanyuange.setX(newX); newDanyuange.setY(newY); newDanyuange.setD(d-1); list.add(newDanyuange); } } } } private static class Danyuange { int x; int y; int d; public int getX() { return x; } public void setX(int x) { this.x = x; } public int getY() { return y; } public void setY(int y) { this.y = y; } public int getD() { return d; } public void setD(int d) { this.d = d; } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
61、简易内存池
题目
请实现一个简易内存池根据请求命令完成内存分配和释放内存池支持两种操作命令REQUEST和 RELEASE ；
其格式为：
REQUEST=请求的内存大小
表示请求分配指定大小内存
如果分配成功，返回分配到的内存首地址；
如果内存不足，或指定的大小为零则输出 error；
RELEASE=释放的内存首地址
表示释放掉之前分配的内存，释放成功无需输出如果，
释放不存在的首地址则输出 error
注意:
1.内存池总大小为 100 字节
2.内存池地址分配必须是连续内存，并优先从低地址分配
3.内存释放后可被再次分配，已释放的内存在空闲时不能被二次释放4.不会释放已申请的内存块的中间地址
5.释放操作只是针对首地址所对应的单个内存块进行操作，不会影响其他内存块
输入：
首行为整数 N，表示操作命令的个数取值范围 8<N<=100
接下来的N行，每行将给出一个操作命令；
操作命令和参数之间用“=”分割
输出：
见题目输出要求
示例1：
输入：
2
REQUEST=10
REQUEST=20
- 1
- 2
- 3
- 4
输出：
0
10
- 1
- 2
- 3
示例2：
输入：
6
REQUEST=10
REQUEST=20
RELEASE=0
RELEASE=20
REQUEST=20
REQUEST=10
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
输出：
0
10
error
30
0
- 1
- 2
- 3
- 4
- 5
- 6
解题思路
1）用二维数组收录输入，会非常便于后续操作；当然也可以用单独的数组；
2）用treemap模拟内存(必须用treemap，需要key有序)；
- RELEASE释放比较简单，包含key就remove，不包含就输出error；
- REQUEST单独一个方法处理，会使代码逻辑很清晰；自定义变量left初始值为0，表示与下一个已用内存首地址之间、未使用内存的首地址；
0————k1-v1————k2-v2————...————kn-vn————max
- 1
- 如上图示意，k-left就代表空闲内存的长度，k1-0就是最前边的空闲内存，从前往后、循环测试map的所有空闲内存key-left是否大于等于新内存l；
- ps：学会取map的key放入list的方法 List keyList = new ArrayList<>(map.keySet())
- 如果这个长度大于等于要存入的长度l，map直接put(left, left + l)，并结束方法return；
- ps：还是为了方便，v不存真实的尾地址索引，而是直接存(索引+1)，即占用内存长度是 [k, v)
- 如果这个长度小于要存入的长度l，则left = v，继续下一个循环；
- 当map的所有key都测试过，仍未找到可以放新内存l的地方，测试 max-left（此时left等于vn）是否大于等于l，
- 如果大于等于，put(left, left + l)
- 如果小于，输出error；
java代码
public class A61简易内存池 { private static Map<Integer, Integer> map = new TreeMap<>(); public static void main(String[] args) { Scanner sc = new Scanner(System.in); int orderNum = Integer.parseInt(sc.nextLine()); String[][] orders = new String[orderNum][]; for (int i = 0; i < orderNum; i++) { orders[i] = sc.nextLine().split("="); } for (int j = 0; j < orderNum; j++) { String order = orders[j][0]; int length = Integer.parseInt(orders[j][1]); if("REQUEST".equals(order)) { requestMethod(length); } else { if(map.containsKey(length)) { map.remove(length); } else { System.out.println("error"); } } } } private static void requestMethod(int length) { int left = 0; if(map.size() == 0){ map.put(length, left + length);//包含左、不包含右 } List<Integer> keyList = new ArrayList<>(map.keySet()); for (Integer key : keyList) { if(key - left >= length) { map.put(left, left + length);//包含左、不包含右 System.out.println(left); return; } else { left = map.get(key); } } //循环结束，表示所有kv之间，都没有找到能放length的地方；检查剩余字节 if(100 - left >= length) { map.put(left, left + length);//包含左、不包含右 System.out.println(left); } else { System.out.println("error"); } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
80、机器人走迷宫
题目
1.房间由 xγ 的方格组成，例如下图为 64 的大小。每一个方格以坐标(x,y)描述。
2.机器人固定从方格(0,0)出发，只能向东或者向北前进，出口固定为房间的最东北角，如下图的方格(5,3)。用例保证机器人可以从入口走到出口。
3.房间有些方格是墙壁，如(4,1),机器人不能经过那儿。
4.有些地方是一旦到达就无法走到出口的，如标记为B的方格，称之为陷阱方格。
5.有些地方是机器人无法达到的，如标记为A的方格，称之为不可达方格，不可达方格不包括墙壁所在的位置。
6.如下实例图中，陷阱方格有2个，不可达方格有3个。
7.请为该机器人实现路径规划功能：给定房间大小，墙壁位置，请计算出陷阱方格与不可达方格分别有多少个
输入
1.第一行为房间的x和y(0<x,y<= 1000)
2.第二行为房间中墙壁的个数 N(0<= N<x*γ)
3. 接着下面会有 N行墙壁的坐标
同一行中如果有多个数据以一个空格隔开，用例保证所有的输入数据均合法(结尾不带回车换行)
6 4
5
0 2
1 2
2 2
4 1
5 1
- 1
- 2
- 3
- 4
- 5
- 6
- 7
输出
陷阱方格与不可达方格数量，两个信息在一行中输出，以一个空格隔开。(结尾不带回车换行)
2 3
- 1
示例二
#输入
6 4
4
2 0
2 1
3 0
3 1
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
#输出
0 4
- 1
- 2
解题思路
写一个方法solve()，功能为从给定起点开始，向北、向东扫描整个棋盘；
假设以(0, 0)为起点扫描，其扫描效果如下：
上图中标记的点位，即为可以扫到的地方，存入checkedSet中；
并且由图可知：
要求的“不可到达点” = 6 * 4 - checkedSet.size() - wallSet.size()
另外，在这个solve()方法中，还可以顺带得到一个集合stopedSet，用来存放往上/往东一步就撞墙的所有点位，如下图
从图中可以看出，如果我们再以stopedSet中的点位为起点，再次调用solve方法，即以起点向北、向东扫描；只有t1、t2两点，运行后得到的checked不包含终点。
注意：为了方便操作，我写了自定义类存放每个点对象；并且solve方法，用了递归调用，可能会有很多重复的点放入同一集合中，所以各个集合都用set存(可以自动去重)；也正因如此，自定义点类，必须重写equals方法，以便set底层确认两个点对象是否相等。
java代码
import java.util.HashSet; import java.util.Objects; import java.util.Scanner; import java.util.Set; public class A80机器人走迷宫 { private static int xLength = 0; private static int yLength = 0; public static void main(String[] args) { Scanner sc = new Scanner(System.in); xLength = sc.nextInt(); yLength = sc.nextInt(); int wallNum = sc.nextInt(); Set<DianModel> wallSet = new HashSet<>(); for (int i = 0; i < wallNum; i++) { int a = sc.nextInt(); int b = sc.nextInt(); wallSet.add(new DianModel(a, b)); } Set<DianModel> checkedSet = new HashSet<>(); Set<DianModel> stopedSet = new HashSet<>(); solve(0, 0, wallSet, checkedSet, stopedSet); int cantGo = xLength * yLength - wallSet.size() - checkedSet.size(); int xianjin = 0; for (DianModel model : stopedSet) { Set<DianModel> newCheckedSet = new HashSet<>(); Set<DianModel> newStopedSet = new HashSet<>(); solve(model.x, model.y, wallSet, newCheckedSet, newStopedSet); if(!newCheckedSet.contains(new DianModel(xLength-1, yLength-1))){ xianjin++; } } System.out.println(xianjin + " " + cantGo); } private static class DianModel { int x; int y; public DianModel(int x, int y) { this.x = x; this.y = y; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; DianModel dianModel = (DianModel) o; return x == dianModel.x && y == dianModel.y; } @Override public int hashCode() { return Objects.hash(x, y); } } private static void solve(int x, int y, Set<DianModel> wallSet, Set<DianModel> checkedSet, Set<DianModel> stopedSet) { if(x >= xLength || y >= yLength) { return; } checkedSet.add(new DianModel(x, y)); //向北 if(wallSet.contains(new DianModel(x, y+1))) { stopedSet.add(new DianModel(x, y)); } else { solve(x, y+1, wallSet, checkedSet, stopedSet); } //向东 if(wallSet.contains(new DianModel(x+1, y))) { stopedSet.add(new DianModel(x, y)); } else { solve(x+1, y, wallSet, checkedSet, stopedSet); } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
