尝试 Leetcode

曾是然的个人博客 / 0 / 7 / 创建于 5年前 / 更新于 5年前

尝试 Leetcode

记录一下自己的小小成长，如果大家有更好更优雅的解法，也可告知我，接受大家一切意见！

GitHub

3.18

Two Sum

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

尝试解法

class Solution
{

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
    function twoSum($nums, $target)
    {
        if (!isset($nums[1])) return;
        foreach ($nums as $key => $num) {
            unset($nums[$key]);
            $result = array_search($target - $num, $nums);
            if ($result !== false) return [$key, $result];
        }
    }
}

目前最优解法

class Solution {

    function twoSum($nums, $target) { 
        $numsCopy = $nums; 
        sort($numsCopy); 
        $num = count($numsCopy); 
        $low = 0; 
        $high = $num-1;

         while($high > $low){
             $sum = $numsCopy[$low] + $numsCopy[$high];
             if($sum == $target){
                $a = $numsCopy[$low];
                $b = $numsCopy[$high];
                break;
             }else if($sum > $target){
                $high--;
             }else{
                $low++;
             }
          }
          for ($i = 0; $i < $num; $i++){
             if($a == $nums[$i]){
                $keyLow = $i;
                break;
             }
          }

          for ($i = $num-1; $i >= 0; $i--){
             if($b == $nums[$i]){
                $keyHigh = $i;
                break;
             }
          }
          return array($keyLow,$keyHigh);
    } 
}

Reverse Integer

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

输入: 123
输出: 321

输入: -123
输出: -321

尝试解法

class Solution 
{

    /**
     * @param Integer $x
     * @return Integer
     */
    function reverse($x) {
        $result = 0;
        while (abs($x) > 9) {
            $num = $x % 10;
            $x = (int)($x / 10);
            $result = $result * 10 + $num;
        }
        $result = $result * 10 + $x;
        if (strlen(base_convert($result, 10, 2)) > 31) return 0;
        return $result;
    }
}

3.19

Palindrome Number

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

输入: 121
输出: true

输入: -123
输出: false

尝试解法

class Solution
{

    /**
     * @param Integer $x
     * @return Boolean
     */
    function isPalindrome($x)
    {
        if ($x < 0) return false;
        if ($x % 10 === 0 && $x != 0) return false;
        $reverse = 0;
        while ($x > $reverse) {
            $reverse = (int)($reverse * 10 + $x % 10);
            $x = (int)($x / 10);
        }
        return $x === $reverse || $x === (int)($reverse / 10);
    }
}

3.20

Roman to Integer

题目有点长，我把链接放这儿哈。查看

尝试解法

class Solution
{

    /**
     * @param String $s
     * @return Integer
     */
    function romanToInt($s)
    {
        $romanMap = [
            1 => 'I',
            5 => 'V',
            10 => 'X',
            50 => 'L',
            100 => 'C',
            500 => 'D',
            1000 => 'M',
        ];

        $nums = [];
        $s = str_split($s, 1);

        foreach ($s as $key => $item) {
            array_push($nums, array_search($item, $romanMap));
        }

        $num = 0;
        for ($i = 0; $i < count($nums) - 1; $i++) {
            if ($nums[$i + 1] > $nums[$i]) {
                $num += $nums[$i + 1] - $nums[$i];
                $i++;
            } else {
                $num += $nums[$i];
            }
        }

        if (isset($nums[$i])) {
            return $num + $nums[$i];
        }

        return $num;
    }
}

3.21

Longest Common Prefix

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串。

输入: ["flower","flow","flight"]
输出: "fl"

尝试解法

class Solution

{

    /**
     * @param String[] $strs
     * @return String
     */
    function longestCommonPrefix($strs)
    {
        usort($strs, function ($current, $next) {
            return strlen($current) > strlen($next);
        });
        $result = '';
        $temp = '';
        foreach (str_split($strs[0], 1) as $str) {
            $temp .= $str;
            for ($i = 1; $i < count($strs); $i++) {
                if (strpos($strs[$i], $temp) !== 0) break 2;
            }
            $result .= $str;
        }
        return $result;
    }
}

3.22

Valid Parentheses

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

输入: "()[]{}"
输出: true
输入: "(]"
输出: false

尝试解法

