• 1网持、給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target宜岛，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那 兩個(gè) 整數(shù)，并返回他們的數(shù)組下標(biāo)功舀。

// 交換數(shù)組的鍵和值萍倡，判斷數(shù)組中是否含有 target - k 的鍵值，即可得到答案
function twoSum($nums, $target) {
    $tmp= array_flip($nums);
    foreach ($nums as $k => $v)
    {
        if (array_key_exists($target - $v, $tmp))
        {
            return [$k, $tmp[$target - $v]];
        }
    }
}

• 2辟汰、有符號(hào)整數(shù)反轉(zhuǎn)

function reverse($x) {
    if (!in_num($x)) return 'error type';
    $remainder = 0; //余數(shù)
    $res = 0; 
    while ($x > 9 || $x < -9)
    {
        $remainder = $x % 10;
        $x = ($x - $remainder ) / 10;
        $res = $res * 10 + $remainder;
    }
    return $res * 10 + $x;
}

• 3列敲、有符號(hào)整數(shù)判斷回文

// 時(shí)間復(fù)雜度：O(lg(n))  空間復(fù)雜度：O(1)
// 類似于第二題
function isPalindrome($x) {
    // 負(fù)數(shù)不會(huì)是回文
    if (is_int($x) && $x < 0) return false;
    
    $tmp = 0;
    while($x > $tmp)
    {
        $tmp = $tmp * 10 + ($x % 10);
        $x = ($x - $tmp) / 10;
    }
    // 如果 x 為類似 121 時(shí)阱佛，最后得到的 tmp 為 12，x為 1
    if ($tmp == $x || $x = $tmp / 10) return true;
    
    return false;
}

• 4戴而、羅馬數(shù)字轉(zhuǎn)整數(shù)

// 從字符串末尾開(kāi)始凑术，獲取兩個(gè)字符，如果前面一個(gè)字符大直接相加所意，否則相減
function romanToInt($s) {
    $map = [
        'I' => 1,
        'V' => 5,
        'X' => 10,
        'L' => 50,
        'C' => 100,
        'D' => 500,
        'M' => 1000
    ];
    $sum = 0;
    for ($i = strlen($s) - 1; $i >= 0; $i -= 2)
    {
        if ($i > 0)
        {
            if ($map[$s[$i]] > $map[$s[$i - 1]])
            {
                $sum += ($map[$s[$i]] - $map[$s[$i - 1]]);
            }
            else
            {
                $sum += ($map[$s[$i]] + $map[$s[$i - 1]]);
            }
        }
        else
        {
            $sum += $map[$s[$i]];
        }
    }
    return $sum;
}

• 5淮逊、獲取字符串公共的前綴

// 先將第一個(gè)元素當(dāng)作公共前綴，與第二個(gè)比較扶踊，去掉不同的的部分泄鹏，以此類推
function longestCommonPrefix($strs) {
    $common = $strs[0];
    for ($i = 1; $i < count($strs); $i++)
    {
        $tmp = '';
        for ($j = 0; $j < strlen($common); $j++)
        {
            if ($common[$j] == $strs[$i][$j])
            {
                $tmp .= $common[$j];
            }
        }
        $common = $tmp;
    }
    return $common;
}
// ["flower","flow","flight"]
// "fl"

• 6、給定一個(gè)只包括 '('秧耗，')'备籽，'{'，'}'分井，'['车猬，']' 的字符串，判斷字符串是否有效

// 采用棧的形式尺锚，判斷 s 的當(dāng)前元素能否與棧的最后一個(gè)元素匹配诈唬，不能則入棧，能則出棧
function isValid($s) {
    if (empty($s) || strlen($s) % 2 == 1) return false;
    
    $map = [
        "(" => ")",
        "[" => "]",
        '{' => "}"
    ];
    $tmp = [];
    for ($i = 0; $i < strlen($s); $i++)
    {
        if ($map[$tmp[count($tmp) - 1]] != $s[$i])
        {
            array_push($tmp, $s[$i]);
        }
        else
        {
            array_pop($tmp);
        }
    }
    if (count($tmp) == 0) return true;
    
    return false;
}

