华为笔试 3.27 500分

3月13日投递了华为简历，通用软件开发

3月27日进行了华为的笔试，我第一题过了100%，第二题过了82%，第三题过了85% , 总共耗时约 70 分钟

一道简单，两道中等吧

今天室友来问我笔试，我就在这里写一写思路，具体代码实现可能过两天在完善了，可能写的很简陋，甚至有错

第一题：具体题目记不得了，大概就是排序，大家应该都会做，我就不讲了

第二题：是一个二叉平衡树的问题，给定一个升序数组，构建为二叉平衡树，找到符合条件的叶子节点，并求符合条件的值的和

思路：

1. 首先肯定不是让你构建一颗二叉平衡树，时间肯定不够
2. 你要知道二叉平衡树的大概概念，以及构建流程，这里就不讲了
3. 核心：查找叶子节点可以用二分查找递归的方法（暂时见代码，如果不理解，之后更新详细版本，今天太晚了）
4. 找出叶子节点了，那就简单了，后面自己写吧

function search(low,high){
  if(low===high){return }
  else{
  	let mid=Math.floor(low+high)/2
	visited[mid]=1
	search(low,mid-1)
	search(mid+1,high)
  }
}
//最后visited数组中为0的元素就是叶子节点

这题我只过了82%的样例，可能哪里出错了，但是我有找到，有无大佬帮忙看看我的思路哪里有问题

具体实现：

function search(visited,low,high){
  if(low===high){
    visited[low]=1
  }
  else if(low<high){
    let mid=Math.floor((low+high)/2)
    search(visited,low,mid-1)
    search(visited,mid+1,high)
  }
}
//输入为一个一维数组
function answer(nums,min,max){
  nums.sort((a,b)=>a-b)
  const visited=new Array(nums.length).fill(0)
  const yezi=[]
  search(visited,0,nums.length-1)
  for(let i=0;i<nums.length;i++){
    if(visited[i]===1){
      yezi.push(nums[i])
    }
  }
  let sum=0,tag=0
  for(let key of yezi){
    if(key>=min&&key<=max){
      sum+=key
      tag=1
    }
  }
  console.log(yezi)
  if(tag){
    return sum
  }
  else{
    if(yezi.length===0){
      return 0
    }
    else{
      return yezi.pop()
    }
  }
}

console.log(answer([7,17,35,56,65,66],56,65))

第三题：拓扑排序，给定一个数字n，表示n个节点，在给定一个二维数组，如[ [ 1 , 0 ] , [ 1 , 2 ] ]表示要完成任务1，先完成任务0，要完成任务1，先完成任务2，输出执行顺序

思路：暴力解法

1. 先遍历二维数组，更新一个前缀任务数组，表示完成该任务，需要先完成的任务的数量
2. 还是循环，查找前缀任务数量为0的任务，并添加到结果队列中，并把相应前缀任务为该任务的任务的前缀任务数量-1（这句话可能有点绕）
3. 就这样循环，直到所有任务都在结果队列里，或者这一次循环没有添加任何任务到结果队列中就结束

具体实现：

//输入n,表示n个任务，然后输入一个二维数组，二维数组中的每一个表示一个任务的前置任务，如[ 1 , 0 ],表示完成任务1需要任务0先完成。
function topologicalSort(n,pretask) {
  const pre=new Array(n).fill(0)
  for(let key of pretask){
    pre[key[0]]++
  }

  const res=[]
  let tag=1
  while(tag && res.length<n){
    tag=0
    for(let i=0;i<n;i++){
      if(pre[i]===0){
        res.push(i)
        pre[i]=-1
        tag=1
        for(let key of pretask){
          if(key[1]===i){
            pre[key[0]]--
          }
        }
      }
    }
  }
  if(res.length!==n){
    return []
  }
  return res
}
console.log(topologicalSort(6,[[1,0],[2,0],[3,1],[3,2],[3,4],[5,4],[5,2]]))

这题我过了85%的样例，最后好像是超时了，还是答案错误，记不得了，优化办法的我觉得可能可以加上排序吧，或者直接换个别的方法，等我明天试一试。

大概先这样吧，讲的很简陋

华为hr什么时候约我面试呀

到现在也没约我面试，估计是没有岗位了，24届春招大家都散了吧，下面是25届实习生的时代了