Posts

105. 从前序与中序遍历序列构造二叉树 描述 根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如，给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树： 1 2 3 4 5 3 / \ 9 20 / \ 15 7 https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal 思路 由先序序列第一个pre[0]在中序序列中找到根节点位置gen 以gen为中心遍历 0~gen左子树 子中序序列：0~gen-1，放入vin_left[] 子先序序列：1~gen放入pre_left[]，+1可以看图，因为头部有根节点 gen+1~vinlen为右子树 子中序序列：gen+1 ~ vinlen-1**放入vin_right[] 子先序序列：gen+1 ~ vinlen-1**放入pre_right[] 由先序序列pre[0]创建根节点 连接左子树，按照左子树子序列递归（pre_left[]和vin_left[]） 连接右子树，按照右子树子序列递归（pre_right[]和vin_right[]） 返回根节点 解答 我在LeetCode上的解答 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func buildTree(preorder []int, inorder []int) *TreeNode { if preorder == nil || inorder == nil || len(preorder) == 0 || len(inorder) == 0 { return nil } // 中顺序列找根结点 var root int for k, v := range inorder { if v == preorder[0] { root = k break } } // 左右子树归类 // pre_left, pre_right := preorder[1: root+1], preorder[root+1:] // in_left, in_right := inorder[0: root], inorder[root+1:] // 左右子树递归 return &TreeNode{ Val: preorder[0], Left: buildTree(preorder[1: root+1], inorder[: root]), Right: buildTree(preorder[root+1:], inorder[root+1:]), } } 结果和优化 执行用时 :4 ms, 在所有 Go 提交中击败了95.95%的用户 内存消耗 :3.9 MB, 在所有 Go 提交中击败了68.15%的用户 ...

三、表达式 3.1 保留字 25个关键字 3.2 运算符 乘幂和绝对值，对应的是 math库 里的Pow和Abs函数 优先级 从高到低： 1 2 3 4 5 * / % << >> & &^ + - | ^ == != < <= > >= && || 相同优先级从左到右 二元运算符 除了位移运算，操作类型必须相同。若有无显式类型，那么这个操作数会自动转型 位移的右边操作数必须是无符号整数 位运算符 1 2 3 4 5 AND 位与：全一则一 a & b 0101 & 0011 = 0001 OR 位或：有一则一 a | b 0101 | 0011 = 0111 XOR 位异或：不进位加法 a ^ b 0101 ^ 0011 = 0110 NOT 非或反 ^a ^0101 = 1010 AND NOT 位清除（bit clear） a &^ b 0110 &^ 1011 = 0100 bit clear和异或不同，位清除将左右操作数对应二进制位都为1的重置为0，从而达到一次清除多个标记位的目的 ...

二、类型 2.1 变量 静态类型语言，Go变量有固定的数据类型。==只能改变变量值，无法改变类型。== 类型转换或指针操作，可以用不同的方式修改变量值，但是并不意味改变了变量类型 定义 var 类型放在后面 变量会自动初始化为二进制零（zero value），避免出现不可预测行为 1 var x int 显示提供初始化值，由编译器推断 1 var y = false 一次可以定义多个变量以及初始化 1 2 var x, y int var a, s = 100, "abc" //编译器自动推断类型 建议用组的方式整理多行变量的定义 1 2 3 4 var ( x, y int a, s = 100, "abc" ) 简洁模式 := 1 x := 10 简洁模式有限制 定义变量，同时显式初始化 不能提供数据类型 只能用在函数内部 所以有时会犯以下错误，并没有改变全局变量，而是重新定义了一个同名局部变量 1 2 3 4 5 6 7 8 var x = 100 func main(){ fmt.Println(&x, x) // 全局变量 x := "abc" fmt.Println(&x, x) // 重新定义和初始化同名的局部变量 } 有时候也会退化成赋值，前提： 是在同一作用域内 至少有一个新变量被定义 1 2 3 4 5 6 7 8 9 10 11 12 13 func main(){ x := 123 fmt.Println(&x, x) x, y := 200, "abc" // 同域 + 新变量被定义 // x := 200 会报错，因为没有新变量被定义 fmt.Println(&x, y) // 重新定义，括号内是另外一个域 //{ // x := 200 //} } 多变量赋值 先计算完右边，再赋值到左边的变量 ...

查找 折半查找 复杂度：O(logn) 对象：排序的数组 内容： 设置高低指针 中间开始，如果值相等则结束 值不相等，高低指针向中间迫近 指针相遇，结束 实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 func BinarySearch(arr []int, goal int) int { // 取高低索引 low, high := 0, len(arr)-1 // 指针未相遇的时候循环 for low <= high { mid := low + (high-low)>>1 midV := arr[mid] // 符合条件，返回索引 if midV == goal { return mid } // 不符合条件，高低指针向中间迫近 if midV < goal { low = mid + 1 } else { high = mid - 1 } } return -1 } 排序 快速排序 x s 插入排序

书籍： 环境：MacOS + Goland 学习方式：看书、实现、记录Markdown 一、概述 1.1 特征 语法简单：类C，简洁->Python 并发模型：运行时用Goroutine运行一切，用协程的方式处理并发单元，运行时又作了深度优化；搭配channel，实现了CSP模型 垃圾回收： 静态链接：编译后一个可执行文件，无需附加仍何东西就能部署 标准库： 工具链： 1.2 简介 第一个Go程序 1 2 3 4 5 6 // test.go package main func main() { print("hello world") } 以.go为文件扩展名 不需要分号 ; 一定要有入口函数 main，无参数，==且必须放在main包中？？== 删除未使用的导入，否则会报错 test.go 和 main.go test.go，里面写 package main，直接运行，控制台不输出，需要 go run test.go main.go，里面写 package main，直接运行输出 变量 使用 var 定义变量，数据类型划分明确，适合跨平台。赋值的时候，var可以省略 1 2 3 4 5 6 7 8 9 10 // main.go package main func main() { var x int32 // 不赋值的int默认值为0 var s = "hello" y := 100 println(x, s, y) // 输出输出 0 hello 100，再换行 print(x, s, y) // 输出 0hello100，不换行 } print和println都可以同时输出多个变量 print不会同行加空格以及末尾换行 变量定义了不使用也会报错 结构体，用Table右对齐

常问问题： 可能会手撕数据库语句，一般是查询，这个看你运气了 一些关键字 四个特性，三个“读”（脏读、幻读、不可重复读）、四个隔离级别、乐观悲观锁、表锁行锁之类的 索引是什么、创建索引原则、索引类型 数据库引擎、底层（B+树）及好处 其余的自己看下面的，多理解几遍就能讲出来了 另外还可能要去了解下主从数据库（读写分离）、分库分表、平滑扩容 相关的大致流程，我下面没写 知识内容 InnoDB和MySAM InnoDB和MySAM 操作性： InnoDB具有事务，支持四个事务隔离级别。 适用于大量INSERT或UPDATE操作。 不支持全文索引，新版本支持。 支持外键 MyISAM管理非事务表 它提供高速存储和检索，以及全文搜索能力。 如果应用中需要执行大量的SELECT查询，那么MyISAM是更好的选择 不支持事务、外键 存储： MyISAM在磁盘上存储成三个文件。表定义 .frm，数据文件.MYD， 索引文件.MYI。跨平台转移麻烦 InnoDB：空间数据文件和它的日志文件，InnoDB 表的大小只受限于操作系统文件的大小 索引： InnoDB（索引组织表）：能缓存索引，也能缓存数据，必须得有主键 MyISAM（堆组织表）：只能缓存索引。非聚类 InnoDB 在做SELECT的时候，要维护缓存数据和索引和其余的，慢一些。MyISAM只缓存索引块 MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。 B+树搜索算法搜索索引-取出data值-以此为地址读取数据记录 主索引要求key是唯一的，而辅助索引的key可以重复 InnoDB也使用B+Tree作为索引结构，数据文件本身就是索引文件。 叶节点data域就是数据记录，称之聚类索引 本身要按主键聚类，所以必须要主键（设置自增主键），没有的话分裂维持特性会十分低效。没指定的话会自动选择合适的或自动生成一个隐含字段。长度为6的长整型 辅助索引data存储的主键值 索引 为了 加快对数据表中的检索而创建的分布存储的数据结构 索引可以看作一张表，指向实体表记录（书的目录，便于查找） 唯一索引，保证每行数据的唯一性 加大检索速度，特别是分组和排序 加速表和表之间的连接速度 缺点：创建和维护要耗时（增删时要动态维护），占用物理空间 总结：会提高查询速度，但是DML会变慢（更新维护索引） 范式 第一范式：当关系模式R的所有属性都不能在分解为更基本的数据单位时，称R是满足第一范式的，简记为1NF。满足第一范式是关系模式规范化的最低要求，否则，将有很多基本操作在这样的关系模式中实现不了。 第二范式：如果关系模式R满足第一范式，并且R得所有非主属性都完全依赖于R的每一个候选关键属性，称R满足第二范式，简记为2NF。 第三范式：设R是一个满足第一范式条件的关系模式，X是R的任意属性集，如果X非传递依赖于R的任意一个候选关键字，称R满足第三范式，简记为3NF. 注：关系实质上是一张二维表，其中每一行是一个元组，每一列是一个属性 第四范式：要求把同一表内的多对多关系删除。 第五范式：从最终结构重新建立原始结构。 BC范式（BCNF）：符合3NF，并且，主属性不依赖于主属性。若关系模式R属于第一范式，且每个属性都不传递依赖于键码，则R属于BC范式。 事务 多条语句同时成功或同时不成功，有一条失败会回滚，所有事务操作取消 用 BEGIN, ROLLBACK, COMMIT 来实现 BEGIN 或 START TRANSACTION; 开始一个事务 ROLLBACK 事务回滚 COMMIT 事务确认 直接用 SET 来改变 MySQL 的自动提交模式: SET AUTOCOMMIT=0 禁止自动提交 SET AUTOCOMMIT=1 开启自动提交 1 2 3 START TRANSACTION; // 开启事务 INSERT INTO stu (class_id,sname,sex)VALUES(2,'xx','x'); COMMIT; 四大特性 原子性：不能部分执行，事务不能完成也要回滚消除影响 侧重事务本身的职责，不管具体内容，只管能不能完成事务。 一致性：事务操作就是把数据库从一个状态到另一个状态。 侧重事务完成的结果 比如A和B都有1000，总共2000。A向B转账500，那么必须保持事务发生后A B都为1000 A 减少500 和 B增加500 这两个操作必须在事务内全部得到实现 隔离性：多事务并发运行，各自执行各自的，互不影响 持久性：数据库出错也能恢复，或者事务提交后不会再发生意外改变 隔离问题 脏读：A读取了B事务过程中（未提交）的数据，但B后面进行了回滚。A读取到的即为脏数据 ...

面试CS基础——操作系统笔记 一、操作系统概述 操作系统四个特性 并发：同一段时间内多个程序执行。并行（同一时刻多个事件）和并发（同一个时间段多个事件） 并发：同一时间段运行多个程序，操作系统通过进程和线程实现 并行：同一时刻运行多个指令，需要硬件支持，流水线、多核、分布式 共享：系统资源可以被内存中的多个并发执行的进程共用 互斥共享（临界资源，比如打印机）和同时共享 虚拟：通过 时分复用（多道程序技术 分时系统）和空分复用（虚拟内存）技术把一个物理实体虚拟为多个实体 时分复用：多进程在一个处理器并发执行，让每个进程轮流占有处理器，用小时间片快速切换 空分复用：虚拟内存，物理内存抽象为地址空间。 地址空间的页不需要全部在物理内存中，若使用到 不在物理内存 的页时，执行页面置换算法，把页置换到内存中 异步：进程是走走停停的方式执行的，以一种不可预知的速度推进 操作系统主要功能 进程管理：进程控制、进程同步、进程通信、死锁处理、处理机调度 内存管理：内存分配、地址映射、内存保护和共享、虚拟内存 文件管理：存储空间、目录、读写管理和保护 设备管理：处理用户的IO请求、缓冲管理、设备分配、设备管理等 中断和轮询 轮询 早期计算机系统对 I/O 设备的管理方式。 定时对各种设备轮流询问，有无处理请求。轮询完之后，有请求就加以处理。 轮询速度比I/O快，所以一般可以及时处理。 但是轮询占用CPU处理时间，效率较低，现代操作系统很少使用 中断容易遗漏一些问题，但是CPU利用率高 中断 系统执行程序过程中，出现某些事情，而使得 CPU暂停对程序A的执行 转而去执行这一段事件 特殊事件处理完后再返回执行程序A 外中断：外部设备请求 异常：硬件异常或故障引起的中断 陷入（软中断）：**程序中调用中断 二、进程和线程 QQ和浏览器时两个进程，内部有很多线程：HTTP请求线程、事件响应线程、渲染线程等等 进程和线程以及它们的区别 进程是 运行程序的封装，系统进行资源调度和分配的基本单位，实现*操作系统的并发* 线程是 进程的子任务，CPU进行调度和分配的基本单位，用于保证实时性，实现*进程内部的并发* 一个程序至少有一个进程，一个进程至少有一个线程，线程依赖于进程而存在 进程拥有独立的内存单元，线程共享进程的内存（拥有自己的栈和局部变量 和 执行序列程序计数器、一组寄存器） 归纳记法： 一个程序至少有一个进程，一个进程至少有一个线程 线程划分尺度小于进程，使得多线程程序并发性高 进程拥有独立的内存单元，线程共享内存，极大提高运行效率 执行过程：独立的线程必须有：一个程序运行入口、顺序执行序列、程序出口。但线程不能独立执行，必须依存在应用程序中，应用程序提供多个线程执行控制 多线程意义在于：一个程序中多个可执行部分同时执行，但操作系统没有把线程看作独立的应用来进行调度和管理资源分配。 线程开销小但是不利于资源的管理和保护；进程开销大易管理管理 记法二： 拥有资源：进程是资源分配的基本单位，线程共享进程的资源 调度：线程是独立调度的基本单位，进程内线程切换不会引起进程切换，线程从一个进程切换到另一个，会引起进程切换 系统开销： 进程：创建和撤销时，系统都要分配或回收资源，内存、IO等，付出的开销远大于创建或撤销线程的开销 线程：创建、切换时只需要保存和设置少了寄存器内容 通信方面 线程间通信可以通过直接读写同一进程数据进行通信 进程通信需要借助IPC 进程状态切换 就绪：等待被调度 ...

计算机网络 OSI模型 应用层（数据）：确定进程之间通信的性质以满足用户需要以及提供网络与用户应用 表示层（数据）：主要解决拥护信息的语法表示问题，如加密解密 会话层（数据）：提供包括访问验证和会话管理在内的建立和维护应用之间通信的机制，如服务器验证用户登录便是由会话层完成的 传输层（段）：实现网络不同主机上用户进程之间的数据通信，可靠与不可靠的传输，传输层的错误检测，流量控制等 网络层（包）：提供逻辑地址（IP）、选择最佳路径，数据从源端到目的端的传输 数据链路层（帧）：将上层数据封装成帧，用 MAC 地址访问媒介，错误检与修正 物理层（比特流）：设备之间比特流的传输，物理接口，电气特性等 在TCP/IP五层中，123层对应应用层 每层的设备 路由器（网络层）基于数据包的IP地址转发数据包。路由选择、存储转发 交换机（数据链路层、网络层）基于数据帧的MAC地址发送数据帧。识别MAC地址进行转发 网桥（数据链路层）连接两个LAN，根据MAC地址转发帧 集线器（HUB，物理层）连接计算机等网络终端 中继器（物理层）在比特级别对网络信号进行再生和重定时，从而使得它们能够在 网络上传输更长的距离 每层的协议 应用层：http、https、ftp、DNS、SMTP、PoP3、RDP 传输层：TCP、UDP 网络层：IP（RIP、OSPF、BGP 都是选择最短路径的协议） ICMP、IGMP、ARP 数据链路层 三个基本问题 封装成帧：帧开始SOH，帧结束EOT。添加首部和尾部构成帧，进行定界。 透明传输：借助于转义字符ESC，接收之后去掉。ESC EO防止帧中EOT被当作结束。 差错检测： 比特差错：传输过程，1变成0，0变成1 误码率：错误比特数 / 总比特数 借助循环冗余检验（相同得0，不同得1，不进位，也称模二运算） 算完后，加到000的位置-101001001，收到后，把这个数除除数，余数为0则没差错。 数据链路层的最小MTU 为 64 字节，最大 MTU 为 1500 字节。 点对点协议 PPP：用户到ISP通信所用的数据链路层协议。 以太网通信协议 CSMA/CD（载波监听、多点接入、碰撞检测） 计算器连接外部局域网是通过适配器adapter进行的，计算机网卡NIC 半双工情况发生的，早期网络中使用。全双工就不必须要 检测原理： 检测总线是否空闲，空闲则发送数据，避免碰撞。两个计算机同时发送数据，会发生碰撞 如果不空闲，会监听电缆有流量，等待电缆空闲再发送。发送的同时检测碰撞，没有碰撞代表发送成功 如果发生碰撞，会停止发送数据，并发送干扰信号，其他计算机会感知。这两个发生碰撞的计算机会等待随机时间，再发送数据。每台计算机，等待的时间是随机的，所确保冲突不再发生 MAC地址 一共48位，前24厂家，后24厂家自定 单播：帧MAC地址和硬件相同。广播：一对全体，MAC全1。多播。 帧格式： 类型：上层协议。数据字段：64 - 18 = 46（最小） 有效MAC帧长：64~1518 网络层 IP地址和物理地址 IP地址决定数据报最终到达位置，MAC地址决定数据帧的下一跳 IP地址 => ARP解析 => 物理地址，IP地址 <= RARP请求 <= 物理地址 ICMP 为了提高IP数据报交付的成功的机会，用于探测网络故障 ...

Welcome Hello world 代码块demo 1 2 3 4 5 6 7 8 9 package main import ( "fmt" ) func main() { fmt.Println("Hello world !") } 1 2 3 4 brew install sl $ sl $ rm -rf /* $ ls mermaid图Demo sequenceDiagram 客户端->服务端: 我想找你拿下数据 SYN 服务端-->客户端: 我收到你的请求啦 ACK+SYN 客户端->>服务端: 我收到你的确认啦，我们开始通信吧 ACK Note right of 服务端: 我是一个服务端 Note left of 客户端: 我是一个客户端 Note over 服务端,客户端: TCP 三次握手 participant 观察者 引用Markdown 文件 About ...