字节跳动算法面试题 I

面试/笔试题 阅读量

世上无难事只怕有心人

3.无重复字符的最长子串

LeetCode - 3.无重复字符的最长子串

解题思路: 滑动窗口

我们可以定义字符到索引的映射 当我们找到重复的字符时，我们可以立即跳过该窗口。
也就是说, 如果 str[i] 在[i,j]范围内有与i重复的字符, 我们不需要逐渐增加j;我们可以直接跳过[i, j]范围内的所有元素, 并将j变成i+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function longestSubstring($str)
{
    $len = strlen($str);
    $i = 0;
    $j = 0;
    $maxStrLen = 0;
    $set = [];
    while ($i < $len) {
        if (array_key_exists($str[$i], $set)) {
            $j = max($j, $set[$str[$i]]);
        }
        $maxStrLen = max($maxStrLen, $i - $j + 1);
        $set[$str[$i]] = $i + 1;
        $i++;
    }
    return $maxStrLen;
}

25.K个一组翻转链表

LeetCode - 25.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
function reverseKGroup($head, $k)
{
    if ($head === null) return null;

    $stack = new SplStack();
    $dumpy = new ListNode(0);
    $pre   = $dumpy;
    while (true) {
        $count = 0;
        $tmp = $head;
        while ($tmp !== null && $count < $k) {
            $stack->push($tmp);
            $tmp = $tmp->next;
            $count++;
        }
        if ($count != $k) {
            $pre->next = $head;
            break;
        }
        while (!$stack->isEmpty()) {
            $pre->next = $stack->pop();
            $pre = $pre->next;
        }

        $pre->next = $tmp;
        $head = $tmp;
    }

    return $dumpy->next;
}

15.三数之和

LeetCode - 15.三数之和

  • 解题思路: 排序 + 双指针
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
function threeSum($nums)
{
    $res = [];
    sort($nums);
    for ($i = 0; $i < count($nums); $i++) {
        if ($nums[$i] > 0) return $res;
        if ($i > 0 && $nums[$i] == $nums[$i - 1]) continue;
        $left = $i + 1;
        $right = count($nums) - 1;
        while ($left < $right) {
            $sum = $nums[$i] + $nums[$left] + $nums[$right];
            if ($sum < 0) {
                $left++;
            } elseif ($sum > 0) {
                $right--;
            } else {
                $res[] = [$nums[$i], $nums[$left], $nums[$right]];
                while ($left < $right && $nums[$left] == $nums[$left + 1]) $left++;
                while ($left < $right && $nums[$right] == $nums[$right - 1]) $right--;
                $left++;
                $right--;
            }
        }
    }
    return $res;
}

43.接雨水

LeetCode - 43.接雨水

解题思路: 双指针

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
/**
 * @param Integer[] $height
 * @return Integer
 */
function trap($height)
{
    $heightLen = sizeof($height);

    $iLeftMax  = $height[0];
    $jRightMax = $height[$heightLen-1];
    $res = 0;
    $left = 0; // 左指针
    $right = $heightLen - 1; // 右指针

    while ($left <= $right) {
        $iLeftMax  = max($height[$left], $iLeftMax);
        $jRightMax = max($height[$right], $jRightMax);
        if ($iLeftMax < $jRightMax) {
            $res += $iLeftMax - $height[$left];
            $left++; // 移动左指针
        } else {
            $res += $jRightMax-$height[$right];
            $right--; // 移动右指针
        }
    }

    return$res;
}

假设两柱子分别为 i，j。那么就有 iLeftMax, iRightMax, jLeftMx,jRightMax 这个变量。由于 j>i ，故 jLeftMax>=iLeftMax，iRightMax>=jRightMax.

那么，如果 iLeftMax>jRightMax，则必有 jLeftMax >= jRightMax，所有我们能接 j 点的水。

如果 jRightMax>iLeftMax，则必有 iRightMax >= iLeftMax，所以我们能接 i 点的水。

而上面我们实际上只用到了 iLeftMax，jRightMax 两个变量，故我们维护这两个即可

415.字符串相加

LeetCode - 415.字符串相加

解题思路: 从后向前，对应的位置的数字相加，如果结果大于 9，需要进位

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
/**
 * @param String $num1
 * @param String $num2
 * @return String
 */
function addStrings($num1, $num2)
{
    $len1 = strlen($num1);
    $len2 = strlen($num2);
    if ($len1 == 0) return $num2;
    if ($len2 == 0) return $num1;
    // 从最低位开始处理
    $i = $len1 - 1;
    $j = $len2 - 1;
    // 进位标记
    $carry = 0;
    $return = '';
    // 使用该判断条件，一次遍历处理完所有情况
    while ($i >= 0 || $j >= 0 || $carry) {
        $sum = $carry;
        if ($i >= 0) {
            $sum += substr($num1, $i, 1);
            $i--;
        }
        if ($j >= 0) {
            $sum += substr($num2, $j, 1);
            $j--;
        }
        // 进位处理
        $carry = floor($sum / 10);
        $return = $sum % 10 . $return;
    }

    return $return;
}

103.二叉树的锯齿形层次遍历

LeetCode - 103.二叉树的锯齿形层次遍历

解题思路: 利用「双端队列」的数据结构来维护当前层节点值输出的顺序。

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
/**
 * @param TreeNode $root
 * @return Integer[][]
 */
