lthero

LeetCodeCampsDay56图论part06 无向图&有向图变成无向树&有向树问题 108.冗余的边 题目描述 有一个图，它是一棵树，他是拥有 n 个节点（节点编号1到n）和 n - 1 条边的连通无环无向图，例如如图： 现在在这棵树上的基础上，添加一条边（依然是n个节点，但有n条边），使这个图变成了有环图，如图： 先请你找出冗余边，删除后，使该图可以重新变成一棵树。 输入描述 第一行包含一个整数 N，表示图的节点个数和边的个数。 后续 N 行，每行包含两个整数 s 和 t，表示图中 s 和 t 之间有一条边。 输出描述 输出一条可以删除的边。如果有多个答案，请删除标准输入中最后出现的那条边。 输入示例 123431 22 31 3 输出示例 11 3 提示信息 图中的 1 2，2 3，1 3 等三条边在删除后都能使原图变为一棵合法的树。但是 1 3 由于是标准输出里最后出现的那条边，所以输出结果为 1 3 数据范围： 1 <= N <= 1000. 并查集思路 如何判断哪条边是多余的？ 对输入的边进行遍历，如果这边的两个节点已经在并查集里 ...

LeetCodeCampsDay55图论part05(并查集) 包含并查集基础与一个基础题目 并查集理论基础 背景 首先要知道并查集可以解决什么问题呢？ 并查集常用来解决连通性问题。 大白话就是当我们需要判断两个元素是否在同一个集合里的时候，我们就要想到用并查集。 并查集主要有两个功能： 将两个元素添加到一个集合中。 判断两个元素在不在同一个集合 接下来围绕并查集的这两个功能来展开讲解。 原理讲解 从代码层面，我们如何将两个元素添加到同一个集合中呢。 此时有录友会想到：可以把他放到同一个数组里或者set 或者 map 中，这样就表述两个元素在同一个集合。 那么问题来了，对这些元素分门别类，可不止一个集合，可能是很多集合，成百上千，那么要定义这么多个数组吗？ 有录友想，那可以定义一个二维数组。 但如果我们要判断两个元素是否在同一个集合里的时候 我们又能怎么办？ 只能把而二维数组都遍历一遍。 而且每当想添加一个元素到某集合的时候，依然需要把把二维数组都遍历一遍，才知道要放在哪个集合里。 这仅仅是一个粗略的思路，如果沿着这个思路去实现代码，非常复杂，因为管理集合还需要很多逻辑。 那么 ...

LeetCodeCampsDay53图论part04 继续使用深度/广度优先解决图的问题 其中105是有向图问题 110.字符串接龙 https://kamacoder.com/problempage.php?pid=1183 题目描述 字典 strList 中从字符串 beginStr 和 endStr 的转换序列是一个按下述规格形成的序列： 序列中第一个字符串是 beginStr。 序列中最后一个字符串是 endStr。 每次转换只能改变一个字符。 转换过程中的中间字符串必须是字典 strList 中的字符串，且strList里的每个字符串只用使用一次。 给你两个字符串 beginStr 和 endStr 和一个字典 strList，找到从 beginStr 到 endStr 的最短转换序列中的字符串数目。如果不存在这样的转换序列，返回 0。 输入描述 第一行包含一个整数 N，表示字典 strList 中的字符串数量。 第二行包含两个字符串，用空格隔开，分别代表 beginStr 和 endStr。 后续 N 行，每行一个字符串，代表 strList 中的字符串。 输出描述 ...

LeetCodeCampsDay52图论part03 101.孤岛的总面积 题目描述 给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域，且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。 现在你需要计算所有孤岛的总面积，岛屿面积的计算方式为组成岛屿的陆地的总数。 输入描述 第一行包含两个整数 N, M，表示矩阵的行数和列数。之后 N 行，每行包含 M 个数字，数字为 1 或者 0。 输出描述 输出一个整数，表示所有孤岛的总面积，如果不存在孤岛，则输出 0。 输入示例 123454 51 1 0 0 01 1 0 0 00 0 1 0 00 0 0 1 1 输出示例 11 提示信息 在矩阵中心部分的岛屿，因为没有任何一个单元格接触到矩阵边缘，所以该岛屿属于孤岛，总面积为 1。 数据范围： 1 <= M, N <= 50。 思路0 题目要求没有任何一个单元格接触到矩阵边缘，那：从四个边缘出发，将与之相邻的格子都变成海洋（设置为0），随后再统计保留下来为陆地的格子即可 如图，在遍历地图周围四个边，靠 ...

