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

Commitfd0a67b

Browse files
authored
Added tasks 73-98
1 parente1365ed commitfd0a67b

File tree

32 files changed

+850
-0
lines changed

32 files changed

+850
-0
lines changed

‎README.md

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -34,6 +34,7 @@ Ruby-based LeetCode algorithm problem solutions, regularly updated.
3434
|-|-|-|-|-|-
3535
| 0034 |[Find First and Last Position of Element in Sorted Array](src/main/ruby/g0001_0100/s0034_find_first_and_last_position_of_element_in_sorted_array/solution.rb)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Binary_Search, Big_O_Time_O(log_n)_Space_O(1) | 60 | 77.52
3636
| 0033 |[Search in Rotated Sorted Array](src/main/ruby/g0001_0100/s0033_search_in_rotated_sorted_array/solution.rb)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Binary_Search, Big_O_Time_O(log_n)_Space_O(1) | 59 | 74.85
37+
| 0074 |[Search a 2D Matrix](src/main/ruby/g0001_0100/s0074_search_a_2d_matrix/solution.rb)| Medium | Top_100_Liked_Questions, Array, Binary_Search, Matrix, Big_O_Time_O(endRow+endCol)_Space_O(1) | 50 | 97.83
3738

3839
####Day 2 Binary Search
3940

@@ -76,6 +77,7 @@ Ruby-based LeetCode algorithm problem solutions, regularly updated.
7677

7778
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
7879
|-|-|-|-|-|-
80+
| 0078 |[Subsets](src/main/ruby/g0001_0100/s0078_subsets/solution.rb)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Bit_Manipulation, Backtracking, Big_O_Time_O(2^n)_Space_O(n\*2^n) | 63 | 70.43
7981

8082
####Day 10 Recursion Backtracking
8183

@@ -89,6 +91,7 @@ Ruby-based LeetCode algorithm problem solutions, regularly updated.
8991
|-|-|-|-|-|-
9092
| 0017 |[Letter Combinations of a Phone Number](src/main/ruby/g0001_0100/s0017_letter_combinations_of_a_phone_number/solution.rb)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, String, Hash_Table, Backtracking, Big_O_Time_O(4^n)_Space_O(n) | 49 | 93.94
9193
| 0022 |[Generate Parentheses](src/main/ruby/g0001_0100/s0022_generate_parentheses/solution.rb)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, String, Dynamic_Programming, Backtracking, Big_O_Time_O(2^n)_Space_O(n) | 43 | 100.00
94+
| 0079 |[Word Search](src/main/ruby/g0001_0100/s0079_word_search/solution.rb)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Matrix, Backtracking, Big_O_Time_O(4^(m\*n))_Space_O(m\*n) | 56 | 100.00
9295

9396
####Day 12 Dynamic Programming
9497

@@ -188,6 +191,7 @@ Ruby-based LeetCode algorithm problem solutions, regularly updated.
188191

189192
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
190193
|-|-|-|-|-|-
194+
| 0074 |[Search a 2D Matrix](src/main/ruby/g0001_0100/s0074_search_a_2d_matrix/solution.rb)| Medium | Top_100_Liked_Questions, Array, Binary_Search, Matrix, Big_O_Time_O(endRow+endCol)_Space_O(1) | 50 | 97.83
191195

192196
####Day 9
193197

@@ -373,6 +377,7 @@ Ruby-based LeetCode algorithm problem solutions, regularly updated.
373377

374378
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
375379
|-|-|-|-|-|-
380+
| 0096 |[Unique Binary Search Trees](src/main/ruby/g0001_0100/s0096_unique_binary_search_trees/solution.rb)| Medium | Top_100_Liked_Questions, Dynamic_Programming, Math, Tree, Binary_Tree, Binary_Search_Tree, Big_O_Time_O(n)_Space_O(1) | 57 | 61.54
376381

377382
####Day 12
378383

@@ -761,6 +766,7 @@ Ruby-based LeetCode algorithm problem solutions, regularly updated.
761766