• 7缩麸、找出第二個(gè)字符串在第一個(gè)字符串出現(xiàn)的開(kāi)始位置

// 找到 haystack 中第一個(gè)與 needle 首字符相同的位置，向后截取 needle 的長(zhǎng)度與之比較
function strStr($haystack, $needle) {
    if (empty($needle)) return 0;
    
    if (strlen($haystack) < strlen($needle)) return -1;
    
    for ($i = 0; $i < strlen($haystack); $i++)
    {
        if ($haystack[$i] == $needle[0])
        {
            if (substr($haystack, $i, strlen($needle)) == $needle)
            {
                return $i;
            }
        }
    }
    return -1;
}

• 8赡矢、給定一個(gè)排序數(shù)組杭朱，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個(gè)元素只出現(xiàn)一次吹散，返回移除后數(shù)組的新長(zhǎng)度弧械。
  不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組**并在使用 O(1) 額外空間的條件下完成

function removeDuplicates(&$nums) {
    $index = $nums[0];
    for ($i = 1; $i < count($nums); $i++)
    {
        if ($index == $nums[$i])
        {
            unset($nums[$i]);
        }
        else
        {
            $index = $nums[$i];
        }
    }
    return count($nums);
}

• 9空民、給定一個(gè)排序不重復(fù)數(shù)組和一個(gè)目標(biāo)值刃唐，在數(shù)組中找到目標(biāo)值，并返回其索引界轩。如果目標(biāo)值不存在于數(shù)組中画饥，返回它將會(huì)被按順序插入的位置。

function searchInsert($nums, $target) {
    for ($i = 0; $i < count($nums); $i++)
    {
        if ($target == $nums[$i])
        {
            return $i;
        }
        if ($target > $nums[$i] && isset($nums[$i + 1]) && $target < $nums[$i + 1])
        {
            return $i + 1;
        }
    }
    return count($nums) + 1;
}

• 10浊猾、給定一個(gè)由整數(shù)組成的非空數(shù)組所表示的非負(fù)整數(shù)抖甘，在該數(shù)的基礎(chǔ)上加一。

function plusOne($digits) {
   // 末尾不為 9葫慎，直接加 1 返回
   if ($digits[$len - 1] != 9)
   {
       $digits[$len - 1] += 1;
       return $digits;
   }
   else
   {
       $digits[$len - 1] = 0;
       for ($i = $len - 2; $i >= 0; $i--)
       {
           // 逢 9 進(jìn)位衔彻，當(dāng)為第一位時(shí)為數(shù)組添加一位
           if ($digits[$i] == 9)
           {
               $digits[$i] = 0;
               if ($i == 0)
               {
                   array_unshift($digits, '1');
               }
               else
               {
                   continue;
               }
           }
           else
           {
               $digits[$i] += 1;
               return $digits;
           }
           
       }
   }
}

• 11薇宠、二進(jìn)制求和

// 逆序兩個(gè)字符串，從頭相加逢 2 進(jìn)一艰额，最后結(jié)果逆序
function addBinary($a, $b) {
    $len = max(strlen($a), strlen($b));
    $carry = 0;
    $newStr = '';
    $a = strrev($a);
    $b = strrev($b);
    for ($i = 0; $i < $len; $i++)
    {
        if (isset($a[$i]) && isset($b[$i]))
        {
            if ($a[$i] + $b[$i] + $carry == 2)
            {
                $newStr .= '0';
                $carry = 1;
            }
            else
            {
                $newStr .= $a[$i] + $b[$i] + $carry;
                $carry = 0;
            }
        }
        elseif (isset($a[$i]) && !isset($b[$i]))
        {
            if ($a[$i] + $carry == 2)
            {
                $newStr .= '0';
                $carry = 1;
            }
            else
            {
                $newStr .= $a[$i] + $carry;
                $carry = 0;
            }
        }
        elseif (!isset($a[$i]) && isset($b[$i]))
        {
            if ($b[$i] + $carry == 2)
            {
                $newStr .= '0';
                $carry = 1;
            }
            else
            {
                $newStr .= $b[$i] + $carry;
                $carry = 0;
            }
        }
    }
    return $carry == 1 ? strrev($newStr . '1') : strrev($newStr);
}

