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

大厂算法面试 7 天冲刺:第6天-树与图深度剖析——高频算法面试题 Java 实战

🧠 第6天:树与图深度剖析——高频算法面试题 & Java 实战


📚 一、核心知识概览 Overview

1. 树(Tree)

树是一种非线性数据结构,常见于面试中的二叉树(Binary Tree)、二叉搜索树(BST)、N叉树等。

常见面试考点:

  • 树的遍历(前序、中序、后序、层序)
  • 最近公共祖先(Lowest Common Ancestor, LCA)
  • 判断平衡树、对称树、二叉搜索树验证等

2. 图(Graph)

图是一种更复杂的数据结构,常用于建模复杂关系,如社交网络、地图、网络延迟等。

常见面试考点:

  • 图的表示(邻接表 / 邻接矩阵)
  • BFS / DFS 遍历
  • 拓扑排序、最短路径(Dijkstra、Floyd)、网络延迟

🧩 二、算法实战 Algorithms & Java 实现


🌟 案例1:二叉树的层序遍历(Level Order Traversal)

💬 题目描述

给你一棵二叉树,请你返回其按层序遍历得到的节点值。

✅ 示例输入
Input: [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
🔍 解法:BFS(队列实现)
public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList<>();if (root == null) return result;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int size = queue.size();List<Integer> level = new ArrayList<>();for (int i = 0; i < size; i++) {TreeNode node = queue.poll();level.add(node.val);if (node.left != null) queue.offer(node.left);if (node.right != null) queue.offer(node.right);}result.add(level);}return result;
}

🌟 案例2:二叉树的最近公共祖先(Lowest Common Ancestor)

💬 题目描述

给定一棵二叉树,找到两个节点的最近公共祖先。

✅ 示例输入
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1  
Output: 3
🔍 解法:递归 + 后序遍历
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root == null || root == p || root == q) return root;TreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p, q);if (left != null && right != null) return root;return left != null ? left : right;
}

🌟 案例3:网络延迟时间(Network Delay Time)

💬 题目描述

给定一个有向图,每条边由三元组 (u, v, w) 表示从节点 uv 的路径时间为 w,返回从源节点 K 发出信号,到所有节点的最短时间

✅ 示例输入
Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2  
Output: 2
🔍 解法:Dijkstra 算法(优先队列实现最短路径)
public int networkDelayTime(int[][] times, int N, int K) {Map<Integer, List<int[]>> graph = new HashMap<>();for (int[] time : times) {graph.computeIfAbsent(time[0], k -> new ArrayList<>()).add(new int[]{time[1], time[2]});}int[] dist = new int[N + 1];Arrays.fill(dist, Integer.MAX_VALUE);dist[K] = 0;PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));pq.offer(new int[]{K, 0});while (!pq.isEmpty()) {int[] cur = pq.poll();int u = cur[0], time = cur[1];if (time > dist[u]) continue;if (!graph.containsKey(u)) continue;for (int[] next : graph.get(u)) {int v = next[0], w = next[1];if (dist[v] > dist[u] + w) {dist[v] = dist[u] + w;pq.offer(new int[]{v, dist[v]});}}}int max = Arrays.stream(dist).skip(1).max().getAsInt();return max == Integer.MAX_VALUE ? -1 : max;
}

🛠 三、JDK 与框架中的应用

数据结构应用场景框架示例
TreeTreeMap、TreeSet、BinaryTree 实现Java Collection Framework
Graph服务依赖图、任务拓扑排序Spring Boot AutoConfig、微服务拓扑

📌 四、总结 Summary

  • 树结构用于分层表达、层级遍历、祖先查找等问题。
  • 图结构用于最短路径、传递闭包、依赖分析等问题。
  • 常用算法包括 BFS/DFS/Dijkstra/拓扑排序 等,掌握 Java 实现是通关面试的关键!

相关文章:

大厂算法面试 7 天冲刺:第6天-树与图深度剖析——高频算法面试题 Java 实战

&#x1f9e0; 第6天&#xff1a;树与图深度剖析——高频算法面试题 & Java 实战 &#x1f4da; 一、核心知识概览 Overview 1. 树&#xff08;Tree&#xff09; 树是一种非线性数据结构&#xff0c;常见于面试中的二叉树&#xff08;Binary Tree&#xff09;、二叉搜索树…...

