前端笔试

并查集

  1. 547. 省份数量
  2. 1202. 交换字符串中的元素
  3. 684. 冗余连接
  4. 947. 移除最多的同行或同列石头
  5. 803. 打砖块
  6. 721. 账户合并
  7. 1319. 连通网络的操作次数

https://zhuanlan.zhihu.com/p/93647900/

手写UnionFind，并查集 不再畏惧 https://leetcode.cn/problems/satisfiability-of-equality-equations/solution/shou-hui-tu-jie-shou-xie-unionfind-bing-cha-ji-bu-/

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
class UnionFind {
  constructor(num) { // num 顶点个数
    this.roots = new Array(num)
    this.ranks = new Array(num)
    for (let i = 0; i < num; i++) {
      this.roots[i] = -1
      this.ranks[i] = 0
    }
  }
  findRoot(x) { // 找出顶点x的根节点
    let x_root = x
    while (this.roots[x_root] !== -1) { // 一直找父节点，找到尽头
      x_root = this.roots[x_root]
    }
    return x_root // 返回根节点
  }
  union(x, y) { // 把顶点x和顶点y所在的集合合并到一起
    let x_root = this.findRoot(x)
    let y_root = this.findRoot(y)
    if (x_root === y_root) return
    let x_rank = this.ranks[x_root]
    let y_rank = this.ranks[y_root]
    if (x_rank < y_rank) {    // 谁高度大，谁就作为根节点
      this.roots[x_root] = y_root
    } else if (y_rank < x_rank) {
      this.roots[y_root] = x_root
    } else {                  // 一样高，谁作为根节点都行
      this.roots[y_root] = x_root
      this.ranks[x_root]++
    }
  }
}

服务器广播

题目描述
服务器连接方式包括直接相连，间接连接。
A 和 B 直接连接， B 和 C 直接连接，则 A 和 C 间接连接。直接连接和间接连接都可以发送广播。
给出一个 N * N 数组，代表 N 个服务器， matrix[i][j] == 1 ，则代表 i 和 j 直接连接；
不等于 1 时，代表 i 和 j 不直接连接。 matrix[i][i]== 1 ，即自己和自己直接连接。
matrix[i][j]==matrix[j][i] 。
计算初始需要给几台服务器广播，才可以使侮个服务器都收到广播。

【分析】
实质是图的遍历，求连通分量的个数；
做这道题的时候没想到遍历该怎么写，用了比较麻烦的方法；
用一个 Set 存储一个连通分量，将它们保存到数组中，数组的长度就是连通分量的个数，即本题的答案；
具体做法是：遍历整个邻接矩阵，每遍历到新的一行，判断当前节点是否已经存在于某个已有的连通分量，如果有，将与其直接连接的节点存到该连通分量；如果没有，新建一个 Set （新连通分量）进行存储，最后得到整个连通分量的数组，用 Set 是保证没有重复，数组也可

【实现】

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
// 获取输入
const input = "[[1,0,1,0,1,1],[0,1,0,0,0,0],[1,0,1,0,0,0],[0,0,0,1,0,0],[1,0,0,0,1,0],[1,0,0,0,0,1]]"
// 转为数组
const arr = JSON.parse(input)

const len = arr.length
// 记录连通分量
const res = []
for (let i = 0; i < len; i++) {
    // 标记：判断当前节点是否已经被记录（已属于已有的某个连通分量）
    let flag = false

    // 当前所指向的连通分量
    let temp = null

    for (const x of res) {
        if (x.has(i)) {
            // 若在连通分量数组中找到，表示该节点已经与之前的节点连通，那么与该节点连通的节点，也与之前的节点间接连通
            temp = x
            flag = true
            break
        }
    }

    if (!flag) {
        // 如果未找到，则创建一个新的set：表示一个新的连通分量
        const set = new Set()
        set.add(i)
        res.push(set)
        temp = set
    }

    for (let j = i + 1; j < len; j++) {
    	// 邻接矩阵对称，所以从 i+1 开始
        if (arr[i][j] === 1) {
        	// i 与 j 直接连通，将 j 存储到 i 所属的连通分量中
            temp.add(j)
        }
    }
}

// 输出结果
console.log(res.length);

华为机试真题_跳格子游戏

地上共有N个格子，你需要跳完地上所有的格子，但是格子间是有强依赖关系的，跳完前一个格子后，后续的格子才会被开启，格子间的依赖关系由多组steps数组给出，steps[0]表示前一个格子,steps[1]表示steps[0]可以开启的格子:

比如[0,1]表示从跳完第0个格子以后第1个格子就开启了，
比如[2,1]，[2,3]表示跳完第2个格子后第1个格子和第3个格子就被开启了

