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

Commit073885f

Browse files
authored
Added tasks 121-153
1 parent6eb92c8 commit073885f

File tree

21 files changed

+759
-0
lines changed

21 files changed

+759
-0
lines changed

‎README.md‎

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -30,6 +30,7 @@ Rust-based LeetCode algorithm problem solutions, regularly updated.
3030

3131
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
3232
|-|-|-|-|-|-
33+
| 0136 |[Single Number](src/main/rust/g0101_0200/s0136_single_number/Solution.rs)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, Array, Bit_Manipulation, Big_O_Time_O(N)_Space_O(1) | 0 | 100.00
3334
| 0007 |[Reverse Integer](src/main/rust/g0001_0100/s0007_reverse_integer/Solution.rs)| Medium | Top_Interview_Questions, Math | 0 | 100.00
3435
| 0009 |[Palindrome Number](src/main/rust/g0001_0100/s0009_palindrome_number/Solution.rs)| Easy | Math | 0 | 100.00
3536

@@ -47,11 +48,13 @@ Rust-based LeetCode algorithm problem solutions, regularly updated.
4748
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
4849
|-|-|-|-|-|-
4950
| 0033 |[Search in Rotated Sorted Array](src/main/rust/g0001_0100/s0033_search_in_rotated_sorted_array/Solution.rs)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Binary_Search, Big_O_Time_O(log_n)_Space_O(1) | 0 | 100.00
51+
| 0153 |[Find Minimum in Rotated Sorted Array](src/main/rust/g0101_0200/s0153_find_minimum_in_rotated_sorted_array/Solution.rs)| Medium | Top_100_Liked_Questions, Array, Binary_Search, Big_O_Time_O(log_N)_Space_O(log_N) | 1 | 77.10
5052

5153
####Udemy Arrays
5254

5355
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
5456
|-|-|-|-|-|-
57+
| 0121 |[Best Time to Buy and Sell Stock](src/main/rust/g0101_0200/s0121_best_time_to_buy_and_sell_stock/Solution.rs)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, Array, Dynamic_Programming, Big_O_Time_O(N)_Space_O(1) | 3 | 98.62
5558
| 0001 |[Two Sum](src/main/rust/g0001_0100/s0001_two_sum/Solution.rs)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, Array, Hash_Table, Big_O_Time_O(n)_Space_O(n) | 0 | 100.00
5659
| 0055 |[Jump Game](src/main/rust/g0001_0100/s0055_jump_game/Solution.rs)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Dynamic_Programming, Greedy, Big_O_Time_O(n)_Space_O(1) | 0 | 100.00
5760
| 0075 |[Sort Colors](src/main/rust/g0001_0100/s0075_sort_colors/Solution.rs)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Sorting, Two_Pointers, Big_O_Time_O(n)_Space_O(1) | 0 | 100.00
@@ -92,6 +95,7 @@ Rust-based LeetCode algorithm problem solutions, regularly updated.
9295
| 0024 |[Swap Nodes in Pairs](src/main/rust/g0001_0100/s0024_swap_nodes_in_pairs/Solution.rs)| Medium | Top_100_Liked_Questions, Linked_List, Recursion, Big_O_Time_O(n)_Space_O(1) | 0 | 100.00
9396
| 0021 |[Merge Two Sorted Lists](src/main/rust/g0001_0100/s0021_merge_two_sorted_lists/Solution.rs)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, Linked_List, Recursion, Big_O_Time_O(m+n)_Space_O(m+n) | 0 | 100.00
9497
| 0025 |[Reverse Nodes in k-Group](src/main/rust/g0001_0100/s0025_reverse_nodes_in_k_group/Solution.rs)| Hard | Top_100_Liked_Questions, Linked_List, Recursion, Big_O_Time_O(n)_Space_O(k) | 0 | 100.00
98+
| 0146 |[LRU Cache](src/main/rust/g0101_0200/s0146_lru_cache/LRUCache.rs)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Hash_Table, Design, Linked_List, Doubly_Linked_List, Big_O_Time_O(1)_Space_O(capacity) | 90 | 75.18
9599

96100
####Udemy Tree Stack Queue
97101