762767
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
763768
|-|-|-|-|-|-
769+
| 0098 |[Validate Binary Search Tree](src/main/ruby/g0001_0100/s0098_validate_binary_search_tree/solution.rb)| 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)) | 68 | 70.23
764770

765771
####Day 9 Graph/BFS/DFS
766772

@@ -842,6 +848,7 @@ Ruby-based LeetCode algorithm problem solutions, regularly updated.
842848

843849
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
844850
|-|-|-|-|-|-
851+
| 0074 |[Search a 2D Matrix](src/main/ruby/g0001_0100/s0074_search_a_2d_matrix/solution.rb)| Medium | Top_100_Liked_Questions, Array, Binary_Search, Matrix, Big_O_Time_O(endRow+endCol)_Space_O(1) | 50 | 97.83
845852
| 0033 |[Search in Rotated Sorted Array](src/main/ruby/g0001_0100/s0033_search_in_rotated_sorted_array/solution.rb)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Binary_Search, Big_O_Time_O(log_n)_Space_O(1) | 59 | 74.85
846853

847854
####Day 9 Binary Search Tree
@@ -874,6 +881,7 @@ Ruby-based LeetCode algorithm problem solutions, regularly updated.
874881
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
875882
|-|-|-|-|-|-
876883
| 0003 |[Longest Substring Without Repeating Characters](src/main/ruby/g0001_0100/s0003_longest_substring_without_repeating_characters/solution.rb)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, String, Hash_Table, Sliding_Window, Big_O_Time_O(n)_Space_O(1) | 94 | 85.62
884+
| 0076 |[Minimum Window Substring](src/main/ruby/g0001_0100/s0076_minimum_window_substring/solution.rb)| Hard | Top_100_Liked_Questions, Top_Interview_Questions, String, Hash_Table, Sliding_Window, Big_O_Time_O(s.length())_Space_O(1) | 175 | 93.33
877885

878886
####Day 15 Tree
879887

@@ -938,6 +946,7 @@ Ruby-based LeetCode algorithm problem solutions, regularly updated.
938946
|-|-|-|-|-|-
939947
| 0001 |[Two Sum](src/main/ruby/g0001_0100/s0001_two_sum/solution.rb)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, Array, Hash_Table, Big_O_Time_O(n)_Space_O(n) | 57 | 89.38
940948
| 0055 |[Jump Game](src/main/ruby/g0001_0100/s0055_jump_game/solution.rb)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Dynamic_Programming, Greedy, Big_O_Time_O(n)_Space_O(1) | 88 | 95.88
949+
| 0075 |[Sort Colors](src/main/ruby/g0001_0100/s0075_sort_colors/solution.rb)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Sorting, Two_Pointers, Big_O_Time_O(n)_Space_O(1) | 54 | 88.46
941950
| 0041 |[First Missing Positive](src/main/ruby/g0001_0100/s0041_first_missing_positive/solution.rb)| Hard | Top_100_Liked_Questions, Top_Interview_Questions, Array, Hash_Table, Big_O_Time_O(n)_Space_O(n) | 130 | 65.63
942951

943952
####Udemy Two Pointers
@@ -962,7 +971,9 @@ Ruby-based LeetCode algorithm problem solutions, regularly updated.
962971

963972
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
964973
|-|-|-|-|-|-
974+
| 0074 |[Search a 2D Matrix](src/main/ruby/g0001_0100/s0074_search_a_2d_matrix/solution.rb)| Medium | Top_100_Liked_Questions, Array, Binary_Search, Matrix, Big_O_Time_O(endRow+endCol)_Space_O(1) | 50 | 97.83
965975
| 0048 |[Rotate Image](src/main/ruby/g0001_0100/s0048_rotate_image/solution.rb)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Math, Matrix, Big_O_Time_O(n^2)_Space_O(1) | 50 | 93.64
976+
| 0073 |[Set Matrix Zeroes](src/main/ruby/g0001_0100/s0073_set_matrix_zeroes/solution.rb)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Hash_Table, Matrix, Big_O_Time_O(m\*n)_Space_O(1) | 59 | 100.00
966977
| 0056 |[Merge Intervals](src/main/ruby/g0001_0100/s0056_merge_intervals/solution.rb)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Sorting, Big_O_Time_O(n_log_n)_Space_O(n) | 103 | 74.70
967978

