知耻而后勇, 日积月累, 每月一篇博客
以下内容, 记录自己刷题过程
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); } }
|