LeetCode代码汇总(一)

2019-04-19  本文已影响0人  yzw12138
// 交换数组的键和值,判断数组中是否含有 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]];
        }
    }
}
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;
}
// 时间复杂度: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;
}
// 从字符串末尾开始,获取两个字符,如果前面一个字符大直接相加,否则相减
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;
}
// 先将第一个元素当作公共前缀,与第二个比较,去掉不同的的部分,以此类推
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"
// 采用栈的形式,判断 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;
}
// 找到 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;
}
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);
}
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;
}
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;
           }
           
       }
   }
}
// 逆序两个字符串,从头相加逢 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);
}
// 二分法
function mySqrt($x) {
    $n = $x;
    $m = 1;
    while ($n > $m)
    {
        $n = ($n + $m)/2;
        $m = $x/$n;
    }
    return (int)$n;
}
// 采用动态规划方法
// 第一和第二行是固定的,以下每行由上一行数据相邻数据相加得来,然后在此行开头结尾补 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]]
// 只进行一次买卖
// 通过动态规划计算第 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);
}
// 异或运算
function singleNumber($nums) {
    $b = 0;
    for($i = 0; $i < count($nums); $i++)
    {
        $b = $b ^ $nums[$i];
    }
    
    return $b;
}
// 从数组两侧开始逐渐向中间递进
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;
    }
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;
}
// 动态规划
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];
}
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;
}
上一篇 下一篇

猜你喜欢

热点阅读