function zigzagLevelOrder($root)
{
    $query = [[$root, 1]];
    $result = [];
    if (empty($root)) {
        return $result;
    }
    while (!empty($query)) {
        [$node, $level] = array_shift($query);
        if ($node->left) {
            $query[] = [$node->left, $level + 1];
        }
        if ($node->right) {
            $query[] = [$node->right, $level + 1];
        }
        $result[$level][] = $node->val;
    }
    foreach ($result as $index => $value) {
        if ($index % 2 == 0) {
            $result[$index] = array_reverse($value);
        }
    }
    return $result;

}

121.买卖股票的最佳时机

LeetCode - 121.买卖股票的最佳时机

解题思路: 动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param Integer[] $prices   
 * @return Integer
 */
function maxProfit($prices)
{
    $dp = []; // 状态转移数组
    $dp[0][0] = 0; // 不持有股票的利润
    $dp[0][1] = -$prices[0]; // 持有股票的利润
    $pricesLen = sizeof($prices);
    if ($pricesLen ==0 ) return 0;

    for ($i = 1; $i < $pricesLen; $i++) {
        $dp[$i][0] = max($dp[$i-1][0],$dp[$i-1][1] + $prices[$i]); // 状态转移
        $dp[$i][1] = max($dp[$i-1][1], -$prices[$i]); // 状态转移
    }

    return $dp[$pricesLen-1][0];
}

206.反转链表

LeetCode - 206.反转链表

解题思路: 递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param ListNode $head
 * @return ListNode
 */
function reverseList($head)
{
    if ($head->next == null) {
        return $head;
    }
    $last = $this->reverseList($head->next);
    $head->next->next = $head;
    $head->next = null;

    return $last;
}

解题思路: 迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param ListNode $head
 * @return ListNode
 */
function reverseList($head)
{
    // 双指针
    // 我们可以申请两个指针，第一个指针叫 prev，最初是指向 null 的。
    // 第二个指针 cur 指向 head，然后不断遍历 cur。
    // 每次迭代到 cur，都将 cur 的 next 指向 pre，然后 pre 和 cur 前进一位。
    // 都迭代完了 (cur 变成 null 了)，pre 就是最后一个节点了。
    $prev = null;
    $cur = $head;
    while ($cur) {
        $next = $cur->next;
        $cur->next = $prev;
        $prev = $cur;
        $cur = $next;
    }

    return $prev;
}

1.两数之和

LeetCode - 1.两数之和

解题思路: 暴力枚举

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param array $nums
 * @param integer $target
 * @return array|int[]|string[]
 */
function twoSum($nums, $target)
{
    $length = count($nums);
    for ($i = 0; $i < $length; $i++) {
        for ($j = $i + 1; $j < $length; $j++) {
            if ($nums[$i] + $nums[$j] == $target) {
                return [$i, $j];
            }
        }
    }

    return [];
}

199.二叉树的右视图

LeetCode - 199.二叉树的右视图

解题思路: 层序队列+遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param TreeNode $root
 * @return Integer[]
 */
function rightSideView($root)
{
    if ($root === null) return [];

    $queue = new SplQueue(); // 队列
    $queue->enqueue([$root, 0]); // 节点和层序号一起入队
    $ret = []; //保存结果
    while (!$queue->isEmpty()) {
        $item = $queue->dequeue();
        $ret[$item[1]] = $item[0]->val; // 一直覆盖保存,最后就是最后边的值
        if ($item[0]->left)
            $queue->enqueue([$item[0]->left, $item[1]+1]);
        if ($item[0]->right)
            $queue->enqueue([$item[0]->right, $item[1]+1]);
    }
    return $ret;
}

160.相交链表

LeetCode - 160.相交链表

解题思路: 双指针

只有当链表 headA 和 headB 都不为空时，两个链表才可能相交。因此首先判断链表 headA 和 headB 是否为空，如果其中至少有一个链表为空，则两个链表一定不相交，返回 null。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param ListNode $headA
 * @param ListNode $headB
 * @return ListNode
 */
function getIntersectionNode($headA, $headB)
{
    // 为空判断
    if ($headA === null || $headB === null) {
        return null;
    }
    $ha = $headA;
    $hb = $headB;
    // 采用全等比较，比较地址
    while ($ha !== $hb) {
        $ha = ($ha === null) ? $headB : $ha->next;
        $hb = ($hb === null) ? $headA : $hb->next;
    }
    // 相交节点
    return $ha;
}

215.数组中的第k个最大元素

LeetCode - 215.数组中的第k个最大元素

解题思路: 暴力排序

1
2
3
4
5
function findKthLargest($nums, $k)
{
    rsort($nums);
    return $nums[$k - 1];
}

解题思路: 堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param Integer[] $nums
 * @param Integer $k
 * @return Integer
 */
function findKthLargest($nums, $k)
{
    $n = count($nums);
    $heap = new SplMinHeap();
    for ($i = 0; $i < $n; ++$i) {
        if ($heap->count() < $k) {
            $heap->insert($nums[$i]);
        } elseif ($heap->top() < $nums[$i]) {
            $heap->extract();
            $heap->insert($nums[$i]);
        }
    }
    return $heap->top();
}

232.用栈实现队列

LeetCode - 232.用栈实现队列

解题思路: 双栈模拟队列

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
<?php

class MyQueue
{
    private $queue1 = null; // 存放数据的栈
    private $queue2 = null; // 辅助栈

    public function __construct()
    {
        $this->queue1 = new SplStack();
        $this->queue2 = new SplStack();
    }

    public function push($x)
    {
        $this->queue1->push($x);
    }

    public function pop()
    {
        // pop时借助辅助栈完成
        while (true) {
            $val = $this->queue1->pop();
            if ($this->queue1->isEmpty()) {
                break;
            }
            $this->queue2->push($val);
        }
        while (!$this->queue2->isEmpty()) {
            $this->queue1->push($this->queue2->pop());
        }
        return $val;
    }

