利用加减法位运算实现除法器 // 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 ...

链表形式的归并排序 // 21.题目链接-来源：力扣（LeetCode） 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。  示例 1： 输入：l1 = [1,2,4], l2 = [1,3,4]输出：[1,1,2,3,4,4] 思路：用两个指针指向两个链表的当前节点，取其中节点值较小者加入我们的结果链表，直到两链表均遍历完即可。细节：用一个「伪头结点」dummy 帮我们简化对结果链表为空时的判断逻辑，当某一个链表为空时，直接将另一条链表的余下部分接入。时间复杂度：O(n)空间复杂度：O(n) 实现：123456789101112131415161718192021222324class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode pre = new ListNode(0); ListNode cur = pre; while (l1 != ...

用栈解决括号配对问题。 // 20.题目链接-来源：力扣（LeetCode） 给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。 有效字符串需满足： 左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。 示例 1： 输入：s = “()”输出：true 思路：括号的配对，可以用栈来解决。因为对于一个有效的括号字符串，当第一个反括号出现时，一定可以与栈顶的正括号配对，消去栈顶元素。这样不停地用反括号消去栈顶元素，当最后一个字符访问后，栈一定为空。于是我们只要模拟这样的栈特性，当反括号出现时，就比较栈顶元素是否与其配对，若配对则消去。当遍历字符串结束后，以栈是否为空来作为判断字符串是否有效的依据。时间复杂度：O(n)空间复杂度：O(n) 实现：12345678910111213141516171819202122232425262728class Solution { public boolean isValid(String s) { Stack<Character& ...