知识图谱

1.redis分布式锁，多个实例共享库存或者销量

2.判断销量是否小于库存，如果小于则继续秒杀，如果大于则返回秒杀结束

3.增加销量

4.创建订单

5.支付成功，更新订单状态为已支付，如果一定时间没有支付，则需要将销量减一

6.

百万qps，数据库扛不住，mysql单机几百qps

不能产生死锁

互斥性，任一时刻只能有一个客户端获取到锁

加锁和解锁必须是同一个客户端，不能误解锁

接口数量

技术指标

接口数量

技术指标

344,939

570,958

357,920

3000

4万多

子主题

上海、北京、南京、广州、北京

pm=static

pm.max_children =128

pm.start_servers = 20

pm.min_spare_servers = 5

pm.max_spare_servers = 35

pm.max_requests = 10000

fastcgi_connect_timeout 5;

fastcgi_send_timeout 10;

fastcgi_read_timeout 10;

gzip on;

worker_processes

worker_connections

最大连接数

原子性操作

数据结构设计

1.生产环境分机房qps、耗时、可用性监控报警

2.提高单机性能

3.利用集群实现高可用

4.压测预案

5.服务灾备

1.根据会员类型，获取该类型下会员权益类实例，调用分阶段函数，precall,  precommit完成事务提交

判断流程

计算方式

压缩列表

双端列表

底层数据结构

理解

hash的扩容和缩容

什么情况下使用压缩列表

整数集合（intset）

字典(hashtable)

什么情况下使用整数集合

底层数据结构

典型应用

为什么有序集合要同时使用字典和跳跃表

编码的转换

底层数据结构

常用操作命令

特点

分布式锁

子主题

1、命令多态

2、编码多态

采用引用计数的方法去实现

redis会对字符串键中包含整数的对象，进行对象共享，范围是0~9999，其它类型比如hash、压缩列表等对象，由于检查其值是否相同，消耗的cpu性能比较大，所以不会做对象共享

1、数据结构

2、有哪些对象

完全基于内存，绝大部分请求是纯粹的内存操作，非常快速。

数据结构简单，对数据操作也简单，Redis中的数据结构是专门进行设计的

单进程单线程

使用多路I/O复用模型，非阻塞IO

1、save命令会用主线程创建RDB文件，会阻塞进程，bgsave命令不会阻塞进程，fork出子进程来创建RDB文件

2、服务器启动时，先判断是否开启AOF持久化功能，如果开启，载入AOF文件，否则才载入RDB文件

3、

定义

触发条件

过程

保证RDB文件完整性

风险

优点

缺点

文件结构

定义

实现

缺点

优点

voltile-lru 从已设置过期时间的数据集中挑选最久没有使用的数据淘汰

voltile-lru 从所有数据集中挑选最久没有使用的数据淘汰

volatile-random 从已设置过期时间的数据集中任意选择数据淘汰

allkeys-random 从数据集中任意选择数据淘汰

volatile-lfu 从设置了过期时间中淘汰使用频率最少的键

allkeys-lfu 从所有键中淘汰使用频率最少的键

volatile-ttl 从已设置过期时间的数据集中挑选将要过期的数据淘汰

noeviction：当内存使用达到阈值的时候，所有引起申请内存的命令会报错

理解

方式

通过配置redis.conf中的maxmemory这个值来开启内存淘汰功能，如果已使用的内存大于maxmemory则开始根据用户配置的不同淘汰策略来淘汰内存（key），从而换取一定的内存

步骤

示意图

步骤

异常情况

定义同上

优点

缺点

定义

任务

缺点

定义

hash函数

高可用

投票机制

优点

定义

一致性hash

定义

常见中间件

开始事务

命令入队

执行事务，返回结果

取消事务

带watch的事务

有一致性

有隔离性

有原子性

持久性

比如下订单和减库存，需要使用锁来锁住

主要利用SETNX 命令和 GETSET命令，解决高并发

SETNX

GETSET

解决方案

1.正常情况下，锁定后，业务执行完毕，解锁，使用del（key）

2.方案1容易出现死锁，获取锁后，需要设置锁超时时间 expire（key， 30）

3.当我们设置了SETNX后,如果redis马上挂掉了,那我们再次 EXPIRE 指令是不是就会无法生效,出现了资源锁死的情况，这时候就要采用方案3来解决，setnx指令本身是不支持传入超时时间的，Redis 2.6.12以上版本为set指令增加了可选参数，伪代码如下：set（key，1，30，NX）,这样就可以取代setnx指令

4.超时后使用del 导致误删其他线程的锁

问题4

应用场景

实现

1.支持事务

2.支持行级锁

3.支持外键约束

4.聚簇索引

6.统计行数，扫描全表

7.删除表时，逐个记录删除

1.支持表级锁

2.支持全文索引

3.统计行数，不需要扫描全表

4.非聚簇索引

特性

特性

意义

生效原则

示例

理解

举例

链接

适用范围

B+tree

B/B- tree

hash

聚簇索引

非聚簇索引

理解

理解

理解

隔离级别

理解

理解

实现原理

隔离级别

sql实现

前提

注意点

show status

explain

show profile

聚合索引优化

1.优化分页查询

用法

注意点

查询的中间结果表

创建视图other

使用视图

1. 提高了重用性，就像一个函数

2. 对数据库重构，却不影响程序的运行

理解

特点

理解

特点

FTP

SSH

Telnet

SMTP

Domain

redis

DNS

HTTP

MySQL数据库服务

rsync

提供格式化的表示和转换数据服务

现在我们已经保证给正确的计算机，发送正确的封装过后的信息了。但是用户级别的体验好不好？难道我每次都要调用TCP去打包，然后调用IP协议去找路由，自己去发？当然不行，所以我们要建立一个自动收发包，自动寻址的功能

建立会话，SESSION认证、断点续传

JPEG、MPEG、ASII

TCP

UDP

提供端到端的可靠报文传递和错误恢复（段Segment）

传输层只是解决了打包的问题。但是如果我有多台计算机，怎么找到我要发的那台？或者，A要给F发信息，中间要经过B，C，D,E，但是中间还有好多节点如K.J.Z.Y。我怎么选择最佳路径？这就是路由要做的事

即路由器，交换机那些具有寻址功能的设备所实现的功能

也称地址解析协议，是根据IP地址获取物理地址的一个TCP/IP协议。它可以解决同一个局域网内主机或路由器的IP地址和MAC地址的映射问题。

我还须要保证传输大量文件时的准确性。于是，我要对发出去的数据进行封装。就像发快递一样，一个个地发

将比特组装成帧和点到点的传递（帧Frame）

主要定义物理设备标准，如网线的接口类型、光纤的接口类型、各种传输介质的传输速率等。它的主要作用是传输比特流(就是由1、0转化为电流强弱来进行传输，到达目的地后在转化为1、0，也就是我们常说的数模转换与模数转换)。这一层的数据叫做比特

定义

定义

1.浏览器获取服务器发来的共钥

2.浏览器生成随机串A作为通信密钥

3.浏览器用共钥加密随机串A，发送给服务器

4.服务器用私钥解密出随机串A得到通信密钥

5.服务端和客户端用随机串A以及对称加密算法进行通信

过程

过程

三次握手

四次挥手

理解

理解

理解

理解

理解

理解

TCP协议是面向字节流的传输协议，要通过TCP连接发送出去的数据都先拷贝到send buffer，可能是从用户空间进程的app buffer拷入的，也可能是从内核的kernel buffer拷入的，拷入的过程是通过send()函数完成的。

最终数据是通过网卡流出去的，所以send buffer中的数据需要拷贝到网卡中。由于一端是内存，一端是网卡设备，可以直接使用DMA(Direct Memory Access,直接存储器访问,外部设备不通过CPU而直接与系统内存交换数据的接口)的方式进行拷贝，无需CPU的参与。也就是说，send buffer中的数据通过DMA的方式拷贝到网卡中并通过网络传输给TCP连接的另一端：接收端。

