自顶向下专题

[E二叉树] lc104. 二叉树的最大深度(dfs+自顶向下)

文章目录 1. 题目来源2. 题目解析 1. 题目来源 链接:104. 二叉树的最大深度 题单: 链表、二叉树与一般树(前后指针/快慢指针/DFS/BFS/直径/LCA) §2.2 自顶向下 DFS 2. 题目解析 思路: 很基础的 dfs 题目哈,使用 bfs 也能做,体会一下两者的区别。自顶向下、自底向上 都可以处理这个题目。 时间复杂度: O ( n

[M二叉树] lc104. 二叉树的最大深度(dfs+自顶向下)

文章目录 1. 题目来源2. 题目解析 1. 题目来源 链接:104. 二叉树的最大深度 题单: 链表、二叉树与一般树(前后指针/快慢指针/DFS/BFS/直径/LCA) §2.2 自顶向下 DFS 2. 题目解析 思路: 很基础的 dfs 题目哈,使用 bfs 也能做,体会一下两者的区别。自顶向下、自底向上 都可以处理这个题目。 时间复杂度: O ( n

编译原理|第四章 自顶向下语法分析方法——知识点总结

1.什么是FIRST、FOLLOW、SELECT集 合?  FIRST:A可以推出的所有式子的“第一个”非终结符! FOLLOW:3个求解规则   1.主程序Beginadvance;E;end2.E过程Procedure EBeginT;E';end3.E'过程Procedure EBeginif sym = '+' thenbeginadvance;E;ende

自顶向下语法分析方法:消除左递归

直接左递归 形如A->Aβ,A∈非终结符,β∈终结符∪非终结符。 消除直接左递归 一般形式:A->Aα1|Aα2|...|Aαm|β1|β2|...|βn其中,αi(1≤i≤m)不等于ε,βj(1≤j≤n)不以A开头,消除直接左递归改写为:A->β1A'|β2A'|...|βnA'A'->α1A'|α2A'|...|αmA'|ε 例如: 文法:S->SaS->b消除直接左

自顶向下语法分析方法:提取左公共因子

若文法中含有形如A->αβ|αγ的产生式,就会使FIRST集相交,就满足不了LL(1)文法的充分必要条件。 可以做下面的等价变换: A->αβ|αγA->α(β|γ) A->αA' 引入新的终结符A'A'->β|γ 一般形式: A->αβ1|αβ2|...|αβnA->α(β1|β2|...|βn)A->A'A'->β1|β2|...|βn 例子: 文法的产生式为:S

自顶向下语法分析方法:LL(1)文法的判别

例子:文法G[S]为 S->AB|bC A->ε|b B->ε|aD C->AD|b D->aS|c 第一步,求出能推出ε的非终结符 首先建立一个以文法的非终结符为上界的一维数组,其数组元素为非终结符,对应每一非终结符有一个标志位,用以记录能否推出ε。如下表 非终结符SABCD初值未定未定未定未定未定第1次扫描是是否第2次扫描是否 能否推出ε步骤如下: 第二步,计算FIR

计算机网络教材——谢希仁教材与配套PPT课件和《计算机网络——自顶向下方法》

教材链接: https://pan.baidu.com/s/1MUkgTVNMvhFdkGxAd0U7Ew?pwd=n3g4 提取码: n3g4  ppt资源:课程包列表 (51zhy.cn) 计算机网络——自顶向下方法(资源在下面的评论区里):计算机网络自顶向下方法第7版中文PDF习题参考 - 哔哩哔哩 (bilibili.com)

计算机网络---自顶向下方法

应用层 HTTP协议 用户和服务器的交互—-cookie cookie技术有四个组件: 在HTTP响应报文中的一个cookie首部行;在HTTP请求报文中的一个cookie首部行;在用户端系统中保留一个cookie文件,并由用户的浏览器进行管理;位于Web站点的一个后台数据库; cookie可以在无状态的HTTP之上建立一个用户会话层; Web缓存 Web缓存也叫代理服务器,它是能代

Spring IOC源码分析(五):IOC的容器上下文ApplicationContext的自顶向下分析

一、spring-context包:IOC的容器上下文 1. ApplicationContext接口 public interface ApplicationContext extends EnvironmentCapable, ListableBeanFactory, HierarchicalBeanFactory,MessageSource, ApplicationEventPublis

<计算机网络自顶向下> 通用转发和SDM

,网络层功能为例的数据平面和控制平面: 网络层功能: 转发——对于从某个端口到来的分组转发到合适的输出端口 路由——决定分组从源端到目标端的路径(依靠路由算法) 每个路由器的控制平面 每个路由器上都有实现路由算法元件(它们之间需要相互交互)-形成传统IP实现方式的控制平面 每台设备上既实现控制功能,又实现数据平面控制功能分布式实现路由表把这两种功能粘连网络设备(中间盒)繁多(比如交换机、

<计算机网络自顶向下> Internet Protocol(未完成)

互联网中的网络层 IP数据报格式 ver: 四个比特的版本号(IPV4 0100, IPV6 0110) headlen:head的长度(头部长度字段(IHL)指定了头部的长度,以32位字(4字节)为单位计算。这个字段的值乘以4就是头部的实际长度,因为每个值代表4个字节。所以,如果IHL字段的值为5,那么头部长度就是5 * 4 = 20字节,IP数据包头部最小长度是20所以这个head

<计算机网络自顶向下> 路由器组成

路由器结构概况 路由:运行路由选择算法/协议(RIP, OSPF, BGP)生成路由表转发:从输入到输出链路交换数据包-根据路由表进行分组的转发中间的fabric是用来接收输入的分组交给输出端口的,完成局部的转发(根据路由处理器上的路由的实体算出的路由表,把路由表交到输入端口,就知道要往哪里转发)  输入端口功能  输入端口缓存 当交换机构的速率小于输入端口的汇聚速率的时候在输入端

【计算机网络】【《计算机网络·自顶向下方法(原书第7版)》笔记】第三章:运输层

文章目录 @[toc]3.1|概述和运输层服务运输层和网络层的关系因特网运输层概述 3.2|多路复用与多路分解无连接的多路复用与多路分解面向连接的多路复用与多路分解TCP客户-服务器示例 Web服务器与TCP 个人主页:丷从心· 系列专栏:计算机网络 3.1|概述和运输层服务 运输层和网络层的关系 网络层提供了主机之间的逻辑通信运输层为运行在不同主机上的进程之间提

<计算机网络自顶向下> TCP拥塞

目录 TCP拥塞控制机制 TCP拥塞感知 TCP速率控制方法  TCP拥塞控制和流量控制的联合动作 TCP拥塞控制策略  TCP吞吐量  TCP公平性 TCP拥塞控制机制 端到端的拥塞控制机制 路由器不向主机提供有关拥塞的反馈信息 路由器负担较轻 符合网络核心简单的TCP/IP架构原则 端系统根据自身得到的信息判断是否发生拥塞,从采取动作拥塞控制的问题 如何检测拥塞

【计算机网络】【《计算机网络·自顶向下方法(原书第7版)》笔记】第二章:应用层

文章目录 @[toc]2.1|网络应用原理网络应用体系结构进程通信进程与计算机网络之间的接口 可供应用程序使用的运输服务可靠数据传输吞吐量定时安全性 因特网提供的运输服务TCP服务面向连接的服务可靠的数据传输服务拥塞控制TCP安全 个人主页:丷从心· 系列专栏:计算机网络 2.1|网络应用原理 网络应用体系结构 客户 − - −服务器体系结构对等体系结构( P

【计算机网络】【《计算机网络·自顶向下方法(原书第7版)》笔记】第一章:计算机网络和因特网

文章目录 @[toc]1.1|什么是因特网1.2|网络边缘接入网家庭接入数字用户线DSL电缆光纤到户FTTH5G固定式无线 企业(和家庭)接入以太网WiFi 广域无线接入 物理媒介导引型媒介与非导引型媒介双绞铜线同轴电缆光纤陆地无线电信道卫星无线电信道 1.3|网络核心分组交换存储转发传输排队时延和分组丢失转发表和路由选择协议 电路交换频分复用FDM时分复用TDM 网络的网络PoP多宿对等因

<计算机网络自顶向下> CDN

视频服务挑战 规模性异构性:不同用户有不同的能力(比如有线接入和移动用户;贷款丰富和受限用户)解决方法是:分布式的应用层面的基础设施CDN 多媒体:视频 视频是固定速度显示的一系列图像的序列,图像又是一系列像素点的序列视频占的带宽太大所以不经过压缩就在网络上传输基本是不可能的压缩的基础 空间的冗余度:一个帧当中一些范围的像素点颜色一样,空间描述的时候可以说某个像素点在那一范围出现时间上的冗余

<计算机网络自顶向下> P2P应用

纯P2P架构 没有或者极少一直运行的Server,Peer节点间歇上网,每次IP地址都可能变化任意端系统都可以直接通信利用peer的服务能力,可扩展性好例子:文件分发; 流媒体; VoIP类别:两个节点相互上载下载文件,互通有无,构成覆盖网overlay(这种网络是逻辑的网络因为是在应用层的网络) 非结构化P2P: 随机连接(集中化目录) DHT(结构化)P2P: 形成特定的结构比如环或者树缺点

计算机网络原理-自顶向下一

计算机网络和因特网 什么是因特网 什么是因特网?回答这个问题有两种方式:其一,从具体构成上看:可以分成基本硬件和软件组件。其二,我们能够根据为分布式应用提供服务的联网基础设施来描述因特网。 因特网是网络的网络,是通信技术和计算机技术紧密结合的产物。是互连的,自治的。 自治:无主从关系互连:互联互通 具体构成描述 因特网是世界范围的计算机网络。互联了世界的计算机网络。在之前计算设备多是电

Netty进阶:自顶向下解析FastThreadLocal

文章目录 FastThreadLocalThread 分析优雅的使用 FastThreadLocal1. InternalThreadLocalMap 底层数据结构2. FastThreadLocal3. set3.1 获取map3.2 设置value 4. get5. remove FastThreadLocalThread 分析 我们知道EventLoopGroup相当

TMA-自顶向下的CPU性能分析

让CPU黑盒不再黑——【TMA_自顶向下的CPU架构性能瓶颈分析方法】(一)What & Why - 知乎  让CPU黑盒不再黑——【TMA_自顶向下的CPU架构性能瓶颈分析方法】(二)How - 知乎  让CPU黑盒不再黑——【TMA_自顶向下的CPU架构性能瓶颈分析方法】(三)Frontend - 知乎 让CPU黑盒不再黑——【TMA_自顶向下的CPU架构性能瓶颈分析方法】(四)Spec

何以谓之“自顶向下,逐步求精”

本篇博客意在介绍一个程序设计的方法——自顶向下,逐步求精。 WHAT IS 自顶向下,逐步求精? According to wikipedia:Top-down and bottom-up are both strategies of information processing and knowledge ordering, used in a variety of fields inclu

LeetCode 2673.使二叉树所有路径值相等的最小代价:自顶向下的DFS 或 自底向上的递推

【LetMeFly】2673.使二叉树所有路径值相等的最小代价:自顶向下的DFS 或 自底向上的递推 力扣题目链接:https://leetcode.cn/problems/make-costs-of-paths-equal-in-a-binary-tree/ 给你一个整数 n 表示一棵 满二叉树 里面节点的数目,节点编号从 1 到 n 。根节点编号为 1 ,树中每个非叶子节点 i 都有两个孩

《DSAA》 12.2.3 红黑树的自顶向下删除

当初自学围棋的时候背过一些定式,一般定式都比较容易,从开始到结束用不了几个回合。直到有一天遇到了像妖刀,大雪崩,大斜这样的大型定式,变化极为繁复,一个定式摆下去能占满1/4个棋盘,这个要掌握就非常困难了。 如果把算法类比为围棋的布局,数据结构类比为定式的话,红黑树无疑就是一个大型定式。个人感觉它的搜索和插入什么的还算简单,而且原书也给出了实现。但难就难在删除,偏偏书里只讲了 大致思路,看着非

《DSAA》 12.1 自顶向下伸展树

在许多应用中,当一个节点被访问后,马上就很可能再次被访问到,研究表明这种情况比人们预料的要频繁的多。所以伸展树的基本想法是:当一个节点被访问后,它就要通过一系列的旋转被放到根上。 自顶向下伸展树的搜索方式非常独特,它实际上是一个拆了又装的过程,这个过程被称为伸展: 最开始先新建两颗空树:L树和R树,用于缓存。在从原树自顶向下搜索时,每一次迭代都将父节点以上的部分拆除,视情况接到两旁的L

自顶向下的CPU架构性能瓶颈分析方法

转载: 让CPU黑盒不再黑——【TMA_自顶向下的CPU架构性能瓶颈分析方法】(一)What & Why - 知乎