《剑指Offer》笔记题解思路技巧优化Java版本——新版leetcode_Part_4

《剑指Offer》笔记&题解&思路&技巧&优化_Part_4 😍😍😍 相知🙌🙌🙌 相识😢😢😢 开始刷题1. LCR 148. 验证图书取出顺序——栈的压入、弹出序列2. LCR 149. 彩灯装饰记录 I——从上到下打印二叉树3. LCR 150. 彩灯装饰记录 II——I.打印二叉树4. LCR 151. 彩灯装饰记录 III——II.打印二叉树5. LCR 152. 验证二叉搜索树的后序遍历序列——二叉搜索树的后序遍历序列6. LCR 153. 二叉树中和为目标值的路径——二叉树中和为某一值的路径7. LCR 154. 复杂链表的复制——复杂链表的复制8. LCR 155. 将二叉搜索树转化为排序的双向链表——二叉搜索树与双向链表9. LCR 156. 序列化与反序列化二叉树——序列化二叉树10. LCR 157. 套餐内商品的排列顺序——字符串的排列

😍😍😍 相知

当你踏入计算机科学的大门，或许会感到一片新奇而陌生的领域，尤其是对于那些非科班出身的学子而言。作为一位非科班研二学生，我深知学习的道路可能会充满挑战，让我们愿意迎接这段充满可能性的旅程。

最近，我开始了学习《剑指Offer》和Java编程的探索之旅。这不仅是一次对计算机科学的深入了解，更是对自己学术生涯的一次扩展。或许，这一切刚刚开始，但我深信，通过努力与坚持，我能够逐渐驾驭这门技艺。

在这个博客中，我将深入剖析《剑指Offer》中的问题，并结合Java编程语言进行解析。

让我们一起踏上这段学习之旅，共同奋斗，共同成长。无论你是已经驾轻就熟的Java高手，还是像我一样初出茅庐的学子，我们都能在这里找到彼此的支持与激励。让我们携手前行，共同迎接知识的挑战，为自己的未来打下坚实的基石。

这是我上一篇博客的，也希望大家多多关注！

《剑指Offer》笔记&题解&思路&技巧&优化 Java版本——新版leetcode_Part_1《剑指Offer》笔记&题解&思路&技巧&优化 Java版本——新版leetcode_Part_2《剑指Offer》笔记&题解&思路&技巧&优化 Java版本——新版leetcode_Part_3 🙌🙌🙌 相识

根据题型可将其分为这样几种类型：

结构概念类（数组，链表，栈，堆，队列，树）搜索遍历类（深度优先搜索，广度优先搜索，二分遍历）双指针定位类（快慢指针，指针碰撞，滑动窗口）排序类（快速排序，归并排序）数学推理类（动态规划，数学） 😢😢😢 开始刷题 1. LCR 148. 验证图书取出顺序——栈的压入、弹出序列

题目跳转： leetcode /problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/description/

想放上自己写的笨思路：

class Solution { public boolean validateBookSequences(int[] putIn, int[] takeOut) { if(putIn.length<=1)return true; boolean[] flag = new boolean[putIn.length]; int slow = 0; for(int i = 0;i < putIn.length;i++){ if(putIn[i]==takeOut[slow]){ slow++; if(slow==putIn.length) return true; flag[i] = true; int temp = i; while(temp>=0&&flag[temp]){ temp--; } while(temp>=0&&putIn[temp]==takeOut[slow]){ slow++; flag[temp] = true; while(temp>=0&&flag[temp]){ temp--; } } } } for(int i = putIn.length-1;i>=0;i--){ if(flag[i])continue; else{ if(putIn[i]==takeOut[slow]){ slow++; flag[i] = true; continue; } else{ return false; } } } return true; } }

虽然代码狗屎，但是我快啊！

下面是大牛的思路！！

解题思路： 如下图所示，给定一个放入序列 putIn 和拿取序列 takeOut ，则放入（压栈）和拿取（弹出）操作的顺序是 唯一确定 的。

