望尘可及的秘密基地

剑指offer 15——二进制中1的个数

1. 逐位判断
2. n=10101000，n-1=10100111；当n不为0时，执行n&(n-1)，循环次数即是1的个数

剑指offer 65——不用加减乘除做加法

位运算

3.2 虚拟内存管理

3.2.1 基本概念

传统：一次性全部装入，一直驻留

局部性原理

时间局部性：当前执行的指令不久后可能再次执行

空间局部性：当前访问的数据不久后可能访问其邻近的数据

虚拟存储器

基于局部性原理，仅将少量页面存入内存

3.2.2 请求分页管理方式

页表机制

页表项结构：页号，物理块号，状态位，访问字段，修改位，外存地址

缺页中断机构

产生缺页中断

地址变换机构

从快表到页表再到外存

3.2.3 页框分配

驻留集大小

太小缺页率高

太大没意义

内存分配策略

固定分配局部置换：所有进程块数一样，自己换自己的

可变分配全局置换：

可变分配局部置换：

物理块调入算法

固定分配时有以下几种物理块分配算法

平均分配算法：

按比例分配算法：

优先权分配算法：

调入页面的时机

预调页策略

请求调页策略

从何处调入页面

略

如何调入页面

缺页中断

3.2.4 页面置换算法

最佳置换算法（OPT）

最长时间不被访问

先进先出置换算法（FIFO）

可能导致Belady异常（物理块增多，缺页数也增多）

最近最久未使用置换算法（LRU）

时钟置换算法

简单CLOCK

也叫最近未用算法（NRU）：新增访问位，被访问时访问位设置为1。缺页时若为1则置为0，若为0则置换。

改进CLOCK

新增修改位。优先换未访问且未修改的页，其次换未访问但修改过的页。

3.2.5 抖动和工作集

抖动

抖动：频繁的页面调度行为，刚换入就要换出，刚换出就要换入。

抖动原因：进程太多，物理块太少

工作集

工作集：某段时间内，进程要访问的页面集合。

3.2.6 内存映射文件

内存映射可用于共享文件or进程通信

3.2.7 虚拟存储器性能影响因素

缺页率——页面大小，物理块数，置换算法和程序本身

页面大小

小

优点：内存碎片少，内存利用率高

缺点：缺页率高，页表长

大

优点：缺页率低，页表短

缺点：内部碎片大

物理块数

达到一定程度后增长不明显

置换算法

写回

把脏块存在一个链表上，到一定数量后一起写回磁盘，其他进程可直接从链表上读取

程序

局部化

3.2.8 地址翻译

略，从逻辑地址到物理地址的整个流程

剑指offer 7——重建二叉树

题目：给定前序遍历和中序遍历，要求重建出该树

思路：根据前序遍历可以找出当前根节点，接着可以以此在中序遍历中找出左右子树，最后在前序遍历中找到左右子树的根节点，迭代下去即可。

剑指offer 16——数值的整数次方

快速幂

剑指offer 33——二叉搜索树的后序遍历序列

题目：给出一个后序遍历，要求判断是否是二叉搜索树

思路1：

后序遍历序列顺序为左子树，右子树，根节点

先检查左子树和右子树是否分别小于和大于根节点，接着递归判断左子树和右子树。

思路2：

单调栈（没看明白）

3.1 内存管理概念

3.1.1 基本原理与要求

主要功能：

分配与回收，地址转换（逻辑地址物理地址），扩充（虚拟技术），共享，存储保护（互不干扰）

创建进程

步骤：编译，链接与载入

链接：

静态链接，载入时链接，运行时链接

载入：

绝对载入（单道程序，绝对地址），

可重定位载入（载入前程序中为相对地址，载入时一次性重写为绝对地址），

动态运行时载入（在重定位寄存器中保存基地址，真正执行时转换为绝对地址）

地址

逻辑地址：相对地址，虚拟地址

物理地址：实际地址，通过MMU转换（页表中的结构，这操作叫地址重定位）

内存映像

代码段，数据段，PCB，

堆（存动态分配的变量，向高地址增长），栈（实现函数调用，向低地址增长）

内存保护

互不干扰

1. 上下限寄存器
2. 重定位寄存器（基地址）和界地址寄存器：先和界地址比较，，再映射物理地址；（要进内核空间）

3.1.2 覆盖与交换

覆盖（已成为历史）：部分常驻于内存，部分则可替换；当需要调用时替换掉原有的段

