实现字符串转换规则 // 13.题目链接-来源：力扣（LeetCode）（简单） 给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。 示例 1: 输入: “III”输出: 3 思路：这题其实可以做得比上一题巧妙，不懂为什么上题中等这题却是简单。首先转换思路比较直白，读入字符串，数值相应增加，那么跟前一题一样，需要先用个表之类的东西存储一下对应关系。难点在于，4和9的数码对应的字符串含有减法（如IX是 10 - 1 = 9，即后面的大数减去前面的小数）。注意到，减法只会出现在大数前的小数，也就是减法永远出现在数字5,10前面的数字1处。而罗马字符整体上是从大到小显示的，一旦出现『小大』组合，便是小数变号。那么我们将字符串倒过来看，是不是就意味着，整体上是从小到大排列，一旦有『大小』组合，便是小数变号。只要此时在大数出现的时候，作一个负号标记，那么该大数往后的小数就一定需要加负号。（如MCMXCIV，倒序是VICXMCM，V是5，那么之后的I（1）就是负数，C是100，那么之后的X（10）就是负数，依此类推）当然字符串逆序需要多一点点额外的开销，整体 ...

实现编码规则 // 12. 题目链接-来源：力扣（LeetCode）（中等） 罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。 字符 数值I 1V 5X 10L 50C 100D 500M 1000例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。 通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况： I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。 X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。  C 可以放在  ...

双指针降低问题复杂度的维数 // 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 + ...