2022-03-29

leetcode:4Sum

问题

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

0 <= a, b, c, d < n
a, b, c, and d are distinct.
nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.

难度

中等

代码

class Solution
{

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[][]
     */
    public function fourSum($nums, $target)
    {
        $len = count($nums);
        if (!$len) {
            return [];
        }

        sort($nums);

        $res = [];
        for ($i = 0, $l1 = $len - 3; $i < $l1; $i++) {
            if ($i && $nums[$i] === $nums[$i - 1]) {
                continue;
            }

            $sum = $target - $nums[$i];
            for ($j = $i + 1, $len1 = $len - 2; $j < $len1; $j++) {
                if ($j === ($i + 1) || $nums[$j] !== $nums[$j - 1]) {
                    $x = $j + 1;
                    $y = $len - 1;

                    while ($x < $y) {
                        $s = $nums[$j] + $nums[$x] + $nums[$y];
                        if ($s === $sum) {
                            $res[] = [$nums[$i], $nums[$j], $nums[$x], $nums[$y]];
                            $x++;
                        } else if ($s > $sum) {
                            $y--;
                        } else {
                            $x++;
                        }

                        while ($x < $y && ($x - 1) > $j && $nums[$x] === $nums[$x - 1]) {
                            $x++;
                        }

                        while ($x < $y && $nums[$y] === $nums[$y + 1]) {
                            $y--;
                        }

                    }
                }
            }
        }

        return $res;
    }
}

这题思路和前面的求3个数差不多,也是利用那里的方法来解,开始在[-2, -1, 0, 0, 1, 2]这个测试没有通过,少了一个答案[-1,0,0,1], 经过一番测试, 发现在最后判断$x相同值时需要加上($x - 1) > $j条件.

2022-03-16

leetcode:Letter Combinations of a Phone Number

问题

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

结果

class Solution {

    public $keyboard = [
            '2' => ['a', 'b', 'c'],
            '3' => ['d', 'e', 'f'],
            '4' => ['g', 'h', 'i'],
            '5' => ['j', 'k', 'l'],
            '6' => ['m', 'n', 'o'],
            '7' => ['p', 'q', 'r', 's'],
            '8' => ['t', 'u', 'v'],
            '9' => ['w', 'x', 'y', 'z'],
    ];

    /**
     * @param String $digits
     * @return String[]
     */
    function letterCombinations($digits) {
        if(!$digits) {
            return [];
        }

        $len = strlen($digits);
        if($len === 1) {
            return $this->keyboard[$digits];
        }
        
        $first = $this->keyboard[$digits[0]];
        $i = 1;

        do{
            $str = substr($digits, $i++, 1);
            if(empty($str)){
                break;
            }

            $first = $this->combination($first, $str);
        }while(true);

        return $first;
    }

    function combination($arr1, $str)
    {
        $res = [];
        $arr = $this->keyboard[$str];
        foreach ($arr1 as $ch) {
            foreach($arr as $item) {
                $res[] = $ch . $item;
            }
        }

        return $res;
    }
}

这个题根据数字要列出所有的字母组合,假如输入239,那么需要用2对应的每一个字母先和3所有的字母组合,然后再和9所有的字母组合,如果再有数字,那么接着和下一个数字的所有字母组合.可以发现这里一直在重复着用上一个字母组合数组去和下一个字母数组组合成一个新的数组直到结束.

2022-03-09

leetcode:Container With Most Water

问题

Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

这里有一个数组,长度在2~10^5之间.求这些数字在坐标中组成的最大的长方形面积.

解决

最容易想到的是直接遍历:

class Solution {


    /**
     * @param Integer[] $height
     * @return Integer
     */
    function maxArea($height) {
        $len = count($height);
        $area = 0;
        for($i = 0, $len1 = $len - 1; $i < $len1; $i++) {
             for($j = $len; $j > $i; $j--) {
                 $area = max(min($height[$i], $height[$j]) * ($j - $i), $area);
             }
        }
        
        return $area;
    }
}

