byu_rself

LC.P1641[统计字典序元音字符串的数目] 题目描述给你一个整数 n，请返回长度为n 、仅由元音 (a, e, i, o, u) 组成且按 字典序排列 的字符串数量。 字符串 s 按 字典序排列 需要满足：对于所有有效的 i，s[i] 在字母表中的位置总是与 s[i+1] 相同或在 s[i+1] 之前。 示例 1： 输入：n = 1输出：5解释：仅由元音组成的 5 个字典序字符串为 [“a”,”e”,”i”,”o”,”u”] 示例 2： 输入：n = 2输出：15解释：仅由元音组成的 15 个字典序字符串为[“aa”,”ae”,”ai”,”ao”,”au”,”ee”,”ei”,”eo”,”eu”,”ii”,”io”,”iu”,”oo”,”ou”,”uu”]注意，”ea” 不是符合题意的字符串，因为 ‘e’ 在字母表中的位置比 ‘a’ 靠后 示例 3： 输入：n = 33输出：66045 提示： 1 <= n <= 50 方法一：记忆化搜索12345678910111213141516171819202122class Sol ...

LC.P442[数组中重复的数据] 题目描述给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数，并以数组形式返回。 你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。 示例1 输入：nums = [4,3,2,7,8,2,3,1]输出：[2,3] 示例 2： 输入：nums = [1,1,2]输出：[1] 示例 3： 输入：nums = [1]输出：[] 提示： n == nums.length 1 <= n <= 105 1 <= nums[i] <= n nums 中的每个元素出现 一次 或 两次 方法一：哈希表1234567891011121314class Solution { public List<Integer> findDuplicates(int[] nums) { Set<Integer> s ...

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 在此列中 ...