class Solution
{
    /**
     * @param String $s
     * @return Boolean
     */
    function isValid($s)
    {
        if (empty($s)) return true;
        $s = str_split($s);
        if (count($s) % 2 !== 0) return false;
        $leftMap = [
            ')' => '(',
            '}' => '{',
            ']' => '['
        ];
        $leftStack = [];
        while (1) {
            if (in_array(current($s), $leftMap)) {
                array_push($leftStack, current($s));
            } else {
                if (array_pop($leftStack) !== $leftMap[current($s)]) {
                    return false;
                }
            }
            if(!next($s)) break;
        }
        return $leftStack === [];
    }
}

3.23

Merge two sorted lists

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4

尝试解法

class Solution
{
    /**
     * @param ListNode $l1
     * @param ListNode $l2
     * @return ListNode
     */
    function mergeTwoLists($l1, $l2)
    {
        if (!$l1 || !$l2) return $l1 ?? $l2;
        if ($l1->val < $l2->val) {
            $list = $l1;
            $list->next = $this->mergeTwoLists($l1->next, $l2);
        } else {
            $list = $l2;
            $list->next = $this->mergeTwoLists($l1, $l2->next);
        }
        return $list;
    }
}

3.24

Remove Duplicates from Sorted Array

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

给定数组 nums = [1, 1, 2]
函数应该返回新的长度 2，并且原数组 nums 的前两个元素被修改为 1，2
你不需要考虑数组中超出新长度后面的元素

尝试解法

class Solution
{
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function removeDuplicates(&$nums)
    {
        $i = 0;
        for ($j = 1; $j < count($nums); $j++) {
            if ($nums[$j] != $nums[$i]) {
                $i++;
                $nums[$i] = $nums[$j];
            }
        }
        return $i + 1;
    }
}

3.25

Remove Element

给定 nums = [3,2,2,3], val = 3
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2
你不需要考虑数组中超出新长度后面的元素

尝试解法

class Solution
{
    /**
     * @param Integer[] $nums
     * @param Integer $val
     * @return Integer
     */
    function removeElement(&$nums, $val)
    {
        $i = 0;
        for ($j = 0; $j < count($nums); $j++) {
            if ($nums[$j] !== $val) {
                $nums[$i] = $nums[$j];
                $i++;
            }
        }
        return $i;
    }
}

3.26

Implement strstr

输入: haystack = "hello", needle = "ll"
输出: 2

尝试解法

class Solution
{
    /**
     * @param String $haystack
     * @param String $needle
     * @return Integer
     */
    function strStr($haystack, $needle)
    {
        if (!$needle) {
            return 0;
        }
        if (strlen($needle) > strlen($haystack)) {
            return -1;
        }
        if (strlen($needle) === strlen($haystack)) {
            for ($i = 0; $i < strlen($needle); $i++) {
                if ($needle[$i] != $haystack[$i]) {
                    return -1;
                }
            }
            return 0;
        }
        $i = 0;
        for ($j = 0; $j < strlen($haystack) - strlen($needle) + 1; $j++) {
            if ($haystack[$j] === $needle[$i]) {
                $i += 1;
                while ($i < strlen($needle)) {
                    if ($needle[$i] !== $haystack[$j + $i]) {
                        $i = 0;
                        break;
                    }
                    $i += 1;
                }
                if ($i === strlen($needle)) {
                    return $j;
                }
            }
        }
        return -1;
    }
}

3.27

Search Insert Position

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。

尝试解法

class Solution
{
    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer
     */
    function searchInsert($nums, $target)
    {
        if (in_array($target, $nums)) {
            return array_search($target, $nums);
        }

        if (current($nums) > $target) {
            array_unshift($nums, $target);
            return 0;
        }

        if (end($nums) < $target) {
            array_push($nums, $target);
            return count($nums) - 1;
        }

        array_push($nums, $target);
        sort($nums);
        return array_search($target, $nums);
    }
}

3.29

Length of Last Word

输入: "Hello World"
输出: 5

尝试解法

class Solution
{
    /**
     * @param String $s
     * @return Integer
     */
    function lengthOfLastWord($s)
    {
        $s = strrev(trim($s));
        $length = 0;
        for ($i = 0; $i < strlen($s); $i++) {
            if ($s[$i] === ' ') {
                return $length;
            }
            $length++;
        }
        return $length;
    }
}

class Solution
{
    function lengthOfLastWord($s)
    {
        $s = explode(' ', trim($s));
        return strlen(end($s));
    }
}

3.30

Plus One

输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123

尝试解法