我开始想的还多一步,定义了一个数组将外层循环每一轮最大值存下来最后再求最大值,对于数组长度不大时没有问题,但是题目中数组长度能够达到10^5,这段代码提交的结果是超时.

后来看他们的解决方法,才发现其实也很简单.

class Solution {


    /**
     * @param Integer[] $height
     * @return Integer
     */
    function maxArea($height) {
        $len = count($height);
        $area = 0;
        $l = 0;
        $r = $len - 1;
        while($l < $r) {
            $area = max($area, min($height[$l], $height[$r]) * ($r - $l));
            if($height[$l] < $height[$r]) {
                $l++;
            } else {
                $r--;
            }
        }

        return $area;
    }
}

首先求最左边和最右边的结果,因为这时长度最长.然后看左边和右边哪个数小,相应的就去找下一个值.

2022-02-25

a标签跨域下载资源

前言

下载功能在网站中十分常见,实现的方式也多样,可以通过后端也可以通过前端.比如:a标签.

问题

a标签有一个属性:download.a标签大多数时候都是用于跳转一个链接.但是加上download属性之后便不会再跳转该链接,而是成了下载.但是这里的下载是有限制条件的.这里清楚的说到:

download属性仅对同源地址或者blob和data协议的有效.

也就是说甲网站想要在网页里用a标签直接下载乙网站的视频或网页是不行的,因为他们域名不同.即使加上download属性,也无效,浏览器也会忽略.

解决方案

虽然不能直接下载,但是后面有提到,blob,data这类是不受限制的,例:

var x = new XMLHttpRequest();
x.open("GET", link, true);
x.responseType = 'blob';
x.onload=(e)=> {
    var url = window.URL.createObjectURL(x.response)
    var a = document.createElement('a')
    a.href = url
    a.download = fileName
    a.click()
}
x.send();

这里是通过ajax发起一个get请求获取到要下载的资源,返回二进制流数据.得到数据后在用a标签去下载

2022-01-12

Uncaught TypeError: window.opener is null

HTML中a标签可以设置target属性,其属性值包括:

_self 默认值
_blank
_parent
_top

其中,_blank会打开一个新的页卡或窗口,A页面通过a标签打开了B页面:

<a href="http://example.com" target="_blank">Go</a>

在B页面中想对A页面操作,那么可以使用window.opener.
可是,如果通过a标签_blank打开的窗口,默认会有一个rel属性并且值为noopener.这就造成B页面中出错:

Uncaught TypeError: window.opener is null

解决这个问题,我们只需在A页面的a标签上加上rel属性,并且值等于opener就解决了.

<a href="http://example.com" target="_blank" rel="opener">Go</a>

对此在https://developer.mozilla.org/en-US/docs/Web/HTML/Element/a中有明确的详细的说明.

如果在A页面中打开B页面是通过js来实现:

window.open("http://example.com", '_blank');

这样,是不会存在a标签那样的问题

2021-12-06

leetcode:3Sum

问题

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

代码

根据投票最高的得到:

class Solution
{

    /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    public function threeSum($nums)
    {
        $len = count($nums);
        if ($len < 3) {
            return [];
        }

        sort($nums, SORT_ASC);
        if ($nums[0] > 0) {
            return [];
        }

        $res = [];
        for ($i = 0, $len1 = $len - 2; $i < $len1; $i++) {
            if ($i === 0 || ($i > 0 && $nums[$i] !== $nums[$i - 1])) {
                $lo  = $i + 1;
                $hi  = $len - 1;
                $sum = 0 - $nums[$i];

                while ($lo < $hi) {
                    $third = $nums[$lo] + $nums[$hi];
                    if ($third === $sum) {
                        $res[] = [$nums[$i], $nums[$lo], $nums[$hi]];

                        while ($lo < $hi && $nums[$lo] === $nums[$lo + 1]) {
                            $lo++;
                        }

                        while ($lo < $hi && $nums[$hi] === $nums[$hi - 1]) {
                            $hi--;
                        }

                        $lo++;
                        $hi--;
                        continue;
                    }

                    if ($third < $sum) {
                        $lo++;
                        continue;
                    }

                    $hi--;
                }
            }
        }

        return $res;
    }
}