Hysteria2客户端使用教程 本文是在linux服务器上（作为客户端！）使用hysteria2代理，不是在服务器上搭建hysteria2！！！！ 客户端安装 官方教程：https://v2.hysteria.network/zh/docs/getting-started/Installation/ 但！由于需要用本方法的机器无法直接用代理，所以安装hysteria2最好先将hy2可执行文件下载到电脑上，再上传到服务器上，再使用本地安装 下载可执行文件 文件 架构 注意 hysteria-linux-amd64 x86-64 hysteria-linux-amd64-avx x86-64 需要 AVX 指令集 hysteria-linux-386 x86 hysteria-linux-arm ARMv7 hysteria-linux-armv5 ARMv5 hysteria-linux-arm64 ARM64 hysteria-linux-s390x s390x hysteria-linux-mipsle MIPS 小 ...

LeetCodeCampsDay51图论part02 包含深度优先搜索和广度优先搜索的基础代码 99. 岛屿数量 https://kamacoder.com/problempage.php?pid=1171 题目描述 给定一个由 1（陆地）和 0（水）组成的矩阵，你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。 输入描述 第一行包含两个整数 N, M，表示矩阵的行数和列数。 后续 N 行，每行包含 M 个数字，数字为 1 或者 0。 输出描述 输出一个整数，表示岛屿的数量。如果不存在岛屿，则输出 0。 输入示例 123454 51 1 0 0 01 1 0 0 00 0 1 0 00 0 0 1 1 输出示例 13 提示信息 根据测试案例中所展示，岛屿数量共有 3 个，所以输出 3。 数据范围： 1 <= N, M <= 50 图论思路 注意题目中每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 也就是说斜角度链接是不算了， 例如示例二，是三个岛屿，如图： 这道题题目是 DFS，BFS，并 ...

LeetCodeCampsDay50图论part01 图论基础 图的基本概念 二维坐标中，两点可以连成线，多个点连成的线就构成了图。 当然图也可以就一个节点，甚至没有节点（空图） 图的种类 整体上一般分为 有向图 和 无向图。 有向图是指 图中边是有方向的： 无向图是指 图中边没有方向： 加权有向图，就是图中边是有权值的，例如： 加权无向图也是同理。 度 无向图中有几条边连接该节点，该节点就有几度。 例如，该无向图中，节点4的度为5，节点6的度为3。 在有向图中，每个节点有出度和入度。 出度：从该节点出发的边的个数。 入度：指向该节点边的个数。 例如，该有向图中，节点3的入度为2，出度为1，节点1的入度为0，出度为2。 连通性 在图中表示节点的连通情况，我们称之为连通性。 连通图 在无向图中，任何两个节点都是可以到达的，我们称之为连通图 ，如图： 如果有节点不能到达其他节点，则为非连通图，如图： 节点1 不能到达节点4。 强连通图 在有向图中，任何两个节点是可以相互到达的，我们称之为 强连通图。 这里有录友可能想，这和无向图中的连通图有什么区别，不是一样 ...

LeetCodeCampsDay49单调栈part02 42. 接雨水 https://leetcode.cn/problems/trapping-rain-water/ 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 示例 1： 123输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]输出：6解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 示例 2： 12输入：height = [4,2,0,3,2,5]输出：9 提示： n == height.length 1 <= n <= 2 * 104 0 <= height[i] <= 105 单调栈思路 和使用双指针按列求解不同，使用单调栈需要按行求解 首先单调栈是按照行方向来计算雨水，如图： 知道这一点，后面的就可以理解了。 使用单调栈内元素的顺序 从大到小还是从小到大呢？ 从栈头（元素从栈头弹出）到栈底的顺序应该是从 ...

LeetCodeCampsDay48单调栈part01 初识单调栈 单调栈 什么时候用单调栈呢？ 通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。时间复杂度为O(n)。 如果暴力求解，比如两层for循环，时间复杂度是O(n^2) 那么单调栈的原理是什么呢？为什么时间复杂度是O(n)就可以找到每一个元素的右边第一个比它大的元素位置呢？ 单调栈的本质是空间换时间，因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素，优点是整个数组只需要遍历一次。 更直白来说，就是用一个栈来记录我们遍历过的元素，因为我们遍历数组的时候，我们不知道之前都遍历了哪些元素，以至于遍历一个元素找不到是不是之前遍历过一个更小的，所以我们需要用一个容器（这里用单调栈）来记录我们遍历过的元素。 在使用单调栈的时候首先要明确如下几点： 单调栈里存放的元素是什么？ 单调栈里只需要存放元素的下标i就可以了，如果需要使用对应的元素，直接T[i]就可以获取。 单调栈里元素是递增呢？ 还是递减呢？ 注意以下讲解中，顺序的描述为 从栈头到栈 ...

LeetCodeCampsDay46动态规划part13 使用dp解决回文串和回文序列问题 647. 回文子串 https://leetcode.cn/problems/palindromic-substrings/ 给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。 示例 1： 123输入：s = "abc"输出：3解释：三个回文子串: "a", "b", "c" 示例 2： 123输入：s = "aaa"输出：6解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa" 提示： 1 <= s.length <= 1000 s 由小写英文字母组成 普通思路 本题和前面写过的26. 单词拆分有点像 需要将s拆分 ...