当前位置: 首页 > news >正文

算法解析-经典150(链表、二叉树)

文章目录

  • 链表
    • 1.环形链表
        • 1.答案
        • 2.思路
    • 2.两数相加
        • 1.答案
        • 2.思路
    • 3.合并两个有序链表
        • 1.答案
        • 2.思路
    • 4.反转链表 II
        • 1.答案
        • 2.思路
    • 5.反转链表
        • 1.答案
        • 2.思路
    • 6.K 个一组翻转链表
        • 1.答案
        • 2.思路
    • 7.删除链表的倒数第 N 个结点
        • 1.答案
        • 2.思路
    • 8.删除排序链表中的重复元素 II
        • 1.答案
        • 2.思路
    • 9.旋转链表
        • 1.答案
        • 2.思路
    • 10.分隔链表
        • 1.答案
        • 2.思路
    • 11.LRU 缓存
        • 1.答案
        • 2.思路
  • 二叉树
    • 1.二叉树的最大深度
        • 1.答案
        • 2.思路
    • 2.相同的树
        • 1.答案
        • 2.思路
    • 3.翻转二叉树
        • 1.答案
        • 2.思路
    • 4.对称二叉树
        • 1.答案
        • 2.思路
    • 5.填充每个节点的下一个右侧节点指针 II
        • 1.答案
        • 2.思路
    • 6.二叉树展开为链表
        • 1.答案
        • 2.思路
    • 7.路径总和
        • 1.答案
        • 2.思路
    • 8.求根节点到叶节点数字之和
        • 1.答案
        • 2.思路
    • 9.二叉搜索树迭代器
        • 1.答案
        • 2.思路
    • 10.完全二叉树的节点个数
        • 1.答案
        • 2.思路
    • 11.二叉树的最近公共祖先
        • 1.答案
        • 2.思路
    • 12.二叉树的右视图
        • 1.答案
        • 2.思路
    • 13.二叉树的层平均值
        • 1.答案
        • 2.思路
    • 14.二叉树的层序遍历
        • 1.答案
        • 2.思路
    • 15.二叉树的锯齿形层序遍历
        • 1.答案
        • 2.思路
    • 16.二叉搜索树的最小绝对差
        • 1.答案
        • 2.思路
    • 17.二叉搜索树中第 K 小的元素
        • 1.答案
        • 2.思路
    • 17.验证二叉搜索树
        • 1.答案
        • 2.思路

链表

1.环形链表

