每日算法 1

算法题 阅读量

知耻而后勇, 日积月累, 每月一篇博客
以下内容, 记录自己刷题过程

720. 词典中最长的单词

LeetCode - 720. 词典中最长的单词

  • 2022/03/17

解题思路: 字符串排序 + 哈希集合

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
class Solution
{
    /**
     * @param String[] $words
     * @return String
     */
    function longestWord($words): String
    {
        // 按字符串长度排序
        usort($words, function ($i, $j) {
            if (strlen($i) != strlen($j)) {
                return strlen($i) - strlen($j);
            }
            // 字典序小的在前面
            return  $i > $j ? -1 : 1;
        });
        $longest = "";
        $hashset = []; // 哈希集合
        $hashset[] = ""; // 将数组转成哈希集合
        foreach ($words as $word) {
            // 判断当前单词去掉最后一个字母之后的前缀是否在哈希集合中
            if (in_array(substr($word, 0, strlen($word) - 1), $hashset)) {
                $longest = $word;
                $hashset[] = $word;
            }
        }

        return $longest;
    }
}

2043. 简易银行系统

LeetCode - 2043. 简易银行系统

  • 2022/03/18

解题思路: 数组模拟

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
class Bank
{
    private $balance;

    /**
     * @param Integer[] $balance
     */
    function __construct($balance)
    {
        $this->balance = $balance;
    }

    /**
     * @param Integer $account1
     * @param Integer $account2
     * @param Integer $money
     * @return Boolean
     */
    function transfer($account1, $account2, $money)
    {
        // account1 取钱
        if (!$this->withdraw($account1, $money)) return false; // account1 提现失败
        // account2 存钱
        if (!$this->deposit($account2, $money)) {
            $this->deposit($account1, $money); // 把钱退回account1
            return false;
        }
        return true;
    }

    /**
     * @param Integer $account
     * @param Integer $money
     * @return Boolean
     */
    function deposit($account, $money)
    {
        if (!isset($this->balance[$account - 1])) return false; // 账户判断
        $this->balance[$account - 1] += $money;
        return true;
    }

    /**
     * @param Integer $account
     * @param Integer $money
     * @return Boolean
     */
    function withdraw($account, $money)
    {
        if (!isset($this->balance[$account - 1])) return false; // 账户判断
        if ($this->balance[$account - 1] < $money) return false; // 余额判断
        $this->balance[$account - 1] -= $money;
        return true;
    }
}

/**
 * Your Bank object will be instantiated and called as such:
 * $obj = Bank($balance);
 * $ret_1 = $obj->transfer($account1, $account2, $money);
 * $ret_2 = $obj->deposit($account, $money);
 * $ret_3 = $obj->withdraw($account, $money);
 */

606. 根据二叉树创建字符串

LeetCode - 606. 根据二叉树创建字符串

  • 2022/03/19

解题思路: 递归

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
class Solution
{
    /**
     * @param TreeNode $root
     * @return String
     */
    function tree2str(TreeNode $root)
    {
        if ($root == null) return ""; // 二叉树为空
        if ($root->left == '' && $root->right == '') { // 当前节点左右子树都为空
            return (string)$root->val;
        }
        if ($root->right == null) { // 当前右子树为空
            // 只需要考虑左子树
            return (string)$root->val . '(' . $this->tree2str($root->left) . ')';
        }
        return (string)$root->val . "(" . $this->tree2str($root->left) . ')(' . $this->tree2str($root->right) . ')';
    }
}

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;
    } 
}

解题思路: 迭代

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
class Solution
{
    /**
     * @param TreeNode $root
     * @return String
     */
    function tree2str($root)
    {
        $ans = '';
        $stack = new SplStack();
        $stack->push($root);
        $vis = [];
        while (!$stack->isEmpty()) {
            $node = $stack->top();
            // 严格比较
            if (in_array($node, $vis, true)) {
                if ($node !== $root) {
                    $ans .= ')';
                }
                $stack->pop();
            } else {
                $vis[] = $node;
                if ($node !== $root) {
                    $ans .= '(';
                }
                $ans .= $node->val;
                // 右子树不为空,左子树为空
                if ($node->left === null && $node->right !== null) {
                    $ans .= '()';
                }
                if ($node->right !== null) {
                    $stack->push($node->right);
                }
                if ($node->left !== null) {
                    $stack->push($node->left);
                }
            }
        }
        
        return (string)$ans;
    }
}

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;
    } 
}

2039. 网络空闲的时刻

LeetCode - 2039. 网络空闲的时刻

  • 2022/03/20

解题思路: 广度优先搜索
我们可以将整个计算机网络视为一个无向图，服务器为图中的节点。根据图中的边对应的关系 edges 即可求出图中任意节点之间的最短距离。利用广度优先搜索求出节点 00 到其他节点的最短距离

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
class Solution
{
    /**
     * @param Integer[][] $edges
     * @param Integer[] $patience
     * @return Integer
     */
    function networkBecomesIdle($edges, $patience) {
        $n = count($patience); // 3
        $g = array_fill(0, $n, []); // [0 => [], 1 => [], 2 => []] 
        foreach ($edges as $e) {
            $x = $e[0];
            $y = $e[1];
            $g[$x][] = $y;
            $g[$y][] = $x;
        }
        $vis = array_fill(0, $n, false); // [0 => false, 1 => false, 2 => false]
        $vis[0] = true; // [0 => true, 1 => false, 2 => false]
        $q = [0 => 0];
        // // 广度优先搜索求解最短的距离，然后计算最后一个能发出去的信息的时间+最短距离*2+1的传递时间
        for ($dist = 1; $q !== []; $dist++) {
            $tmp = $q;
            $q = [];
            foreach ($tmp as $x) {
                foreach ($g[$x] as $v) {
                    if ($vis[$v]) continue;
                    $vis[$v] = true;
                    $q[] = $v;
                    // floor 解决PHP隐式转换问题
                    $ans = max($ans, floor(($dist*2 - 1) / $patience[$v]) * $patience[$v] + $dist*2 + 1);

                }
            }
        }
        return $ans;
    }
}

653. 两数之和 IV - 输入 BST

LeetCode - 653. 两数之和 IV - 输入 BST

  • 2022/03/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
29
30
31
32
33
34
35
36
37
/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution
{
    /**
     * @param TreeNode $root
     * @param Integer $k
     * @return Boolean
     */
    function findTarget($root, $k)
    {
        $array[] = ""; // 哈希集合
        return $this->dfs($root, $k, $array);
    }

    function dfs($root, $k, &$array)
    {
        if ($root->val === null) return false;
        if (in_array(($k - $root->val), $array)) {
            return true;
        }
        $array[] = $root->val;

        return $this->dfs($root->left, $k, $array) || $this->dfs($root->right, $k, $array);
    }
}

解题思路: 广度优先搜索 + 哈希表

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
/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution
{
    /**
     * @param TreeNode $root
     * @param Integer $k
     * @return Boolean
     */
    function findTarget($root, $k)
    {
        $set[] = ''; // 哈希表
        $queue = new SplQueue();
        $queue->push($root);
        while (!$queue->isEmpty()) {
            $node = $queue->shift();
            if (in_array(($k - $node->val), $set)) {
                return true;
            }
            array_push($set, $node->val);
            if ($node->left) {
                $queue->push($node->left);
            }
            if ($node->right) {
                $queue->push($node->right);
            }
        }

        return false;
    }
}

2038. 如果相邻两个颜色均相同则删除当前颜色

LeetCode - 2038. 如果相邻两个颜色均相同则删除当前颜色

  • 2022/03/22

解题思路: 贪心算法

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 String $colors
     * @return Boolean
     */
    function winnerOfGame($colors)
    {
        $freq = [0, 0];
        $cur = 'C';
        $cnt = 0;
        // 当 Alice 的操作数大于 Bob 的操作数时，Alice 获胜；否则，Bob 获胜。
        for ($i = 0; $i < strlen($colors); $i++) {
            $c = $colors[$i];
            if ($c !== $cur) {
                $cur = $c;
                $cnt = 1;
            } else {
                $cnt += 1;
                if ($cnt >= 3) {
                    // ord('A') - ord('A') = 0
                    // ord('B') - ord('A') = 1
                    $freq[ord($cur) - ord('A')] += 1;
                }
            }
        }
        return $freq[0] > $freq[1];
    }
}

440. 字典序的第K小数字

LeetCode - 440. 字典序的第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
32
33
34
35
36
class Solution
{
    /**
     * @param Integer $n
     * @param Integer $k
     * @return Integer
     */
    function findKthNumber($n, $k)
    {
        $cur = 1;
        $k--;
        while ($k > 0) {
            $steps = $this->getSteps($cur, $n);
            if ($steps <= $k) {
                $k -= $steps;
                $cur++;
            } else {
                $cur *= 10;
                $k--;
            }
        }
        return $cur;
    }

    function getSteps($cur, $n)
    {
        $first = $last = $cur;
        while ($first <= $n) {
            $steps += min($last, $n) - $first + 1;
            $first *= 10;
            $last = $last * 10 + 9;
        }

        return $steps;
    }
}

661. 图片平滑器

LeetCode - 661. 图片平滑器

解题思路: 遍历

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
class Solution
{
    /**
     * @param Integer[][] $img
     * @return Integer[][]
     */
    function imageSmoother($img)
    {
        $h = count($img); // 长度
        $w = count($img[0]); // 宽度

        $ret = [];
        for ($i = 0; $i < $h; $i++) {
            for ($j = 0; $j < $w; $j++) {
                $count = 0;
                foreach([$i - 1, $i, $i + 1] as $iv) {
                    foreach([$j - 1, $j, $j + 1] as $jv) {
                        if ($iv >= 0 && $iv < $h && $jv >= 0 && $jv < $w) {
                            // 下标在数组范围内
                            $ret[$i][$j] += $img[$iv][$jv];
                            $count++;
                        }
                    } 
                }
                $ret[$i][$j] = floor($ret[$i][$j]/$count);
            }
        }
        return $ret;
    }
}

172. 阶乘后的零

LeetCode - 172. 阶乘后的零

解题思路: 质因数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution
{
    /**
     * @param Integer $n
     * @return Integer
     */
    function trailingZeroes($n)
    {
        $num = 0;
        // n! 尾零的数量即为 n! 中因子 10 的个数，而 10=2×5，因此转换成求 n! 中质因子 2 的个数和质因子 5 的个数的较小值。
        while ($n > 0) {
            $n = (int)($n/5);
            $num += $n;
        }
        return $num;
    }
}

682. 棒球比赛

LeetCode - 682. 棒球比赛

解题思路: 链表长度

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
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution
{
    /**
     * @param ListNode $head
     * @param Integer $n
     * @return ListNode
     */
    function removeNthFromEnd($head, $n)
    {
        $dummyHead = new ListNode(0, $head);
        $length = $this->getLength($head); // 链表长度
        $cur = $dummyHead;
        // 第 L−n+1 个节点时，它就是我们需要删除的节点
        for ($i = 1; $i < $length - $n + 1; $i++) {
            $cur = $cur->next;
        }
        $cur->next = $cur->next->next;

        return $dummyHead->next;
    }

    private function getLength($head)
    {
        $length = 0;
        while ($head != null) {
            $head = $head->next;
            $length++;
        }
        return $length;
    }
}

解题思路: 栈

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 $head
 * @param Integer $n
 * @return ListNode
 */
