LeetCode练习

发表于 不明生物：

本文记录LeetCode练习。

算法

两数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
    function twoSum($nums, $target) {
        if(is_array($nums)){ 
            foreach($nums as $k1=>$v){
                $offset = $target-$v;
                $k2 = array_search($offset,$nums);
                if(false !== $k2 && $k1!=$k2){
                    return [$k1,$k2];
                } 
            }
        }
        return [];
    }
}

两数相加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val) { $this->val = $val; }
 * }
 */
class Solution {

    /**
     * @param ListNode $l1
     * @param ListNode $l2
     * @return ListNode
     */
    function addTwoNumbers($l1, $l2) {
        
        $node = new ListNode(0);
        
        $out = 0;// 上一次进位
        
        $header = $node;// 头结点
        
        while($l1 || $l2){
            
            $x  = $l1->val ?? 0;
            
            $y  = $l2->val ?? 0;
            
            $sum  = $x + $y + $out;
            
            $val = intval($sum % 10);
            
            // 下一次进位
            $out = intval($sum / 10);
            
            // 构建下一个结点
            $node->next = new ListNode($val); 
                           
            // 指针移到下一个结点
            $node = $node->next;
    
            $l1 = $l1->next ?? null;
            $l2 = $l2->next ?? null;
        }
        // 最后一个计算溢位
        if($out > 0){
          $node->next = new ListNode($out); 
        }
        
        return $header->next;
    }
}

最大数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution { 
    /**
     * @param Integer[] $nums
     * @return String
     */
    function largestNumber($nums) {
     
       if (!is_array($nums)) return ''; 
        $len = count($nums);
        for ($i = 0; $i < $len; $i++) {
            for ($j = $i + 1; $j < $len; $j++) {
               
                if ( $nums[$i] . $nums[$j] <  $nums[$j] . $nums[$i] ) {
                    
                    $_tmp = $nums[$i];
                    $nums[$i] = $nums[$j];
                    $nums[$j] = $_tmp;
                
                }
            }
        }
        $ret =  implode($nums);
        return empty($ret[0]) ? '0' : $ret;
    }
}

无重复字符的最长子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {

    /**
     * @param String $s
     * @return Integer
     */
    function lengthOfLongestSubstring($s) {
        
        $len = strlen($s);
        
        $p = 0;
        
        $_tmp = ""; 
        
        $max = 0;
        
        while($p < $len){ 
           
           $target = $s[$p];
           
           $pos = strpos($_tmp,$target);
            
           if (false !== $pos) {

                $c = strlen($_tmp); 
               
                $t =  $pos;
               
                $_tmp = substr($_tmp, $t-$c+1,$c-$t-1);  
           }
      
           $_tmp .= $target;
            
           $c = strlen($_tmp); 
            
           if( $c > $max ) {
                $max = $c;
           } 
           $p++;
        }  
        return $max;
    }
}

寻找两个有序数组的中位数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {

    /**
     * @param Integer[] $nums1
     * @param Integer[] $nums2
     * @return Float
     */
    function findMedianSortedArrays($nums1, $nums2) {

        // define recursive function
        $recursive = function (array $nums1, int $i, array $nums2, int $j, int $k) use (&$recursive) {
            if (!isset($nums1[$i]))
                return $nums2[$j + $k - 1];//nums1为空数组
            if (!isset($nums2[$j]))
                return $nums1[$i + $k - 1];//nums2为空数组
            if ($k == 1)// 最后一次递归
                return min($nums1[$i], $nums2[$j]);

            $k2 = intval($k / 2);

            $midVal1 = $nums1[$i + $k2 - 1] ?? PHP_INT_MAX;
            $midVal2 = $nums2[$j + $k2 - 1] ?? PHP_INT_MAX;

            if ($midVal1 < $midVal2) {
                return $recursive($nums1, $i + $k2, $nums2, $j, $k - $k2);
            } else {
                return $recursive($nums1, $i, $nums2, $j + $k2, $k - $k2);
            }
        };

        // calc
        $len = count($nums1) + count($nums2);
        $left = $recursive($nums1, 0, $nums2, 0, intval($len + 1) / 2);
        $right = $recursive($nums1, 0, $nums2, 0, intval($len + 2) / 2);
        return ($left + $right) / 2.0;
    } 

}

最长回文子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution { 
    /**
     * @param String $s
     * @return String
     */
    function longestPalindrome($str) {
        $len = strlen($str);
        $hlen = 1;
        $start = 0;
        for ($i = 0; $i < $len; $i++) {
            $l = $h = $i;
            // 下面两个while只可能有一个执行
            while ($h < $len - 1 && $str[$l] == $str[$h + 1]) {// 非中心对称
                $h++;
            }
            while (
                $l > 0 && $h < $len - 1 // 边界
                && $str[$l - 1] == $str[$h + 1]//  中心对称
            ) {
                $l--;
                $h++;
            }
            $max = $h - $l + 1;
            if ($hlen < $max) {
                $hlen = $max;
                $start = $l;
            } 
        } 
        return substr($str, $start, $hlen);
    }
}

Z 字形变换

思路分析：

以 row = 5 为例，

1
2
3
4
5
1       9        17        25          33
2    8 10     16 18     24 26       32 34
3  7   11   15   19   23   27    31    35
4 6    12 14     20 22     28 30       36
5      13        21        29          37

取出竖列

k(第K行)\i(第i列) 1 2 3 4 5
1 1 9 17 25 33
2 2 10 18 26 34
3 3 11 19 27 35
4 4 12 20 28 36
5 5 13 21 29 37

