byu_rself

LC.P1574[删除最短的子数组使剩余数组有序] 题目描述给你一个整数数组 arr ，请你删除一个子数组（可以为空），使得 arr 中剩下的元素是 非递减 的。 一个子数组指的是原数组中连续的一个子序列。 请你返回满足题目要求的最短子数组的长度。 示例1 输入：arr = [1,2,3,10,4,2,3,5]输出：3解释：我们需要删除的最短子数组是 [10,4,2] ，长度为 3 。剩余元素形成非递减数组 [1,2,3,3,5] 。另一个正确的解为删除子数组 [3,10,4] 。 示例2 输入：arr = [5,4,3,2,1]输出：4解释：由于数组是严格递减的，我们只能保留一个元素。所以我们需要删除长度为 4 的子数组，要么删除 [5,4,3,2]，要么删除 [4,3,2,1]。 示例3 输入：arr = [1,2,3]输出：0解释：数组已经是非递减的了，我们不需要删除任何元素。 示例4 输入：arr = [1]输出：0 提示： 1 <= arr.length <= 10^5 0 <= arr[i] < ...

LC.P814[二叉树剪枝] 题目描述给你二叉树的根结点 root ，此外树的每个结点的值要么是 0 ，要么是 1 。 返回移除了所有不包含 1 的子树的原二叉树。 节点 node 的子树为 node 本身加上所有 node 的后代。 示例1 输入：root = [1,null,0,0,1]输出：[1,null,0,null,1]解释：只有红色节点满足条件“所有不包含 1 的子树”。 右图为返回的答案。 示例2 输入：root = [1,0,1,0,0,0,1]输出：[1,null,1,null,1] 示例3 输入：root = [1,1,0,1,1,0,1,0]输出：[1,1,0,1,1,null,1] 提示： 树中节点的数目在范围 [1, 200] 内 Node.val 为 0 或 1 方法一：递归首先确定边界条件，当输入为空时，返回空。然后对左子树和右子树分别递归，递归完成后，当这三个条件：左子树为空，右子树为空，当前节点的值为0同时满足时，才表示以当前节点为根的原二叉树的所有节点都为0，需要将这棵子树移除，返回空。有任一条件不满足时 ...

