Skip to content

Commit ccbcdea

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.0960
No.0960.Delete Columns to Make Sorted III
1 parent 736c9eb commit ccbcdea

File tree

8 files changed

+300
-3
lines changed

8 files changed

+300
-3
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -67,6 +67,7 @@
6767
- [摘樱桃](/solution/0700-0799/0741.Cherry%20Pickup/README.md) - 线性 DP、数字三角形模型
6868
- [摘樱桃 II](/solution/1400-1499/1463.Cherry%20Pickup%20II/README.md) - 线性 DP、数字三角形模型
6969
- [最长递增子序列](/solution/0300-0399/0300.Longest%20Increasing%20Subsequence/README.md) - 线性 DP、最长上升子序列模型
70+
- [删列造序 III](/solution/0900-0999/0960.Delete%20Columns%20to%20Make%20Sorted%20III/README.md) - 线性 DP、最长上升子序列模型
7071

7172

7273
### 4. 高级数据结构

‎README_EN.md

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -65,7 +65,8 @@ Complete solutions to [LeetCode](https://leetcode.com/problemset/all/), [LCOF](h
6565
- [Minimum Path Sum](/solution/0000-0099/0064.Minimum%20Path%20Sum/README_EN.md) - Linear problem
6666
- [Cherry Pickup](/solution/0700-0799/0741.Cherry%20Pickup/README_EN.md) - Linear problem
6767
- [Cherry Pickup II](/solution/1400-1499/1463.Cherry%20Pickup%20II/README_EN.md) - Linear problem
68-
- [Longest Increasing Subsequence](/solution/0300-0399/0300.Longest%20Increasing%20Subsequence/README_EN.md) - Linear problem
68+
- [Longest Increasing Subsequence](/solution/0300-0399/0300.Longest%20Increasing%20Subsequence/README_EN.md) - Linear problem, LIS
69+
- [Delete Columns to Make Sorted III](/solution/0900-0999/0960.Delete%20Columns%20to%20Make%20Sorted%20III/README_EN.md) - Linear problem, LIS
6970

7071
### 4. Advanced Data Structures
7172

‎solution/0900-0999/0960.Delete Columns to Make Sorted III/README.md

Lines changed: 102 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -68,15 +68,116 @@
6868
<!-- 这里可写当前语言的特殊实现逻辑 -->
6969

7070
```python
71-
71+
class Solution:
72+
def minDeletionSize(self, strs: List[str]) -> int:
73+
n = len(strs[0])
74+
dp = [1] * n
75+
for i in range(1, n):
76+
for j in range(i):
77+
if all(s[j] <= s[i] for s in strs):
78+
dp[i] = max(dp[i], dp[j] + 1)
79+
return n - max(dp)
7280
```
7381

7482
### **Java**
7583

7684
<!-- 这里可写当前语言的特殊实现逻辑 -->
7785

7886
```java
87+
class Solution {
88+
public int minDeletionSize(String[] strs) {
89+
int n = strs[0].length();
90+
int[] dp = new int[n];
91+
Arrays.fill(dp, 1);
92+
int mx = 1;
93+
for (int i = 1; i < n; ++i) {
94+
for (int j = 0; j < i; ++j) {
95+
if (check(i, j, strs)) {
96+
dp[i] = Math.max(dp[i], dp[j] + 1);
97+
}
98+
}
99+
mx = Math.max(mx, dp[i]);
100+
}
101+
return n - mx;
102+
}
103+
104+
private boolean check(int i, int j, String[] strs) {
105+
for (String s : strs) {
106+
if (s.charAt(i) < s.charAt(j)) {
107+
return false;
108+
}
109+
}
110+
return true;
111+
}
112+
}
113+
```
114+
115+
### **C++**
116+
117+
```cpp
118+
class Solution {
119+
public:
120+
int minDeletionSize(vector<string>& strs) {
121+
int n = strs[0].size();
122+
vector<int> dp(n, 1);
123+
int mx = 1;
124+
for (int i = 1; i < n; ++i)
125+
{
126+
for (int j = 0; j < i; ++j)
127+
{
128+
if (check(i, j, strs))
129+
{
130+
dp[i] = max(dp[i], dp[j] + 1);
131+
}
132+
}
133+
mx = max(mx, dp[i]);
134+
}
135+
return n - mx;
136+
}
137+
138+
bool check(int i, int j, vector<string>& strs) {
139+
for (string& s : strs)
140+
if (s[i] < s[j])
141+
return false;
142+
return true;
143+
}
144+
};
145+
```
79146

147+
### **Go**
148+
149+
```go
150+
func minDeletionSize(strs []string) int {
151+
n := len(strs[0])
152+
dp := make([]int, n)
153+
mx := 1
154+
dp[0] = 1
155+
check := func(i, j int) bool {
156+
for _, s := range strs {
157+
if s[i] < s[j] {
158+
return false
159+
}
160+
}
161+
return true
162+
}
163+
for i := 1; i < n; i++ {
164+
dp[i] = 1
165+
for j := 0; j < i; j++ {
166+
if check(i, j) {
167+
dp[i] = max(dp[i], dp[j]+1)
168+
}
169+
}
170+
mx = max(mx, dp[i])
171+
}
172+
return n - mx
173+
}
174+
175+
func max(a, b int) int {
176+
if a > b {
177+
return a
178+
}
179+
return b
180+
}
80181
```
81182

82183
### **...**

‎solution/0900-0999/0960.Delete Columns to Make Sorted III/README_EN.md

Lines changed: 102 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -59,13 +59,114 @@ Note that strs[0] &gt; strs[1] - the array strs is not necessarily in lexicograp
5959
### **Python3**
6060

6161
```python
62-
62+
class Solution:
63+
def minDeletionSize(self, strs: List[str]) -> int:
64+
n = len(strs[0])
65+
dp = [1] * n
66+
for i in range(1, n):
67+
for j in range(i):
68+
if all(s[j] <= s[i] for s in strs):
69+
dp[i] = max(dp[i], dp[j] + 1)
70+
return n - max(dp)
6371
```
6472

6573
### **Java**
6674

6775
```java
76+
class Solution {
77+
public int minDeletionSize(String[] strs) {
78+
int n = strs[0].length();
79+
int[] dp = new int[n];
80+
Arrays.fill(dp, 1);
81+
int mx = 1;
82+
for (int i = 1; i < n; ++i) {
83+
for (int j = 0; j < i; ++j) {
84+
if (check(i, j, strs)) {
85+
dp[i] = Math.max(dp[i], dp[j] + 1);
86+
}
87+
}
88+
mx = Math.max(mx, dp[i]);
89+
}
90+
return n - mx;
91+
}
92+
93+
private boolean check(int i, int j, String[] strs) {
94+
for (String s : strs) {
95+
if (s.charAt(i) < s.charAt(j)) {
96+
return false;
97+
}
98+
}
99+
return true;
100+
}
101+
}
102+
```
103+
104+
### **C++**
105+
106+
```cpp
107+
class Solution {
108+
public:
109+
int minDeletionSize(vector<string>& strs) {
110+
int n = strs[0].size();
111+
vector<int> dp(n, 1);
112+
int mx = 1;
113+
for (int i = 1; i < n; ++i)
114+
{
115+
for (int j = 0; j < i; ++j)
116+
{
117+
if (check(i, j, strs))
118+
{
119+
dp[i] = max(dp[i], dp[j] + 1);
120+
}
121+
}
122+
mx = max(mx, dp[i]);
123+
}
124+
return n - mx;
125+
}
126+
127+
bool check(int i, int j, vector<string>& strs) {
128+
for (string& s : strs)
129+
if (s[i] < s[j])
130+
return false;
131+
return true;
132+
}
133+
};
134+
```
68135

136+
### **Go**
137+
138+
```go
139+
func minDeletionSize(strs []string) int {
140+
n := len(strs[0])
141+
dp := make([]int, n)
142+
mx := 1
143+
dp[0] = 1
144+
check := func(i, j int) bool {
145+
for _, s := range strs {
146+
if s[i] < s[j] {
147+
return false
148+
}
149+
}
150+
return true
151+
}
152+
for i := 1; i < n; i++ {
153+
dp[i] = 1
154+
for j := 0; j < i; j++ {
155+
if check(i, j) {
156+
dp[i] = max(dp[i], dp[j]+1)
157+
}
158+
}
159+
mx = max(mx, dp[i])
160+
}
161+
return n - mx
162+
}
163+
164+
func max(a, b int) int {
165+
if a > b {
166+
return a
167+
}
168+
return b
169+
}
69170
```
70171

71172
### **...**

‎solution/0900-0999/0960.Delete Columns to Make Sorted III/Solution.cpp

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
class Solution {
2+
public:
3+
int minDeletionSize(vector<string>& strs) {
4+
int n = strs[0].size();
5+
vector<int> dp(n, 1);
6+
int mx = 1;
7+
for (int i = 1; i < n; ++i)
8+
{
9+
for (int j = 0; j < i; ++j)
10+
{
11+
if (check(i, j, strs))
12+
{
13+
dp[i] = max(dp[i], dp[j] + 1);
14+
}
15+
}
16+
mx = max(mx, dp[i]);
17+
}
18+
return n - mx;
19+
}
20+
21+
bool check(int i, int j, vector<string>& strs) {
22+
for (string& s : strs)
23+
if (s[i] < s[j])
24+
return false;
25+
return true;
26+
}
27+
};

‎solution/0900-0999/0960.Delete Columns to Make Sorted III/Solution.go

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
func minDeletionSize(strs []string) int {
2+
n := len(strs[0])
3+
dp := make([]int, n)
4+
mx := 1
5+
dp[0] = 1
6+
check := func(i, j int) bool {
7+
for _, s := range strs {
8+
if s[i] < s[j] {
9+
return false
10+
}
11+
}
12+
return true
13+
}
14+
for i := 1; i < n; i++ {
15+
dp[i] = 1
16+
for j := 0; j < i; j++ {
17+
if check(i, j) {
18+
dp[i] = max(dp[i], dp[j]+1)
19+
}
20+
}
21+
mx = max(mx, dp[i])
22+
}
23+
return n - mx
24+
}
25+
26+
func max(a, b int) int {
27+
if a > b {
28+
return a
29+
}
30+
return b
31+
}

‎solution/0900-0999/0960.Delete Columns to Make Sorted III/Solution.java

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
class Solution {
2+
public int minDeletionSize(String[] strs) {
3+
int n = strs[0].length();
4+
int[] dp = new int[n];
5+
Arrays.fill(dp, 1);
6+
int mx = 1;
7+
for (int i = 1; i < n; ++i) {
8+
for (int j = 0; j < i; ++j) {
9+
if (check(i, j, strs)) {
10+
dp[i] = Math.max(dp[i], dp[j] + 1);
11+
}
12+
}
13+
mx = Math.max(mx, dp[i]);
14+
}
15+
return n - mx;
16+
}
17+
18+
private boolean check(int i, int j, String[] strs) {
19+
for (String s : strs) {
20+
if (s.charAt(i) < s.charAt(j)) {
21+
return false;
22+
}
23+
}
24+
return true;
25+
}
26+
}

‎solution/0900-0999/0960.Delete Columns to Make Sorted III/Solution.py

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
class Solution:
2+
def minDeletionSize(self, strs: List[str]) -> int:
3+
n = len(strs[0])
4+
dp = [1] * n
5+
for i in range(1, n):
6+
for j in range(i):
7+
if all(s[j] <= s[i] for s in strs):
8+
dp[i] = max(dp[i], dp[j] + 1)
9+
return n - max(dp)

0 commit comments

Comments
 (0)