• 1、同构字符串判断

// 获取每个字符串不同字母的索引位置判断是否相同
function isIsomorphic($s, $t) {
    $a = $this->getIndex($s);
    $b = $this->getIndex($t);
    return $a == $b;
}
function getIndex($s) {
    $res = [];
    for ($i = 0; $i < strlen($s); $i++)
    {
        $res[$s[$i]][] = $i;
    }
    return array_values($res);
}
// 输入: s = "egg", t = "add"
// 输出: true

• 2、给定一个整数数组，判断是否存在重复元素。

function containsDuplicate($nums) {
    $map = [];
    for ($i = 0; $i < count($nums); $i++)
    {
        if (isset($map[$nums[$i]]))
        {
            return true;
        }
        else
        {
            $map[$nums[$i]] = 0;
        }
    }
}

• 3、给定一个整数，编写一个函数来判断它是否是 2 的幂次方。

// 采用位运算 & 来解决该问题
// 2 的 n 次幂可以表示为：2^0, 2^1, 2^2, 2^3……
// 如果我们将其转换为二进制表示为：1, 10, 100, 1000, 10000……
// 因此我们可以看到，如果一个数是 2 的 n 次幂，那么该数的二进制中就只含有一个 1
// n - 1的二进制为：1, 011, 0111, 01111……
// 所以 n 和 n - 1 进行 & 运算，为 0 则表示该数是 2 的 n 次幂
function isPowerOfTwo($n) {
    return ($n & ($n -1)) == 0;
}

同理在计算 3 的幂次方、4 的幂次方等时，同样可以使用此类方法，先将 n 转换为对应进制的数，判断转完之后的数字是否只含有一个 1

• 4、给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的一个字母异位词。

// 统计每个字母出现次数进行比较
function isAnagram($s, $t) {
    $a = $this->getCount($s);
    $b = $this->getCount($t);
    if (count($a) != count($b)) return false;
    print_r($a);
    print_r($b);
    foreach ($a as $k => $v)
    {
        if (!isset($b[$k]) || $v != $b[$k])
        {
            return false;
        }
    }
    return true;
}
function getCount($s) {
    $map = [];
    for ($i = 0; $i < strlen($s); $i++)
    {
        if (isset($map[$s[$i]]))
        {
            $map[$s[$i]]++;
        }
        else
        {
            $map[$s[$i]] = 1;
        }
    }
    return $map;
}

//将两个字符串转数组排序后比较
function isAnagram($s, $t) {
    $a = asort(str_split($s));
    $b = asort(str_split($t));
    return $a == $b;
}

• 5、给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。

// 假设给定一个三位数 abc，可以表示为 100 * a + 10 * b + c
// 第一次计算后可以得到结果为 a+b+c，相比与原始值此次计算数值减小 99 * a + 9 * b = 9 * ( 11 * a + b)，减少了 9 的整数倍
// 因此可以通过 abc 对 9 取余得到结果
function addDigits($num) {
    return $num % 9 == 0 ? 9 : $num % 9 ;
}

• 6、编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。不要给另外的数组分配额外的空间，你必须修改输入数组**、使用 O(1) 的额外空间解决这一问题。

// 从中间开始调换两侧元素
function reverseString(&$s) {
    if (count($s) % 2 == 0)
    {
        $right = count($s) / 2;
        $left = $right - 1;
    }
    else
    {
        $right = count($s) / 2 - 1;
        $left = count($s) / 2 + 1;
    }
    for ($i = count($s) / 2; $i < count($s); $i++)
    {
        $tmp = $s[$right];
        $s[$right] = $s[$left];
        $s[$left] = $tmp;
        $left--;
        $right++;
    }
}

• 7、判断一个整数是否是完全平方数

// 二分查找
function isPerfectSquare($num) {
    $left = 1;
    $right = $num;
    while($left < $right)
    {
        $tmp = floor(($left + $right) / 2);
        if (pow($tmp, 2) == $num)
        {
            return true;
        }
        elseif (pow($tmp, 2) > $num)
        {
            $right = $tmp - 1;
        }
        else
        {
            $left = $tmp + 1;
        }
    }
    return false;
}

• 8、判断丑数，丑数是只包含质因数 2, 3, 5 的正整数。

function isUgly($num) {
    while($num > 1)
    {
        if ($num % 2 == 0) $num = $num / 2;
        elseif ($num % 3 == 0) $num = $num / 3;
        elseif ($num % 5 == 0) $num = $num / 5;
        else return false;
    }
    return true;
}

• 9、给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。

// 利用位运算符异或
// 也可以通过求和
function missingNumber($nums) {
    $res = count($nums);
    for ($i = 0; $i <= count($nums); $i++)
    {
        $res = $res ^ $nums[$i];
    }
    return $res;
}

• 10、给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

// 方法一：第一步删除数组中的 0 元素并记录个数，第二步在数组末尾补 0
function moveZeroes(&$nums) {
    $count = 0;
    for ($i = 0; $i < count($nums); $i++)
    {
        if ($nums[$i] == 0)
        {
            $count++;
            unset($nums[$i]);
        }
    }
    if ($count > 0)
    {
        for($i = 0; $i < $count; $i++)
        {
            array_push($nums, 0);
        }
    }
}
// 方法二：采用快排的思想，大于 0 的放在一个数组，小于 0 的放在一个数组，同样也可以采用冒泡的方式
function moveZeroes(&$nums) {
    $left = $right = [];
    for ($i = 0; $i < count($nums); $i++)
    {
        if ($nums[$i] > 0)
        {
            $right[] = $nums[$i];
        }
        else
        {
            $left[] = $nums[$i];
        }
    }
    $nums = array_merge($right, $left);
}