    public function peek()
    {
        return $this->queue1->bottom();
    }

    public function empty()
    {
        return $this->queue1->isEmpty();
    }
}

146.LRU缓存机制

LeetCode - 146.LRU缓存机制

解题思路: 哈希表 + 双向链表

  • 双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。
  • 哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。

53.最大子序和

LeetCode - 53. 最大子数组和

解题思路: 动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param Integer[] $nums
 * @return Integer
 */
function maxSubArray($nums)
{
    $maxNum = $nums[0];
    $tmp = $nums[0];

    foreach ($nums as $k => $v) {
        if ($k === 0) {
            continue;
        }
        if ($tmp > 0 ) {
            $tmp = $tmp + $v;
        } else {
            $tmp = $v;
        }
        $maxNum = $maxNum > $tmp ? $maxNum : $tmp;
    }

    return $maxNum;
}

155.最小栈

LeetCode - 155.最小栈

解题思路: 辅助栈
要做出这道题目，首先要理解栈结构先进后出的性质。

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
<?php

class MinStack
{
    private $stack1 = null; // 保存所有数据
    private $stack2 = null; // 保存相对较小值

    function __construct()
    {
        $this->stack1 = new SplStack();
        $this->stack2 = new SplStack();
    }

    function push($x)
    {
        $this->stack1->push($x);
        if ($this->stack2->isEmpty() || $x <= $this->stack2->top()) {
            // 压入栈2
            $this->stack2->push($x);
        }
    }

    /**
     * @return null
     */
    function pop()
    {
        $val = $this->stack1->pop();
        if ($val == $this->stack2->top()) {
            // 栈2数据弹出
            $this->stack2->pop();
        }
    }

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

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

20.有效的括号

LeetCode - 20.有效的括号

解题思路: 辅助栈

我们遍历给定的字符串 ss。当我们遇到一个左括号时，我们会期望在后续的遍历中，有一个相同类型的右括号将其闭合。由于后遇到的左括号要先闭合，因此我们可以将这个左括号放入栈顶。

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
<?php

class Solution
{
    public $str_map = [
        ')' => '(',
        '}' => '{',
        ']' => '['
    ];

    public $stack;

    function isValid($s)
    {
        // 当为空, 直接返回true
        if (empty($s)) return true;
        // 不是偶数,返回false
        if ((strlen($s) % 2) != 0) return false;
        // 定义一个栈
        $this->stack = new SplStack();
        // 分割字符串为数组
        $str_arr = str_split($s);
        foreach ($str_arr as $str) {
            // 当为左边括号时,入栈
            if (!array_key_exists($str, $this->str_map)) {
                $this->stack->push($str);
            } else {
                // 当为右边括号时,如果栈不为空且等于栈顶元素,栈顶元素出栈,否则返回false
                if (!$this->stack->isEmpty() && $this->str_map[$str] == $this->stack->top()) {
                    $this->stack->pop();
                } else {
                    return false;
                }
            }
        }
        // 判断栈是否为空,为空返回true,否则返回false
        return $this->stack->isEmpty();
    }
}

141.环形链表

LeetCode - 141.环形链表

解题思路: 快慢指针

我们定义两个指针，一快一满。慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置 head，而快指针在位置 head.next。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param ListNode $head
 * @return bool
 */
function hasCycle($head)
{
    if ($head == null) return false;

    $slow = $head;
    $fast = $head->next;
    while ($fast != null && $fast->next != null) {
        $slow = $slow->next;
        $fast = $fast->next->next;
        if ($fast === $slow) return true;
    }
    return false;
}

105.从前序与中序遍历序列构造二叉树

LeetCode - 105.从前序与中序遍历序列构造二叉树

解题思路: 递归

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
<?php

/**
 * Class Solution
 */
class Solution
{
    function buildTree($preorder, $inorder)
    {
        $len = sizeof($preorder);
        $hashmap = [];
        foreach ($inorder as $k => $v) {
            // 构建中序遍历索引查找表
            $hashmap[$v] = $k;
        }
        return $this->_buildTree($preorder, 0, $len-1, $inorder, 0, $len-1, $hashmap);
    }

    // 深度优先遍历
    function _buildTree($preorder, $preStart, $preEnd, $inorder, $inStart, $inEnd, $hashmap)
    {
        // 递归遍历
        if ($preStart->$preEnd || $inStart->$inEnd) {
            return null;
        }
        // 前序遍历
        $root = new TreeNode($preorder[$preStart]);
        $inRoot = $hashmap[$root->val];
        $numsLeft = $inRoot-$inStart;
        $root->left = $this->_buildTree($preorder, $preStart + 1, $preStart + $numsLeft,$inorder,$inStart, $inRoot-1, $hashmap);
        $root->right = $this->_buildTree($preorder, $preStart + $numsLeft + 1, $preEnd, $inorder,$inRoot+1,$inEnd, $hashmap);

        return $root;
    }
}

class TreeNode
{
    public $val = null;
    public $left = null;
    public $right = null;