968979
####Udemy Linked List
@@ -977,6 +988,8 @@ Ruby-based LeetCode algorithm problem solutions, regularly updated.
977988

978989
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
979990
|-|-|-|-|-|-
991+
| 0094 |[Binary Tree Inorder Traversal](src/main/ruby/g0001_0100/s0094_binary_tree_inorder_traversal/solution.rb)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, Depth_First_Search, Tree, Binary_Tree, Stack, Big_O_Time_O(n)_Space_O(n) | 56 | 84.00
992+
| 0098 |[Validate Binary Search Tree](src/main/ruby/g0001_0100/s0098_validate_binary_search_tree/solution.rb)| 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)) | 68 | 70.23
980993

981994
####Udemy Trie and Heap
982995

@@ -1003,6 +1016,7 @@ Ruby-based LeetCode algorithm problem solutions, regularly updated.
10031016
|-|-|-|-|-|-
10041017
| 0022 |[Generate Parentheses](src/main/ruby/g0001_0100/s0022_generate_parentheses/solution.rb)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, String, Dynamic_Programming, Backtracking, Big_O_Time_O(2^n)_Space_O(n) | 43 | 100.00
10051018
| 0039 |[Combination Sum](src/main/ruby/g0001_0100/s0039_combination_sum/solution.rb)| Medium | Top_100_Liked_Questions, Array, Backtracking, Big_O_Time_O(2^n)_Space_O(n+2^n) | 79 | 74.84
1019+
| 0078 |[Subsets](src/main/ruby/g0001_0100/s0078_subsets/solution.rb)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Bit_Manipulation, Backtracking, Big_O_Time_O(2^n)_Space_O(n\*2^n) | 63 | 70.43
10061020
| 0017 |[Letter Combinations of a Phone Number](src/main/ruby/g0001_0100/s0017_letter_combinations_of_a_phone_number/solution.rb)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, String, Hash_Table, Backtracking, Big_O_Time_O(4^n)_Space_O(n) | 49 | 93.94
10071021
| 0046 |[Permutations](src/main/ruby/g0001_0100/s0046_permutations/solution.rb)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Backtracking, Big_O_Time_O(n\*n!)_Space_O(n+n!) | 62 | 89.60
10081022

@@ -1044,6 +1058,7 @@ Ruby-based LeetCode algorithm problem solutions, regularly updated.
10441058

10451059
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
10461060
|-|-|-|-|-|-
1061+
| 0074 |[Search a 2D Matrix](src/main/ruby/g0001_0100/s0074_search_a_2d_matrix/solution.rb)| Medium | Top_100_Liked_Questions, Array, Binary_Search, Matrix, Big_O_Time_O(endRow+endCol)_Space_O(1) | 50 | 97.83
10471062

10481063
####Day 6 String
10491064

@@ -1071,6 +1086,7 @@ Ruby-based LeetCode algorithm problem solutions, regularly updated.
10711086

10721087
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
10731088
|-|-|-|-|-|-
1089+
| 0094 |[Binary Tree Inorder Traversal](src/main/ruby/g0001_0100/s0094_binary_tree_inorder_traversal/solution.rb)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, Depth_First_Search, Tree, Binary_Tree, Stack, Big_O_Time_O(n)_Space_O(n) | 56 | 84.00
10741090

10751091
####Day 11 Tree
10761092

@@ -1091,6 +1107,7 @@ Ruby-based LeetCode algorithm problem solutions, regularly updated.
10911107

10921108
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
10931109
|-|-|-|-|-|-
1110+
| 0098 |[Validate Binary Search Tree](src/main/ruby/g0001_0100/s0098_validate_binary_search_tree/solution.rb)| 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)) | 68 | 70.23
10941111