当通过TCP连接接收数据时，数据肯定是先通过网卡流入的，然后同样通过DMA的方式拷贝到recv buffer中，再通过recv()函数将数据从recv buffer拷入到用户空间进程的app buffer中。

url中增加特殊的字符，然后向数据库发起请求，拼凑出sql语句，达到攻击的目的

1.查询的时候用预处理的方式

2.addslashes()和mysql_real_escape_string()等转义函数进行转义

往Web页面里插入恶意html代码，当用户浏览该页之时，嵌入其中Web里面的html代码会被执行，从而达到恶意攻击用户的特殊目的

htmlspecialchars() 将字符串中的标签转换为html实体

利用用户身份伪造非用户本意的请求操作

1.验证码

2. cookie中放token，服务器验证token

原因

解决办法

原因

类似栈的先入后出原则（FILO）

new 的作用是初始化一个指向类型的指针(*T)，传递给new 函数的是一个类型，不是一个值。返回值是 指向这个新分配的零值的指针

make 的作用是为 slice，map 或 chan 初始化并返回引用(T)

Sprintf()，是把格式字符串输出到指定字符串中，所以参数比printf多一个char*。那就是目标字符串地址。

Printf() 是和标准输出文件(stdout)关联的,Fprintf 则没有这个限制.

Fprintf()， 是把格式字符串输出到指定文件设备中，所以参数笔printf多一个文件指针FILE*。主要用于文件操作。Fprintf()是格式化输出到一个stream，通常是到文件。

数组

切片

1.当一个go程获得Mutex,其他的只能等,除非这个go程释放这个Mutex

2.RWMutex在读锁占用的情况下,会阻止写,但不会阻止读

3.RwMutex在写锁占用的情况下,会阻止写,也阻止读

select 的功能和 select, poll, epoll 相似， 就是监听 IO 操作，当 IO 操作发生时，触发相应的动作

M

P

G

首先创建一个G对象，G对象保存到P本地队列或者是全局队列。P此时去唤醒一个M。P继续执行它的执行序。M寻找是否有空闲的P，如果有则将该G对象移动到它本身。接下来M执行一个调度循环(调用G对象->执行->清理线程→继续找新的Goroutine执行)。

M执行过程中，随时会发生上下文切换。当发生上线文切换时，需要对执行现场进行保护，以便下次被调度执行时进行现场恢复。Go调度器M的栈保存在G对象上，只需要将M所需要的寄存器(SP、PC等)保存到G对象上就可以实现现场保护。当这些寄存器数据被保护起来，就随时可以做上下文切换了，在中断之前把现场保存起来。如果此时G任务还没有执行完，M可以将任务重新丢到P的任务队列，等待下一次被调度执行。当再次被调度执行时，M通过访问G的vdsoSP、vdsoPC寄存器进行现场恢复(从上次中断位置继续执行)。

内存泄露，是从操作系统的角度上来阐述的，形象的比喻就是“操作系统可提供给所有进程的存储空间(虚拟内存空间)正在被某个进程榨干”，导致的原因就是程序在运行的时候，会不断地动态开辟的存储空间，这些存储空间在在运行结束之后后并没有被及时释放掉。

垃圾回收器(Garbage Collector)尝试回收不再被程序所需要的对象所占用的内存

go runtime在一定条件下（内存超过阈值或定期如2min），暂停所有任务的执行，进行mark&sweep操作，操作完成后启动所有任务的执行。在内存使用较多的场景下，go程序在进行垃圾回收时会发生非常明显的卡顿现象（Stop The World）。在对响应速度要求较高的后台服务进程中，这种延迟简直是不能忍受的！

go runtime分离了mark和sweep操作，和以前一样，也是先暂停所有任务执行并启动mark，mark完成后马上就重新启动被暂停的任务了，而是让sweep任务和普通协程任务一样并行的和其他任务一起执行。如果运行在多核处理器上，go会试图将gc任务放到单独的核心上运行而尽量不影响业务代码的执行。go team自己的说法是减少了50%-70%的暂停时间。

理解

理解

hashTable

zval

extensions通过组件的方式提供各种基础服务，常见的内置函数（如array系列）、标准库都是通过extension来实现

server application programming interface

通过一系列钩子函数，使得php可以和外围交互数据

cgi

cli

通过遍历hashtable的双向链表完成

使用工厂模式，可以避免当改变某个类的名字或者方法之后，在调用这个类的所有的代码中都修改它的名字或者参数。

解决全局共享和交换对象。已经创建好的对象，挂在到某个全局可以使用的数组上，在需要使用的时候，直接从该数组上获取即可。将对象注册到全局的树上。任何地方直接去访问。

PHP中的数据库操作有MySQL,MySQLi,PDO三种，可以用适配器模式统一成一致，使不同的数据库操作，统一成一样的API。类似的场景还有cache适配器，可以将memcache,redis,file,apc等不同的缓存函数，统一成一致。
首先定义一个接口(有几个方法，以及相应的参数)。然后，有几种不同的情况，就写几个类实现该接口。将完成相似功能的函数，统一成一致的方法。

将各种截然不同的函数接口封装成统一的API。

将一组特定的行为和算法封装成类，以适应某些特定的上下文环境。

假如有一个电商网站系统，针对男性女性用户要各自跳转到不同的商品类目，并且所有的广告位展示不同的广告。在传统的代码中，都是在系统中加入各种if else的判断，硬编码的方式。如果有一天增加了一种用户，就需要改写代码。使用策略模式，如果新增加一种用户类型，只需要增加一种策略就可以。其他所有的地方只需要使用不同的策略就可以。
首先声明策略的接口文件，约定了策略的包含的行为。然后，定义各个具体的策略实现类。

观察者模式(Observer)，当一个对象状态发生变化时，依赖它的对象全部会收到通知，并自动更新。

观察者模式实现了低耦合，非侵入式的通知与更新机制。

表示在 `php-fpm` 运行时直接 `fork` 出 `pm.max_chindren` 个子进程，

M / (m * 1.2)

表示，运行时 `fork` 出 `start_servers` 个进程，随着负载的情况，动态的调整，最多不超过 `max_children` 个进程。

在 N + 20% 和 M / m 之间。

参数说明：

N 是 CPU 内核数量。

M 是 PHP 能利用的内存数量。

m 是每个 PHP 进程平均使用的内存数量。

hashtable

zval

通常是指用来存放程序中已初始化且不为0的全局变量如：静态变量和常量

空间小，读取快，一般存储长度类型不变的数据类型，比如int、float、bool局部变量

存储长度不固定，比较大的数据类型，比如数组、类、字符串、new出来的对象

函数或者方法

内存泄漏指的是在程序运行过程中申请了内存，但是在使用完成后没有及时释放的现象， 对于普通运行时间较短的程序来说可能问题不会那么明显，但是对于长时间运行的程序， 比如Web服务器，后台进程等就比较明显了，随着系统运行占用的内存会持续上升， 可能会因为占用内存过高而崩溃，或被系统杀掉

1.PHP初始化执行，启动zend引擎，加载已经注册的扩展模块

2.读取脚本文件，zend引擎对脚本进行词法分析、语法分析、生成语法生成树

3.zend引擎编译语法树，生成opcode中间代码

4. zend引擎执行opcode，返回执行结果

是PHP应对每次都需要重复编译的脚本文件而开发的组件，可以节省解析脚本文件的开销

opcache是使用了共享内存的机制，将需要缓存的内容放入到共享内存中，供其它进程使用

不要给opcahe设置过期时间，不要在流量高峰期发布代码

array_keys

array_values

array_flip

in_array

array_search

$bool = array_key_exists('a',$arr)

$lowarr = array_change_key_case($arr,CASE_LOWER)

$arr_count = array_count_values($arr);

$key = array_key_first($arr)

$last = array_pop($array);

$new_array = array_push($array,$value1,$value2,...);
$new_array = array_unshift($array,$value1,$value2,...);

$reverse = array_reverse($arr)

