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

Commitb56653d

Browse files
authored
Added tasks 73-78
1 parentb1b7748 commitb56653d

File tree

15 files changed

+472
-0
lines changed

15 files changed

+472
-0
lines changed
Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
namespaceLeetCodeNet.G0001_0100.S0073_set_matrix_zeroes{
2+
3+
usingSystem;
4+
usingXunit;
5+
6+
publicclassSolutionTest{
7+
[Fact]
8+
publicvoidSetZeroes(){
9+
varinput=newint[][]{newint[]{1,1,1},newint[]{1,0,1},newint[]{1,1,1}};
10+
varoutput=newint[][]{newint[]{1,0,1},newint[]{0,0,0},newint[]{1,0,1}};
11+
newSolution().SetZeroes(input);
12+
Assert.Equal(input,output);
13+
}
14+
15+
[Fact]
16+
publicvoidSetZeroes2(){
17+
varinput=newint[][]{newint[]{0,1,2,0},newint[]{3,4,5,2},newint[]{1,3,1,5}};
18+
varoutput=newint[][]{newint[]{0,0,0,0},newint[]{0,4,5,0},newint[]{0,3,1,0}};
19+
newSolution().SetZeroes(input);
20+
Assert.Equal(input,output);
21+
}
22+
}
23+
}
Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
namespaceLeetCodeNet.G0001_0100.S0074_search_a_2d_matrix{
2+
3+
usingSystem;
4+
usingXunit;
5+
6+
publicclassSolutionTest{
7+
[Fact]
8+
publicvoidSearchMatrix(){
9+
varinput=newint[][]{newint[]{1,3,5,7},newint[]{10,11,16,20},newint[]{23,30,34,60}};
10+
Assert.True(newSolution().SearchMatrix(input,3));
11+
}
12+
13+
[Fact]
14+
publicvoidSearchMatrix2(){
15+
varinput=newint[][]{newint[]{1,3,5,7},newint[]{10,11,16,20},newint[]{23,30,34,60}};
16+
Assert.False(newSolution().SearchMatrix(input,13));
17+
}
18+
}
19+
}
Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
namespaceLeetCodeNet.G0001_0100.S0075_sort_colors{
2+
3+
usingSystem;
4+
usingXunit;
5+
6+
publicclassSolutionTest{
7+
[Fact]
8+
publicvoidSortColors(){
9+
varinput=newint[]{2,0,2,1,1,0};
10+
varoutput=newint[]{0,0,1,1,2,2};
11+
newSolution().SortColors(input);
12+
Assert.Equal(output,input);
13+
}
14+
15+
[Fact]
16+
publicvoidSortColors2(){
17+
varinput=newint[]{2,0,2,1,1,0};
18+
varoutput=newint[]{0,0,1,1,2,2};
19+
newSolution().SortColors(input);
20+
Assert.Equal(output,input);
21+
}
22+
}
23+
}
Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
namespaceLeetCodeNet.G0001_0100.S0076_minimum_window_substring{
2+
3+
usingSystem;
4+
usingXunit;
5+
6+
publicclassSolutionTest{
7+
[Fact]
8+
publicvoidMinWindow(){
9+
Assert.Equal("BANC",newSolution().MinWindow("ADOBECODEBANC","ABC"));
10+
}
11+
12+
[Fact]
13+
publicvoidMinWindow2(){
14+
Assert.Equal("a",newSolution().MinWindow("a","a"));
15+
}
16+
17+
[Fact]
18+
publicvoidMinWindow3(){
19+
Assert.Equal("",newSolution().MinWindow("a","aa"));
20+
}
21+
}
22+
}
Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
namespaceLeetCodeNet.G0001_0100.S0078_subsets{
2+
3+
usingSystem;
4+
usingXunit;
5+
6+
publicclassSolutionTest{
7+
[Fact]
8+
publicvoidCombine(){
9+
varoutput=newList<List<int>>{newList<int>{1,2},newList<int>{1,3},newList<int>{1,4},newList<int>{2,3},newList<int>{2,4},newList<int>{3,4}};
10+
Assert.Equal(output,newSolution().Combine(4,2));
11+
}
12+
13+
[Fact]
14+
publicvoidCombine2(){
15+
varoutput=newList<List<int>>{newList<int>{1}};
16+
Assert.Equal(output,newSolution().Combine(1,1));
17+
}
18+
}
19+
}
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
namespaceLeetCodeNet.G0001_0100.S0073_set_matrix_zeroes{
2+
3+
// #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Array #Hash_Table #Matrix
4+
// #Udemy_2D_Arrays/Matrix #Big_O_Time_O(m*n)_Space_O(1)
5+
// #2024_01_05_Time_123_ms_(97.51%)_Space_52_MB_(8.21%)
6+
7+
publicclassSolution{
8+
publicvoidSetZeroes(int[][]matrix){
9+
List<int>yRow=newList<int>();
10+
11+
for(introw=0;row<matrix.Length;row++){
12+
boolhasZero=false;
13+
for(intcolumn=0;column<matrix[0].Length;column++){
14+
if(matrix[row][column]==0){
15+
hasZero=true;
16+
yRow.Add(column);
17+
}
18+
}
19+
20+
if(hasZero){
21+
for(intcolumn=0;column<matrix[0].Length;column++){
22+
matrix[row][column]=0;
23+
}
24+
}
25+
}
26+
27+
foreach(intcolumninyRow){
28+
for(introw=0;row<matrix.Length;row++){
29+
matrix[row][column]=0;
30+
}
31+
}
32+
33+
34+
}
35+
}
36+
}
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: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
namespaceLeetCodeNet.G0001_0100.S0074_search_a_2d_matrix{
2+
3+
// #Medium #Top_100_Liked_Questions #Array #Binary_Search #Matrix #Data_Structure_I_Day_5_Array
4+
// #Algorithm_II_Day_1_Binary_Search #Binary_Search_I_Day_8 #Level_2_Day_8_Binary_Search
5+
// #Udemy_2D_Arrays/Matrix #Big_O_Time_O(endRow+endCol)_Space_O(1)
6+
// #2024_01_05_Time_75_ms_(92.10%)_Space_43_MB_(19.86%)
7+
8+
publicclassSolution{
9+
publicboolSearchMatrix(int[][]matrix,inttarget){
10+
inttargetRow=0;
11+
intcolSize=matrix[0].Length;
12+
while(targetRow<matrix.Length-1&&target>matrix[targetRow][colSize-1]){
13+
targetRow++;
14+
}
15+
returnArray.BinarySearch(matrix[targetRow],target)>=0?true:false;;
16+
}
17+
}
18+
}
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: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
namespaceLeetCodeNet.G0001_0100.S0075_sort_colors{
2+
3+
// #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Array #Sorting #Two_Pointers
4+
// #Data_Structure_II_Day_2_Array #Udemy_Arrays #Big_O_Time_O(n)_Space_O(1)
5+
// #2024_01_05_Time_96_ms_(95.14%)_Space_44.8_MB_(20.40%)
6+
7+
publicclassSolution{
8+
publicvoidSortColors(int[]nums){
9+
varlow=0;
10+
varmid=0;
11+
varhigh=nums.Length-1;
12+
13+
while(mid<=high){
14+
if(nums[mid]==0){
15+
vartemp=nums[low];
16+
nums[low]=nums[mid];
17+
nums[mid]=temp;
18+
mid++;
19+
low++;
20+
}
21+
elseif(nums[mid]==1){
22+
mid++;
23+
}
24+
else{
25+
vartemp=nums[mid];
26+
nums[mid]=nums[high];
27+
nums[high]=temp;
28+
high--;
29+
}
30+
}
31+
}
32+
}
33+
}
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: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
namespaceLeetCodeNet.G0001_0100.S0076_minimum_window_substring{
2+
3+
// #Hard #Top_100_Liked_Questions #Top_Interview_Questions #String #Hash_Table #Sliding_Window
4+
// #Level_2_Day_14_Sliding_Window/Two_Pointer #Big_O_Time_O(s.length())_Space_O(1)
5+
// #2024_01_05_Time_66_ms_(93.87%)_Space_43.1_MB_(33.62%)
6+
7+
publicclassSolution{
8+
publicstringMinWindow(strings,stringt){
9+
if(string.IsNullOrEmpty(s)||string.IsNullOrEmpty(s)||s.Length<t.Length){
10+
return"";
11+
}
12+
13+
IDictionary<char,int>map=newDictionary<char,int>(t.Length);
14+
for(intindex=0;index<t.Length;index++){
15+
charc=t[index];
16+
if(!map.ContainsKey(c)){
17+
map.Add(c,1);
18+
}
19+
else{
20+
map[c]++;
21+
}
22+
}
23+
24+
IDictionary<char,int>foundMap=newDictionary<char,int>(t.Length);
25+
intmatchRequired=map.Keys.Count;
26+
intmatched=0;
27+
28+
intminWindowStart=-1;
29+
intminWindowEnd=-1;
30+
intminWindow=Int32.MaxValue;
31+
32+
intstart=0;
33+
intend=0;
34+
while(start<=end&&end<s.Length){
35+
charc=s[end];
36+
if(!map.ContainsKey(c)){
37+
end++;
38+
continue;
39+
}
40+
41+
if(!foundMap.ContainsKey(c)){
42+
foundMap.Add(c,1);
43+
}
44+
else{
45+
foundMap[c]++;
46+
}
47+
if(foundMap[c]==map[c]){
48+
matched++;
49+
}
50+
51+
while(matched==matchRequired&&start<=end){
52+
if((end-start+1)<minWindow){
53+
minWindowStart=start;
54+
minWindowEnd=end;
55+
minWindow=end-start+1;
56+
}
57+
58+
varstartChar=s[start];
59+
if(foundMap.ContainsKey(startChar)){
60+
foundMap[startChar]--;
61+
if(foundMap[startChar]<map[startChar]){
62+
matched--;
63+
}
64+
}
65+
start++;
66+
}
67+
68+
end++;
69+
}
70+
71+
returnminWindow<Int32.MaxValue?s.Substring(minWindowStart,minWindowEnd-minWindowStart+1):"";
72+
}
73+
}
74+
}

0 commit comments

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