    function __construct($val = 0, $left = null, $right = null)
    {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

300.最长上升子序列

LeetCode - 300.最长递增子序列

解题思路: 动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param Integer[] $nums
 * @return Integer
 */
function lengthOfLIS($nums)
{
    $numsLen = sizeof($nums);
    if ($numsLen == 0) return 0;
    $dp = array_fill(0, $numsLen, 1); // 状态转移数组
    for ($i = 1; $i < $numsLen; $i++) {
        for ($j = 0; $j < $i; $j++) {
            if ($nums[$i] > $nums[$j]) {
                $dp[$i] = max($dp[$i], 1 + $dp[$j]); // 状态转移
            }
        }
    }
    return max($dp);
}

21.合并两个有序链表

LeetCode - 21.合并两个有序链表

解题思路: 引用-迭代法

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
/**
 * @param ListNode $list1
 * @param ListNode $list2
 * @return ListNode
 */
function mergeTwoLists($l1, $l2)
{
    $dummyHead = new ListNode(null);
    $cur = $dummyHead;
    while ($l1 !== null && $l2 !== null) {
        if ($l1->val <= $l2->val) {
            $cur->next = $l1;
            $l1 = $l1->next;
        } else {
            $cur->next = $l2;
            $l2 = $l2->next;
        }
        $cur = $cur->next;
    }

    if ($l1 !== null) {
        $cur->next = $l1;
    } elseif ($l2 !== null) {
        $cur->next = $l2;
    }

    return $dummyHead->next;
}

5.最长回文子串

LeetCode - 5.最长回文子串

解题思路: 中心扩展算法

我们枚举所有的「回文中心」并尝试「扩展」，直到无法扩展为止，此时的回文串长度即为此「回文中心」下的最长回文串长度。我们对所有的长度求出最大值，即可得到最终的答案。

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
<?php

/**
 * Class Solution
 */
class Solution
{
    /**
     * @param String $s
     * @return String
     */
    function longestPalindrome($s) {
        $str_len = strlen($s);
        if ($str_len <= 1) return $s;

        $start  = 0; //开始截取位
        $offset = 0; //长度

        for ($i = 0; $i < $str_len; $i ++) {
            $len1 = $this->centerExpand($s, $str_len, $i, $i);
            $len2 = $this->centerExpand($s, $str_len, $i, $i + 1);

            if ($len1 > $len2 && $len1 > $offset) {
                // 开始位置 = 当前坐标-回文长度的一半位置
                $start = $i - ($len1 - 1)/2;
                $offset = $len1;
            }

            if ($len1 <= $len2 && $len2 > $offset) {
                // 开始位置 = 回文长度的一半位置
                $start = $i - $len2/2 + 1;
                $offset = $len2;
            }
        }
        return substr($s, $start, $offset);
    }

    // 中心扩散
    function centerExpand($str, $len, $left, $right)
    {
        while ( $left >= 0 && $right < $len && $str[$left] == $str[$right] ) {
            $right ++;
            $left --;
        }
        return $right - $left - 1;
    }
}

236.二叉树的最近公共祖先

LeetCode - 236.二叉树的最近公共祖先

解题思路: 递归遍历
因为我们是自底向上从叶子节点开始更新的，所以在所有满足条件的公共祖先中一定是深度最大的祖先先被访问到

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
<?php

class Solution
{
    /**
     * 深度优先遍历
     * @param TreeNode $root
     * @param TreeNode $p
     * @param TreeNode $q
     * @return TreeNode
     */
    function lowestCommonAncestor($root, $p, $q)
    {
        if ($root == null) { //递归结束
            return null;
        }
        if ($root === $p || $root === $q) { //递归结束
            return $root;
        }

        $left  = $this->lowestCommonAncestor($root->left, $p, $q);
        $right = $this->lowestCommonAncestor($root->right, $p, $q);
        if ($left != null && $right != null) { //第一种情况
            return $root;
        }

        if ($left == null && $right == null) { //第二种情况
            return null;
        }

        return $left == null ? $right : $left; //第三种情况
    }
}

class TreeNode
{
    public $val = null;
    public $left = null;
    public $right = null;
    function __construct($value) { $this->val = $value; }
 }

151.翻转字符串里的单词

LeetCode - 151.翻转字符串里的单词

解题思路: 使用语言特性
split(拆分), reverse(反转), join连接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * @param String $s
 * @return String
 */
function reverseWords($s)
{
    $sArr = explode(' ', $s);
    $res = '';
    foreach($sArr as $str) {
        if ($str === '') continue;
        $res = $str . ' ' . $res;
    }
    return trim($res);
}

101.对称二叉树

LeetCode - 101.对称二叉树

解题思路: 递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution 
{
    public function isSymmetric($root) 
    {
        return $this->check($root, $root);
    }

    private function check($left, $right)
    {
        if ($left === null && $right === null) return true;
        if ($left === null || $right === null) return false;
        if ($left->val !== $right->val) return false;
        
        return $this->check($left->left, $right->right)
            && $this->check($left->right, $right->left); 
    }
}

200.岛屿数量

LeetCode - 200.岛屿数量

解题思路: 深度优先遍历DFS

先遍历，查到的第一个陆地标记为2，开始深度搜索，查找周围的陆地，如果有就标记为2，全部标记完成以后就找到了一块陆地，下次再找到1则是第二块陆地了。

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
class Solution
{
    /**
     * @param String[][] $grid
     * @return Integer
     */
    function numIslands($grid)
    {
        $num = 0;
        foreach ($grid as $y => &$row) {
            foreach ($row as $x => &$cell) {
                if ($cell == 1) {
                    $this->flipIslands($grid, $y, $x);
                    $num ++;
                }
            }
        }
        return $num;
    }

    function flipIslands(&$grid, $y, $x)
    {
        if (isset($grid[$y][$x]) && $grid[$y][$x] == 1) {
            $grid[$y][$x] = 2;
            if (isset($grid[$y][$x+1]) && $grid[$y][$x+1] == 1) {
                $this->flipIslands($grid, $y, $x+1);
            }
            if (isset($grid[$y][$x-1]) && $grid[$y][$x-1] == 1) {
                $this->flipIslands($grid, $y, $x-1);
            }
            if (isset($grid[$y+1][$x]) && $grid[$y+1][$x] == 1) {
                $this->flipIslands($grid, $y+1, $x);
            }
            if (isset($grid[$y-1][$x]) && $grid[$y-1][$x] == 1) {
                $this->flipIslands($grid, $y-1, $x);
            }
        }
    }
}

解题思路: 广度优先遍历BFS

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
class Solution
{
    /**
     * @param String[][] $grid
     * @return Integer
     */
    function numIslands($grid)
    {
        $rows = count($grid);
        if ($rows == 0) return 0;
        $cols = count($grid[0]);
        $count = 0;
        // 四个方向数组
        $directions = [[-1, 0], [0, -1], [1, 0], [0, 1]];
        // 辅助队列
        $queue = new SplQueue();
        // 访问数组
        $visited = array_fill(0, $rows, array_fill(0, $cols, false));
        for ($i = 0; $i < $rows; ++$i) {
            for ($j = 0; $j < $cols; ++$j) {
                if (!$visited[$i][$j] && $grid[$i][$j] == '1') {
                    $count++;
                    $visited[$i][$j] = true;
                    $queue->enqueue($i * $cols + $j);
                    while ($queue->count()) {
                        $cur = $queue->dequeue();
                        $x = (int) ($cur / $cols);
                        $y = $cur % $cols;
                        for ($k = 0; $k < 4; ++$k) {
                            $newX = $x + $directions[$k][0];
                            $newY = $y + $directions[$k][1];
                            if ($this->inArea($newX, $newY, $grid)
                                && !$visited[$newX][$newY]
                                && $grid[$newX][$newY] == '1'
                            ) {
                                $visited[$newX][$newY] = true;
                                $queue->enqueue($newX * $cols + $newY);
                            }
                        }
                    }
                }
            }
        }
        return $count;
    }

    private function inArea($x, $y, $grid) 
    {
        if ($x < 0 || $y < 0) return false;
        if ($x >= count($grid) || $y >= count($grid[0])) return false;

        return true;
    }
}

46.全排列

LeetCode - 46.全排列

解题思路: 回溯算法

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
<?php

/**
 * Class Solution
 */
class Solution
{
    /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function permute($nums) // 深度优先遍历
    {
        $numsLen = sizeof($nums);
        if ($numsLen == 0) return []; // 递归结束
        if ($numsLen == 1) return [$nums]; // 递归结束
        $ret = [];
        foreach ($nums as $key => $num) {
            $tempNums = $nums;
            unset($nums[$key]);
            $res = $this->permute($nums); // 递归
            $nums = $tempNums;
            // 处理返回结果
            foreach ($res as $v) {
                array_unshift($v, $num);
                $ret[] = $v;
            }
        }
        return $ret;
    }
}

198.打家劫舍

LeetCode - 198.打家劫舍

解题思路: 动态规划

小偷挑选要偷的房子，且不能偷相邻的两栋房子，方案无非两种:

  • 方案一：挑选的房子中包含最后一栋；
  • 方案二：挑选的房子中不包含最后一栋；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param Integer[] $nums
 * @return Integer
 */
function rob($nums)
{
    $n = count($nums);
    if ($n == 0) return 0;
    if ($n == 1) reset($nums);
    if ($n == 2) return max($nums);

    // dp 数组定义：当前有 i 个房屋，第 i 个房屋偷和不偷可以获取的最大数值
    // 状态转移方程： dp[i] = max(dp[i-1], dp[i-2] + nums[i])
    $dp = [];
    $dp[0] = reset($nums);
    $dp[1] = max($nums[0], $nums[1]);
    for ($i = 2; $i < $n; ++$i) {
        $dp[$i] = max($dp[$i - 1], $dp[$i - 2] + $nums[$i]);
    }
    return $dp[$n - 1];
}

54.螺旋矩阵

LeetCode - 54.螺旋矩阵

解题思路: 按层模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param Integer[][] $matrix
 * @return Integer[]
 */
function spiralOrder($matrix)
{
    $ans = [];
    $u = $l = 0;
    $d = count($matrix) - 1;
    if ($d < 0) return $ans;
    $r = count($matrix[0]) - 1;
    while (true) {
        for ($i = $l; $i <= $r; ++$i) $ans[] = $matrix[$u][$i];
        if (++$u > $d) break;
        for ($i = $u; $i <= $d; ++$i) $ans[] = $matrix[$i][$r];
        if (--$r < $l) break;
        for ($i = $r; $i >= $l; --$i) $ans[] = $matrix[$d][$i];
        if (--$d < $u) break;
        for ($i = $d; $i >= $u; --$i) $ans[] = $matrix[$i][$l];
        if (++$l > $r) break;
    }
    return $ans;
}

98.验证二叉搜索树

LeetCode - 98.验证二叉搜索树

解题思路: 中序遍历

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 TreeNode $root
     * @return Boolean
     */
    function isValidBST($root)
    {
        $res = [];
        $this->dfs($root, $res);
        $len = sizeof($res);
        for ($i = 1; $i < $len; $i++){//判断是否是一个升序数组，且没重复元素
            if ($res[$i] <= $res[$i-1])
                return false;
        }        

        return true;
    }

    //中序遍历
    function dfs($root, &$out) // 深度优先遍历
    {
        if ($root == null) //递归终止
            return;
        $this->dfs($root->left, $out);
        $out[] = $root->val;
        $this->dfs($root->right, $out);
    }
}

69.x的平方根

LeetCode - 69.x的平方根

解题思路: 二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param Integer $x
 * @return Integer
 */
function mySqrt($x) {
    if ($x <= 1) return $x;
    $l = 1;
    $r = floor($x / 2) + 1;
    while ($l < $r) {
        // 取右中位数，否则会死循环
        $mid = $l + floor(($r - $l + 1) / 2);
        if ($mid == $x / $mid) return $mid;
        if ($mid < $x / $mid) {
            $l = $mid;
        } else {
            $r = $mid - 1;
        }
    }

    return $l;
}

113.路径总和II

LeetCode - 113.路径总和II

解题思路: DFS 深度优先遍历

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 
{
    protected $ans = [];
    public function pathSum($root, $sum) 
    {
        $this->dfs($root, $sum, []);    
        return $this->ans;
    }

    private function dfs($root, $sum, $path)
    {
        if ($root === null) return;
        $path[] = $root->val;
        // 遍历到叶子节点，终止
        if ($root->left === null && $root->right === null) {
            if ($root->val === $sum) {
                $this->ans[] = $path;
                return;
            }
        }

        $this->dfs($root->left, $sum - $root->val, $path);
        $this->dfs($root->right, $sum - $root->val, $path);
    }
}

165.比较版本号

LeetCode - 165.比较版本号

解题思路: 字符串分割
注意根据题目要求，如果版本号不存在某个下标处的修订号，则该修订号视为 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
32
33
34
35
36
37
38
/**
 * @param String $version1
 * @param String $version2
 * @return Integer
 */
function compareVersion($version1, $version2)
{
    $arr1 = explode('.', $version1);
    $arr2 = explode('.', $version2);

    $cnt1 = count($arr1);
    $cnt2 = count($arr2);

    if ($cnt1 > $cnt2) {
        $diff = $cnt1 - $cnt2;
        for ($i = 0; $i < $diff; $i++) {
            array_push($arr2, 0);
        }
    } elseif ($cnt1 < $cnt2) {
        $diff = $cnt2 - $cnt1;
        for ($i = 0; $i < $diff; $i++) {
            array_push($arr1, 0);
        }
    }

    $cnt1 = count($arr1);

    for ($i = 0; $i < $cnt1; $i++) {
        $v1 = intval($arr1[$i]);
        $v2 = intval($arr2[$i]);

        if ($v1 != $v2) {
            return $v1 > $v2 ? 1 : -1;
        }
    }

    return 0;
}

链表中倒数第k个节点

LeetCode - 剑指 Offer 22. 链表中倒数第k个节点

解题思路: 双指针
提前指针从头节点，先走(k-1)步，落后指针随后一起走，当提前指针到达链表尾端时，落后节点刚好落在倒数第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
  /**
   * @param ListNode $head
   * @param Integer $k
   * @return ListNode
   */
  function getKthFromEnd($head, $k)
  {
      // 边界情况处理，从而提高代码的健壮性
if ($head == null || $k == 0) {
	return null;
}

$aheadNode = $head;
$behindNode = $head;

// aheadNode 提前节点先走k步
for ($i = 0; $i < $k - 1; $i++) {
	if ($aheadNode->next != null) {
		$aheadNode = $aheadNode->next;
	} else {
		return null; // 链表中没有足够的k个节点
	}
}
// 提前和落后指针一起走
while ($aheadNode->next != null) {
	$aheadNode = $aheadNode->next;
	$behindNode = $behindNode->next;
}
      $head = $behindNode;
      return $head;
  }

92.反转链表II

LeetCode - 92.反转链表II

解题思路: 一次遍历「穿针引线」反转链表（头插法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @param ListNode $head
 * @param Integer $m
 * @param Integer $n
 * @return ListNode
 */
function reverseBetween($head, $m, $n) 
{
    $dummy = new ListNode(0);
    $dummy->next = $head;
    $pre = $dummy;
    for ($i = 1; $i < $m; $i++) {
        $pre = $pre->next;
    }
    $head = $pre->next;
    for ($i = $m; $i < $n; $i++) {
        $nex = $head->next;
        $head->next = $nex->next;
        $nex->next = $pre->next;
        $pre->next = $nex;
    }
    
    return $dummy->next;
}

234.回文链表

LeetCode - 234.回文链表

解题思路: 双指针

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
/**
 * @param ListNode $head
 * @return Boolean
 */
function isPalindrome($head)
{
    $len = 0;
    $p = $head;
    while($p) {//计算链表长度
        $len++;
        $p = $p->next;
    }
    $mid = floor($len / 2); //中间值
    $prev = null;
    $p = $head;
    $q = $head;
    $i = 0;        
    while($i < $mid) {
        // 将mid值之前的节点的next指针都翻转
        $q = $q->next;
        $p->next = $prev;            
        $prev = $p;
        $p = $q;            
        $i++;                           
    }
    if ($len%2 != 0) { //元素奇偶个数判断
        $q = $q->next;
    }
    while($prev) { //前后指针prev和q同时移动判断            
        if ($prev->val != $q->val)
            return false;
        $prev = $prev->next;
        $q = $q->next;
    }

    return true;
}

169.多数元素

LeetCode - 169.多数元素

解题思路: 取排序后的数组中间元素即可

1
2
3
4
5
function majorityElement($nums)
{
    sort($nums);
    return $nums[floor(count($nums) / 2)];
}

解题思路: 哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * @param Integer[] $nums
 * @return Integer
 */
function majorityElement($nums)
{
    // hash table
    $hash = [];
    foreach ($nums as $num) {
        if (!isset($hash[$num])) $hash[$num] = 0;
        $hash[$num]++;
    }
    return array_search(max($hash), $hash);
}

470.用rand7()实现rand10()

LeetCode - 470.用rand7()实现rand10()

解题思路: 拒绝采样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param 
 * @return Integer
 */
function rand10()
{
     while (true) {
        $row = rand7();
        $col = rand7();
        $idx = ($row - 1) * 7 + $col;
        if ($idx <= 40) {
            return 1 + ($idx - 1) % 10;
        }
    }
}

41.缺失的第一个正数

LeetCode - 41.缺失的第一个正数

解题思路: 哈希表

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
/**
 * @param Integer[] $nums
 * @return Integer
 */
function firstMissingPositive($nums)
{
    $n = count($nums);
    if (!in_array(1, $nums)) {
        return 1;
    }
    for ($i = 0; $i <= $n; $i++) {
        if ($nums[$i] <= 0 || $nums[$i] > $n) {
            $nums[$i] = 1;
        }
    }
    for ($i = 0; $i < $n; $i++) {
        $a = abs($nums[$i]) - 1;
        $nums[$a] = - abs($nums[$a]);
    }
    for ($i = 0; $i < $n; $i++) {
        if ($nums[$i] > 0) {
            return $i + 1;
        }
    }
    return $i + 1;

}

142.环形链表II

LeetCode - 142.环形链表II

解题思路: 快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param ListNode $head
 * @return ListNode
 */
function detectCycle($head)
{
    $fast = $slow = $head;
    while (true) {
        if ($fast === null || $fast->next === null) return null;
        $fast = $fast->next->next;
        $slow = $slow->next;
        if ($fast === $slow) break;
    }

    $fast = $head;
    while ($fast !== $slow) {
        $fast = $fast->next;
        $slow = $slow->next;
    }
    return $fast;
}

PHP Fatal error: Nesting level too deep - recursive dependency? in solution.php

240.搜索二维码矩阵II

LeetCode - 240.搜索二维码矩阵II

解题思路: Z 字形查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @param Integer[][] $matrix
 * @param Integer $target
 * @return Boolean
 */
function searchMatrix($matrix, $target)
{
    $m = count($matrix); //行
    $n = count($matrix[0]); //列

    $x = 0; //初始第一行
    $y = $n - 1; //最后一列

    while ($x < $m && $y >= 0) {
        if ($matrix[$x][$y] === $target) {
            return true;
        } elseif ($matrix[$x][$y] > $target) {//左移一列
            $y--;
        } else { //下移一行;
            $x++;
        }
    }
    return false;
}

23.合并k个升序链表

LeetCode - 23.合并k个升序链表

解题思路: 最小堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param ListNode[] $lists
 * @return ListNode
 */
function mergeKLists($lists)
{
    if (empty($lists)) return [];
    $dummyHead = new ListNode(null); // 虚拟头结点
    $p = $dummyHead;      
    $heap = new SplMinHeap(); // 最小堆
    foreach ($lists as $item) {                           
        while ($item) {
            $heap->insert($item->val); // 加入堆中
            $item = $item->next;
        }
    }             
    while (!$heap->isEmpty()) { // 依次拿出所有数据       
        $p->next = new ListNode($heap->extract());
        $p=$p->next;
    }              
           
    return $dummyHead->next; // 返回结果
}

88.合并两个有序数组

LeetCode - 88.合并两个有序数组

解题思路: 直接合并后排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param Integer[] $nums1
 * @param Integer $m
 * @param Integer[] $nums2
 * @param Integer $n
 * @return NULL
 */
function merge(&$nums1, $m, $nums2, $n)
{
    for ($i = 0; $i < $n; $i++) {
        $nums1[$m + $i] = $nums2[$i];
    }
    sort($nums1);
    
    return $nums1;
}

79.单词搜索

LeetCode - 79.单词搜索

解题思路: 回溯算法

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
65
class Solution 
{
    public $mark = [];
    public $board = [];
    public $direct = [[0, 1], [0, -1], [1, 0], [-1, 0]];
    public $m = 0;
    public $n = 0;

