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

《剑指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. 验证图书取出顺序——栈的压入、弹出序列

题目跳转：https://leetcode.cn/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——从上到下打印二叉树

题目跳转：https://leetcode.cn/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.打印二叉树

题目跳转：https://leetcode.cn/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.打印二叉树

题目跳转：https://leetcode.cn/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. 验证二叉搜索树的后序遍历序列——二叉搜索树的后序遍历序列

题目跳转：https://leetcode.cn/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++){ // 进行判断后续的区域是否所有的值都是大于当前的根节点，如果出现小于的值就直接返回falseif (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. 二叉树中和为目标值的路径——二叉树中和为某一值的路径

题目跳转：https://leetcode.cn/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. 复杂链表的复制——复杂链表的复制

题目跳转：https://leetcode.cn/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. 将二叉搜索树转化为排序的双向链表——二叉搜索树与双向链表

题目跳转：https://leetcode.cn/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. 序列化与反序列化二叉树——序列化二叉树

题目跳转：https://leetcode.cn/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. 套餐内商品的排列顺序——字符串的排列

题目跳转：https://leetcode.cn/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对象。