在断层环境中应用二分法 // 题目链接-来源：力扣（LeetCode） 整数数组 nums 按升序排列，数组中的值 互不相同 。 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。 给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。 示例 1： 输入：nums = [4,5,6,7,0,1,2], target = 0输出：4 思路：旋转排序数组，某种程度上是有序的，因此考虑二分法。阻碍我们流畅使用二分法的只有一个因素，就是数组旋转后会出现断层。但是断层有一定的规律。我们可以将数组分为「较大部分」和「较小部分」 ...

贪心算法判定对称条件。 // 题目链接-来源：力扣（LeetCode） 给你一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。 示例 1： 输入：s = “(()”输出：2解释：最长有效括号子串是 “()” 思路：我们可以遍历每个字符。分别记录正括号和反括号的数量 left 和 right。当两个数字相等时，即可判断整个子串有效，更新最大子串长度。而当右括号的数量较大时，我们就可以将两个数字置 0，因为多余的右括号出现在最右时，左侧的子串已经不能构成合法的字符串。这种考虑有个瑕疵，就是当左侧有很多多余的左括号时，我们的 right 永远小于 left，即使遍历到字符串末尾也无法统计出有效子串长度。此时我们只需反向遍历字符串，将前面的判断规则镜像处理，以左括号数量超越右括号为重置条件。 时间复杂度：O(n)空间复杂度：O(1) 实现：1234567891011121314151617181920212223242526272829303132333435363738394041424344class Solution { ...

找规律 // 题目链接-来源：力扣（LeetCode） 实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。 必须 原地 修改，只允许使用额外常数空间。 示例 1： 输入：nums = [1,2,3]输出：[1,3,2] 思路：考虑「下一个排列」的特征。 首先，可以想到，如果数组为完全逆序，则意味着我们找不到下一个排序了。此时我们就必须重排数组。 反之，如果数组存在顺序对（即存在 nums[i] < nums[i + 1]），我们可以判定数组中一定存在「下一个排列」。 对于字典序，靠前的元素的权重大于靠后的元素，于是我们应该优先考察靠后元素。我们可以从后往前遍历数组，跳过逆序对，当我们遍历到第一组顺序对（记为 nums[i]，nums[i + 1]）时，我们有如下推论： nums[i + 1] 以及之后的元素必为逆序排列， 且 nums[i + 1] 从下标 i 到 length - 1 这个局部的最大值。（因为我们是从后向前遍历的，否则就不会停在这 ...

利用分组遍历精简字符串的匹配。 // 30.题目链接-来源：力扣（LeetCode） 给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。 注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。 示例 1： 输入：s = “barfoothefoobarman”, words = [“foo”,”bar”]输出：[0,9]解释：从索引 0 和 9 开始的子串分别是 “barfoo” 和 “foobar” 。输出的顺序不重要, [9,0] 也是有效答案。 思路：本题可以先从暴力解着手开展思路。记 words 的单词个数为 wNum， 每个单词长度为 wLen。我们可以遍历 s 中的每一位，以之为起点开始向后查找单词，总共查找 wNum 次，每次跨越 wLen 个字符，用一个哈希表统计单词出现次数，并与 words 中的次数进行比较，若一致则可将此位加入结果列表中。我们如何优化暴力解呢？考虑如下字符串实例 s = “wo ...

利用加减法位运算实现除法器 // 29.题目链接-来源：力扣（LeetCode） 给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。 返回被除数 dividend 除以除数 divisor 得到的商。 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2 示例 1: 输入: dividend = 10, divisor = 3输出: 3解释: 10/3 = truncate(3.33333..) = truncate(3) = 3 思路：题目要求不能用乘除法，也就是几乎要我们实现一个有符号整数除法器。我们可以参考竖式计算的思路来构造这个除法器。 在竖式中，我们固定被除数 dividend，依次从高到低遍历其每一位。 在每一轮遍历中，我们对除数 divisor 进行左移操作，直到移位后的结果「恰好」小于等于 dividend （「恰好」的意 ...

