Skip to content

Commit 4f880b8

Browse files
HugoWenHugoWen
committed
week3
1 parent d130428 commit 4f880b8

8 files changed

Lines changed: 399 additions & 0 deletions

File tree

‎Week_03/id_6/LeetCode_104_6.php‎

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
<?php
2+
3+
4+
/**
5+
* Definition for a binary tree node.
6+
* class TreeNode {
7+
* public $val = null;
8+
* public $left = null;
9+
* public $right = null;
10+
* function __construct($value) { $this->val = $value; }
11+
* }
12+
*/
13+
class Solution
14+
{
15+
16+
/**
17+
* @param TreeNode $root
18+
* @return Integer
19+
*/
20+
function maxDepth($root)
21+
{
22+
if ($root == null) return 0;
23+
return max($this->maxDepth($root->left), $this->maxDepth($root->right)) + 1;
24+
}
25+
}

‎Week_03/id_6/LeetCode_200_6.php‎

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
<?php
2+
3+
4+
class Solution {
5+
6+
/**
7+
* @param String[][] $grid
8+
* @return Integer
9+
*/
10+
function numIslands($grid)
11+
{
12+
if (empty($grid)) return 0;
13+
14+
$sum = 0;
15+
$width = count($grid);
16+
$height = count($grid[0]);
17+
for ($i = 0; $i < $width; $i ++) {
18+
for ($j = 0; $j < $height; $j ++) {
19+
if ($grid[$i][$j] == '1') {
20+
$sum ++;
21+
$this->bfs($grid, $i, $j);
22+
}
23+
}
24+
}
25+
26+
return $sum;
27+
}
28+
29+
function bfs(&$grid, $i, $j)
30+
{
31+
$x = [$i - 1, $i, $i + 1, $i];
32+
$y = [$j, $j - 1, $j, $j + 1];
33+
$width = count($grid);
34+
$height = count($grid[0]);
35+
36+
for ($k = 0; $k < 4; $k ++) {
37+
if ($x[$k] < 0 || $y[$k] < 0 || $x[$k] > $width - 1 || $y[$k] > $height - 1 || $grid[$x[$k]][$y[$k]] == '0') {
38+
continue;
39+
}
40+
41+
$grid[$x[$k]][$y[$k]] = '0';
42+
$this->bfs($grid, $x[$k], $y[$k]);
43+
}
44+
}
45+
}
46+
47+
$grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]];
48+
$sol = new Solution();
49+
var_dump($sol->numIslands($grid));

‎Week_03/id_6/LeetCode_210_6.php‎

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
<?php
2+
3+
4+
class Solution {
5+
6+
/**
7+
* @param Integer $numCourses
8+
* @param Integer[][] $prerequisites
9+
* @return Integer[]
10+
*/
11+
function findOrder($numCourses, $prerequisites)
12+
{
13+
if ($numCourses <= 0) return [];
14+
15+
$in_degree = [];
16+
$graph = [];
17+
$queue = [];
18+
19+
foreach ($prerequisites as $prerequisite) {
20+
$graph[$prerequisite[1]][] = $prerequisite[0];
21+
if (!isset($in_degree[$prerequisite[0]])) $in_degree[$prerequisite[0]] = 0;
22+
$in_degree[$prerequisite[0]] ++;
23+
}
24+
25+
for ($i = 0; $i < $numCourses; $i ++) {
26+
if (!isset($in_degree[$i])) {
27+
$queue[] = $i;
28+
}
29+
}
30+
31+
$res = [];
32+
while ($queue) {
33+
$node = array_shift($queue);
34+
$res[] = $node;
35+
if (!isset($graph[$node])) {
36+
continue;
37+
}
38+
$next_courses = $graph[$node];
39+
foreach ($next_courses as $next_course) {
40+
$in_degree[$next_course] --;
41+
if ($in_degree[$next_course] == 0) {
42+
$queue[] = $next_course;
43+
}
44+
}
45+
}
46+
47+
if (count($res) == $numCourses) {
48+
return $res;
49+
}
50+
51+
return [];
52+
}
53+
}
54+
55+
$sol = new Solution();
56+
$numCourses = 4;
57+
$prerequisites = [[1,0],[2,0],[3,1],[3,2]];
58+
var_export($sol->findOrder($numCourses, $prerequisites));

