数据结构与算法_数据算法:数组、栈、队列、链表、树、散列表、堆、图

数据结构与算法

• 数据结构指的是“一组数据的存储结构”，算法指的是“操作数据的一组方法”。
• 数据结构是为算法服务的，算法是要作用在特定的数据结构上的。

最常用的数据结构与算法:

数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表(可进行二分查找的有序链表,es中的联合索引使用跳表查询posting list)、图、Trie树(前缀树,字典树,es中的倒排索引中term index用的就是这种结构)

算法： 递归、排序、二分查找、搜索、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
1
2
3

一.数据结构

数据结构简介:

数据结构是相互间存在特定关系的数据的集合，分为逻辑结构和物理结构。
1

1.逻辑结构

    集合结构：数据元素之间没有特别的关系，仅同属相同集合。

    线性结构：数据元素间是一对一的关系

    树形结构：数据元素间存在一对多的层次关系
    
    图形结构：数据元素之间是多对多的关系
1
2
3
4
5
6
7

2.物理结构

物理结构是逻辑结构在计算机中存储形式，分为顺序存储结构和链式存储结构。

顺序存储结构将数据存储在地址连续的存储单元里。

链式存储结构将数据存储在任意的存储单元里，通过保存地址的方式找到相关联的数据元素
1
2
3
4
5

八大数据结构

数组,栈,队列,链表,树,图,堆,散列

①数组:
优点:按照索引查询元素速度快,按照索引遍历数组方便
缺点:大小固定后无法扩容,只能存储一种类型的数据,不利于增加删除元素
1
2
3

②栈:
特点:先进后出,递归场景
1
2

③队列:
特点:先进先出,多线程场景
1
2

④链表:
优点:任意的添加,删除元素
缺点:占用空间大,查询不便
1
2
3

⑤树:
平衡二叉树,B+树,红黑树
1
2

⑥图:
在存储数据上有着比较复杂和高效的算法，分别有邻接矩阵、邻接表、十字链表、邻接多重表、边集数组等存储结构
1
2

⑦堆:
完全二叉树,堆排序
1
2

⑧散列:
哈希查找
1
2

二.算法

1.复杂度分析

1.1大O复杂度表示法

公式:T(n)=O(f(n))

T(n)表示代码执行的时间; n表示数据规模的大小; f(n) 表示每行代码执行的次数总和。因为这是一个公式， 所以用f(n)来表示。公式中的O,表示代码的执行时间T(n)与f(n)表达式成正比。

大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度，简称时间复杂度。

1.2复杂度分析法则

• 单段代码看高频：比如循环。
• 多段代码取最大：比如一段代码中有单循环和多重循环，那么取多重循环的复杂度。
• 嵌套代码求乘积：比如递归、多重循环等
• 多个规模求加法：比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相加。

1.3时间复杂度分析

• 只关注循环执行次数最多的一段代码
• 加法法则：总复杂度等于量级最大的那段代码的复杂度
• 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

1.4几种常见时间复杂度实例分析

• 多项式阶：随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长。包括，
  O(1)（常数阶）、O(logn)（对数阶）、O(n)（线性阶）、O(nlogn)（线性对数阶）、O(n^2)（平方阶）
  、O(n^3)（立方阶）
• 非多项式阶：随着数据规模的增长，算法的执行时间和空间占用暴增，这类算法性能极差。包括，
  O(2^n)（指数阶）、O(n!)（阶乘阶）

1.5空间复杂度分析

表示算法的存储空间与数据规模之间的增长关系。

我们常见的空间复杂度就是O(1)、O(n)、 O(n2), 像O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。而且，空间复杂度分析比时间复杂度分析要简单很多。

2.基本算法思想

2.1.枚举算法思想

枚举算法思想的最大特点是，在面对任何问题时它会去尝试每一种解决方法。在进行归纳推理时，如果逐个考察了某类事件的所有可能情况，因而得出一般结论，那么这个结论是可靠的，这种归纳方法叫作枚举法。

2.2.递推算法思想

1.顺推法：从已知条件出发，逐步推算出要解决问题的方法。

2.逆推法：从已知结果出发，用迭代表达式逐步推算出问题开始的条件，即顺推法的逆过程。

