每日算法 2

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

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
{
/**
* @param Integer[] $arr
* @return Boolean
*/
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; // 无法找到足够的2x和x配对
$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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
class Solution
{
/**
* @param String $password
* @return Integer
*/
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); // 解决PHP隐式转换问题
return max($replace, 3 - $categories);
default:
// 替换次数和删除次数
$replace = 0;
$remove = $n - 20;
// k mod 3 = 1 的组数,删除2个字符可以减少1次替换操作
$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) {
// 如果是 k mod 3 = 0 的组, 优先删除1个字符, 减少1次替换操作
$remove--;
$replace--;
} elseif ($cnt % 3 == 1) {
// 如果是 k mod 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);

// 使用 k mod 3 =1 的组的数量, 由剩余的替换次数, 组数和剩余的删除次数共同决定
$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. 寻找比目标字母大的最小字母](https://leetcode-cn.com/problems/find-smallest-letter-greater-than-target/)

> 解题思路: 线性查找

```php
class Solution
{
/**
* @param String[] $letters
* @param String $target
* @return String
*/
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;

/**
* @param int[] $nums
*/
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;
}

/**
* @param int $index
* @param int $val
* @return NULL
*/
function update($index, $val)
{
$this->add($index + 1, $val - $this->nums[$index]);
$this->nums[$index] = $val;
}

/**
* @param int $left
* @param int $right
* @return int
*/
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
{
/**
* @param Integer $left
* @param Integer $right
* @return Integer
*/
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
{
/**
* @param Integer $n
* @param Integer[][] $edges
* @return Integer[]
*/
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);
}
}

Powered by Hexo and Hexo-theme-hiker

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

访客数 : | 访问量 :