什么是动态规划？将原问题拆解成若干子问题，同时保存子问题的答案，使得每个子问题只求解一次，最终获得原问题的答案。 记忆化搜索 - 自顶向下的解决问题 动态规划 - 自底向上的解决问题 0-1背包问题F(n,C)考虑将 n 个物品放进容量为 c 的背包，使得价值最大。 状态转移方程如下： F(i,c) = F(i-1,c)或 F(i,c) = v(i) + F(i-1, c-w(i)) 即： F(i,c) = max(F(i-1,c), v(i)+F(i-1,c-w(i))) 面试实战 Climbing Stairs(#70) Integer Break(#343) House Robber(#198) Partition Equal Subset Sum(#416) Longest Increasing Subsequence(#300) dijkstra 单源最短路径算法也是动态规划 程序具体实现： 见代码。

运算符的种类有哪些？按照不同功能区分，可以分为： 算术运算符 字符串运算符 赋值运算符 位运算符 逻辑运算符 比较运算符 三元运算符 运算符优先级问题PHP运算符优先级遵循的规则是，高优先级的运算符先执行，低优先级的运算符后执行，同一优先级按照从左到右的顺序执行。 注意：在PHP运算符中，优先级从高到低的顺序是：算数运算符 > 关联运算符 > 逻辑运算符 ++、–的含义是什么？++$a或--$a：表示先将变量加1或减1，后做赋值操作 $a++或$a--：表示先做赋值操作，后将变量加1或减1

缓存异常缓存雪崩 理解： 雪崩，就是某东西蜂拥而至的意思，像雪崩一样。这里指Redis缓存大规模集体失效，在高并发情况下使得key大规模访问MySQL，导致MySQL崩掉。 解决方案： 通常的解决方案是将key的过期时间后面加上一个随机数，让key均匀的失效； 考虑用队列或者锁让程序执行在压力范围之内，当然这种方案可能会影响并发量； 热点数据可以考虑不失效。 缓存穿透 理解： 访问透过Redis直接访问MySQL，通常是一个不存在的key，在MySQL中查询为null，每次请求落在MySQL且高并发。 解决方案： 将查到的null设成该key的缓存对象； 根据明显错误的key在逻辑层就就进行验证； 同时，你也可以分析用户行为，是否为故意请求或者爬虫、攻击者。针对用户访问做限制； 其他等等，比如用布隆过滤器(超大型hashmap)先过滤。 缓存击穿 理解： 指一个key非常热点，大并发集中对这一个点进行访问，这个key在失效的瞬间，持续的大并发就穿破缓存，直接请求MySQL，就像蛮力击穿一样，导致MySQL崩掉。 解决方案： 可以使用互斥锁避免大量请求同时落 ...

1.概述为了保证并发访问的正确性，Redis提供了两种方法：加锁和原子操作。 1.1 加锁概念：在读取数据前，客户端需要先获取锁，否则无法进行操作；当一个客户端获取锁后，就会一直持有这把锁，直到客户端完成数据更新，才释放这把锁。 问题： 加锁操作多，降低系统的并发访问性能； Redis客户端加锁时，需要用到分布式锁，而分布式锁实现复杂，需要用额外的存储系统来提供加解锁操作。 并发访问中对什么进行控制？ 指对多个客户端访问操作同一份数据的过程进行控制，以保证任何一个客户端发送的操作在Redis实例上执行时具有互斥性。并发访问控制主要是数据修改操作。修改数据时，基本流程为两步： 客户端先把数据读取到本地，在本地进行修改； 客户端修改完数据后，再写回 Redis。 我们把这个流程叫做 “读取-修改-写回” 操作（Read-Modify-Write，简称为 RMW 操作）。访问同一份数据的RMW操作代码，叫做临界区代码。 例子： 加锁前： 出现这个现象的原因是，临界区代码中的客户端 读取数据、更新数据、再写回数据 涉及了三个操作，而这三个操作在执行时并不具有互斥性，多个客户端基于 ...

1. 跟索引相关的一些算法B+Tree 是借鉴了二分查找法、二叉查找树、平衡二叉树、B-Tree 的一些思想构建的。我们通过了解这些算法，来一层一层拨开 B+Tree 的面纱。 1.1 二分查找法二分查找法的查找过程是：将记录按顺序排列，查找时先以有序列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将查询范围缩小为左半部分；如果要找的元素值大于该中点元素，则将查询范围缩小为右半部分。以此类推，直到查到需要的值。 1.2 二叉查找树二叉查找树中，左子树所有节点的值都小于父节点的值，右子树所有节点的值都大于父节点键值，并且每个节点最多只有两棵子树。 1.3 平衡二叉(查找)树满足二叉树的定义，并且满足任何节点的两棵子树的高度差最大为 1。 1.4 B-Tree(平衡多路查找树)B-Tree 可以理解为一个节点可以拥有 2 个子节点的多路查找树。 B-Tree 中同一键值不会出现多次，要么在叶子节点，要么在内节点上。 比如用 1、2、3、5、6、7、9 这些数字构建一个 B-Tree 结构，其图形如下： 与平衡二叉树相比，B-Tree 利用多个分支节点，减少获取记录时经历的节点数 ...

递归调用的一个重要特征要返回回溯 回溯法是暴力解法的一个主要实现手段排列问题 Permutations(#46) 组合问题使用回溯法解决组合问题； 回溯法的剪枝； Combinations(#77) 在二维平面上使用回溯法 Word Search(#79) Number of Islands(#200) 回溯法是经典人工智能的基础 N-Queens(#51) 面试实战 Letter-Combinations-of-a-Phone-Number(#17) 程序具体实现： 见代码。

基本数据类型有哪些？数据类型及其描述： 备注 数据类型 类型 取值 标量类型 bool 布尔型 true,false int 整型 -2147483647~2147483648 string 字符串型 长度取决于其内存 float 浮点型 最大值为1.8e308 复合类型 object 对象 通过new实例化 array 数组 $arr = [1,2,3]; 特殊类型 resource 资源 资源是一种特殊的数据类型，无法直接获得变量，需要通过专门的函数来访问：1. 数据库访问通过MySQL函数库、MySQLi函数库或PDO函数库实现2. 文件访问通过FileSystem函数库实现3. 目录操作通过Directory函数库实现4. 图像操作通过GD库实现 NULL 空值 NULL 除了原始数据类型外，PHP还提供了三种伪类型： mixed（混合类型）：表示一个参数可以接收多种不同的数据类型 number（数值类型）：表示一个参数可以是int或float callback（可回调类型）：回调类型

1.快速学会分析SQL执行效率1.1 定位慢 SQL1.1.1 通过慢查询日志确定已经执行完的慢查询 何为慢查询日志？ 响应时间 >= 参数 long_query_time(单位秒，默认 10) 扫描记录数 >= 参数 min_examined_row_limit(默认值 0) 使用慢查询日志，一般分为四步 开启慢查询日志(set global slow_query_log = on;) 设置慢查询的阈值(set global long_query_time = 1;) 确定慢查询日志路径(show global variables like "datadir";) 确定慢查询日志的文件名(show global variables like "slow_query_log_file";) 1.1.2 show processlist查看正在执行的慢查询1.2 分析慢查询我们可以通过 explain、show profile 和 trace 等诊断工具来分析慢查询。 1.2.1 使用 explai ...

二叉树，天然的递归结构。递归算法中，需要注意：递归终止条件、递归过程。 复习二叉树相关的所有操作二分搜索树中的问题二分搜索树中的基本操作 面试实战 Invert Binary Tree(#226) Path Sum(#112) Binary Tree Paths(#257) Path Sum III(#437) Lowest Common Ancestor of a Binary Search Tree(#235) 程序具体实现： 见代码。

什么是常量？常量是一个简单值的标识符，在脚本执行期间该值不能改变（除了所谓的魔术常量，它们其实并不是常量）。常量默认区别大小写，常量有以下特点： 常量前面没有美元符号（$） 常量可以在任何地方定义和访问 常量一旦定义就不能被重新定义、取消定义或者修改它的值 常量的值只能是标量（int/float/string/bool） 常量分为自定义常量和预定义常量： 自定义常量使用define()函数来定义。 bool define(string $name, mixed $value [, bool case_insensitive]) 预定义常量（魔术常量） 名称 说明 LINE 常量所在的文件中的当前行号 FILE 常量所在的文件的完整路径和文件名 FUNCTION 常量所在的函数名称 CLASS 常量所在的类名称 METHOD 常量所在的方法名称 什么是变量？ 命名规则 变量由一个美元符号$开头，$后是一个标识符。标识符只能由字母、数字和下划线组成，并且不能以数字开头，变量对大小写敏感。 命名方式 驼峰命名法(小驼峰)：首个单词小写，其后 ...

栈栈和递归的紧密关系 二叉树中的算法 前序遍历：Binary Tree Preorder Traversal (#144) 中序遍历：Binary Tree Inorder Traversal (#94) 后序遍历：Binary Tree Postorder Traversal (#145) 递归算法 非递归算法 具体实现： 见代码 队列队列的基本应用 - 广度优先遍历 - 树：层次遍历 - 图：无权图的最短路径 BFS 和图的最短路径 优先队列优先队列的底层实现：堆 使用优先队列解决算法问题 面试实战 Valid Parentheses(#20) 思想：栈 Binary Tree Level Order Traversal(#102) 思想：队列 Perfect Squares(#279) Top K Frequent Elements(#347) 思想：优先队列 程序具体实现： 见代码。

final有什么用？final用于声明方法和类，分别表示方法不可以被覆盖、类不可被继承。 final方法：当一个方法被声明为final时，不允许任何子类重写这个方法，但子类可以使用这个方法。注意：final不能修饰类的成员变量 final类：当一个类被声明为final时，此类不能被继承，所有方法都不能被重写。注意：一个类不能既被声明为abstract，又被声明为final finally有什么用？PHP5.5新增了finally模块。finally作为异常处理的一部分，它只能用在try/catch语句中，并且附带着一个语句块，表示这段语句最终一定被执行，经常用在需要释放资源的情况下。try/catch/finally一般的使用方法为： assert有什么作用？static有什么用？static在PHP语言中主要用来修饰成员变量和成员方法 static修饰成员变量 PHP类提供了两种类型的变量，用static关键字修饰的静态变量和没有static关键字修饰的实例变量。 静态变量属于类，在内存中只有一个拷贝（所有实例都共享静态变量），只要静态变量所在的类被加载，这个静态变量就会被分配 ...

1.如何预防 SQL 注入？1.1 何为 SQL 注入？SQL 注入：是利用某些数据库的外部接口将用户数据插入到实际的数据库操作语句中，从而达到入侵数据库甚至操作系统的目的。 SQL 注入产生的主要原因：程序对用户输入的数据没有进行严格的过滤，导致非法数据库查询语句的执行。 SQL 注入具有很大的危害，可能会导致攻击者非法入侵系统，或者盗取数据，甚至清空数据等。 1.2 如何进行 SQL 注入攻击？1.3 如何预防 SQL 注入？控制输入变量的格式 增加了对输入信息的判断，过滤掉一些带特殊字符的输入。 转义特殊字符 有时，我们程序是允许输入信息带特殊字符的，这种情况就可以使用转义的方式，防止 SQL 注入。 2.主键是否需要设置为自增？2.1 主键和聚簇索引的关系 在 InnoDB 中，聚集索引不一定是主键，但是主键一定是聚集索引：原因是如果没有定义主键，聚集索引可能是第一个不允许为 null 的唯一索引，如果也没有这样的唯一索引，InnoDB 会选择内置 6 字节长的 ROW ID作为隐含的聚集索引。 InnoDB 的数据是按照主键顺序存放的，而聚集索引就是按照每张表的主键构造一颗 ...

MySQL表大小限制MySQL一般安装部署在Linux操作系统上（例如CentOS 7.4），默认都是InnoDB存储引擎，且开启了独立表空间选项（参数innodb_file_per_table=1），此时创建一个表 orders 就会自动生成一个数据文件orders.ibd，文件大小是受操作系统 Block 大小限制的，下面是 ext3 文件系统块大小和最大尺寸的对应关系。 操作系统块大小 最大文件尺寸 最大文件系统尺寸 1KB 16GB 2TB 2KB 256GB 8TB 4KB 2TB 16TB 8KB 16TB 32TB 查看操作系统页大小及块大小 这就说明 MySQL 单表的最大尺寸不能超过2TB，我们简单来算一下，假设一个表的平均行长度为32KB（InnoDB最大行长度限制65536字节，64KB），那么他最大能存储多少行数据？4 x 1024 x 1024 x 1024 / 32 = 134217728大约 1.4 亿不到。 分表方案分表的应用场景是单表数据量增长速度过快，影响了业务接口的响应时间，但是 MySQL 实例的 ...

面试实战 Reverse Linked List(#206) Remove Linked List Elements(#203) 思想：设置虚拟头结点 Swap Nodes in Paris(#24) 思想：设置虚拟头结点 Delete Node in a Linked List(#237) Remove Nth Node From End of List(#19) 思想：双指针技术 程序见代码。