数据结构算法总结

线性表

  • 数组
  • 链表
    • 单链表
    • 双向链表
    • 循环链表
    • 双向循环链表
    • 静态链表
    • 顺序栈
    • 链式栈
  • 队列
    • 普通队列
    • 双端队列
    • 阻塞队列
    • 并发队列
    • 阻塞并发队列

散列表

  • 散列函数
  • 冲突解决
    • 链表法
    • 开放寻址
    • 其他
  • 动态扩容
  • 位图

  • 二叉树
    • 平衡二叉树
    • 二叉查找树
    • 平衡二叉查找树
      • AVL树
      • 红黑树
    • 完全二叉树
    • 满二叉树
  • 多路查找树
    • B树
    • B+树
    • 2-3树
    • 2-3-4树
    • 小顶堆
    • 大顶堆
    • 优先级队列
    • 斐波那契堆
    • 二项堆
  • 其他
    • 树状数组
    • 线段树

  • 图的存储
    • 邻接矩阵
    • 邻接表
  • 拓扑排序
  • 最短路径
  • 关键路径
  • 最小生成树
  • 二分图
  • 最大流

复杂度分析

  • 空间复杂度
  • 时间复杂度
    • 最好
    • 最坏
    • 平均
    • 均摊

基本算法思想

  • 贪心算法
  • 分治算法
  • 动态规划
  • 回溯算法
  • 枚举算法

排序

  • O(n^2)
    • 冒泡排序
    • 插入排序
    • 选择排序
    • 希尔排序
  • O(nlogn)
    • 归并排序
    • 快速排序
    • 堆排序
  • O(n)
    • 计数排序
    • 基数排序
    • 桶排序

搜索

  • 深度优先搜索
  • 广度优先搜索
  • A*启发式搜索

查找

  • 线性表查找
  • 树结构查找
  • 散列表查找

字符串匹配

  • 朴素
  • KMP
  • Robin-Karp
  • Boyer-Moore
  • AC自动机
  • Trie
  • 后缀数组

其他

  • 数论
  • 计算几何
  • 概率分析
  • 并查集
  • 拓扑网络
  • 矩阵运算
  • 线性规划

PHP版本迭代更新特性(持续更新)

PHP 7 新特性

  • 类型声明
  • 命名空间批量声明
  • 匿名类
  • 老式构造方法废弃
  • Throwable接口
  • 新的操作符
  • 常量数组
  • switch不再支持多个默认值
  • session_start函数调整
  • unserialize引入过滤器

类型生声明

函数入参和出参支持声明类型:

declare(strict_types=1); // 严格限制入参类型

function test(int $num) : int 
{
    return $num * $num;
}

print_r(test('2'));

命名空间批量声明

同一命名空间下的类、方法、常量可以合并引入(非混合模式、混合模式、复合模式),以复合模式为例:

use Publishers\{
    Paper\Book,
    Electronic\Ebook,
    Media\Video,
    Media\Audio
}

匿名类

与正常类相似,可以继承父类、实现接口,区别在于没有类名。主要用于快速实现小块的功能单元:

class Math
{
    public $first_number = 10;
    public $second_number = 20;

    public function add() : float
    {
        return $this->first_number + $this->second_number;
    }

    public function multiply_num()
    {
        return new class() extends Math
        {
            public function multiply(float $third_number) : float
            {
                return $this->add() * $third_number;
            }
        };
    }
}

$math = new Math();
print_r($math->multiply_num()->multiply(2));  

老式构造方法废弃

使用与类名同名的函数作为构造函数这种方式不推荐使用,将会在未来版本中移除。

Throwable接口

异常(Exception)和绝大部分错误(Fatal)都能通过 try/catch 的方式予以捕获并处理(继承自 Throwable 接口):

<?php
try {
    $a = 20;
    $division = $a / 0;
} catch (DivisionByZeroError $e) {
    echo $e->getMessage();
}

新操作符

  1. <=> 用于对参数进行比较: 两边相等返回0,左边小于右边返回-1,左边大于右边返回1
  2. ?? 三元运算符的优化,以前需要这么写: $title = isset($_POST[『title』]) ? $_POST[『title』] : NULL; 现在可以这么写: $title = $_POST[『title』] ?? NULL;
  3. 统一变量语法 为了解决 $$first[『name』] 这种写法容易造成语法混淆,引入统一变量语法,这种写法需要改为: ${$first[『name』]} 即将优先执行的部分用花括号括起来,否则会报错,并且得到不确定的输出。

