链表操作 // 题目链接-来源：力扣（LeetCode） 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。 示例1： 输入：1->2->4, 1->3->4输出：1->1->2->3->4->4 思路：基本的链表操作，也是归并排序操作的主体部分（两个链表代表的子序列已经排序完成）。主体部分用两个指针 cur1 cur2 分别记录两个链表当前访问的位置，比较大小，依次复制即可。最后分别对剩余部分一次性复制处理。链表操作前增加一个无意义的头结点 newHead ，可以事半功倍，免去繁琐的空链表判断。事后返回 newHead.next 即可。 时间复杂度：O(n)空间复杂度：O(1) 实现：12345678910111213141516171819202122232425class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode l = new ListNode ...

反转链表经典题 // 题目链接-来源：力扣（LeetCode） 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。 示例: 输入: 1->2->3->4->5->NULL输出: 5->4->3->2->1->NULL 思路：反转链表经典解法无非两种，一是递归法，二是用指针遍历链表迭代操作。指针遍历较为直观，且占用常数空间。但递归法容易写出较为简洁的代码，这里介绍递归法。首先，每次递归都假设当前节点的下下个节点及以后已经实现了反转，由于我们要获取反转后的链表头（也就是原链表的表尾），这个链表头就需要我们通过递归函数层层返回上来。我们用一个变量 newHead 记录之。然后我们只需要关注当前节点与下个进行反转即可。先让下个节点的尾部指向自己，再将当前节点尾部置为 null，即完成了当前层的递归，最后记得将前面记录的 newHead 返回给上层函数。时间复杂度：O(n)空间复杂度：O(n) 实现：1234567891011121314151617181920212223class Solution
...

链表查找，双指针 // 题目链接-来源：力扣（LeetCode） 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。 例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。 示例： 给定一个链表: 1->2->3->4->5, 和 k = 2. 返回链表 4->5. 思路：一个比较直观而暴力的思路就是，先遍历整个链表，计数总节点数 n，那么需要返回的链表就是第 n - k + 1 个节点。进一步优化：以上方法需要遍历两次链表，能不能只遍历一次？可以，那就是「双指针」法。不过这个双指针起始位置不再是一左一右，而是一个 latter 从链表头出发，另一个 former 从相距 k - 1 个节点处出发，等到 former 移动到表尾时，latter 自然而然指向了倒数第 k 个节点。时间复杂度：O(n)空间复杂度：O(1) 实现：123456789101112131415161718class Solu ...

双指针 // 题目链接-来源：力扣（LeetCode） 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。 示例： 输入：nums = [1,2,3,4]输出：[1,3,2,4]注：[3,1,2,4] 也是正确的答案之一。 思路：我们的目标是让数组「左侧」全是奇数，如果暴力解的话，那么我们就从头遍历数组，碰到偶数的话，从尾部反向遍历数组，寻找第一个奇数进行交换。但实际上，我们很容易想到优化的方案：经过交换的尾部数组已经符合要求，我们不需要每次都从末尾开始查找奇数，只要从上一次落脚点查找就可以了，于是想到双指针法。一个指针 left 从左侧开始查找偶数，另一个指针 right 从右侧开始查找奇数，都找到以后进行交换即可。指针移动过程中需要时刻保持 left < right。时间复杂度：O(n)空间复杂度：O(1) 实现：123456789101112131415161718class Solution { public int[] exchange(int[] nums) { ...

字符串处理，确定有限状态自动机 // 题目链接-来源：力扣（LeetCode） 请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。 数值（按顺序）可以分成以下几个部分： 若干空格一个 小数 或者 整数（可选）一个 ‘e’ 或 ‘E’ ，后面跟着一个 整数若干空格小数（按顺序）可以分成以下几个部分： （可选）一个符号字符（’+’ 或 ‘-‘）下述格式之一：至少一位数字，后面跟着一个点 ‘.’至少一位数字，后面跟着一个点 ‘.’ ，后面再跟着至少一位数字一个点 ‘.’ ，后面跟着至少一位数字整数（按顺序）可以分成以下几个部分： （可选）一个符号字符（’+’ 或 ‘-‘）至少一位数字部分数值列举如下： [“+100”, “5e2”, “-123”, “3.1416”, “-1E-16”, “0123”]部分非数值列举如下： [“12e”, “1a3.14”, “1.2.3”, “+-5”, “12e+5.4”] 示例 1： 输入：s = “0”输出：true 思路：注意到字符串有很多状态和可能，如果一个一个用 if-else 类似硬编码的方式处理本题，代码会相当繁琐 ...

