Jiankychen's Blog

# LeetCode 42. 接雨水 42. Trapping Rain Water 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 示例 1： 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are be

# LeetCode 11. 盛最多水的容器 11. Container With Most Water 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 说明：你不能倾斜容器。 示例 1： 输入：height = [1,8,6,2,5,4,8,3,7] 输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为

# LeetCode 10. 正则表达式匹配 10. Regular Expression Matching 给你一个字符串 s 和一个字符规律 p ，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。 '.' 匹配任意单个字符 '*' 匹配零个或多个前面的那一个元素 所谓匹配，是要涵盖 整个 字符串 s 的，而不是部分字符串。 示例 1： 输入：s = "aa", p = "a" 输出：false 解释："a" 无法

# LeetCode 1005. K 次取反后最大化的数组和 1005. Maximize Sum Of Array After K Negations 给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组： 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。 以这种方式修改数组后，返回数组 可能的最大和 。 示例 1： 输入：nums = [4,2,3], k = 1 输出：5 解释：选择下标 1 ，nums 变为 [4,-2,3] 示例 2： 输入

# LeetCode 131. 分割回文串 131. Palindrome Partitioning 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。 回文串 是正着读和反着读都一样的字符串。 示例 1： 输入：s = "aab" 输出：[["a","a","b"],["aa","b"]] 示例 2： 输入：s = "a" 输出：[["a"]] 提示： 1

回溯法也叫回溯搜索法，它是一种搜索的方式 只要有递归就会有回溯 回溯法的工作原理 构造空间树 进行遍历 如遇到边界条件，即不再向下搜索，转而搜索另一棵子树 达到目标条件，输出结果 回溯的本质是穷举，即便加入 剪枝 操作，回溯法也并不高效 回溯法一般可以解决如下几种问题： 组合问题 ：N 个数里面按一定规则找出 k 个数的集合 切割问题 ：一个字符串按一定规则有几种切割方式 子集问题 ：一个 N 个数的集合里有多少符合条件的子集 排列问题 ：N 个数按一定规则全排列，有几种排列方式 棋盘问题 ：N 皇后，解数独等等 以上问题都可以近似成：在集合中查找子集。可以把这些问题抽

# LeetCode 100. 相同二叉树 100. Same Tree 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。 示例 1： 输入：p = [1,2,3], q = [1,2,3] 输出：true 示例 2： 输入：p = [1,2], q = [1,null,2] 输出：false 示例 3： 输入：p = [1,2,1], q = [1,1,2] 输出：false 提示： 两棵树上的节点数目都在范围 [0,10

# LeetCode 1047. 删除字符串中的所有相邻重复项 1047. Remove All Adjacent Duplicates In String 给出由小写字母组成的字符串 S ，重复项删除操作 会选择两个相邻且相同的字母，并删除它们。 在 S 上反复执行重复项删除操作，直到无法继续删除。 在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。 示例 1： 输入：s = "abbaca" 输出："ca" 解释：例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相

Knuth-Morris-Pratt 算法，简称 KMP 算法，由 Donald Knuth、James H. Morris 和 Vaughan Pratt 三人于 1977 年联合发表 KMP 算法主要应用于 字符串匹配 基本思想：当出现字符串不匹配时，可以利用前面已经匹配的那些字符中的信息，避免从头再做匹配 以 在文本串中查找是否出现过一个模式串 为例： 检测文本串 "aabaabaaf" 中是否含有 模式串 "aabaaf"，KMP 算法的查找过程如下所示 令 nnn 表示文本串长度，mmm 表示模式串长度，暴力匹配的时间复杂度为 O(n×m)O

# LeetCode 151. 颠倒字符串中的单词 LeetCode 151. Reverse Words in a String 给你一个字符串 s ，请你反转字符串中 单词 的顺序。 单词 是由非空格字符组成的字符串。 s 中使用至少一个空格将字符串中的 单词 分隔开。 返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。 注意：输入字符串 s 中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。 示例 1： 输入：s = "the sky is blue" 输出：&q