结果

318/318 cases passed (180 ms)
Your runtime beats 95.24 % of php submissions
Your memory usage beats 85.71 % of php submissions (24.9 MB)

2021-11-26

leetcode:Longest Common Prefix

问题

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string “”.

代码

class Solution
{

    /**
     * @param String[] $strs
     * @return String
     */
    public function longestCommonPrefix($strs)
    {
        $prefix = '';

        $min = min(array_map('strlen', $strs));
        if (!$min) {
            return $prefix;
        }

        for ($i = 0; $i < $min; $i++) {
            $alpha = $strs[0][$i];
            for ($j = 1, $b = count($strs); $j < $b; $j++) {
                if ($strs[$j][$i] !== $alpha) {
                    return $prefix;
                }
            }

            $prefix .= $alpha;
        }

        return $prefix;
    }
}

结果

123/123 cases passed (5 ms)
Your runtime beats 85.19 % of php submissions
Your memory usage beats 60.49 % of php submissions (15.7 MB)

2021-11-25

leetcode:Integer to Roman

题目

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

代码

class Solution
{

    /**
     * @param Integer $num
     * @return String
     */
    public function intToRoman($num)
    {
        $roman = '';

        $nine   = ['', 'CM', 'XC', 'IX'];
        $four   = ['', 'CD', 'XL', 'IV'];
        $greate = ['', 'D', 'L', 'V'];
        $less   = ['M', 'C', 'X', 'I'];
        $steps  = [1000, 100, 10, 1];

        $i = 0;
        while ($i < 4) {
            $x = intval($num / $steps[$i]);
            if ($x < 1) {
                $i++;
                continue;
            }
            $num = $num % $steps[$i];

            $times = $x % 5;
            if ($times === 4) {
                if ($x > 5) {
                    $roman .= $nine[$i];
                    $i++;
                    continue;
                }

                $roman .= $four[$i];
                $i++;
                continue;
            }

            if ($x >= 5) {
                $roman .= $greate[$i] . str_repeat($less[$i], $times);
                $i++;
                continue;
            }

            $roman .= str_repeat($less[$i], $times);
            $i++;
        }

        return $roman;
    }
}

结果

Accepted
3999/3999 cases passed (20 ms)
Your runtime beats 70.13 % of php submissions
Your memory usage beats 94.81 % of php submissions (15.4 MB)

2021-11-03

leetcode: Longest Palindromic Substring

问题

Given a string s, return the longest palindromic substring in s.

代码

class Solution {

    /**
     * @param String $s
     * @return String
     */
    function longestPalindrome($s) {
        $len = strlen($s);
        if ($len === 1) {
            return $s;
        }

        if ($len === 2) {
            if ($s[0] === $s[1]) {
                return $s;
            }

            return $s[0];
        }

        $palindromic = $s[0];
        $max = 1;
        for($i = 0; $i < $len; $i++) {
            if (strlen(substr($s, $i)) < $max) {
                break;
            }
            
            for($j = $len - $i - 1; $j >= 0; $j--) {
                if ($j + 1 < $max) {
                    break;
                }

                $str = substr($s, $i, $j + 1);
                $sub = strrev($str);
                if ($sub === $str) {
                    if($max < strlen($sub)) {
                        $palindromic = $sub;
                        $max = strlen($sub);
                    }

                    break;
                }
            }
        }

        return $palindromic;
    }
}

结果

11510/11510 cases passed (90 ms)
Your runtime beats 9.13 % of php submissions
Your memory usage beats 99.87 % of php submissions (15.1 MB)