常量数组

define('STORES', ['en', 'fr', 'ar']);

switch不再支持多个默认值

switch(true)
{
    default:
        echo '1';
        break;
    default:
        echo '2';    
}

以上代码在 PHP 7 中会报错: Fatal error: Switch statements may only contain one default …

session_start函数调整

支持传递配置参数以覆盖 php.ini 中的默认配置。

unserialize引入过滤器

为了安全起见,在该函数中引入过滤器,以限定可以反序列化的对象。

PHP 7.4 转自 PHP7.4新特性预览

  • 短闭包 RFC
  • 属性类型定义 RFC
  • Null Coalescing Assignment Operator RFC
  • 自定义对象序列化 RFC
  • 弃用左关联三元运算符 RFC
  • 预加载 RFC
  • 外部函数接口 RFC
  • Reflection for references RFC
  • mb_str_split RFC
  • ext-hash 始终开启RFC

短闭包

引用更简单的闭包写法,在原来的基础加上fn关键字,采用了类型javascript =>写法。

<?php
// 7.3之前
array_map(function (User $user) { 
    return $user->id; 
}, $users)
// 现在
array_map(fn(User $user) => $user->id, $users)

关于短封闭的一些注意事项:

  • 可以直接访问父作用域,不需要使用use关键字
  • $this像普通的闭包一样可用
  • 短闭包只能包含一行,也就是return语句

属性类型定义

可以指定类属性的类型定义,更加的明确类型。

<?php

class A
{
    public string $name;

    public Foo $foo;

    protected ClassName $classType;

    private ?ClassName $nullableClassType;

     // Types are also legal on static properties
    public static iterable $staticProp;


}

关于属性类型定义更详细的说明请参考此处

Null Coalescing Assignment Operator

更短的??操作符写法。

<?php
// 7.4之前
$data['date'] = $data['date'] ?? new DateTime();

// 现在
$data['date'] ??= new DateTime();

弃用左关联三元运算符

与大多数其他语言不同,PHP中的三元运算符是左关联的而不是右关联的。对于在不同语言之间切换的程序员来说,左关联行为通常没有用,并且令人困惑。此RFC建议弃用并删除三元运算符的左关联性,并且需要显式使用括号。

<?php

echo 1 ? 2 : 3 ? 4 : 5;   // deprecated 7.4, 7.3 之前这是ok的。
echo (1 ? 2 : 3) ? 4 : 5; // ok 

自定义对象序列化

添加两个新的序列化魔术方法__serialize,__unserialize主要来解决__wakeupSerializable带来一些问题。可以通过https://wiki.php.net/rfc/custom_object_serialization来查看对比。

预加载

预加载是PHP这期核心的变更,可以带来一些重大的性能改进。

简而言之,如果您使用的所有PHP Web框架,则必须在每次请求时加载和重新编译其文件。预加载允许服务器在启动时在内存中加载PHP文件,并使它们永久可用于所有后续请求。

性能提升当然需要付出代价,如果预加载文件的来源发生变化,则必须重新启动服务器。

外部函数接口

外部函数接口,简称FFI,此API允许在纯PHP中加载共享库(.DLL或.so),调用C函数和访问C数据结构,而无需深入了解Zend扩展API,也无需学习第三种“中间”语言。对于PHP,FFI开辟了一种在纯PHP中编写PHP扩展和绑定到C库的方法。。 这是一个复杂的主题。您仍然需要C知识才能正确使用此功能。大家可以阅读该项目来了解https://github.com/dstogov/php-ffi

Reflection for references

SymfonyvarCloner转储程序,这样的库很大程度上依赖于反射API来可靠地转储变量。以前,没有对引用的适当反射支持,导致这些库依赖hack来检测引用。 PHP 7.4添加了ReflectionReference类来解决这个问题。

mb_str_split

添加了多字节的字符串分割函数和str_split一样。

<?php
print_r(mb_str_split("你好中国", 2));

Array
(
    [0] => 你好
    [1] => 中国
)

ext-hash 默认开启

哈希扩展(ext / hash)始终可用,类似于datesplpcre扩展。