$sum = array_sum($array);
$product = array_product($array);

array_unique($array,SORT_STRING);

$bool = shuffle($arr);

array_rand(array,num=1)

current()：返回数组中的当前元素(第一个指针指向的元素)。

$myarr = array_chunk($arr,2)

$arr_1 = ['A','B','C'];
$arr_2 = ['a','b','c'];
$arr_3 = array_combine($arr_1,$arr_2);

array_fill_keys

array_merge

array_merge_recursive

extract(array)

list($drink, , $power) = array('coffee', 'brown', 'caffeine');

range(0,8,2) ==> [0,2,4,6,8]

2.sort()、rsort():对值进行升序和降序的排序

3.ksort()、krsort():对键名进行升序和降序的排序

4.asort()、arsort():保持索引关系的同时，对值进行升序和降序的排序

5.usort()、uksort()、uasort():使用自定义的排序函数，进行按值的升序排序、按键名的升序排序、保持索引关系的升序排序

6.natsort():使用自然排序算法对数组进行排序
7.natcasesort():使用自然排序算法对数组进行不区分大小写字母的排序

array_walk($arr,'myFunction')：对数组中的每个成员应用自定义函数

array_diff

array_diff_key

array_intersect($array1, $array2, ...)

array_map()

array_walk()

floor

ceil

round

intval

字符串查找

截取字符串

替换字符串

字符长度

分割成数组

字符大小写转换

返回指定的字符或ascii

顺序数组

logn

o(1)

function check($arr,$res)
{
$right = count($arr);
$left = 0;

//匹配循环
while ($left <= $right) {
//得到中间位置
$middle = floor(($right + $left) / 2);
//匹配数据
if ($arr[$middle] == $res) {
return $middle+1;
}
//没有找到
if ($arr[$middle] < $res) {
$left = $middle + 1;
} else {
$right = $middle - 1;
}
}
return false;
}

特点

从左到右，两个元素相比较，假定小的在前，大的在后，如果左边大于右边，则互换值，循环n-1轮

平均o(n2)

最好 o(n)

o(1)

for ($i = 0; $i < count($a) ; $i++) {
　　// 第二层为从$i+1的地方循环到数组最后
for ($j = $i+1; $j < count($a); $j++) {
　　　　　// 比较数组中两个相邻值的大小
if ($a[$i] > $a[$j]) {
$tem = $a[$i]; // 这里临时变量，存贮$i的值
$a[$i] = $a[$j]; // 第一次更换位置
$a[$j] = $tem; // 完成位置互换
}
}
}

取个中间值（一般是数组第一个元素），如果是数组的元素个数<=1，则没必要比较直接返回，如果大于1，则从左到右依次与中间值比较，小于中间值，放左边数组，反之，放右边数组，左右数组作为参数，递归调用该函数，最后合并左数组、中间值、右数组

平均nlogn

最坏 n2

最好 nlogn

计算规则

nlogn

// 判断是否需要运行，因下面已拿出一个中间值，这里<=1
if (count($a) <= 1) {
return $a;
}

$middle = $a[0]; // 中间值

$left = array(); // 接收小于中间值
$right = array();// 接收大于中间值

// 循环比较
for ($i=1; $i < count($a); $i++) {

if ($middle < $a[$i]) {

// 大于中间值
$right[] = $a[$i];
} else {

// 小于中间值
$left[] = $a[$i];
}
}

// 递归排序划分好的2边
$left = quick_sort($left);
$right = quick_sort($right);

// 合并排序后的数据，别忘了合并中间值
return array_merge($left, array($middle), $right);

利用递归，先拆分、后合并、再排序。

均分数列为两个子数列

递归重复上一步骤，直到子数列只有一个元素

父数列合并两个子数列并排序，递归返回数列

时间复杂度O(n log n)

// 归并排序主程序
function mergeSort($arr) {
$len = count($arr);
if ($len <= 1) {
return $arr;
} // 递归结束条件, 到达这步的时候, 数组就只剩下一个元素了, 也就是分离了数组

$mid = intval($len / 2); // 取数组中间
$left = array_slice($arr, 0, $mid); // 拆分数组0-mid这部分给左边left
$right = array_slice($arr, $mid); // 拆分数组mid-末尾这部分给右边right
$left = mergeSort($left); // 左边拆分完后开始递归合并往上走
$right = mergeSort($right); // 右边拆分完毕开始递归往上走
$arr = merge($left, $right); // 合并两个数组,继续递归

return $arr;
}

// merge函数将指定的两个有序数组(arrA, arr)合并并且排序
function merge($arrA, $arrB) {
$arrC = array();
while (count($arrA) && count($arrB)) {
// 这里不断的判断哪个值小, 就将小的值给到arrC, 但是到最后肯定要剩下几个值,
// 不是剩下arrA里面的就是剩下arrB里面的而且这几个有序的值, 肯定比arrC里面所有的值都大所以使用
$arrC[] = $arrA[0] < $arrB[0] ? array_shift($arrA) : array_shift($arrB);
}

return array_merge($arrC, $arrA, $arrB);
}

class Solution {
public:
ListNode *sortList(ListNode *head){
if (!head || !head->next) return head; //空链表和只有一个元素的链表不需要排序

ListNode *p = head, *q = head->next;
//找到链表的中间位置
while (q&&q->next){ //快慢指针，注意必须前两步存在
p = p->next;
q = q->next->next;
}
ListNode *left = sortList(p->next); //右链表
p->next = NULL; //将其断开，为两个链表
ListNode *right = sortList(head);

return merge(left, right);
}

ListNode *merge(ListNode *left, ListNode *right)
{
ListNode dummy(0); //申请一个假节点
ListNode *p = &dummy;
while (left&&right){
if (left->val < right->val){
p->next = left;
left = left->next;
}
else{
p->next = right;
right = right->next;
}
p = p->next;
}
if (left)p->next = left;
if (right)p->next = right;
return dummy.next;
}

};

第一层循环：遍历待比较的所有数组元素
第二层循环：将本轮选择的元素(selected)与已经排好序的元素(ordered)相比较。如果：selected > ordered，那么将二者交换。

如果有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法

//插入排序
function insert_sort($arr) {
//获取数组单元个数
$count = count($arr);
//外层循环用于从未排序区域中取出待排序元素                                                                                                                                                for ($i=1; $i < $count; $i++) {
//获取当前需要插入已排序区域的元素值
$temp = $arr[$i];
//内层循环用于从已排序区域寻找待排序元素的插入位置
for ($j=$i-1; $j >= 0; $j--) {
//如果$arr[$i]比已排序区域的$arr[$j]小，就后移$arr[$j]
 if ($temp < $arr[$j]) {
 $arr[$j+1] = $arr[$j];
 $arr[$j] = $temp;
}  }
}
return $arr; }

堆分为两种：最大堆和最小堆，在最大堆中，父节点的值比每一个子节点的值都要大。在最小堆中，父节点的值比每一个子节点的值都要小。

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆

O(nlogn)

a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] 

因为是数组,下标从0开始,所以,下标为n根结点的左子结点为2n+1,右子结点为2n+2;

$arr=array(49,38,65,97,76,13,27,50);


$arrSize=count($arr);
//将第一次排序抽出来，因为最后一次排序不需要再交换值了。

buildHeap($arr,$arrSize);


for($i=$arrSize-1;$i>0;$i--){

swap($arr,$i,0);

$arrSize--;

buildHeap($arr,$arrSize);

}


//用数组建立最小堆

function buildHeap(&$arr,$arrSize){

//计算出最开始的下标$index,如图,为数字"97"所在位置,比较每一个子树的父结点和子结点,将最小值存入父结点中
//从$index处对一个树进行循环比较,形成最小堆

for($index=intval($arrSize/2)-1; $index>=0; $index--){

//如果有左节点,将其下标存进最小值$min

if($index*2+1<$arrSize){

$min=$arr[$index*2+1] > $arr[$index*2+2] ? $index*2+2 : $index*2+1;

}

//将子结点中较小的和父结点比较,若子结点较小,与父结点交换位置,同时更新较小

if($arr[$min]<$arr[$index]){

swap($arr,$min,$index);

}

}

}