C语言编译和链接错题

一、错题重现 1.用在switch语句中的关键字不包含哪个&#xff1f;( ) A.continue B.break C.default D.case 2.下面代码的结果是&#xff1a;( ) A.3 B.4 C.随机值 D.5 3.下面那个不是转义字符&#xff1f; A.\n B.\060 C.\q D.\b 二、错因分析及思考 1.题目看…...

吴恩达深度学习复盘(7)一个简单训练示例

简介 本篇简单讲解简单的神经网络训练。通过回顾逻辑回归模型训练&#xff0c;了解神经网络训练的相关内容。比如训练步骤、损失函数、优化算法以及深度学习库的使用&#xff0c;了解训练过程中的相关概念。 例子 手写数字识别&#xff08;判断是 0 还是 1&#xff09;。这是…...

道路坑洼目标检测数据集-665-labelme

文章目录 1.介绍3.标签介绍4.标注工具5.数据集下载 1.介绍 目标&#xff1a;从道路图像中检测坑洼&#xff1b; 应用&#xff1a;检测道路地形和坑洼可实现平稳行驶&#xff0c;小型数据集常常用于学习和学术研究&#xff1b; 详细信息&#xff1a; 665 张图、1740个在坑洼处标…...

提升移动端用户体验:解决输入框被软键盘遮挡的有效方法

解决移动端输入框被软键盘覆盖的问题 在开发移动端网页时&#xff0c;如果页面包含输入框&#xff0c;则可能会遇到输入框被弹出的软键盘遮挡的问题。为了解决这个问题&#xff0c;我们需要理解两种常见的情况以及相应的解决策略。 浏览器未主动聚焦到输入框 现代浏览器和移…...

函数极限常见计算方法集锦

本文非常直接&#xff0c;如标题所见就是一个常见的计算方式极限方法的集锦。 所以内在逻辑性确实不强&#xff0c;主要通过例题的形式阐述。 添项减项 当题目出现了交错的形式便可以考虑添项减项。 一般而言我们会加一项交错项&#xff0c;减一项交错项。 例如出现 A B …...

Tomcat的部署

Tomcat 服务器是一个免费的开放源代码的Web 应用服务器&#xff0c;属于轻量级应用服务器&#xff0c;在中小型系统和 并发访问用户不是很多的场合下被普遍使用&#xff0c;Tomcat 具有处理HTML页面的功能&#xff0c;它还是一个Servlet和 JSP容器 官网:Apache Tomcat - Welco…...

Ubuntu(CentOS、Rockylinux等)快速进入深度学习pytorch环境

这里写自定义目录标题 安装进入系统&#xff08;如Ubuntu22.04&#xff09;安装anacondapip、conda换源pip换源conda换源 安装nvidia安装pytorch环境针对于wsl的优化 安装进入系统&#xff08;如Ubuntu22.04&#xff09; docker 、 wsl 、 双系统 、服务器系统 推荐 Ubuntu 20…...

AI 如何帮助我们提升自己,不被替代

在当今快速发展的时代&#xff0c;人工智能&#xff08;AI&#xff09;正逐渐渗透到生活的方方面面。许多人担心 AI 会取代人类的工作&#xff0c;然而&#xff0c;AI 更多的是作为一种强大的赋能工具&#xff0c;帮助我们提升自身能力&#xff0c;让我们在工作中更具竞争力。以…...

ROS2 多机时间同步(Chrony配置简明指南)

适用场景&#xff1a; 主机运行 ROS2 Humble&#xff08;发布 /scan 等&#xff09;&#xff0c;板子运行 ROS2 Foxy&#xff08;发布 /tf 等&#xff09;&#xff0c;两边通过 ROS_DOMAIN_ID 跨平台通讯。需要保证系统时间对齐&#xff0c;避免 TF 插值失败、建图抖动等问题。…...

C 语言排序算法:从基础到进阶的全面解析一、引言