• 12澄港、求整數(shù)的平方根，如果為小數(shù)直接取整

// 二分法
function mySqrt($x) {
    $n = $x;
    $m = 1;
    while ($n > $m)
    {
        $n = ($n + $m)/2;
        $m = $x/$n;
    }
    return (int)$n;
}

• 13柄沮、給定一個(gè)非負(fù)整數(shù) numRows回梧，生成楊輝三角的前 numRows 行

// 采用動(dòng)態(tài)規(guī)劃方法
// 第一和第二行是固定的，以下每行由上一行數(shù)據(jù)相鄰數(shù)據(jù)相加得來(lái)铡溪，然后在此行開(kāi)頭結(jié)尾補(bǔ) 1
function generate($numRows) {
    $arr = [];
    $arr[1] = [1];
    $arr[2] = [1, 1];
    for ($i = 3; $i <= $numRows; $i++)
    {
        $arr[$i] = [1];
        for ($j = 0; $j < count($arr[$i -1]) - 1; $j++)
        {
            array_push($arr[$i], ($arr[$i -1][$j] + $arr[$i -1][$j + 1]));
        }
        array_push($arr[$i], 1);
    }
    return $arr;
}
// 輸出結(jié)果：[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

• 14漂辐、買賣股票最佳時(shí)機(jī)

// 只進(jìn)行一次買賣
// 通過(guò)動(dòng)態(tài)規(guī)劃計(jì)算第 i 天賣出的最大利潤(rùn)為 max(前一天賣出的最大利潤(rùn)，今天價(jià)錢(qián) - 之前最低價(jià)錢(qián))
function maxProfit($prices) {
    if (count($prices) == 1 || count($prices) == 0) return 0;
    
    $dp[0] = 0;
    $min = $prices[0];
    for ($i = 1; $i < count($prices); $i++)
    {
        $dp[$i] = max($dp[$i - 1], ($prices[$i] - $min));
        if ($prices[$i] < $min)
        {
            $min = $prices[$i];
        }
    }
    
    rsort($dp);
    
    return $dp[0];
}
// 輸入：[7,1,5,3,6,4]
// 輸出：5 

//多次進(jìn)行買賣
// 只需比較相鄰兩個(gè)大小棕硫，如果后面的大髓涯，就可以獲取到這天的利潤(rùn)，跳過(guò)當(dāng)天繼續(xù)向下循環(huán)
function maxProfit($prices) {
    if (count($prices) == 0 || count($prices) == 1) return 0;
    
    $dp = [];
    for ($i = 0; $i < count($prices); $i++)
    {
        if ($prices[$i + 1] - $prices[$i] > 0)
        {
            $dp[] = $prices[$i + 1] - $prices[$i];
            $i++;
        }
    }
    return array_sum($dp);
}

• 15哈扮、給定一個(gè)非空整數(shù)數(shù)組纬纪，除了某個(gè)元素只出現(xiàn)一次以外，其余每個(gè)元素均出現(xiàn)兩次滑肉。找出那個(gè)只出現(xiàn)了一次的元素包各。

// 異或運(yùn)算
function singleNumber($nums) {
    $b = 0;
    for($i = 0; $i < count($nums); $i++)
    {
        $b = $b ^ $nums[$i];
    }
    
    return $b;
}

• 16、給定一個(gè)已按照升序排列 的有序數(shù)組靶庙，找到兩個(gè)數(shù)使得它們相加之和等于目標(biāo)數(shù)问畅。函數(shù)應(yīng)該返回這兩個(gè)下標(biāo)值 index1 和 index2，其中 index1 必須小于 index2六荒。

