每日算法 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
2


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 - 2022 Keep It Simple And Stupid All Rights Reserved.

访客数 : | 访问量 :