请你计算是否能由给出的steps数组跳完所有的格子,如果可以输出yes，否则输出no

思路：

首先定义一个列表保存格子开启状态，列表长度为N

  • 1 表示格子是开启状态，可以从该点去打开其他点
  • 0 表示格子是关闭状态，需要其他点来打开
  • 输入的每行，第二个元素就是需要被开启的格子所以置为0
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
// 找格子
let n = 5
// let data = [[4, 3], [0,4], [2,1], [3,2], [0,1], [1, 3]]
let data = [[0, 3], [0,4], [0,1], [0,2]]

function jump () {
    // 定义一个数组维护格子的状态 舒适化时 data[i][1]表示需要其他格子开启，因此初始化为0
    let sourceState = new Array(n).fill(1)
    for (let i = 0; i <data.length; i++) {
        sourceState[data[i][1]] = 0
    }
    let states = sourceState.slice()

    // 第一个参数表示，当前的节点，第二参数表示已经走过的路径
    let dfs = (cur, link) => {
        if (link.length == n) {
            res.push(link.slice())
            return 
        }


        // 从给的路径去找
        for (let [start, end] of data) {
            // 还需要判断是否走过该节点了
            if (link.includes(end)) {
                continue
            }
            if (start == cur) {
                // 记录当前开启的节点
                states[end] = 1
                // 从开启的节点，继续迭代
                link.push(end)
                dfs(end, link)
                // 撤销，下一次迭代
                link.pop()
            }
        }
        // 从statas中找
        for (let i = 0; i< states.length; i++) {
            // 还需要判断是否走过该节点了
            if (link.includes(i)) {
                continue
            }
            if (states[i] == 1) {
                link.push(i)
                dfs(i, link)
                // 撤销，下一次迭代
                link.pop()
            }
        }

    }


    // 查找过程，需要我们从 states 中的已开启节点出发，递归遍历
    let res = []
    for (let i = 0; i< sourceState.length; i++) {
        if (sourceState[i] == 1) {
            dfs(i, [i])
        }
    }
    console.log(res)
}
jump()

二叉树的中序遍历

【二叉树中序遍历】

根据给定的二叉树结构描述字符串，输出该二叉树按照中序遍历结果字符串。中序遍历顺序为：左子树，根结点，右子树。

输入描述

由大小写字母、左右大括号、逗号组成的字符串:字母代表一个节点值，左右括号内包含该节点的子节点。

左右子节点使用逗号分隔，逗号前为空则表示左子节点为空，没有逗号则表示右子节点为空。

二叉树节点数最大不超过100。

注:输入字符串格式是正确的，无需考虑格式错误的情况。

输出描述

输出一个字符串为二叉树中序遍历各节点值的拼接结果。

示例 1 输入输出示例仅供调试，后台判题数据一般不包含示例

输入

1
a{b{d,e{g,h{,I}}},c{f}}

输出

1
dbgehiafc

答案

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
// 遍历中序二叉树
class Node {
    constructor(val, left, right) {
        this.val = val
        this.left = left || null
        this.right = right || null
    }
}
function traverse(node) {
    if (node == null) {
        return 
    }
	// 遍历就简单了
    if (node.left) traverse(node.left)
    res.push(node.val)
    if (node.right) traverse(node.right)
}
function str2tree(str) {
    let parent = null,left = null,right =null, temp
    let data = str.split('')
    let stack = [] // 维护栈来构建二叉树
    for (let i = 0; i < data.length; i++) {
        let cur = data[i]
        if (cur == '}') {
            // 出栈，处理数据
            let popStr = stack.pop()  
            while ( popStr.val !== '{') {
                if (popStr.val == ',') {
                    // 修改为右节点，temp初始化
                    right = temp
                    temp = null
                } else {
                    // 遇到值，默认是左节点
                    temp = popStr
                }
                popStr = stack.pop()
            }
            // 当前的str为 {
            left = temp
            parent = stack.pop()
            parent.left = left
            parent.right = right
            left = null
            right = null
            // 把新的子结构放进数组
            stack.push(parent)
            parent = null
        } else {
            stack.push(new Node(cur))
            console.log(stack)
        }
    }
    return stack.pop()
    
}
let inputs = 'a{b{d,e{g,h{,I}}},c{f}}'
// 转成 tree之后开始遍历
let treeRoot = str2tree(inputs)
let res = []
traverse(treeRoot)
console.log(res)
前端笔试
#前端 #笔试 #机试
前端笔试
http://example.com/2023/04/24/前端笔试/
作者
lyric
发布于
2023年4月24日
许可协议