//此函数用来交换下数组$arr中下标为$one和$another的数据

function swap(&$arr,$one,$another){

$tmp=$arr[$one];

$arr[$one]=$arr[$another];

$arr[$another]=$tmp;

}

子主题

1.选出最小数与第一个数交换

2.从除去第一个数，剩余的数中选出最小数与第二个数交换

3.以此类推

平均、最坏、最好 都是n2

n1

function order($arr){
//定义中间变量
$temp = 0;
$count = count($arr);
for($i=0; $i<$count-1; $i++){
//定义最小位置
$minIndex = $i;
for($j= $i+1; $j<$count; $j++){
if($arr[$j] < $arr[$minIndex]){
$minIndex = $j;
}
}
if($i != $minIndex){
$temp = $arr[$i];
$arr[$i] = $arr[$minIndex];
$arr[$minIndex] = $temp;

}
}
return $arr;

}

从n=3开始，第一个数+第二个数=第三个数

long long Fibonacci(unsigned int n)
{
return n < 2 ? n : Fibonacci(n - 1) + Fibonacci(n - 2);
}

时间复杂度 o(n2)

空间复杂度 o(n)

class Solution {

/**
* @param Integer $N
* @return Integer
*/
function fib($N) {
if ($N < 2) return $N;
return $this->fib($N - 1) + $this->fib($N - 2);
}
}

1.有n级台阶,每次走1级或2级,问有多少种走法,可以走完.

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法

function jumpFloor($number)
{
$prePreNum = 1;
$preNum = 2;
$temp = 3;
// write code here
if($number == 1){
return 1;
}
if($number == 2){
return 2;
}

for($i=3;$i<=$number;$i++){
$temp = $prePreNum + $preNum;
$prePreNum = $preNum;
$preNum = $temp;
}
return $temp;
}

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

function jumpFloorII($number)
{
// write code here
if($number == 1) return 1;
return pow(2,($number - 1));
}

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

function maxSubArray($nums) {
for($i=1;$i<count($nums);$i++)
$nums[$i] = max($nums[$i],$nums[$i]+$nums[$i-1]);
return max($nums);
}

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

先把第一个字符串认为是公共前缀，然后从第二个遍历每个字符串，与前一个字符串的每个字母进行比较，如果遇到不同的，则记录不同的位置，然后获取公共前缀，接着用这个公共前缀和后面的字符串再进行比较，最终把公共前缀获取到

class Solution {
/**
* @param String[] $strs
* @return String
*/
function longestCommonPrefix($strs) {
if (empty($strs)) {
return "";
}
$ans = $strs[0];
$count = count($strs);
for ($i = 1; $i < $count; $i++) {
$j = 0;
for (; $j < strlen($ans) && $j < strlen($strs[$i]); $j++) {
if (substr($ans, $j, 1) != substr($strs[$i], $j, 1)) {
break;
}
}
$ans = substr($ans, 0, $j);
if ($ans == "") {
return "";
}
}
return $ans;
}
}

双指针，快慢指针

public int removeDuplicates(int[] nums) {
if (nums.length == 0) return 0;
int i = 0;
for (int j = 1; j < nums.length; j++) {
if (nums[j] != nums[i]) {
i++;
nums[i] = nums[j];
}
}
return i + 1;
}

给定两个数组，编写一个函数来计算它们的交集。

把一个数组存到hash中，遍历另一个数组，检查是否在哈希中，在的话就是目标元素，同时为了唯一性删除哈希中已存在元素。

class Solution {

/**
* @param Integer[] $nums1
* @param Integer[] $nums2
* @return Integer[]
*/
function intersection($nums1, $nums2) {
$map = [];
$res = [];
for ($i = 0;$i < count($nums1); $i++) {
$map[$nums1[$i]] = true;
}

for ($i = 0; $i < count($nums2); $i++) {
if ($map[$nums2[$i]]) {
$res[] = $nums2[$i];
unset($map[$nums2[$i]]);
}
}

return $res;
}
}

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

输出: [1,2,2,3,5,6]

两个指针从后向前：
两个指针分别指向每个数组的尾部：
这样不用额外的空间。

function merge2(&$nums1, $m, $nums2, $n) {
//两个指针的下标
$p1 = $m - 1;
$p2 = $n - 1;
$p = $m + $n - 1;//指向 nums1合并后末尾的位置
while(($p1 >=0) && ($p2 >=0)) {
$nums1[$p--] = ($nums1[$p1] < $nums2[$p2]) ? $nums2[$p2--] : $nums1[$p1--];//谁大，把谁放在末尾
}
//当然也有可能nums1都很大，已经循环结束，但是nums2还没合并过去
while ($p1 < 0 && $p2 >= 0) {
$nums1[$p--] = $nums2[$p2 --];
}
$nums1 = array_splice($nums1, 0, $m+$n);//截取后面多余的
}

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

1.先排序，那么第k个元素自然就是第k大的元素了

class Solution {

/**
* @param Integer[] $nums
* @param Integer $k
* @return Integer
*/

private $nums = [];
function findKthLargest($nums, $k) {
$count = count($nums);
$this->nums = $nums;
$this->quicksort($this->nums, 0, $count-1);
return $this->nums[$count-$k];
}

function quicksort(&$arr, $begin, $end){
if($begin >= $end){
return;
}
$l = $begin;
$r = $end;
$flag = $arr[$begin];

while($l < $r){
while($l < $r && $flag < $arr[$r] ){
$r--;
}
if($l < $r){
$this->swap($arr, $l, $r);
$l ++;
}

while($l < $r && $flag > $arr[$l] ){
$l++;
}
if($l < $r){
$this->swap($arr, $l, $r);
$r --;
}

}
$arr[$l] = $flag;
$this->quicksort($arr,$begin,$l-1);
$this->quicksort($arr,$l+1,$end);


}

function swap(&$arr, $l, $r){
$temp = $arr[$l];
$arr[$l] = $arr[$r];
$arr[$r] = $temp;
}
}

• 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

function findNumberIn2DArray($matrix, $target) {
//从左下角开始往上找
$row = count($matrix);
$col = count($matrix[0]);
$x = $row -1 ;
$y = 0;
while($x >=0 && $y < $col){
if($matrix[$x][$y] == $target ){
return true;
}elseif($matrix[$x][$y] > $target ){
$x --;
}else{
$y ++;
}
}
return false;
}

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

function rotate(&$nums, $k){
$len = count($nums);
$k %= $len;
$this->reverse($nums, 0, $len-1);
$this->reverse($nums, 0, $k-1);
$this->reverse($nums, $k, $len-1);
}
function reverse(&$nums, $start, $end){
while($start < $end){
$tmp = $nums[$start];
$nums[$start++] = $nums[$end];
$nums[$end--] = $tmp;
}
}

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

function generate($numRows) {
$res = [];
for($i = 0; $i< $numRows; $i++){
for($j = 0; $j<= $i; $j++){
if($j==$i || $j == 0){
$res[$i][$j] = 1;
}else{
$res[$i][$j] = $res[$i-1][$j-1]+ $res[$i-1][$j];
}
}
}
return $res;
}

题目

代码

解题思路

复杂度

代码

题目

代码

class Solution
{
/**
* @param ListNode $head
* @return ListNode
*/
function reverseList($head)
{
// double pointer
// 我们可以申请两个指针，第一个指针叫 prev，最初是指向 null 的。
// 第二个指针 cur 指向 head，然后不断遍历 cur。
// 每次迭代到 cur，都将 cur 的 next 指向 pre，然后 pre 和 cur 前进一位。
// 都迭代完了 (cur 变成 null 了)，pre 就是最后一个节点了。
$prev = null;
$cur = $head;
while ($cur) {
$next = $cur->next;
$cur->next = $prev;
$prev = $cur;
$cur = $next;
}
return $prev;
}
}

