8000 Added tasks 647-1143 · pytdev/LeetCode-in-Php@0b0e1dc · GitHub
[go: up one dir, main page]
Skip to content

Commit 0b0e1dc

Browse files
javadevjavadev
authored
Added tasks 647-1143
1 parent 6399120 commit 0b0e1dc

File tree

13 files changed

+364
-2
lines changed

13 files changed

+364
-2
lines changed

‎README.md

Lines changed: 11 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -309,6 +309,7 @@ Php-based LeetCode algorithm problem solutions, regularly updated.
309309

310310
| <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- -->
311311
|-|-|-|-|-|-
312+
| 1143 |[Longest Common Subsequence](src/main/php/g1101_1200/s1143_longest_common_subsequence/Solution.php)| Medium | Top_100_Liked_Questions, String, Dynamic_Programming, Big_O_Time_O(n\*m)_Space_O(n\*m) | 191 | 96.00
312313
| 0072 |[Edit Distance](src/main/php/g0001_0100/s0072_edit_distance/Solution.php)| Hard | Top_100_Liked_Questions, String, Dynamic_Programming, Big_O_Time_O(n^2)_Space_O(n2) | 29 | 75.00
313314

314315
#### Day 20
@@ -417,6 +418,7 @@ Php-based LeetCode algorithm problem solutions, regularly updated.
417418

418419
| <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- -->
419420
|-|-|-|-|-|-
421+
| 0739 |[Daily Temperatures](src/main/php/g0701_0800/s0739_daily_temperatures/Solution.php)| Medium | Top_100_Liked_Questions, Array, Stack, Monotonic_Stack, Big_O_Time_O(n)_Space_O(n) | 410 | 100.00
420422

421423
#### Day 7
422424

@@ -749,7 +751,7 @@ Php-based LeetCode algorithm problem solutions, regularly updated.
749751
| <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- -->
750752
|-|-|-|-|-|-
751753
| 0543 |[Diameter of Binary Tree](src/main/php/g0501_0600/s0543_diameter_of_binary_tree/Solution.php)| Easy | Top_100_Liked_Questions, Depth_First_Search, Tree, Binary_Tree, Big_O_Time_O(n)_Space_O(n) | 0 | 100.00
752-
| 0437 |[Path Sum III](src/main/php/g0401_0500/s0437_path_sum_iii/Solution.php)| Medium | Top_100_Liked_Questions, Depth_First_Search, Tree, Binary_Tree, Big_O_Time_O(n)_Space_O(n) | 8 | 100.00
754+
| 0437 |[Path Sum III](src/main/php/g0401_0500/s0437_path_sum_iii/Solution.php)| Medium | Top_100_Liked_Questions, Depth_First_Search, Tree, Binary_Tree, Big_O_Time_O(n)_Space_O(n) | 11 | 100.00
753755

754756
#### Day 8 Binary Search
755757

@@ -951,6 +953,7 @@ Php-based LeetCode algorithm problem solutions, regularly updated.
951953
| 0070 |[Climbing Stairs](src/main/php/g0001_0100/s0070_climbing_stairs/Solution.php)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, Dynamic_Programming, Math, Memoization, Big_O_Time_O(n)_Space_O(n) | 3 | 82.81
952954
| 0064 |[Minimum Path Sum](src/main/php/g0001_0100/s0064_minimum_path_sum/Solution.php)| Medium | Top_100_Liked_Questions, Array, Dynamic_Programming, Matrix, Big_O_Time_O(m\*n)_Space_O(m\*n) | 20 | 81.48
953955
| 0300 |[Longest Increasing Subsequence](src/main/php/g0201_0300/s0300_longest_increasing_subsequence/Solution.php)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Dynamic_Programming, Binary_Search, Big_O_Time_O(n\*log_n)_Space_O(n) | 24 | 90.91
956+
| 1143 |[Longest Common Subsequence](src/main/php/g1101_1200/s1143_longest_common_subsequence/Solution.php)| Medium | Top_100_Liked_Questions, String, Dynamic_Programming, Big_O_Time_O(n\*m)_Space_O(n\*m) | 191 | 96.00
954957
| 0072 |[Edit Distance](src/main/php/g0001_0100/s0072_edit_distance/Solution.php)| Hard | Top_100_Liked_Questions, String, Dynamic_Programming, Big_O_Time_O(n^2)_Space_O(n2) | 29 | 75.00
955958
| 0010 |[Regular Expression Matching](src/main/php/g0001_0100/s0010_regular_expression_matching/Solution.php)| Hard | Top_100_Liked_Questions, Top_Interview_Questions, String, Dynamic_Programming, Recursion, Big_O_Time_O(m\*n)_Space_O(m\*n) | 10 | 64.52
956959

