树的镜像 // 题目链接-来源：力扣（LeetCode） 请完成一个函数，输入一个二叉树，该函数输出它的镜像。 例如输入：      4   /     2     7 / \   / 1   3 6   9镜像输出：      4   /     7     2 / \   / 9   6 3   1 示例 1： 输入：root = [4,2,7,1,3,6,9]输出：[4,7,2,9,6,3,1] 思路：遍历树的各节点，每次将两棵子树交换即可。时间复杂度：O(n)空间复杂度：O(n) 实现：1234567891011121314151617class Solution { public TreeNode mirrorTree(TreeNode root) { if (root == null) { return null; } root.left = mirrorTree(root. ...

树的子结构，树的遍历 // 题目链接-来源：力扣（LeetCode） 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构) B是A的子结构， 即 A中有出现和B相同的结构和节点值。 例如:给定的树 A:      3    /    4   5  /  1   2给定的树 B：    4   / 1返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。 示例 1： 输入：A = [1,2,3], B = [3,1]输出：false 思路：由于我们实现并不知道A的具体结构，因此为了不漏过A的任何一个节点，我们必须对A进行遍历。三种遍历中，先序遍历的递归方法最为简单直观，因此我们采用递归的先序遍历作为算法的模板。 根节点：对于A的每个节点（同时也是当前子树的根节点），我们都考虑是否能让其与B的根节点进入判定流程：根据题目规则，空树不是子结构，同时子结构要求节点形状和节点值都相等，因此只有当节点存在并且节点值相等时，我们才进入对B更深一层子树的判定环节。 左子树：当根节点满足要求后，我们再考虑 ...

链表操作 // 题目链接-来源：力扣（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)，待返回后，「恢复现场」，将这位数字删除，进入下一个 ...