function printListFromTailToHead($head)
{
$list = [];
while($head != null){
$list[] = $head->val;
$head = $head->next;
}
return array_reverse($list);
}

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

方法一: 暴力法

方法二: 哈希表法

方法三：双指针法

利用快慢指针

function isPalindrome($head){
$fast = $head; //设定快指针；
$slow = $head; //设定慢指针；
//先利用快慢指针遍历链表，快指针到达终点最后一个元素时，使慢指针指向中点；
while($fast !== null && $fast->next !== null){
$fast = $fast->next->next; //走2步；
$slow = $slow->next; //走1步；
}

//此时slow已到达中点；反转后半部分
$reveredList = null; //定义空指针，用于存放反转链表，指向头元素；
$tmpCurrent = $slow->next; //定义当前需要反转的元素，反转后半部分；
while($tmpCurrent !== null){ //当当前的元素为空时退出；
$next = $tmpCurrent->next; //先将下一个要反转的元素赋值给next；
$tmpCurrent->next = $reveredList; //实现当前元素的next指针反转过来指向reveredList头元素；
$reveredList =$tmpCurrent; //reveredList向后移动一位指向最新反转的元素，准备下一次反转；
$tmpCurrent = $next; //把当前需要反转指针向后移动一位，指向下一位需要反转的元素；

}
//遍历链表比较
$h = $head->next; //准备好原始的链表
while($reveredList !== null){ //当已经反转好的链表最后元素为空
if ($reveredList->val != $h->val) {//比较元素的值
return false;
}
$h = $h->next; //向后移动一位
$reveredList = $reveredList->next; //准备比较下一位元素
}
return true;
}

输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9

func deleteNode(node *ListNode) {
node.Val = node.Next.Val
node.Next = node.Next.Next
}

何时终止：当 l1 为空或 l2 为空时结束
返回值：每一层调用都返回排序好的链表头
本级递归处理：如果 l1.val 值更小，则将 l1.next 与排序好的链表头相接，l2 同理
O(m+n)，mm 分别为 l1、l2 的长度

// 递归实现
function mergeTwoLists($l1, $l2) {

if(empty($l1)) return $l2;
if(empty($l2)) return $l1;

if($l1->val<= $l2->val) {
$l1->next = $this->mergeTwoLists($l1->next,$l2);
return $l1;
}else{
$l2->next = $this->mergeTwoLists($l1,$l2->next);
return $l2;
}
}

给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
};

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

前后指针比较值，相同则删除

function deleteDuplicates($head) {
$cur = $head;
while($cur != null && $cur->next != null){
if($cur->val == $cur->next->val){
$cur->next = $cur->next->next;
}else{
$cur = $cur->next;
}
}

return $head;
}

子主题

class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
ListNode* fast = head;
ListNode* low = head;
while (fast != NULL) {
fast = fast->next;
if (k == 0) {
low = low->next;
} else {
k--;
}
}
return low;
}
};

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

function reConstructBinaryTree($pre, $vin)
{
// write code here
if($pre && $vin){
$treeRoot = new TreeNode($pre[0]);
$index = array_search($pre[0],$vin);
$treeRoot->left = reConstructBinaryTree(array_slice($pre,1,$index), array_slice($vin,0,$index));
$treeRoot->right = reConstructBinaryTree(array_slice($pre,$index + 1), array_slice($vin,$index + 1));
return $treeRoot;
}

}

函数

函数

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

function TreeDepth($pRoot)
{
// write code here
if($pRoot == null)
return 0;
$l = TreeDepth($pRoot->left);
$r = TreeDepth($pRoot->right);
return $l > $r ? $l+1 : $r +1;
}

子主题

子主题

理解

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == NULL)
return NULL;
return bfs(root,p,q);
}
TreeNode* bfs(TreeNode* root, TreeNode* p, TreeNode* q) {
// 边界条件
if(root == NULL) return NULL;
if(root == p) return p;
if(root == q) return q;

TreeNode* l = bfs(root -> left, p, q); // 向左查
TreeNode* r = bfs(root -> right, p, q); // 向右查

// 当前子树的最近公共祖先判断
if(l != NULL && r != NULL) return root;
else if(l != NULL) return l;
else return r;
}

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//如果是分布在两边，则为root，如果都在左边，遍历左边，如果都在右边，遍历右边
if(root->val > p->val && root->val > q->val){
root = lowestCommonAncestor(root->left, p, q);
}else if(root->val < p->val && root->val < q->val){
root = lowestCommonAncestor(root->right, p, q);
}

return root;
}

请完成一个函数，输入一个二叉树，该函数输出它的镜像

function mirrorTree($root) {
if($root == null){
return [];
}
$temp = new TreeNode(0);
$temp = $root->left;
$root->left = $root->right;
$root->right = $temp;

$this->mirrorTree($root->left);
$this->mirrorTree($root->right);

return $root;
}
}

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。

class Solution {

/**
* @param TreeNode $root
* @return Integer
*/
function diameterOfBinaryTree($root) {
$max = 0;
if ($root == null) return $max;

$this->deep($root, $max);

return $max;
}

public function deep($node, &$max)
{
if ($node == null) return 0;

$left = $this->deep($node->left, $max);
$right = $this->deep($node->right, $max);

$max = max($max, $left + $right);
return max($left, $right) + 1;
}
}

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

function mergeTrees($t1, $t2) {
if($t1 ==null){
return $t2;
}
if($t2 ==null){
return $t1;
}
$t1->val += $t2->val;
$t1->left = $this->mergeTrees($t1->left, $t2->left);
$t1->right = $this->mergeTrees($t1->right, $t2->right);

return $t1;
}

子主题

class Solution {

/**
* @param TreeNode $root
* @return Boolean
*/
function isSymmetric($root) {
return $this->isMirror($root,$root);
}

function isMirror($t1,$t2){
if($t1==null&&$t2==null){
return true;
}
if($t1==null||$t2==null){
return false;
}
return ($t1->val==$t2->val)&&
$this->isMirror($t1->right,$t2->left)&&
$this->isMirror($t1->left,$t2->right);
}
}

