模拟矩阵路径进行遍历 // 题目链接-来源：力扣（LeetCode） 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。 示例 1： 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]输出：[1,2,3,6,9,8,7,4,5] 思路：由于矩阵形状相当规则，所以模拟顺时针方向遍历并不困难。关键点在于，决定何时转向，以及转向哪个方向，还有最终在何时停止。转向的时机：我们可以先判定当前前进方向上的下一个位置是否「可达」。首先需要维护一个同样大小的 visited[][] 矩阵，记录访问过的位置，若访问过，则「不可达」。另外，当下个位置发生数组越界时，同样不可达。这样我们只要在「不可达」时转向，「可达」时前进即可。方向确定：为了使代码简单，不至于对4个方向都做一次判断，我们可以维护一个类似时钟指针一样顺时针旋转的向量数组 directions[][]，这个数组里存储4个方向上的方向向量，例如， {0,1} 表示当前前进方向是上方。每次需要转向时，指针前进一位并对 4（数组长度） 求余即可进入下个方向。终止条件：我们可以计数输出的数字个数，当 ...

树的结构 // 题目链接-来源：力扣（LeetCode） 请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。     1   /   2   2 / \ / 3  4 4  3但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:     1   /   2   2   \      3    3 示例 1： 输入：root = [1,2,2,3,4,4,3]输出：true 思路：我们要判断镜像，关键在于找到每个节点应该比较的对象。对于任意两个节点 L 与 R，它们是否镜像取决于对应的子节点是否镜像，即 L.left 与 R.right， 还有 L.right 与 R.left是否镜像。于是我们可以这样递归地往下判定，直到最低层向上递归地返回判定结果。需要返回 false 的情况有 两节点不全为空 两节点均不空时值不相等 传递镜像位置子节点返回 false 判定。时间复杂度：O(n)空间复杂度：O(n) ...

树的镜像 // 题目链接-来源：力扣（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 ...