跳到主要内容

25 篇博文 含有标签「广度优先搜索」

查看所有标签

· 阅读需 2 分钟

1、题干

给你两棵二叉树的根节点 pq ,编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

 

示例 1:

输入:p = [1,2,3], q = [1,2,3]
输出:true

示例 2:

输入:p = [1,2], q = [1,null,2]
输出:false

示例 3:

输入:p = [1,2,1], q = [1,1,2]
输出:false

 

提示:

  • 两棵树上的节点数目都在范围 [0, 100]
  • -104 <= Node.val <= 104

2、思路

DFS 判断两棵树当前节点值是否相等,左右子树是否相等

3、代码

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
if (p && q) return p.val === q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);

return !p && !q;
};

· 阅读需 2 分钟

1、题干

给定一个二叉树:

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}

填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL

初始状态下,所有 next 指针都被设置为 NULL

 

示例 1:

输入:root = [1,2,3,4,5,null,7]
输出:[1,#,2,3,#,4,5,7,#]
解释:给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。序列化输出按层序遍历顺序(由 next 指针连接),'#' 表示每层的末尾。

示例 2:

输入:root = []
输出:[]

 

提示:

  • 树中的节点数在范围 [0, 6000]
  • -100 <= Node.val <= 100

进阶:

  • 你只能使用常量级额外空间。
  • 使用递归解题也符合要求,本题中递归程序的隐式栈空间不计入额外空间复杂度。

    2、思路

    BFS模拟,每一层的节点用一个队列存储,队列中节点的 next 指向下一个节点即可。

    这题没有 Rust 编码环境。。

    3、代码

    function connect(root: Node | null): Node | null {
    let queue: Node[] = root ? [root] : [];

    while (queue.length) {
    const nextQueue = [];
    for (let i = 0; i < queue.length; i++) {
    queue[i].next = queue[i + 1];
    if (queue[i].left) nextQueue.push(queue[i].left);
    if (queue[i].right) nextQueue.push(queue[i].right);
    }
    queue = nextQueue;
    }

    return root;
    };

    · 阅读需 3 分钟

    1、题干

    骑士在一张 n x n 的棋盘上巡视。在 有效 的巡视方案中,骑士会从棋盘的 左上角 出发,并且访问棋盘上的每个格子 恰好一次

    给你一个 n x n 的整数矩阵 grid ,由范围 [0, n * n - 1] 内的不同整数组成,其中 grid[row][col] 表示单元格 (row, col) 是骑士访问的第 grid[row][col] 个单元格。骑士的行动是从下标 0 开始的。

    如果 grid 表示了骑士的有效巡视方案,返回 true;否则返回 false

    注意,骑士行动时可以垂直移动两个格子且水平移动一个格子,或水平移动两个格子且垂直移动一个格子。下图展示了骑士从某个格子出发可能的八种行动路线。

     

    示例 1:

    输入:grid = [[0,11,16,5,20],[17,4,19,10,15],[12,1,8,21,6],[3,18,23,14,9],[24,13,2,7,22]]
    输出:true
    解释:grid 如上图所示,可以证明这是一个有效的巡视方案。

    示例 2:

    输入:grid = [[0,3,6],[5,8,1],[2,7,4]]
    输出:false
    解释:grid 如上图所示,考虑到骑士第 7 次行动后的位置,第 8 次行动是无效的。

     

    提示:

    • n == grid.length == grid[i].length
    • 3 <= n <= 7
    • 0 <= grid[row][col] < n * n
    • grid 中的所有整数 互不相同

    2、思路

    从左上角开始 DFS 遍历,如果能完成遍历则说明巡视方案有效

    3、代码

    function checkValidGrid(grid: number[][]): boolean {
    let vis = 0;
    const dirs = [[-2, -1], [2, 1], [-2, 1], [2, -1], [-1, -2], [1, 2], [-1, 2], [1, -2]];
    const t = grid.length * grid[0].length;

    function dfs(r: number, c: number) {
    vis++;
    if (grid[r][c] === t - 1) return;

    for (const [dr, dc] of dirs) {
    if (grid[r + dr]?.at(c + dc) === grid[r][c] + 1) {
    dfs(r + dr, c + dc);
    break;
    }
    }
    }

    dfs(0, 0);

    return vis === t;
    };

    4、复杂度

    • 时间复杂度: O(n2)O(n^2)
    • 空间复杂度: O(n2)O(n^2)

    5、执行结果

    image.png

    · 阅读需 4 分钟

    1、题干

    给你一个字符串 s 以及两个整数 ab 。其中,字符串 s 的长度为偶数,且仅由数字 09 组成。

    你可以在 s 上按任意顺序多次执行下面两个操作之一:

    • 累加:将  a 加到 s 中所有下标为奇数的元素上(下标从 0 开始)。数字一旦超过 9 就会变成 0,如此循环往复。例如,s = "3456"a = 5,则执行此操作后 s 变成 "3951"
    • 轮转:将 s 向右轮转 b 位。例如,s = "3456"b = 1,则执行此操作后 s 变成 "6345"

    请你返回在 s 上执行上述操作任意次后可以得到的 字典序最小 的字符串。

    如果两个字符串长度相同,那么字符串 a 字典序比字符串 b 小可以这样定义:在 ab 出现不同的第一个位置上,字符串 a 中的字符出现在字母表中的时间早于 b 中的对应字符。例如,"0158” 字典序比 "0190" 小,因为不同的第一个位置是在第三个字符,显然 '5' 出现在 '9' 之前。

     

    示例 1:

    输入:s = "5525", a = 9, b = 2
    输出:"2050"
    解释:执行操作如下:
    初态:"5525"
    轮转:"2555"
    累加:"2454"
    累加:"2353"
    轮转:"5323"
    累加:"5222"
    累加:"5121"
    轮转:"2151"
    累加:"2050"​​​​​
    无法获得字典序小于 "2050" 的字符串。

    示例 2:

    输入:s = "74", a = 5, b = 1
    输出:"24"
    解释:执行操作如下:
    初态:"74"
    轮转:"47"
    累加:"42"
    轮转:"24"​​​​​
    无法获得字典序小于 "24" 的字符串。

    示例 3:

    输入:s = "0011", a = 4, b = 2
    输出:"0011"
    解释:无法获得字典序小于 "0011" 的字符串。

     

    提示:

    • 2 <= s.length <= 100
    • s.length 是偶数
    • s 仅由数字 09 组成
    • 1 <= a <= 9
    • 1 <= b <= s.length - 1

    2、思路

    没啥思路,BFS+备忘录过了

    BFS枚举,遍历队列中的字符串,对每个字符串执行轮转和累加操作,如果操作结果没有被访问过则添加到下个队列,重复上述步骤直到队列为空

    3、代码

    function findLexSmallestString(s: string, a: number, b: number): string {
    let ans = s, queue = [s], visited = new Set().add(s);

    while (queue.length) {
    const next = [];

    for (const q of queue) {
    // 是否最小
    if (q < ans) ans = q;

    // 轮转
    const rs = q.slice(q.length - b) + q.slice(0, q.length - b);
    if (!visited.has(rs)) visited.add(rs), next.push(rs);

    // 累加
    const arr = [...q];
    for (let i = 1; i < q.length; i += 2) {
    arr[i] = `${(+q[i] + a) % 10}`;
    }
    const as = arr.join('');
    if (!visited.has(as)) visited.add(as), next.push(as);
    }

    queue = next;
    }

    return ans;
    };

    4、执行结果

    image.png

    · 阅读需 4 分钟

    1、题干

    如果你熟悉 Shell 编程,那么一定了解过花括号展开,它可以用来生成任意字符串。

    花括号展开的表达式可以看作一个由 花括号逗号小写英文字母 组成的字符串,定义下面几条语法规则:

    • 如果只给出单一的元素 x,那么表达式表示的字符串就只有 "x"R(x) = {x}
      • 例如,表达式 "a" 表示字符串 "a"
      • 而表达式 "w" 就表示字符串 "w"
    • 当两个或多个表达式并列,以逗号分隔,我们取这些表达式中元素的并集。R({e_1,e_2,...}) = R(e_1) ∪ R(e_2) ∪ ...
      • 例如,表达式 "{a,b,c}" 表示字符串 "a","b","c"
      • 而表达式 "{{a,b},{b,c}}" 也可以表示字符串 "a","b","c"
    • 要是两个或多个表达式相接,中间没有隔开时,我们从这些表达式中各取一个元素依次连接形成字符串。R(e_1 + e_2) = {a + b for (a, b) in R(e_1) × R(e_2)}
      • 例如,表达式 "{a,b}{c,d}" 表示字符串 "ac","ad","bc","bd"
    • 表达式之间允许嵌套,单一元素与表达式的连接也是允许的。
      • 例如,表达式 "a{b,c,d}" 表示字符串 "ab","ac","ad"​​​​​​
      • 例如,表达式 "a{b,c}{d,e}f{g,h}" 可以表示字符串 "abdfg", "abdfh", "abefg", "abefh", "acdfg", "acdfh", "acefg", "acefh"

    给出表示基于给定语法规则的表达式 expression,返回它所表示的所有字符串组成的有序列表。

    假如你希望以「集合」的概念了解此题,也可以通过点击 “显示英文描述” 获取详情。

     

    示例 1:

    输入:expression = "{a,b}{c,{d,e}}"
    输出:["ac","ad","ae","bc","bd","be"]

    示例 2:

    输入:expression = "{{a,z},a{b,c},{ab,z}}"
    输出:["a","ab","ac","z"]
    解释:输出中 不应 出现重复的组合结果。

     

    提示:

    • 1 <= expression.length <= 60
    • expression[i]'{''}'',' 或小写英文字母组成
    • 给出的表达式 expression 用以表示一组基于题目描述中语法构造的字符串

    2、思路

    本题要处理的子表达式主要包括3类:

    • 单层:{xxx,xxx}
    • 嵌套:{{xxx},{xxx}}
    • 相接:{xxx}{xxx}xxx{xxx}{xxx}xxx

    具体代码实现逻辑如下:

    • 扁平化:把最内层的单层表达式提取到上一层(这会逐渐把嵌套和单层表达式都处理掉)
    • 拼接组合:拼接组合最内层相接子表达式
    • 重复这两个步骤直到表达式中没有任何花括号
    • 最后对表达式进行拆分、去重、排序

    3、代码

    function braceExpansionII(exp: string): string[] {
    const reg0 = /\{([a-z,]+)\}/g;
    const reg1 = new RegExp(`(?<![a-z}])${reg0.source}(?![a-z{])`, 'g');
    const reg2 = new RegExp(`(${reg0.source}){2,}|[a-z]+(${reg0.source})+|(${reg0.source})+[a-z]+`, 'g');

    while (1) {
    const f1 = reg1.test(exp);
    if (f1) exp = exp.replace(reg1, '$1');

    const f2 = reg2.test(exp);
    if (f2) {
    exp = exp.replace(reg2, (m) => {
    const reg = new RegExp(`${reg0.source}|[a-z]+`, 'g');

    const tokenGroup = (m.match(reg) || []).map(s => s.split(/,|\{|\}/).filter(Boolean));

    let ans = tokenGroup[0];
    for (let i = 1; i < tokenGroup.length; i++) {
    const newAns = [];
    for (const h of ans) {
    for (const t of tokenGroup[i]) {
    newAns.push(h + t);
    }
    }
    ans = newAns;
    }

    return `{${ans.join(',')}}`
    });
    }

    if (!f1 && !f2) break;
    }

    return [...new Set(exp.split(','))].sort();
    };

    4、执行结果

    image.png

    · 阅读需 4 分钟

    1、题干

    你还记得那条风靡全球的贪吃蛇吗?

    我们在一个 n*n 的网格上构建了新的迷宫地图,蛇的长度为 2,也就是说它会占去两个单元格。蛇会从左上角((0, 0) 和 (0, 1))开始移动。我们用 0 表示空单元格,用 1 表示障碍物。蛇需要移动到迷宫的右下角((n-1, n-2) 和 (n-1, n-1))。

    每次移动,蛇可以这样走:

    • 如果没有障碍,则向右移动一个单元格。并仍然保持身体的水平/竖直状态。
    • 如果没有障碍,则向下移动一个单元格。并仍然保持身体的水平/竖直状态。
    • 如果它处于水平状态并且其下面的两个单元都是空的,就顺时针旋转 90 度。蛇从((r, c)(r, c+1))移动到 ((r, c)(r+1, c))。
    • 如果它处于竖直状态并且其右面的两个单元都是空的,就逆时针旋转 90 度。蛇从((r, c)(r+1, c))移动到((r, c)(r, c+1))。

    返回蛇抵达目的地所需的最少移动次数。

    如果无法到达目的地,请返回 -1

     

    示例 1:

    输入:grid = [[0,0,0,0,0,1],
    [1,1,0,0,1,0],
      [0,0,0,0,1,1],
      [0,0,1,0,1,0],
      [0,1,1,0,0,0],
      [0,1,1,0,0,0]]
    输出:11
    解释:
    一种可能的解决方案是 [右, 右, 顺时针旋转, 右, 下, 下, 下, 下, 逆时针旋转, 右, 下]。

    示例 2:

    输入:grid = [[0,0,1,1,1,1],
      [0,0,0,0,1,1],
      [1,1,0,0,0,1],
      [1,1,1,0,0,1],
      [1,1,1,0,0,1],
      [1,1,1,0,0,0]]
    输出:9

     

    提示:

    • 2 <= n <= 100
    • 0 <= grid[i][j] <= 1
    • 蛇保证从空单元格开始出发。

    2、思路

    使用 BFS 模拟,模拟过程使用二维矩阵存储访问状态,访问状态使用二进制表示:0未访问,1水平访问,2垂直访问,3水平访问+垂直访问

    3、代码

    function minimumMoves(grid: number[][]): number {
    const n = grid.length;
    const dirs = [[0, 0], [0, 1], [1, 0], [1, 1]];
    const visited = grid.map(g => g.map(() => 0));

    function validate([r1, c1, r2, c2]: number[]) {
    const s = r1 === r2 ? 1 : 2;
    return grid[r1]?.at(c1) === 0 && grid[r2]?.at(c2) === 0 && (visited[r1][c1] | s) !== visited[r1][c1];
    }

    for (let step = 0, queue = [[0, 0, 0, 1]]; queue.length; step++) {
    const nextQueue = [];
    for (const [r1, c1, r2, c2] of queue) {
    if (r1 === n - 1 && r2 === n - 1 && c1 === n - 2 && c2 === n - 1) return step;

    const s = r1 === r2 ? 1 : 2;
    if ((visited[r1][c1] | s) === visited[r1][c1]) continue;

    visited[r1][c1] = visited[r1][c1] | s;

    // 水平:向右直走、向下平移
    // 垂直:向下直走、向右平移
    const p1 = [r1, c1 + 1, r2, c2 + 1], p2 = [r1 + 1, c1, r2 + 1, c2];
    if (validate(p1)) nextQueue.push(p1);
    if (validate(p2)) nextQueue.push(p2);

    // 旋转:必须满足4宫格为0
    if (!dirs.every(([dr, dc]) => grid[r1 + dr]?.at(c1 + dc) === 0)) continue;

    // 水平:顺时针旋转
    const p3 = [r1, c1, r2 + 1, c2 - 1];
    if (r1 === r2 && validate(p3)) nextQueue.push(p3);

    // 垂直:逆时针旋转
    const p4 = [r1, c1, r2 - 1, c2 + 1];
    if (c1 === c2 && validate(p4)) nextQueue.push(p4);
    }

    queue = nextQueue;
    }

    return -1;
    };

    4、复杂度

    • 时间复杂度:O(n2)O(n^2)
    • 空间复杂度:O(n2)O(n^2)

    5、执行结果

    image.png

    · 阅读需 3 分钟

    1、题干

    给定一个整数 n,即有向图中的节点数,其中节点标记为 0n - 1。图中的每条边为红色或者蓝色,并且可能存在自环或平行边。

    给定两个数组 redEdges 和 blueEdges,其中:

    • redEdges[i] = [ai, bi] 表示图中存在一条从节点 ai 到节点 bi 的红色有向边,
    • blueEdges[j] = [uj, vj] 表示图中存在一条从节点 uj 到节点 vj 的蓝色有向边。

    返回长度为 n 的数组 answer,其中 answer[X] 是从节点 0 到节点 X 的红色边和蓝色边交替出现的最短路径的长度。如果不存在这样的路径,那么 answer[x] = -1

     

    示例 1:

    输入:n = 3, red_edges = [[0,1],[1,2]], blue_edges = []
    输出:[0,1,-1]

    示例 2:

    输入:n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]
    输出:[0,1,-1]

     

    提示:

    • 1 <= n <= 100
    • 0 <= redEdges.length, blueEdges.length <= 400
    • redEdges[i].length == blueEdges[j].length == 2
    • 0 <= ai, bi, uj, vj < n

    2、思路

    整体思路分为 建表BFS 两步:

    • 建表:将所有邻接点关系存入二维矩阵,第一维下标表示出发点,第二维元素表示到达点,到达点使用正负数表示红蓝两种状态
    • BFS:广度优先搜索所有可能存在的红蓝交替路径,找出最短路径

    3、代码

    function shortestAlternatingPaths(n: number, redEdges: number[][], blueEdges: number[][]): number[] {
    const edges: Set<number>[] = new Array(n).fill(0).map(() => new Set());
    for (const [e0, e1] of redEdges) edges[e0].add(e1);
    for (const [e0, e1] of blueEdges) edges[e0].add(-e1);

    const ans = new Array(n).fill(Infinity);
    let nodes = edges[0], visited = new Set([0]);

    for (let depth = 1; nodes.size; depth++) {
    const nextNodes: Set<number> = new Set();

    for (const n of nodes) {
    if (visited.has(n)) continue;
    visited.add(n);

    const i = n < 0 ? -n : n;
    ans[i] = Math.min(ans[i], depth);

    for (const e of edges[i]) {
    if (Math.sign(n) !== Math.sign(e)) nextNodes.add(e);
    }
    }

    nodes = nextNodes;
    }

    return ans[0] = 0, ans.map(a => a === Infinity ? -1 : a);
    }

    4、复杂度

    • 时间复杂度:O(n)O(n)
    • 空间复杂度:O(n)O(n)

    5、执行结果

    image.png

    · 阅读需 5 分钟

    1、题干

    给定一个二维网格 grid ,其中:

    • '.' 代表一个空房间
    • '#' 代表一堵墙
    • '@' 是起点
    • 小写字母代表钥匙
    • 大写字母代表锁

    我们从起点开始出发,一次移动是指向四个基本方向之一行走一个单位空间。我们不能在网格外面行走,也无法穿过一堵墙。如果途经一个钥匙,我们就把它捡起来。除非我们手里有对应的钥匙,否则无法通过锁。

    假设 k 为 钥匙/锁 的个数,且满足 1 <= k <= 6,字母表中的前 k 个字母在网格中都有自己对应的一个小写和一个大写字母。换言之,每个锁有唯一对应的钥匙,每个钥匙也有唯一对应的锁。另外,代表钥匙和锁的字母互为大小写并按字母顺序排列。

    返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙,返回 -1 。

     

    示例 1:

    输入:grid = ["@.a..","###.#","b.A.B"]
    输出:8
    解释:目标是获得所有钥匙,而不是打开所有锁。

    示例 2:

    输入:grid = ["@..aA","..B#.","....b"]
    输出:6

    示例 3:

    输入: grid = ["@Aa"]
    输出: -1

     

    提示:

    • m == grid.length
    • n == grid[i].length
    • 1 <= m, n <= 30
    • grid[i][j] 只含有 '.''#''@''a'-'f' 以及 'A'-'F'
    • 钥匙的数目范围是 [1, 6] 
    • 每个钥匙都对应一个 不同 的字母
    • 每个钥匙正好打开一个对应的锁

    Problem: 864. 获取所有钥匙的最短路径

    2、思路

    写过最长的代码,心态崩了

    思路:

    • 回溯,对所有钥匙进行排列组合,得到所有路径(不校验路径是否连通)
    • 遍历所有路径,累计从起点经过所有钥匙需要的步数,结果取最小步数
    • 广搜计算两把钥匙之间的最短路径(需要校验路径是否连通)

    3、Code

    function shortestPathAllKeys(grid: string[]): number {
    const m = grid.length, n = grid[0].length;

    const M = 10007;
    const encode = (i: number, j: number) => i * M + j;
    const decode = (d: number) => [(d / M) >> 0, d % M];

    let start = 0;
    const keys: number[] = [];
    for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
    if (grid[i][j] === "@") start = encode(i, j);
    if (grid[i][j] >= "a" && grid[i][j] <= "f") keys.push(encode(i, j));
    }
    }

    // 寻找两把钥匙之间的最短路径
    function bfs(source: number, target: number, visited: Set<number>, foundKeys: Set<string>): number {
    let queue = [source];
    const [ti, tj] = decode(target);

    let step = 1;
    while (queue.length) {
    const nextQueue = new Set<number>();

    for (const q of queue) {
    if (visited.has(q)) continue;
    visited.add(q);

    const [qi, qj] = decode(q);
    const dirs = [[qi, qj + 1], [qi, qj - 1], [qi + 1, qj], [qi - 1, qj],];

    for (const [i, j] of dirs) {
    if (!grid[i] || !grid[i][j] || grid[i][j] === "#") continue;
    if (grid[i][j] >= "A" && grid[i][j] <= "F" && !foundKeys.has(grid[i][j].toLowerCase())) continue;
    if (i === ti && j === tj) return step;

    nextQueue.add(encode(i, j));
    }
    }

    step++;
    queue = [...nextQueue];
    }

    return 0;
    }

    // 遍历所有路径,累计从起点经过所有钥匙需要的步数,结果取最小步数
    let res = Infinity;
    function calcSteps(path: Set<number>) {
    let step = 0, source = start, foundKeys = new Set<string>();

    for (const p of path) {
    const st = bfs(source, p, new Set(), foundKeys);
    step += st;
    if (!st || step >= res) return;

    const [pi, pj] = decode(p);
    foundKeys.add(grid[pi][pj]);
    source = p;
    }

    if (step < res) res = step;
    }

    // 对钥匙进行排列组合
    function dfs(path: Set<number>) {
    for (const k of keys) {
    if (path.has(k)) continue;
    path.add(k);
    dfs(path);
    if (path.size === keys.length) calcSteps(path);
    path.delete(k);
    }
    }

    dfs(new Set());

    return res === Infinity ? -1 : res;
    }

    4、复杂度

    • 时间复杂度:O(k!mn)O(k!*mn)
    • 空间复杂度:O(mn)O(mn)

    5、执行结果

    image.png

    · 阅读需 3 分钟

    1、题干

    给你一个由若干括号和字母组成的字符串 s ,删除最小数量的无效括号,使得输入的字符串有效。

    返回所有可能的结果。答案可以按 任意顺序 返回。

     

    示例 1:

    输入:s = "()())()"
    输出:["(())()","()()()"]

    示例 2:

    输入:s = "(a)())()"
    输出:["(a())()","(a)()()"]

    示例 3:

    输入:s = ")("
    输出:[""]

     

    提示:

    • 1 <= s.length <= 25
    • s 由小写英文字母以及括号 '('')' 组成
    • s 中至多含 20 个括号

    深圳阿里Lazada笔试题T4,30min钟4道题,这道题没时间写

    1d58c1fc375efb4172fc38ed625cfb94.gif


    2、解题思路

    回溯+剪枝枚举所有可行的情况,遍历过程中判断合法子串只需要判断已选子串长度不为0且左括号被消耗完即 lc=0,详细逻辑见注释


    3、代码

    var removeInvalidParentheses = function (s) {
    let res = [''];

    // 初始状态:字符串下标i,已选字符数组chars,左括号数量lc
    function backtrace(i, chars, lc) {
    // 合法子串,比较长度并填入最终结果
    if (!lc && chars.length && chars.length > res[0].length) res = [chars.join('')];
    else if (!lc && chars.length && chars.length === res[0].length) res.push(chars.join(''));

    // 下标越界,遍历结束
    if (i >= s.length - 1) return;

    // 遍历所有待选字符
    for (let j = i + 1; j < s.length; j++) {
    const c = s[j];
    // 剪枝:存在无法配对的右括号
    if (c === ')' && !lc) continue;
    // 剪枝:1、左括号比剩余子串更长;2、已选子串长度加上未遍历子串长度还是小于结果子串的长度
    if (lc > s.length - j || chars.length + s.length - j < res[0].length) break;

    // 选择当前字符
    chars.push(c);
    // 递归搜索
    backtrace(j, chars, c === '(' ? lc + 1 : (c === ')' ? lc - 1 : lc));
    // 撤销选择
    chars.pop();
    }
    }

    // 初始状态:字符串下标i为-1,已选字符数组chars为空数组,左括号数量lc为0
    backtrace(-1, [], 0);

    return [...new Set(res)];
    };

    4、执行结果

    image.png

    · 阅读需 5 分钟

    1、题干

    树可以看成是一个连通且 无环 的 无向 图。

    给定往一棵 n 个节点 (节点值 1~n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1n 中间,且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ,edges[i] = [ai, bi] 表示图中在 aibi 之间存在一条边。

    请找出一条可以删去的边,删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案,则返回数组 edges 中最后出现的边。

     

    示例 1:

    输入: edges = [[1,2],[1,3],[2,3]]
    输出: [2,3]

    示例 2:

    输入: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
    输出: [1,4]

     

    提示:

    • n == edges.length
    • 3 <= n <= 1000
    • edges[i].length == 2
    • 1 <= ai < bi <= edges.length
    • ai != bi
    • edges 中无重复元素
    • 给定的图是连通的 

     

    注意:本题与主站 684 题相同: https://leetcode-cn.com/problems/redundant-connection/

    并查集还没学会,只能先用树和图的思想解题

    image.png


    2、解题思路

    在树的概念中,叶子结点是指没有子结点的结点,叶子节点只跟父节点存在关联,即只有1条边。如果某个节点下只有叶子节点,把该节点下的所有叶子节点都移除掉之后它自己就变成了叶子节点。如果循环往复地移除树的所有叶子节点,最终这棵树的节点数会变为0

    如果按题目意思在树中添加一条边,这棵树会变成一个有环图,而在移除所有叶子节点的操作中,环上的所有节点都不会被移除,本题就是利用这个结论解题。


    总体思路 :循环往复地移除树上所有的叶子节点,直到不存在叶子节点,最后遍历找到环中最后出现的边。


    大体步骤

    • 先用矩阵建立节点关联关系,记为 matrix
      • matrix 是一维数组,下标表示节点值
      • matrix 中的元素是哈希集合,集合中包含与当前节点关联的所有节点
    • 遍历 matrix 并把当前节点加入队列 queue 中,进行叶子节点的判断与移除
      • 若该节点是叶子节点,则双向移除该节点与父节点的关联关系,同时把父节点加入队列 queue 中进行下一轮处理
      • 若该节点不是叶子节点则跳过
    • 最后遍历二维数组 edges 并在 matrix 中查找出处于环上且序号最大的边

    3、代码

    var findRedundantConnection = function (edges) {
    const n = edges.length, matrix = new Array(n + 1).fill(0);

    for (const [i, j] of edges) {
    !matrix[i] ? (matrix[i] = new Set([j])) : matrix[i].add(j);
    !matrix[j] ? (matrix[j] = new Set([i])) : matrix[j].add(i);
    }

    for (let k = 1; k <= n; k++) {
    const queue = [k];

    for (const i of queue) {
    if (matrix[i].size !== 1) continue;

    const j = matrix[i].keys().next().value;
    matrix[i].delete(j), matrix[j].delete(i);
    queue.push(j);
    }
    }

    return edges.reduce((a, [i, j]) => (matrix[i].size > 1 && matrix[j].size > 1 ? [i, j] : a), null);
    };

    4、复杂度

    • 时间复杂度:O(nlogn)O(nlogn),复杂度比较高的代码在双层循环剪叶子那一段,外层循环 nn 次,内层循环最多为树的高度 lognlogn
    • 空间复杂度:O(n)O(n)

    5、执行结果

    • 执行用时: 68 ms
    • 内存消耗: 42.1 MB

    image.png