- 1树绩、同構(gòu)字符串判斷
// 獲取每個字符串不同字母的索引位置判斷是否相同
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萨脑、給定一個整數(shù)數(shù)組,判斷是否存在重復(fù)元素葱峡。
function containsDuplicate($nums) {
$map = [];
for ($i = 0; $i < count($nums); $i++)
{
if (isset($map[$nums[$i]]))
{
return true;
}
else
{
$map[$nums[$i]] = 0;
}
}
}
- 3砚哗、給定一個整數(shù),編寫一個函數(shù)來判斷它是否是 2 的冪次方砰奕。
// 采用位運算 & 來解決該問題
// 2 的 n 次冪可以表示為:2^0, 2^1, 2^2, 2^3……
// 如果我們將其轉(zhuǎn)換為二進制表示為:1, 10, 100, 1000, 10000……
// 因此我們可以看到蛛芥,如果一個數(shù)是 2 的 n 次冪,那么該數(shù)的二進制中就只含有一個 1
// n - 1的二進制為:1, 011, 0111, 01111……
// 所以 n 和 n - 1 進行 & 運算军援,為 0 則表示該數(shù)是 2 的 n 次冪
function isPowerOfTwo($n) {
return ($n & ($n -1)) == 0;
}
同理在計算 3 的冪次方仅淑、4 的冪次方等時,同樣可以使用此類方法胸哥,先將 n 轉(zhuǎn)換為對應(yīng)進制的數(shù)涯竟,判斷轉(zhuǎn)完之后的數(shù)字是否只含有一個 1
- 4、給定兩個字符串 s 和 t 空厌,編寫一個函數(shù)來判斷 t 是否是 s 的一個字母異位詞庐船。
// 統(tǒng)計每個字母出現(xiàn)次數(shù)進行比較
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;
}
//將兩個字符串轉(zhuǎn)數(shù)組排序后比較
function isAnagram($s, $t) {
$a = asort(str_split($s));
$b = asort(str_split($t));
return $a == $b;
}
- 5、給定一個非負(fù)整數(shù) num嘲更,反復(fù)將各個位上的數(shù)字相加筐钟,直到結(jié)果為一位數(shù)。
// 假設(shè)給定一個三位數(shù) abc赋朦,可以表示為 100 * a + 10 * b + c
// 第一次計算后可以得到結(jié)果為 a+b+c篓冲,相比與原始值此次計算數(shù)值減小 99 * a + 9 * b = 9 * ( 11 * a + b),減少了 9 的整數(shù)倍
// 因此可以通過 abc 對 9 取余得到結(jié)果
function addDigits($num) {
return $num % 9 == 0 ? 9 : $num % 9 ;
}
- 6宠哄、編寫一個函數(shù)壹将,其作用是將輸入的字符串反轉(zhuǎn)過來。輸入字符串以字符數(shù)組
char[]
的形式給出毛嫉。不要給另外的數(shù)組分配額外的空間诽俯,你必須修改輸入數(shù)組**、使用 O(1) 的額外空間解決這一問題承粤。
// 從中間開始調(diào)換兩側(cè)元素
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暴区、判斷一個整數(shù)是否是完全平方數(shù)
// 二分查找
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、判斷丑數(shù)密任,丑數(shù)是只包含質(zhì)因數(shù) 2, 3, 5 的正整數(shù)颜启。
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 個數(shù)的序列浪讳,找出 0 .. n 中沒有出現(xiàn)在序列中的那個數(shù)缰盏。
// 利用位運算符異或
// 也可以通過求和
function missingNumber($nums) {
$res = count($nums);
for ($i = 0; $i <= count($nums); $i++)
{
$res = $res ^ $nums[$i];
}
return $res;
}
- 10、給定一個數(shù)組 nums,編寫一個函數(shù)將所有 0 移動到數(shù)組的末尾口猜,同時保持非零元素的相對順序负溪。
// 方法一:第一步刪除數(shù)組中的 0 元素并記錄個數(shù),第二步在數(shù)組末尾補 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 的放在一個數(shù)組川抡,小于 0 的放在一個數(shù)組,同樣也可以采用冒泡的方式
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须尚、給定一種規(guī)律 pattern 和一個字符串 str 崖堤,判斷 str 是否遵循相同的規(guī)律。
// map
function wordPattern($pattern, $str) {
$map1 = $this->getMap($pattern, strlen($pattern));
$arr = explode(" ", $str);
$map2 = $this->getMap($arr, count($arr));
return $map1 == $map2;
}
// 獲取內(nèi)容索引數(shù)組
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 塊石頭撩轰。 拿掉最后一塊石頭的人就是獲勝者胯甩。你作為先手。每一步都是最優(yōu)解堪嫂。
// 此題困擾我好久偎箫,想過好幾個辦法,好像都沒辦法實現(xiàn)皆串,最后沒辦法看了官方的題解淹办,原來是一道找規(guī)律的題,找到規(guī)律只需一行代碼
// 如果石頭個數(shù)為:1愚战、2娇唯、3齐遵,那么你一定能贏
// 如果石頭個數(shù)為:4寂玲,那么無論你先拿幾個石頭都會輸,因此可以發(fā)現(xiàn)如果在對方拿石頭回合梗摇,石頭個數(shù)為 4 是拓哟,那么對方一定會輸
// 如果石頭個數(shù)為:5、6伶授、7断序,根據(jù)上一個條件,此次你可以拿1糜烹、2违诗、3個石頭,為對方留下 4 個疮蹦,那么他一定輸
// 如果石頭個數(shù)為:8诸迟,此輪當(dāng)你拿過石頭后,剩余數(shù)量為 5、6阵苇、7 中的一個壁公,此時對方拿完給你剩余 4 個石頭,對方一定會贏
// 因此得出結(jié)論绅项,如果石頭個數(shù)為 4 的倍數(shù)紊册,那么你就沒有贏得可能
// 規(guī)律找的好,代碼寫得少
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铺浇、給定一個包含大寫字母和小寫字母的字符串痢畜,找到通過這些字母構(gòu)造成的最長的回文串。在構(gòu)造過程中鳍侣,請注意區(qū)分大小寫丁稀。比如 "Aa" 不能當(dāng)做一個回文字符串。
// 想要構(gòu)成回文字符串倚聚,包含的字符必須是偶數(shù)個线衫,最多有一個計數(shù)個的字母
// 第一步:計算字符串中不同字母的個數(shù)并存入數(shù)組
// 第二步:獲取數(shù)組中最大的奇數(shù),同時將數(shù)組中的奇數(shù)刪除
// 第四步:計算數(shù)據(jù) value 的和最大奇數(shù)的和即為結(jié)果
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惑折、統(tǒng)計字符串中的單詞個數(shù)授账,這里的單詞指的是連續(xù)的不是空格的字符。
// 英文字母的 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 枚硬幣镀梭。給定一個數(shù)字 n,找出可形成完整階梯行的總行數(shù)朱灿。
function arrangeCoins($n) {
$sum = 1;
$index = 1;
while ($sum <= $n)
{
$index++;
$sum += $index;
}
return $index - 1;
}
- 17续扔、給定一個范圍在 1 ≤ a[i] ≤ n ( n = 數(shù)組大小 ) 的 整型數(shù)組攻臀,數(shù)組中的元素一些出現(xiàn)了兩次,另一些只出現(xiàn)一次纱昧。找到所有在 [1, n] 范圍之間沒有出現(xiàn)在數(shù)組中的數(shù)字刨啸。
// 首次遍歷數(shù)組將數(shù)組內(nèi)值放到對應(yīng)位置上,然后遍歷新的數(shù)組识脆,不存在的索引即為結(jié)果
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设联、給定一個非空的字符串加匈,判斷它是否可以由它的一個子串重復(fù)多次構(gòu)成。給定的字符串只含有小寫英文字母仑荐,并且長度不超過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粘招、給定一個二進制數(shù)組啥寇, 計算其中最大連續(xù)1的個數(shù)。
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洒扎、對于一個 正整數(shù)辑甜,如果它和除了它自身以外的所有正因子之和相等,我們稱它為“完美數(shù)”袍冷。
// 計算所有因子求和
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;
}