zhuwenxing#Interview-Notebook#剑指 Offer 题解 - 20~291

* [20. 表示数值的字符串](#20-表示数值的字符串) * [21. 调整数组顺序使奇数位于偶数前面](#21-调整数组顺序使奇数位于偶数前面) * [22. 链表中倒数第 K 个结点](#22-链表中倒数第-k-个结点) * [23. 链表中环的入口结点](#23-链表中环的入口结点) * [24. 反转链表](#24-反转链表) * [25. 合并两个排序的链表](#25-合并两个排序的链表) * [26. 树的子结构](#26-树的子结构) * [27. 二叉树的镜像](#27-二叉树的镜像) * [28 对称的二叉树](#28-对称的二叉树) * [29. 顺时针打印矩阵](#29-顺时针打印矩阵) # 20. 表示数值的字符串 [NowCoder](https://www.nowcoder.com/practice/6f8c901d091949a5837e24bb82a731f2?tpId=13&tqId=11206&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking) ## 题目描述 ``` true "+100" "5e2" "-123" "3.1416" "-1E-16" ``` ``` false "12e" "1a3.14" "1.2.3" "+-5" "12e+4.3" ``` ## 解题思路 使用正则表达式进行匹配。 ```html [] ： 字符集合 () ： 分组 ? ： 重复 0 ~ 1 次 + ： 重复 1 ~ n 次 * ： 重复 0 ~ n 次 . ： 任意字符 \\. ： 转义后的 . \\d ： 数字 ``` ```java public boolean isNumeric(char[] str) { if (str == null || str.length == 0) return false; return new String(str).matches("[+-]?\\d*(\\.\\d+)?([eE][+-]?\\d+)?"); } ``` # 21. 调整数组顺序使奇数位于偶数前面 [NowCoder](https://www.nowcoder.com/practice/beb5aa231adc45b2a5dcc5b62c93f593?tpId=13&tqId=11166&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking) ## 题目描述 需要保证奇数和奇数，偶数和偶数之间的相对位置不变，这和书本不太一样。
## 解题思路 方法一：创建一个新数组，时间复杂度 O(N)，空间复杂度 O(N)。 ```java public void reOrderArray(int[] nums) { // 奇数个数 int oddCnt = 0; for (int x : nums) if (!isEven(x)) oddCnt++; int[] copy = nums.clone(); int i = 0, j = oddCnt; for (int num : copy) { if (num % 2 == 1) nums[i++] = num; else nums[j++] = num; } } private boolean isEven(int x) { return x % 2 == 0; } ``` 方法二：使用冒泡思想，每次都当前偶数上浮到当前最右边。时间复杂度 O(N²)，空间复杂度 O(1)，时间换空间。 ```java public void reOrderArray(int[] nums) { int N = nums.length; for (int i = N - 1; i > 0; i--) { for (int j = 0; j < i; j++) { if (isEven(nums[j]) && !isEven(nums[j + 1])) { swap(nums, j, j + 1); } } } } private boolean isEven(int x) { return x % 2 == 0; } private void swap(int[] nums, int i, int j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; } ``` # 22. 链表中倒数第 K 个结点 [NowCoder](https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&tqId=11167&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking) ## 解题思路 设链表的长度为 N。设置两个指针 P1 和 P2，先让 P1 移动 K 个节点，则还有 N - K 个节点可以移动。此时让 P1 和 P2 同时移动，可以知道当 P1 移动到链表结尾时，P2 移动到第 N - K 个节点处，该位置就是倒数第 K 个节点。