第二十章：实战十：算法面试题实战解析

在PHP程序员的求职之路上，算法面试是一道不可或缺且极具挑战性的门槛。它不仅考验着求职者的编程基础，还对其逻辑思维、问题解决能力以及时间复杂度控制提出了高要求。本章将精选几道经典的算法面试题，结合PHP语言特性，进行深入的实战解析，帮助读者理解算法背后的思想，提升应对算法面试的能力。

20.1 题目一：反转链表

问题描述：给定一个单链表的头节点head，要求反转链表并返回反转后的头节点。链表节点的定义如下：

class ListNode {
    public $val = 0;
    public $next = null;
    function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}

解题思路：反转链表的关键在于三个指针的运用——当前节点current、前一个节点prev以及后一个节点nextTemp。遍历链表，逐个调整节点的指向即可。

PHP代码实现：

function reverseList($head) {
    $prev = null;
    $current = $head;
    while ($current !== null) {
        $nextTemp = $current->next; // 保存后一个节点
        $current->next = $prev; // 反转当前节点指向
        $prev = $current; // 前一个节点向前移动
        $current = $nextTemp; // 当前节点向前移动
    }
    return $prev; // 当遍历结束时，prev即为新的头节点
}

复杂度分析：时间复杂度为O(n)，其中n是链表的长度，因为需要遍历整个链表。空间复杂度为O(1)，仅使用了几个指针变量。

20.2 题目二：两数之和

问题描述：给定一个整数数组nums和一个目标值target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

解题思路：使用哈希表（在PHP中对应为关联数组）来存储遍历过的数字及其对应的索引。遍历数组时，检查target - 当前值是否已存在于哈希表中，若存在则找到了一对解；否则，将当前值及其索引加入哈希表。

PHP代码实现：

function twoSum($nums, $target) {
    $hashMap = [];
    $length = count($nums);
    for ($i = 0; $i < $length; $i++) {
        $complement = $target - $nums[$i];
        if (isset($hashMap[$complement])) {
            return [$hashMap[$complement], $i];
        }
        $hashMap[$nums[$i]] = $i;
    }
    return []; // 如果没有找到符合条件的两个数，则返回空数组
}

复杂度分析：时间复杂度为O(n)，其中n是数组的长度，因为每个元素只被遍历一次。空间复杂度也为O(n)，在最坏情况下（没有找到解时），哈希表需要存储所有元素。

20.3 题目三：最长回文子串

问题描述：给定一个字符串s，找到s中最长的回文子串。你可以假设s的最大长度为1000。

解题思路：有多种方法可以解决此问题，如中心扩展法、动态规划、Manacher算法等。这里采用中心扩展法，因为其实现简单且易于理解。该方法的基本思想是以每个字符或每对相邻字符为中心，向两边扩展，检查回文长度。

PHP代码实现（中心扩展法）：

function longestPalindrome($s) {
    $start = 0;
    $maxLength = 0;
    $length = strlen($s);
    for ($i = 0; $i < $length; $i++) {
        $len1 = expandAroundCenter($s, $i, $i); // 奇数长度回文
        $len2 = expandAroundCenter($s, $i, $i + 1); // 偶数长度回文
        $len = max($len1, $len2);
        if ($len > $maxLength) {
            $start = $i - floor(($len - 1) / 2);
            $maxLength = $len;
        }
    }
    return substr($s, $start, $maxLength);
}
function expandAroundCenter($s, $left, $right) {
    $L = $left;
    $R = $right;
    while ($L >= 0 && $R < strlen($s) && $s[$L] === $s[$R]) {
        $L--;
        $R++;
    }
    return $R - $L - 1; // 返回回文长度，注意要减去多算的两次边界
}

复杂度分析：时间复杂度为O(n^2)，因为对于每个中心，我们可能需要检查O(n)个字符来确定回文长度。空间复杂度为O(1)，因为我们只使用了常数个变量。

20.4 总结

本章通过三道经典的算法面试题，深入探讨了链表操作、哈希表应用以及字符串处理的算法思想。这些题目不仅考察了基础的编程技能，更强调了逻辑思维和算法设计的重要性。在实际面试中，面对复杂问题时，保持冷静，将大问题分解为小问题，并灵活运用所学算法和数据结构知识，是解决问题的关键。希望本章的解析能帮助读者在算法面试中更加游刃有余，顺利斩获心仪的offer。