Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit61d7d47

Browse files
authored
Added tasks 543-1143
1 parent4e1ddaa commit61d7d47

File tree

13 files changed

+384
-3
lines changed

13 files changed

+384
-3
lines changed

‎README.md‎

Lines changed: 14 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -111,7 +111,7 @@ Rust-based LeetCode algorithm problem solutions, regularly updated.
111111
|-|-|-|-|-|-
112112
| 0094 |[Binary Tree Inorder Traversal](src/main/rust/g0001_0100/s0094_binary_tree_inorder_traversal/Solution.rs)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, Depth_First_Search, Tree, Binary_Tree, Stack, Big_O_Time_O(n)_Space_O(n) | 0 | 100.00
113113
| 0102 |[Binary Tree Level Order Traversal](src/main/rust/g0101_0200/s0102_binary_tree_level_order_traversal/Solution.rs)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Breadth_First_Search, Tree, Binary_Tree, Big_O_Time_O(N)_Space_O(N) | 1 | 80.61
114-
| 0543 |[Diameter of Binary Tree](src/main/rust/g0501_0600/s0543_diameter_of_binary_tree/Solution.java)| Easy | Top_100_Liked_Questions, Depth_First_Search, Tree, Binary_Tree, Big_O_Time_O(n)_Space_O(n) |1 |65.86
114+
| 0543 |[Diameter of Binary Tree](src/main/rust/g0501_0600/s0543_diameter_of_binary_tree/Solution.rs)| Easy | Top_100_Liked_Questions, Depth_First_Search, Tree, Binary_Tree, Big_O_Time_O(n)_Space_O(n) |0 |100.00
115115
| 0226 |[Invert Binary Tree](src/main/rust/g0201_0300/s0226_invert_binary_tree/Solution.rs)| Easy | Top_100_Liked_Questions, Depth_First_Search, Breadth_First_Search, Tree, Binary_Tree, Big_O_Time_O(n)_Space_O(n) | 0 | 100.00
116116
| 0104 |[Maximum Depth of Binary Tree](src/main/rust/g0101_0200/s0104_maximum_depth_of_binary_tree/Solution.rs)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, Depth_First_Search, Breadth_First_Search, Tree, Binary_Tree, Big_O_Time_O(N)_Space_O(H) | 1 | 80.46
117117
| 0124 |[Binary Tree Maximum Path Sum](src/main/rust/g0101_0200/s0124_binary_tree_maximum_path_sum/Solution.rs)| Hard | Top_100_Liked_Questions, Top_Interview_Questions, Dynamic_Programming, Depth_First_Search, Tree, Binary_Tree, Big_O_Time_O(N)_Space_O(N) | 0 | 100.00
@@ -140,6 +140,7 @@ Rust-based LeetCode algorithm problem solutions, regularly updated.
140140
| 0070 |[Climbing Stairs](src/main/rust/g0001_0100/s0070_climbing_stairs/Solution.rs)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, Dynamic_Programming, Math, Memoization, Big_O_Time_O(n)_Space_O(n) | 0 | 100.00
141141
| 0064 |[Minimum Path Sum](src/main/rust/g0001_0100/s0064_minimum_path_sum/Solution.rs)| Medium | Top_100_Liked_Questions, Array, Dynamic_Programming, Matrix, Big_O_Time_O(m\*n)_Space_O(m\*n) | 0 | 100.00
142142
| 0300 |[Longest Increasing Subsequence](src/main/rust/g0201_0300/s0300_longest_increasing_subsequence/Solution.rs)| Medium | Top_100_Liked_Questions, Array, Dynamic_Programming, Binary_Search, Big_O_Time_O(n\*log_n)_Space_O(n) | 0 | 100.00
143+
| 1143 |[Longest Common Subsequence](src/main/rust/g1101_1200/s1143_longest_common_subsequence/Solution.rs)| Medium | Top_100_Liked_Questions, String, Dynamic_Programming, Big_O_Time_O(n\*m)_Space_O(n\*m) | 4 | 78.99
143144
| 0072 |[Edit Distance](src/main/rust/g0001_0100/s0072_edit_distance/Solution.rs)| Medium | Top_100_Liked_Questions, String, Dynamic_Programming, Big_O_Time_O(n^2)_Space_O(n2) | 0 | 100.00
144145
| 0010 |[Regular Expression Matching](src/main/rust/g0001_0100/s0010_regular_expression_matching/Solution.rs)| Hard | Top_Interview_Questions, String, Dynamic_Programming, Recursion, Big_O_Time_O(m\*n)_Space_O(m\*n) | 0 | 100.00
145146

