🌐 AI搜索 & 代理 主页
Skip to content

Commit da4f62c

Browse files
authored
Added tasks 79-114
1 parent 71b18a7 commit da4f62c

File tree

21 files changed

+848
-0
lines changed

21 files changed

+848
-0
lines changed

README.md

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -109,6 +109,7 @@ C-based LeetCode algorithm problem solutions, regularly updated.
109109

110110
| <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- -->
111111
|-|-|-|-|-|-
112+
| 0105 |[Construct Binary Tree from Preorder and Inorder Traversal](src/main/c/g0101_0200/s0105_construct_binary_tree_from_preorder_and_inorder_traversal/Solution.c)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Hash_Table, Tree, Binary_Tree, Divide_and_Conquer, Big_O_Time_O(N)_Space_O(N) | 3 | 95.24
112113

113114
#### Day 16 Tree
114115

@@ -283,6 +284,7 @@ C-based LeetCode algorithm problem solutions, regularly updated.
283284
|-|-|-|-|-|-
284285
| 0017 |[Letter Combinations of a Phone Number](src/main/c/g0001_0100/s0017_letter_combinations_of_a_phone_number/Solution.c)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, String, Hash_Table, Backtracking, Big_O_Time_O(4^n)_Space_O(n) | 0 | 100.00
285286
| 0022 |[Generate Parentheses](src/main/c/g0001_0100/s0022_generate_parentheses/Solution.c)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, String, Dynamic_Programming, Backtracking, Big_O_Time_O(2^n)_Space_O(n) | 0 | 100.00
287+
| 0079 |[Word Search](src/main/c/g0001_0100/s0079_word_search/Solution.c)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Matrix, Backtracking, Big_O_Time_O(4^(m\*n))_Space_O(m\*n) | 121 | 92.31
286288

287289
#### Day 12 Dynamic Programming
288290

@@ -568,6 +570,7 @@ C-based LeetCode algorithm problem solutions, regularly updated.
568570

569571
| <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- -->
570572
|-|-|-|-|-|-
573+
| 0096 |[Unique Binary Search Trees](src/main/c/g0001_0100/s0096_unique_binary_search_trees/Solution.c)| Medium | Dynamic_Programming, Math, Tree, Binary_Tree, Binary_Search_Tree, Big_O_Time_O(n)_Space_O(1) | 0 | 100.00
571574

572575
#### Day 12
573576

@@ -674,6 +677,7 @@ C-based LeetCode algorithm problem solutions, regularly updated.
674677

675678
| <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- -->
676679
|-|-|-|-|-|-
680+
| 0104 |[Maximum Depth of Binary Tree](src/main/c/g0101_0200/s0104_maximum_depth_of_binary_tree/Solution.c)| 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) | 0 | 100.00
677681

678682
#### Day 11 Containers and Libraries
679683

@@ -946,6 +950,7 @@ C-based LeetCode algorithm problem solutions, regularly updated.
946950

947951
| <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- -->
948952
|-|-|-|-|-|-
953+
| 0102 |[Binary Tree Level Order Traversal](src/main/c/g0101_0200/s0102_binary_tree_level_order_traversal/Solution.c)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Breadth_First_Search, Tree, Binary_Tree, Big_O_Time_O(N)_Space_O(N) | 0 | 100.00
949954

950955
#### Day 7 Binary Search
951956

@@ -956,6 +961,7 @@ C-based LeetCode algorithm problem solutions, regularly updated.
956961

957962
| <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- -->
958963
|-|-|-|-|-|-
964+
| 0098 |[Validate Binary Search Tree](src/main/c/g0001_0100/s0098_validate_binary_search_tree/Solution.c)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Depth_First_Search, Tree, Binary_Tree, Binary_Search_Tree, Big_O_Time_O(N)_Space_O(log(N)) | 0 | 100.00
959965

960966
#### Day 9 Graph/BFS/DFS
961967

@@ -1076,6 +1082,7 @@ C-based LeetCode algorithm problem solutions, regularly updated.
10761082

10771083
| <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- -->
10781084
|-|-|-|-|-|-
1085+
| 0101 |[Symmetric Tree](src/main/c/g0101_0200/s0101_symmetric_tree/Solution.c)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, Depth_First_Search, Breadth_First_Search, Tree, Binary_Tree, Big_O_Time_O(N)_Space_O(log(N)) | 0 | 100.00
10791086

10801087
#### Day 16 Design
10811088

@@ -1169,6 +1176,7 @@ C-based LeetCode algorithm problem solutions, regularly updated.
11691176

11701177
| <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- -->
11711178
|-|-|-|-|-|-
1179+
| 0114 |[Flatten Binary Tree to Linked List](src/main/c/g0101_0200/s0114_flatten_binary_tree_to_linked_list/Solution.c)| Medium | Top_100_Liked_Questions, Depth_First_Search, Tree, Binary_Tree, Stack, Linked_List, Big_O_Time_O(N)_Space_O(N) | 0 | 100.00
11721180
| 0024 |[Swap Nodes in Pairs](src/main/c/g0001_0100/s0024_swap_nodes_in_pairs/Solution.c)| Medium | Top_100_Liked_Questions, Linked_List, Recursion, Big_O_Time_O(n)_Space_O(1) | 0 | 100.00
11731181
| 0021 |[Merge Two Sorted Lists](src/main/c/g0001_0100/s0021_merge_two_sorted_lists/Solution.c)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, Linked_List, Recursion, Big_O_Time_O(m+n)_Space_O(m+n) | 0 | 100.00
11741182
| 0025 |[Reverse Nodes in k-Group](src/main/c/g0001_0100/s0025_reverse_nodes_in_k_group/Solution.c)| Hard | Top_100_Liked_Questions, Linked_List, Recursion, Big_O_Time_O(n)_Space_O(k) | 0 | 100.00
@@ -1177,6 +1185,10 @@ C-based LeetCode algorithm problem solutions, regularly updated.
11771185

11781186
| <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- -->
11791187
|-|-|-|-|-|-
1188+
| 0094 |[Binary Tree Inorder Traversal](src/main/c/g0001_0100/s0094_binary_tree_inorder_traversal/Solution.c)| 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
1189+
| 0102 |[Binary Tree Level Order Traversal](src/main/c/g0101_0200/s0102_binary_tree_level_order_traversal/Solution.c)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Breadth_First_Search, Tree, Binary_Tree, Big_O_Time_O(N)_Space_O(N) | 0 | 100.00
1190+
| 0104 |[Maximum Depth of Binary Tree](src/main/c/g0101_0200/s0104_maximum_depth_of_binary_tree/Solution.c)| 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) | 0 | 100.00
1191+
| 0098 |[Validate Binary Search Tree](src/main/c/g0001_0100/s0098_validate_binary_search_tree/Solution.c)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Depth_First_Search, Tree, Binary_Tree, Binary_Search_Tree, Big_O_Time_O(N)_Space_O(log(N)) | 0 | 100.00
11801192

11811193
#### Udemy Trie and Heap
11821194

@@ -1273,11 +1285,15 @@ C-based LeetCode algorithm problem solutions, regularly updated.
12731285

12741286
| <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- -->
12751287
|-|-|-|-|-|-
1288+
| 0094 |[Binary Tree Inorder Traversal](src/main/c/g0001_0100/s0094_binary_tree_inorder_traversal/Solution.c)| 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
12761289

12771290
#### Day 11 Tree
12781291

12791292
| <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- -->
12801293
|-|-|-|-|-|-
1294+
| 0102 |[Binary Tree Level Order Traversal](src/main/c/g0101_0200/s0102_binary_tree_level_order_traversal/Solution.c)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Breadth_First_Search, Tree, Binary_Tree, Big_O_Time_O(N)_Space_O(N) | 0 | 100.00
1295+
| 0104 |[Maximum Depth of Binary Tree](src/main/c/g0101_0200/s0104_maximum_depth_of_binary_tree/Solution.c)| 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) | 0 | 100.00
1296+
| 0101 |[Symmetric Tree](src/main/c/g0101_0200/s0101_symmetric_tree/Solution.c)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, Depth_First_Search, Breadth_First_Search, Tree, Binary_Tree, Big_O_Time_O(N)_Space_O(log(N)) | 0 | 100.00
12811297

