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

Commit2c923bb

Browse files
authored
Added tasks 56-72
1 parent834a543 commit2c923bb

File tree

15 files changed

+371
-0
lines changed

15 files changed

+371
-0
lines changed
Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
namespaceLeetCodeNet.G0001_0100.S0056_merge_intervals{
2+
3+
usingSystem;
4+
usingXunit;
5+
6+
publicclassSolutionTest{
7+
[Fact]
8+
publicvoidMerge(){
9+
varinput=newint[][]{newint[]{1,3},newint[]{2,6},newint[]{8,10},newint[]{15,18}};
10+
varexpected=newint[][]{newint[]{1,6},newint[]{8,10},newint[]{15,18}};
11+
Assert.Equal(expected,newSolution().Merge(input));
12+
}
13+
14+
[Fact]
15+
publicvoidMerge2(){
16+
varinput=newint[][]{newint[]{1,4},newint[]{4,5}};
17+
varexpected=newint[][]{newint[]{1,5}};
18+
Assert.Equal(expected,newSolution().Merge(input));
19+
}
20+
}
21+
}
Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
namespaceLeetCodeNet.G0001_0100.S0062_unique_paths{
2+
3+
usingSystem;
4+
usingXunit;
5+
6+
publicclassSolutionTest{
7+
[Fact]
8+
publicvoidUniquePaths(){
9+
Assert.Equal(28,newSolution().UniquePaths(3,7));
10+
}
11+
12+
[Fact]
13+
publicvoidUniquePaths2(){
14+
Assert.Equal(3,newSolution().UniquePaths(3,2));
15+
}
16+
}
17+
}
Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
namespaceLeetCodeNet.G0001_0100.S0064_minimum_path_sum{
2+
3+
usingSystem;
4+
usingXunit;
5+
6+
publicclassSolutionTest{
7+
[Fact]
8+
publicvoidMinPathSum(){
9+
varinput=newint[][]{newint[]{1,3,1},newint[]{1,5,1},newint[]{4,2,1}};
10+
Assert.Equal(7,newSolution().MinPathSum(input));
11+
}
12+
13+
[Fact]
14+
publicvoidMinPathSum2(){
15+
varinput=newint[][]{newint[]{1,2,3},newint[]{4,5,6}};
16+
Assert.Equal(12,newSolution().MinPathSum(input));
17+
}
18+
}
19+
}
Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
namespaceLeetCodeNet.G0001_0100.S0070_climbing_stairs{
2+
3+
usingSystem;
4+
usingXunit;
5+
6+
publicclassSolutionTest{
7+
[Fact]
8+
publicvoidClimbStairs(){
9+
Assert.Equal(2,newSolution().ClimbStairs(2));
10+
}
11+
12+
[Fact]
13+
publicvoidClimbStairs2(){
14+
Assert.Equal(3,newSolution().ClimbStairs(3));
15+
}
16+
}
17+
}
Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
namespaceLeetCodeNet.G0001_0100.S0072_edit_distance{
2+
3+
usingSystem;
4+
usingXunit;
5+
6+
publicclassSolutionTest{
7+
[Fact]
8+
publicvoidMinDistance(){
9+
Assert.Equal(3,newSolution().MinDistance("horse","ros"));
10+
}
11+
12+
[Fact]
13+
publicvoidMinDistance2(){
14+
Assert.Equal(5,newSolution().MinDistance("intention","execution"));
15+
}
16+
}
17+
}
Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
namespaceLeetCodeNet.G0001_0100.S0056_merge_intervals{
2+
3+
// #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Array #Sorting
4+
// #Data_Structure_II_Day_2_Array #Level_2_Day_17_Interval #Udemy_2D_Arrays/Matrix
5+
// #Big_O_Time_O(n_log_n)_Space_O(n) #2024_01_05_Time_149_ms_(89.48%)_Space_55.6_MB_(11.71%)
6+
7+
publicclassSolution{
8+
publicint[][]Merge(int[][]intervals){
9+
Array.Sort(intervals,(a,b)=>a[0]-b[0]);
10+
for(inti=1;i<intervals.Length;i++){
11+
if(intervals[i][0]<=intervals[i-1][1]){
12+
intervals[i][0]=intervals[i-1][0];
13+
intervals[i][1]=Math.Max(intervals[i-1][1],intervals[i][1]);
14+
intervals[i-1][0]=-1;
15+
}
16+
}
17+
returnintervals.Where(obj=>obj[0]!=-1).ToArray();
18+
}
19+
}
20+
}
Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
56\. Merge Intervals
2+
3+
Medium
4+
5+
Given an array of`intervals` where <code>intervals[i] =[start<sub>i</sub>, end<sub>i</sub>]</code>, merge all overlapping intervals, and return_an array of the non-overlapping intervals that cover all the intervals in the input_.
6+
7+
**Example 1:**
8+
9+
**Input:** intervals =[[1,3],[2,6],[8,10],[15,18]]
10+
11+
**Output:**[[1,6],[8,10],[15,18]]
12+
13+
**Explanation:** Since intervals[1,3] and[2,6] overlaps, merge them into[1,6].
14+
15+
**Example 2:**
16+
17+
**Input:** intervals =[[1,4],[4,5]]
18+
19+
**Output:**[[1,5]]
20+
21+
**Explanation:** Intervals[1,4] and[4,5] are considered overlapping.
22+
23+
**Constraints:**
24+
25+
* <code>1 <= intervals.length <= 10<sup>4</sup></code>
26+
*`intervals[i].length == 2`
27+
* <code>0 <= start<sub>i</sub> <= end<sub>i</sub> <= 10<sup>4</sup></code>
Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
namespaceLeetCodeNet.G0001_0100.S0062_unique_paths{
2+
3+
// #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Dynamic_Programming #Math
4+
// #Combinatorics #Algorithm_II_Day_13_Dynamic_Programming #Dynamic_Programming_I_Day_15
5+
// #Level_1_Day_11_Dynamic_Programming #Big_O_Time_O(m*n)_Space_O(m*n)
6+
// #2024_01_05_Time_16_ms_(93.42%)_Space_26.2_MB_(96.08%)
7+
8+
publicclassSolution{
9+
publicintUniquePaths(intm,intn){
10+
int[]array=newint[n];
11+
for(inti=0;i<n;i++){
12+
array[i]=1;
13+
}
14+
for(inti=1;i<m;i++){
15+
for(intj=1;j<n;j++){
16+
array[j]=array[j]+array[j-1];
17+
}
18+
}
19+
returnarray[n-1];
20+
}
21+
}
22+
}
Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
62\. Unique Paths
2+
3+
Medium
4+
5+
A robot is located at the top-left corner of a`m x n` grid (marked 'Start' in the diagram below).
6+
7+
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
8+
9+
How many possible unique paths are there?
10+
11+
**Example 1:**
12+
13+
![](https://assets.leetcode.com/uploads/2018/10/22/robot_maze.png)
14+
15+
**Input:** m = 3, n = 7
16+
17+
**Output:** 28
18+
19+
**Example 2:**
20+
21+
**Input:** m = 3, n = 2
22+
23+
**Output:** 3
24+
25+
**Explanation:**
26+
27+
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
28+
1. Right -> Down -> Down
29+
2. Down -> Down -> Right
30+
3. Down -> Right -> Down
31+
32+
**Example 3:**
33+
34+
**Input:** m = 7, n = 3
35+
36+
**Output:** 28
37+
38+
**Example 4:**
39+
40+
**Input:** m = 3, n = 3
41+
42+
**Output:** 6
43+
44+
**Constraints:**
45+
46+
*`1 <= m, n <= 100`
47+
* It's guaranteed that the answer will be less than or equal to <code>2 * 10<sup>9</sup></code>.
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
namespaceLeetCodeNet.G0001_0100.S0064_minimum_path_sum{
2+
3+
// #Medium #Top_100_Liked_Questions #Array #Dynamic_Programming #Matrix
4+
// #Dynamic_Programming_I_Day_16 #Udemy_Dynamic_Programming #Big_O_Time_O(m*n)_Space_O(m*n)
5+
// #2024_01_05_Time_74_ms_(94.37%)_Space_42.6_MB_(18.50%)
6+
7+
publicclassSolution{
8+
publicintMinPathSum(int[][]grid){
9+
intm=grid.Length;
10+
intn=grid[0].Length;
11+
for(inti=1;i<n;i++){
12+
grid[0][i]+=grid[0][i-1];
13+
}
14+
for(inti=1;i<m;i++){
15+
grid[i][0]+=grid[i-1][0];
16+
}
17+
for(inti=1;i<m;i++){
18+
for(intj=1;j<n;j++){
19+
grid[i][j]+=Math.Min(grid[i][j-1],grid[i-1][j]);
20+
}
21+
}
22+
returngrid[m-1][n-1];
23+
}
24+
}
25+
}
Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
64\. Minimum Path Sum
2+
3+
Medium
4+
5+
Given a`m x n``grid` filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.
6+
7+
**Note:** You can only move either down or right at any point in time.
8+
9+
**Example 1:**
10+
11+
![](https://assets.leetcode.com/uploads/2020/11/05/minpath.jpg)
12+
13+
**Input:** grid =[[1,3,1],[1,5,1],[4,2,1]]
14+
15+
**Output:** 7
16+
17+
**Explanation:** Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.
18+
19+
**Example 2:**
20+
21+
**Input:** grid =[[1,2,3],[4,5,6]]
22+
23+
**Output:** 12
24+
25+
**Constraints:**
26+
27+
*`m == grid.length`
28+
*`n == grid[i].length`
29+
*`1 <= m, n <= 200`
30+
*`0 <= grid[i][j] <= 100`
Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
namespaceLeetCodeNet.G0001_0100.S0070_climbing_stairs{
2+
3+
// #Easy #Top_100_Liked_Questions #Top_Interview_Questions #Dynamic_Programming #Math #Memoization
4+
// #Algorithm_I_Day_12_Dynamic_Programming #Dynamic_Programming_I_Day_2
5+
// #Level_1_Day_10_Dynamic_Programming #Udemy_Dynamic_Programming #Big_O_Time_O(n)_Space_O(n)
6+
// #2024_01_05_Time_15_ms_(94.90%)_Space_26.2_MB_(96.48%)
7+
8+
publicclassSolution{
9+
publicintClimbStairs(intn){
10+
int[]dp=newint[n+1];
11+
dp[0]=1;
12+
for(inti=0;i<dp.Length;i++){
13+
if(i+1<dp.Length){
14+
dp[i+1]+=dp[i];
15+
}
16+
if(i+2<dp.Length){
17+
dp[i+2]+=dp[i];
18+
}
19+
}
20+
returndp[dp.Length-1];
21+
}
22+
}
23+
}
Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
70\. Climbing Stairs
2+
3+
Easy
4+
5+
You are climbing a staircase. It takes`n` steps to reach the top.
6+
7+
Each time you can either climb`1` or`2` steps. In how many distinct ways can you climb to the top?
8+
9+
**Example 1:**
10+
11+
**Input:** n = 2
12+
13+
**Output:** 2
14+
15+
**Explanation:** There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps
16+
17+
**Example 2:**
18+
19+
**Input:** n = 3
20+
21+
**Output:** 3
22+
23+
**Explanation:** There are three ways to climb to the top. 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step
24+
25+
**Constraints:**
26+
27+
*`1 <= n <= 45`
Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
namespaceLeetCodeNet.G0001_0100.S0072_edit_distance{
2+
3+
// #Hard #Top_100_Liked_Questions #String #Dynamic_Programming
4+
// #Algorithm_II_Day_18_Dynamic_Programming #Dynamic_Programming_I_Day_19
5+
// #Udemy_Dynamic_Programming #Big_O_Time_O(n^2)_Space_O(n2)
6+
// #2024_01_05_Time_51_ms_(95.38%)_Space_44.5_MB_(20.65%)
7+
8+
publicclassSolution{
9+
publicintMinDistance(stringword1,stringword2){
10+
varmap=newint[word1.Length+1,word2.Length+1];
11+
for(inti=0;i<=word1.Length;i++){
12+
map[i,0]=i;
13+
}
14+
for(inti=0;i<=word2.Length;i++){
15+
map[0,i]=i;
16+
}
17+
for(inti=1;i<=word1.Length;i++){
18+
for(varj=1;j<=word2.Length;j++){
19+
varadd=word1[i-1]==word2[j-1]?0:1;
20+
varmin=Math.Min(map[i-1,j]+1,map[i,j-1]+1);
21+
map[i,j]=Math.Min(min,map[i-1,j-1]+add);
22+
}
23+
}
24+
returnmap[word1.Length,word2.Length];
25+
}
26+
}
27+
}
Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
72\. Edit Distance
2+
3+
Hard
4+
5+
Given two strings`word1` and`word2`, return_the minimum number of operations required to convert`word1` to`word2`_.
6+
7+
You have the following three operations permitted on a word:
8+
9+
* Insert a character
10+
* Delete a character
11+
* Replace a character
12+
13+
**Example 1:**
14+
15+
**Input:** word1 = "horse", word2 = "ros"
16+
17+
**Output:** 3
18+
19+
**Explanation:** horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e')
20+
21+
**Example 2:**
22+
23+
**Input:** word1 = "intention", word2 = "execution"
24+
25+
**Output:** 5
26+
27+
**Explanation:** intention -> inention (remove 't') inention -> enention (replace 'i' with 'e') enention -> exention (replace 'n' with 'x') exention -> exection (replace 'n' with 'c') exection -> execution (insert 'u')
28+
29+
**Constraints:**
30+
31+
*`0 <= word1.length, word2.length <= 500`
32+
*`word1` and`word2` consist of lowercase English letters.

0 commit comments

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