LeetCode代碼匯總(二)

  • 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;
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末磷醋,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子胡诗,更是在濱河造成了極大的恐慌邓线,老刑警劉巖,帶你破解...
    沈念sama閱讀 218,755評論 6 507
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件煌恢,死亡現(xiàn)場離奇詭異骇陈,居然都是意外死亡,警方通過查閱死者的電腦和手機瑰抵,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,305評論 3 395
  • 文/潘曉璐 我一進店門你雌,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人二汛,你說我怎么就攤上這事婿崭。” “怎么了肴颊?”我有些...
    開封第一講書人閱讀 165,138評論 0 355
  • 文/不壞的土叔 我叫張陵氓栈,是天一觀的道長。 經(jīng)常有香客問我苫昌,道長颤绕,這世上最難降的妖魔是什么幸海? 我笑而不...
    開封第一講書人閱讀 58,791評論 1 295
  • 正文 為了忘掉前任祟身,我火速辦了婚禮,結(jié)果婚禮上物独,老公的妹妹穿的比我還像新娘袜硫。我一直安慰自己,他們只是感情好挡篓,可當(dāng)我...
    茶點故事閱讀 67,794評論 6 392
  • 文/花漫 我一把揭開白布婉陷。 她就那樣靜靜地躺著帚称,像睡著了一般。 火紅的嫁衣襯著肌膚如雪秽澳。 梳的紋絲不亂的頭發(fā)上闯睹,一...
    開封第一講書人閱讀 51,631評論 1 305
  • 那天,我揣著相機與錄音担神,去河邊找鬼楼吃。 笑死,一個胖子當(dāng)著我的面吹牛妄讯,可吹牛的內(nèi)容都是我干的孩锡。 我是一名探鬼主播,決...
    沈念sama閱讀 40,362評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼亥贸,長吁一口氣:“原來是場噩夢啊……” “哼躬窜!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起炕置,我...
    開封第一講書人閱讀 39,264評論 0 276
  • 序言:老撾萬榮一對情侶失蹤荣挨,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后朴摊,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體垦沉,經(jīng)...
    沈念sama閱讀 45,724評論 1 315
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,900評論 3 336
  • 正文 我和宋清朗相戀三年仍劈,在試婚紗的時候發(fā)現(xiàn)自己被綠了厕倍。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 40,040評論 1 350
  • 序言:一個原本活蹦亂跳的男人離奇死亡贩疙,死狀恐怖讹弯,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情这溅,我是刑警寧澤组民,帶...
    沈念sama閱讀 35,742評論 5 346
  • 正文 年R本政府宣布,位于F島的核電站悲靴,受9級特大地震影響臭胜,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜癞尚,卻給世界環(huán)境...
    茶點故事閱讀 41,364評論 3 330
  • 文/蒙蒙 一耸三、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧浇揩,春花似錦仪壮、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,944評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽爽彤。三九已至,卻和暖如春缚陷,著一層夾襖步出監(jiān)牢的瞬間适篙,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,060評論 1 270
  • 我被黑心中介騙來泰國打工箫爷, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留匙瘪,地道東北人。 一個月前我還...
    沈念sama閱讀 48,247評論 3 371
  • 正文 我出身青樓蝶缀,卻偏偏與公主長得像丹喻,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子翁都,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 44,979評論 2 355

推薦閱讀更多精彩內(nèi)容