@@ -1107,6 +1110,7 @@ Php-based LeetCode algorithm problem solutions, regularly updated.
11071110

11081111
| <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- -->
11091112
|-|-|-|-|-|-
1113+
| 0763 |[Partition Labels](src/main/php/g0701_0800/s0763_partition_labels/Solution.php)| Medium | Top_100_Liked_Questions, String, Hash_Table, Greedy, Two_Pointers, Big_O_Time_O(n)_Space_O(1) | 5 | 83.33
11101114

11111115
#### Day 8 String
11121116

@@ -1379,6 +1383,7 @@ Php-based LeetCode algorithm problem solutions, regularly updated.
13791383

13801384
| <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- -->
13811385
|-|-|-|-|-|-
1386+
| 1143 |[Longest Common Subsequence](src/main/php/g1101_1200/s1143_longest_common_subsequence/Solution.php)| Medium | Top_100_Liked_Questions, String, Dynamic_Programming, Big_O_Time_O(n\*m)_Space_O(n\*m) | 191 | 96.00
13821387

13831388
#### Day 18 Dynamic Programming
13841389

@@ -1406,11 +1411,15 @@ Php-based LeetCode algorithm problem solutions, regularly updated.
14061411

14071412
| # | Title | Difficulty | Tag | Time, ms | Time, %
14081413
|------|----------------|-------------|-------------|----------|---------
1414+
| 1143 |[Longest Common Subsequence](src/main/php/g1101_1200/s1143_longest_common_subsequence/Solution.php)| Medium | Top_100_Liked_Questions, String, Dynamic_Programming, Algorithm_II_Day_17_Dynamic_Programming, Dynamic_Programming_I_Day_19, Udemy_Dynamic_Programming, Big_O_Time_O(n\*m)_Space_O(n\*m) | 191 | 96.00
1415+
| 0763 |[Partition Labels](src/main/php/g0701_0800/s0763_partition_labels/Solution.php)| Medium | Top_100_Liked_Questions, String, Hash_Table, Greedy, Two_Pointers, Data_Structure_II_Day_7_String, Big_O_Time_O(n)_Space_O(1) | 5 | 83.33
1416+
| 0739 |[Daily Temperatures](src/main/php/g0701_0800/s0739_daily_temperatures/Solution.php)| Medium | Top_100_Liked_Questions, Array, Stack, Monotonic_Stack, Programming_Skills_II_Day_6, Big_O_Time_O(n)_Space_O(n) | 410 | 100.00
1417+
| 0647 |[Palindromic Substrings](src/main/php/g0601_0700/s0647_palindromic_substrings/Solution.php)| Medium | Top_100_Liked_Questions, String, Dynamic_Programming, Big_O_Time_O(n^2)_Space_O(n) | 25 | 75.00
14091418
| 0560 |[Subarray Sum Equals K](src/main/php/g0501_0600/s0560_subarray_sum_equals_k/Solution.php)| Medium | Top_100_Liked_Questions, Array, Hash_Table, Prefix_Sum, Data_Structure_II_Day_5_Array, Big_O_Time_O(n)_Space_O(n) | 82 | 100.00
14101419
| 0543 |[Diameter of Binary Tree](src/main/php/g0501_0600/s0543_diameter_of_binary_tree/Solution.php)| Easy | Top_100_Liked_Questions, Depth_First_Search, Tree, Binary_Tree, Level_2_Day_7_Tree, Udemy_Tree_Stack_Queue, Big_O_Time_O(n)_Space_O(n) | 0 | 100.00
14111420
| 0494 |[Target Sum](src/main/php/g0401_0500/s0494_target_sum/Solution.php)| Medium | Top_100_Liked_Questions, Array, Dynamic_Programming, Backtracking, Big_O_Time_O(n\*(sum+s))_Space_O(n\*(sum+s)) | 27 | 75.00
14121421
| 0438 |[Find All Anagrams in a String](src/main/php/g0401_0500/s0438_find_all_anagrams_in_a_string/Solution.php)| Medium | Top_100_Liked_Questions, String, Hash_Table, Sliding_Window, Algorithm_II_Day_5_Sliding_Window, Programming_Skills_II_Day_12, Level_1_Day_12_Sliding_Window/Two_Pointer, Big_O_Time_O(n+m)_Space_O(1) | 29 | 66.67
1413-
| 0437 |[Path Sum III](src/main/php/g0401_0500/s0437_path_sum_iii/Solution.php)| Medium | Top_100_Liked_Questions, Depth_First_Search, Tree, Binary_Tree, Level_2_Day_7_Tree, Big_O_Time_O(n)_Space_O(n) | 8 | 100.00
1422+
| 0437 |[Path Sum III](src/main/php/g0401_0500/s0437_path_sum_iii/Solution.php)| Medium | Top_100_Liked_Questions, Depth_First_Search, Tree, Binary_Tree, Level_2_Day_7_Tree, Big_O_Time_O(n)_Space_O(n) | 11 | 100.00
14141423
| 0416 |[Partition Equal Subset Sum](src/main/php/g0401_0500/s0416_partition_equal_subset_sum/Solution.php)| Medium | Top_100_Liked_Questions, Array, Dynamic_Programming, Level_2_Day_13_Dynamic_Programming, Big_O_Time_O(n\*sums)_Space_O(n\*sums) | 245 | 86.67
14151424
| 0394 |[Decode String](src/main/php/g0301_0400/s0394_decode_string/Solution.php)| Medium | Top_100_Liked_Questions, String, Stack, Recursion, Level_1_Day_14_Stack, Udemy_Strings, Big_O_Time_O(n)_Space_O(n) | 3 | 77.78
14161425
| 0347 |[Top K Frequent Elements](src/main/php/g0301_0400/s0347_top_k_frequent_elements/Solution.php)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Hash_Table, Sorting, Heap_Priority_Queue, Counting, Divide_and_Conquer, Quickselect, Bucket_Sort, Data_Structure_II_Day_20_Heap_Priority_Queue, Big_O_Time_O(n\*log(n))_Space_O(k) | 23 | 84.85