一、引言 在 C 语言编程领域&#xff0c;排序算法是一项基础且核心的技能。无论是处理海量数据&#xff0c;还是优化程序性能&#xff0c;选择合适的排序算法都至关重要。本文将深入剖析 C 语言中常见的几种排序算法&#xff0c;包括冒泡排序、选择排序、插入排序、希尔排序、…...

蓝桥云客--团队赛

2.团队赛【算法赛】 - 蓝桥云课 问题描述 蓝桥杯最近推出了一项团队赛模式&#xff0c;要求三人组队参赛&#xff0c;并规定其中一人必须担任队长。队长的资格很简单&#xff1a;其程序设计能力值必须严格大于其他两名队友程序设计能力值的总和。 小蓝、小桥和小杯正在考虑报名…...

VBA第三十八期 VBA自贡分把表格图表生成PPT

上一节讲到把数据区域自动生成PPT&#xff0c;这一实例是把图表自动生成PPT。 Sub CopyA11ChartsToPresenta&#xff08;&#xff09; Dim PP As PowerPoint. Application Dim PPPres As PowerPoint. Presentation Dim PPSlide As PowerPoint. SlideDim i As Integer Shee…...

Linux字符驱动设备开发入门之框架搭建

声明 本博客所记录的关于正点原子i.MX6ULL开发板的学习笔记&#xff0c;&#xff08;内容参照正点原子I.MX6U嵌入式linux驱动开发指南&#xff0c;可在正点原子官方获取正点原子Linux开发板 — 正点原子资料下载中心 1.0.0 文档&#xff09;&#xff0c;旨在如实记录我在学校学…...

Nextjs15 实战 - React Notes之SidebarNoteList优化和Suspense的使用

current branch 对应如下文档 redis ioredis 本专栏内容均可在Github&#xff1a;notes_02 找到 完整项目使用技术栈&#xff1a; Nextjs15 MySQL Redis Auth Prisma i18n strapi Docker vercel 一、本节目标 实现笔记列表展开回收和 Suspense 的实践 二、修改根…...

第三十章:Python-NetworkX库:创建、操作与研究复杂网络

一、NetworkX库简介 NetworkX是一个强大的Python库&#xff0c;用于创建、操作和研究复杂网络&#xff08;图&#xff09;的结构、动态和功能。它支持多种类型的图&#xff0c;包括无向图、有向图、加权图和多重图&#xff0c;并提供了丰富的图论算法和可视化工具。资源绑定附…...

cpp自学 day19(多态)

一、基本概念 同一操作作用于不同的对象&#xff0c;产生不同的执行结果 &#x1f449; 就像「按F1键」&#xff1a;在Word弹出帮助文档&#xff0c;在PS弹出画笔设置&#xff0c;​同一个按键触发不同功能 &#xff08;1&#xff09;多态类型 类型实现方式绑定时机​静态多态…...

Unity:销毁(Destroy)

Destroy的基本概念 Destroy是Unity提供的一个方法&#xff0c;用于立即或延迟销毁游戏对象&#xff08;GameObject&#xff09;或其组件&#xff08;Component&#xff09;。它会从场景中移除对象&#xff0c;并释放相关资源&#xff08;比如内存&#xff09;。 语法 销毁Ga…...

【C++初阶】模板进阶

目录 模板参数 模板的特化 函数特化 类模板特化 全特化 偏特化 模板分离编译 分离编译 模板的分离编译 为什么模板不支持声明和定义分离呢&#xff1f; 解决方法 模板总结 优点 缺点 模板参数 模板参数分为类型形参和非类型参数 类型形参&#xff1a;出现在模板…...

BN 层的作用, 为什么有这个作用?

BN 层&#xff08;Batch Normalization&#xff09;——这是深度神经网络中非常重要的一环&#xff0c;它大大改善了网络的训练速度、稳定性和收敛效果。 &#x1f9e0; 一句话理解 BN 层的作用&#xff1a; Batch Normalization&#xff08;批归一化&#xff09;通过标准化每一…...

CNN 里面能自然起到防止过拟合的办法