1.答案
package com.sunxiansheng.classic150.g1;/*** Description: 141. 环形链表** @Author sun* @Create 2024/12/24 13:37* @Version 1.0*/
public class t141 {public boolean hasCycle(ListNode head) {// 快慢指针,慢的走一步,快的走两步,如果相遇就是有环ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;if (slow == fast) {return true;}}return false;}
}
2.思路

快慢指针,慢的走一步,快的走两步,如果相遇就是有环

2.两数相加

1.答案
package com.sunxiansheng.classic150.g1;/*** Description: 2. 两数相加** @Author sun* @Create 2024/12/24 13:44* @Version 1.0*/
public class t2 {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode res = new ListNode(-1); // 哑节点ListNode index = res;int carry = 0; // 进位ListNode t1 = l1;ListNode t2 = l2;while (t1 != null || t2 != null) {// 获取当前节点的值,若为空则为0int val1 = (t1 != null) ? t1.val : 0;int val2 = (t2 != null) ? t2.val : 0;// 计算当前节点的和及进位int sum = val1 + val2 + carry;carry = sum / 10;sum %= 10;// 添加当前节点res.next = new ListNode(sum);res = res.next;// 移动指针if (t1 != null) t1 = t1.next;if (t2 != null) t2 = t2.next;}// 检查是否还有未处理的进位if (carry > 0) {res.next = new ListNode(carry);}return index.next;}
}
2.思路

就是只要两个指针有一个不是null就可以获取节点值, 如果一个指针为空,那么节点值就是0,注意在计算和的时候需要加上上次的进位,并且还要计算当前进位以及和

3.合并两个有序链表

1.答案
package com.sunxiansheng.classic150.g1;/*** Description: 21. 合并两个有序链表** @Author sun* @Create 2024/12/24 14:37* @Version 1.0*/
public class t21 {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {// 哨兵节点ListNode dummy = new ListNode(-1);ListNode temp = dummy;while (list1 != null && list2 != null) {if (list1.val <= list2.val) {temp.next = new ListNode(list1.val);temp = temp.next;list1 = list1.next;} else {temp.next = new ListNode(list2.val);temp = temp.next;list2 = list2.next;}}// 到这就表明有一个为null了temp.next = list1 == null ? list2 : list1;return dummy.next;}
}
2.思路

就是比较两个节点,谁小谁就放到结果后面,最后将剩余的整条链表接到结果后面即可

4.反转链表 II

1.答案
package com.sunxiansheng.classic150.g1;import java.util.jar.JarEntry;/*** Description: 92. 反转链表 II** @Author sun* @Create 2024/12/25 09:10* @Version 1.0*/
public class t92 {public ListNode reverseBetween(ListNode head, int left, int right) {// 找到left的前一个节点ListNode dummy = new ListNode(0);dummy.next = head;ListNode prev = dummy;for (int i = 0; i < left - 1; i++) {prev = prev.next;}ListNode start = prev.next;ListNode then = start.next;for (int i = 0; i < right - left; i++) {start.next = then.next;then.next = prev.next;prev.next = then;then = start.next;}return dummy.next;}
}
2.思路

要想反转链表,就要找到三个东西,prev,start,then,然后套公式,假如有三个节点就循环两次即可

5.反转链表

1.答案
package com.sunxiansheng.classic150.g1;/*** Description: 206. 反转链表** @Author sun* @Create 2024/12/25 09:57* @Version 1.0*/
public class t206 {public ListNode reverseList(ListNode head) {if (head == null) {return head;}ListNode dummy = new ListNode(-1);dummy.next = head;// 三要素ListNode prev = dummy;ListNode start = head;ListNode then = head.next;// 套公式,假如五个节点需要循环四次!while (start.next != null) {start.next = then.next;then.next = prev.next;prev.next = then;then = start.next;}return dummy.next;}
}
2.思路

三要素:prev,start,then,套公式,假如五个节点需要循环四次!

6.K 个一组翻转链表

1.答案
package com.sunxiansheng.classic150.g1;/*** Description: 25. K 个一组翻转链表** @Author sun* @Create 2024/12/25 10:04* @Version 1.0*/
public class t25 {public ListNode reverseKGroup(ListNode head, int k) {// 创建哨兵节点ListNode dummy = new ListNode(-1);dummy.next = head;ListNode prev = dummy;while (true) {// 检查是否有足够的节点可以反转ListNode temp = prev;int count = 0;while (temp.next != null) {count ++;temp = temp.next;}// 只要没有足够的节点,就breakif (count < k) {break;}// 到这里就可以反转一组链表了ListNode start = prev.next;ListNode then = start.next;reverse(prev, start, then, k);// 反转之后更新prevprev = start;}return dummy.next;}/*** 反转一组链表** @param prev* @param start* @param then*/private void reverse(ListNode prev, ListNode start, ListNode then, int k) {for (int i = 0; i < k - 1; i++) {start.next = then.next;then.next = prev.next;prev.next = then;then = start.next;}}
}
2.思路

首先要知道反转一组链表就是标准公式执行k-1次,然后要知道反转完链表之后的指针状态

1:prev

2:start

3:then

4

反转一次后,prev不变,start和then向后移动一位

1:prev

2

3:start

4:then

这样在反转完一组链表之后,更新prev=start即可

7.删除链表的倒数第 N 个结点

1.答案
package com.sunxiansheng.classic150.g1;/*** Description: 19. 删除链表的倒数第 N 个结点** @Author sun* @Create 2024/12/25 13:10* @Version 1.0*/
public class t19 {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(-1);dummy.next = head;getNodeNum(dummy, n);return dummy.next;}public static int getNodeNum(ListNode node, int n) {if (node.next == null) {// 倒数第一个节点return 1;} else {int nodeNum = getNodeNum(node.next, n);// 如果这个节点数就是要删除的就进行删除if (n == nodeNum) {if (n == 1) {node.next = null;} else {node.next = node.next.next;}}return nodeNum + 1;}}
}
2.思路

使用递归来完成,递归从最后一个节点开始计数,也就是返回当前节点是倒数第几个节点,然后进行删除操作即可

8.删除排序链表中的重复元素 II

1.答案
package com.sunxiansheng.classic150.g1;/*** Description: 82. 删除排序链表中的重复元素 II** @Author sun* @Create 2024/12/25 13:21* @Version 1.0*/
public class t82 {public ListNode deleteDuplicates(ListNode head) {ListNode dummy = new ListNode(-1);dummy.next = head;ListNode temp = dummy;while (temp.next != null) {ListNode right = temp.next;// 首先判断当前元素是不是重复元素if (right.next != null && right.val == right.next.val) {// 如果是重复元素,就将right移动到不重复的元素的位置while (right.next != null && right.val == right.next.val) {right = right.next;}right = right.next;// 删除重复元素temp.next = right;// 然后temp就不用变了} else {// 如果不重复,那么temp正常移动temp = temp.next;}}return dummy.next;}
}
2.思路

使用虚拟节点进行正常遍历,首先判断当前元素是不是重复元素,如果是,就使用while移动到重复元素的最后一个元素的位置,并且再向后移动一个,让temp指向这个指针实现删除操作

9.旋转链表

1.答案
package com.sunxiansheng.classic150.g1;/*** Description: 61. 旋转链表** @Author sun* @Create 2024/12/25 13:47* @Version 1.0*/
public class t61 {public ListNode rotateRight(ListNode head, int k) {if (head == null || head.next == null) {return head;}ListNode[] find = new ListNode[1];ListNode dummy = new ListNode(-10);dummy.next = head;// 统计链表元素个数ListNode temp = dummy;int count = 0;while (temp.next != null) {count++;temp = temp.next;}if (k % count == 0) {return head;}findNode(dummy, k % count, find, dummy);return find[0];}/*** 找到倒数第k个节点,然后让倒数第k-1个节点指向null,并且让最后一个节点的next指向第一个节点** @param node* @param k* @param find*/public static int findNode(ListNode node, int k, ListNode[] find, ListNode dummy) {if (node.next == null) {node.next = dummy.next;return 1;} else {int nodeNum = findNode(node.next, k, find, dummy);// 表明当前节点的后一个节点是倒数第k个节点if (nodeNum == k) {// 记录节点find[0] = node.next;// 让当前节点指向nullnode.next = null;}return nodeNum + 1;}}
}
2.思路

递归找到倒数第k-1个节点,让他的next指向null,并且找到最后一个节点,让他的next指向第一个节点

10.分隔链表

1.答案
package com.sunxiansheng.classic150.g1;/*** Description: 86. 分隔链表** @Author sun* @Create 2024/12/25 14:21* @Version 1.0*/
public class t86 {public ListNode partition(ListNode head, int x) {// 两个链表,一个链表存储小于等于x的节点,另一个链表存储大于等于x的节点ListNode small = new ListNode(-1);ListNode big = new ListNode(-1);ListNode s = small;ListNode b = big;// 遍历链表ListNode dummy = new ListNode(-1);dummy.next = head;ListNode temp = dummy;while (temp.next != null) {// 取出当前元素ListNode cur = temp.next;if (cur.val < x) {s.next = cur;s = s.next;} else {b.next = cur;b = b.next;}temp = temp.next;}// 注意需要让大的节点的next为nullb.next = null;// 拼接链表s.next = big.next;return small.next;}
}
2.思路

使用两个链表,一个存小于x的元素,另一个存大于等于x的元素,最后拼接链表即可

11.LRU 缓存

1.答案
package com.sunxiansheng.classic150.g1;import java.util.HashMap;
import java.util.Map;/*** Description: 146. LRU 缓存** @Author sun* @Create 2024/12/25 14:47* @Version 1.1*/
public class LRUCache {/*** 节点*/class DLinkedNode {int key;int value;DLinkedNode prev;DLinkedNode next;public DLinkedNode() {}public DLinkedNode(int key, int value) {this.key = key;this.value = value;}}private Map<Integer, DLinkedNode> cache = new HashMap<>();private int size;private int capacity;private DLinkedNode head, tail;public LRUCache(int capacity) {this.size = 0;this.capacity = capacity;// 使用头结点和尾节点head = new DLinkedNode();tail = new DLinkedNode();head.next = tail;tail.prev = head;}/*** 获取值*/public int get(int key) {DLinkedNode node = cache.get(key);if (node == null) {return -1;}// 移动到头部moveToHead(node);return node.value;}/*** 插入或更新值*/public void put(int key, int value) {DLinkedNode node = cache.get(key);if (node == null) {// 如果不存在,新建节点DLinkedNode newNode = new DLinkedNode(key, value);cache.put(key, newNode);addToHead(newNode);size++;// 超出容量,移除尾部节点if (size > capacity) {DLinkedNode tailNode = removeTail();cache.remove(tailNode.key);size--;}} else {// 如果存在,更新值并移动到头部node.value = value;moveToHead(node);}}/*** 添加节点到头部*/private void addToHead(DLinkedNode node) {node.prev = head;node.next = head.next;head.next.prev = node;head.next = node;}/*** 移除节点*/private void removeNode(DLinkedNode node) {node.prev.next = node.next;node.next.prev = node.prev;}/*** 移动节点到头部*/private void moveToHead(DLinkedNode node) {removeNode(node);addToHead(node);}/*** 移除尾部节点*/private DLinkedNode removeTail() {DLinkedNode tailNode = tail.prev;removeNode(tailNode);return tailNode;}
}
2.思路

LRU缓存由双向链表和缓存的Map来实现

双向链表有四个参数:key,value,prev,next

Map的key是key,value是双向链表的节点

整体缓存的属性有Map,head,tail,大小和容量

注意首先实现四个方法,分别是从双向链表中删除元素,添加元素到头部,移动元素到头部,删除尾部节点

二叉树

1.二叉树的最大深度

1.答案
package com.sunxiansheng.classic150.g1;/*** Description: 104. 二叉树的最大深度** @Author sun* @Create 2024/12/26 10:13* @Version 1.0*/
public class t104 {public int maxDepth(TreeNode root) {if (root == null) {return 0;} else {int left = maxDepth(root.left);int right = maxDepth(root.right);// 左右子树的最大深度加1,就是当前子树的最大深度return Math.max(left, right) + 1;}}
}
2.思路

左右子树的最大深度加1,就是当前子树的最大深度

2.相同的树

1.答案
package com.sunxiansheng.classic150.g1;/*** Description: 100. 相同的树** @Author sun* @Create 2024/12/26 10:23* @Version 1.0*/
public class t100 {public static boolean isSameTree(TreeNode left, TreeNode right) {if (left == null && right == null) {return true;} else if (left == null || right == null) {return false;} else {// 首先比较当前两个节点是不是相同,if (left.val != right.val) {return false;}boolean leftTree = isSameTree(left.left, right.left);boolean rightTree = isSameTree(left.right, right.right);// 左右子树都要是相同的才可以return leftTree && rightTree;}}
}
2.思路

确认递归函数定义,参数传递状态,确认终止条件,对返回值进行处理

3.翻转二叉树

1.答案
package com.sunxiansheng.classic150.g1;/*** Description: 226. 翻转二叉树** @Author sun* @Create 2024/12/26 10:37* @Version 1.0*/
public class t226 {public TreeNode invertTree(TreeNode root) {if (root == null) {return null;} else {TreeNode left = invertTree(root.left);TreeNode right = invertTree(root.right);// 反转左右子树root.left = right;root.right = left;return root;}}
}
2.思路

从底向下, 反转左右子树

4.对称二叉树

1.答案
package com.sunxiansheng.classic150.g1;/*** Description: 101. 对称二叉树** @Author sun* @Create 2024/12/26 10:42* @Version 1.0*/
public class t101 {public boolean isSymmetric(TreeNode root) {if (root == null) {return true;}return check(root.left, root.right);}// 检查左右子树是否是对称的public static boolean check(TreeNode left, TreeNode right) {if (left == null && right == null) {return true;} else if (left == null || right == null) {return false;} else {if (left.val != right.val) {return false;}boolean leftTree = check(left.right, right.left);boolean rightTree = check(right.right, left.left);return leftTree && rightTree;}}
}
2.思路

跟相同的树的思路类似的,不过需要单独写一个递归函数来检查左右子树是否对称

5.填充每个节点的下一个右侧节点指针 II

1.答案
package com.sunxiansheng.classic150.g1;import javax.swing.*;
import java.util.LinkedList;
import java.util.Queue;/*** Description: 117. 填充每个节点的下一个右侧节点指针 II** @Author sun* @Create 2024/12/26 10:52* @Version 1.0*/
public class t117 {class Node {public int val;public Node left;public Node right;public Node next;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, Node _left, Node _right, Node _next) {val = _val;left = _left;right = _right;next = _next;}};public Node connect(Node root) {if (root == null) {return null;}// 队列Queue<Node> queue = new LinkedList<>();// 根节点入队queue.offer(root);while (!queue.isEmpty()) {// 当前层的节点数int size = queue.size();// 前一个节点Node prev = null;// 遍历当前层节点for (int i = 0; i < size; i++) {// 取出当前节点Node node = queue.poll();if (prev == null) {prev = node;} else {prev.next = node;prev = node;}// 左右节点入队if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}}return root;}
}
2.思路

层序遍历即可,记录前一个节点,让前一个节点的next指向当前节点

6.二叉树展开为链表

1.答案
package com.sunxiansheng.classic150.g1;/*** Description: 114. 二叉树展开为链表** @Author sun* @Create 2024/12/26 11:04* @Version 1.0*/
public class t114 {TreeNode prev;// 反前序遍历public void flatten(TreeNode root) {if (root == null) {return;} else {flatten(root.right);flatten(root.left);root.left = null;root.right = prev;prev = root;}}
}
2.思路

反前序遍历

7.路径总和

1.答案
package com.sunxiansheng.classic150.g1;/*** Description: 112. 路径总和** @Author sun* @Create 2024/12/26 12:18* @Version 1.0*/
public class t112 {public boolean hasPathSum(TreeNode root, int targetSum) {if (root == null) {return false;}int[] cur = new int[2];backtrace(root, targetSum, cur);return cur[1] == 10000;}public static void backtrace(TreeNode root, int targetSum, int[] curSum) {if (root.left == null && root.right == null) {// 计算和curSum[0] += root.val;// 判断是否是结果if (curSum[0] == targetSum) {// 使用curSum[1]作为标记curSum[1] = 10000;}// 回溯curSum[0] -= root.val;} else {// 计算和curSum[0] += root.val;// 传递状态if (root.left != null) {backtrace(root.left, targetSum, curSum);}if (root.right != null) {backtrace(root.right, targetSum, curSum);}// 回溯curSum[0] -= root.val;}}
}
2.思路

用到了回溯法,核心就是参数记录路径,传递参数 ,当遇到叶子节点时计算结果并回溯

8.求根节点到叶节点数字之和

1.答案
package com.sunxiansheng.classic150.g1;/*** Description: 129. 求根节点到叶节点数字之和** @Author sun* @Create 2024/12/26 12:40* @Version 1.0*/
public class t129 {public int sumNumbers(TreeNode root) {int[] sum = new int[1];backtrace(root, new StringBuilder(), sum);return sum[0];}public static void backtrace(TreeNode root, StringBuilder path, int[] sum) {if (root.right == null && root.left == null) {// 叶子节点// 记录路径path.append(root.val);// 计算结果sum[0] += Integer.parseInt(path.toString());// 回溯path.deleteCharAt(path.length() - 1);} else {// 记录路径path.append(root.val);// 传递状态if (root.left != null) {backtrace(root.left, path, sum);}if (root.right != null) {backtrace(root.right, path, sum);}// 回溯path.deleteCharAt(path.length() - 1);}}
}
2.思路

就是回溯老套路了

9.二叉搜索树迭代器

1.答案
package com.sunxiansheng.classic150.g1;import java.util.ArrayList;
import java.util.List;/*** Description: 173. 二叉搜索树迭代器** @Author sun* @Create 2024/12/26 12:56* @Version 1.0*/
public class BSTIterator {private List<Integer> arr;private int idx;public BSTIterator(TreeNode root) {idx = 0;arr = new ArrayList<>();middleOrder(root);}public int next() {return arr.get(idx++);}public boolean hasNext() {return idx < arr.size();}// 中序遍历,将结果放到数组中public void middleOrder(TreeNode root) {if (root == null) {return;} else {middleOrder(root.left);arr.add(root.val);middleOrder(root.right);}}
}
2.思路

就是先中序遍历到数组里面,然后根据方法的意思来编写迭代器即可

10.完全二叉树的节点个数

1.答案
package com.sunxiansheng.classic150.g1;/*** Description: 222. 完全二叉树的节点个数** @Author sun* @Create 2024/12/27 08:35* @Version 1.0*/
public class t222 {public int countNodes(TreeNode root) {int[] res = new int[1];count(root, res);return res[0];}private void count(TreeNode root, int[] res) {if (root == null) {return;} else {res[0]++;count(root.left, res);count(root.right, res);}}
}
2.思路

遍历一下统计数量即可

11.二叉树的最近公共祖先

1.答案
package com.sunxiansheng.classic150.g1;/*** Description: 236. 二叉树的最近公共祖先** @Author sun* @Create 2024/12/27 08:53* @Version 1.0*/
public class t236 {public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root == null) {return null;} else if (root == p || root == q){return root;} else {TreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p, q);// 都为空,则当前子树的公共祖先就是nullif (left == null && right == null) {return null;}// 一个为空,一个不为空,返回不为空的if (left == null || right == null) {return left == null ? right : left;}// 如果两个都不为空,则当前节点就是公共祖先return root;}}
}
2.思路

首先对递归函数进行定义,返回根节点为root的树对于节点p和q的公共祖先,然后对终止条件进行处理,如果根节点为空,那么公共祖先就为空,如果根节点为p或者q,就直接返回p或者q,最后对else进行处理,如果左右子树都返回空,就返回空,一个为空,一个不为空,就返回不为空的,两个都不为空,则当前节点就是公共祖先

12.二叉树的右视图

1.答案
package com.sunxiansheng.classic150.g1;import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;/*** Description: 199. 二叉树的右视图** @Author sun* @Create 2024/12/27 09:22* @Version 1.0*/
public class t199 {public List<Integer> rightSideView(TreeNode root) {List<Integer> res = new ArrayList<>();if (root == null) {return res;}// 队列Queue<TreeNode> queue = new LinkedList<>();// 根节点入队queue.offer(root);while (!queue.isEmpty()) {// 当前层的节点个数int size = queue.size();// 遍历当前层的节点for (int i = 0; i < size; i++) {TreeNode node = queue.poll();// 只要最后一个元素if (i == size - 1) {res.add(node.val);}// 左右子树if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}}return res;}
}
2.思路

层序遍历即可

13.二叉树的层平均值

1.答案
package com.sunxiansheng.classic150.g1;import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;/*** Description: 637. 二叉树的层平均值** @Author sun* @Create 2024/12/27 09:33* @Version 1.0*/
public class t637 {public List<Double> averageOfLevels(TreeNode root) {List<Double> res = new ArrayList<>();if (root == null) {return res;}// 层序遍历Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int n = queue.size();double sum = 0;for (int i = 0; i < n; i++) {TreeNode node = queue.poll();sum += node.val;if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}res.add(sum / n);}return res;}
}
2.思路

简单的层序遍历

14.二叉树的层序遍历

1.答案
package com.sunxiansheng.classic150.g1;import com.sun.org.apache.bcel.internal.generic.NOP;import javax.annotation.Resource;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;/*** Description: 102. 二叉树的层序遍历** @Author sun* @Create 2024/12/27 09:38* @Version 1.0*/
public class t102 {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> res = new ArrayList<>();if (root == null) {return res;}// 队列Queue<TreeNode> queue = new LinkedList<>();// 根节点入队queue.offer(root);while (!queue.isEmpty()) {// 当前层的节点数int size = queue.size();// 当前层的节点List<Integer> list = new ArrayList<>();// 遍历当前层的节点for (int i = 0; i < size; i++) {// 取出当前节点TreeNode node = queue.poll();list.add(node.val);// 左右节点入队if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}// 加入到结果res.add(list);}return res;}
}
2.思路

基本层序遍历

15.二叉树的锯齿形层序遍历

1.答案
package com.sunxiansheng.classic150.g1;import com.sun.org.apache.bcel.internal.generic.NOP;import javax.annotation.Resource;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;/*** Description: 103. 二叉树的锯齿形层序遍历** @Author sun* @Create 2024/12/27 09:38* @Version 1.0*/
public class t103 {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {List<List<Integer>> res = new ArrayList<>();if (root == null) {return res;}// 队列Queue<TreeNode> queue = new LinkedList<>();// 根节点入队queue.offer(root);// 是否向右遍历boolean toRight = true;while (!queue.isEmpty()) {// 当前层的节点数int size = queue.size();// 当前层的节点LinkedList<Integer> list = new LinkedList<>();// 遍历当前层的节点for (int i = 0; i < size; i++) {// 取出当前节点TreeNode node = queue.poll();// 根据标志来决定是添加到链表的头部还是尾部if (toRight) {list.addLast(node.val);} else {list.addFirst(node.val);}// 左右节点入队if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}// 加入到结果res.add(list);// 更改方向toRight = !toRight;}return res;}
}
2.思路

根据方向标识决定是添加到链表的头部还是尾部

16.二叉搜索树的最小绝对差

1.答案
package com.sunxiansheng.classic150.g1;import java.nio.file.Path;/*** Description: 530. 二叉搜索树的最小绝对差** @Author sun* @Create 2024/12/27 09:50* @Version 1.0*/
public class t530 {public int getMinimumDifference(TreeNode root) {// 核心,二叉搜索树的中序遍历是升序,那么最小差值一定是相邻的两个节点的差值int[] res = new int[2];res[0] = Integer.MAX_VALUE;// res[1]就是prevres[1] = -1;middleOrder(root, res);return res[0];}public static void middleOrder(TreeNode root, int[] res) {if (root == null) {return;} else {middleOrder(root.left, res);// root即为当前节点if (res[1] == -1) {res[1] = root.val;} else {// 计算差值并更新prevres[0] = Math.min(res[0], root.val - res[1]);res[1] = root.val;}middleOrder(root.right, res);}}
}
2.思路

利用二叉搜索树的中序遍历是升序这个特性来做即可,记录一下prev,求相邻两个节点的差值并记录最小差值

17.二叉搜索树中第 K 小的元素

1.答案
package com.sunxiansheng.classic150.g1;/*** Description: 230. 二叉搜索树中第 K 小的元素** @Author sun* @Create 2024/12/27 10:26* @Version 1.0*/
public class t230 {public int kthSmallest(TreeNode node, int k) {int[] res = new int[2];// res[0]是第k小的元素,res[1]是第几个元素middleOrder(node, k, res);return res[0];}public static void middleOrder(TreeNode root, int k, int[] res) {if (root == null) {return;} else {middleOrder(root.left, k, res);// root即为当前元素// 如果当前是第k个元素,记录结果直接returnif (++res[1] == k) {res[0] = root.val;return;}middleOrder(root.right, k, res);}}
}
2.思路

利用二叉搜索树的中序遍历是升序这个特性来做即可

17.验证二叉搜索树

1.答案
package com.sunxiansheng.classic150.g1;/*** Description: 98. 验证二叉搜索树** @Author sun* @Create 2024/12/27 10:33* @Version 1.0*/
public class t98 {public boolean isValidBST(TreeNode root) {Integer[] res = new Integer[2];// res[0]如果是null,则是二叉搜索树,res[1]存的是前一个节点的值middleOrder(root, res);return res[0] == null;}private void middleOrder(TreeNode root, Integer[] res) {if (root == null) {return;} else {middleOrder(root.left, res);if (res[1] == null) {res[1] = root.val;} else {// 判断是否满足要求if (!(root.val > res[1])) {res[0] = 1;return;}// 更新prevres[1] = root.val;}middleOrder(root.right, res);}}
}
2.思路

利用二叉搜索树的中序遍历是升序这个特性来做即可,直接中序遍历,在根做处理

相关文章:

算法解析-经典150(链表、二叉树)

文章目录 链表1.环形链表1.答案2.思路 2.两数相加1.答案2.思路 3.合并两个有序链表1.答案2.思路 4.反转链表 II1.答案2.思路 5.反转链表1.答案2.思路 6.K 个一组翻转链表1.答案2.思路 7.删除链表的倒数第 N 个结点1.答案2.思路 8.删除排序链表中的重复元素 II1.答案2.思路 9.旋…...

蓝桥杯-Python

1. 冒泡排序 算法步骤&#xff1a; 比较相邻元素&#xff0c;如果第一个大于第二个则交换从左往右遍历一遍&#xff0c;重复第一步&#xff0c;可以保证最大的元素在最后面重复上述操作&#xff0c;可以得到第二大、第三大、… n int(input()) a list(map(int, input()…...

语雀导入md文件图片丢失

经常被困扰是&#xff0c;从语雀导入md文件&#xff0c;即使知道把md文件和本地图片文件夹打包成zip进行导入&#xff0c;还是出现图片丢失 解决方式1&#xff1a; 把图片和md文件放到同个目录下&#xff0c;重新打包成zip文件&#xff0c;导入后有图片了 解决方式2&#xf…...

【Logstash02】企业级日志分析系统ELK之Logstash 输入 Input 插件

Logstash 使用 Logstash 命令 官方文档 https://www.elastic.co/guide/en/logstash/current/first-event.html #各种插件 https://www.elastic.co/guide/en/logstash/current/input-plugins.html https://www.elastic.co/guide/en/logstash/current/filter-plugins.html htt…...

HP 电脑开机黑屏 | 故障判断 | BIOS 恢复 | BIOS 升级

注&#xff1a;本文为 “HP 电脑开机黑屏 | 故障判断 | BIOS 恢复 | BIOS 升级” 相关文章合辑。 引文图片 csdn 转储异常&#xff0c;重传。 篇 1&#xff1a;Smart-Baby 回复中给出故障现象判断参考 篇 2、篇3 &#xff1a;HP 官方 BIOS 恢复、升级教程 开机黑屏&#xff0c…...

Nginx代理本地exe服务http为https

Nginx代理本地exe服务http为https 下载NginxNginx命令exe服务http代理为https 下载Nginx 点击下载Nginx 下载好之后是一个压缩包&#xff0c;解压放到没有中文的路径下就可以了 Nginx命令 调出cmd窗口cd到安装路径 输入&#xff1a;nginx -v 查看版本 nginx -h&#xff…...

enzymejest TDD与BDD开发实战

一、前端自动化测试需要测什么 1. 函数的执行逻辑&#xff0c;对于给定的输入&#xff0c;输出是否符合预期。 2. 用户行为的响应逻辑。 - 对于单元测试而言&#xff0c;测试粒度较细&#xff0c;需要测试内部状态的变更与相应函数是否成功被调用。 - 对于集成测试而言&a…...

Linux菜鸟级常用的基本指令和基础知识

前言:很多Linux初学者都会头疼于指令太多记不住&#xff0c;笔者刚学习Linux时也是如此&#xff0c;学习Linux指令时&#xff0c;学了后面的指令&#xff0c;前面的指令也会忘的差不多了&#xff0c;针对于以上这些情况&#xff0c;笔者今天来分享一篇Linux菜鸟级的常用指令的博…...

Spark创建多种数据格式的DataFrame

假如我们要通过RDD[Row]创建一个包含多个列的DataFrame&#xff0c;重点是列的数据类型可能会包含多个&#xff0c;这时候需要有一点技巧。 | uid | user_name | age | income | |:----|:----------|:----|:-------| | 1111 | nituchao | 21 | 123.0 | 这个DataFrame里包含…...

C语言:指针

1. 什么是指针&#xff1f; 在C语言中&#xff0c;指针是一个变量&#xff0c;用于存储另一个变量的内存地址。指针不是直接保存值&#xff0c;而是保存数据所在的内存位置。 语法&#xff1a; type *pointer_name; 例如&#xff1a; int *ptr; 在这个例子中&#xff0c;pt…...

kafka生产者专题(原理+拦截器+序列化+分区+数据可靠+数据去重+事务)

目录 生产者发送数据原理参数说明代码示例&#xff08;同步发送数据&#xff09;代码示例&#xff08;异步&#xff09; 异步和同步的区别同步发送定义与流程特点 异步发送定义与流程特点 异步回调描述代码示例 拦截器描述代码示例 消息序列化描述代码示例&#xff08;自定义序…...

谷歌2025年AI战略与产品线布局

在2024年12月的战略会议上,谷歌高层向员工描绘了2025年的宏伟蓝图,特别是在人工智能(AI)领域。这一年被定位为AI发展的关键转折点,谷歌计划通过一系列新产品和创新来巩固其在全球科技领域的领导地位。本文将深入探讨谷歌的2025年AI战略、重点产品以及竞争策略。 一、整体…...

Kernel Stack栈溢出攻击及保护绕过

前言 本文介绍Linux内核的栈溢出攻击&#xff0c;和内核一些保护的绕过手法&#xff0c;通过一道内核题及其变体从浅入深一步步走进kernel世界。 QWB_2018_core 题目分析 start.sh qemu-system-x86_64 \-m 128M \-kernel ./bzImage \-initrd ./core.cpio \-append "…...

QT-窗口嵌入外部exe

窗口类&#xff1a; #pragma once #include <QApplication> #include <QWidget> #include <QVBoxLayout> #include <QProcess> #include <QTimer> #include <QDebug> #include <Windows.h> #include <QWindow> #include <…...

38-其他地方使用模式

38-其他地方使用模式 模式除了可以在 match 表达式中使用外&#xff0c;还可以使用在变量定义&#xff08;等号左侧是个模式&#xff09;和 for in 表达式&#xff08;for 关键字和 in 关键字之间是个模式&#xff09;中。 但是&#xff0c;并不是所有的模式都能使用在变量定…...

才气小波与第一性原理

才气小波与第一性原理 才气小波与第一性原理具身智能云藏山鹰类型物热力学第二定律的动力机械外骨骼诠释才气小波导引社会科学概论软凝聚态数学意气实体过程王阳明代数Wangyangmingian王阳明算符才气语料库命运社会科学概论意气实体过程业务分层框架示例 才气小波与第一性原理 …...

104周六复盘 (188)UI

1、早上继续看二手书的一个章节&#xff0c;程序开发流程、引擎、AI等内容&#xff0c; 内容很浅&#xff0c;基本上没啥用&#xff0c;算是复习。 最大感触就是N年前看同类书的里程碑、AI相关章节时&#xff0c;会感觉跟自己没啥关系&#xff0c; 而如今则密切相关&#xf…...

CDP集群安全指南-动态数据加密

[〇]关于本文 集群的动态数据加密主要指的是加密通过网络协议传输的数据&#xff0c;防止数据在传输的过程中被窃取。由于大数据涉及的主机及服务众多。你需要更具集群的实际环境来评估需要为哪些环节实施动态加密。 这里介绍一种通过Cloudera Manager 的Auto-TLS功能来为整个…...

C# 设计模式:装饰器模式与代理模式的区别

C# 设计模式&#xff1a;装饰器模式与代理模式的区别 在软件设计中&#xff0c;装饰器模式&#xff08;Decorator Pattern&#xff09;和代理模式&#xff08;Proxy Pattern&#xff09;都是结构型设计模式&#xff0c;它们的目的都是通过对对象进行包装&#xff0c;来增加或改…...

[深度学习] 大模型学习1-大语言模型基础知识

大语言模型&#xff08;Large Language Model&#xff0c;LLM&#xff09;是一类基于Transformer架构的深度学习模型&#xff0c;主要用于处理与自然语言相关的各种任务。简单来说&#xff0c;当用户输入文本时&#xff0c;模型会生成相应的回复或结果。它能够完成许多任务&…...

GitLab集成Runner详细版--及注意事项汇总【最佳实践】

一、背景 看到网上很多用户提出的runner问题其实实际都不是问题&#xff0c;不过是因为对runner的一些细节不清楚导致了误解。本文不系统性的介绍GitLab-Runner&#xff0c;因为这类文章写得好的特别多&#xff0c;本文只汇总一些常几的问题/注意事项。旨在让新手少弯路。 二、…...

STM32-笔记34-4G遥控灯

4G接线 一、项目需求 服务器通过4G模块远程遥控开关灯。 二、项目实现 复制项目文件夹38-wifi控制风扇项目 重命名为39-4G遥控点灯 打开项目文件 加载文件 main.c #include "sys.h" #include "delay.h" #include "led.h" #include "ua…...

PHP 使用集合 处理复杂数据 提升开发效率

文章精选推荐 1 JetBrains Ai assistant 编程工具让你的工作效率翻倍 2 Extra Icons&#xff1a;JetBrains IDE的图标增强神器 3 IDEA插件推荐-SequenceDiagram&#xff0c;自动生成时序图 4 BashSupport Pro 这个ides插件主要是用来干嘛的 &#xff1f; 5 IDEA必装的插件&…...

AI代码开发实践-微信小程序开发

接上回&#xff0c;本人参加了一次小孩学校组织的护学岗&#xff0c;萌生了开发一个微信小程序的水印相机的想法&#xff0c;说干就干。 最近也是在学习用AI编程&#xff0c;索性之前也用一点&#xff0c;今天就尝试一下 工具选择&#xff0c;环境搭建 阿里-通义灵码 通义灵…...

【网络安全 | 漏洞挖掘】私有项目中的账户接管过程

未经许可,不得转载。 正文 该程序包含多个通配符目标。在逐一搜索后,我最终发现了一个具有 P4 严重级别的 IDOR 漏洞(不正确的直接对象引用),允许我删除其他用户在帖子中的评论。 其中一个目标是一个只有单个域名的网站,提供注册、登录和重置密码功能。我尝试寻找任何可…...

【算法不挂科】算法期末考试【选择题专项练习】<多单元汇总>

前言 大家好吖&#xff0c;欢迎来到 YY 滴算法不挂科系列 &#xff0c;热烈欢迎&#xff01; 本章主要内容面向接触过C的老铁 主要内容含&#xff1a; 一.选择题 【1】算法绪论 1.算法与程序的区别是( ) A.输出 B.输入 C.确定性 D.有穷性 D 2.算法复杂度分析的两种基本方法…...

分布式消息中间件有哪些知名的产品

首先是Apache Kafka&#xff0c;它是一个分布式流处理平台&#xff0c;专注于高性能、低延迟的实时数据管道和流应用。Kafka通过分区和复制机制实现了高可用性和容错性&#xff0c;支持消息的持久化存储和高效的数据传输。其强大的生态系统还提供了丰富的客户端库和集成工具&am…...

kubernets基础入门

首先通过Kubernets架构图来认识Kubernets各个功能组件之间是怎么相互关联配合工作的。 一、Kubernets架构图&#xff1a; 通过上图来介绍集群功能组件通信详细过程&#xff1a; kubernetes api server 作为集群的核心&#xff0c;负责集群各功能模块之间的通信。集群内的各个功…...

【数据库初阶】MySQL数据类型

&#x1f389;博主首页&#xff1a; 有趣的中国人 &#x1f389;专栏首页&#xff1a; 数据库初阶 &#x1f389;其它专栏&#xff1a; C初阶 | C进阶 | 初阶数据结构 亲爱的小伙伴们&#xff0c;大家好&#xff01;在这篇文章中&#xff0c;我们将深入浅出地为大家讲解 MySQL…...

(九千七-星河襟)椭圆曲线加密(ECC, Elliptic Curve Cryptography)及其例题

椭圆曲线加密&#xff08;ECC&#xff09;是一种基于椭圆曲线数学的公钥加密技术。它提供了一种高效的加密方法&#xff0c;能够在较小的密钥长度下实现与传统加密算法&#xff08;如RSA&#xff09;相同的安全级别。以下是ECC的主要特点和工作原理的总结&#xff1a; 1. 基本…...

LookingGlass使用

背景 Looking Glass 是一款开源应用程序&#xff0c;可以直接使用显卡直通的windows虚拟机。 常见环境是Linux hostwindows guest&#xff0c;基本部署结构图&#xff1a; 编译 git clone --recursive https://github.com/gnif/LookingGlass.git编译client mkdir client/b…...

ArcGIS Server 10.2授权文件过期处理

新的一年&#xff0c;arcgis server授权过期了&#xff0c;服务发不不了。查看ecp授权文件&#xff0c;原来的授权日期就到2024.12.31日。好吧&#xff0c;这里直接给出处理方法。 ArcGIS 10.2安装时&#xff0c;有的破解文件中会有含一个这样的注册程序&#xff0c;没有的话&…...

js es6 reduce函数, 通过规格生成sku

const specs [{ name: 颜色, values: [红色, 蓝色, 绿色] },{ name: 尺寸, values: [S, M, L] } ];function generateSKUs(specs) {return specs.reduce((acc, spec) > {const newAcc [];for (const combination of acc) {for (const value of spec.values) {newAcc.push(…...

Spring 事务底层原理

61 张图&#xff0c;剖析 Spring 事务&#xff0c;就是要钻到底&#xff01; 拜托&#xff01;面试请不要再问我 Transactional my&#xff1a; AOP Transactional PlatformTransactionManager&#xff1a;数据源隔离 TransactionInterceptor&#xff1a;拦截添加了注解的…...

ruoyi 分页 查询超出后还有数据; Mybatis-Plus 分页 超出后还有数据

修改&#xff1a;MybatisPlusConfig 类中 分页合理化修改为&#xff1a;paginationInnerInterceptor.setOverflow(false);...

基于Java的超级玛丽游戏的设计与实现【源码+文档+部署讲解】

目 录 1、绪论 1.1背景以及现状 1.2 Java语言的特点 1.3 系统运行环境及开发软件&#xff1a; 1.4 可行性的分析 1.4.1 技术可行性 1.4.2 经济可行性 1.4.3 操作可行性 2、 需求分析 2.1 用户需求分析 2.2功能需求分析 2.3界面设计需求分析…...

智慧工地信息管理与智能预警平台

建设背景与政策导向 智慧工地信息管理与智能预警平台的出现&#xff0c;源于工地管理面临的诸多挑战&#xff0c;如施工地点分散、危险区域多、监控手段落后等。随着政府对建筑产业现代化的积极推动&#xff0c;各地纷纷出台政策支持智慧工地的发展&#xff0c;旨在通过信息技…...

使用Apache Mahout制作 推荐引擎

目录 创建工程 基本概念 关键概念 基于用户与基于项目的分析 计算相似度的方法 协同过滤 基于内容的过滤 混合方法 创建一个推荐引擎 图书评分数据集 加载数据 从文件加载数据 从数据库加载数据 内存数据库 协同过滤 基于用户的过滤 基于项目的过滤 添加自定…...

记录:导出功能:接收文件流数据进行导出(vue3)

请求接口&#xff1a;一定要加responseType: blob 后端返回数据&#xff1a; api.js export function export() {return request({url: dev/api/export,method: get,responseType: blob,//一定要加}) } vue&#xff1a; import {export} from /api// 导出 const exportTab…...

GraphRAG vs 传统 RAG:如何通过知识图谱提升 AI 检索能力

相比传统 RAG 仅能独立检索文本片段的局限性&#xff0c;GraphRAG通过构建实体关系图谱实现了信息间的连接&#xff0c;让 AI 能更完整地理解和检索复杂的关联信息&#xff0c;从而生成更准确和连贯的回答 问题背景: 想象有一本详细记录某人(X)成就的传记,每个章节都描述了他的…...

问题清除指南|关于num_classes与 BCELoss、BCEWithLogitsLoss 和 CrossEntropyLoss 的关系

前言&#xff1a;关于「 num_classes 1 」引发的探究。 2024年尾声&#xff0c;学弟问到一个问题&#xff1a;在研究工作 CNNDetection 的github开源代码 networks/trainer.py 文件的 line 27 self.model resnet50(num_classes1) 中&#xff0c;变量 num_classes 的值为1&…...

组网实训实现

小型单元网络实现 IP划分&#xff1a; 外网:172.1.1.0/24 172.1.2.0/24 内网&#xff1a;基于192.168.3.0/24的子网划分 综合办公楼&#xff1a;192.168.3.00 000000 /26&#xff08;192.168.3.0-192.168.3.63&#xff09; 综合一楼&#xff1a;192.168.3.0000 0000 /28&…...

【DevOps】Jenkins部署

Jenkins部署 文章目录 Jenkins部署资源列表基础环境一、部署Gilab1.1、安装Gitlab1.2、修改配置文件1.3、加载配置文件1.4、访问Gitlab1.5、修改root登录密码1.6、创建demo测试项目1.7、上传代码1.8、验证上传的代码 二、部署Jenkins所需软件2.1、部署JDK2.2、部署Tomcat2.3、部…...

HTML——38.Span标签和字符实体

<!DOCTYPE html> <html><head><meta charset"UTF-8"><title>span标签和字符实体</title><style type"text/css">h1{text-align: center;}p{text-indent: 2em;}span{color: red;}</style></head><…...

doris:基于 Arrow Flight SQL 的高速数据传输链路

Doris 基于 Arrow Flight SQL 协议实现了高速数据链路&#xff0c;支持多种语言使用 SQL 从 Doris 高速读取大批量数据。 用途​ 从 Doris 加载大批量数据到其他组件&#xff0c;如 Python/Java/Spark/Flink&#xff0c;可以使用基于 Arrow Flight SQL 的 ADBC/JDBC 替代过去…...

文献阅读 | B. S. Carmo 2010

目录 一、文献名称二、原文地址三、ABSTRACT主要发现详细观察分岔分析雷诺数依赖性比较见解意义结论 四、IINTRODUCTION历史研究回顾计算研究近期研究进展研究空白与目的论文结构 一、文献名称 二、原文地址 研究目的&#xff1a;研究串列排列双圆柱体周围流场中的次级不稳定性…...

GRAPE——RLAIF微调VLA模型:通过偏好对齐提升机器人策略的泛化能力(含24年具身模型汇总)

前言 24年具身前沿模型大汇总 过去的这两年&#xff0c;工作之余&#xff0c;我狂写大模型与具身的文章&#xff0c;加之具身大火&#xff0c;每周都有各种朋友通过CSDN私我及我司「七月在线」寻求帮助/指导(当然&#xff0c;也欢迎各大开发团队与我司合作共同交付&#xff09…...

超越YOLO11!DEIM:先进的实时DETR目标检测

DEIM: DETR with Improved Matching for Fast Convergence arXiv: https://arxiv.org/abs/2412.04234 Project webpage&#xff1a;https://www.shihuahuang.cn/DEIM/ GitHub&#xff1a;https://github.com/ShihuaHuang95/DEIM 1 背景&#xff1a;DETR目标检测框架 目标检…...

django vue3实现大文件分段续传(断点续传)

前端环境准备及目录结构&#xff1a; npm create vue 并取名为big-file-upload-fontend 通过 npm i 安装以下内容"dependencies": {"axios": "^1.7.9","element-plus": "^2.9.1","js-sha256": "^0.11.0&quo…...

用户注册模块(芒果头条项目进度4)

1 创建⽤户模块⼦应⽤ 1.1 在项⽬包⽬录下 创建apps的python包。 1.2 在apps包下 创建应⽤userapp $ cd 项⽬包⽬录/apps $ python ../../manage.py startapp userapp 1.3 配置导包路径 默认情况下导包路径指向项⽬根⽬录 # 通过下⾯语句可以打印当前导包路径 print(sys.pa…...