Skip to content

Commit 7a0f951

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problems
* No.1432.Max Difference You Can Get From Changing an Integer * No.1436.Destination City * No.1437.Check If All 1's Are at Least Length K Places Away
1 parent c5ca447 commit 7a0f951

File tree

19 files changed

+573
-79
lines changed

19 files changed

+573
-79
lines changed

‎solution/1100-1199/1192.Critical Connections in a Network/README_EN.md

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -53,6 +53,48 @@
5353

5454
```
5555

56+
### **C++**
57+
58+
```cpp
59+
class Solution {
60+
public:
61+
int count = 0;
62+
vector<int> dfn, low;
63+
vector<vector<int>> graph;
64+
vector<vector<int>> res;
65+
void tarjan(int u, int fa) {
66+
dfn[u] = low[u] = ++count;
67+
for (auto& v : graph[u]) {
68+
if (v == fa)
69+
continue;
70+
if (!dfn[v]) {
71+
tarjan(v, u);
72+
low[u] = min(low[u], low[v]);
73+
if (dfn[u] < low[v])
74+
res.push_back({u, v});
75+
} else {
76+
low[u] = min(dfn[v], low[u]);
77+
}
78+
}
79+
}
80+
81+
vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
82+
dfn.resize(n);
83+
low.resize(n);
84+
graph.resize(n);
85+
for (auto& edge : connections) {
86+
graph[edge[0]].push_back(edge[1]);
87+
graph[edge[1]].push_back(edge[0]);
88+
}
89+
for (int i = 0; i < n; i++) {
90+
if (!dfn[i])
91+
tarjan(i, -1);
92+
}
93+
return res;
94+
}
95+
};
96+
```
97+
5698
### **...**
5799

58100
```

‎solution/1400-1499/1432.Max Difference You Can Get From Changing an Integer/README.md

Lines changed: 81 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -69,22 +69,102 @@
6969

7070
<!-- 这里可写通用的实现逻辑 -->
7171

72+
**方法一：贪心**
73+
74+
要想得到最大差值，那么我们应该拿到最大值与最小值，这样差值最大。
75+
76+
从高到低枚举 `nums` 每个位置上的数，如果数字不为 `9`，就将所有该数字替换为 `9`，得到最大整数 $a$。
77+
78+
从高到低枚举 `nums` 每个位置上的数，首位不能为 `0`，因此如果首位不为 `1`，我们将其替换为 `1`；如果非首位，且数字不与首位相同，我们将其替换为 `0`。得到最大整数 $b$。
79+
80+
答案为差值 $a - b$。
81+
82+
时间复杂度 $O(log(num))$。
83+
7284
<!-- tabs:start -->
7385

7486
### **Python3**
7587

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

7890
```python
79-
91+
class Solution:
92+
def maxDiff(self, num: int) -> int:
93+
a, b = str(num), str(num)
94+
for c in a:
95+
if c != '9':
96+
a = a.replace(c, '9')
97+
break
98+
for i, c in enumerate(b):
99+
if i == 0:
100+
if c != '1':
101+
b = b.replace(c, '1')
102+
break
103+
else:
104+
if c != '0' and c != b[0]:
105+
b = b.replace(c, '0')
106+
break
107+
return int(a) - int(b)
80108
```
81109

82110
### **Java**
83111

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

86114
```java
115+
class Solution {
116+
public int maxDiff(int num) {
117+
String a = String.valueOf(num);
118+
String b = String.valueOf(num);
119+
for (char c : a.toCharArray()) {
120+
if (c != '9') {
121+
a = a.replaceAll(String.valueOf(c), "9");
122+
break;
123+
}
124+
}
125+
for (int i = 0; i < b.length(); ++i) {
126+
char c = b.charAt(i);
127+
if (i == 0) {
128+
if (c != '1') {
129+
b = b.replaceAll(String.valueOf(c), "1");
130+
break;
131+
}
132+
} else {
133+
if (c != '0' && c != b.charAt(0)) {
134+
b = b.replaceAll(String.valueOf(c), "0");
135+
break;
136+
}
137+
}
138+
}
139+
return Integer.parseInt(a) - Integer.parseInt(b);
140+
}
141+
}
142+
```
87143

144+
### **Go**
145+
146+
```go
147+
func maxDiff(num int) int {
148+
a, b := num, num
149+
s := strconv.Itoa(num)
150+
for i := range s {
151+
if s[i] != '9' {
152+
a, _ = strconv.Atoi(strings.ReplaceAll(s, string(s[i]), "9"))
153+
break
154+
}
155+
}
156+
if s[0] > '1' {
157+
b, _ = strconv.Atoi(strings.ReplaceAll(s, string(s[0]), "1"))
158+
} else {
159+
for i := 1; i < len(s); i++ {
160+
if s[i] != '0' && s[i] != s[0] {
161+
b, _ = strconv.Atoi(strings.ReplaceAll(s, string(s[i]), "0"))
162+
break
163+
}
164+
}
165+
}
166+
return a - b
167+
}
88168
```
89169

90170
### **...**

