找规律 // 题目链接-来源：力扣（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 标记末尾节点之后的节点，也就是链表的剩余部分。于是我们的可以 ...

用最小堆合并多个链表 // 23.题目链接-来源：力扣（LeetCode） 给你一个链表数组，每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中，返回合并后的链表。 示例 1： 输入：lists = [[1,4,5],[1,3,4],[2,6]]输出：[1,1,2,3,4,4,5,6]解释：链表数组如下：[ 1->4->5, 1->3->4, 2->6]将它们合并到一个有序链表中得到。1->1->2->3->4->4->5->6 思路：我们的思路基于「合并2个升序链表」拓展。在 k = 2 时，我们所要获取的链表节点实际上是当前节点值最小的那个节点。于是，我们只要维护一个可以方便获取到 当前活跃链表的未处理值 的最小堆即可。这个最小堆（优先级队列）能让我们以单次平均 O(logk) 的复杂度获取所需的节点。细节： 我们需要提供一个比较器接口给最小堆，这个比较器需要返回两个节点中节点值较小的那一个节点。 另外，当我们弹出一个节点，将其加入我们的返回列表以后，我们要将它的后 ...

DFS + 回溯法解决字符串生成问题 // 22.题目链接-来源：力扣（LeetCode） 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 示例 1： 输入：n = 3输出：[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”] 思路：这是字符串生成的问题，可以考虑 DFS + 回溯法。我们利用 DFS 递归地遍历当前下一位所有可能的括号组合（当前至多有 2 种选择），然后用回溯法回到递归前的状态，当左右括号数等于所需的对数时，即收集结果。如此我们可以遍历每一位的括号组合。细节：「剪枝」，即进行下一步之前，通过条件判断过滤掉一些不可能的选择，比如，右括号不能多于左括号，所以当左右括号数相等时，我们下一步只能添加左括号；否则，我们既可以添加左括号，也可右括号，依次回溯遍历即可。时间复杂度：O(4^n/n^0.5)空间复杂度：O(n) 实现：123456789101112131415161718192021222324252627282930313233343536class S ...