分别用 vector 和 unordered_map 实现并查集
并查集是一种基础数据结构,主要解决连通性问题。这里不对并查集的概念做详细的解释,主要是介绍并查集的两种实现。 vector 实现 参考《算法》 第四版中…
|
759
|
|
Dijkstra 算法——求解最短路径问题
迪杰斯特拉算法(Dijkstra's algorithm)是一种用于解决单源最短路径问题的贪心算法。它可以找到从一个起始顶点到其他所有顶点的最短路径,并且适用于边的权重非负的图…
|
953
|
|
LeetCode | 516.最长回文子序列
给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。 子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。 示例 1: 输入:s = "b…
|
916
|
|
LeetCode | 473.火柴拼正方形
你将得到一个整数数组 matchsticks ,其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒,但你可以把它们连在一起…
|
979
|
|
LeetCode | 416.分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。 示例 1: 输入:nums = [1,5,11,5] 输出:true 解释:数…
|
963
|
|
LeetCode | 218.天际线问题
城市的天际线是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。给你所有建筑物的位置和高度,请返回由这些建筑物形成的天际线 。 每个建筑物的几何信息由数组 buildings …
|
1,015
|
|
LeetCode | 62.不同路径
一个机器人位于一个 m x n 网格的左上角(坐标 (0, 0))。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(坐标 (m - 1, n - 1))。 问总共有多少条不同的路径?…
|
1,018
|
|
LeetCode | 22.括号生成
数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。 示例 1: 输入:n = 3 输出:["((()))","(()())&q…
|
1,139
|
|
LeetCode | 5.最长回文子串
给你一个字符串 s,找到 s 中最长的回文子串。 如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。 示例 1: 输入:s = "babad" 输出:"bab&…
|
1,044
|
|
LeetCode | 113.路径总和 Ⅱ
给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 叶子节点 是指没有子节点的节点。 示例 1: 输入:root = […
|
1,016
|
|
LeetCode | 109.有序链表转换二叉搜索树
给定一个单链表的头节点 head ,其中的元素 按升序排序 ,将其转换为高度平衡的二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。 示例 1: 输入…
|
922
|
|
LeetCode | 105.从前序遍历和中序遍历构造二叉树
给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。 示例 1: 输入: preo…
|
970
|
|
剑指 Offer 68 – II.二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深…
|
997
|
|
LeetCode | 501.二叉搜索树中的众数
给你一个含重复值的二叉搜索树(BST)的根节点 root ,找出并返回 BST 中的所有 众数(即,出现频率最高的元素)。 如果树中有不止一个众数,可以按 任意顺序 返回。 假定 BST 满足如下定义…
|
881
|
|
LeetCode | 145.二叉树的后序遍历
给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历 。 示例 1: 1 \ 2 / 3 输入:root = [1,null,2,3] 输出:[3,2,1] 示例 2: 输入:root = […
|
892
|
|
LeetCode | 144 二叉树的前序遍历
给你二叉树的根节点 root ,返回它节点值的 前序 遍历。 示例 1: 1 \ 2 / 3 输入:root = [1,null,2,3] 输出:[1,2,3] 示例 2: 输入:root = [] …
|
850
|
|
LeetCode | 94.二叉树的中序遍历
给定一个二叉树的根节点 root ,返回它的 中序 遍历 。 示例 1: 输入:root = [1,null,2,3] 输出:[1,3,2] 示例 2: 输入:root = [] 输出:[] 示例 3…
|
897
|
|
LeetCode | 133.克隆图
给你无向 连通 图中一个节点的引用,请你返回该图的 深拷贝(克隆)。 图中的每个节点都包含它的值 val(int) 和其邻居的列表(list[Node])。 class Node { public: …
|
1,077
|
|
LeetCode | 2367.算术三元组的数目
给你一个下标从 0 开始、严格递增 的整数数组 nums 和一个正整数 diff 。如果满足下述全部条件,则三元组 (i, j, k) 就是一个 算术三元组 : i < j < k , n…
|
828
|
|
经典图论问题:传递信息
小朋友 A 在和 ta 的小伙伴们玩传信息游戏,游戏规则如下: 有 n 名玩家,所有玩家编号分别为 0 ~ n - 1,其中小朋友 A 的编号为 0 每个玩家都有固定的若干个可传信息的其他玩家(也可能…
|
947
|
|