public boolean isSameTree(TreeNode p, TreeNode q) {
if(p==null && q==null) return true;
if(p==null || q==null) return false;
return (p.val==q.val) && isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

给定一个二叉树，判断它是否是高度平衡的二叉树。

class Solution {

/**
* @param TreeNode $root
* @return Boolean
*/
function isBalanced($root) {
if($root == null){
return true;
}
$left = $this->gethight($root->left);
$right = $this->gethight($root->right);

if(abs($left-$right) > 1){
return false;
}
return $this->isBalanced($root->left) && $this->isBalanced($root->right);
}

function gethight($root){
if($root ==null){
return 0;
}
return max($this->gethight($root->left),$this->gethight($root->right))+1;
}
}

也叫二叉排序树，简称为BST。它具有这样的性质：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉搜索树。(仔细观察可以发现，二叉搜索树的中序遍历可以得到一个有序数组)。

二叉搜索树中的搜索

判断是否是二叉搜索树

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

class Solution {

/**
* @param TreeNode $root
* @return Integer
*/
public $max = 0;
function maxPathSum($root) {
if(empty($root)){
return 0;
}
$this->max = $root->val;
$this->maxPath($root);
return $this->max;
}
function maxPath($node){
if(empty($node)){
return 0;
}
$left = $this->maxPath($node->left);
$right = $this->maxPath($node->right);
$all = $node->val + $left + $right;
$half = $node->val + max(0, $left, $right);
$this->max = max($this->max, $all, $half);
return $half;
}
}

给定一棵二叉搜索树，请找出其中第k大的节点。

function kthLargest($root, $k) {
$stack = [];
$count = 1;
while(!empty($root) || !empty($stack)){
while($root != null){
array_push($stack, $root);
$root = $root->right;
}
$node = array_pop($stack);
if($count == $k){
return $node->val;
}
$count ++;
$root = $node->left;
}
return 0;
}

若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

堆排序

高度为h，由2^h-1个节点构成的二叉树称为满二叉树。

从根节点出发，沿着左子树方向进行纵向遍历，直到找到叶子节点为止。然后回溯到前一个节点，进行右子树节点的遍历，直到遍历完所有可达节点为止。利用数据结构“栈”，父节点入栈，父节点出栈，先右子节点入栈，后左子节点入栈。递归遍历全部节点。

先序遍历

中序遍历

后序遍历

层次遍历

从根节点出发，沿着左子树方向进行纵向遍历，直到找到叶子节点为止。然后回溯到前一个节点，进行右子树节点的遍历，直到遍历完所有可达节点为止。利用数据结构“栈”，父节点入栈，父节点出栈，先右子节点入栈，后左子节点入栈。递归遍历全部节点。

层次遍历

class Solution {

/**
* @param Integer[] $nums
* @return TreeNode
*/
public $nums = [];
function sortedArrayToBST($nums) {
$this->nums = $nums;
return $this->helper(0, count($nums)-1);
}
function helper($left, $right){
if($left > $right){
return null;
}
$mid = ($right + $left) / 2;
$mid = ceil($mid);
$node = new TreeNode($this->nums[$mid]);
$node->left = $this->helper($left, $mid-1);
$node->right = $this->helper($mid+1, $right);

return $node;

}
}

function climbStairs($n) {
$prepre = 1;
$pre = 2;
$temp = 3;
if($n ==1 ){
return 1;
}
if($n ==2 ){
return 2;
}
for($i = 3 ; $i <= $n; $i ++){
$temp = $prepre + $pre;
$prepre = $pre;
$pre = $temp;
}

return $temp;
}

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和

function maxSubArray($nums) {
for($i = 1; $i< count($nums); $i++){
$nums[$i] = max($nums[$i], $nums[$i] + $nums[$i-1]);

}
return max($nums);
}

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

public int maxProfit(int[] prices) {
int len = prices.length;
if (len < 2) {
return 0;
}

// 0：用户手上不持股所能获得的最大利润，特指卖出股票以后的不持股，非指没有进行过任何交易的不持股
// 1：用户手上持股所能获得的最大利润

// 注意：因为题目限制只能交易一次，因此状态只可能从 1 到 0，不可能从 0 到 1
// 状态转移方程：
// dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
// dp[i][1] = max(dp[i - 1][1], -prices[i])
int[][] dp = new int[len][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i = 1; i < len; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
}
return dp[len - 1][0];
}

function maxProfit($prices) {
$max = 0;
$min = $prices[0];
for($i = 0 ; $i< count($prices); $i ++ ){
$min = min($min, $prices[$i]);
$max = max($max, ($prices[$i] - $min));

}
return $max;
}

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

class Solution {

/**
* @param String $s
* @return Boolean
*/
function isValid($s) {
//构造映射map
$map = [')' => '(', ']' => '[', '}' => '{'];
$stack = [];
for($i = 0; $i < strlen($s); $i++){
if(isset($map[$s[$i]])) {
$key = array_pop($stack);
if($map[$s[$i]] != $key){
return false;
}
}else{
array_push($stack,$s[$i]);
}
}

return $stack ? false : true;
}
}

子主题

运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

class LRUCache {
/**
* @param Integer $capacity
*/
function __construct($capacity) {
$map = [];
$list = [];
$this->capacity = $capacity;
}

/**
* @param Integer $key
* @return Integer
*/
function get($key) {
if(!array_key_exists( $key, $this->map)){
return -1;
}else{
unset($this->list[array_search($key, $this->list)]);
array_push($this->list, $key);
return $this->map[$key];
}
}

/**
* @param Integer $key
* @param Integer $value
* @return NULL
*/
function put($key, $value) {
if(array_key_exists($key, $this->map)){
unset($this->list[array_search($key, $this->list)]);
}else{
if(count($this->map) == $this->capacity){
$firstkey = array_shift($this->list);
unset($this->map[$firstkey]);
}
}
$this->map[$key] = $value;
array_push($this->list, $key);

}
}

LFU（Least Frequently Used ，最近最少使用算法）也是一种常见的缓存算法。

顾名思义，LFU算法的思想是：如果一个数据在最近一段时间很少被访问到，那么可以认为在将来它被访问的可能性也很小。因此，当空间满时，最小频率访问的数据最先被淘汰。

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) -- 将元素 x 推入栈中。
pop() -- 删除栈顶的元素。
top() -- 获取栈顶元素。
getMin() -- 检索栈中的最小元素。
示例:

class MinStack {
/**
* initialize your data structure here.
*/
public $stack = [];
public $helper = [];
function __construct() {
}

/**
* @param Integer $x
* @return NULL
*/
function push($x) {
array_push($this->stack,$x);
if(count($this->helper) == 0 || $x <= end($this->helper)){
array_push($this->helper,$x);
}
}

/**
* @return NULL
*/
function pop() {
if(!empty($this->stack)){
$key = array_pop($this->stack);
}
if(isset($key) && count($this->helper) && $key == end($this->helper)){
array_pop($this->helper);
}
}

/**
* @return Integer
*/
function top() {
if(count($this->stack) == 0){
return null;
}
return end($this->stack);
}

/**
* @return Integer
*/
function getMin() {
if(count($this->helper) == 0){
return null;
}
return end($this->helper);
}
}

/**
* Your MinStack object will be instantiated and called as such:
* $obj = MinStack();
* $obj->push($x);
* $obj->pop();
* $ret_3 = $obj->top();
* $ret_4 = $obj->getMin();
*/

回文串是一个正读和反读都一样的字符串

设置头，尾双指针，指针向中间遍历判断字符串。跳过非数字和字母字符，满足数字或字母的字符，统一转化为小写，判断两个字符值是否相等

class Solution {
/**
* 双指针解法
* 时间复杂度 O(n)
* 空间复杂度 O(1)
* @param String $s
* @return Boolean
*/
function isPalindrome($s)
{
$i = 0;
$j = strlen($s) - 1;
while($i < $j) {
// 非数字和字符串跳过
while ($i < $j && !ctype_alnum($s[$i])) $i++;
while ($i < $j && !ctype_alnum($s[$j])) $j--;
if (strtolower($s[$i]) != strtolower($s[$j])) return false;
$i++;
$j--;
}
return true;
}
}

function isPalindrome($x) {
if($x !== ''){
$x = (string)$x;
$x_length = strlen($x);
if($x_length == '1') return true;
for($i = 0; $i < $x_length/2; $i++){
if($x[$i] != $x[$x_length - $i - 1]) return false;
}
return true;
}
return false;
}

判断是否是字母和数字或字母数字的组合

双指针，首尾同时扫描并交换

class Solution {

/**
* @param String[] $s
* @return NULL
*/
function reverseString(&$s) {
$front = 0;
$rear = count($s) - 1;
while ($front < $rear) {
$tmp = $s[$front];
$s[$front++] = $s[$rear];
$s[$rear--] = $tmp;
}
}
}

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

function replaceSpace($str)
{
return $r = str_replace(' ','%20',$str);
}

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。

注意：

num1 和num2 的长度都小于 5100.
num1 和num2 都只包含数字 0-9.
num1 和num2 都不包含任何前导零。
你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式。

双指针法

function addStrings($num1, $num2) {
$p1 = strlen($num1) - 1;
$p2 = strlen($num2) - 1;

$carry = 0;
$res = '';

while ($p1 >= 0 OR $p2 >= 0) {
$n1 = $p1 >= 0 ? $num1[$p1] : 0;
$n2 = $p2 >= 0 ? $num2[$p2] : 0;

$sum = $n1 + $n2 + $carry;
$carry = intval($sum / 10);
$res = ($sum % 10) . $res;
$p1--;
$p2--;
}

if ($carry > 0) {
$res = $carry . $res;
}

return $res;
}
}

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