‎src/main/php/g0601_0700/s0647_palindromic_substrings/Solution.php

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
<?php
2+
3+
namespace leetcode\g0601_0700\s0647_palindromic_substrings;
4+
5+
// #Medium #Top_100_Liked_Questions #String #Dynamic_Programming #Big_O_Time_O(n^2)_Space_O(n)
6+
// #2023_12_24_Time_25_ms_(75.00%)_Space_19.6_MB_(50.00%)
7+
8+
class Solution {
9+
private function expand($a, $l, $r, &$res) {
10+
while ($l >= 0 && $r < count($a)) {
11+
if ($a[$l] != $a[$r]) {
12+
return;
13+
} else {
14+
$res[0]++;
15+
$l--;
16+
$r++;
17+
}
18+
}
19+
}
20+
21+
/**
22+
* @param String $s
23+
* @return Integer
24+
*/
25+
public function countSubstrings($s) {
26+
$a = str_split($s);
27+
$res = array(0);
28+
for ($i = 0; $i < count($a); $i++) {
29+
$this->expand($a, $i, $i, $res);
30+
$this->expand($a, $i, $i + 1, $res);
31+
}
32+
return $res[0];
33+
}
34+
}

‎src/main/php/g0601_0700/s0647_palindromic_substrings/readme.md

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
647\. Palindromic Substrings
2+
3+
Medium
4+
5+
Given a string `s`, return _the number of **palindromic substrings** in it_.
6+
7+
A string is a **palindrome** when it reads the same backward as forward.
8+
9+
A **substring** is a contiguous sequence of characters within the string.
10+
11+
**Example 1:**
12+
13+
**Input:** s = "abc"
14+
15+
**Output:** 3
16+
17+
**Explanation:** Three palindromic strings: "a", "b", "c".
18+
19+
**Example 2:**
20+
21+
**Input:** s = "aaa"
22+
23+
**Output:** 6
24+
25+
**Explanation:** Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
26+
27+
**Constraints:**
28+
29+
* `1 <= s.length <= 1000`
30+
* `s` consists of lowercase English letters.

‎src/main/php/g0701_0800/s0739_daily_temperatures/Solution.php

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
<?php
2+
3+
namespace leetcode\g0701_0800\s0739_daily_temperatures;
4+
5+
// #Medium #Top_100_Liked_Questions #Array #Stack #Monotonic_Stack #Programming_Skills_II_Day_6
6+
// #Big_O_Time_O(n)_Space_O(n) #2023_12_24_Time_410_ms_(100.00%)_Space_29.9_MB_(100.00%)
7+
8+
class Solution {
9+
/**
10+
* @param Integer[] $temperatures
11+
* @return Integer[]
12+
*/
13+
public function dailyTemperatures($temperatures) {
14+
$sol = array_fill(0, count($temperatures), 0);
15+
$sol[count($temperatures) - 1] = 0;
16+
for ($i = count($sol) - 2; $i >= 0; $i--) {
17+
$j = $i + 1;
18+
while ($j <= count($sol)) {
19+
if ($temperatures[$i] < $temperatures[$j]) {
20+
$sol[$i] = $j - $i;
21+
break;
22+
} else {
23+
if ($sol[$j] == 0) {
24+
break;
25+
}
26+
$j = $j + $sol[$j];
27+
}
28+
}
29+
}
30+
return $sol;
31+
}
32+
}

‎src/main/php/g0701_0800/s0739_daily_temperatures/readme.md

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
739\. Daily Temperatures
2+
3+
Medium
4+
5+
Given an array of integers `temperatures` represents the daily temperatures, return _an array_ `answer` _such that_ `answer[i]` _is the number of days you have to wait after the_ <code>i<sup>th</sup></code> _day to get a warmer temperature_. If there is no future day for which this is possible, keep `answer[i] == 0` instead.
6+
7+
**Example 1:**
8+
9+
**Input:** temperatures = [73,74,75,71,69,72,76,73]
10+
11+
**Output:** [1,1,4,2,1,1,0,0]
12+
13+
**Example 2:**
14+
15+
**Input:** temperatures = [30,40,50,60]
16+
17+
**Output:** [1,1,1,0]
18+
19+
**Example 3:**
20+
21+
**Input:** temperatures = [30,60,90]
22+
23+
**Output:** [1,1,0]
24+
25+
**Constraints:**
26+
27+
* <code>1 <= temperatures.length <= 10<sup>5</sup></code>
28+
* `30 <= temperatures[i] <= 100`

‎src/main/php/g0701_0800/s0763_partition_labels/Solution.php

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
<?php
2+
3+
namespace leetcode\g0701_0800\s0763_partition_labels;
4+
5+
// #Medium #Top_100_Liked_Questions #String #Hash_Table #Greedy #Two_Pointers
6+
// #Data_Structure_II_Day_7_String #Big_O_Time_O(n)_Space_O(1)
7+
// #2023_12_24_Time_5_ms_(83.33%)_Space_19.5_MB_(50.00%)
8+
9+
class Solution {
10+
/**
11+
* @param String $s
12+
* @return Integer[]
13+
*/
14+
public function partitionLabels($s) {
15+
$letters = str_split($s);
16+
$result = array();
17+
$position = array_fill(0, 26, 0);
18+
for ($i = 0; $i < count($letters); $i++) {
19+
$position[ord($letters[$i]) - ord('a')] = $i;
20+
}
21+
$i = 0;
22+
$prev = -1;
23+
$max = 0;
24+
while ($i < count($letters)) {
25+
if ($position[ord($letters[$i]) - ord('a')] > $max) {
26+
$max = $position[ord($letters[$i]) - ord('a')];
27+
}
28+
if ($i == $max) {
29+
array_push($result, $i - $prev);
30+
$prev = $i;
31+
}
32+
$i++;
33+
}
34+
return $result;
35+
}
36+
}