字符串处理，动态规划 // 题目链接-来源：力扣（LeetCode） 请实现一个函数用来匹配包含’. ‘和’*‘的正则表达式。模式中的字符’.’表示任意一个字符，而’*‘表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”ab*ac*a”匹配，但与”aa.a”和”ab*a”均不匹配。 示例 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 ...

链表操作 // 题目链接-来源：力扣（LeetCode） 给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。 返回删除后的链表的头节点。 注意：此题对比原题有改动 示例 1: 输入: head = [4,5,1,9], val = 5输出: [4,1,9]解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9. 思路：链表操作的题，涉及到删除操作的，往往可以自己定义一个无意义的头结点 newHead 接到所给链表的头部，方便后续代码写得方便简洁（省略对 head 是否为空的单独判断）。题中要求简单的删除操作，只要用一个遍历指针 cur 从我们的头结点出发，判断 cur.next = val，若相等，删除该节点即可，cur.next 接到 cur.next.next 上。结束后返回 newHead.next 即可。时间复杂度：O(n)空间复杂度：O(1) 实现：12345678910111213141516class Solution { public L ...

全排列，DFS，回溯 // 题目链接-来源：力扣（LeetCode） 输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。 示例 1: 输入: n = 1输出: [1,2,3,4,5,6,7,8,9] 思路：鉴于LeetCode中本题只需输出int，可知n不存在越界可能。只要实现一个关于整数的n次幂的计算方法，对任意n调用 pow(10, n) ，再从1开始循环打印即可。拓展：当然对于更广泛的使用场景而言（也是本题真正的考点），我们要考虑大数越界的情况，即输入的n可能是一个 long 型大数，甚至是一个类似 __uint128_t 的大数。那么我们需要借助不限长度的字符串，帮助我们实现数字的打印。于是问题转化成，「输出n位 ‘0’~’9’数字的全排列」，我们可以用回溯算法+ DFS 来解决此类字符串的拼接、遍历问题。对于函数的主体 DFS(n)，算法结构如下： 对于每一位数字，我们在字符串中加上它，然后继续对其下一位使用 DFS(n - 1)，待返回后，「恢复现场」，将这位数字删除，进入下一个 ...

二分法，快速幂 // 题目链接-来源：力扣（LeetCode）实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。 示例 1： 输入：x = 2.00000, n = 10输出：1024.00000 思路：此题一上来应有暴力求解的思路，通过 pow(x, n - 1) (n > 0)或 pow(x, n + 1) (n < 0)递归或迭代地求解。但是暴力解法会超时，我们考虑简化运算。注意到，当n为偶数的时候，我们只需计算 pow(x, n / 2)，然后将结果平方即可。而当n为奇数时，我们依然可以 计算 pow(x, n / 2)，将结果平方后再多乘一个 x 即可。事实上，这就是快速幂的思路，我们用 res 存储结果，在 n 为奇数（用 n & 1 判断）时，额外进行 res *= x。在 n 为偶数时，对 n 减半（用 n >> 1 操作），同时让 x 平方。即可在 log n 时间内得到结果。细节上，在 n 为负数时，取反然后将 x 取倒数 ...

位运算 // 题目链接-来源：力扣（LeetCode）请实现一个函数，输入一个整数（以二进制串形式），输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。 示例 1： 输入：00000000000000000000000000001011输出：3解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 ‘1’。 思路：以最低为为基准，与 1 做与运算，就能得到当前位是否为1。然后将整数逻辑右移，重复与运算，循环31次即可遍历所有位。进一步优化：关于位运算，有个用途很广的小技巧， n & (n - 1)，这个式子的返回值是「当前二进制串的最末尾一个“1”变成“0”」的值举例 1010 & (1010 - 1) = 1010 & (1001) = 1000可以看到倒数第 2 位上的 “1” 被消除了。这样对于 “1”比较稀疏的串，就不需要遍历32位这么多了。 时间复杂度：O(1)空间复杂度：O(1) 实现：1234567 ...