KMP算法解决串的模式匹配 // 28.题目链接-来源：力扣（LeetCode） 实现 strStr() 函数。 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回  -1 。 说明： 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。 示例 1： 输入：haystack = “hello”, needle = “ll”输出：2 思路：此题是 KMP 算法的典型应用。记 haystack 的长度为 h，needle 的长度为 n，则暴力解法可以在 O(hn)的复杂度内完成查找（每次在 haystack 中移动到新的一位时，最坏情况下要从此处开始依次与 needle 作比较）。考虑优化解法。我们的问题是，是否每次匹配失败后，needle 的指针都要回退到开头？能否 ...

数组元素的交换 // 27.题目链接-来源：力扣（LeetCode） 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 输入：nums = [3,2,2,3], val = 3输出：2, nums = [2,2]解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。 思路：注意到元素的顺序可以改变，为了最大限度减少访存次数，我们不直接删除数组元素，而是将丢弃的元素交换到数组末尾。同时为了尽可能降低复杂度，我们采用双指针，一个前指针 i 指向待处理的元素，从前往后遍历，另一个后指针 len 指向数组尾部元素，从后往前遍历，跳过我们需要删除的 ...

用二分法定位数组中的元素 // 26.题目链接-来源：力扣（LeetCode） 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。 示例 1： 输入：nums = [1,1,2]输出：2, nums = [1,2]解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。 思路：我们可以跳跃地处理数组的数据。容易想象，对于处理完毕的结果数组，在有效长度（即返回值对应的长度）内，每一个元素的值都不相等。我们只要跳跃地取出这些值，依次复制到数组头部，待跳跃超出了数组实际长度后停止即可。由于数组有序，容易想到用二分法来定位待操作的元素。我们可以写一个辅助函数 findNextEle(target)，这个函数的作用是返回 「数组中大于 target 的第一个元素」。对于数组中的第一个元素，我们令 target = nums[0]，调 ...

链表中多个子链表的翻转 // 25.题目链接-来源：力扣（LeetCode） 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。 k 是一个正整数，它的值小于或等于链表的长度。 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。 进阶： 你可以设计一个只使用常数额外空间的算法来解决此问题吗？你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。 示例 1： 输入：head = [1,2,3,4,5], k = 2输出：[2,1,4,3,5] 思路：此题是上一题的一般情况，我们可以沿用其框架，即对于一段长度为 k 的待处理节点，用 preCur 指向该段的前驱，用 curFront 标记本段的起始节点，然后对 preCur 之后的 k 个节点，我们提取一个 reverse() 方法单独处理对其的翻转操作，返回反转以后的头结点。由于我们要避免处理长度不足 k 的末尾段，在进行 reverse() 操作之前，我们要从 preCur 之后数出 k 个节点，若计数未满即至表尾，则表示已经无需操作，跳出循环。每次循环末尾，我们需要更新 ...

交换、反转链表中的节点 // 24.题目链接-来源：力扣（LeetCode） 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。 示例 1： 输入：head = [1,2,3,4]输出：[2,1,4,3] 思路：本题是下一题「25. K 个一组翻转链表」的特例，理清本题思路有助于我们解决下一题。此类题目有递归法和迭代法两种。递归法代码简洁，但由于递归本身需要的栈空间，空间复杂度为 O(1)，且不易理解，故采用迭代法。首先还是用一个「哑节点」dummy 插入链表头部。直观上理解，我们可以从头到尾一对一对地依次翻转每一段节点（在本题中，一段即有 2 个节点，而在下一题种，一段有 k 个节点），事实上这样做的效率也是最高的，因为无需额外的遍历。用指针 curFront 标记当前要处理的段的起始节点，用指针 preCur 抓住该节点的前驱，用指针 curNext (对于下一题是 curEnd) 标记当前节点对的末尾（第二个）节点，用指针 rest 标记末尾节点之后的节点，也就是链表的剩余部分。于是我们的可以 ...