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

Commit5fe2997

Browse files
authored
Added tasks 120-135
1 parentf12c053 commit5fe2997

File tree

33 files changed

+1098
-0
lines changed

33 files changed

+1098
-0
lines changed

‎README.md‎

Lines changed: 29 additions & 0 deletions
Large diffs are not rendered by default.
Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
120\. Triangle
2+
3+
Medium
4+
5+
Given a`triangle` array, return_the minimum path sum from top to bottom_.
6+
7+
For each step, you may move to an adjacent number of the row below. More formally, if you are on index`i` on the current row, you may move to either index`i` or index`i + 1` on the next row.
8+
9+
**Example 1:**
10+
11+
**Input:** triangle =[[2],[3,4],[6,5,7],[4,1,8,3]]
12+
13+
**Output:** 11
14+
15+
**Explanation:** The triangle looks like:
16+
17+
<ins>2</ins>
18+
19+
<ins>3</ins> 4
20+
21+
6 <ins>5</ins> 7
22+
23+
4 <ins>1</ins> 8 3
24+
25+
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).
26+
27+
**Example 2:**
28+
29+
**Input:** triangle =[[-10]]
30+
31+
**Output:** -10
32+
33+
**Constraints:**
34+
35+
*`1 <= triangle.length <= 200`
36+
*`triangle[0].length == 1`
37+
*`triangle[i].length == triangle[i - 1].length + 1`
38+
* <code>-10<sup>4</sup> <= triangle[i][j] <= 10<sup>4</sup></code>
39+
40+
**Follow up:** Could you do this using only`O(n)` extra space, where`n` is the total number of rows in the triangle?
Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
package s0120_triangle
2+
3+
// #Medium #Array #Dynamic_Programming #Algorithm_I_Day_12_Dynamic_Programming
4+
// #Dynamic_Programming_I_Day_13 #Udemy_Dynamic_Programming #Top_Interview_150_Multidimensional_DP
5+
// #2025_05_18_Time_0_ms_(100.00%)_Space_5.48_MB_(16.19%)
6+
7+
funcminimumTotal(triangle [][]int)int {
8+
iflen(triangle)==0 {
9+
return0
10+
}
11+
dp:=make([][]int,len(triangle))
12+
fori:=rangedp {
13+
dp[i]=make([]int,len(triangle[len(triangle)-1]))
14+
forj:=rangedp[i] {
15+
dp[i][j]=-10001
16+
}
17+
}
18+
returndfs(triangle,dp,0,0)
19+
}
20+
21+
funcdfs(triangle [][]int,dp [][]int,row,colint)int {
22+
ifrow>=len(triangle) {
23+
return0
24+
}
25+
ifdp[row][col]!=-10001 {
26+
returndp[row][col]
27+
}
28+
sum:=triangle[row][col]+min(dfs(triangle,dp,row+1,col),dfs(triangle,dp,row+1,col+1))
29+
dp[row][col]=sum
30+
returnsum
31+
}
32+
33+
funcmin(a,bint)int {
34+
ifa<b {
35+
returna
36+
}
37+
returnb
38+
}
Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
package s0120_triangle
2+
3+
import (
4+
"github.com/stretchr/testify/assert"
5+
"testing"
6+
)
7+
8+
funcTestMinimumTotal(t*testing.T) {
9+
triangle:= [][]int{
10+
{2},
11+
{3,4},
12+
{6,5,7},
13+
{4,1,8,3},
14+
}
15+
assert.Equal(t,11,minimumTotal(triangle))
16+
}
17+
18+
funcTestMinimumTotal2(t*testing.T) {
19+
triangle:= [][]int{
20+
{-10},
21+
}
22+
assert.Equal(t,-10,minimumTotal(triangle))
23+
}
24+
25+
funcTestMinimumTotal3(t*testing.T) {
26+
vartriangle [][]int
27+
assert.Equal(t,0,minimumTotal(triangle))
28+
}
Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
122\. Best Time to Buy and Sell Stock II
2+
3+
Medium
4+
5+
You are given an integer array`prices` where`prices[i]` is the price of a given stock on the <code>i<sup>th</sup></code> day.
6+
7+
On each day, you may decide to buy and/or sell the stock. You can only hold**at most one** share of the stock at any time. However, you can buy it then immediately sell it on the**same day**.
8+
9+
Find and return_the**maximum** profit you can achieve_.
10+
11+
**Example 1:**
12+
13+
**Input:** prices =[7,1,5,3,6,4]
14+
15+
**Output:** 7
16+
17+
**Explanation:** Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4. Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3. Total profit is 4 + 3 = 7.
18+
19+
**Example 2:**
20+
21+
**Input:** prices =[1,2,3,4,5]
22+
23+
**Output:** 4
24+
25+
**Explanation:** Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Total profit is 4.
26+
27+
**Example 3:**
28+
29+
**Input:** prices =[7,6,4,3,1]
30+
31+
**Output:** 0
32+
33+
**Explanation:** There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.
34+
35+
**Constraints:**
36+
37+
* <code>1 <= prices.length <= 3 * 10<sup>4</sup></code>
38+
* <code>0 <= prices[i] <= 10<sup>4</sup></code>
Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
package s0122_best_time_to_buy_and_sell_stock_ii
2+
3+
// #Medium #Top_Interview_Questions #Array #Dynamic_Programming #Greedy #Dynamic_Programming_I_Day_7
4+
// #Udemy_Arrays #Top_Interview_150_Array/String
5+
// #2025_05_18_Time_0_ms_(100.00%)_Space_5.11_MB_(46.22%)
6+
7+
funcmaxProfit(prices []int)int {
8+
max:=0
9+
fori:=1;i<len(prices);i++ {
10+
ifprices[i]>prices[i-1] {
11+
max+=prices[i]-prices[i-1]
12+
}
13+
}
14+
returnmax
15+
}
Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
package s0122_best_time_to_buy_and_sell_stock_ii
2+
3+
import (
4+
"github.com/stretchr/testify/assert"
5+
"testing"
6+
)
7+
8+
funcTestMaxProfit(t*testing.T) {
9+
prices:= []int{7,1,5,3,6,4}
10+
assert.Equal(t,7,maxProfit(prices))
11+
}
12+
13+
funcTestMaxProfit2(t*testing.T) {
14+
prices:= []int{1,2,3,4,5}
15+
assert.Equal(t,4,maxProfit(prices))
16+
}
17+
18+
funcTestMaxProfit3(t*testing.T) {
19+
prices:= []int{7,6,4,3,1}
20+
assert.Equal(t,0,maxProfit(prices))
21+
}
Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
123\. Best Time to Buy and Sell Stock III
2+
3+
Hard
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+
Find the maximum profit you can achieve. You may complete**at most two transactions**.
8+
9+
**Note:** You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
10+
11+
**Example 1:**
12+
13+
**Input:** prices =[3,3,5,0,0,3,1,4]
14+
15+
**Output:** 6
16+
17+
**Explanation:** Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3. Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.
18+
19+
**Example 2:**
20+
21+
**Input:** prices =[1,2,3,4,5]
22+
23+
**Output:** 4
24+
25+
**Explanation:** Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.
26+
27+
**Example 3:**
28+
29+
**Input:** prices =[7,6,4,3,1]
30+
31+
**Output:** 0
32+
33+
**Explanation:** In this case, no transaction is done, i.e. max profit = 0.
34+
35+
**Constraints:**
36+
37+
* <code>1 <= prices.length <= 10<sup>5</sup></code>
38+
* <code>0 <= prices[i] <= 10<sup>5</sup></code>
Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
package s0123_best_time_to_buy_and_sell_stock_iii
2+
3+
// #Hard #Array #Dynamic_Programming #Top_Interview_150_Multidimensional_DP
4+
// #2025_05_20_Time_0_ms_(100.00%)_Space_12.50_MB_(32.12%)
5+
6+
funcmaxProfit(prices []int)int {
7+
iflen(prices)==0 {
8+
return0
9+
}
10+
fb:=-1<<31
11+
sb:=-1<<31
12+
fs:=0
13+
ss:=0
14+
for_,price:=rangeprices {
15+
fb=max(fb,-price)
16+
fs=max(fs,fb+price)
17+
sb=max(sb,fs-price)
18+
ss=max(ss,sb+price)
19+
}
20+
returnss
21+
}
22+
23+
funcmax(a,bint)int {
24+
ifa>b {
25+
returna
26+
}
27+
returnb
28+
}
Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
package s0123_best_time_to_buy_and_sell_stock_iii
2+
3+
import (
4+
"github.com/stretchr/testify/assert"
5+
"testing"
6+
)
7+
8+
funcTestMaxProfit(t*testing.T) {
9+
prices:= []int{3,3,5,0,0,3,1,4}
10+
assert.Equal(t,6,maxProfit(prices))
11+
}
12+
13+
funcTestMaxProfit2(t*testing.T) {
14+
prices:= []int{1,2,3,4,5}
15+
assert.Equal(t,4,maxProfit(prices))
16+
}
17+
18+
funcTestMaxProfit3(t*testing.T) {
19+
prices:= []int{7,6,4,3,1}
20+
assert.Equal(t,0,maxProfit(prices))
21+
}
22+
23+
funcTestMaxProfit4(t*testing.T) {
24+
varprices []int
25+
assert.Equal(t,0,maxProfit(prices))
26+
}

0 commit comments

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