LeetCode每日一题
2022-03-01
7分钟阅读时长
(03-25) 892. 三维形体的表面积
class Solution {
/**
* @param Integer[][] $grid
* @return Integer
*/
function surfaceArea($grid) {
$n = count($grid);
$area = 0;
for ($i = 0; $i < $n; $i++) {
for ($j = 0; $j < $n; $j++) {
$level = $grid[$i][$j];
if ($level > 0) {
//贡献的面积 << 2 相当于 * 4
$area += 2 + ($level << 2);
//减去重合的面积 << 1 相当于 * 2
$area -= $i > 0 ? min($level, $grid[$i - 1][$j]) << 1 : 0;
//减去重合的面积
$area -= $j > 0 ? min($level, $grid[$i][$j - 1]) << 1 : 0;
}
}
}
return $area;
}
}
03-26 999. 车的可用捕获量
class Solution {
/**
* @param String[][] $board
* @return Integer
*/
function numRookCaptures($board) {
$cnt = $st = $ed = 0;
//查找车
for ($i =0 ; $i < 8; $i++) {
for ($j = 0; $j < 8; $j++) {
if ($board[$i][$j] == 'R') {
$st = $i;
$ed = $j;
break;
}
}
}
//遍历扩散
$dx = [-1, 1, 0, 0];
$dy = [0, 0, -1, 1];
for ($i = 0; $i < 4; $i++) {
for ($step = 0;; $step++){
$x = $st + $dx[$i] * $step;
$y = $ed + $dy[$i] * $step;
//遇到边界或者白色的象
if ($x < 0 || $x >= 8 || $y < 0 || $y >= 8 || $board[$x][$y] =='B') break;
if ($board[$x][$y] == 'p') {
$borad[$x][$y] = '.';
$cnt++;
break;
}
}
}
return $cnt;
}
}
03-27 914. 卡牌分组
class Solution {
/**
* @param Integer[] $deck
* @return Boolean
*/
function hasGroupsSizeX($deck) {
$map = [];
foreach ($deck as $n) {
$map[$n] = $map[$n]? $map[$n] + 1: 1;
}
$g = -1;
foreach($map as $i=>$count) {
if ($g == -1) {
$g = $count;
} else {
$g = $this->gcd($g, $count);
}
}
return $g >= 2;
}
function hasGroupsSizeX2($deck) {
$map = array_count_values($deck);
$g = -1;
foreach($map as $i=>$count) {
$g = $g == -1 ? $count : $this->gcd($g, $count);
}
return $g >= 2;
}
function gcd ($x , $y) {
return $y == 0 ? $x : $this->gcd($y, $x % $y);
}
}
03-29 1162. 地图分析
class Solution {
private $n;
private $grid;
/**
* 广度优先搜索
* @param Integer[][] $grid
* @return Integer
*/
function maxDistance($grid) {
$n = count($grid);
$q = [];
for ($i = 0; $i < $n; $i++)
for ($j = 0; $j < $n; $j++)
if ($grid[$i][$j] == 1)
$q[] = [$i, $j];
if (count($q) == $n * $n || count($q) ==0) return -1;
$level = 0;
$dx = [1, -1, 0, 0];
$dy = [0, 0, 1, -1];
while($q) {
$size = count($q);
while ($size--) {
[$x, $y] = array_shift($q);
for ($i = 0; $i < 4; $i++) {
$xi = $x + $dx[$i];
$yi = $y + $dy[$i];
if ($xi >= 0 && $xi < $n && $yi >= 0 && $yi < $n && $grid[$xi][$yi] == 0){
$q[] = [$xi, $yi];
$grid[$xi][$yi] = 1;
}
}
}
$level += 1;
}
return $level - 1;
}
/**
* 动态规划
* @param Integer[][] $grid
* @return Integer
*/
function maxDistance($grid) {
$n = count($grid);
$m = count($grid[0]);
$res = 0;
for ($i = 0; $i < $n; $i++) {
for ($j = 0; $j < $m; $j++) {
if ($grid[$i][$j] == 1) continue;
$grid[$i][$j] = 201; //201 here cuz as the despription, the size won't exceed 100.
if ($i > 0) $grid[$i][$j] = min($grid[$i][$j], $grid[$i-1][$j] + 1);
if ($j > 0) $grid[$i][$j] = min($grid[$i][$j], $grid[$i][$j-1] + 1);
}
}
for ($i = $n-1; $i > -1; $i--) {
for ($j = $m-1; $j > -1; $j--) {
if ($grid[$i][$j] == 1) continue;
if ($i < $n-1) $grid[$i][$j] = min($grid[$i][$j], $grid[$i+1][$j] + 1);
if ($j < $m-1) $grid[$i][$j] = min($grid[$i][$j], $grid[$i][$j+1] + 1);
$res = max($res, $grid[$i][$j]); //update the maximum
}
}
return $res == 201 ? -1 : $res - 1;
}
}
03-30 面试题62. 圆圈中最后剩下的数字
class Solution {
/**
* 递归
* @param Integer $n
* @param Integer $m
* @return Integer
*/
function lastRemaining($n, $m) {
if ($n == 1)
return 0;
$x = $this->lastRemaining($n - 1, $m);
return ($m + $x) % $n;
}
}
04-01 1111. 有效括号的嵌套深度
class Solution {
/**
* @param String $seq
* @return Integer[]
*/
function maxDepthAfterSplit($seq) {
$ans = [];
$d = 0;
foreach (str_split($seq) as $c) {
if ($c == '(') {
$d += 1;
$ans[] = $d % 2;
} else {
$ans[] = $d % 2;
$d -= 1;
}
}
return $ans;
}
}
04-14 445. 两数相加 II
/**
* Definition for a singly-linked list.
* class ListNode {
* public $val = 0;
* public $next = null;
* function __construct($val) { $this->val = $val; }
* }
*/
class Solution {
/**
* 方法一：栈
* 方法二：链表翻转相加
* @param ListNode $l1
* @param ListNode $l2
* @return ListNode
*/
function addTwoNumbers($l1, $l2) {
if (!$l1) return $l2;
if (!$l2) return $l1;
$s1 = $s2 = [];//数组模拟栈
while ($l1) {
$s1[] = $l1->val;
$l1 = $l1->next;
}
while ($l2) {
$s2[] = $l2->val;
$l2 = $l2->next;
}
$sum = 0;
$head = null;
while ($s1 || $s2 || $sum > 0) {
$sum += $s1 ? array_pop($s1) : 0;
$sum += $s2 ? array_pop($s2) : 0;
$node = new ListNode($sum % 10);
$node->next = $head;
$head = $node;
$sum = intval($sum / 10);
}
return $head;
}
}
04-15 542. 01 矩阵
class Solution {
/**
* @param Integer[][] $matrix
* @return Integer[][]
*/
function updateMatrix($matrix) {
$m = count($matrix);
if ($m == 0) return $matrix;
$n = count($matrix[0]);
$ans = [];
$queue = [];
for ($i = 0; $i < $m; $i++) {
for ($j = 0; $j < $n; $j++) {
if ($matrix[$i][$j] == 0) {
$ans[$i][$j] = 0;
$queue[] = [$i, $j];
} else {
$ans[$i][$j] = $m + $n; //最大值
}
}
}
$dx = [0, 1, 0, -1];
$dy = [1, 0, -1, 0];
while ($queue) {
[$x, $y] = array_shift($queue);
for($i = 0; $i < 4; $i++){
$nx = $x + $dx[$i];
$ny = $y + $dy[$i];
if($nx >= 0 && $nx < $m && $ny >= 0 && $y < $n){
if($ans[$nx][$ny] > $ans[$x][$y] + 1){
$ans[$nx][$ny] = $ans[$x][$y] + 1;
$queue[] = [$nx, $ny];
}
}
}
}
return $ans;
}
}
04-16 56. 合并区间
class Solution {
/**
* @param Integer[][] $intervals
* @return Integer[][]
*/
function merge($intervals) {
$count = count($intervals);
$output = [];
array_multisort(array_column($intervals, 0),$intervals);
for ($i = 0, $j = 0; $i < $count; $i++) {
if (empty($output) || $output[$j - 1][1] < $intervals[$i][0]) {
$output[$j++] = $intervals[$i];
} else {
$output[$j - 1][1] = max($intervals[$i][1], $output[$j - 1][1]);
}
}
return $output;
}
}
04-17 55. 跳跃游戏
class Solution {
/**
* 方法一：贪心法
* 方法二：动态规划
* @param Integer[] $nums
* @return Boolean
*/
function canJump($nums) {
if (!$nums) return false;
$revCanJump = count($nums) - 1;
for ($i = $revCanJump; $i >= 0; $i--) {
if ($nums[$i] + $i >= $revCanJump) {
$revCanJump = $i;
}
}
return $revCanJump == 0;
}
}
04-21 1248. 统计「优美子数组」
class Solution {
/**
* @param Integer[] $nums
* @param Integer $k
* @return Integer
*/
function numberOfSubarrays($nums, $k) {
$n = count($nums);
$odd = [];
$ans = $cnt = 0;
$odd[0] = -1;
for ($i = 0; $i < $n; $i++) {
if ($nums[$i] & 1) $odd[++$cnt] = $i;
}
$odd[++$cnt] = $n;
for ($i = 1; $i + $k <= $cnt; $i++) {
$ans + ($odd[$i] - $odd[$i - 1]) * ($odd[$i + $k] - $odd[$i + $k -1]);
}
return $ans;
}
function numberOfSubarrays1($nums, $k) {
$n = count($nums);
$ans = $odd = 0;
$cnt = [1];
for ($i = 0; $i < $n; $i++) {
$odd += $nums[$i] & 1;
$ans += $odd > $k ? $cnt[$odd - $k] : 0;
$cnt[$odd] += 1;
}
return $ans;
}
}