在 CNN&#xff08;卷积神经网络&#xff09;中&#xff0c;其实有 一些结构和机制 天然就具有防止过拟合&#xff08;overfitting&#xff09;的作用&#xff0c;不完全依赖额外的正则化手段。 &#x1f9e0; 一、CNN 天然防过拟合的几个原因&#xff1a; 1️⃣ 局部连接&…...

存储基石:深度解读Linux磁盘管理机制与文件系统实战

Linux系列 文章目录 Linux系列前言一、磁盘1.1 初识磁盘1.2 磁盘的物理结构1.3 磁盘的存储结构1.4 磁盘的逻辑结构 二、文件系统2.1 系统对磁盘的管理2.2 文件在磁盘中的操作 前言 Linux 文件系统是操作系统中用于管理和组织存储设备&#xff08;如硬盘、SSD、USB 等&#xff…...

AI Agent设计模式六:ReAct

概念 &#xff1a;思考-执行循环系统 ✅ 优点&#xff1a;提升任务完成度&#xff0c;适合复杂问题拆解❌ 缺点&#xff1a;执行延迟较高&#xff0c;资源消耗大 from langchain_core.messages import SystemMessage, HumanMessage, ToolMessage, AIMessage from langgraph.pr…...

使用MySQL时出现 Ignoring query to other database 错误

Ignoring query to other database 错误 当在远程连接软件中输入MySQL命令出现该错误 导致错误原因是&#xff1a;登录mysql时账户名没有加上u 如果出现该错误&#xff0c;退出mysql&#xff0c;重新输入正确格式进入即可&#xff01;...

(三)链式工作流构建——打造智能对话的强大引擎

上一篇&#xff1a;&#xff08;二&#xff09;输入输出处理——打造智能对话的灵魂 在前两个阶段&#xff0c;我们已经搭建了一个基础的智能对话&#xff0c;并深入探讨了输入输出处理的细节。今天&#xff0c;我们将进入智能对话的高级阶段——链式工作流构建。这一阶段的目…...

跳跃连接(Skip Connection)与残差连接(Residual Connection)

1. 跳跃连接&#xff08;Skip Connection&#xff09;的基本概念 跳跃连接是一种在深度神经网络中广泛应用的技术&#xff0c;它允许信息在网络中跨层直接传递。在传统的神经网络里&#xff0c;每一层的输出仅仅是前一层输出经过特定变换后的结果。而在具备跳跃连接的网络中&a…...

[特殊字符] 通过Postman和OAuth 2.0连接Dynamics 365 Online的详细步骤 [特殊字符]

&#x1f31f; 引言 在企业应用开发中&#xff0c;Dynamics 365 Online作为微软的核心CRM平台&#xff0c;提供了强大的Web API接口。本文将教你如何通过Postman和OAuth 2.0认证实现与Dynamics 365的安全连接&#xff0c;轻松调用数据接口。 &#x1f4dd; 准备工作 工具安装…...

什么是RPC通信

RPC&#xff08;Remote Procedure Call&#xff0c;远程过程调用&#xff09;通信是一种允许程序像调用本地函数一样调用远程服务器上函数的通信技术。它简化了分布式系统中的网络交互&#xff0c;隐藏了底层网络通信的复杂性&#xff0c;使开发者能够专注于业务逻辑。 一、RPC…...

HANA如何在存储过程里执行动态SQL

业务场景需求&#xff1a; 在HANA里如何实现动态的SQL控制&#xff0c;比如需要多个单据里&#xff0c;实现某个自定义字段不允许重复 一般的写法是需要在每个业务单据里加对应的存储过程控制&#xff0c;这样的话&#xff0c;需要在每个业务单据里进行控制&#xff0c;SQL维…...

NO.66十六届蓝桥杯备战|基础算法-贪心-区间问题|凌乱的yyy|Rader Installation|Sunscreen|牛栏预定(C++)

区间问题是另⼀种⽐较经典的贪⼼问题。题⽬⾯对的对象是⼀个⼀个的区间&#xff0c;让我们在每个区间上做出取舍。 这种题⽬的解决⽅式⼀般就是按照区间的左端点或者是右端点排序&#xff0c;然后在排序之后的区间上&#xff0c;根据题⽬要求&#xff0c;制定出相应的贪⼼策略&…...

