数据结构是算法的基石，如果没有扎实的数据结构基础，要想把算法学好甚至融会贯通是非常困难的，而优秀的算法又往往取决于你采用哪种数据结构
数组、字符串(Array & String)
字符串转化
数组和字符串是最基本的数据结构，在很多编程语言中都有着非常相似的性质，围绕着这两者的算法面试题是最多的
很多时候，在分析字符串相关面试题的过程中，我们往往要针对字符串中的每一个字符进行分析和处理，甚至有时候我们得先把给定的字符串转换成字符数组后再进行分析和处理
举例：翻转字符串 "algorithm"
注意：字符串中的字符是不允许被修改的，我们只能将原字符串转换成字符数组针对每一个字符进行分析和处理
解法：
<?php
/**
* 在这里我们不使用 php built in function 处理，在 php 中有一个built in function strRev 一行代码即可实现翻转字符串，
* 但是在面试的时候这肯定是面试官不愿意看到结果，面试在一定程度上考察的是我们处理问题的思维逻辑。如果要是在实际开发中我们可以使用 php built in function
*
* 另外需要注意的是，要想实现字符串翻转我们在这里需要将给定的字符串转换成字符数组，然后再分析处理。在 php 中的字符串可以直接作为数组处理，比如代码：
* echo $str[4]; 输出结果为 r，则代表的是该字符串的第四个字符为 r
*/
// 待测试字符串
$str = 'algorithm';
function str_rev($str) {
// 结合 for 循环，将第二个条件置为 true，模拟死循环，计算字符串的长度
for($i = 0;true;$i++) {
if(!isset($str[$i])) {
break;
}
}
// 通过上面 for 循环计算出字符串长度，下面我们根据使用下标获取字符数组元素，将字符串从末尾开始循环进行字符串拼接
$newStr = '';
for($j = $i - 1;$j >= 0;$j--) {
$newStr .= $str[$j];
}
return $newStr;
}
// 输出
var_dump(str_rev($str));
数组的优缺点
掌握一种数据结构，就必须要了解这种数据结构的优缺点，这样我们才能根据其特性选择适合我们算法的数据结构，数组的优点：
- 数组支持随机访问，可根据数组下标在时间复杂度为 O(1) 的情况下访问数组元素
而数组的缺点在于：
- 数组在分配内存空间前需要预估下要存储数据元素的大小，如果分配内存空间不够需要手动扩容，这在一定程度上会耗费资源，使得性能受到一定影响
- 数组的插入和删除操作，均需要移动元素，这使得其插入和删除操作的时间复杂度为 O(n)
所以我们在是否选择数组作为我们算法的数据结构时，需要考虑到数组的优缺点，比如算法中查询、插入和删除哪种操作比较多，根据数据确定知道数组明显不擅长元素插入和删除
例题分析
给定两个字符串 s 和 t，编写一个函数来判断 t 是否是 s 的字母异位词
示例 1：
输入：s = "anagram",t = "nagaram"
输出：true
示例 2：
输入：s = "rat",t = "car"
输出：false
说明：你可以假设字符串只包含小写字母
字母异位词，也就是两个字符串中相同字符的数量要对应相等。例如，s 等于 "anagram"，t 等于 "nagaram", s 和 t 就互为字母异位词。因为他们都包含三个字符 a,一个字符 g,一个字符 m，一个字符 n ，以及一个字符 r。而当 s 为 "rat" ，t 为 "cat" 的时候，s 和 t 不互为字母异位词
具体代码实现如下：
class Solution {
/**
* @param String $s
* @param String $t
* @return Boolean
*/
function isAnagram($s, $t) {
// 首先互为字母异位词的两个字符串长度一定相等
// 使用 for 循环分别计算两个字符串的长度
// 计算字符串 s 的长度
for($i = 0;true;$i ++) {
if(!isset($s[$i])) {
break;
}
}
// 计算字符串 t 的长度
for($j = 0;true;$j ++) {
if(!isset($t[$j])) {
break;
}
}
// 判断两个字符串长度是否相等，如果不相等，这两个字符串一定不互为字母异位词
if($i != $j) {
return false;
}
// 判断当两个字符串同时输入的都是空字符串时，则两个字符串也互为字母异位词
if($i == 0 && $j == 0) {
return true;
}
// 定义一个字符数组，使用 26 个小写字母作为数组的 key,将 每个 key 对应的 value 统一置为 0
$letterArr = array('a'=>0,'b'=>0,'c'=>0,'d'=>0,'e'=>0,'f'=>0,'g'=>0,'h'=>0,'i'=>0,'j'=>0,'k'=>0,'l'=>0,'m'=>0,'n'=>0,'o'=>0,'p'=>0,'q'=>0,'r'=>0,'s'=>0,'t'=>0,'u'=>0,'v'=>0,'w'=>0,'x'=>0,'y'=>0,'z'=>0);
// 计算字符串 s 中的字符 在字符数组 letterArr 中出现的个数
for($m = 0;$m < $i;$m++){
if(isset($letterArr[$s[$m]])) {
$letterArr[$s[$m]]++;
}else{
$letterArr[$s[$m]] = 1;
}
}
// 计算字符串 t 中的字符 在字符数组中 letterArr 出现的个数，并将其减 1
for($n = 0;$n < $j;$n++) {
if(!isset($letterArr[$t[$n]]) || $letterArr[$t[$n]] == 0) {
return false;
}
if(isset($letterArr[$t[$n]])) {
$letterArr[$t[$n]]--;
}
}
return true;
}
}
$solution = new Solution();
$s = 'aacc';
$t = 'ccac';
$solution = $solution->isAnagram($s,$t);
echo $solution;
上面代码是我在 leetcode 提交的具体实现逻辑，在上述代码中我未使用 php 内置函数，在计算字符串长度时，使用 for 循环模拟死循环，解题思路：
一个重要前提是假设输入的两个字符串中的字符都是小写字母，小写字母我们知道一共有 26 个，因此：
- 创建一个包含 26 个小写字母的字符数组，并将每个小写字母作为数组的 key,每个 key 对应的 value 初始化为 0，将出现在字符串 s 中的字符加 1，而将出现在字符串 t 中的字符减 1，最后判断每个小写字母对应的值 value 是否都为 0，如果都为 0，则说明输入的两个字符串互为字母异位词
例题分析
翻转字符串：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1：
输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]
示例 2：
输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
具体代码实现如下：
class Solution {
/**
* @param String[] $s
* @return NULL
*/
function reverseString(&$s) {
for($i = 0;true;$i++) {
if(!isset($s[$i])) {
break;
}
}
for($n = 0;$n < $i;$n++) {
$temp = $s[$n];
$s[$n] = $s[$i - 1];
$s[$i - 1] = $temp;
$i--;
}
return $s;
}
}
$str = ["h","e","l","l","o"];
$solution = new Solution();
$result = $solution->reverseString($str);
var_dump($result);
解题思路
使用两个指针，一个指针指向字符数组的第一个字符，一个指向字符数组的最后一个字符，然后相互交换。交换之后，两个指针向中央一步步地靠拢，直到两个指针相遇。这是一种比较快速和直观的方法
例题分析
替换空格：请实现一个函数，把字符串 s 中的空格替换成 "%20"
示例 1：
输入：s = "We are happy."
输出："We%20are%20happy."
这道题目是剑指offer上面的一道原题，在力扣上这道题目的难度等级是简单，我们来分析下这道题目，如果面试中拿到面试官给我们的题目，我们首先不要着急答题，先和面试官沟通清楚题目的要求，有的面试官可能不会说，让我们自己主动思考，比如上面这道题目。
看到上面这道题目我们应该想到有两种情况存在，一个是在原有字符串的基础上直接替换;一个是创建新字符串，在新字符串上替换。如果是在原始字符串上替换的话，那么需要保证字符串后面有足够多的空闲内存，因为字符串中的空格被替换后字符串的长度变长了，之前处于空格后面的字符需要向后移动，如果字符串后面没有足够多的内存空间，那么有可能会出现内存覆盖的问题，这些需要向面试官确认，我们来看下这两情况分别对应的具体实现：
创建新字符串，在新字符串上替换
class Solution {
/**
* @param String $s
* @return String
*/
function replaceSpace($s) {
// 计算字符串的长度
for ($sLength = 0;true;$sLength++) {
if(!isset($s[$sLength])) {
break;
}
}
$S = "";
for ($i = 0;$i < $sLength;$i++) {
if($s[$i] == " ") {
$S .= '%20';
}else{
$S .= $s[$i];
}
}
return $S;
}
}
$str = 'We are happy.';
$solution = new Solution();
$result = $solution->replaceSpace($str);
var_dump($result);