‎Week_03/id_6/LeetCode_295_6.php‎

Lines changed: 87 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,87 @@
1+
<?php
2+
3+
class MedianFinder {
4+
5+
public $arr;
6+
7+
/**
8+
* initialize your data structure here.
9+
*/
10+
function __construct() {
11+
$this->arr = [];
12+
}
13+
14+
/**
15+
* @param Integer $num
16+
* @return NULL
17+
*/
18+
function addNum($num) {
19+
if (count($this->arr) == 0) {
20+
$this->arr[] = $num;
21+
return;
22+
}
23+
24+
$left = 0;
25+
$right = count($this->arr) - 1;
26+
27+
if ($this->arr[0] >= $num) {
28+
array_unshift($this->arr, $num);
29+
return;
30+
}
31+
32+
if ($this->arr[$right] <= $num) {
33+
$this->arr[] = $num;
34+
return;
35+
}
36+
37+
while ($left < $right) {
38+
$mid = (int)($left + $right) / 2;
39+
if ($num <= $this->arr[$mid]) {
40+
$right = $mid;
41+
} else {
42+
$left = $mid + 1;
43+
}
44+
}
45+
46+
for ($i = count($this->arr); $i > $left; $i --) {
47+
$this->arr[$i] = $this->arr[$i - 1];
48+
}
49+
$this->arr[$left] = $num;
50+
return;
51+
}
52+
53+
/**
54+
* @return Float
55+
*/
56+
function findMedian() {
57+
$len = count($this->arr);
58+
if ($len & 1) {
59+
return $this->arr[(int)($len / 2)];
60+
}
61+
62+
return (float)($this->arr[$len / 2 - 1] + $this->arr[$len / 2]) / 2;
63+
}
64+
}
65+
66+
/**
67+
* Your MedianFinder object will be instantiated and called as such:
68+
* $obj = MedianFinder();
69+
* $obj->addNum($num);
70+
* $ret_2 = $obj->findMedian();
71+
*/
72+
73+
$obj = new MedianFinder();
74+
$obj->addNum(1);var_dump($obj->arr);
75+
var_dump($obj->findMedian());
76+
$obj->addNum(2);var_dump($obj->arr);
77+
var_dump($obj->findMedian());
78+
$obj->addNum(3);var_dump($obj->arr);
79+
var_dump($obj->findMedian());
80+
$obj->addNum(14);var_dump($obj->arr);
81+
var_dump($obj->findMedian());
82+
$obj->addNum(35);var_dump($obj->arr);
83+
var_dump($obj->findMedian());
84+
$obj->addNum(19);var_dump($obj->arr);
85+
var_dump($obj->findMedian());
86+
$obj->addNum(34);var_dump($obj->arr);
87+
var_dump($obj->findMedian());