@@ -284,6 +285,7 @@ Rust-based LeetCode algorithm problem solutions, regularly updated.
284285
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
285286
|-|-|-|-|-|-
286287
| 0238 |[Product of Array Except Self](src/main/rust/g0201_0300/s0238_product_of_array_except_self/Solution.rs)| Medium | Top_100_Liked_Questions, Array, Prefix_Sum, Big_O_Time_O(n^2)_Space_O(n) | 8 | 87.13
288+
| 0560 |[Subarray Sum Equals K](src/main/rust/g0501_0600/s0560_subarray_sum_equals_k/Solution.rs)| Medium | Top_100_Liked_Questions, Array, Hash_Table, Prefix_Sum, Big_O_Time_O(n)_Space_O(n) | 7 | 96.88
287289

288290
####Day 6 String
289291

@@ -294,6 +296,7 @@ Rust-based LeetCode algorithm problem solutions, regularly updated.
294296

295297
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
296298
|-|-|-|-|-|-
299+
| 0763 |[Partition Labels](src/main/rust/g0701_0800/s0763_partition_labels/Solution.rs)| Medium | String, Hash_Table, Greedy, Two_Pointers, Big_O_Time_O(n)_Space_O(1) | 1 | 97.06
297300

298301
####Day 8 String
299302

@@ -564,6 +567,7 @@ Rust-based LeetCode algorithm problem solutions, regularly updated.
564567

565568
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
566569
|-|-|-|-|-|-
570+
| 1143 |[Longest Common Subsequence](src/main/rust/g1101_1200/s1143_longest_common_subsequence/Solution.rs)| Medium | Top_100_Liked_Questions, String, Dynamic_Programming, Big_O_Time_O(n\*m)_Space_O(n\*m) | 4 | 78.99
567571

568572
####Day 18 Dynamic Programming
569573

@@ -870,6 +874,7 @@ Rust-based LeetCode algorithm problem solutions, regularly updated.
870874

871875
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
872876
|-|-|-|-|-|-
877+
| 1143 |[Longest Common Subsequence](src/main/rust/g1101_1200/s1143_longest_common_subsequence/Solution.rs)| Medium | Top_100_Liked_Questions, String, Dynamic_Programming, Big_O_Time_O(n\*m)_Space_O(n\*m) | 4 | 78.99
873878
| 0072 |[Edit Distance](src/main/rust/g0001_0100/s0072_edit_distance/Solution.rs)| Medium | Top_100_Liked_Questions, String, Dynamic_Programming, Big_O_Time_O(n^2)_Space_O(n2) | 0 | 100.00
874879

875880
####Day 20
@@ -978,6 +983,7 @@ Rust-based LeetCode algorithm problem solutions, regularly updated.
978983

979984
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
980985
|-|-|-|-|-|-
986+
| 0739 |[Daily Temperatures](src/main/rust/g0701_0800/s0739_daily_temperatures/Solution.rs)| Medium | Top_100_Liked_Questions, Array, Stack, Monotonic_Stack, Big_O_Time_O(n)_Space_O(n) | 33 | 91.80
981987

982988
####Day 7
983989

@@ -1307,7 +1313,7 @@ Rust-based LeetCode algorithm problem solutions, regularly updated.
13071313