12821298
#### Day 12 Tree
12831299

@@ -1293,11 +1309,22 @@ C-based LeetCode algorithm problem solutions, regularly updated.
12931309

12941310
| <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- -->
12951311
|-|-|-|-|-|-
1312+
| 0098 |[Validate Binary Search Tree](src/main/c/g0001_0100/s0098_validate_binary_search_tree/Solution.c)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Depth_First_Search, Tree, Binary_Tree, Binary_Search_Tree, Big_O_Time_O(N)_Space_O(log(N)) | 0 | 100.00
12961313

12971314
## Algorithms
12981315

12991316
| # | Title | Difficulty | Tag | Time, ms | Time, %
13001317
|------|----------------|-------------|-------------|----------|---------
1318+
| 0114 |[Flatten Binary Tree to Linked List](src/main/c/g0101_0200/s0114_flatten_binary_tree_to_linked_list/Solution.c)| Medium | Top_100_Liked_Questions, Depth_First_Search, Tree, Binary_Tree, Stack, Linked_List, Udemy_Linked_List, Big_O_Time_O(N)_Space_O(N) | 0 | 100.00
1319+
| 0105 |[Construct Binary Tree from Preorder and Inorder Traversal](src/main/c/g0101_0200/s0105_construct_binary_tree_from_preorder_and_inorder_traversal/Solution.c)| 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) | 3 | 95.24
1320+
| 0104 |[Maximum Depth of Binary Tree](src/main/c/g0101_0200/s0104_maximum_depth_of_binary_tree/Solution.c)| 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) | 0 | 100.00
1321+
| 0102 |[Binary Tree Level Order Traversal](src/main/c/g0101_0200/s0102_binary_tree_level_order_traversal/Solution.c)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Breadth_First_Search, Tree, Binary_Tree, Data_Structure_I_Day_11_Tree, Level_1_Day_6_Tree, Udemy_Tree_Stack_Queue, Big_O_Time_O(N)_Space_O(N) | 0 | 100.00
1322+
| 0101 |[Symmetric Tree](src/main/c/g0101_0200/s0101_symmetric_tree/Solution.c)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, Depth_First_Search, Breadth_First_Search, Tree, Binary_Tree, Data_Structure_I_Day_11_Tree, Level_2_Day_15_Tree, Big_O_Time_O(N)_Space_O(log(N)) | 0 | 100.00
1323+
| 0098 |[Validate Binary Search Tree](src/main/c/g0001_0100/s0098_validate_binary_search_tree/Solution.c)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Depth_First_Search, Tree, Binary_Tree, Binary_Search_Tree, Data_Structure_I_Day_14_Tree, Level_1_Day_8_Binary_Search_Tree, Udemy_Tree_Stack_Queue, Big_O_Time_O(N)_Space_O(log(N)) | 0 | 100.00
1324+
| 0096 |[Unique Binary Search Trees](src/main/c/g0001_0100/s0096_unique_binary_search_trees/Solution.c)| Medium | Dynamic_Programming, Math, Tree, Binary_Tree, Binary_Search_Tree, Dynamic_Programming_I_Day_11, Big_O_Time_O(n)_Space_O(1) | 0 | 100.00
1325+
| 0094 |[Binary Tree Inorder Traversal](src/main/c/g0001_0100/s0094_binary_tree_inorder_traversal/Solution.c)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, Depth_First_Search, Tree, Binary_Tree, Stack, Data_Structure_I_Day_10_Tree, Udemy_Tree_Stack_Queue, Big_O_Time_O(n)_Space_O(n) | 0 | 100.00
1326+
| 0084 |[Largest Rectangle in Histogram](src/main/c/g0001_0100/s0084_largest_rectangle_in_histogram/Solution.c)| Hard | Top_100_Liked_Questions, Top_Interview_Questions, Array, Stack, Monotonic_Stack, Big_O_Time_O(n_log_n)_Space_O(log_n) | 7 | 86.96
1327+
| 0079 |[Word Search](src/main/c/g0001_0100/s0079_word_search/Solution.c)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Matrix, Backtracking, Algorithm_II_Day_11_Recursion_Backtracking, Big_O_Time_O(4^(m\*n))_Space_O(m\*n) | 121 | 92.31
13011328
| 0078 |[Subsets](src/main/c/g0001_0100/s0078_subsets/Solution.c)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Bit_Manipulation, Backtracking, Algorithm_II_Day_9_Recursion_Backtracking, Udemy_Backtracking/Recursion, Big_O_Time_O(2^n)_Space_O(n\*2^n) | 0 | 100.00
13021329
| 0076 |[Minimum Window Substring](src/main/c/g0001_0100/s0076_minimum_window_substring/Solution.c)| Hard | Top_100_Liked_Questions, Top_Interview_Questions, String, Hash_Table, Sliding_Window, Level_2_Day_14_Sliding_Window/Two_Pointer, Big_O_Time_O(s.length())_Space_O(1) | 0 | 100.00
13031330
| 0075 |[Sort Colors](src/main/c/g0001_0100/s0075_sort_colors/Solution.c)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Sorting, Two_Pointers, Data_Structure_II_Day_2_Array, Udemy_Arrays, Big_O_Time_O(n)_Space_O(1) | 0 | 100.00
Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
// #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Array #Matrix #Backtracking
2+
// #Algorithm_II_Day_11_Recursion_Backtracking #Big_O_Time_O(4^(m*n))_Space_O(m*n)
3+
// #2024_11_02_Time_121_ms_(92.31%)_Space_7.9_MB_(54.94%)
4+
5+
bool dfsb(char **board, int mrow, int mcol, char *word, int crow, int ccol) {
6+
// This means we are done with search
7+
if (word[0] == '\0') {
8+
return true;
9+
}
10+
11+
// Out of bound check; search ends in this path
12+
if (crow < 0 || ccol < 0 || crow >= mrow || ccol >= mcol) {
13+
return false;
14+
}
15+
16+
// Not found; search ends
17+
if (board[crow][ccol] != word[0]) {
18+
return false;
19+
}
20+
21+
// Mark the cell as visited
22+
board[crow][ccol] = '.';
23+
24+
// Check adjacent cells
25+
if (dfsb(board, mrow, mcol, word + 1, crow, ccol + 1)) return true; // Right
26+
if (dfsb(board, mrow, mcol, word + 1, crow, ccol - 1)) return true; // Left
27+
if (dfsb(board, mrow, mcol, word + 1, crow - 1, ccol)) return true; // Up
28+
if (dfsb(board, mrow, mcol, word + 1, crow + 1, ccol)) return true; // Down
29+
30+
// Undo marking if no match found
31+
board[crow][ccol] = word[0];
32+
return false;
33+
}
34+
35+
bool exist(char **board, int num_rows, int *num_cols, char *word) {
36+
for (int row = 0; row < num_rows; ++row) {
37+
for (int col = 0; col < *num_cols; ++col) {
38+
if (dfsb(board, num_rows, *num_cols, word, row, col)) {
39+
return true;
40+
}
41+
}
42+
}
43+
return false;
44+
}
Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
79\. Word Search
2+
3+
Medium
4+
5+
Given an `m x n` grid of characters `board` and a string `word`, return `true` _if_ `word` _exists in the grid_.
6+
7+
The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.
8+
9+
**Example 1:**
10+
11+
![](https://assets.leetcode.com/uploads/2020/11/04/word2.jpg)
12+
13+
**Input:** board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
14+
15+
**Output:** true
16+
17+
**Example 2:**
18+
19+
![](https://assets.leetcode.com/uploads/2020/11/04/word-1.jpg)
20+
21+
**Input:** board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
22+
23+
**Output:** true
24+
25+
**Example 3:**
26+
27+
![](https://assets.leetcode.com/uploads/2020/10/15/word3.jpg)
28+
29+
**Input:** board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
30+
31+
**Output:** false
32+
33+
**Constraints:**
34+
35+
* `m == board.length`
36+
* `n = board[i].length`
37+
* `1 <= m, n <= 6`
38+
* `1 <= word.length <= 15`
39+
* `board` and `word` consists of only lowercase and uppercase English letters.
40+
41+
**Follow up:** Could you use search pruning to make your solution faster with a larger `board`?
Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
// #Hard #Top_100_Liked_Questions #Top_Interview_Questions #Array #Stack #Monotonic_Stack
2+
// #Big_O_Time_O(n_log_n)_Space_O(log_n) #2024_11_02_Time_7_ms_(86.96%)_Space_14.4_MB_(94.96%)
3+
4+
#include <stdio.h>
5+
#include <stdlib.h>
6+
#include <stdbool.h>
7+
8+
int maxOfThreeNums(int a, int b, int c) {
9+
return (a > b ? (a > c ? a : c) : (b > c ? b : c));
10+
}
11+
12+
int findMinInArray(int* a, int start, int limit) {
13+
int min = __INT_MAX__;
14+
int minIndex = -1;
15+
for (int index = start; index < limit; index++) {
16+
if (a[index] < min) {
17+
min = a[index];
18+
minIndex = index;
19+
}
20+
}
21+
return minIndex;
22+
}
23+
24+
bool checkIfSorted(int* a, int start, int limit) {
25+
for (int i = start + 1; i < limit; i++) {
26+
if (a[i] < a[i - 1]) {
27+
return false;
28+
}
29+
}
30+
return true;
31+
}
32+
33+
int largestArea(int* a, int start, int limit) {
34+
if (a == NULL || limit == 0) {
35+
return 0;
36+
}
37+
if (start == limit) {
38+
return 0;
39+
}
40+
if (limit - start == 1) {
41+
return a[start];
42+
}
43+
if (limit - start == 2) {
44+
int maxOfTwoBars = (a[start] > a[start + 1]) ? a[start] : a[start + 1];
45+
int areaFromTwo = (a[start] < a[start + 1] ? a[start] : a[start + 1]) * 2;
46+
return (maxOfTwoBars > areaFromTwo) ? maxOfTwoBars : areaFromTwo;
47+
}
48+
if (checkIfSorted(a, start, limit)) {
49+
int maxWhenSorted = 0;
50+
for (int i = start; i < limit; i++) {
51+
int area = a[i] * (limit - i);
52+
if (area > maxWhenSorted) {
53+
maxWhenSorted = area;
54+
}
55+
}
56+
return maxWhenSorted;
57+
} else {
58+
int minInd = findMinInArray(a, start, limit);
59+
return maxOfThreeNums(
60+
largestArea(a, start, minInd),
61+
a[minInd] * (limit - start),
62+
largestArea(a, minInd + 1, limit)
63+
);
64+
}
65+
}
66+
67+
int largestRectangleArea(int* heights, int length) {
68+
return largestArea(heights, 0, length);
69+
}
Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
84\. Largest Rectangle in Histogram
2+
3+
Hard
4+
5+
Given an array of integers `heights` representing the histogram's bar height where the width of each bar is `1`, return _the area of the largest rectangle in the histogram_.
6+
7+
**Example 1:**
8+
9+
![](https://assets.leetcode.com/uploads/2021/01/04/histogram.jpg)
10+
11+
**Input:** heights = [2,1,5,6,2,3]
12+
13+
**Output:** 10
14+
15+
**Explanation:** The above is a histogram where width of each bar is 1.
16+
17+
The largest rectangle is shown in the red area, which has an area = 10 units.
18+
19+
**Example 2:**
20+
21+
![](https://assets.leetcode.com/uploads/2021/01/04/histogram-1.jpg)
22+
23+
**Input:** heights = [2,4]
24+
25+
**Output:** 4
26+
27+
**Constraints:**
28+
29+
* <code>1 <= heights.length <= 10<sup>5</sup></code>
30+
* <code>0 <= heights[i] <= 10<sup>4</sup></code>

0 commit comments

Comments
 (0)