‎Week_03/id_6/LeetCode_320_6.php‎

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
<?php
2+
3+
4+
class Solution {
5+
6+
/**
7+
* @param Integer $n
8+
* @param Integer[][] $edges
9+
* @return Integer[]
10+
*/
11+
function findMinHeightTrees($n, $edges)
12+
{
13+
if ($n == 1) return [0];
14+
15+
$adj = [];
16+
foreach ($edges as $edge) {
17+
$adj[$edge[0]][] = $edge[1];
18+
$adj[$edge[1]][] = $edge[0];
19+
}
20+
21+
$leaves = [];
22+
for ($i = 0; $i < $n; $i ++) {
23+
if (count($adj[$i]) == 1) {
24+
$leaves[] = $i;
25+
}
26+
}
27+
28+
while ($n > 2) {
29+
$n -= count($leaves);
30+
foreach ($leaves as $k => $leaf) {
31+
$root = current($adj[$leaf]);
32+
$key = array_search($leaf, $adj[$root]);
33+
unset($adj[$root][$key]);
34+
unset($leaves[$k]);
35+
if (count($adj[$root]) == 1) {
36+
$leaves[] = $root;
37+
}
38+
}
39+
}
40+
41+
return $leaves;
42+
}
43+
}
44+
45+
$n = 4;
46+
$edges = [[1, 0], [1, 2], [1, 3]];
47+
$n = 6;
48+
$edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]];
49+
50+
$n = 11;
51+
$edges = [[0,1],[0,2],[2,3],[0,4],[2,5],[5,6],[3,7],[6,8],[8,9],[9,10]];
52+
53+
$sol = new Solution();
54+
var_dump($sol->findMinHeightTrees($n, $edges));

‎Week_03/id_6/LeetCode_329_6.php‎

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
<?php
2+
3+
4+
class Solution {
5+
6+
public $visited = [];
7+
8+
/**
9+
* @param Integer[][] $matrix
10+
* @return Integer
11+
*/
12+
function longestIncreasingPath($matrix)
13+
{
14+
if (!$matrix) return 0;
15+
16+
$len = 1;
17+
18+
$width = count($matrix);
19+
$height = count($matrix[0]);
20+
21+
for ($i = 0; $i < $width; $i ++) {
22+
for ($j = 0; $j < $height; $j ++) {
23+
$len = max($len, $this->dfs($matrix, $i, $j));
24+
}
25+
}
26+
27+
return $len;
28+
}
29+
30+
function dfs($m, $i, $j)
31+
{
32+
if (isset($this->visited[$i][$j])) return $this->visited[$i][$j];
33+
34+
$x = [$i - 1, $i, $i + 1, $i];
35+
$y = [$j, $j - 1, $j, $j + 1];
36+
$width = count($m);
37+
$height = count($m[0]);
38+
$len = 1;
39+
40+
for ($k = 0; $k < 4; $k ++) {
41+
if ($x[$k] < 0 || $y[$k] < 0 || $x[$k] > $width - 1 || $y[$k] > $height - 1 || $m[$x[$k]][$y[$k]] <= $m[$i][$j]) {
42+
continue;
43+
}
44+
$len = max($len, $this->dfs($m, $x[$k], $y[$k]) + 1);
45+
}
46+
47+
$this->visited[$i][$j] = $len;
48+
return $len;
49+
}
50+
}
51+
52+
$m = [[9,9,4],[6,6,8],[2,1,1]];
53+
$m = [[0],[1],[5],[5]];
54+
$sol = new Solution();
55+
var_dump($sol->longestIncreasingPath($m));

‎Week_03/id_6/LeetCode_547_6.php‎

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
<?php
2+
3+
4+
class Solution {
5+
6+
public $visited = [];
7+
/**
8+
* @param Integer[][] $M
9+
* @return Integer
10+
*/
11+
function findCircleNum($M)
12+
{
13+
if (!$M) return 0;
14+
15+
$sum = 0;
16+
for ($i = 0; $i < count($M); $i ++) {
17+
if (!isset($this->visited[$i])) {
18+
$this->bfs($M, $i);
19+
$sum ++;
20+
}
21+
}
22+
23+
return $sum;
24+
}
25+
26+
function bfs($m, $i)
27+
{
28+
for ($j = 0; $j < count($m); $j ++) {
29+
if ($m[$i][$j] == '1' && !isset($this->visited[$j])) {
30+
$this->visited[$j] = 1;
31+
$this->bfs($m, $j);
32+
}
33+
}
34+
}
35+
}
36+
37+
$M = [[1,0,0,1],[0,1,1,0],[0,1,1,1],[1,0,1,1]];
38+
$sol = new Solution();
39+
var_dump($sol->findCircleNum($M));

0 commit comments

Comments
 (0)