13081314
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
13091315
|-|-|-|-|-|-
1310-
| 0543 |[Diameter of Binary Tree](src/main/rust/g0501_0600/s0543_diameter_of_binary_tree/Solution.java)| Easy | Top_100_Liked_Questions, Depth_First_Search, Tree, Binary_Tree, Big_O_Time_O(n)_Space_O(n) |1 |65.86
1316+
| 0543 |[Diameter of Binary Tree](src/main/rust/g0501_0600/s0543_diameter_of_binary_tree/Solution.rs)| Easy | Top_100_Liked_Questions, Depth_First_Search, Tree, Binary_Tree, Big_O_Time_O(n)_Space_O(n) |0 |100.00
13111317
| 0437 |[Path Sum III](src/main/rust/g0401_0500/s0437_path_sum_iii/Solution.rs)| Medium | Depth_First_Search, Tree, Binary_Tree, Big_O_Time_O(n)_Space_O(n) | 0 | 100.00
13121318

13131319
####Day 8 Binary Search
@@ -1394,7 +1400,12 @@ Rust-based LeetCode algorithm problem solutions, regularly updated.
13941400

13951401
| # | Title | Difficulty | Tag | Time, ms | Time, %
13961402
|------|----------------|-------------|-------------|----------|---------
1397-
| 0543 |[Diameter of Binary Tree](src/main/rust/g0501_0600/s0543_diameter_of_binary_tree/Solution.java)| 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) | 1 | 65.86
1403+
| 1143 |[Longest Common Subsequence](src/main/rust/g1101_1200/s1143_longest_common_subsequence/Solution.rs)| 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) | 4 | 78.99
1404+
| 0763 |[Partition Labels](src/main/rust/g0701_0800/s0763_partition_labels/Solution.rs)| Medium | String, Hash_Table, Greedy, Two_Pointers, Data_Structure_II_Day_7_String, Big_O_Time_O(n)_Space_O(1) | 1 | 97.06
1405+
| 0739 |[Daily Temperatures](src/main/rust/g0701_0800/s0739_daily_temperatures/Solution.rs)| Medium | Top_100_Liked_Questions, Array, Stack, Monotonic_Stack, Programming_Skills_II_Day_6, Big_O_Time_O(n)_Space_O(n) | 33 | 91.80
1406+
| 0647 |[Palindromic Substrings](src/main/rust/g0601_0700/s0647_palindromic_substrings/Solution.rs)| Medium | String, Dynamic_Programming, Big_O_Time_O(n^2)_Space_O(n) | 0 | 100.00
1407+
| 0560 |[Subarray Sum Equals K](src/main/rust/g0501_0600/s0560_subarray_sum_equals_k/Solution.rs)| Medium | Top_100_Liked_Questions, Array, Hash_Table, Prefix_Sum, Data_Structure_II_Day_5_Array, Big_O_Time_O(n)_Space_O(n) | 7 | 96.88
1408+
| 0543 |[Diameter of Binary Tree](src/main/rust/g0501_0600/s0543_diameter_of_binary_tree/Solution.rs)| 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
13981409
| 0494 |[Target Sum](src/main/rust/g0401_0500/s0494_target_sum/Solution.rs)| Medium | Array, Dynamic_Programming, Backtracking, Big_O_Time_O(n\*(sum+s))_Space_O(n\*(sum+s)) | 3 | 83.33
13991410
| 0438 |[Find All Anagrams in a String](src/main/rust/g0401_0500/s0438_find_all_anagrams_in_a_string/Solution.rs)| 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) | 2 | 89.29
14001411
| 0437 |[Path Sum III](src/main/rust/g0401_0500/s0437_path_sum_iii/Solution.rs)| Medium | Depth_First_Search, Tree, Binary_Tree, Level_2_Day_7_Tree, Big_O_Time_O(n)_Space_O(n) | 0 | 100.00
Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
// #Easy #Top_100_Liked_Questions #Depth_First_Search #Tree #Binary_Tree #Level_2_Day_7_Tree
2+
// #Udemy_Tree_Stack_Queue #Big_O_Time_O(n)_Space_O(n)
3+
// #2024_09_13_Time_0_ms_(100.00%)_Space_3.9_MB_(13.76%)
4+
5+
// Definition for a binary tree node.
6+
// #[derive(Debug, PartialEq, Eq)]
7+
// pub struct TreeNode {
8+
// pub val: i32,
9+
// pub left: Option<Rc<RefCell<TreeNode>>>,
10+
// pub right: Option<Rc<RefCell<TreeNode>>>,
11+
// }
12+
//
13+
// impl TreeNode {
14+
// #[inline]
15+
// pub fn new(val: i32) -> Self {
16+
// TreeNode {
17+
// val,
18+
// left: None,
19+
// right: None
20+
// }
21+
// }
22+
// }
23+
use std::rc::Rc;
24+
use std::cell::RefCell;
25+
use std::cmp::max;
26+
implSolution{
27+
pubfndiameter_of_binary_tree(root:Option<Rc<RefCell<TreeNode>>>) ->i32{
28+
letmut diameter =0;
29+
30+
fnhelper(root:Option<Rc<RefCell<TreeNode>>>,diameter:&muti32) ->(i32,i32){
31+
ifletSome(root) = root{
32+
let(l1, l2) =helper(root.borrow().left.clone(), diameter);
33+
let(r1, r2) =helper(root.borrow().right.clone(), diameter);
34+
35+
*diameter =max(*diameter, l1 + l2);
36+
*diameter =max(*diameter, r1 + r2);
37+
38+
let l = l1.max(l2) +1;
39+
let r = r1.max(r2) +1;
40+
return(l, r);
41+
}
42+
43+
// (depth, diameter that doesn't pass through )
44+
(-1, -1)
45+
}
46+
47+
let(l, r) =helper(root,&mut diameter);
48+
diameter =max(diameter, l + r);
49+
diameter
50+
}
51+
}
Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
543\. Diameter of Binary Tree
2+
3+
Easy
4+
5+
Given the`root` of a binary tree, return_the length of the**diameter** of the tree_.
6+
7+
The**diameter** of a binary tree is the**length** of the longest path between any two nodes in a tree. This path may or may not pass through the`root`.
8+
9+
The**length** of a path between two nodes is represented by the number of edges between them.
10+
11+
**Example 1:**
12+
13+
![](https://assets.leetcode.com/uploads/2021/03/06/diamtree.jpg)
14+
15+
**Input:** root =[1,2,3,4,5]
16+
17+
**Output:** 3
18+
19+
**Explanation:** 3 is the length of the path[4,2,1,3] or[5,2,1,3].
20+
21+
**Example 2:**
22+
23+
**Input:** root =[1,2]
24+
25+
**Output:** 1
26+
27+
**Constraints:**
28+
29+
* The number of nodes in the tree is in the range <code>[1, 10<sup>4</sup>]</code>.
30+
*`-100 <= Node.val <= 100`
Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
// #Medium #Top_100_Liked_Questions #Array #Hash_Table #Prefix_Sum #Data_Structure_II_Day_5_Array
2+
// #Big_O_Time_O(n)_Space_O(n) #2024_09_13_Time_7_ms_(96.88%)_Space_2.8_MB_(25.00%)
3+
4+
use std::collections::HashMap;
5+
6+
implSolution{
7+
pubfnsubarray_sum(nums:Vec<i32>,k:i32) ->i32{
8+
letmut temp_sum =0;
9+
letmut ret =0;
10+
letmut sum_count:HashMap<i32,i32> =HashMap::new();
11+
sum_count.insert(0,1);
12+
13+
for&numin nums.iter(){
14+
temp_sum += num;
15+
ifletSome(&count) = sum_count.get(&(temp_sum - k)){
16+
ret += count;
17+
}
18+
let entry = sum_count.entry(temp_sum).or_insert(0);
19+
*entry +=1;
20+
}
21+
22+
ret
23+
}
24+
}
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
560\. Subarray Sum Equals K
2+
3+
Medium
4+
5+
Given an array of integers`nums` and an integer`k`, return_the total number of subarrays whose sum equals to_`k`.
6+
7+
A subarray is a contiguous**non-empty** sequence of elements within an array.
8+
9+
**Example 1:**
10+
11+
**Input:** nums =[1,1,1], k = 2
12+
13+
**Output:** 2
14+
15+
**Example 2:**
16+
17+
**Input:** nums =[1,2,3], k = 3
18+
19+
**Output:** 2
20+
21+
**Constraints:**
22+
23+
* <code>1 <= nums.length <= 2 * 10<sup>4</sup></code>
24+
*`-1000 <= nums[i] <= 1000`
25+
* <code>-10<sup>7</sup> <= k <= 10<sup>7</sup></code>
Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
// #Medium #String #Dynamic_Programming #Big_O_Time_O(n^2)_Space_O(n)
2+
// #2024_09_13_Time_0_ms_(100.00%)_Space_2.2_MB_(38.46%)
3+
4+
implSolution{
5+
fnexpand(s:&[char],mutl:i32,mutr:i32,res:&muti32){
6+
while l >=0 &&(rasusize) < s.len(){
7+
if s[lasusize] != s[rasusize]{
8+
return;
9+
}else{
10+
*res +=1;
11+
l -=1;
12+
r +=1;
13+
}
14+
}
15+
}
16+
17+
pubfncount_substrings(s:String) ->i32{
18+
let a:Vec<char> = s.chars().collect();
19+
letmut res =0;
20+
for iin0..a.len(){
21+
Solution::expand(&a, iasi32, iasi32,&mut res);// Odd length palindromes
22+
Solution::expand(&a, iasi32,(i +1)asi32,&mut res);// Even length palindromes
23+
}
24+
res
25+
}
26+
}
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.
Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
// #Medium #Top_100_Liked_Questions #Array #Stack #Monotonic_Stack #Programming_Skills_II_Day_6
2+
// #Big_O_Time_O(n)_Space_O(n) #2024_09_13_Time_33_ms_(91.80%)_Space_3.4_MB_(99.45%)
3+
4+
implSolution{
5+
pubfndaily_temperatures(temperatures:Vec<i32>) ->Vec<i32>{
6+
letmut sol =vec![0; temperatures.len()];
7+
for iin(0..temperatures.len() -1).rev(){
8+
letmut j = i +1;
9+
while j < temperatures.len(){
10+
if temperatures[i] < temperatures[j]{
11+
sol[i] =(j - i)asi32;
12+
break;
13+
}elseif sol[j] ==0{
14+
break;
15+
}
16+
j += sol[j]asusize;
17+
}
18+
}
19+
sol
20+
}
21+
}
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`
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
// #Medium #String #Hash_Table #Greedy #Two_Pointers #Data_Structure_II_Day_7_String
2+
// #Big_O_Time_O(n)_Space_O(1) #2024_09_13_Time_1_ms_(97.06%)_Space_2.1_MB_(41.18%)
3+
4+
implSolution{
5+
pubfnpartition_labels(s:String) ->Vec<i32>{
6+
let letters:Vec<char> = s.chars().collect();
7+
letmut result =Vec::new();
8+
letmut position =vec![0;26];
9+
10+
// Store the last occurrence of each letter in the string
11+
for(i,&ch)in letters.iter().enumerate(){
12+
position[(chasusize) -('a'asusize)] = i;
13+
}
14+
15+
letmut i =0;
16+
letmut prev = -1;
17+
letmut max =0;
18+
19+
// Iterate over the string to find partitions
20+
while i < letters.len(){
21+
let ch_pos = position[(letters[i]asusize) -('a'asusize)];
22+
if ch_pos > max{
23+
max = ch_pos;
24+
}
25+
26+
if i == max{
27+
result.push((iasi32) -(prevasi32));
28+
prev = iasi32;
29+
}
30+
31+
i +=1;
32+
}
33+
34+
result
35+
}
36+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp