知耻而后勇, 日积月累, 每月一篇博客
以下内容, 记录自己刷题过程
954. 二倍数对数组
LeetCode - 954. 二倍数对数组
解题思路: 哈希表+排序
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
{
function canReorderDoubled($arr)
{
$count = array_count_values($arr);
if ($count[0] % 2) return false;
usort($arr, function ($a, $b) {
return abs($a) - abs($b);
});
foreach ($arr as $x) {
if ($count[$x] == 0) continue;
if ($count[2 * $x] < $count[$x]) return false;
$count[$x] -= 1;
$count[2 * $x] -= 1;
}
return true;
}
}
|
420. 强密码检验器
LeetCode - 420. 强密码检验器
解题思路: 分类讨论
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
| class Solution
{
function strongPasswordChecker($password)
{
$hasLower = $hasUpper = $hasDigit = 0;
$n = strlen($password);
for ($i = 0; $i < $n; $i++) {
if ($this->isLower($password[$i])) {
$hasLower = 1;
} elseif ($this->isUpper($password[$i])) {
$hasUpper = 1;
} elseif (is_numeric($password[$i])) {
$hasDigit = 1;
}
}
$categories = $hasLower + $hasUpper + $hasDigit;
switch ($n) {
case $n < 6:
return max(6 - $n, 3 - $categories);
case $n <= 20:
$replace = $cnt = 0;
$cur = '#';
for ($i = 0; $i < $n; $i++) {
if ($password[$i] == $cur) {
$cnt++;
} else {
$replace += floor($cnt / 3);
$cnt = 1;
$cur = $password[$i];
}
}
$replace += floor($cnt / 3);
return max($replace, 3 - $categories);
default:
$replace = 0;
$remove = $n - 20;
$rm2 = $cnt = 0;
$cur = '#';
for ($i = 0; $i < $n; $i++) {
if ($password[$i] == $cur) {
$cnt++;
continue;
}
if ($remove > 0 && $cnt >= 3) {
if ($cnt % 3 == 0) {
$remove--;
$replace--;
} elseif ($cnt % 3 == 1) {
$rm2++;
}
}
$replace += floor($cnt / 3);
$cnt = 1;
$cur = $password[$i];
}
if ($remove > 0 && $cnt >= 3) {
if ($cnt % 3 == 0) {
$remove--;
$replace--;
} elseif ($cnt % 3 == 1) {
$rm2++;
}
}
$replace += floor($cnt / 3);
$use2 = min(min($replace, $rm2), (int)($remove / 2));
$replace -= $use2;
$remove -= $use2 * 2;
$use3 = min($replace, (int)($remove / 3));
$replace -= $use3;
$remove -= $use3 * 3;
return ($n - 20) + max($replace, 3 - $categories);
}
}
function isLower($char)
{
if (ord($char) >= ord('a') && ord($char) <= ord('z')) {
return true;
}
return false;
}
function isUpper($char)
{
if (ord($char) >= ord('A') && ord($char) <= ord('Z')) {
return true;
}
return false;
}
}
|
744. 寻找比目标字母大的最小字母
LeetCode - 744. 寻找比目标字母大的最小字母
解题思路: 线性查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution
{
function nextGreatestLetter($letters, $target)
{
foreach ($letters as $letter) {
if ($letter > $target) {
return $letter;
}
}
return $letters[0];
}
}
|
307. 区域和检索 - 数组可修改
LeetCode - 307. 区域和检索 - 数组可修改
解题思路: 树状数组
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
| class NumArray
{
private $nums;
private $n;
function __construct($nums)
{
$this->nums = $nums;
$this->n = count($nums);
$this->tree = array_fill(0, $this->n + 1, 0);
for ($i = 0; $i < $this->n; $i++) $this->add($i + 1, $nums[$i]);
}
function lowbit($x)
{
return $x & (-$x);
}
function query($x)
{
$ans = 0;
for ($i = $x; $i > 0; $i -= $this->lowbit($i))
$ans += $this->tree[$i];
return $ans;
}
function add($x, $u)
{
for ($i = $x; $i <= $this->n; $i += $this->lowbit($i))
$this->tree[$i] += $u;
}
function update($index, $val)
{
$this->add($index + 1, $val - $this->nums[$index]);
$this->nums[$index] = $val;
}
function sumRange($left, $right)
{
return $this->query($right + 1) - $this->query($left);
}
}
|
762. 二进制表示中质数个计算置位
LeetCode - 762. 二进制表示中质数个计算置位
解题思路: 数学+位运算
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
{
function countPrimeSetBits($left, $right)
{
$ans = 0;
for ($x = $left; $x <= $right; ++$x) {
if ($this->isPrime($this->bitCount($x))) {
++$ans;
}
}
return $ans;
}
function isPrime($x)
{
if ($x < 2) return false;
for ($i = 2; $i ** 2 <= $x; ++$i) {
if ($x % $i == 0) return false;
}
return true;
}
function bitCount($x)
{
$x = $x - (($x >> 1) & 0x55555555);
$x = ($x & 0x33333333) + (($x >> 2) & 0x33333333);
$x = ($x + ($x >> 4)) & 0x0f0f0f0f;
$x = $x + ($x >> 8);
$x = $x + ($x >> 16);
return $x & 0x3f;
}
}
|
310. 最小高度树
LeetCode - 310. 最小高度树
解题思路: 拓扑排序
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
{
function findMinHeightTrees($n, $edges)
{
$dict = [];
foreach ($edges as $pair) {
$dict[$pair[0]][$pair[1]] = true;
$dict[$pair[1]][$pair[0]] = true;
}
while (count($dict) > 2) {
foreach ($dict as $key => $nodes) {
if (count($nodes) <= 1) {
foreach ($nodes as $node => $_) {
unset($dict[$key]);
unset($dict[$node][$key]);
}
}
}
}
if (count($dict) == 0) return [0];
return array_keys($dict);
}
}
|