@@ -100,6 +104,7 @@ Rust-based LeetCode algorithm problem solutions, regularly updated.
100104
| 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
101105
| 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
102106
| 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
107+
| 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
103108
| 0098 |[Validate Binary Search Tree](src/main/rust/g0001_0100/s0098_validate_binary_search_tree/Solution.rs)| Medium | String, Dynamic_Programming | 1 | 77.46
104109

105110
####Udemy Trie and Heap
@@ -116,6 +121,8 @@ Rust-based LeetCode algorithm problem solutions, regularly updated.
116121

117122
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
118123
|-|-|-|-|-|-
124+
| 0139 |[Word Break](src/main/rust/g0101_0200/s0139_word_break/Solution.rs)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, String, Hash_Table, Dynamic_Programming, Trie, Memoization, Big_O_Time_O(M+max\*N)_Space_O(M+N+max) | 0 | 100.00
125+
| 0152 |[Maximum Product Subarray](src/main/rust/g0101_0200/s0152_maximum_product_subarray/Solution.rs)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Dynamic_Programming, Big_O_Time_O(N)_Space_O(1) | 1 | 71.23
119126
| 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
120127
| 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
121128
| 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
@@ -159,6 +166,7 @@ Rust-based LeetCode algorithm problem solutions, regularly updated.
159166

160167
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
161168
|-|-|-|-|-|-
169+
| 0121 |[Best Time to Buy and Sell Stock](src/main/rust/g0101_0200/s0121_best_time_to_buy_and_sell_stock/Solution.rs)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, Array, Dynamic_Programming, Big_O_Time_O(N)_Space_O(1) | 3 | 98.62
162170

163171
####Day 4 Array
164172

@@ -229,6 +237,7 @@ Rust-based LeetCode algorithm problem solutions, regularly updated.
229237

230238
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
231239
|-|-|-|-|-|-
240+
| 0136 |[Single Number](src/main/rust/g0101_0200/s0136_single_number/Solution.rs)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, Array, Bit_Manipulation, Big_O_Time_O(N)_Space_O(1) | 0 | 100.00
232241
| 0015 |[3Sum](src/main/rust/g0001_0100/s0015_3sum/Solution.rs)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Sorting, Two_Pointers, Big_O_Time_O(n\*log(n))_Space_O(n^2) | 27 | 81.94
233242

234243
####Day 2 Array
@@ -417,6 +426,7 @@ Rust-based LeetCode algorithm problem solutions, regularly updated.
417426

418427
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
419428
|-|-|-|-|-|-
429+
| 0136 |[Single Number](src/main/rust/g0101_0200/s0136_single_number/Solution.rs)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, Array, Bit_Manipulation, Big_O_Time_O(N)_Space_O(1) | 0 | 100.00
420430

421431
###Algorithm II
422432

@@ -432,6 +442,7 @@ Rust-based LeetCode algorithm problem solutions, regularly updated.
432442

433443
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
434444
|-|-|-|-|-|-
445+
| 0153 |[Find Minimum in Rotated Sorted Array](src/main/rust/g0101_0200/s0153_find_minimum_in_rotated_sorted_array/Solution.rs)| Medium | Top_100_Liked_Questions, Array, Binary_Search, Big_O_Time_O(log_N)_Space_O(log_N) | 1 | 77.10
435446

436447
####Day 3 Two Pointers
437448

@@ -508,6 +519,7 @@ Rust-based LeetCode algorithm problem solutions, regularly updated.
508519

509520
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
510521
|-|-|-|-|-|-
522+
| 0139 |[Word Break](src/main/rust/g0101_0200/s0139_word_break/Solution.rs)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, String, Hash_Table, Dynamic_Programming, Trie, Memoization, Big_O_Time_O(M+max\*N)_Space_O(M+N+max) | 0 | 100.00
511523

512524
####Day 16 Dynamic Programming
513525

@@ -605,6 +617,7 @@ Rust-based LeetCode algorithm problem solutions, regularly updated.
605617

