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

Commit 7a0f951

Browse files
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
### **...**
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+
}
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+
}
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)

AltStyle によって変換されたページ (->オリジナル) /