• 11、给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。

// map
function wordPattern($pattern, $str) {
    $map1 = $this->getMap($pattern, strlen($pattern));
    $arr = explode(" ", $str);
    $map2 = $this->getMap($arr, count($arr));
    return $map1 == $map2;
}
// 获取内容索引数组
function getMap($tmp, $len) {
    $map = [];
    for ($i = 0; $i < $len; $i++)
    {
        $map[$tmp[$i]][] = $i;
    }
    return array_values($map);
}
// 输入: pattern = "abba", str = "dog cat cat dog"
// 输出: true

• 12、你和你的朋友，两个人一起玩 Nim 游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。每一步都是最优解。

// 此题困扰我好久，想过好几个办法，好像都没办法实现，最后没办法看了官方的题解，原来是一道找规律的题，找到规律只需一行代码
// 如果石头个数为：1、2、3，那么你一定能赢
// 如果石头个数为：4，那么无论你先拿几个石头都会输，因此可以发现如果在对方拿石头回合，石头个数为 4 是，那么对方一定会输
// 如果石头个数为：5、6、7，根据上一个条件，此次你可以拿1、2、3个石头，为对方留下 4 个，那么他一定输
// 如果石头个数为：8，此轮当你拿过石头后，剩余数量为 5、6、7 中的一个，此时对方拿完给你剩余 4 个石头，对方一定会赢
// 因此得出结论，如果石头个数为 4 的倍数，那么你就没有赢得可能
// 规律找的好，代码写得少
function canWinNim($n) {
    return $n % 4 != 0;
}

• 13、给定两个字符串 s 和 t，它们只包含小写字母。字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。请找出在 t 中被添加的字母。

// 相同字符异或后为 0
function findTheDifference($s, $t) {
    $res = $s . $t;
    $tmp = $res[0];
    for ($i = 1; $i < (strlen($s) + strlen($t)); $i++)
    {
        $tmp = $tmp ^ $res[$i];
    }
    return $tmp;
}

• 14、给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。

// 想要构成回文字符串，包含的字符必须是偶数个，最多有一个计数个的字母
// 第一步：计算字符串中不同字母的个数并存入数组
// 第二步：获取数组中最大的奇数，同时将数组中的奇数删除
// 第四步：计算数据 value 的和最大奇数的和即为结果
function longestPalindrome($s) {
    $map = [];
    for ($i = 0; $i < strlen($s); $i++)
    {
        if (isset($map[$s[$i]]))
        {
            $map[$s[$i]]++;
        }
        else
        {
            $map[$s[$i]] = 1;
        }
    }
    $max = 0;
    foreach ($map as $k => $val)
    {
        if ($val % 2 != 0)
        {
            $max = $val;
            unset($map[$k]);
        }
    }
    return array_sum($map) + $max;
}

• 15、统计字符串中的单词个数，这里的单词指的是连续的不是空格的字符。

// 英文字母的 ASCII 范围在 65~122 之间
function countSegments($s) {
    $count = 0;
    for ($i = 0; $i < strlen($s); $i++)
    {
        if (ord($s[$i]) < 65 || ord($s[$i]) > 122)
        {
            $count++;
        }
    }
    return $count;
}

• 16、你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。给定一个数字 n，找出可形成完整阶梯行的总行数。

function arrangeCoins($n) {
    $sum = 1;
    $index = 1;
    while ($sum <= $n)
    {
        $index++;
        $sum += $index;
    }
    return $index - 1;
}

• 17、给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。找到所有在 [1, n] 范围之间没有出现在数组中的数字。

// 首次遍历数组将数组内值放到对应位置上，然后遍历新的数组，不存在的索引即为结果
function findDisappearedNumbers($nums) {
    $arr = [];
    for ($i = 0; $i < count($nums); $i++)
    {
        $arr[$nums[$i]] = $nums[$i];
    }
    $res = [];
    for ($i = 1; $i <= count($nums); $i++)
    {
        if (!isset($arr[$i]))
        {
            $res[] = $i;
        }
    }
    return $res;
}

• 18、给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

// 位运算，
function repeatedSubstringPattern($s) {
    if (strlen($s) % 2 != 0) return false;
    
    $res = $s[0];
    for ($i = 1; $i < strlen($s); $i++)
    {
        $res ^= $s[$i];
    }
    return $res == 0;
}

• 19、给定一个二进制数组， 计算其中最大连续1的个数。

function findMaxConsecutiveOnes($nums) {
    $count = $max = 0;
    for ($i = 0; $i < count($nums); $i++)
    {
        if ($nums[$i] == 1)
        {
            $count++;
        }
        else
        {
            
            $max = max($count, $max);
            $count = 0;
        }
    }
    return $max;
}

• 20、对于一个 正整数，如果它和除了它自身以外的所有正因子之和相等，我们称它为“完美数”。

// 计算所有因子求和
function checkPerfectNumber($num) {
   $arr = [1];
   for ($i = 2; $i < sqrt($num); $i++)
   {
       if ($num % $i == 0)
       {
           $arr[] = $i;
           $arr[] = $num / $i;
       }
   }
   return array_sum($arr) == $num;
}