10951112
###Data Structure II
10961113

@@ -1104,6 +1121,7 @@ Ruby-based LeetCode algorithm problem solutions, regularly updated.
11041121

11051122
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
11061123
|-|-|-|-|-|-
1124+
| 0075 |[Sort Colors](src/main/ruby/g0001_0100/s0075_sort_colors/solution.rb)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Sorting, Two_Pointers, Big_O_Time_O(n)_Space_O(1) | 54 | 88.46
11071125
| 0056 |[Merge Intervals](src/main/ruby/g0001_0100/s0056_merge_intervals/solution.rb)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Sorting, Big_O_Time_O(n_log_n)_Space_O(n) | 103 | 74.70
11081126

11091127
####Day 3 Array
@@ -1289,6 +1307,16 @@ Ruby-based LeetCode algorithm problem solutions, regularly updated.
12891307

12901308
| # | Title | Difficulty | Tag | Time, ms | Time, %
12911309
|------|----------------|-------------|-------------|----------|---------
1310+
| 0098 |[Validate Binary Search Tree](src/main/ruby/g0001_0100/s0098_validate_binary_search_tree/solution.rb)| 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)) | 68 | 70.23
1311+
| 0096 |[Unique Binary Search Trees](src/main/ruby/g0001_0100/s0096_unique_binary_search_trees/solution.rb)| Medium | Top_100_Liked_Questions, Dynamic_Programming, Math, Tree, Binary_Tree, Binary_Search_Tree, Dynamic_Programming_I_Day_11, Big_O_Time_O(n)_Space_O(1) | 57 | 61.54
1312+
| 0094 |[Binary Tree Inorder Traversal](src/main/ruby/g0001_0100/s0094_binary_tree_inorder_traversal/solution.rb)| 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) | 56 | 84.00
1313+
| 0084 |[Largest Rectangle in Histogram](src/main/ruby/g0001_0100/s0084_largest_rectangle_in_histogram/solution.rb)| Hard | Top_100_Liked_Questions, Top_Interview_Questions, Array, Stack, Monotonic_Stack, Big_O_Time_O(n_log_n)_Space_O(log_n) | 197 | 98.25
1314+
| 0079 |[Word Search](src/main/ruby/g0001_0100/s0079_word_search/solution.rb)| 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) | 56 | 100.00
1315+
| 0078 |[Subsets](src/main/ruby/g0001_0100/s0078_subsets/solution.rb)| 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) | 63 | 70.43
1316+
| 0076 |[Minimum Window Substring](src/main/ruby/g0001_0100/s0076_minimum_window_substring/solution.rb)| 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) | 175 | 93.33
1317+
| 0075 |[Sort Colors](src/main/ruby/g0001_0100/s0075_sort_colors/solution.rb)| 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) | 54 | 88.46
1318+
| 0074 |[Search a 2D Matrix](src/main/ruby/g0001_0100/s0074_search_a_2d_matrix/solution.rb)| Medium | Top_100_Liked_Questions, Array, Binary_Search, Matrix, Data_Structure_I_Day_5_Array, Algorithm_II_Day_1_Binary_Search, Binary_Search_I_Day_8, Level_2_Day_8_Binary_Search, Udemy_2D_Arrays/Matrix, Big_O_Time_O(endRow+endCol)_Space_O(1) | 50 | 97.83
1319+
| 0073 |[Set Matrix Zeroes](src/main/ruby/g0001_0100/s0073_set_matrix_zeroes/solution.rb)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Hash_Table, Matrix, Udemy_2D_Arrays/Matrix, Big_O_Time_O(m\*n)_Space_O(1) | 59 | 100.00
12921320
| 0072 |[Edit Distance](src/main/ruby/g0001_0100/s0072_edit_distance/solution.rb)| Hard | Top_100_Liked_Questions, String, Dynamic_Programming, Algorithm_II_Day_18_Dynamic_Programming, Dynamic_Programming_I_Day_19, Udemy_Dynamic_Programming, Big_O_Time_O(n^2)_Space_O(n2) | 139 | 73.91
12931321
| 0070 |[Climbing Stairs](src/main/ruby/g0001_0100/s0070_climbing_stairs/solution.rb)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, Dynamic_Programming, Math, Memoization, Algorithm_I_Day_12_Dynamic_Programming, Dynamic_Programming_I_Day_2, Level_1_Day_10_Dynamic_Programming, Udemy_Dynamic_Programming, Big_O_Time_O(n)_Space_O(n) | 48 | 96.01
12941322
| 0064 |[Minimum Path Sum](src/main/ruby/g0001_0100/s0064_minimum_path_sum/solution.rb)| Medium | Top_100_Liked_Questions, Array, Dynamic_Programming, Matrix, Dynamic_Programming_I_Day_16, Udemy_Dynamic_Programming, Big_O_Time_O(m\*n)_Space_O(m\*n) | 78 | 52.50
Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
# Definition for a binary tree node.
2+
classTreeNode
3+
attr_accessor:val,:left,:right
4+
5+
definitialize(val=0,left=nil,right=nil)
6+
@val=val
7+
@left=left
8+
@right=right
9+
end
10+
end
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
73\. Set Matrix Zeroes
2+
3+
Medium
4+
5+
Given an`m x n` integer matrix`matrix`, if an element is`0`, set its entire row and column to`0`'s, and return_the matrix_.
6+
7+
You must do it[in place](https://en.wikipedia.org/wiki/In-place_algorithm).
8+
9+
**Example 1:**
10+
11+
![](https://assets.leetcode.com/uploads/2020/08/17/mat1.jpg)
12+
13+
**Input:** matrix =[[1,1,1],[1,0,1],[1,1,1]]
14+
15+
**Output:**[[1,0,1],[0,0,0],[1,0,1]]
16+
17+
**Example 2:**
18+
19+
![](https://assets.leetcode.com/uploads/2020/08/17/mat2.jpg)
20+
21+
**Input:** matrix =[[0,1,2,0],[3,4,5,2],[1,3,1,5]]
22+
23+
**Output:**[[0,0,0,0],[0,4,5,0],[0,3,1,0]]
24+
25+
**Constraints:**
26+
27+
*`m == matrix.length`
28+
*`n == matrix[0].length`
29+
*`1 <= m, n <= 200`
30+
* <code>-2<sup>31</sup> <= matrix[i][j] <= 2<sup>31</sup> - 1</code>
31+
32+
**Follow up:**
33+
34+
* A straightforward solution using`O(mn)` space is probably a bad idea.
35+
* A simple improvement uses`O(m + n)` space, but still not the best solution.
36+
* Could you devise a constant space solution?
Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
# #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Array #Hash_Table #Matrix
2+
# #Udemy_2D_Arrays/Matrix #Big_O_Time_O(m*n)_Space_O(1)
3+
# #2023_11_22_Time_59_ms_(100.00%)_Space_212.3_MB_(21.11%)
4+
5+
# @param {Integer[][]} matrix
6+
# @return {Void} Do not return anything, modify matrix in-place instead.
7+
defset_zeroes(matrix)
8+
result=[]
9+
m=matrix.length
10+
n=matrix[0].length
11+
12+
(0...m).eachdo |i|
13+
(0...n).eachdo |j|
14+
result <<[i,j]ifmatrix[i][j] ==0
15+
end
16+
end
17+
18+
result.eachdo |r,c|
19+
(0...n).eachdo |i|
20+
matrix[r][i]=0
21+
end
22+
(0...m).eachdo |j|
23+
matrix[j][c]=0
24+
end
25+
end
26+
matrix
27+
end
28+
Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
74\. Search a 2D Matrix
2+
3+
Medium
4+
5+
Write an efficient algorithm that searches for a value in an`m x n` matrix. This matrix has the following properties:
6+
7+
* Integers in each row are sorted from left to right.
8+
* The first integer of each row is greater than the last integer of the previous row.
9+
10+
**Example 1:**
11+
12+
![](https://assets.leetcode.com/uploads/2020/10/05/mat.jpg)
13+
14+
**Input:** matrix =[[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
15+
16+
**Output:** true
17+
18+
**Example 2:**
19+
20+
![](https://assets.leetcode.com/uploads/2020/10/05/mat2.jpg)
21+
22+
**Input:** matrix =[[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
23+
24+
**Output:** false
25+
26+
**Constraints:**
27+
28+
*`m == matrix.length`
29+
*`n == matrix[i].length`
30+
*`1 <= m, n <= 100`
31+
* <code>-10<sup>4</sup> <= matrix[i][j], target <= 10<sup>4</sup></code>
Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
# #Medium #Top_100_Liked_Questions #Array #Binary_Search #Matrix #Data_Structure_I_Day_5_Array
2+
# #Algorithm_II_Day_1_Binary_Search #Binary_Search_I_Day_8 #Level_2_Day_8_Binary_Search
3+
# #Udemy_2D_Arrays/Matrix #Big_O_Time_O(endRow+endCol)_Space_O(1)
4+
# #2023_11_22_Time_50_ms_(97.83%)_Space_210.9_MB_(97.83%)
5+
6+
# @param {Integer[][]} matrix
7+
# @param {Integer} target
8+
# @return {Boolean}
9+
defsearch_matrix(matrix,target)
10+
end_col=matrix[0].length
11+
target_row=0
12+
result=false
13+
14+
matrix.each_with_indexdo |row,i|
15+
ifrow[end_col -1] >=target
16+
target_row=i
17+
break
18+
end
19+
end
20+
21+
matrix[target_row].each_with_indexdo |element,i|
22+
ifelement ==target
23+
result=true
24+
break
25+
end
26+
end
27+
28+
returnresult
29+
end
Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
75\. Sort Colors
2+
3+
Medium
4+
5+
Given an array`nums` with`n` objects colored red, white, or blue, sort them**[in-place](https://en.wikipedia.org/wiki/In-place_algorithm)** so that objects of the same color are adjacent, with the colors in the order red, white, and blue.
6+
7+
We will use the integers`0`,`1`, and`2` to represent the color red, white, and blue, respectively.
8+
9+
You must solve this problem without using the library's sort function.
10+
11+
**Example 1:**
12+
13+
**Input:** nums =[2,0,2,1,1,0]
14+
15+
**Output:**[0,0,1,1,2,2]
16+
17+
**Example 2:**
18+
19+
**Input:** nums =[2,0,1]
20+
21+
**Output:**[0,1,2]
22+
23+
**Example 3:**
24+
25+
**Input:** nums =[0]
26+
27+
**Output:**[0]
28+
29+
**Example 4:**
30+
31+
**Input:** nums =[1]
32+
33+
**Output:**[1]
34+
35+
**Constraints:**
36+
37+
*`n == nums.length`
38+
*`1 <= n <= 300`
39+
*`nums[i]` is`0`,`1`, or`2`.
40+
41+
**Follow up:** Could you come up with a one-pass algorithm using only constant extra space?
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
# #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Array #Sorting #Two_Pointers
2+
# #Data_Structure_II_Day_2_Array #Udemy_Arrays #Big_O_Time_O(n)_Space_O(1)
3+
# #2023_11_22_Time_54_ms_(88.46%)_Space_211.2_MB_(15.38%)
4+
5+
# @param {Integer[]} nums
6+
# @return {Void} Do not return anything, modify nums in-place instead.
7+
defsort_colors(nums)
8+
l=0
9+
h=nums.size -1
10+
i=0
11+
whilei <=h
12+
ifnums[i] ==2
13+
nums[i]=nums[h]
14+
nums[h]=2
15+
h -=1
16+
elsifnums[i] ==0
17+
nums[i]=nums[l]
18+
nums[l]=0
19+
l +=1
20+
i +=1
21+
else
22+
i +=1
23+
end
24+
end
25+
end

0 commit comments

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