class Solution {

/**
* @param Integer $x
* @return Integer
*/
function mySqrt($x) {
if($x <= 1){
return $x;
}
$left = 1;
$right = $x;
while($left < $right){
$mid = $left+ (int)(($right- $left)/2) +1 ;
$num = $mid*$mid;

if($num > $x){
$right = $mid-1;
}else{
$left = $mid;
}

}

return $right;
}
}

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。

双指针法

function strStr($haystack, $needle) {
$i=0;
$j=0;
while(isset($haystack[$i]) && isset($needle[$j])){
if($haystack[$i] == $needle[$j]){
$i++;
$j++;
}else{
$i = $i - $j + 1;
$j = 0;
}
}
if($j==strlen($needle)){
return $i-$j;
}
return -1;
}

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

class Solution {

/**
* @param String[] $strs
* @return String
*/
function longestCommonPrefix($strs) {
$count = count($strs);
$common = $strs[0];

if(empty($strs)){
return '';
}

for($i = 1 ; $i < $count; $i ++ ){

for($j = 0 ; $j< strlen($common) && $j< strlen($strs[$i]); $j ++){
if(substr($common, $j, 1) != substr($strs[$i], $j, 1)){
break;
}
}

$common = substr($common, 0, $j);

if($common == ''){
return '';
}
}

return $common;

}
}

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c。

子主题

两个位都为1时，结果才为1

两个位都为0时，结果才为0

异或

各系统之间由进程内的通信，变为进程之间的通信，最常用的通信方式就是网络调用

RPC

kafka

理解

适用场景

理解

适用场景

依赖的服务长时间响应失败或者超时，就要考虑不去调用下游了，熔断之后还要间歇性去访问下游，如果下游服务恢复了，关闭熔断策略

定义

缺点

全称

定义

缺点

cd .. 返回上一级目录

cd ../..返回上两级目录

cd - 返回上次所在的目录

cd ~ 或者 cd 返回用户主目录

cd /返回用户根目录

ls 查看目录中的文件

ls -F 查看目录中的文件

ls -l 显示文件和目录的详细资料

ls -a 显示隐藏文件

显示目录的树形结构

mkdir abc 默认权限drwxr-xr-x

mkdir -p test/test1 递归创建多个目录

mkdir -v hao 创建新目录都显示信息

mkdir -m 777 pc 创建权限为777的目录

可以删除空文件或者空目录

rm 删除文件，目录不会删除，文件可以恢复

rm -f 强制删除，不询问

rm -r 将参数中列出的全部目录和子目录均递归地删除

rm -i 询问是否删除

mv test.log test1.txt 重命名

mv info/ logs 如果logs不存在，则重命名目录

mv log1.txt log2.txt log3.txt test3 将文件移动到目录

-i 询问是否覆盖已有同名文件

-f 强制覆盖已有同名文件

cp file1 file2 当前目录下复制文件

cp file1 file2 dir 拷贝文件到dir目录下

cp -r directory_1 /home/pungki/office 拷贝目录

cp dir/* . 把目录下文件复制到当前目录

ln -s file1 lnk1 创建一个指向文件或目录的软链接,类似于快捷方式，但是与主连接是同步修改的，可以跨分区和文件系统，可以创建目录和文件，如果原文件被删除，则软连接成为死连接

ln file1 lnk1 创建一个指向文件或目录的物理链接 ，创建一个，增加一个连接数，不能跨分区和文件系统，不能创建目录，只能创建文件，inode相同

touch -r log.log log2012.log 更新log.log的时间和log2012.log时间戳相同

touch -t 201211142234.50 log.log 设定文件时间

iconv -l 查看所有编码

iconv -f gbk -t utf-8 cloud.cpp 将gbk转换成utf8

介绍

相关命令

硬链接

软链接（符号链接）

-type b/d/c/p/l/f #查是块设备、目录、字符设备、管道、符号链接、普通文件

-mtime -n +n #按文件更改时间来查找文件，-n指n天以内，+n指n天以前

-atime -n +n #按文件访问时间来查找文件，-n指n天以内，+n指n天以前

-ctime -n +n #按文件创建时间来查找文件，-n指n天以内，+n指n天以前

find / -name file1 从 '/' 开始进入根文件系统搜索文件和目录

find / -user user1 搜索属于用户 'user1' 的文件和目录

find . -name "*.log" 根据关键字查找

find /usr/bin -type f -amin n 查找系统中最后N分钟访问的文件

find /usr/bin -type f -atime n 查找系统中最后n*24小时访问的文件

find /usr/bin -type f -cmin n 查找系统中最后N分钟被改变文件状态的文件

find /usr/bin -type f -ctime n 查找系统中最后n*24小时被改变文件状态的文件

find /usr/bin -type f -mmin n 查找系统中最后N分钟被改变文件数据的文件

find /usr/bin -type f -mtime n 查找系统中最后n*24小时被改变文件数据的文件

find /opt/soft/test/ -perm 777 按照目录或文件的权限来查找文件

find . -type d | sort 查找当前所有目录并排序

find /home -size +512k 查大于512k的文件

find /home -size -512k 查小于512k的文件

find /home -used -2 列出文件或目录被改动过之后，在2日内被存取过的文件或目录

find /tmp -name tmp.txt -exec cat {} \; 查找文件并执行cat命令

find / -group cat # 查找在系统中属于cat属组的文件

find / -nouser #查找在系统中属于作废用户的文件

find /home -name tmp.txt -maxdepth 4 列出/home内的tmp.txt 查时深度最多为3层

find ./ -mtime -1 -type f -exec ls -l {} \; 查询当天修改过的文件

find . -type d -print 从当前目录查找，仅查找目录，找到后，打印路径名

find / -name access_log 2 >/dev/null 无错误查找

find / -size 1500c （查找1,500字节大小的文件，c表示字节）

find . -name '*.html' -exec grep 'mailto:'{} 查找字符串

定义

命令

定义

定义

读取--用数字4表示

写入--用数字2表示

执行--用数字1表示

有只读权限的用户不能用cd进入该目录：还必须有执行权限才能进入

有执行权限的用户只有在知道文件名，并拥有读权利的情况下才可以访问目录下的文件

必须有读和执行权限才可以ls列出目录清单，或使用cd命令进入目录

chmod -R 777 /home/mypackage 加入-R 参数，就可以将读写权限传递给子文件夹

定义

命令

定义

命令

定义

命令

zip newfilename.zip filename1 filename2

zip -r newfilename.zip file1 file2 －r表示递归压缩子目录下所有文件

zip -d myfile.zip smart.txt 删除压缩文件中smart.txt文件

zip -m myfile.zip ./rpm_info.txt 向压缩文件中myfile.zip中添加rpm_info.txt文件

unzip -o -d /home/sunny myfile.zip 把myfile.zip文件解压到 /home/sunny/ -o:不提示的情况下覆盖文件；-d /home/sunny 指明将文件解压缩到/home/sunny目录下

-c: 建立压缩档案

-x：解压

-t：查看内容

-r：向压缩归档文件末尾追加文件

-u：更新原压缩包中的文件

tar –cvf jpg.tar *.jpg //将目录里所有jpg文件打包成tar.jpg

tar –czf jpg.tar.gz *.jpg //将目录里所有jpg文件打包成jpg.tar后，并且将其用gzip压缩，生成一个gzip压缩过的包，命名为jpg.tar.gz

tar –cjf jpg.tar.bz2 *.jpg //将目录里所有jpg文件打包成jpg.tar后，并且将其用bzip2压缩，生成一个bzip2压缩过的包，命名为jpg.tar.bz2

rar a jpg.rar *.jpg //rar格式的压缩

tar –xvf file.tar //解压 tar包

tar -xzvf file.tar.gz //解压tar.gz

tar -xjvf file.tar.bz2 //解压 tar.bz2

unrar e file.rar //解压rar

df -h 查看磁盘还剩多少空间

du -sh [目录名] 查看该目录大小

du -sm [文件夹] 返回该文件夹总M数

du -h --max-depth=1 [目录名] 查看指定文件夹下的所有文件大小（包含子文件夹）

i: 在当前光标所在字符的前面，转为输入模式

a: 在当前光标所在字符的后面，转为输入模式

o: 在当前光标所在行的下方，新建一行，并转为输入模式

I：在当前光标所在行的行首，转换为输入模式

A：在当前光标所在行的行尾，转换为输入模式

O：在当前光标所在行的上方，新建一行，并转为输入模式

gI: 在当前行第一列插入

vim -c cmd file: 在打开文件前，先执行指定的命令

vim -r file: 恢复上次异常退出的文件

vim -R file: 以只读的方式打开文件，但可以强制保存

vim -M file: 以只读的方式打开文件，不可以强制保存

vim -y num file: 将编辑窗口的大小设为num行

vim + file: 从文件的末尾开始

vim +num file: 从第num行开始

vim +/string file 打开file，并将光标停留在第一个找到的string上

h或退格: 左移一个字符

l或空格: 右移一个字符

j 下移一个字符

k 上移一个字符

0: 移动到行首

$: 移动到行尾

gg: 到文件头部

G: 到文件尾部

(: 前移1句

): 后移1句

{: 前移1段

}: 后移1段

ctrl+f: 下翻一屏

ctrl+b: 上翻一屏

ctrl+d: 下翻半屏

ctrl+u: 上翻半屏

ctrl+e: 向下滚动一行

ctrl+y: 向上滚动一行

zz: 将当前行移动到屏幕中央

zt: 将当前行移动到屏幕顶端

zb: 将当前行移动到屏幕底端

[n]x: 剪切光标右边n个字符，相当于d[n]l

[n]X: 剪切光标左边n个字符，相当于d[n]h

y: 复制在可视模式下选中的文本

yy or Y: 复制整行文本

y[n]w: 复制一(n)个词

y$: 从光标当前位置复制到行尾

y0: 从光标当前位置复制到行首

:m,ny<cr> 复制m行到n行的内容

y1G或ygg: 复制光标以上的所有行

yG: 复制光标以下的所有行

[n] dd: 删除（剪切）1(n)行

p: 在光标之后粘贴

P: 在光标之前粘贴

d0: 删除（剪切）当前位置到行首的内容

#dd」：从光标所在行开始删除#行

/something: 在后面的文本中查找something

?something: 在前面的文本中查找something

n: 向后查找下一个

N: 向前查找下一个

/pattern/+number: 将光标停在包含pattern的行后面第number行上

/pattern/-number: 将光标停在包含pattern的行前面第number行上

v，V 按字符、行进行选择

y 将选区复制

p 将选区粘贴

d 将选区删除

:sp 分割当前窗口

:sp 1.php 将其他文件分割进来

ctrl+w 然后 箭头 可以在多个窗口间移动

R 运行 runnable (on run queue)

D 不可中断(收到信号不唤醒和不可运行, 进程必须等待直到有中断发生)

S 中断(休眠中, 受阻, 在等待某个条件的形成或接受到信号)

T 停止(进程收到SIGSTOP, SIGSTP, SIGTIN, SIGTOU信号后停止运行)

Z 僵死(进程已终止, 但进程描述符存在, 直到父进程调用wait4()系统调用后释放)

截图

每一列含义

截图

术语

参数说明

每一列

查看打开指定文件的所有进程：lsof 文件名

显示指定进程名的所有进程：lsof -c 进程名

显示用户能打开的所有进程：lsof -u 用户名

显示指定目录下被进程打开的文件：lsof +d 目录名

30 21 * * * 每天的21:30分执行

1 1 1,10,20 * * 每月的1、10、20号执行【逗号】

0,30 18-23 * * * 18点到23点之间，0或30分执行【-】

* */1 * * * 每隔一个小时执行【/】

