双指针降低问题复杂度的维数 // 11. 题目链接-来源：力扣（LeetCode）（中等） 给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。 说明：你不能倾斜容器。 思路：本质上就是求n块板子两两配对，它们之间的长度和距离所围成的矩形面积。如果暴力解，每块板子都与剩下的n-1块板子配对计算一次面积，也不是不行，但是复杂度为O(n²)，太笨了。简化问题，首先面积 = 距离 * 高度，距离好办，我们一开始分别选择两侧的板子就能保证距离最远。高度呢，那就逐渐缩短距离，以距离换高度。那么从哪边开始缩呢，根据短板原理，需要先改变较低的一边，否则水位只可能下降（另一侧变得比这一侧还要矮）或者持平（另一侧变高或者不变）。所以确定好距离收缩的规则，从两侧向中间收缩，每次收缩求出面积取最大值即可。时间复杂度：O(n)空间复杂度：O(1) 实现：123456789101112131415161 ...

二维动态规划解决正则表达式匹配问题 // 10.题目链接-来源：力扣（LeetCode）（困难） 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。 ‘.’ 匹配任意单个字符‘*’ 匹配零个或多个前面的那一个元素所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。 示例 1： 输入：s = “aa” p = “a”输出：false解释：”a” 无法匹配 “aa” 整个字符串。 ####思路：本题是一道动态规划处理字符串的的经典题目。对于’.’，一个简化的考虑就是，我们设计一个方法 match(char a, char b)，当且仅当 a = b 或者 a、b之中任意一个为’.’时返回 true 。我们用 f(i, j)表示 s截至第i - 1个字符s[i - 1]的子串，与 p截至第j - 1个字符p[j - 1]的子串 是匹配的。那么我们要考虑的问题就是，f(i + 1, j)是否成立，f(i, j + 1)是否成立。注意，f(0, n) 和 f(m, 0) 分别对应「s为空串」以及「p为空串」 ...

用双端队列解决回文串判定 // 9.题目链接-来源：力扣（LeetCode）（简单） 给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。 回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。  示例 1： 输入：x = 121输出：true ####思路：首先排除负数，因为负号 ‘-‘ 只可能出现在一侧。然后想到有一种数据结构天然就很适合处理回文，那就是双向队列 Deque，Java中 LinkedList 实现了Deque接口，所以我们可以直接拿来用。将 x 逐位取余数分离出来，入队。最后不停弹出首尾元素进行比较 removeFirst() == removeLast ? ，在 size() 等于0或1的时候返回即可。这样也自动规避了溢出问题。另外像题解的方法比较巧妙，只比较一半长度的回文数，但是它仍要对后半部分作出处理，所以时间上并不会有什么优势。时间复杂度：O(logn)空间复杂度：O(1) 实现：12345678910111213141516171819 ...

用自动机使判断流程变得清晰 // 8.题目链接-来源：力扣（LeetCode）（中等） 请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。 函数 myAtoi(string s) 的算法如下： 读入字符串并丢弃无用的前导空格 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。 将前面步骤读入的这些数字转换为整数（即，”123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。 如果整数数超过 32 位有符号整数范围 [−231,  231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。 返回整数作为最终结果。 ...

整数处理时注意大数的溢出 // 7.题目链接-来源：力扣（LeetCode）（简单） 给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。 如果反转后整数超过 32 位的有符号整数的范围 [-$2^31$,  $2^31$ − 1] ，就返回 0。 假设环境不允许存储 64 位整数（有符号或无符号）。 示例 1： 输入：x = 123输出：321 ####思路：大体思路就是对 x 取余加到结果数 ret 当中，ret 左移，x右移，循环迭代即可。难点在于细节，不能存储64位数据的情况下如何识别32位数据的溢出。首先确定输入范围，x本身不会溢出，那么最大位数就是十进制10位，[-$2^31$,  $2^31$ − 1]，即[-2147483648, 2147483647]。考虑一个反转后的部分结果 ret，当 ret 达到9位的，并且 x 还不为0的时候，我们就可以考虑溢出问题了。 对于 ret > 214748364 或者 ret < -214748364 的情况，继续右移之后必然溢出，不用考虑x。 对于 -214748364 &l ...

