用双端队列解决回文串判定 // 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 ...

用哈希表降低查找的复杂度。 // 1. 题目链接-来源：力扣（LeetCode） （简单） 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。 示例 1： 输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。 ####思路：给定条件查找数据的问题，很容易想到哈希表。建立一个HashMap存储nums中的数值 value 以及对应下标 index1，然后遍历数组值，再查找哈希表中 target - nums[i] 对应的 index2，打包输出即可。 注意index1和index2不能相同。时间复杂度：O(n)空间复杂度：O(n) 实现：1234567891011121314151617class Solution { publ ...

以树的遍历为载体，查找节点的公共祖先至此，剑指Offer(第2版)刷题小记 告一段落。之后将继续更新力扣主站的刷题记录。 // 题目链接-来源：力扣（LeetCode） 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” 例如，给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4] 示例 1: 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1输出: 3解释: 节点 5 和节点 1 的最近公共祖先是节点 3。 思路：对比上题 BST，其未经优化的解法即是对应一般二叉树的通解。时间复杂度：O(n)空间复杂度：O(n) 实现：1234567891011121314151617181920class Solution { public Tree ...