* 23-7/1 * * *23到7点之间，每隔一个小时【-/】

crontab -l 列出所有

crontab -e 编辑

crontab -r 删除

cat /etc/crontab 查看crontab配置

就是linux的用户库，保存所有用户但是不保存密码

adm:x:3:4:adm:/var/adm:/bin/bash

用户名:密码占位x:UID:GID:home目录:使用的shell

用户密码，是加密过的

还包含密码修改&过期等信息

理解

理解

理解

理解

理解

1. JobClient

2. JobTracker

3. TaskTracker

4. HDFS

1. JobClient通过RPC协议向JobTracker请求一个新应用的ID，用于MapReduce作业的ID

2. JobTracker检查作业的输出说明。例如，如果没有指定输出目录或目录已存在，作业就不提交，错误抛回给JobClient，否则，返回新的作业ID给JobClient

3. JobClient将作业所需的资源（包括作业JAR文件、配置文件和计算所得得输入分片）复制到以作业ID命名的HDFS文件夹中

4. JobClient通过submitApplication()提交作业

5. JobTracker收到调用它的submitApplication()消息后，进行任务初始化

6. JobTracker读取HDFS上的要处理的文件，开始计算输入分片，每一个分片对应一个TaskTracker

7. TaskTracker通过心跳机制领取任务（任务的描述信息）

8. TaskTracker读取HDFS上的作业资源（JAR包、配置文件等），启动一个java child子进程，用来执行具体的任务（MapperTask或ReducerTask）

9. TaskTracker将Reduce结果写入到HDFS当中

1)设置 InputFormat 类, 将数据切分为 Key-Value(K1和V1) 对, 输入到第二步；

2)自定义 Map 逻辑, 将第一步的结果转换成另外的 Key-Value(K2和V2)对, 输出结果；

3)对输出的 Key-Value 对进行分区；

4)对不同分区的数据按照相同的 Key 排序；

5)(可选) 对分组过的数据初步规约, 降低数据的网络拷贝；

6)对数据进行分组, 相同 Key 的 Value 放入一个集合中；

7)对多个 Map 任务的结果进行排序以及合并, 编写 Reduce 函数实现自己的逻辑, 对输入的 Key-Value 进行处理, 转为新的 Key-Value(K3和V3)输出；

8)设置 OutputFormat 处理并保存 Reduce 输出的 Key-Value 数据；

通过执行定时调度或者脚本去执行HQL语句，并将结果保存

定义

模式

包括

作用

理解

内部表

外部表

理解

理解

row_number

rank

order by

sort by

cluster by

distrbute by

partition by

成因

分类

解决办法

进程之间交换数据必须通过内核，在内核中开辟一块缓存区，进程1把数据从用户空间拷贝到内核缓存区，进程2再从内核缓存区把数据读走

管道

信号量

消息队列

共享内存

套接字

在多条线程访问的时候，我们的程序还能按照我们预期的行为去执行

1. 进程是资源分配的单位，一个进程可以内可以包含多个线程，进程资源不共享

2. 进程拥有自己独立的堆和栈，既不共享堆，亦不共享栈，进程由操作系统调度。

3. 进程的创建调用fork或者vfork

调度

切换

具体过程

1. 线程是CPU调度的基本单元，多个线程共享进程内的资源（寄存器、堆栈、上下文）

2. 线程中执行时一般都要进行同步和互斥，因为他们共享同一进程的所有资源

3. 线程拥有自己独立的栈和共享的堆，共享堆，不共享栈，线程亦由操作系统调度

4. 线程的创建调用pthread_create

临界区（Critical Section）

互斥量 (Mutex)

事件（Event）

信号量（Semaphore）

1.  用户态的线程，用户态调度，不同协程的模型实现可能是单线程，也可能是多线程

2. 协程的切换是由程序自行控制，没有线程切换的开销

3. 不需要多线程的锁机制，因为只有一个线程，也不存在同时写变量冲突，在协程中控制共享资源不加锁，只需要判断状态就好了，所以执行效率比多线程高很多。

延伸

延伸

理解

特点

理解

特点

缺点

做法

select/poll

epoll

区别

相同

理解

理解

内核空间是操作系统所在的内存区域

用户空间是用户进程所在的内存区域