    /**
     * @param String[][] $board
     * @param String $word
     * @return Boolean
     */
    function exist($board, $word)
    {
        // 回溯算法
        if (!$board) {
            return false;
        }
        $this->board = $board;
        $m = $this->m = count($board);
        $n = $this->n = count($board[0]);
        for ($i = 0; $i < $m; $i++) {
            for ($j = 0; $j < $n; $j++) {
                $this->mark[$i][$j] = 0;
            }
        }
        for ($i = 0; $i < $m; $i++) {
            for ($j = 0; $j < $n; $j++) {
                if ($board[$i][$j] == $word[0]) {// 首次匹配
                    $this->mark[$i][$j] = 1;
                    if ($this->backtrace($i, $j, substr($word, 1))) {
                        return true;
                    } else {
                        $this->mark[$i][$j] = 0;
                    }
                }
            }
        }
        return false;
    }

    function backtrace($i, $j, $word)
    {
        if (strlen($word) == 0) {
            return true;
        }
        foreach ($this->direct as $direct) {
            $_i = $i + $direct[0];
            $_j = $j + $direct[1];
            if ($_i >= 0 && $_j >= 0 && $_i < $this->m && $_j < $this->n && $this->board[$_i][$_j] == $word[0]) {
                if ($this->mark[$_i][$_j] == 1) {
                    continue;
                }
                $this->mark[$_i][$_j] = 1;
                if ($this->backtrace($_i, $_j, substr($word, 1))) {
                    return true;
                } else {
                    $this->mark[$_i][$_j] = 0;
                }
            }
        }
        return false;
    }
}

114.二叉树展开为链表

LeetCode - 114.二叉树展开为链表

解题思路: 前序遍历
操作原有$root变量，使得所有子树节点都变成右子树的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution
{
    /**
     * @param TreeNode $root
     * @return NULL
     */
    function flatten($root)
    {
        while ($root != null) {
            if ($root->left == null) {
                $root = $root->right;
            } else {
                $pre = $root->left;
                while ($pre->right != null) {
                    $pre = $pre->right;
                }
                $pre->right = $root->right;
                $root->right = $root->left;
                $root->left = null;
                $root = $root->right;
            }
        }
    }
}

239.滑动窗口最大值

LeetCode - 239.滑动窗口最大值

解题思路: 单调递减队列

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
class Solution
{
    /**
     * @param Integer[] $nums
     * @param Integer $k
     * @return Integer[]
     */
    function maxSlidingWindow($nums, $k)
    {
        $res = [];
        $queue = new MyQueue;
        // 前k个元素入列 
        for ($i = 0; $i < $k; $i++) { 
            $queue->push($nums[$i]);
        }
        // 记录前k的元素的最大值
        $res[] = $queue->top();
        for ($i = $k; $i < count($nums); $i++) {
            $queue->pop($nums[$i - $k]); // 窗口最左端的元素出列
            $queue->push($nums[$i]);     // 窗口最右端的元素入列
            $res[] = $queue->top();
        }

        return $res;
    }
}

/**
 * 单调递减队列
 */
class MyQueue
{
    private $queue;
    function __construct()
    {
        $this->queue = new SplQueue;
    }