‎solution/1400-1499/1432.Max Difference You Can Get From Changing an Integer/README_EN.md

Lines changed: 69 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -52,13 +52,81 @@ We have now a = 9 and b = 1 and max difference = 8
5252
### **Python3**
5353

5454
```python
55-
55+
class Solution:
56+
def maxDiff(self, num: int) -> int:
57+
a, b = str(num), str(num)
58+
for c in a:
59+
if c != '9':
60+
a = a.replace(c, '9')
61+
break
62+
for i, c in enumerate(b):
63+
if i == 0:
64+
if c != '1':
65+
b = b.replace(c, '1')
66+
break
67+
else:
68+
if c != '0' and c != b[0]:
69+
b = b.replace(c, '0')
70+
break
71+
return int(a) - int(b)
5672
```
5773

5874
### **Java**
5975

6076
```java
77+
class Solution {
78+
public int maxDiff(int num) {
79+
String a = String.valueOf(num);
80+
String b = String.valueOf(num);
81+
for (char c : a.toCharArray()) {
82+
if (c != '9') {
83+
a = a.replaceAll(String.valueOf(c), "9");
84+
break;
85+
}
86+
}
87+
for (int i = 0; i < b.length(); ++i) {
88+
char c = b.charAt(i);
89+
if (i == 0) {
90+
if (c != '1') {
91+
b = b.replaceAll(String.valueOf(c), "1");
92+
break;
93+
}
94+
} else {
95+
if (c != '0' && c != b.charAt(0)) {
96+
b = b.replaceAll(String.valueOf(c), "0");
97+
break;
98+
}
99+
}
100+
}
101+
return Integer.parseInt(a) - Integer.parseInt(b);
102+
}
103+
}
104+
```
61105

106+
### **Go**
107+
108+
```go
109+
func maxDiff(num int) int {
110+
a, b := num, num
111+
s := strconv.Itoa(num)
112+
for i := range s {
113+
if s[i] != '9' {
114+
a, _ = strconv.Atoi(strings.ReplaceAll(s, string(s[i]), "9"))
115+
break
116+
}
117+
}
118+
if s[0] > '1' {
119+
b, _ = strconv.Atoi(strings.ReplaceAll(s, string(s[0]), "1"))
120+
} else {
121+
for i := 1; i < len(s); i++ {
122+
if s[i] != '0' && s[i] != s[0] {
123+
b, _ = strconv.Atoi(strings.ReplaceAll(s, string(s[i]), "0"))
124+
break
125+
}
126+
}
127+
}
128+
return a - b
129+
}
62130
```
63131

64132
### **...**

‎solution/1400-1499/1432.Max Difference You Can Get From Changing an Integer/Solution.go

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
func maxDiff(num int) int {
2+
a, b := num, num
3+
s := strconv.Itoa(num)
4+
for i := range s {
5+
if s[i] != '9' {
6+
a, _ = strconv.Atoi(strings.ReplaceAll(s, string(s[i]), "9"))
7+
break
8+
}
9+
}
10+
if s[0] > '1' {
11+
b, _ = strconv.Atoi(strings.ReplaceAll(s, string(s[0]), "1"))
12+
} else {
13+
for i := 1; i < len(s); i++ {
14+
if s[i] != '0' && s[i] != s[0] {
15+
b, _ = strconv.Atoi(strings.ReplaceAll(s, string(s[i]), "0"))
16+
break
17+
}
18+
}
19+
}
20+
return a - b
21+
}

‎solution/1400-1499/1432.Max Difference You Can Get From Changing an Integer/Solution.java

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
class Solution {
2+
public int maxDiff(int num) {
3+
String a = String.valueOf(num);
4+
String b = String.valueOf(num);
5+
for (char c : a.toCharArray()) {
6+
if (c != '9') {
7+
a = a.replaceAll(String.valueOf(c), "9");
8+
break;
9+
}
10+
}
11+
for (int i = 0; i < b.length(); ++i) {
12+
char c = b.charAt(i);
13+
if (i == 0) {
14+
if (c != '1') {
15+
b = b.replaceAll(String.valueOf(c), "1");
16+
break;
17+
}
18+
} else {
19+
if (c != '0' && c != b.charAt(0)) {
20+
b = b.replaceAll(String.valueOf(c), "0");
21+
break;
22+
}
23+
}
24+
}
25+
return Integer.parseInt(a) - Integer.parseInt(b);
26+
}
27+
}

‎solution/1400-1499/1432.Max Difference You Can Get From Changing an Integer/Solution.py

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
class Solution:
2+
def maxDiff(self, num: int) -> int:
3+
a, b = str(num), str(num)
4+
for c in a:
5+
if c != '9':
6+
a = a.replace(c, '9')
7+
break
8+
for i, c in enumerate(b):
9+
if i == 0:
10+
if c != '1':
11+
b = b.replace(c, '1')
12+
break
13+
else:
14+
if c != '0' and c != b[0]:
15+
b = b.replace(c, '0')
16+
break
17+
return int(a) - int(b)

0 commit comments

Comments
 (0)