LC.P654[最大二叉树] 题目描述给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建: 创建一个根节点，其值为 nums 中的最大值。 递归地在最大值 左边 的 子数组前缀上 构建左子树。 递归地在最大值 右边 的 子数组后缀上 构建右子树。 返回 nums 构建的最大二叉树 。 示例1 输入：nums = [3,2,1,6,0,5]输出：[6,3,5,null,2,0,null,null,1]解释：递归调用如下所示： [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。 [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。 空数组，无子节点。 [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。 空数组，无子节点。 只有一个元素，所以子节点是一个值为 1 的节点。 [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。 只有一个元素，所以子节点是一个值为 0 的节点。 空数组，无子节点。 ...

LC.P1032[字符流]困难 题目描述设计一个算法：接收一个字符流，并检查这些字符的后缀是否是字符串数组 words 中的一个字符串。 例如，words = ["abc", "xyz"] 且字符流中逐个依次加入 4 个字符 'a'、'x'、'y' 和 'z' ，你所设计的算法应当可以检测到 "axyz" 的后缀 "xyz" 与 words 中的字符串 "xyz" 匹配。 按下述要求实现 StreamChecker 类： StreamChecker(String[] words) ：构造函数，用字符串数组 words 初始化数据结构。 boolean query(char letter)：从字符流中接收一个新字符，如果字符流中的任一非空后缀能匹配 words 中的某一字符串，返回 true ；否则，返回 false。 示例 输入：[“StreamChecker”, “query”, “query”, “query”, ...

LC.P297[二叉树的序列化与反序列化] 题目描述序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。 请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。 提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。 示例1 输入：root = [1,2,3,null,null,4,5]输出：[1,2,3,null,null,4,5] 示例2 输入：root = []输出：[] 提示： 树中结点数在范围 [0, 104] 内 -1000 <= Node.val <= 1000 方法一：BFS1234567891011121314151617181920212223242526 ...

LC.P1630[等差子数组] 题目描述如果一个数列由至少两个元素组成，且每两个连续元素之间的差值都相同，那么这个序列就是 等差数列 。更正式地，数列 s 是等差数列，只需要满足：对于每个有效的 i ， s[i+1] - s[i] == s[1] - s[0] 都成立。 例如，下面这些都是 等差数列 ： 1, 3, 5, 7, 97, 7, 7, 73, -1, -5, -9 下面的数列 不是等差数列 ： 1, 1, 2, 5, 7 给你一个由 n 个整数组成的数组 nums，和两个由 m 个整数组成的数组 l 和 r，后两个数组表示 m 组范围查询，其中第 i 个查询对应范围 [l[i], r[i]] 。所有数组的下标都是 从 0 开始 的。 返回 boolean 元素构成的答案列表 answer 。如果子数组 nums[l[i]], nums[l[i]+1], ... , nums[r[i]] 可以 重新排列 形成 等差数列 ，answer[i] 的值就是 true；否则answer[i] 的值就是 false 。 示例1 输入：nums = [4,6,5,9, ...

LC.P952[按公因数计算最大组件大小] 题目描述给定一个由不同正整数的组成的非空数组nums，考虑下面的图： 有nums.length个节点，按从nums[0]到nums[nums.length - 1]标记； 只有当nums[i]和nums[j]共用一个大于 1 的公因数时，nums[i]和nums[j]之间才有一条边。 返回图中最大连通组件的大小 。 示例1 输入：nums = [4,6,15,35]输出：4 示例2 输入：nums = [20,50,9,63]输出：2 示例3 输入：nums = [2,3,6,7,4,12,21,39]输出：8 提示： 1 <= nums.length <= 2 * 104 1 <= nums[i] <= 105 nums 中所有值都 不同 思路由题意，如果$nums[i]$和$nums[j]$存在边，则至少会被同一个质因数所映射。 利用并查集维护联通块数量，用哈希表维护映射关系。 映射关系为：<质因数，下标$i$> 12345678910111213141 ...

LC.P1626[无矛盾的最佳球队] 题目描述假设你是球队的经理。对于即将到来的锦标赛，你想组合一支总体得分最高的球队。球队的得分是球队中所有球员的分数总和 。 然而，球队中的矛盾会限制球员的发挥，所以必须选出一支没有矛盾的球队。如果一名年龄较小球员的分数严格大于一名年龄较大的球员，则存在矛盾。同龄球员之间不会发生矛盾。 给你两个列表scores和ages，其中每组scores[i]和ages[i]表示第i名球员的分数和年龄。请你返回所有可能的无矛盾球队中得分最高那支的分数 。 示例1 输入：scores = [1,3,5,10,15], ages = [1,2,3,4,5]输出：34解释：你可以选中所有球员。 示例2 输入：scores = [4,5,6,5], ages = [2,1,2,1]输出：16解释：最佳的选择是后 3 名球员。注意，你可以选中多个同龄球员。 示例3 输入：scores = [1,2,3,5], ages = [8,9,10,1]输出：6解释：最佳的选择是前 3 名球员。 提示： 1 ...

LC.P827[最大人工岛][困难] 题目描述给你一个大小为 n x n 二进制矩阵 grid 。最多只能将一格0变成1。 返回执行此操作后，grid中最大的岛屿面积是多少？ 岛屿由一组上、下、左、右四个方向相连的1形成。 示例1 输入: grid = [[1, 0], [0, 1]]输出: 3解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。 示例2 输入: grid = [[1, 1], [1, 0]]输出: 4解释: 将一格0变成1，岛屿的面积扩大为 4。 示例3 输入: grid = [[1, 1], [1, 1]]输出: 4解释: 没有0可以让我们变成1，面积依然为 4。 提示： n == grid.length n == grid[i].length 1 <= n <= 500 grid[i][j] 为 0 或 1 思路第一次遍历grid数组，使用并查集将相邻的1归到同一个集合中，并统计每个岛屿的面积，由size数组记录。 再次遍历grid，对于每个0，统计与该点相邻的四个点所在的岛屿，累加去重后的岛屿 ...

快速排序模板123456789101112131415161718192021222324252627#include <iostream>using namespace std;int n;const int N = 1e6 + 10;int q[N];void quick_sort(int q[], int l, int r) { if (l >= r) return; int x = q[l + r >> 1], i = l - 1, j = r + 1; while (i < j) { do i++; while (q[i] < x); do j--; while (q[j] > x); if (i < j) swap(q[i], q[j]); } quick_sort(q, l, j); quick_sort(q, j + 1, r);}int main() { scanf("%d", &n); for (int i = 0; i < ...