华为通软|暑期实习|笔试合集
得空，整理一下之前搞懂了的一些笔试内容
04-19笔试
第一题.服务器能耗统计
- 服务器有三种运行状态:空载、单任务、多任务，每个时间片的能耗的分别为1、3、4;
- 每个任务由起始时间片和结束时间片定义运行时间:
- 如果一个时间片只有一个任务需要执行，则服务器处于单任务状态；
- 如果一个时间片有多个任务需要执行，则服务器处于多任务状态；
- 给定一个任务列表，请计算出从第一个任务开始，到所有任务结束，服务器的总能耗。
- 输入：一个只包含整数的二维数组:
- 第一行的数字表示一共有多少个任务
- 后续每行包含由空格分割的两个整数，用于确定每一个任务的起始时间片和结束时间片;
- 任务执行时间包含起始和结束时间片，即任务执行时间是左闭右闭的;
- 结束时间片一定大于等于起始时间片;
- 时间片范围: [0，1000000]: 任务数范围: [1,10000];
- 输出：一个整数，代表服务器的总能耗。
样例1：
样例2：
- 思路：差分数组统计区间，然后遍历区间（因为区间只有100w，所以可以直接遍历），按规则叠加即可。
// 第一题
// 时间复杂度O(n),空间复杂度O(max)
let arr = [[2,5],[8,9]];
let task1 = arr => {
let max = 0;
// 首先找到传入的任务中，最长的结束时间
for(let i = 0; i < arr.length; i++){
if(arr[i][1] > max) max = arr[i][1];
}
// 用最长的结束时间新建一个标记数组
let visit = new Array(max + 1).fill(0);
// 如果检测到是传入数据的左边界，visit对应+1，是右边界则减一，差分的思想
for(let i = 0; i < arr.length; i++){
visit[arr[i][0]]++;
visit[arr[i][1]]--;
}
// 分别用以中途计数，返回答案和标记是否已经有任务运行过
let cnt = 0;
let ans = 0;
let flag = 0;
for(let i = 0; i <= max; i++){
// 注意这里是左闭右闭的区间，如果是右区间，应该先算值再进行加减
// 如果是左区间和常规值，就需要先加减再计算
if(visit[i] == - 1){
if(cnt == 1){
ans += 3;
flag = 1;
} else if(cnt >= 2){
ans += 4;
} else if(cnt == 0 && flag){
ans += 1;
}
cnt += visit[i];
} else {
cnt += visit[i];
if(cnt == 1){
ans += 3;
flag = 1;
} else if(cnt >= 2){
ans += 4;
} else if(cnt == 0 && flag){
ans += 1;
}
}
}
return ans;
}
// console.log(task1(arr))
第二题、 树上逃离
- 给定一棵树，这个树有n个节点，节点编号从0开始依次递增，0固定为根节点。在这棵树上有一个小猴子，初始时该猴子位于根节点(0号) 上，小猴子一次可以沿着树上的边从一个节点挪到另一个节点，但这棵树上有一些节点设置有障碍物，如果某个节点上设置了障碍物，小猴子就不能通过连接该节点的边挪动到该节点上。问小猴子是否能跑到树的叶子节点(叶子节点定义为只有一条边连接的节点)，如果可以，请输出小猴子跑到叶子节点的最短路径(通过的边最少)，否则输出字符串NULL。
- 输入
- 第一行给出数字n，表示这个树有n个节点，节点编号从0开始依次递增，0固定为根节点，1<=n<10000
- 第二行给出数字edge，表示接下来有edge行，每行是一条边
- 接下来的edge行是边: x y，表示x和y节点有一条边连接
- 边信息结束后接下来的一行给出数字block，表示接下来有block行，每行是个障碍物
- 接下来的block行是障碍物: X，表示节点x上存在障碍物
- 输出
- 如果小猴子能跑到树的叶子节点，请输出小猴子跑到叶子节点的最短路径(通过的边最少)，比如小猴子从0经过1到达2 (叶子节点) ，那么输出“0->1->2”，否则输出“NULL”。注意如果存在多条最短路径，请按照节点序号排序输出，比如0->1和0->3两条路径，第一个节点0一样，则比较第二个节点1和3，1比3小，因此输出0->1这条路径。再如 0->5->2->3 和0->5->1->4，则输出 0->5-31->4
样例1：
- 解释: n=4,edge=[[0,1],[0,2],[0,3]],block=[2,3]表示一个有4个节点、3条边的树，其中节点2和节点3上有障碍物，小猴子能从0到达叶子节点1 (节点1只有一条边[1,0]和它连接，因此是叶子节点) ，即可以跑出这个树，所以输出为0->1。
样例2
- 解释: 节点4上有障碍物，因此0-3-4这条路不通，节点2和节点6都是叶子节点，但0->1->2比0->1->5->6路径短(通过的边最少) ，因此输出为0->1->2
样例3：
- 解释:节点1是叶子节点，但存在障碍物，因此小猴子无法到达叶子节点，输出NULL
- 思路：典型最短路模型。使用bfs找到距离根最近的节点即可，注意要存储每个遍历状态经过的路径。
// 第二题
// 时间复杂度,空间复杂度都是O(N + E)
let task2 = (n, edge, block)=>{
// 用map存邻接表
let map = {};
// 遍历edge数组，记录邻接表
for(let i = 0; i < edge.length; i++){
if(!map[edge[i][0]]){
map[edge[i][0]] = [edge[i][1]];
} else {
map[edge[i][0]].push(edge[i][1]);
}
}
// console.log(map)
// bfs用的队列
let queue = [];
// 初始化压入[0]
queue.push([0]);
while(queue.length !== 0){
// 取队头元素，这里是一个路径
let curList = queue.shift();
// 取路径的最后一个元素
let cur = curList[curList.length - 1];
// 因为前面已经确认了他不是叶子节点，所以可以直接遍历
for(let next of map[cur]){
// 如果不是障碍物，并且是叶子节点
if(!block.includes(next) && !map[next]){
// 直接返回
return [...curList, next].join('->');
// 否则压入队列
} else if(!block.includes(next) && map[next]){
queue.push([...curList, next]);
}
}
}
// 对于为空的情况额外处理
return null;
}
// console.log(task2(4,[[0,1],[0,2],[0,3]],[2,3]))
04-26笔试
第一题、批量初始化次数
- 某部门在开发一个代码分析工具，需要分析模块之间的依赖关系，用来确定模块的初始化顺序、是否有循环依赖等问题。"批量初始化”是指一次可以初始化一个或多个模块。例如模块1依赖模块2，模块3也依赖模块2，但模块1和3没有依赖关系，则必须先"批量初始化”模块2，再"批量初始化"模块1和3。现给定一组模块间的依赖关系，请计算需要“批量初始化"的次数。
- 输入
- (1)第1行只有一个数字.表示模块总数N。
- (2)随后的N行依次表示模块1到N的依赖数据。每行的第1个数表示依赖的模块数量(不会超过N)，之后的数字表示当前模块依赖的ID序列。该序列不会重复出现相同的数字，模块ID的取值定在[1,N]之内。
- (3)模块总数N取值范围 1<=N<=1000.
- (4)每一行里面的数字按1个空格分隔。
- 输出
- 输出“批量初始化次数”.若有循环依赖无法完成初始化，则输出-1。
样例1：
样例2：
- 思路：拓扑排序模拟即可。
// 4.26第一题
// 时间复杂度O(n),空间复杂度O(n)
const task3 = (n,arr)=> {
let inDegree = new Array(n + 1).fill(0);
let map = {};
for(let i = 0; i < arr.length; i++){
let len = arr[i].length;
for(let j = 0; j < len; j++){
if(j == 0){
inDegree[i + 1] = arr[i][j];
continue;
}
if(!map[arr[i][j]]){
map[arr[i][j]] = [i + 1];
} else {
map[arr[i][j]].push(i + 1);
}
}
}
console.log(map,inDegree)
let depth = 0;
let queue = [];
for(let i = 1; i <= n; i++){
if(inDegree[i] == 0){
queue.push(i);
}
}
let cnt = 0;
while(queue.length){
// 用长度来限制每次只遍历一批
let len = queue.length;
cnt++;
while(len--){
let key = queue.shift();
let target = map[key];
if(target && target.length){
for(let k of target){
inDegree[k]--;
if(inDegree[k] == 0){
queue.push(k);
}
}
}
}
}
return cnt == 0 ? -1 : cnt;
}
//console.log(task3(3,[[1,2],[1,3],[1,1]]))
05-06笔试
第二题、表达式计算
- 给定一个字符串形式的表达式，保证每个字符串表达式中仅包含加(+)这1种运算符，计算并输出表达式结果.
- 要注意的是，+号两边的数据仅可能包含数字字符、小数点字符与特殊字符，特殊字符包括!@#，这些特殊字符的加法运算有特别的规则:
- !+!=0 !+@=13 !+#=4 @+@=7 @+#=20 #+#=5
- 注意1.保证每个表达式仅包含一个运算符 2.保证表达式一定可运算且有数据结果 3.保证运算符两边数据有效(不会出现包含两个小数点之类的无效数据) 4.表达式内不存在空格 5.特殊字符的加法运算符合交换律 6.如果表达式中包含特殊字符，则运算中不会出现数字与特殊字符的加法运算 7.表达式两边的数据均不以0开头，比如不会出现这样的表达式0250+0110
- 输入
- 第一行: 代表字符串长度(长度在[1,1000]之间)
- 第二行:代表一个字符串表达式
- 输出
- 输出一行，输出表达式结果
- 注意: 小数最后位如果为0则省略，如结果250.010则输出250.01，结果250.0则省略为250;同时，如果计算结果为”0250”，也需以最简化形式”250”输出。
样例1输入：
输出：250.0001
参考力扣435题，不难，慢慢做就好
第三题、魔幻森林救公主
- 一名王子的未婚妻公主被抓到了魔幻森林中，王子需要去救她，魔幻森林危险重重，除了一些怪物之外，还有时隐时现的路障，王子只能绕过怪物、绕过出现的路障或者等路障消失之后通过。
- 魔幻森林是一个n*n大小的二维地图，森林中的k只怪物分别在各自的位置中。每个地图点都有一个路障的状态循环，状态循环以3个单位时间作为一个环，我们用0代表没有路障，用1代表有路障，如'011'表示初始单位时间路障消失，下一个单位时间路障出现，再下一个单位时间路障继续存在.
- 王子在每个单位时间可以向上、下、左、右某个方向移动一个地图单位，也可以选择不移动，如果王子移动方向上有怪物，或者王子移动目的地在下一个单位时间存在路漳，则不可以朝该方向移动，同时，如果王子当前位置在下一个单位时间会出现路障，那王子也不可以选择停在原地.
- 我们需要计算王子到达公主的位置的最短时间
- 第一行: 地图大小n (2 <=n<= 100)
- 第二行: 怪物数量k (0 < k<= n*n-2)
- 第三行: 怪物位置，每个位置包含row和col用于代表row行col例，用空格分开，位置之间用空格间隔，三个位置示例: row1 col1 row2 col2 row3 col3，地图左上角位置为0 0，输入保证所有位置合法
- 第四行: 公主位置和王子起始位置共两个位置，row1 col1 row2 col2
- 第五行开始的n行: 每行n个字符串空格分开，每个字符串长度固定为3，内容固定只有’0‘和'1'，表示每个地图点的路障的状态循环
- 注意:
- 1.输入数据保证一定能找到公主
- 2.输入数据保证怪物位置与公主位置、王子起始位置不重合
- 3.输入数据保证怪物位置、公主位置下，路障的状态循环一定为'000'，即路障一定不会出现
- 4.输入数据保证王子起始位置的路障在第一个单位时间不会出现
- 5.输入数据保证位置一定合法
- 输出
- 输出一个数字，代表找到公主花费的最短时间
样例1输入
输出：5
- 解释: 最快路王子移动顺序: (0,0)-> (0,0)-> (0,1)-> (0,2)-> (1,2)-> (2,2)
- 另一条路 (时间6) : (0,0)->(1,0)->(1,0)-> (1,0)-> (2,0)->(2,1)->(2,2)
样例2输入
输出 4
- 解释：最快路王子移动顺序:(0,0)->(1,0)->(0,0)-> (0,1)->(0,2)
- 另一条路 (时间6) : (0,0)->(1,0)-> (2,0)-> (2,1)->(2,2)-> (1,2)->(0.2)
- 思路与代码：最短路的模型，但是要注意判断怪兽和障碍物的位置，并且每个位置可以原地踏步，由于每个点的障碍物变化是以3为周期的，所以每个位置最多只需要停留3次即可。
// 5-06第三题
// 空间复杂度O(n^3) 时间复杂度最大可以是O(n^2)，原本是O(V + E),顶点数+边数
// 二维矩阵的顶点数为n*n,边数为5*n^2
const question3 = (n,k,prince,princess,obtical,map) => {
let direction = [-1, 0, 1, 0, -1]; //遍历方向
let res = 0;
let grid = [];
for(let k = 0; k < 3; k++){
let tempArr = [];
for(let i = 0; i < n; i++){
let path = [];
for(let j = 0; j < n; j++){
path.push(map[i][j][k]); //用三维数组存储地图
}
tempArr.push(path);
}
grid.push(tempArr);
}
for(let i = 0; i < k; i++){ // 将障碍加入地图中
grid[0][obtical[i][0]][obtical[i][1]] = '1';
grid[1][obtical[i][0]][obtical[i][1]] = '1';
grid[2][obtical[i][0]][obtical[i][1]] = '1';
}
let queue = [];
let visit = Array.from(Array(n),()=>Array(n).fill(0));
queue.push([prince[0],prince[1],0,0]);
// bfs最短路径问题
while(queue.length){
[x, y, time, wait_time] = queue.shift();
if(x == princess[0] && y == princess[1]){
return time;
}
for(let i = 0; i < 4; i++){ //往四个方向遍历
let nx = x + direction[i];
let ny = y + direction[i + 1]; //这里尤其注意，如果等待时间超过3，这个点已经没有意义了，直接终止
if(nx < 0 || ny < 0 || nx >= n || ny >= n || visit[nx][ny] || grid[(time + 1) % 3][nx][ny] === '1' || wait_time > 3){
continue;
}
visit[nx][ny] = 1;// 每次压入队列time + 1，等待时间为0
queue.push([nx, ny, time + 1, 0]);
}// 如果等待时间不超过3并且下一个坐标为0，则可以原地不动
if(wait_time <= 3 && grid[(time + 1) % 3][x][y] === '0'){
queue.push([x, y, time + 1, wait_time + 1]);
}
}
}
console.log(question3(3,1,[0,0],[0,2],[[1,1]],[['010','011','000'],['000','000','000'],['000','000','000']]));
#23届找工作求助阵地##我的实习求职记录##华为##我的求职思考##华为信息集散地#
