LeetCode代码汇总（一）

  • 1、给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
// 交换数组的键和值，判断数组中是否含有 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、有符号整数反转
function reverse($x) {
    if (!in_num($x)) return 'error type';
    $remainder = 0; //余数
    $res = 0; 
    while ($x > 9 || $x < -9)
    {
        $remainder = $x % 10;
        $x = ($x - $remainder ) / 10;
        $res = $res * 10 + $remainder;
    }
    return $res * 10 + $x;
}
  • 3、有符号整数判断回文
// 时间复杂度：O(lg(n))  空间复杂度：O(1)
// 类似于第二题
function isPalindrome($x) {
    // 负数不会是回文
    if (is_int($x) && $x < 0) return false;
    
    $tmp = 0;
    while($x > $tmp)
    {
        $tmp = $tmp * 10 + ($x % 10);
        $x = ($x - $tmp) / 10;
    }
    // 如果 x 为类似 121 时，最后得到的 tmp 为 12，x为 1
    if ($tmp == $x || $x = $tmp / 10) return true;
    
    return false;
}
  • 4、罗马数字转整数
// 从字符串末尾开始，获取两个字符，如果前面一个字符大直接相加，否则相减
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、获取字符串公共的前缀
// 先将第一个元素当作公共前缀，与第二个比较，去掉不同的的部分，以此类推
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、给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效
// 采用栈的形式，判断 s 的当前元素能否与栈的最后一个元素匹配，不能则入栈，能则出栈
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、找出第二个字符串在第一个字符串出现的开始位置
// 找到 haystack 中第一个与 needle 首字符相同的位置，向后截取 needle 的长度与之比较
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、给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
    不要使用额外的数组空间，你必须在原地修改输入数组**并在使用 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、给定一个排序不重复数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
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、给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
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 进位，当为第一位时为数组添加一位
           if ($digits[$i] == 9)
           {
               $digits[$i] = 0;
               if ($i == 0)
               {
                   array_unshift($digits, '1');
               }
               else
               {
                   continue;
               }
           }
           else
           {
               $digits[$i] += 1;
               return $digits;
           }
           
       }
   }
}
  • 11、二进制求和
// 逆序两个字符串，从头相加逢 2 进一，最后结果逆序
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、求整数的平方根，如果为小数直接取整
// 二分法
function mySqrt($x) {
    $n = $x;
    $m = 1;
    while ($n > $m)
    {
        $n = ($n + $m)/2;
        $m = $x/$n;
    }
    return (int)$n;
}
  • 13、给定一个非负整数 numRows，生成杨辉三角的前 numRows 行
// 采用动态规划方法
// 第一和第二行是固定的，以下每行由上一行数据相邻数据相加得来，然后在此行开头结尾补 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;
}
// 输出结果：[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
  • 14、买卖股票最佳时机
// 只进行一次买卖
// 通过动态规划计算第 i 天卖出的最大利润为 max(前一天卖出的最大利润，今天价钱 - 之前最低价钱)
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 

//多次进行买卖
// 只需比较相邻两个大小，如果后面的大，就可以获取到这天的利润，跳过当天继续向下循环
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、给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
// 异或运算
function singleNumber($nums) {
    $b = 0;
    for($i = 0; $i < count($nums); $i++)
    {
        $b = $b ^ $nums[$i];
    }
    
    return $b;
}
  • 16、给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
// 从数组两侧开始逐渐向中间递进
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、给定一个正整数，返回它在 Excel 表中相对应的列名称
function convertToTitle($n) {
    $tmp = '';
    while($n > 26)
    {
        $tmp .= chr(64 + ($n % 26));
        $n = intval($n / 26); 
    }
    return chr($n + 64) . strrev($tmp);
}

-18、给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

// 从第一个元素开始，如果与之相同，计数加一，否则减一，如果计数为 0，目标数换成下一个元素
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、给定一个数组，在两两不相邻的情况下计算最大和（打家劫舍问题）
// 动态规划
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、统计所有小于非负整数 n 的质数的数量
function countPrimes($n) {
    $count = 0;
    for ($i = 2; $i < $n; $i++)
    {
        $tmp = 0;
        // 判断一个数是否是质数，只需要判断该数是否可以被根号 n之前的数整除
        for ($j = 1; $j <= sqrt($i); $j++)
        {
            if ($i % $j == 0)
            {
                $tmp++;
            }
        }
        if ($tmp == 1)
        {
            $count++;
        }
    }
    return $count;
}
// 厄拉多塞质数筛选法
function countPrimes($n) {
    $nums = [];
    // 创建一个小于 n 的整数数组
    for ($i = 0; $i < $n; $i++)
    {
        $nums[$i] = $i;
    }
    // 从第 3 个开始，将数组之后它的倍数置为 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;
            }
        }
    }
    // 统计质数个数
    $count = 0;
    foreach ($nums as $val)
    {
        if ($val != 0 && $val != 1)
        {
            $count++;
        }
    }
    
    return $count;
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 217,277评论 6赞 503
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 92,689评论 3赞 393
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 163,624评论 0赞 353
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 58,356评论 1赞 293
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 67,402评论 6赞 392
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,292评论 1赞 301
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,135评论 3赞 418
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,992评论 0赞 275
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,429评论 1赞 314
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,636评论 3赞 334
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,785评论 1赞 348
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,492评论 5赞 345
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 41,092评论 3赞 328
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,723评论 0赞 22
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,858评论 1赞 269
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,891评论 2赞 370
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,713评论 2赞 354