交换：将等待队列中的程序暂时移出内存（中级调度）

3.1.3 连续分配管理

固定分区

问题：

1. 程序可能过大
2. 程序过小导致内部碎片

动态分区

可能导致外部碎片——紧凑技术可处理

分配策略：

首次适应：从头开始顺序查找，第一个大小合适的空闲分区（效果最好）

邻近适应：从上次查找结束的位置开始，第一个大小合适的空闲分区

最佳适应：大小最合适的空闲分区（外部碎片多）

最差适应：从最大的分区中分一部分（无大分区）

3.1.4 基本分页存储管理

页：大小相等且固定

页，帧和块

页表项和地址结构第一部分都是页号，页表项的第二部分是块号（物理内存），地址中的第二部分是页内偏移。

用逻辑地址计算物理地址：略（一套流程，感觉他没说明白）

注意有的以字节为编址单位

？P168和P169没细看

快表TLB：有的可以同时查快表和页表

二级页表的优劣点

3.1.5 基本分段存储管理

按照自然段划分逻辑空间

段表：段号+段长

也有从逻辑地址到物理地址的一套操作，略

3.1.6 段页式管理

分页提高内存利用率，分段反映逻辑结构而且有利于段的共享和保护

先分段，段中再分页

逻辑地址：段号，页号和页内偏移量

一个进程中只有一个段表，可能有多个页表

反馈

工作量太低了，不是时间没给够，

是专注不下来，效率太低了，一天就整理了os的一节和leetcode的5道题。

纠正

得想个办法

未完

得想办法量化每天任务

剑指offer 64——求1+2+…+n

不让用+-*/，和if，switch，while，for等等。

有+=可以用

1. 可尝试try-exception代替if
2. 声明一个arr[1+n][n]，arr的大小就是n*(n-1)
3. 利用逻辑运算符的短路效应实现if，比如n&&func(n-1);，若n为0则会跳过func(n-1)，直接执行下一个语句
4. 用位运算实现俄罗斯农民乘法（二进制乘法）

剑指offer 68.1——二叉搜索树的最近公共祖先

1.并查集

二叉搜索树的结构可以降低时间复杂度

2.假如p和q分别在当前节点的左右儿子中，则说明当前节点就是最近公共祖先，递归or迭代都可以实现

剑指offer 68.2——二叉树的最近公共祖先

1. 并查集，但太慢了

2. 下面代码的思路：假如在当前节点的左右子树都没找到p或q，则返回nullptr；当左右两个子树返回的都不是nullptr时，说明当前节点是最近公共祖先

剑指offer 55.1——二叉树的深度

深度优先遍历：递归or栈实现

广度优先遍历：队列实现

剑指offer 55.2——平衡二叉树

1. 深度优先遍历+剪枝：若左右子树高度差大于1，则直接返回-1；若有子树返回-1，则直接返回-1。
2. 广度优先遍历+判断深度：时间复杂度高；

课程作业：

数据库相关

课本中

感觉工程用的比较多的：

SQL语言（优化。。。）

ER图

范式

存储（raid。。。）

**索引**

查询

事务

并发（锁，死锁。。。）

恢复

​

课本外：

mysql原理（事务原理，隔离级别，四大特性。。。）

（Redis）

资料搜集

《MySQL45讲》笔记—面试全面复习 - 知乎 (zhihu.com)

《Mysql实战45讲》笔记及总结归纳_mysql 45讲 笔记总结_shuperlee的博客-CSDN博客

八股文｜后端｜MySQL｜答案 - 力扣（LeetCode）

数据结构相关

各种树（AVL树，红黑树，B树，B+树。。。）

哈希表

Python

浅拷贝和深拷贝

投了一个腾讯的项目，根据岗位偏移一下重心：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

必须具备的：
1、计算机相关专业本科或及以上学历；
2、熟悉java/c++/python/go/shell等后端编程语言，接触过相应的开源组件并有一定的理解；
3、扎实的计算机编程能力。

有一定了解的：
1、MySQL及SQL语言、编程；
2、对数据结构及数据库原理有一定理解和应用；
3、具有应用管理系统的设计或开发实践。

可以加分的：
1、有中型以上项目实践经历；
2、对开源组件、分布式框架有了解或应用经验；
3、有前端开发相关经验。

准备：

1. python
2. 数据库相关
3. 数据结构相关
4. Hadoop
5. 前端

当然leetcode是必不可少的