算法

简化路径题目71. 简化路径 给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为 更加简洁的规范路径。 在 Unix 风格的文件系统中规则如下： 一个点 '.' 表示当前目录本身。 此外，两个点 '..' 表示将目录切换到上一级（指向父目录）。 任意多个连续的斜杠（即，'//' 或 '///'）都被视为单个斜杠 '/'。 任何其他格式的点（例如，'...' 或 '....'）均被视为有效的文件/目录名称。 返回的 简化路径 必须遵循下述格式： 始终以斜杠 '/' 开头。 两个目录名之间必须只有一个斜杠 '/' 。 最后一个目录名（如果存在）不能 以 '/' 结尾。 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。 返回简化后得到的 规范路径 。 示例...

有效的括号题目20. 有效的括号 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。 有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号。 示例 1： 输入：s = “()” 输出：true 示例 2： 输入：s = “()[]{}” 输出：true 示例 3： 输入：s = “(]” 输出：false 示例 4： 输入：s = “([])” 输出：true 提示： 1 <= s.length <= 104 s 仅由括号 '()[]{}' 组成 题解本体要注意一点，按照正确的顺序😭😭😭😭 12345678910111213141516public boolean isValid(String s) { ...

合并区间题目56. 合并区间 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。 示例 1： 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]输出：[[1,6],[8,10],[15,18]]解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 示例 2： 输入：intervals = [[1,4],[4,5]]输出：[[1,5]]解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。 提示： 1 <= intervals.length <= 104 intervals[i].length == 2 0 <= starti <= endi <= 104 题解题解一（排序法）123456789101112131415public int[][] merge(int[][] interval...

汇总区间题目228. 汇总区间 给定一个 无重复元素 的 有序 整数数组 nums 。 返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。 列表中的每个区间范围 [a,b] 应该按如下格式输出： "a->b" ，如果 a != b "a" ，如果 a == b 示例 1： 输入：nums = [0,1,2,4,5,7]输出：[“0->2”,”4->5”,”7”]解释：区间范围是： [0,2] –> “0->2” [4,5] –> “4->5” [7,7] –> “7” 示例 2： 输入：nums = [0,2,3,4,6,8,9]输出：[“0”,”2->4”,”6”,”8->9”]解释：区间范围是： [0,0] –...

最长连续序列题目128. 最长连续序列 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 1： 输入：nums = [100,4,200,1,3,2]输出：4解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。 示例 2： 输入：nums = [0,3,7,2,5,8,4,6,0,1]输出：9 提示： 0 <= nums.length <= 105 -109 <= nums[i] <= 109 题解 排序后，滑动窗口解题，挺简单的 12345678910111213141516171819202122232425262728public static int longestConsecutive(int[] nums) { if (nums.length == 0) return 0; int max = 0; int temp = 1; A...

存在重复元素II题目219. 存在重复元素 II 给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。 示例 1： 输入：nums = [1,2,3,1], k = 3输出：true 示例 2： 输入：nums = [1,0,1,1], k = 1输出：true 示例 3： 输入：nums = [1,2,3,1,2,3], k = 2输出：false 提示： 1 <= nums.length <= 105 -109 <= nums[i] <= 109 0 <= k <= 105 题解题解一（暴力法）123456789101112public static boolean containsNearbyDuplicate(int[] nums, int k) { for ...

快乐数题目202. 快乐数 编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」 定义为： 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。 如果这个过程 结果为 1，那么这个数就是快乐数。 如果 n 是 快乐数 就返回 true ；不是，则返回 false 。 示例 1： 输入：n = 19输出：true解释：12 + 92 = 8282 + 22 = 6862 + 82 = 10012 + 02 + 02 = 1 示例 2： 输入：n = 2输出：false 提示： 1 <= n <= 231 - 1 题解 挺简单一题，只要知道不是快乐数的机制就好了 一旦出现循环，接肯定不是快乐数 12345678910111213141516171819202122232425262728293031323334public static boolean isHappy(int n) { ...

字母异位词分组题目49. 字母异位词分组 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。 示例 1: 12输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]输出: [["bat"],["nat","tan"],["ate","eat","tea"]] 示例 2: 12输入: strs = [""]输出: [[""]] 示例 3: 12输入: strs = ["a"]输出: [["a"]] 提示： 1 <= strs.length <= 104 0 <= strs[i].length <...

有效的字母异位词题目242. 有效的字母异位词 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的 字母异位词。 字母异位词 字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次。 示例 1: 12输入: s = "anagram", t = "nagaram"输出: true 示例 2: 12输入: s = "rat", t = "car"输出: false 提示: 1 <= s.length, t.length <= 5 * 104 s 和 t 仅包含小写字母 进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？ 题解题解一 按照同一规则排序后比较是否相同 12345678910public boolean isAnagram(String s, String t) { if (s.length() != t.length()) { ret...

无重复字符的最长子串题目3. 无重复字符的最长子串 给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。 示例 1: 123输入: s = "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 示例 2: 123输入: s = "bbbbb"输出: 1解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 示例 3: 1234输入: s = "pwwkew"输出: 3解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。 提示： 0 <= s.length <= 5 * 104 s 由英文字母、数字、符号和空格组成 题解 使用滑动窗口方法，挺简单的 12345678910111213141516public static int length...

单词规律题目290. 单词规律 给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。 这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。 示例1: 12输入: pattern = "abba", s = "dog cat cat dog"输出: true 示例 2: 12输入:pattern = "abba", s = "dog cat cat fish"输出: false 示例 3: 12输入: pattern = "aaaa", s = "dog cat cat dog"输出: false 提示: 1 <= pattern.length <= 300 pattern 只包含小写英文字母 1 <= s.length <= 3000 s 只包含小写英文字母和 ' ' s 不包含 任何前导或尾随对空格 s 中每个单词...

同构字符串题目205. 同构字符串 给定两个字符串 s 和 t ，判断它们是否是同构的。 如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。 每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。 示例 1: 12输入：s = "egg", t = "add"输出：true 示例 2： 12输入：s = "foo", t = "bar"输出：false 示例 3： 12输入：s = "paper", t = "title"输出：true 提示： 1 <= s.length <= 5 * 104 t.length == s.length s 和 t 由任意有效的 ASCII 字符组成 题解 和 290. 单词规律 同样的解法 1234567891011121314151617public static boolean...

赎金信383. 赎金信 给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。 如果可以，返回 true ；否则返回 false 。 magazine 中的每个字符只能在 ransomNote 中使用一次。 示例 1： 12输入：ransomNote = "a", magazine = "b"输出：false 示例 2： 12输入：ransomNote = "aa", magazine = "ab"输出：false 示例 3： 12输入：ransomNote = "aa", magazine = "aab"输出：true 提示： 1 <= ransomNote.length, magazine.length <= 105 ransomNote 和 magazine 由小写英文字母组成 题解题解一（暴力法）123456789101112131415161718...

长度最小的子数组题目209. 长度最小的子数组 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。 示例 1： 123输入：target = 7, nums = [2,3,1,2,4,3]输出：2解释：子数组 [4,3] 是该条件下的长度最小的子数组。 示例 2： 12输入：target = 4, nums = [1,4,4]输出：1 示例 3： 12输入：target = 11, nums = [1,1,1,1,1,1,1,1]输出：0 提示： 1 <= target <= 109 1 <= nums.length <= 105 1 <= nums[i] <= 104 进阶： 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。 题解题解一（暴力法）123456...

面试经典-三数之和题目15. 三数之和 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。 注意：答案中不可以包含重复的三元组。 示例 1： 12345678输入：nums = [-1,0,1,2,-1,-4]输出：[[-1,-1,2],[-1,0,1]]解释：nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。注意，输出的顺序和三元组的顺序并不重要。 示例 2： 123输入：nums = [0,1,1]输出：[]解释：唯一可能的三元组和不为 0 。 ...

文本左右对齐题目68. 文本左右对齐 给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。 你应该使用 “贪心算法” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。 要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。 文本的最后一行应为左对齐，且单词之间不插入额外的空格。 注意: 单词是指由非空格字符组成的字符序列。 每个单词的长度大于 0，小于等于 maxWidth。 输入单词数组 words 至少包含一个单词。 示例 1: 1234567输入: words = ["This", "is", "an", "example", "of", "text", "justification."],...

盛最多水的容器题目11. 盛最多水的容器 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 说明：你不能倾斜容器。 示例 1： 输入：[1,8,6,2,5,4,8,3,7]输出：49解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。 示例 2： 输入：height = [1,1]输出：1 提示： n == height.length 2 <= n <= 105 0 <= height[i] <= 104 题解题解一（暴力求解）12345678910public static int maxArea(int[] height) { int max = 0; for (int i = 0; i < height.length; i++)...

两数之和II_输入有序数组题目167. 两数之和 II - 输入有序数组 给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。 以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。 你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。 你所设计的解决方案必须只使用常量级的额外空间。 示例 1： 输入：numbers = [2,7,11,15], target = 9输出：[1,2]解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。 示例 2： 输入：numbers = [2,3,4]...

面试经典-判断子序列题目详情392. 判断子序列 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。 进阶： 如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？ 示例 1： 输入：s = “abc”, t = “ahbgdc”输出：true 示例 2： 输入：s = “axc”, t = “ahbgdc”输出：false 提示： 0 <= s.length <= 100 0 <= t.length <= 10^4 两个字符串都只由小写字符组成。 题解12345678910111213141516171819202122public static boo...

面试经典-验证回文串题目详情125. 验证回文串 如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。 字母和数字都属于字母数字字符。 给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。 示例 1： 输入: s = “A man, a plan, a canal: Panama”输出：true解释：”amanaplanacanalpanama” 是回文串。 示例 2： 输入：s = “race a car”输出：false解释：”raceacar” 不是回文串。 示例 3： 输入：s = “ “输出：true解释：在移除非字母数字字符之后，s 是一个空字符串 “” 。由于空字符串正着反着读都一样，所以是回文串。 提示： 1 <= s.length <= 2 * 105 s 仅由可打印的 ASCII 字符组成 题解 比较简单，建议直接AC 12345678910111213public static boolea...