606618
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
607619
|-|-|-|-|-|-
620+
| 0153 |[Find Minimum in Rotated Sorted Array](src/main/rust/g0101_0200/s0153_find_minimum_in_rotated_sorted_array/Solution.rs)| Medium | Top_100_Liked_Questions, Array, Binary_Search, Big_O_Time_O(log_N)_Space_O(log_N) | 1 | 77.10
608621

609622
###Binary Search II
610623

@@ -743,11 +756,13 @@ Rust-based LeetCode algorithm problem solutions, regularly updated.
743756

744757
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
745758
|-|-|-|-|-|-
759+
| 0152 |[Maximum Product Subarray](src/main/rust/g0101_0200/s0152_maximum_product_subarray/Solution.rs)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Dynamic_Programming, Big_O_Time_O(N)_Space_O(1) | 1 | 71.23
746760

747761
####Day 7
748762

749763
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
750764
|-|-|-|-|-|-
765+
| 0121 |[Best Time to Buy and Sell Stock](src/main/rust/g0101_0200/s0121_best_time_to_buy_and_sell_stock/Solution.rs)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, Array, Dynamic_Programming, Big_O_Time_O(N)_Space_O(1) | 3 | 98.62
751766

752767
####Day 8
753768

@@ -758,6 +773,7 @@ Rust-based LeetCode algorithm problem solutions, regularly updated.
758773

759774
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
760775
|-|-|-|-|-|-
776+
| 0139 |[Word Break](src/main/rust/g0101_0200/s0139_word_break/Solution.rs)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, String, Hash_Table, Dynamic_Programming, Trie, Memoization, Big_O_Time_O(M+max\*N)_Space_O(M+N+max) | 0 | 100.00
761777
| 0042 |[Trapping Rain Water](src/main/rust/g0001_0100/s0042_trapping_rain_water/Solution.rs)| Hard | Top_100_Liked_Questions, Top_Interview_Questions, Array, Dynamic_Programming, Two_Pointers, Stack, Monotonic_Stack, Big_O_Time_O(n)_Space_O(1) | 0 | 100.00
762778

763779
####Day 10
@@ -1144,6 +1160,7 @@ Rust-based LeetCode algorithm problem solutions, regularly updated.
11441160

11451161
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
11461162
|-|-|-|-|-|-
1163+
| 0121 |[Best Time to Buy and Sell Stock](src/main/rust/g0101_0200/s0121_best_time_to_buy_and_sell_stock/Solution.rs)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, Array, Dynamic_Programming, Big_O_Time_O(N)_Space_O(1) | 3 | 98.62
11471164

11481165
####Day 6 Tree
11491166

@@ -1222,6 +1239,7 @@ Rust-based LeetCode algorithm problem solutions, regularly updated.
12221239

12231240
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
12241241
|-|-|-|-|-|-
1242+
| 0148 |[Sort List](src/main/rust/g0101_0200/s0148_sort_list/Solution.rs)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Sorting, Two_Pointers, Linked_List, Divide_and_Conquer, Merge_Sort, Big_O_Time_O(log(N))_Space_O(log(N)) | 21 | 81.82
12251243

12261244
####Day 5 Greedy
12271245

@@ -1269,6 +1287,7 @@ Rust-based LeetCode algorithm problem solutions, regularly updated.
12691287

12701288
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
12711289
|-|-|-|-|-|-
1290+
| 0152 |[Maximum Product Subarray](src/main/rust/g0101_0200/s0152_maximum_product_subarray/Solution.rs)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Dynamic_Programming, Big_O_Time_O(N)_Space_O(1) | 1 | 71.23
12721291

12731292
####Day 14 Sliding Window/Two Pointer
12741293

@@ -1315,6 +1334,16 @@ Rust-based LeetCode algorithm problem solutions, regularly updated.
13151334