0101安装matplotlib_numpy_pandas-报错-python

文章目录 1 前言2 报错报错1&#xff1a;ModuleNotFoundError: No module named distutils报错2&#xff1a;ERROR:root:code for hash blake2b was not found.报错3&#xff1a;**ModuleNotFoundError: No module named _tkinter**报错4&#xff1a;UserWarning: Glyph 39044 …...

SQL ServerAlways On 可用性组配置失败

问题现象&#xff1a; 配置 Always On 可用性组时&#xff0c;报错 “无法将数据库加入可用性组”&#xff08;错误 41158&#xff09;&#xff0c;或提示 “WSFC 群集资源无法联机”&#xff08;错误 19471&#xff09;。 快速诊断 验证 WSFC 群集状态&#xff1a; # 检查群集…...

01 - UnLua访问蓝图

前文回顾&#xff1a;配置好了智能提示和调试 分别对私有的和公开函数&#xff0c;变量&#xff0c;组件&#xff0c;事件进行测试。 测试 在BeginPlay中&#xff0c;分别访问他们。这里引入了GetDisplayName函数打印相机组件名 打印结果&#xff1a; 结论 不管是私有的&…...

6.5.图的基本操作

一.图的基本操作&#xff1a; 1.判断图G是否存在弧<x,y>或边(x,y)&#xff1a; a.使用邻接矩阵来实现判断无向图G中是否存在边(x,y)&#xff1a; 以上述图片的无向图为例&#xff0c;用邻接矩阵存储无向图时想要判断两个顶点之间是否有边是很方便的&#xff0c; 比如判…...

2025全新开源双端系统源码:获取通讯录、相册、短信、定位及已装应用信息

分享一套全新上线的双端信息采集系统源码&#xff0c;支持提取通讯录、相册、短信、定位信息及已安装应用数据。源码完全开源&#xff0c;只做轻微测试需要的自取&#xff0c;简易教程放在压缩包里面了&#xff0c;欢迎有需要的朋友自取参考。 下载地址&#xff1a;下载地址.t…...

es基本概念

Elasticsearch 的架构与基本概念 Elasticsearch&#xff08;简称 ES&#xff09;是一个开源的分布式搜索和分析引擎&#xff0c;基于 Apache Lucene 构建。它被广泛用于全文搜索、日志分析、实时数据分析等场景。以下是其架构概述及其基本概念的详细解释。 Elasticsearch 的架…...

算法刷题记录——LeetCode篇(2.5) [第141~150题](持续更新)

更新时间&#xff1a;2025-04-04 算法题解目录汇总&#xff1a;算法刷题记录——题解目录汇总技术博客总目录&#xff1a;计算机技术系列博客——目录页 141. 环形链表 给你一个链表的头节点 head &#xff0c;判断链表中是否有环。 如果链表中有某个节点&#xff0c;可以通…...

【Rust学习】Rust数据类型,函数,条件语句,循环

本文专栏&#xff1a;Rust学习 目录 一&#xff0c;数据类型 1&#xff0c;标量类型 1.1&#xff0c;整型 1.2&#xff0c;整型溢出 1.3&#xff0c;浮点数型 1.4&#xff0c;布尔类型 1.5&#xff0c;字符型 2&#xff0c;复合类型 2.1&#xff0c;Tuple(元组) 2.2&am…...

PgVectore的使用

PgVectore的使用 一、PgVector的安装 参照博客&#xff1a;https://blog.csdn.net/u012953777/article/details/147013691?spm1001.2014.3001.5501 二、PgVector的使用 1、创建表与插入数据​ ​​定义向量字段​​&#xff1a; CREATE TABLE items (id SERIAL PRIMARY …...

智能工厂的数字孪生与信息物理系统架构研究

摘要 本文以工业 4.0 为背景&#xff0c;系统分析数字孪生&#xff08;Digital Twin&#xff09;与信息物理系统&#xff08;CPS&#xff09;在智能工厂中的协同架构。通过构建 "感知 - 映射 - 决策 - 执行" 的四层技术框架&#xff0c;结合三一重工、海尔等企业案例…...

基于YOLO11实例分割与奥比中光相机的快递包裹抓取点检测

