莘县网站开发,中升乙源建设公司网站,深圳微商城网站制作,副业做网站程序《剑指Offer》笔记题解思路技巧优化_Part_4 #x1f60d;#x1f60d;#x1f60d; 相知#x1f64c;#x1f64c;#x1f64c; 相识#x1f622;#x1f622;#x1f622; 开始刷题1. LCR 148. 验证图书取出顺序——栈的压入、弹出序列2. LCR 14… 《剑指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.length1)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(slowputIn.length) return true;flag[i] true;int temp i;while(temp0flag[temp]){temp--;}while(temp0putIn[temp]takeOut[slow]){slow;flag[temp] true;while(temp0flag[temp]){temp--;}}}}for(int i putIn.length-1;i0;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) {StackInteger 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(rootnull)return new int[0];//层序遍历ListInteger arrayList new ArrayList();QueueTreeNode 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 ListListInteger decorateRecord(TreeNode root) {if(rootnull)return new ArrayList();//层序遍历ListListInteger result new ArrayList();QueueTreeNode queue new LinkedList();queue.add(root);while(!queue.isEmpty()){int k queue.size();ListInteger 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 ListListInteger decorateRecord(TreeNode root) {if(rootnull)return new ArrayList();//层序遍历ListListInteger result new ArrayList();boolean flag true;QueueTreeNode queue new LinkedList();queue.add(root);while(!queue.isEmpty()){int k queue.size();ListInteger 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 {ListListInteger result new ArrayList();public ListListInteger pathTarget(TreeNode root, int target) {dfs(root,target,new ArrayList());return result;}public void dfs(TreeNode root,int target,ListInteger 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(headnull) return head;HashMapNode,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;StackNode 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(preNodenull){preNode tnode;preNode.left tnode;preNode.right tnode;}else{tnode.left preNode;preNode.right tnode;preNode tnode;}if(newHeadnull){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(,);QueueString queue new LinkedListString();for(int i 0; i arr.length; i){queue.offer(arr[i]);}return help(queue);
}
public TreeNode help(QueueString 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 ListString 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!0words[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对象。