13161335
| # | Title | Difficulty | Tag | Time, ms | Time, %
13171336
|------|----------------|-------------|-------------|----------|---------
1337+
| 0153 |[Find Minimum in Rotated Sorted Array](src/main/rust/g0101_0200/s0153_find_minimum_in_rotated_sorted_array/Solution.rs)| Medium | Top_100_Liked_Questions, Array, Binary_Search, Algorithm_II_Day_2_Binary_Search, Binary_Search_I_Day_12, Udemy_Binary_Search, Big_O_Time_O(log_N)_Space_O(log_N) | 1 | 77.10
1338+
| 0152 |[Maximum Product Subarray](src/main/rust/g0101_0200/s0152_maximum_product_subarray/Solution.rs)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Dynamic_Programming, Dynamic_Programming_I_Day_6, Level_2_Day_13_Dynamic_Programming, Udemy_Dynamic_Programming, Big_O_Time_O(N)_Space_O(1) | 1 | 71.23
1339+
| 0148 |[Sort List](src/main/rust/g0101_0200/s0148_sort_list/Solution.rs)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Sorting, Two_Pointers, Linked_List, Divide_and_Conquer, Merge_Sort, Level_2_Day_4_Linked_List, Big_O_Time_O(log(N))_Space_O(log(N)) | 21 | 81.82
1340+
| 0146 |[LRU Cache](src/main/rust/g0101_0200/s0146_lru_cache/LRUCache.rs)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Hash_Table, Design, Linked_List, Doubly_Linked_List, Udemy_Linked_List, Big_O_Time_O(1)_Space_O(capacity) | 90 | 75.18
1341+
| 0139 |[Word Break](src/main/rust/g0101_0200/s0139_word_break/Solution.rs)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, String, Hash_Table, Dynamic_Programming, Trie, Memoization, Algorithm_II_Day_15_Dynamic_Programming, Dynamic_Programming_I_Day_9, Udemy_Dynamic_Programming, Big_O_Time_O(M+max\*N)_Space_O(M+N+max) | 0 | 100.00
1342+
| 0136 |[Single Number](src/main/rust/g0101_0200/s0136_single_number/Solution.rs)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, Array, Bit_Manipulation, Data_Structure_II_Day_1_Array, Algorithm_I_Day_14_Bit_Manipulation, Udemy_Integers, Big_O_Time_O(N)_Space_O(1) | 0 | 100.00
1343+
| 0131 |[Palindrome Partitioning](src/main/rust/g0101_0200/s0131_palindrome_partitioning/Solution.rs)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, String, Dynamic_Programming, Backtracking, Big_O_Time_O(N\*2^N)_Space_O(2^N\*N) | 65 | 85.18
1344+
| 0128 |[Longest Consecutive Sequence](src/main/rust/g0101_0200/s0128_longest_consecutive_sequence/Solution.rs)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Hash_Table, Union_Find, Big_O_Time_O(N_log_N)_Space_O(1) | 4 | 99.44
1345+
| 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, Udemy_Tree_Stack_Queue, Big_O_Time_O(N)_Space_O(N) | 0 | 100.00
1346+
| 0121 |[Best Time to Buy and Sell Stock](src/main/rust/g0101_0200/s0121_best_time_to_buy_and_sell_stock/Solution.rs)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, Array, Dynamic_Programming, Data_Structure_I_Day_3_Array, Dynamic_Programming_I_Day_7, Level_1_Day_5_Greedy, Udemy_Arrays, Big_O_Time_O(N)_Space_O(1) | 3 | 98.62
13181347
| 0114 |[Flatten Binary Tree to Linked List](src/main/rust/g0101_0200/s0114_flatten_binary_tree_to_linked_list/Solution.rs)| Medium | Array, Hash_Table, Tree, Binary_Tree, Divide_and_Conquer | 0 | 100.00
13191348
| 0105 |[Construct Binary Tree from Preorder and Inorder Traversal](src/main/rust/g0101_0200/s0105_construct_binary_tree_from_preorder_and_inorder_traversal/Solution.rs)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Hash_Table, Tree, Binary_Tree, Divide_and_Conquer, Data_Structure_II_Day_15_Tree, Big_O_Time_O(N)_Space_O(N) | 2 | 84.72
13201349
| 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, Data_Structure_I_Day_11_Tree, Programming_Skills_I_Day_10_Linked_List_and_Tree, Udemy_Tree_Stack_Queue, Big_O_Time_O(N)_Space_O(H) | 1 | 80.46
Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
// #Easy #Top_100_Liked_Questions #Top_Interview_Questions #Array #Dynamic_Programming
2+
// #Data_Structure_I_Day_3_Array #Dynamic_Programming_I_Day_7 #Level_1_Day_5_Greedy #Udemy_Arrays
3+
// #Big_O_Time_O(N)_Space_O(1) #2024_09_09_Time_3_ms_(98.62%)_Space_3_MB_(9.92%)
4+
5+
6+
implSolution{
7+
pubfnmax_profit(prices:Vec<i32>) ->i32{
8+
letmut max_profit =0;
9+
letmut min_price = prices[0];
10+
11+
for pricein prices.iter().skip(1){
12+
if*price > min_price{
13+
max_profit = max_profit.max(*price - min_price);
14+
}else{
15+
min_price =*price;
16+
}
17+
}
18+
19+
max_profit
20+
}
21+
}
Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
121\. Best Time to Buy and Sell Stock
2+
3+
Easy
4+
5+
You are given an array`prices` where`prices[i]` is the price of a given stock on the <code>i<sup>th</sup></code> day.
6+
7+
You want to maximize your profit by choosing a**single day** to buy one stock and choosing a**different day in the future** to sell that stock.
8+
9+
Return_the maximum profit you can achieve from this transaction_. If you cannot achieve any profit, return`0`.
10+
11+
**Example 1:**
12+
13+
**Input:** prices =[7,1,5,3,6,4]
14+
15+
**Output:** 5
16+
17+
**Explanation:** Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
18+
19+
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
20+
21+
**Example 2:**
22+
23+
**Input:** prices =[7,6,4,3,1]
24+
25+
**Output:** 0
26+
27+
**Explanation:** In this case, no transactions are done and the max profit = 0.
28+
29+
**Constraints:**
30+
31+
* <code>1 <= prices.length <= 10<sup>5</sup></code>
32+
* <code>0 <= prices[i] <= 10<sup>4</sup></code>
Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
// #Hard #Top_100_Liked_Questions #Top_Interview_Questions #Dynamic_Programming #Depth_First_Search
2+
// #Tree #Binary_Tree #Udemy_Tree_Stack_Queue #Big_O_Time_O(N)_Space_O(N)
3+
// #2024_09_09_Time_0_ms_(100.00%)_Space_4.3_MB_(90.79%)
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+
implSolution{
26+
pubfnmax_path_sum(root:Option<Rc<RefCell<TreeNode>>>) ->i32{
27+
letmut max = i32::MIN;
28+
Solution::helper(&root,&mut max);
29+
max
30+
}
31+
32+
fnhelper(node:&Option<Rc<RefCell<TreeNode>>>,max:&muti32) ->i32{
33+
ifletSome(n) = node{
34+
let n = n.borrow();
35+
let left =Solution::helper(&n.left, max).max(0);
36+
let right =Solution::helper(&n.right, max).max(0);
37+
let current = n.val + left + right;
38+
*max =(*max).max(current);
39+
return n.val + left.max(right);
40+
}
41+
0
42+
}
43+
}
Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
124\. Binary Tree Maximum Path Sum
2+
3+
Hard
4+
5+
A**path** in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence**at most once**. Note that the path does not need to pass through the root.
6+
7+
The**path sum** of a path is the sum of the node's values in the path.
8+
9+
Given the`root` of a binary tree, return_the maximum**path sum** of any**non-empty** path_.
10+
11+
**Example 1:**
12+
13+
![](https://assets.leetcode.com/uploads/2020/10/13/exx1.jpg)
14+
15+
**Input:** root =[1,2,3]
16+
17+
**Output:** 6
18+
19+
**Explanation:** The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.
20+
21+
**Example 2:**
22+
23+
![](https://assets.leetcode.com/uploads/2020/10/13/exx2.jpg)
24+
25+
**Input:** root =[-10,9,20,null,null,15,7]
26+
27+
**Output:** 42
28+
29+
**Explanation:** The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.
30+
31+
**Constraints:**
32+
33+
* The number of nodes in the tree is in the range <code>[1, 3 * 10<sup>4</sup>]</code>.
34+
*`-1000 <= Node.val <= 1000`

0 commit comments

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