本博客来源于CSDN机器鱼&#xff0c;未同意任何人转载。 更多内容&#xff0c;欢迎点击本专栏&#xff0c;查看更多内容。 0 引言 项目采用六轴机械臂搭配末端真空吸盘&#xff0c;从无序包裹中抓取想要的包裹。AI算法需要提供各包裹的抓取点的3D坐标与3D姿态。由于快递包裹含…...

简单程序语言理论与编译技术·22 实现一个从AST到RISCV的编译器

本文是记录专业课“程序语言理论与编译技术”的部分笔记。 LECTURE 22&#xff08;实现一个从AST到RISCV的编译器&#xff09; 一、问题分析 1、完整的编译器&#xff08;如LLVM&#xff09;需先完成AST到IR的转换&#xff0c;并进行代码优化&#xff0c;再到汇编&#xff0…...

无锡无人机驾驶证培训费用

无锡无人机驾驶证培训费用&#xff0c;随着科技的迅速发展&#xff0c;无人机在众多行业中发挥着举足轻重的作用。从影视制作到农业监测&#xff0c;再到物流运输与城市规划&#xff0c;无人机的应用场景不断扩展&#xff0c;因此越来越多的人开始意识到学习无人机驾驶技能的重…...

[ctfshow web入门] web5

前置知识 引用博客&#xff1a;phps的利用 当服务器配置了 .phps 文件类型时&#xff0c;访问 .phps 文件会以语法高亮的形式直接显示 PHP 源代码&#xff0c;而不是执行它。.phps被作为辅助开发者的一种功能&#xff0c;开发者可以通过网站上访问xxx.phps直接获取高亮源代码 …...

第五章:架构安全性_《凤凰架构:构建可靠的大型分布式系统》

第五章 架构安全性 一、认证机制 核心知识点&#xff1a; 认证标准&#xff1a; HTTP Basic认证&#xff1a;Base64编码传输凭证&#xff0c;需配合HTTPS使用OAuth 2.0&#xff1a;授权框架&#xff0c;重点掌握四种授权模式&#xff1a; 授权码模式&#xff08;最安全&#…...

控件主题效果添加程序设计

以下是针对Qt Designer设计的控件添加阴影效果的完整解决方案&#xff0c;结合可视化设置与动态主题支持&#xff1a; 一、基础阴影效果实现方案 1. 通过QSS实现简易阴影&#xff08;适用于简单需求&#xff09; /* 使用多重边框模拟阴影效果 */ QFrame#customWidget {borde…...

用swift playground写个ios应用和大模型或者网站交互

import SwiftUIstruct ContentView: View {State private var textFieldText: String ""State private var outputText: String "输出将会显示在这里"private let tip:String "消息已发送&#xff0c;请等待"State private var history:[Stri…...

Mlivus Cloud SDK v2的革新:从痛点剖析到实战优化

目录 从V1到V2:开发者体验的范式转变 深度解析SDK v2的架构革新 1. 统一接口范式:终结API混乱时代 2. 原生异步支持:高并发场景的性能救星 3. Schema Cache机制:性能优化的隐形冠军 4. 全功能REST API:简化集成的关键 实战指南:从迁移到深度优化 平滑迁移策略 性…...

【图像处理基石】什么是AWB?

1. AWB&#xff08;自动白平衡&#xff09;的定义 AWB&#xff08;Auto White Balance&#xff09;是一种图像处理技术&#xff0c;通过算法校正不同色温光源下图像的色彩偏差&#xff0c;使白色在任何光照条件下都能准确呈现为白色&#xff0c;从而让图像颜色更接近人眼真实感…...

[蓝桥杯 2017 省 B] k 倍区间

P8649 [蓝桥杯 2017 省 B] k 倍区间 题目描述 给定一个长度为 N N N 的数列&#xff0c; A 1 , A 2 , ⋯ A N A_1,A_2, \cdots A_N A1​,A2​,⋯AN​&#xff0c;如果其中一段连续的子序列 A i , A i 1 , ⋯ A j ( i ≤ j ) A_i,A_{i1}, \cdots A_j(i \le j) Ai​,Ai1​,⋯…...