class Solution
{
    /**
     * @param Integer[] $digits
     * @return Integer[]
     */
    function plusOne($digits)
    {
        for ($i = array_key_last($digits); $i > -1; $i--) {
            if ($digits[$i] === 9) {
                $digits[$i] = 0;
                continue;
            }
            if ($digits[$i] < 9) {
                $digits[$i] = $digits[$i] + 1;
                return $digits;
            }
        }
        array_unshift($digits, 1);
        return $digits;
    }
}

4.2

Add Binary

输入: a = "11", b = "1"
输出: "100"

尝试解法

class Solution
{
    /**
     * @param String $a
     * @param String $b
     * @return String
     */
    function addBinary($a, $b)
    {
        $result = '';

        if (strlen($a) > strlen($b)) {
            $b = str_pad($b, strlen($a), 0, STR_PAD_LEFT);
        } else {
            $a = str_pad($a, strlen($b), 0, STR_PAD_LEFT);
        }

        for ($i = 0; $i < strlen($a); $i++) {
            $result .= $a[$i] + $b[$i];
        }

        $result = strrev($result);

        for ($i = 0; $i < strlen($result); $i++) {
            if ($result[$i] < 2) {
                continue;
            }

            $result[$i] = $result[$i] - 2;
            if (isset($result[$i + 1])) {
                $result[$i + 1] = $result[$i + 1] + 1;
                continue;
            }

            $result .= 1;
        }

        return strrev($result);
    }
}

4.3

Combine Two Tables

题目

select FirstName, LastName, City, State
from Person left join Address
on Person.PersonId = Address.PersonId;

4.10

Single Number

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

输入: [2,2,1]
输出: 1

class Solution
{

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function singleNumber($nums)
    {
        $result = 0;
        foreach ($nums as $num) {
            $result ^= $num;
        }

        return $result;
    }
}

学习 leetcode

本作品采用《CC 协议》，转载必须注明作者和本文链接

Hello。

本帖由 Summer 于 5年前加精

讨论数量: 7

Egfly

见习助教 14 声望 / PHP开发 @ 回炉重造

这是目前看到的最优解，耗时大概30左右。我写的最快70 :joy:

5年前评论

曾是然

课程读者 279 声望 / Developer @ Tencent

@Egfly 很巧妙！

Aliliin

课程读者 522 声望 / Phper @ 转 Goer

本人最简单的暴力解法,速度吗?就别提了.

public function twoSum($nums, $target)
    {
        $outArr = [];
        foreach ($nums as $key => $num) {
            $num1 = $target - $num;
            foreach ($nums as $k => $n) {
                if ($k != $key) {
                    if ($num1 == $n) {
                        $outArr = [
                            $key,
                            $k,
                        ];
                        if (!empty($outArr)) {
                            return $outArr;
                        }
                    }
                }
            }
        }
        return $outArr;
    }

@Ali 我大一的时候，学 c 的时候，考试就用这种暴力算法！ :cow: :beer:

kzh4435

L5.4 译者 163 声望 / PHP @ PHP

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
    function twoSum($nums, $target) {
        foreach ($nums as $k=>$v){
            $t=$target-$v;
            if(in_array($t,$nums)){
                if($k!=array_keys($nums,$t)[0]) {
                    $arr = [array_keys($nums, $t)[0], $k];
                }
            }
        }
        return $arr;
    }
}

JeffreyBool

课程读者 373 声望 / golang工程师 @ 映客直播

@Ali O(n2) 时间复杂度啊

UpGod

66 声望

  function twoSum($nums, $target) {
        foreach($nums as $i=>$v){
            if(($j=array_search($target-$v,$nums))!==false && $i!=$j){  
                return [$i,$j];
            }
        }
        return [];
    }

执行用时 : 140 ms, 在所有 php 提交中击败了58.47%的用户
内存消耗 : 15.7 MB, 在所有 php 提交中击败了48.95%的用户

我想要最优解

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容，与人为善，比聪明更重要！

帮助

尝试 Leetcode

尝试 Leetcode

3.18

Two Sum

尝试解法

目前最优解法

Reverse Integer

尝试解法

3.19

Palindrome Number

尝试解法

3.20

Roman to Integer

尝试解法

3.21

Longest Common Prefix

尝试解法

3.22

Valid Parentheses

尝试解法

3.23

Merge two sorted lists

尝试解法

3.24

Remove Duplicates from Sorted Array

尝试解法

3.25

Remove Element

尝试解法

3.26

Implement strstr

尝试解法

3.27

Search Insert Position

尝试解法

3.29

Length of Last Word

尝试解法

3.30

Plus One

尝试解法

4.2

Add Binary

尝试解法

4.3

Combine Two Tables

4.10

Single Number

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

请登录