function removeNthFromEnd($head, $n)
{
    $dummyHead = new ListNode(0, $head);
    $cur = $dummyHead;
    $stack = new SplStack();
    while ($cur != null) {
        $stack->push($cur);
        $cur = $cur->next;
    }
    // 根据栈「先进后出」的原则，我们弹出栈的第 n 个节点就是需要删除的节点
    for ($i = 0; $i < $n; $i++) {
        $stack->pop();
    }
    $pre = $stack->top();
    $pre->next = $pre->next->next;

    return $dummyHead->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
/**
 * @param ListNode $head
 * @param Integer $n
 * @return ListNode
 */
function removeNthFromEnd($head, $n)
{
    $dummyHead = new ListNode(0, $head);
    $first  = $head;
    $second = $dummyHead;
    // first指针, 先走n个节点
    for ($i = 0; $i < $n; $i++) {
        $first = $first->next;
    }
    // first遍历结束, second正好在倒数第n个节点
    while ($first != null) {
        $first  = $first->next;
        $second = $second->next;
    }
    // 删除节点
    $second->next = $second->next->next;

    return $dummyHead->next;
}

2028. 找出缺失的观测数据

LeetCode - 2028. 找出缺失的观测数据

解题思路: 模拟构造

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution
{
    /**
     * @param Integer[] $rolls
     * @param Integer $mean
     * @param Integer $n
     * @return Integer[]
     */
    function missingRolls($rolls, $mean, $n)
    {
        $missSum = ($mean * ($n + count($rolls))) - array_sum($rolls); // 缺失数据总和
        if ($missSum < $n || $missSum > $n*6) return []; // 每次观测数据的范围是 1 到 6
        $avg  = (int)($missSum / $n);
        $less = $missSum % $n;
        $ans  = array_fill(0, $n, $avg);
        for ($i = 0; $i < $n; $i++) {
            $ans[$i] = $avg + ($i < $less ? 1 : 0);
        }
        return $ans;
    }
}

693. 交替位二进制数

LeetCode - 693. 交替位二进制数

解题思路: 位运算

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution
{
    /**
     * @param Integer $n
     * @return Boolean
     */
    function hasAlternatingBits($n)
    {
        $tmp = $n ^ ($n >> 1);

        return ($tmp & ($tmp + 1)) == 0;
    }
}

2024. 考试的最大困扰度

LeetCode - 2024. 考试的最大困扰度

解题思路: 滑动窗口

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
class Solution
{
    /**
     * @param String $answerKey
     * @param Integer $k
     * @return Integer
     */
    function maxConsecutiveAnswers($answerKey, $k)
    {
        return max($this->maxConsecutiveChar($answerKey, $k, 'T'), $this->maxConsecutiveChar($answerKey, $k, 'F'));
    }

    function maxConsecutiveChar($answerKey, $k, $byte)
    {
        $ans = $left = $sum = 0;
        $n = strlen($answerKey);
        for ($i = 0; $i < $n; $i++) {
            if ($answerKey[$i] != $byte) $sum++;
            while ($sum > $k) {
                if ($answerKey[$left] != $byte) $sum--;
                $left++;
            }
            $ans = max($ans, $i - $left + 1);
        }

        return $ans;
    }
}

1606. 找到处理最多请求的服务器

LeetCode - 1606. 找到处理最多请求的服务器

解题思路: 

1

728. 自除数

LeetCode - 728. 自除数

解题思路: 模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution
{
    /**
     * @param Integer $left
     * @param Integer $right
     * @return Integer[]
     */
    function selfDividingNumbers($left, $right)
    {
        $array = [];
        for ($num = $left; $left <= $right; $num = ++$left) {
            while ($num) {
                $mod = $num % 10;
                if ($mod == 0 || $left % $mod != 0) {
                    continue 2;
                }
                $num = (int)($num / 10);
            }
            $array[] = $left;
        }
        return $array;
    }
}

Powered by Hexo and Hexo-theme-hiker

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

访客数 : | 访问量 :