下图中 pushed 和 popped 分别对应本题的 putIn 和 takeOut 。 如下图所示，栈的数据操作具有 先入后出 的特性，因此某些拿取序列是无法实现的。 考虑借用一个辅助栈 stack ，模拟 放入 / 拿取操作的排列。根据是否模拟成功，即可得到结果。

入栈操作： 按照压栈序列的顺序执行。出栈操作： 每次入栈后，循环判断 “ 栈顶元素 = 拿取序列的当前元素 栈顶元素 = 拿取序列的当前元素 栈顶元素=拿取序列的当前元素” 是否成立，将符合拿取序列顺序的栈顶元素全部拿取。

由于题目规定 “栈的所有数字均不相等” ，因此在循环入栈中，每个元素出栈的位置的可能性是唯一的（若有重复数字，则具有多个可出栈的位置）。因而，在遇到 “栈顶元素 = 拿取序列的当前元素” 就应立即执行出栈。

代码：

class Solution { public boolean validateBookSequences(int[] putIn, int[] takeOut) { Stack<Integer> stack = new Stack<>(); int i = 0; for(int num : putIn) { stack.push(num); // num 入栈 while(!stack.isEmpty() && stack.peek() == takeOut[i]) { // 循环判断与出栈 stack.pop(); i++; } } return stack.isEmpty(); } }

---

2. LCR 149. 彩灯装饰记录 I——从上到下打印二叉树

题目跳转： leetcode /problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/description/

class Solution { public int[] decorateRecord(TreeNode root) { if(root==null)return new int[0]; //层序遍历 List<Integer> arrayList = new ArrayList<>(); Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); queue.add(null); while(!queue.isEmpty()){ TreeNode temp = queue.poll(); if(temp!=null){ arrayList.add(temp.val); if(temp.left!=null)queue.add(temp.left); if(temp.right!=null)queue.add(temp.right); } else{ if(!queue.isEmpty())queue.add(null); } } int[] result = new int[arrayList.size()]; for(int i = 0;i < result.length;i++){ result[i] = arrayList.get(i); } return result; } }

return list.stream().mapToInt(Integer::intValue).toArray();

---

3. LCR 150. 彩灯装饰记录 II——I.打印二叉树

题目跳转： leetcode /problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/description/

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List<List<Integer>> decorateRecord(TreeNode root) { if(root==null)return new ArrayList<>(); //层序遍历 List<List<Integer>> result = new ArrayList<>(); Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while(!queue.isEmpty()){ int k = queue.size(); List<Integer> arrayList = new ArrayList<>(); for(int i = 0;i < k;i++){ TreeNode temp = queue.poll(); arrayList.add(temp.val); if(temp.left!=null)queue.add(temp.left); if(temp.right!=null)queue.add(temp.right); } result.add(arrayList); } return result; } }

---

4. LCR 151. 彩灯装饰记录 III——II.打印二叉树

题目跳转： leetcode /problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/description/

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List<List<Integer>> decorateRecord(TreeNode root) { if(root==null)return new ArrayList<>(); //层序遍历 List<List<Integer>> result = new ArrayList<>(); boolean flag =true; Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while(!queue.isEmpty()){ int k = queue.size(); List<Integer> arrayList = new ArrayList<>(); for(int i = 0;i < k;i++){ TreeNode temp = queue.poll(); arrayList.add(temp.val); if(temp.left!=null)queue.add(temp.left); if(temp.right!=null)queue.add(temp.right); } if(flag){ result.add(arrayList); flag = false; } else{ Collections.reverse(arrayList); result.add(arrayList); flag = true; } } return result; } }

---

5. LCR 152. 验证二叉搜索树的后序遍历序列——二叉搜索树的后序遍历序列

题目跳转： leetcode /problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/description/

class Solution { // 要点：二叉搜索树中根节点的值大于左子树中的任何一个节点的值，小于右子树中任何一个节点的值，子树也是 public boolean verifyTreeOrder(int[] postorder) { if (postorder.length < 2) return true; return verify(postorder, 0, postorder.length - 1); } // 递归实现 private boolean verify(int[] postorder, int left, int right){ if (left >= right) return true; // 当前区域不合法的时候直接返回true就好 int rootValue = postorder[right]; // 当前树的根节点的值 int k = left; while (k < right && postorder[k] < rootValue){ // 从当前区域找到第一个大于根节点的，说明后续区域数值都在右子树中 k++; } for (int i = k; i < right; i++){ // 进行判断后续的区域是否所有的值都是大于当前的根节点，如果出现小于的值就直接返回false if (postorder[i] < rootValue) return false; } // 当前树没问题就检查左右子树 if (!verify(postorder, left, k - 1)) return false; // 检查左子树 if (!verify(postorder, k, right - 1)) return false; // 检查右子树 return true; // 最终都没问题就返回true } }

---

6. LCR 153. 二叉树中和为目标值的路径——二叉树中和为某一值的路径

题目跳转： leetcode /problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/description/

学一下dfs的模板吧~~

function dfsTemplate(root) { //存储最终结果 let res; //初始化当前结果 let start; //构造递归函数dfs,通常参数为当前节点和当前结果 let dfs = function (node, currentResult) { //终止条件返回判断 if (node == null) { return; } //更新当前结果currentResult //若到达末尾叶子结点，进行最优结果更新 if (node.left == null && node.right == null) { //update res } //左右子树递归 dfs(node.left, currentResult); dfs(node.right, currentResult); } dfs(root, start); return res; } /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { List<List<Integer>> result = new ArrayList<>(); public List<List<Integer>> pathTarget(TreeNode root, int target) { dfs(root,target,new ArrayList<>()); return result; } public void dfs(TreeNode root,int target,List<Integer> list){ if(root == null) return; list.add(root.val); if (root.left == null&& root.right == null&& target == root.val){ result.add(new ArrayList<>(list)); } dfs(root.left, target - root.val,list); dfs(root.right, target - root.val, list); list.remove(list.size()-1); } }

---

7. LCR 154. 复杂链表的复制——复杂链表的复制

题目跳转： leetcode /problems/fu-za-lian-biao-de-fu-zhi-lcof/description/

让我看看谁return head了

如果直接返回啦，你知道不行，面试官问你为什么不行？你要答出关键词！！！浅拷贝与深拷贝

哈希表！

/* // Definition for a Node. class Node { int val; Node next; Node random; public Node(int val) { this.val = val; this.next = null; this.random = null; } } */ class Solution { public Node copyRandomList(Node head) { if(head==null) return head; HashMap<Node,Node> hashMap = new HashMap<>(); Node cur = head; while(cur!=null){ hashMap.put(cur,new Node(cur.val)); cur = cur.next; } Node temp = head; while(temp!=null){ hashMap.get(temp).next = hashMap.get(temp.next); hashMap.get(temp).random = hashMap.get(temp.random); temp = temp.next; } return hashMap.get(head); } }

---

8. LCR 155. 将二叉搜索树转化为排序的双向链表——二叉搜索树与双向链表

题目跳转： leetcode /problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/description/

class Solution { public Node treeToDoublyList(Node root) { if(root == null)return null; Stack<Node> stack = new Stack<>(); Node preNode = null; Node newHead = null; stack.push(root); while(!stack.isEmpty()){ Node temp = stack.pop(); if(temp!=null){ if(temp.right!=null) stack.push(temp.right); stack.push(temp); stack.push(null); if(temp.left!=null) stack.push(temp.left); } else{ Node tnode= stack.pop(); if(preNode==null){ preNode = tnode; preNode.left = tnode; preNode.right = tnode; } else{ tnode.left = preNode; preNode.right = tnode; preNode = tnode; } if(newHead==null){ newHead = tnode; newHead.left = tnode; newHead.right = tnode; } else{ newHead.left = preNode; preNode.right = newHead; } } } return newHead; } } class Solution { // 1. 中序，递归，来自解题大佬 Node pre, head; public Node treeToDoublyList(Node root) { // 边界值 if(root == null) return null; dfs(root); // 题目要求头尾连接 head.left = pre; pre.right = head; // 返回头节点 return head; } void dfs(Node cur) { // 递归结束条件 if(cur == null) return; dfs(cur.left); // 如果pre为空，就说明是第一个节点，头结点，然后用head保存头结点，用于之后的返回 if (pre == null) head = cur; // 如果不为空，那就说明是中间的节点。并且pre保存的是上一个节点， // 让上一个节点的右指针指向当前节点 else if (pre != null) pre.right = cur; // 再让当前节点的左指针指向父节点，也就连成了双向链表 cur.left = pre; // 保存当前节点，用于下层递归创建 pre = cur; dfs(cur.right); } }

---

9. LCR 156. 序列化与反序列化二叉树——序列化二叉树

题目跳转： leetcode /problems/xu-lie-hua-er-cha-shu-lcof/description/

public String serialize(TreeNode root) { if(root == null){ return "null,"; } String res = root.val + ","; res += serialize(root.left); res += serialize(root.right); return res; } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { String[] arr = data.split(","); Queue<String> queue = new LinkedList<String>(); for(int i = 0; i < arr.length; i++){ queue.offer(arr[i]); } return help(queue); } public TreeNode help(Queue<String> queue){ String val = queue.poll(); if(val.equals("null")){ return null; } TreeNode root = new TreeNode(Integer.valueOf(val)); root.left = help(queue); root.right = help(queue); return root; }

---

10. LCR 157. 套餐内商品的排列顺序——字符串的排列

题目跳转： leetcode /problems/zi-fu-chuan-de-pai-lie-lcof/description/

class Solution { public List<String> result = new ArrayList<>(); public String[] goodsOrder(String goods) { char[] chars = goods.toCharArray(); Arrays.sort(chars); StringBuilder stringBuilder = new StringBuilder(); boolean [] visited = new boolean[goods.length()]; backTrack(stringBuilder,chars,visited); return result.toArray(new String[0]); } public void backTrack(StringBuilder stringBuilder,char [] words,boolean [] visited){ if(stringBuilder.length()==words.length){ result.add(stringBuilder.toString()); return; } for (int i = 0; i < words.length; i++) { if(i!=0&&words[i]==words[i-1]&&!visited[i-1]){ continue; } if(!visited[i]){ stringBuilder.append(words[i]); visited[i] = true; backTrack(stringBuilder,words,visited); stringBuilder.deleteCharAt(stringBuilder.length()-1); visited[i] = false; } } } }

在Java中，result.toArray(new String[0]) 是将ArrayList result 转换为字符串数组的一种常见方式。这是在Java集合框架中使用的惯用方法。

具体来说，result.toArray() 返回一个包含ArrayList中所有元素的Object数组。但是，由于泛型擦除的存在，你可能无法直接得到一个泛型数组，比如 String[]。因此，通常会传递一个具有相同类型的空数组作为参数，以确保返回的是正确类型的数组。

在这里，new String[0] 是创建了一个空的String数组，然后传递给 toArray() 方法，告诉它要返回一个String类型的数组。实际上，这个空数组只是用于获取数组的类型信息，它不会被修改或使用。

在Java中，StringBuilder 类提供了 deleteCharAt(int index) 方法，用于删除指定索引位置的字符。该方法的语法是：

public StringBuilder deleteCharAt(int index)

其中，index 参数是要删除的字符的索引位置。索引从0开始，表示字符串中的第一个字符。删除后，StringBuilder的长度将减少一个字符。

例如，假设有一个StringBuilder对象：

StringBuilder sb = new StringBuilder("Hello");

如果你想删除字符串中的第二个字符（索引为1），可以使用 deleteCharAt() 方法：

sb.deleteCharAt(1);

这将使StringBuilder对象的内容变为 “Helo”，即删除了索引为1的字符。请注意，这个方法是在原始StringBuilder对象上直接操作的，而不是创建一个新的StringBuilder对象。

---