‎src/main/php/g0701_0800/s0763_partition_labels/readme.md

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
763\. Partition Labels
2+
3+
Medium
4+
5+
You are given a string `s`. We want to partition the string into as many parts as possible so that each letter appears in at most one part.
6+
7+
Return _a list of integers representing the size of these parts_.
8+
9+
**Example 1:**
10+
11+
**Input:** s = "ababcbacadefegdehijhklij"
12+
13+
**Output:** [9,7,8]
14+
15+
**Explanation:**
16+
17+
The partition is "ababcbaca", "defegde", "hijhklij".
18+
This is a partition so that each letter appears in at most one part.
19+
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits s into less parts.
20+
21+
**Example 2:**
22+
23+
**Input:** s = "eccbbbbdec"
24+
25+
**Output:** [10]
26+
27+
**Constraints:**
28+
29+
* `1 <= s.length <= 500`
30+
* `s` consists of lowercase English letters.

‎src/main/php/g1101_1200/s1143_longest_common_subsequence/Solution.php

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
<?php
2+
3+
namespace leetcode\g1101_1200\s1143_longest_common_subsequence;
4+
5+
// #Medium #Top_100_Liked_Questions #String #Dynamic_Programming
6+
// #Algorithm_II_Day_17_Dynamic_Programming #Dynamic_Programming_I_Day_19
7+
// #Udemy_Dynamic_Programming #Big_O_Time_O(n*m)_Space_O(n*m)
8+
// #2023_12_24_Time_191_ms_(96.00%)_Space_35.5_MB_(100.00%)
9+
10+
class Solution {
11+
/**
12+
* @param String $text1
13+
* @param String $text2
14+
* @return Integer
15+
*/
16+
public function longestCommonSubsequence($text1, $text2) {
17+
$n = strlen($text1);
18+
$m = strlen($text2);
19+
$dp = array_fill(0, $n + 1, array_fill(0, $m + 1, 0));
20+
for ($i = 1; $i <= $n; $i++) {
21+
for ($j = 1; $j <= $m; $j++) {
22+
if ($text1[$i - 1] == $text2[$j - 1]) {
23+
$dp[$i][$j] = $dp[$i - 1][$j - 1] + 1;
24+
} else {
25+
$dp[$i][$j] = max($dp[$i - 1][$j], $dp[$i][$j - 1]);
26+
}
27+
}
28+
}
29+
return $dp[$n][$m];
30+
}
31+
}

‎src/main/php/g1101_1200/s1143_longest_common_subsequence/readme.md

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
1143\. Longest Common Subsequence
2+
3+
Medium
4+
5+
Given two strings `text1` and `text2`, return _the length of their longest **common subsequence**._ If there is no **common subsequence**, return `0`.
6+
7+
A **subsequence** of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.
8+
9+
* For example, `"ace"` is a subsequence of `"abcde"`.
10+
11+
A **common subsequence** of two strings is a subsequence that is common to both strings.
12+
13+
**Example 1:**
14+
15+
**Input:** text1 = "abcde", text2 = "ace"
16+
17+
**Output:** 3
18+
19+
**Explanation:** The longest common subsequence is "ace" and its length is 3.
20+
21+
**Example 2:**
22+
23+
**Input:** text1 = "abc", text2 = "abc"
24+
25+
**Output:** 3
26+
27+
**Explanation:** The longest common subsequence is "abc" and its length is 3.
28+
29+
**Example 3:**
30+
31+
**Input:** text1 = "abc", text2 = "def"
32+
33+
**Output:** 0
34+
35+
**Explanation:** There is no such common subsequence, so the result is 0.
36+
37+
**Constraints:**
38+
39+
* `1 <= text1.length, text2.length <= 1000`
40+
* `text1` and `text2` consist of only lowercase English characters.

‎src/test/php/g0601_0700/s0647_palindromic_substrings/SolutionTest.php

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
<?php
2+
3+
namespace leetcode\g0601_0700\s0647_palindromic_substrings;
4+
5+
use PHPUnit\Framework\TestCase;
6+
7+
class SolutionTest extends TestCase {
8+
public function testCountSubstrings() {
9+
$this->assertEquals(3, (new Solution())->countSubstrings("abc"));
10+
}
11+
12+
public function testCountSubstrings2() {
13+
$this->assertEquals(6, (new Solution())->countSubstrings("aaa"));
14+
}
15+
}

0 commit comments

Comments
 (0)
0