byu_rself

LC.P41[缺失的第一个正数] 题目描述给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。 示例1 输入：nums = [1,2,0]输出：3 示例2 输入：nums = [3,4,-1,1]输出：2 示例3 输入：nums = [7,8,9,11,12]输出：1 提示： 1 <= nums.length <= 5 * 105 -231 <= nums[i] <= 231 - 1 方法一：哈希表12345678910class Solution { public int firstMissingPositive(int[] nums) { Set<Integer> set = new HashSet<>(); for (int num : nums) set.add(num); for (int i = 1; i <= nu ...

LC.P1092[最短公共超序列] 题目描述给出两个字符串 str1 和 str2，返回同时以 str1 和 str2 作为子序列的最短字符串。如果答案不止一个，则可以返回满足条件的任意一个答案。 （如果从字符串 T 中删除一些字符（也可能不删除，并且选出的这些字符可以位于 T 中的 任意位置），可以得到字符串 S，那么 S 就是 T 的子序列） 示例 输入：str1 = “abac”, str2 = “cab”输出：”cabac”解释：str1 = “abac” 是 “cabac” 的一个子串，因为我们可以删去 “cabac” 的第一个 “c”得到 “abac”。str2 = “cab” 是 “cabac” 的一个子串，因为我们可以删去 “cabac” 末尾的 “ac” 得到 “cab”。最终我们给出的答案是满足上述属性的最短字符串。 提示： 1 <= str1.length, str2.length <= 1000 str1 和 str2 都由小写英文字母组成。 方法一：动态规划先用动态规划求出两个字符串的最长公共子序列， ...

LC.P686[重复叠加字符串匹配] 题目描述给定两个字符串 a 和 b，寻找重复叠加字符串 a 的最小次数，使得字符串 b 成为叠加后的字符串 a 的子串，如果不存在则返回 -1。 注意：字符串 "abc" 重复叠加 0 次是 ""，重复叠加 1 次是 "abc"，重复叠加 2 次是 "abcabc"。 示例1 输入：a = “abcd”, b = “cdabcdab”输出：3解释：a 重复叠加三遍后为 “abcdabcdabcd”, 此时 b 是其子串。 示例2 输入：a = “a”, b = “aa”输出：2 提示： 1 <= a.length <= 104 1 <= b.length <= 104 a 和 b 由小写英文字母组成 方法一：KMP12345678910111213141516171819202122232425262728293031323334353637383940414243class Solution ...

LC.P28[找出字符串中第一个匹配项的下标] 题目描述给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。 示例1 输入：haystack = “sadbutsad”, needle = “sad”输出：0解释：”sad” 在下标 0 和 6 处匹配。第一个匹配项的下标是 0 ，所以返回 0 。 示例2 输入：haystack = “leetcode”, needle = “leeto”输出：-1解释：”leeto” 没有在 “leetcode” 中出现，所以返回 -1 。 提示： 1 <= haystack.length, needle.length <= 104 haystack 和 needle 仅由小写英文字符组成 方法一：暴力12345678910111213141516class Solution { public in ...

LC.P1638[统计只差一个字符的子串数目] 题目描述给你两个字符串 s 和 t ，请你找出 s 中的非空子串的数目，这些子串满足替换 一个不同字符 以后，是 t 串的子串。换言之，请你找到 s 和 t 串中 恰好 只有一个字符不同的子字符串对的数目。 比方说， "computer" and "computation" 只有一个字符不同： 'e'/'a' ，所以这一对子字符串会给答案加 1 。 请你返回满足上述条件的不同子字符串对数目。 一个 子字符串 是一个字符串中连续的字符。 示例1 输入：s = “aba”, t = “baba”输出：6解释：以下为只相差 1 个字符的 s 和 t 串的子字符串对：(“aba”, “baba”)(“aba”, “baba”)(“aba”, “baba”)(“aba”, “baba”)(“aba”, “baba”)(“aba”, “baba”)加粗部分分别表示 s 和 t 串选出来的子字符串。 示例2 输入：s = “ab”, t ...

LC.P310[最小高度树] 题目描述树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。 给你一棵包含 n个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。 可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树 。 请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。 树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。 示例1 输入：n = 4, edges = [[1,0],[1,2],[1,3]]输出：[1]解释：如图所示，当根是标签为 1 的节点时，树的高度是 1 ，这是唯一的最小高度树。 示例2 输入：n = 6, edges = [[3,0],[3,1],[3,2],[3, ...

LC.P2395[和相等的子数组] 题目描述给你一个下标从 0 开始的整数数组 nums ，判断是否存在 两个 长度为 2 的子数组且它们的 和 相等。注意，这两个子数组起始位置的下标必须 不相同 。 如果这样的子数组存在，请返回 true，否则返回 false 。 子数组 是一个数组中一段连续非空的元素组成的序列。 示例1 输入：nums = [4,2,4]输出：true解释：元素为 [4,2] 和 [2,4] 的子数组有相同的和 6 。 示例2 输入：nums = [1,2,3,4,5]输出：false解释：没有长度为 2 的两个子数组和相等。 示例3 输入：nums = [0,0,0]输出：true解释：子数组 [nums[0],nums[1]] 和 [nums[1],nums[2]] 的和相等，都为 0 。注意即使子数组的元素相同，这两个子数组也视为不相同的子数组，因为它们在原数组中的起始位置不同。 提示： 2 <= nums.length <= 1000 -109 <= nums[i] <= 109 方法一 ...

LC.P987[二叉树的垂序遍历] 题目描述给你二叉树的根结点 root，请你设计算法计算二叉树的 垂序遍历 序列。 对位于 (row, col) 的每个结点而言，其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1) 。树的根结点位于 (0, 0) 。 二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束，按列索引每一列上的所有结点，形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点，则按结点的值从小到大进行排序。 返回二叉树的 垂序遍历 序列。 示例1 输入：root = [3,9,20,null,null,15,7]输出：[[9],[3,15],[20],[7]]解释：列 -1 ：只有结点 9 在此列中。列 0 ：只有结点 3 和 15 在此列中，按从上到下顺序。列 1 ：只有结点 20 在此列中。列 2 ：只有结点 7 在此列中。 示例2 输入：root = [1,2,3,4,5,6,7]输出：[[4],[2],[1,5,6],[3],[7]]解释：列 -2 ：只有结点 4 在此列中 ...

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，需要将这棵子树移除，返回空。有任一条件不满足时 ...