可以得到竖列取值的规律:

  • 当 row != 1 时, m = k+2(i-1)(n-1),
  • 当 row = 1 时, m = i.

其中 k ： 层级， i ： 列数，n ： 行数, m：对应竖列上的值

分析每个数列中间值关系

i k ans
2 1 m+8
2 2 m+6
2 3 m+4
2 4 m+2
2 5 m+0
* * *
i’ n m+2(n-k) 中间值ans看着像和i是无关的，事实上是有关的，别忘了m的取值

得出结论，中间值的规律：

  • ans = m+2(n-k)

算法实现如下 : 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution
{
    function convert($str, $n)
    {
        $k = 1;
        $tmp = '';
        if ($n == 1) {
            $tmp = $str;
        } else {
            $strlen = strlen($str);
            while ($k <= $n) {
                $i = 1;
                $f = $n - $k;
                while ($i <= $strlen) {
                    $m = $k + 2 * ($i - 1) * ($n - 1);
                    $ans = $m + 2 * $f;
                    if (empty($str[$m - 1]))
                        break;
                    $tmp .= $str[$m - 1];
                    if ($f > 0 && $f < $n - 1 && !empty($str[$ans - 1])) {
                        $tmp .= $str[$ans - 1];
                    }
                    $i++;

                }
                $k++;
            }
        }
        return $tmp;
    }
}

整数反转

法一: 栈思想

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {

    /**
     * @param Integer $x
     * @return Integer
     */ 
    function reverse($x)
    {
        $rev = 0;
        $max = (1 << 31) - 1;// 最大值
        $min = -1 << 31;// 最小值
        if ($x > $max || $x < $min) return 0;// 参数是否超出 
        while ($x != 0) {
            
            $pop = $x % 10; // 取最后一位数

            $x = intval($x / 10);// 降位
            
            // 越界判断
            if ($rev > $max / 10 || ($rev == $max / 10 && $pop > $max % 10)) return 0; // 正数
            if ($rev < $min / 10 || ($rev == $min / 10 && $pop < $min % 10)) return 0; // 负数
            
            // 逆序升位
            $rev = $rev * 10 + $pop;
        }
        return $rev;
    } 
 
}

法二: 字符串反转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {

    /**
     * @param Integer $x
     * @return Integer
     */ 
    function reverse($x)
    {
        $max = (1 << 31) - 1;// 最大值
        $min = -1 << 31;// 最小值

        if ($x > $max || $x < $min) return 0;// 参数是否超出 

        $is_negative = $x < 0 ? true : false; // 正负判断

        $x = $is_negative ? -$x : $x; // 转成整数

        $x = '' . $x; // 转换成字符串 

        $rev_str = $is_negative? '-' : '' ; // 保留符号

        for ($len = strlen($x), $i = $len - 1; $i >= 0; $i--) { // 逆转字符
            $rev_str .= $x[$i];
        }

        // 判断是否越界输出
        return -1 == $this->int_str_compare($rev_str, $is_negative ? $min : $max) ?  intval($rev_str) : 0;
    }

    //
    // 数字字符串大小比较( 虽然 -1 > -2,但是此处不考虑负数，所以 -1 < -2)
    //
    //  -1 表示 str1 < str2
    //   0 表示 str1 = str2
    //   1 表示 str1 > str2
    //
    function int_str_compare($str1, $str2)
    {
        $len1 = strlen($str1 = '' . $str1);
        $len2 = strlen($str2 = '' . $str2);
        
        // 长度对齐
        if ($len1 > $len2) {
            $str2 = str_pad($str2, $len1, '0', STR_PAD_LEFT);
        } else {
            $str1 = str_pad($str1, $len2, '0', STR_PAD_LEFT);
        }

        $compare = 0;// 大小比较
        for ($i = 0, $len = strlen($str1); $i < $len; $i++) {
            $f = intval($str1[$i]) - intval($str2[$i]); // 数字的每一位长度肯定不会超出0-9的范围，所以肯定不会超出
            if ($f > 0) {
                $compare = 1;
                break;// 有一个比它大就全部比它大
            } elseif ($f < 0) {
                $compare = -1;
                break;// 有一个比它小就全部比它小
            } else {
                $compare = 0;// 相等的话就继续比较下一位，直到最后以为相等才能说明str1等于str2
            }
        } 
        return $compare;
    } 
}

SQL架构

第二高的薪水

1
select (select distinct(Salary) from Employee order by Salary DESC limit 1 offset 1) as SecondHighestSalary

第N高的薪水

1
2
3
4
5
6
7
CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT
BEGIN
  SET N=N-1;
  RETURN (
      select (select distinct(Salary) from Employee order by Salary DESC limit 1 offset N) as getNthHighestSalary
  );
END

分数排名

1
SELECT a.Score,(select count(distinct(b.Score)) from Scores as b where b.Score>a.Score)+1 as Rank FROM Scores as a ORDER BY Score DESC

连续出现的数字

1
2
3
4
5
6
7
8
9
10
select distinct Num as ConsecutiveNums
from (
  select Num, 
    case 
      when @prev = Num then @count := @count + 1
      when (@prev := Num) is not null then @count := 1
    end as CNT
  from Logs, (select @prev := null,@count := null) as t
) as temp
where temp.CNT >= 3

不懂自定义变量的同学可以参考mysql中的用户变量

关注作者公众号,获取更多资源!
赏作者一杯咖啡~