尝试 Leetcode

尝试 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) {
            echo $result ^= $num;
            $result ^= $num;
        }

        return $result;
    }
}

4.23

Min Stack

设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。

  • push(x) -- 将元素 x 推入栈中。
  • pop() -- 删除栈顶的元素。
  • top() -- 获取栈顶元素。
  • getMin() -- 检索栈中的最小元素。
    尝试解法
    
    class MinStack
    {
protected $stack;

/**
 * initialize your data structure here.
 */
function __construct()
{
    $this->stack = [];
}

/**
 * @param Integer $x
 * @return NULL
 */
function push($x)
{
    $this->stack[] = $x;
}

/**
 * @return NULL
 */
function pop()
{
    array_pop($this->stack);
}

/**
 * @return Integer
 */
function top()
{
    return end($this->stack);
}

/**
 * @return Integer
 */
function getMin()
{
    return min($this->stack);
}

}

Hello。

本帖由 Summer 于 1个月前 加精
《L04 微信小程序从零到发布》
从小程序个人账户申请开始,带你一步步进行开发一个微信小程序,直到提交微信控制台上线发布。
《L05 电商实战》
从零开发一个电商项目,功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等
讨论数量: 6
Egfly
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);
    } 
}

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

1个月前

@Egfly 很巧妙!

1个月前
Ali

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

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;
    }
1个月前

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

1个月前
kzh4435
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;
    }
}
4周前
kenuo

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

3天前

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!