华为提前批机考20210630
哈哈 牛友们 有收到结果么。。我还没有收到，，hr说过了会有通知。我问题没过有没有 他不回我。。。
1. 一道图算法，求图是否连通，如果连通则求出最小权值和 （leetcode hard）
题主一开始思路错了，想成了广度优先。考完试才反应过来是权值和。所以这道就GG了。
贴一下js实现吧
本题难点：
图结构的构建
最小生成树的算法
js的输入处理。。华为的机考只有Node 所以只会v8的同学注意了。
class Vertex {
constructor(data){
this.data = data
this.firstEdge = null
this.outNum = 0
this.inNum = 0
}
}
class Edge {
constructor(data,weight = 0,nextEdge = null){
this.data = data
this.nextEdge = nextEdge
this.weight = weight
}
}
class Graph {
constructor(isDirect){
this.eNum = 0
this.adj = []
this.isDirect = isDirect
}
_find(vData){
let pos = -1
for(let i = 0;i<this.adj.length;i++){
if(vData === this.adj[i].data){
pos = i
}
}
return pos
}
initVertex(verArry){
for(let i = 0;i<verArry.length;i++){
let newVex = new Vertex(verArry[i])
this.adj[i] = newVex
}
}
insertVertex(data) {
let newVex = new Vertex(data)
this.adj.push(newVex)
}
addEdge(v1, v2, weight = 0) { // 向图中插入边(v1, v2)
let posV1 = this._find(v1)
let posV2 = this._find(v2)
let edgeV1 = new Edge(v1, weight)
let edgeV2 = new Edge(v2, weight)
// 如果是无向图，在插入边(v1, v2)时还要插入边(v2, v1)
if (!this.isDirect) {
if (!this.hashEdge(v1, v2) && !this.hashEdge(v2, v1)) {
if (posV1 > -1) {
let curVex = this.adj[posV1].firstEdge
if (!curVex) {
this.adj[posV1].firstEdge = edgeV2
this.adj[posV1].outNum++
} else {
let length = this.adj[posV1].outNum - 1
while (length--) {
curVex = curVex.nextEdge
}
curVex.nextEdge = edgeV2
this.adj[posV1].outNum++
}
}
if (posV2 > -1) {
let curVex = this.adj[posV2].firstEdge
if (!curVex) {
this.adj[posV2].firstEdge = edgeV1
this.adj[posV2].outNum++
} else {
let length = this.adj[posV2].outNum - 1
while (length--) {
curVex = curVex.nextEdge
}
curVex.nextEdge = edgeV1
this.adj[posV2].outNum++
}
}
this.eNum++
}
} else {
if (!this.hashEdge(v1, v2)) {
if (posV1 > -1) { // 如果顶点x在顶点表中
let curVer = this.adj[posV1].firstEdge;
if (!curVer) { // 如果当前顶点没有第一个边节点
this.adj[posV1].firstEdge = edgeV2;
this.adj[posV1].outNum++;
} else {
let len = this.adj[posV1].outNum - 1;
while (len--) {
curVer = curVer.nextEdge;
}
curVer.nextEdge = edgeV2;
this.adj[posV1].outNum++; // 顶点x的出度增长
}
this.eNum++;
}
if (posV2 > -1) {
let curVer = this.adj[posV2]
curVer.inNum++
}
}
}
}
getEdgeWeight(v1, v2) {
let pos = this._find(v1)
if (pos > -1) {
let curVer = this.adj[pos].firstEdge
while (curVer) {
if (curVer.data === v2) { return curVer.weight }
curVer = curVer.nextEdge
}
return 0
}
}
_BSF(vData, visited) {
let result = ''
const queue = []
let pos = this._find(vData)
if (pos > -1) {
result += `${vData}`
visited[pos] = true
let curVer = this.adj[pos]
queue.push(curVer)
while (queue.length) {
curVer = queue.shift()
//注意要回到顶点表中再次出发
pos = this._find(curVer.data)
curVer = this.adj[pos].firstEdge
while (curVer) {
pos = this._find(curVer.data)
if (!visited[pos]) {
result += `->${curVer.data}`
visited[pos] = true
queue.push(curVer)
}
curVer = curVer.nextEdge
}
}
}
return result
}
//判断图是否连通
isConnece(vData = this.adj[0].data) {
const visited = []
for (let i = 0; i < this.adj.length; i++) {
visited[i] = false
}
this._BSF(vData, visited)
for (let i = 0; i < visited.length; i++) {
if (visited[i] = false) { return false }
}
return true
}
//普利姆算法 求最小生成树 只不过本题需要一些改动 因为是定起点
getPrimMSTree() {
if (!this.isConnece()) { return }
let V = this.adj //顶点集
let Vt = [V[0]] //添加任意一顶点
let VVt = V.filter(item => Vt.indexOf(item) === -1) //VVt = V - Vt
let MSTtree = new Graph(this.isDirect)
V.forEach(item => MSTtree.insertVertex(item.data)) //先将所有顶点都放入图中
while (Vt.length !== V.length) {
let mVt = null //权值最小的第一个顶点
let mVVt = null //权值最小的另一个顶点
let minW = Number.MAX_SAFE_INTEGER //先将minW附一个最大值
//在vt和vvt中找到权值最小的边
// V是图中所有所有顶点的集合，VT初始时在V中任选一个顶点（算法实现里假设总是选择第一个顶点），
//找出VT与V-VT中所有能构成的边的组合，选择其中权重最小的组合，然后取出这个组合在V-VT的中
//顶点放入VT中，直到VT=V。
for (let i = 0; i < Vt.length; i++) {
for (let j = 0; j < VVt.length; j++) {
let weight = this.getEdgeWeight(Vt[i].data, VVt[j].data)
if (weight && weight < minW) {
minW = weight
mVt = Vt[i]
mVVt = VVt[j]
}
}
}
Vt.push(mVVt)
MSTtree.addEdge(mVt.data, mVVt.data, minW)
VVt = V.filter(x => Vt.indexOf(x) === -1);
}
return MSTtree
}
}
2. 输入两个连续递增的序列s1，s2 。ss1和ss2分别为他们的子序列，求满足ss1[i+1] - ss1[i] === ss2[i+1] - ss2[i] 的子序列的最长长度。(leetcode middle) 题主的思路 构建原两个序列的相邻两数的差数组 distance1,distance2。之后对两个数组进行顺位的比对 如果相等则index++ 如果distance1[i] > distance2[i] 则 distance2[i]+=distance2[i+1]
同时distance2.splice(index+1,1) s2.splice(index,1)，在递归。distance1[i] < distance2[i] 同理。最后根据index截取两个序列的长度。（65%通过率。。。）
难点：index的控制和distance和s位置的映射关系
js输入的处理 （竟然因为输入最后一位是空格 在构建的时候出了NaN 调试的半天）
吐槽一下华为机试，题目没有完全通过，也不告诉你为啥 是结果错了还是超时了。。也没有错的那道题的用例。。
3. 逃出生天
一个二维数组每个位置有一个数表示几秒之后该位置不能通过，一个人从[0,0]开始要移动到[row-1,col-1]。每次移动需要消耗一秒。(leetcode middle)
题主思路：广度优先，每次循环多了一次整个二维数组的数减一 不过只有30%通过率 。早上突然想到 可以在判断移动的时候用数组的值-已经走的步数。这样就不用每次都二维数组的值减一了。效率会高一点。。不过我怎么之后是因为我的结果有问题还是因为超时才导致没通过的。。。。
总结: 这场机考两个小时 算下来总过才做出一道完整的题 65%+30% 。之前一直在leetcode刷题 不熟悉自己处理输入的这种形式，而且考前只练习了V8。题的思路都有，但是代码实现不顺畅，总是有的细节把握不好。牛客网的华为机试建议下架。本来刷了几道里面的困难题以为自己考试稳了。结果难度根本不是一个量级 （牛客网华为机试里的困难题相当于leetcode的middle偏简单的）。
投递交通银行等公司7个岗位 >
腾讯一面1066人在聊