// 從數(shù)組兩側(cè)開(kāi)始逐漸向中間遞進(jìn)
function twoSum($numbers, $target) {
        $left = 0;
        $right = count($numbers) - 1;
        while($left < $right)
        {
            if ($numbers[$left] + $numbers[$right] == 9)
            {
                return [$left + 1, $right + 1];
            } 
            elseif ($numbers[$left] + $numbers[$right] > 9)
            {
                $right--;
            }
            else
            {
                $left++;
            }
        }
        return null;
    }

• 17护姆、給定一個(gè)正整數(shù)，返回它在 Excel 表中相對(duì)應(yīng)的列名稱

function convertToTitle($n) {
    $tmp = '';
    while($n > 26)
    {
        $tmp .= chr(64 + ($n % 26));
        $n = intval($n / 26); 
    }
    return chr($n + 64) . strrev($tmp);
}

-18掏击、給定一個(gè)大小為 n 的數(shù)組卵皂，找到其中的眾數(shù)。眾數(shù)是指在數(shù)組中出現(xiàn)次數(shù)大于 ? n/2 ? 的元素砚亭。

// 從第一個(gè)元素開(kāi)始灯变，如果與之相同，計(jì)數(shù)加一捅膘，否則減一添祸，如果計(jì)數(shù)為 0，目標(biāo)數(shù)換成下一個(gè)元素
function majorityElement($nums) {
    $count = 0;
    $tmp = '';
    for ($i = 0; $i < count($nums); $i++)
    {
        if ($count == 0)
        {
            $tmp = $nums[$i];
        }
        if ($tmp == $nums[$i])
        {
            $count++;
        }
        else
        {
            $count--;
        }
    }
    return $tmp;
}

• 19篓跛、給定一個(gè)數(shù)組膝捞，在兩兩不相鄰的情況下計(jì)算最大和（打家劫舍問(wèn)題）

// 動(dòng)態(tài)規(guī)劃
function rob($nums) {
    $max = [$nums[0], max($nums[0], $nums[1])];
    
    for ($i = 2; $i < count($nums); $i++)
    {
        $max[$i] = max(($nums[$i] + $max[$i - 2]), $max[$i - 1]);
    }
    return $max[count($nums) - 1];
}

• 20、統(tǒng)計(jì)所有小于非負(fù)整數(shù) n 的質(zhì)數(shù)的數(shù)量

function countPrimes($n) {
    $count = 0;
    for ($i = 2; $i < $n; $i++)
    {
        $tmp = 0;
        // 判斷一個(gè)數(shù)是否是質(zhì)數(shù)，只需要判斷該數(shù)是否可以被根號(hào) n之前的數(shù)整除
        for ($j = 1; $j <= sqrt($i); $j++)
        {
            if ($i % $j == 0)
            {
                $tmp++;
            }
        }
        if ($tmp == 1)
        {
            $count++;
        }
    }
    return $count;
}
// 厄拉多塞質(zhì)數(shù)篩選法
function countPrimes($n) {
    $nums = [];
    // 創(chuàng)建一個(gè)小于 n 的整數(shù)數(shù)組
    for ($i = 0; $i < $n; $i++)
    {
        $nums[$i] = $i;
    }
    // 從第 3 個(gè)開(kāi)始蔬咬，將數(shù)組之后它的倍數(shù)置為 0
    for ($i = 2; $i < $n; $i++)
    {
        for ($j = $i + 1; $j < $n; $j++)
        {
            if ($nums[$i] != 0 && (($nums[$j] % $nums[$i]) == 0))
            {
                $nums[$j] = 0;
            }
        }
    }
    // 統(tǒng)計(jì)質(zhì)數(shù)個(gè)數(shù)
    $count = 0;
    foreach ($nums as $val)
    {
        if ($val != 0 && $val != 1)
        {
            $count++;
        }
    }
    
    return $count;
}