<?php
//斐波那契数列,使用递推法求解
function fib_dt($n) {
    $arr_fib = [0, 1];
    for ($i = 2; $i <= $n; $i++) {
        $arr_fib[$i] = $arr_fib[$i - 1] + $arr_fib[$i - 2];
    }
    return $arr_fib;
}
1
2
3
4
5
6
7
8
9

2.3.递归算法思想

在计算机编程应用中，递归算法对解决大多数问题是十分有效的，它能够使算法的描述变得简洁而且易于理解。递归算法有如下3个特点。

① 递归过程一般通过函数或子过程来实现。

② 递归算法在函数或子过程的内部，直接或者间接地调用自己的算法。

③ 递归算法实际上是把问题转化为规模缩小了的同类问题的子问题，然后再递归调用函数或过程来表示问题的解。

在使用递归算法时，读者应该注意如下4点。

① 递归是在过程或函数中调用自身的过程。

② 在使用递归策略时，必须有一个明确的递归结束条件，这称为递归出口。

③ 递归算法通常显得很简洁，但是运行效率较低，所以一般不提倡用递归算法设计程序。

④ 在递归调用过程中，系统用栈来存储每一层的返回点和局部量。如果递归次数过多，则容易造成栈溢出，所以一般不提倡用递归算法设计程序。

<?php
//斐波那契数列问题,使用递归法求解
function fib_dg($n) {
    if ($n == 0) return 0;
    if ($n == 1) return 1;
    return fib_dg($n - 1) + fib_dg($n - 2);
}
1
2
3
4
5
6
7

2.4.分治算法思想

在编程过程中，经常遇到处理数据相当多、求解过程比较复杂、直接求解法会比较耗时的问题。在求解这类问题时，可以采用各个击破的方法。具体做法是：先把这个问题分解成几个较小的子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个大问题的解。如果这些子问题还是比较大，还可以继续再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。这就是分治算法的基本思想。

使用分治算法解题的一般步骤如下。

① 分解，将要解决的问题划分成若干个规模较小的同类问题。

② 求解，当子问题划分得足够小时，用较简单的方法解决。

③ 合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。

<?php
//最大子序和问题,使用分治法求解
function maxSubArray($arr) {
    return findMaxSumSubarray($arr, 0, count($arr) - 1);
}

function findMaxSumSubarray($nums, $low, $hight) {
    if ($low == $hight) {
        return $nums[$low];
    }
    $mid = floor(($low + $hight) / 2);
    $left_sum = findMaxSumSubarray($nums, $low, $mid);              	//当最大连续子数组在左数组中
    $right_sum = findMaxSumSubarray($nums, $mid + 1, $hight);         	//当最大连续子数组在右数组中
    $cross_sum = findMaxSumAcrossSubarray($nums, $low, $mid, $hight);  	//当最大连续子数组跨越中点
    return max($left_sum, $right_sum, $cross_sum);
}

function findMaxSumAcrossSubarray($nums, $low, $mid, $hight) {
    $left_max = PHP_INT_MIN;
    $right_max = PHP_INT_MIN;
    $sum = 0;
    for ($i = $mid; $i >= $low; $i--) {
        $sum += $nums[$i];
        $left_max = $left_max > $sum ? $left_max : $sum;
    }
    $sum = 0;
    for ($j = $mid + 1; $j <= $hight; $j++) {
        $sum += $nums[$j];
        $right_max = $right_max > $sum ? $right_max : $sum;
    }
    return $left_max + $right_max;
}

var_dump(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]));

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
35

2.5.贪心算法思想

贪心算法也被称为贪婪算法，它在求解问题时总想用在当前看来是最好方法来实现。这种算法思想不从整体最优上考虑问题，仅仅是在某种意义上的局部最优求解。

虽然贪心算法并不能得到所有问题的整体最优解，但是面对范围相当广泛的许多问题时，能产生整体最优解或者是整体最优解的近似解。由此可见，贪心算法只是追求某个范围内的最优，可以称之为“温柔的贪婪”。

贪心算法基础

贪心算法从问题的某一个初始解出发，逐步逼近给定的目标，以便尽快求出更好的解。当达到算法中的某一步不能再继续前进时，就停止算法，给出一个近似解。由贪心算法的特点和思路可看出，贪心算法存在以下3个问题。