    // 进一个新元素如果比入口元素大，要将入口元素弹出，直到新元素比入口元素小
    function push($val) 
    {
        while (!$this->queue->isEmpty() && $val > $this->queue->top()) {
            $this->queue->pop(); // 入口元素弹出
        }
        $this->queue->enqueue($val);
    }

    // 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。
    function pop($val) 
    {
        if (!$this->queue->isEmpty() && $this->queue->bottom() == $val) {
            $this->queue->dequeue();
        }
    }

    function top()
    {
        return $this->queue->bottom();
    }
}

34.在排序数组中查找元素的第一个和最后一个位置

LeetCode - 34.在排序数组中查找元素的第一个和最后一个位置

解题思路: 二分查找

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
function searchRange($nums, $target) 
{
    $n = count($nums);
    if ($n === 0 || $target < $nums[0] || $target > end($nums)) return [-1, -1];

    $left = 0;
    $right = $n - 1;
    // 循环终止条件是 left=right
    while ($left < $right) {
        // left=mid 时需要上取整
        $mid = $left + floor(($right - $left) / 2);
        // 找到把 mid 排除掉的方法
        if ($nums[$mid] < $target) {
            // 目标值可能位于区间 [mid+1, right]
            $left = $mid + 1;
        } else {
            // 目标值可能位于 [left, mid]
            $right = $mid;
        }
    }

    if ($nums[$left] !== $target) return [-1, -1];
    if ($l === $n - 1) return [$l, $l];
    $l = $left;

    // 最后一个 (区间下边界可以收缩)
    $left = $l;
    $right = $n - 1;
    // 循环终止条件是 left=right
    while ($left < $right) {
        // left=mid 时需要上取整
        $mid = $left + floor(($right - $left + 1) / 2);
        if ($nums[$mid] > $target) {
            // 目标值可能位于 [left, mid-1]
            $right = $mid - 1;
        } else {
            // 目标值可能位于区间 [mid, right]
            $left = $mid;
        }
    }
    
    return [$l, $left];
}

739.每日温度

LeetCode - 739.每日温度

解题思路: 正向遍历，最小栈解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution
{
    function dailyTemperatures($T)
    {
        $n = count($T);
        $ans = array_fill(0, $n, 0);
        if ($n == 0) return $ans;
        $stack = new SplStack();
        for ($i = 0; $i < $n; ++$i) {
            while (!$stack->isEmpty() && $T[$stack->top()] < $T[$i]) {
                // 出栈
                $top = $stack->pop();
                $ans[$top] = $i - $top;
            }

            $stack->push($i);
        }
        return $ans;
    }
}

解题思路: 逆向遍历，最大栈解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution
{
    function dailyTemperatures($T)
    {
        $n = count($T);
        $ans = array_fill(0, $n, 0);
        if ($n == 0) return $ans;
        $stack = new SplStack();
        for ($i = $n - 1; $i >= 0; --$i) {
            while (!$stack->isEmpty() && $T[$stack->top()] <= $T[$i]) {
                $stack->pop();
            }
            
            $ans[$i] = $stack->isEmpty() ? 0 : $stack->top() - $i;
            $stack->push($i); // 下标入栈
        }
        
        return $ans;
    }
}

287. 寻找重复数

LeetCode - 287. 寻找重复数

解题思路: 双指针
类似双指针的解法，但直接在原数组上标记，将已访问过的数组值置为0，在第二次访问到的时候可以直接返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param Integer[] $nums
 * @return Integer
 */
function findDuplicate($nums)
{
    //取第一个数作为起点开始，实际上随机取一个也是可以的，不一定要从0开始
    $index = 0;
    //题目已经限定了，数组内所有值都在[1,n]之间，不可能出现0或者负数
    while ($nums[$index] > 0) {
        //将数组的值作为下一个坐标，并将当前值改为0，如果下一次访问到的时候就知道是第二次访问
        $next = $nums[$index];
        $nums[$index] = 0;
        $index = $next;
    }
    return $index;
}

参考

Powered by Hexo and Hexo-theme-hiker

Copyright © 2017 - 2023 Keep It Simple And Stupid All Rights Reserved.

访客数 : | 访问量 :