利用线性表结构省略访问的间隔 // 6. 题目链接-来源：力扣（LeetCode）（中等） 将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。 比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下： P A H NA P L S I I GY I R之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：”PAHNAPLSIIGYIR”。 请你实现这个将字符串进行指定行数变换的函数：string convert(string s, int numRows); 示例 1： 输入：s = “PAYPALISHIRING”, numRows = 3输出：”PAHNAPLSIIGYIR” ####思路：这个题要是想清楚了存储的方式和方向还是蛮简单的。首先，先考虑输出顺序，是横向输出，那么我倾向于顺着输出的方向分行存储。这里每一行用List存储就行，不论是LinkedList还是ArrayList区别不大。当然，也可以用 StringBuilder 存储，更为高效。然后是纵 ...

用双端队列实现回文子串判定、动态规划实现高效查找 // 5. 题目链接-来源：力扣（LeetCode） （中等） 给你一个字符串 s，找到 s 中最长的回文子串。 示例 1： 输入：s = “babad”输出：”bab”解释：”aba” 同样是符合题意的答案。 ####思路：这里借鉴了第3题中的『滑动窗口』思路，无非是把『无重复子串』变成了『回文子串』，自己再写一个判定回文的函数替换掉原先的条件即可即可。当然本题也能用动态规划解。我们只要初始化长度为 1 和 长度为 2 子串 的 isPalindrome 状态并记录，即可避免重复计算，优化效率。即 我们以 s 中的每一个字符为起点，向两侧扩展，只要两头碰到的字符相同，即为回文串并更新最大长度，否则即停止扩展进入下一字符。注意，我们既要以单个字符为起点，探讨奇数长度的字符串；也要以一对字符为起点。探讨偶数长度的字符串。因为我们每次扩展时长度增加 2，只能遍历奇数或者偶数中的某一种情况。时间复杂度：O(n²) 遍历一次数组复杂度O(n)，判断是否回文的函数复杂度也为O(n)空间复杂度：O(n) 实现：1234567891 ...

在两个有序数组间实现二分查找。 // 题目链接-来源：力扣（LeetCode） 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 示例 1： 输入：nums1 = [1,3], nums2 = [2]输出：2.00000解释：合并数组 = [1,2,3] ，中位数 2 思路：二分法的实现需要考虑的越界条件比较多，我们考虑依次遍历。数组总长度为 len = m + n，当总长为奇数时，中位数为中间值，否则为中间两数的平均值。为了统一中位数的表达，我们依然用两个目标指针 len / 2 和 (len + 1) / 2 + 1 记录中点值并取平均得到中位数，当总长为奇数时，这两个数相等，否则，这两个数为中点两侧的值。用一个计数值 i 不停计数我们遍历过的数字，用另外两个指针 i1 和 i2 分别记录两个数组中下次当前遍历位置。哪一个值更小，我们就优先排除哪个，当遍历到到 i = len / 2 和 i = (len + ...

用哈希表优化子串的遍历与跳转，实现剪枝。 // 3. 题目链接-来源：力扣（LeetCode） （中等） 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: s = “abcabcbb”输出: 3解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。 ####思路：这是一个「滑动窗口」问题。基本思路就是用一个开头下标start和一个结尾下标i来标记当前处理的区域。接下来考虑怎么判断重复问题，最直观的想法就是查找，最快的查找就是哈希表（复杂度O(1)）。那么就考虑维护一个哈希表isRepeated，存储当前子串中的字符，每次i扫过新的字符就查表，如果存在key则说明重复，不存在则将其加入；然后start前进，直到找到重复字符所在的下标，前进的同时逐个删去经过的字符在表中的记录。进一步优化：考虑最坏情况，可能存在”abcdefgg”这样的字符串，start指向’a’，当i扫过第2个’g’的时候，哈希表查到冲突，但是start需要依次扫过abcdefg才能确定冲突的位置，效率太低。优化方案：用HashMap而不是HashSet， ...

链表基本操作 // 2. 题目链接-来源：力扣（LeetCode） （中等） 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。 示例 1： 输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8] 解释：342 + 465 = 807. ####思路：就是实现一个简单的整数加法，比一些常见的数字处理题要简单，简单之处在于： 链表形式输出，不用考虑溢出问题。 输入是逆序，输出也是逆序，与正常手工计算的顺序相同，很直观。 细节：留意一下进位即可，用一个变量carry记录是否进位 时间复杂度：O(n)空间复杂度：O(n) 实现：12345678910111213141516171819202122232425262728293031323334class Solution { public ListNode addTwoNumb ...