① 不能保证最后的解是最优的。

② 不能用来求最大或最小解问题。

③ 只能求满足某些约束条件的可行解的范围。

贪心算法的基本思路如下。

① 建立数学模型来描述问题。

② 把求解的问题分成若干个子问题。

③ 对每一子问题求解，得到子问题的局部最优解。

④ 把子问题的局部最优解合并成原来解问题的一个解。

实现该算法的基本过程如下。

（1）从问题的某一初始解出发。

（2）while能向给定总目标前进一步。

（3）求出可行解的一个解元素。

（4）由所有解元素组合成问题的一个可行解。

<?php
//最大子序和问题,使用贪心算法求解
function maxSubArray_tx($nums) {
    $length = count($nums);
    $max = PHP_INT_MIN;
    $sum = 0;
    for ($i = 0; $i < $length; $i++) {
        $sum += $nums[$i];
        $max = max($max, $sum);
        if ($sum < 0) {
            $sum = 0;
        }
    }
    return $max;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.6.动态规划算法思想

步骤：

1.找出最优解的性质，刻画其结构特征；

2.递归地定义最优解；

3.以自底向上的方式计算出最优值；

4.根据计算最优值时得到的信息，构造一个最优解

只需求出最优值，步骤4可以省略；若需求出问题的一个最优解，则必须执行步骤4。

适用环境：

1.最优子结构。一个问题的最优解包含了其子问题的最优解。

2.重叠子问题。原问题的递归算法可以反复地解同样的子问题，而不是总是产生新的子问题

dp[i]表示nums中以nums[i]结尾的最大子序和
dp[i] = max(dp[i-1] + nums[i] ,nums[i]);
dp[i]要么是当前的数字,要么是与前面的最大子序和的和

max表示nums中最大子序和
max = max(dp[0-i]);
最大子序和为nums从dp[0]到dp[i]中的最大值

<?php
//最大子序和问题,使用动态规划法求解
function maxSubArray_dp($nums)
{
    $pre = $max = $nums[0];
    for ($i = 1; $i < count($nums); $i++) {
        $pre = max($nums[$i], $pre + $nums[$i]);
        $max = max($pre, $max);
    }
    return $max;
}
1
2
3
4
5
6
7
8
9
10
11

2.7.回溯算法思想

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法。

在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。

<?php
//全排列问题,回溯法求解
function permute($nums) {
    $res = [];
    backtracking($nums, [], $res);
    return $res;
}

function backtracking($nums, $arr, &$res) {
    if (count($arr) == count($nums)) {
        $res[] = $arr;
        return;
    }

    foreach ($nums as $value) {
        if (!in_array($value, $arr)) {
            $arr[] = $value;
            backtracking($nums, $arr, $res);
            array_pop($arr);
        }
    }
}

var_dump(permute([1,2,3]));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

2.8.分支界限算法思想

类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。

分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。
此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。

3.排序

3.1冒泡排序

基本思想：

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

<?php
//冒泡排序
function bubbleSort(&$nums) {
    $count = count($nums);
    for ($i = 0; $i < $count - 1; $i++) {
        for ($j = 0; $j < $count - $i - 1; $j++) {
            if ($nums[$j] > $nums[$j + 1]) {
                $temp = $nums[$j];
                $nums[$j] = $nums[$j + 1];
                $nums[$j + 1] = $temp;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.2 快速排序

基本思想：

1）选择一个基准元素,通常选择第一个元素或者最后一个元素,

2）通过一趟排序讲待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大。

3）此时基准元素在其排好序后的正确位置

4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

• 一趟排序
  
• 排序全过程
  

<?php
//快速排序
function quickSort(&$nums) {
    $count = count($nums);
    quickSortHelp($nums, 0, $count - 1);
}

function quickSortHelp(&$nums, $low, $hight) {
    if ($low < $hight) {
        $privot_loc = partition($nums, $low, $hight);
        quickSortHelp($nums, $low, $privot_loc - 1);
        quickSortHelp($nums, $privot_loc + 1, $hight);
    }
}

function partition(&$nums, $low, $hight) {
    $privot_key = $nums[$low];
    while ($low < $hight) {
        while ($nums[$hight] > $privot_key && $low < $hight) {
            $hight--;
        }
        swap($privot_key, $nums[$hight]);
        while ($nums[$low] < $privot_key && $low < $hight) {
            $low++;
        }
        swap($privot_key, $nums[$low]);
    }
    $nums[$low] = $privot_key;
    return $low;
}

function swap(&$a, &$b) {
    $temp = $a;
    $a = $b;
    $b = $temp;
}
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
35
36

3.3 插入排序

基本思想:

将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。

要点：设立哨兵，作为临时存储和判断数组边界之用。

直接插入排序示例：

<?php
//直接插入排序
function insertSort(&$nums) {
    for ($i = 1; $i < count($nums); $i++) {
        if ($nums[$i] < $nums[$i - 1]) {
            $flag = $nums[$i];                 //哨兵
            for ($j = $i - 1; $j >= 0 && $flag < $nums[$j]; $j--) {
                $nums[$j + 1] = $nums[$j];
            }
            $nums[$j + 1] = $flag;
        }
        print_arr($nums);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.4希尔排序

基本思想：

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

操作方法：

1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
2. 按增量序列个数k，对序列进行k 趟排序；
3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

<?php
//希尔排序
function shellSort(&$array) {
    $count = count($array);
    $dk = floor($count / 2);
    while ($dk >= 1) {
        shellSortHelp($array, $dk);
        print_arr($array);
        $dk = floor($dk / 2);
    }
}

function shellSortHelp(&$array, $dk) {
    for ($i = $dk; $i < count($array); $i++) {
        if ($array[$i] < $array[$i - $dk]) {
            $flag = $array[$i];             //哨兵
            for ($j = $i - $dk; $j >= 0 && $flag < $array[$j]; $j -= $dk) {
                $array[$j + $dk] = $array[$j];
            }
            $array[$j + $dk] = $flag;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

3.5归并排序

基本思想：

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归并排序示例：

<?php
//归并排序
function mergeSort(&$nums) {
    mergeSortHelp($nums, $nums, 0, count($nums) - 1);
}

function mergeSortHelp($arraySR, &$arrayTR1, $s, $t) //将SR归并到TR1 {
    if ($s == $t) {     //如果只有一个元素
        $arrayTR1[$s] = $arraySR[$s];
    } else {
        $m = floor(($s + $t) / 2);
        mergeSortHelp($arraySR, $arrayTR2, $s, $m);
        mergeSortHelp($arraySR, $arrayTR2, $m + 1, $t);
        merge($arrayTR2, $arrayTR1, $s, $m, $t);
    }
    print_arr($arrayTR1);
}

function merge($arraySR, &$arrayTR, $i, $m, $n)     //SR[i...m]和SR[m+1...n]归并到TR[i...n] {
    for ($j = $m + 1, $k = $i; $i <= $m && $j <= $n; $k++) {
        if ($arraySR[$i] < $arraySR[$j]) {
            $arrayTR[$k] = $arraySR[$i++];
        } else {
            $arrayTR[$k] = $arraySR[$j++];
        }
    }
    while ($i <= $m) {
        $arrayTR[$k++] = $arraySR[$i++];
    }
    while ($j <= $n) {
        $arrayTR[$k++] = $arraySR[$j++];
    }
}
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

3.6选择排序

基本思想：

在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。

简单选择排序的示例：

操作方法：

第一趟，从n 个记录中找出关键码最小的记录与第一个记录交换；

第二趟，从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换；

以此类推…

第i 趟，则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换，

直到整个序列按关键码有序。

<?php
//简单选择排序
function selectSort(&$array) {
    $count = count($array);
    for ($i = 0; $i < $count - 1; $i++) {
        $min = $array[$i];
        $key_min = $i;
        for ($j = $i + 1; $j < $count; $j++) {
            if ($array[$j] < $min) {
                $min = $array[$j];
                $key_min = $j;
            }
        }
        $temp = $array[$i];
        $array[$i] = $array[$key_min];
        $array[$key_min] = $temp;
        print_arr($array);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

3.7堆排序

堆排序是一种树形选择排序，是对直接选择排序的有效改进。

基本思想：

堆的定义如下：具有n个元素的序列（k1,k2,…,kn),当且仅当满足

时称之为堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最小项（小顶堆）。
若以一维数组存储一个堆，则堆对应一棵完全二叉树，且所有非叶结点的值均不大于(或不小于)其子女的值，根结点（堆顶元素）的值是最小(或最大)的。如：

• 大顶堆序列：（96, 83,27,38,11,09)

• 小顶堆序列：（12，36，24，85，47，30，53，91）
  
  初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树（一维数组存储二叉树），调整它们的存储序，使之成为一个堆，将堆顶元素输出，得到n 个元素中最小(或最大)的元素，这时堆的根节点的数最小（或者最大）。然后对前面(n-1)个元素重新调整使之成为堆，输出堆顶元素，得到n 个元素中次小(或次大)的元素。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。称这个过程为堆排序。

因此，实现堆排序需解决两个问题：

1. 如何将n 个待排序的数建成堆；
2. 输出堆顶元素后，怎样调整剩余n-1 个元素，使其成为一个新堆。

<?php
//堆排序  时间复杂度：O(n*log n)
function heapSort(&$array) {
    $count = count($array);
    //对顺序表进行堆排序
    for ($i = floor($count / 2 - 1); $i >= 0; $i--) {
        HeapAdjust($array, $i, $count);
    }
    for ($i = $count - 1; $i > 0; $i--) {
        $temp = $array[$i];
        $array[$i] = $array[0];
        $array[0] = $temp;
        HeapAdjust($array, 0, $i);
        print_arr($array);
    }
}

function HeapAdjust(&$array, $s, $length) {
    $temp = $array[$s];
    for ($i = 2 * $s + 1; $i < $length; $i *= 2 + 1) {          //进入交换后的子树，没有交换则跳出循环
        if ($i + 1 < $length && $array[$i] < $array[$i + 1])    //左右子树比较，指向值大的子树
            $i++;
        if ($array[$i] > $temp) {
            $array[$s] = $array[$i];
            $s = $i;
        } else {
            break;
        }
    }
    $array[$s] = $temp;
}
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

3.8基数排序

它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

<?php
//基数排序
function baseSort(&$array)
{
    $len = count($array);
    $max = max($array);
    $arr_tong = [];
    $cnt = 1;
    while (floor($max / 10) != 0) {
        $max = floor($max / 10);
        $cnt++;
    }
    for ($i = 0; $i < $cnt; $i++) {             //从低位到高位一次排序
        for ($j = 0; $j < $len; $j++) {                     //进桶操作
            $tong = ($array[$j] / pow(10, $i)) % 10;
            $arr_tong[$tong][] = $array[$j];
        }
        for ($array_index = 0, $j = 0; $j < 10; $j++) {     //出桶操作
            if (!empty($arr_tong[$j])) {
                foreach ($arr_tong[$j] as $v) {
                    $array[$array_index++] = $v;
                }
            }
        }
        unset($arr_tong);
    }
}
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

4.技巧

4.1双指针

<?php
//快慢指针解决环形链表问题
function detectCycle($head) {
    $fast = $slow = $head;
    while (true) {
        if ($fast === null || $fast->next === null) {
            return null;
        }
        $fast = $fast->next->next;
        $slow = $slow->next;
        if ($fast === $slow) break;
    }

    $fast = $head;
    while ($fast !== $slow) {
        $fast = $fast->next;
        $slow = $slow->next;
    }
    return $fast;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

根据题意，任意时刻，fast 指针走过的距离都为 slow 指针的 2 倍。因此，我们有:
a+(n+1)b+nc=2(a+b) => a=c+(n−1)(b+c)

有了a=c+(n−1)(b+c) 的等量关系，我们会发现：从相遇点到入环点的距离加上 n-1 圈的环长，恰好等于从链表头部到入环点的距离。

因此，当发现slow 与fast 相遇时，我们再额外使用一个指针 ptr。起始，它指向链表头部；随后，它和 slow 每次向后移动一个位置。最终，它们会在入环点相遇。

4.2位运算

<?php
//位运算求解只出现一次的数字
function singleNumber($nums) {
    $ret = 0;
    foreach ($nums as $item) {
        $ret ^= $item;
    }

    return $ret;
}
var_dump(singleNumber([2, 2, 4]));
1
2
3
4
5
6
7
8
9
10
11