Skip to content

Commit fac93e9

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problems
* No.0859.Buddy Strings * No.0861.Score After Flipping Matrix
1 parent e7b9f2f commit fac93e9

File tree

10 files changed

+231
-74
lines changed

10 files changed

+231
-74
lines changed

‎solution/0800-0899/0859.Buddy Strings/README.md

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -51,6 +51,21 @@
5151

5252
<!-- 这里可写通用的实现逻辑 -->
5353

54+
**方法一：字符统计**
55+
56+
首先，先理解亲密字符串的意思：
57+
58+
- 若两个字符串的长度或字符出现的频数不等，一定不是亲密字符串；
59+
- 若两个字符串对应位置不相等的字符数量为 2，或者数量为 0 并且字符串存在两个相同字符，则是亲密字符串。
60+
61+
因此，我们先判断两个字符串长度，若不等，直接返回 `false`。
62+
63+
接着，统计两个字符串的字符频数，记为 `cnt1` 和 `cnt2`，若 `cnt1` 不等于 `cnt2`，直接返回 `false`。
64+
65+
然后枚举两个字符串，统计对应位置不相等的字符数量，若为 2，则返回 `true`；若为 0，且字符串存在两个相同字符，则返回 `true`。
66+
67+
时间复杂度 $O(n)$，空间复杂度 $O(C)$。其中 $n$ 是字符串 `s` 或 `goal` 的长度；而 $C$ 为字符集大小。
68+
5469
<!-- tabs:start -->
5570

5671
### **Python3**
@@ -163,6 +178,34 @@ func buddyStrings(s string, goal string) bool {
163178
}
164179
```
165180

181+
### **TypeScript**
182+
183+
```ts
184+
function buddyStrings(s: string, goal: string): boolean {
185+
const m = s.length;
186+
const n = goal.length;
187+
if (m != n) {
188+
return false;
189+
}
190+
const cnt1 = new Array(26).fill(0);
191+
const cnt2 = new Array(26).fill(0);
192+
let diff = 0;
193+
for (let i = 0; i < n; ++i) {
194+
cnt1[s.charCodeAt(i) - 'a'.charCodeAt(0)]++;
195+
cnt2[goal.charCodeAt(i) - 'a'.charCodeAt(0)]++;
196+
if (s[i] != goal[i]) {
197+
++diff;
198+
}
199+
}
200+
for (let i = 0; i < 26; ++i) {
201+
if (cnt1[i] != cnt2[i]) {
202+
return false;
203+
}
204+
}
205+
return diff == 2 || (diff == 0 && cnt1.some(v => v > 1));
206+
}
207+
```
208+
166209
### **...**
167210

168211
```

‎solution/0800-0899/0859.Buddy Strings/README_EN.md

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -155,6 +155,34 @@ func buddyStrings(s string, goal string) bool {
155155
}
156156
```
157157

158+
### **TypeScript**
159+
160+
```ts
161+
function buddyStrings(s: string, goal: string): boolean {
162+
const m = s.length;
163+
const n = goal.length;
164+
if (m != n) {
165+
return false;
166+
}
167+
const cnt1 = new Array(26).fill(0);
168+
const cnt2 = new Array(26).fill(0);
169+
let diff = 0;
170+
for (let i = 0; i < n; ++i) {
171+
cnt1[s.charCodeAt(i) - 'a'.charCodeAt(0)]++;
172+
cnt2[goal.charCodeAt(i) - 'a'.charCodeAt(0)]++;
173+
if (s[i] != goal[i]) {
174+
++diff;
175+
}
176+
}
177+
for (let i = 0; i < 26; ++i) {
178+
if (cnt1[i] != cnt2[i]) {
179+
return false;
180+
}
181+
}
182+
return diff == 2 || (diff == 0 && cnt1.some(v => v > 1));
183+
}
184+
```
185+
158186
### **...**
159187

160188
```

‎solution/0800-0899/0859.Buddy Strings/Solution.ts

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
function buddyStrings(s: string, goal: string): boolean {
2+
const m = s.length;
3+
const n = goal.length;
4+
if (m != n) {
5+
return false;
6+
}
7+
const cnt1 = new Array(26).fill(0);
8+
const cnt2 = new Array(26).fill(0);
9+
let diff = 0;
10+
for (let i = 0; i < n; ++i) {
11+
cnt1[s.charCodeAt(i) - 'a'.charCodeAt(0)]++;
12+
cnt2[goal.charCodeAt(i) - 'a'.charCodeAt(0)]++;
13+
if (s[i] != goal[i]) {
14+
++diff;
15+
}
16+
}
17+
for (let i = 0; i < 26; ++i) {
18+
if (cnt1[i] != cnt2[i]) {
19+
return false;
20+
}
21+
}
22+
return diff == 2 || (diff == 0 && cnt1.some(v => v > 1));
23+
}

‎solution/0800-0899/0861.Score After Flipping Matrix/README.md

Lines changed: 50 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -41,11 +41,13 @@
4141

4242
<!-- 这里可写通用的实现逻辑 -->
4343

44-
贪心。
44+
**方法一：贪心**
4545

46-
每一行的数字要尽可能大，因此，遍历每一行，若行首元素为 0，则将该行每个元素进行翻转，即 `grid[i][j] ^= 1`；
46+
每一行的数字要尽可能大，因此，遍历每一行，若行首元素为 0，则将该行每个元素进行翻转，即 `grid[i][j] ^= 1`。
4747

48-
接着，遍历每一列，统计列中元素为 1 的个数 `cnt`，若 `cnt`(1 的个数) 比 `m - cnt`(0 的个数) 小，则将该列进行翻转。实际过程中，并不需要对列进行翻转，只需要取 `max(cnt, m - cnt)`，即表示 1 的个数，再乘上该位的大小 `n - j - 1`，即求得当前列的大小。累加每一列大小即可。
48+
接着，遍历每一列，若该列中 1 的个数小于 0 的个数，则将该列进行翻转。实际过程中，并不需要对列进行翻转，只需要取 `max(cnt, m - cnt)`，即表示 1 的个数，再乘上该位的大小 `1 << (n - j - 1)`，即求得当前列的大小。累加每一列大小即可。
49+
50+
时间复杂度 $O(m\times n)$，空间复杂度 $O(1)$。其中 $m$, $n$ 分别为矩阵的行数和列数。
4951

5052
<!-- tabs:start -->
5153

@@ -61,14 +63,11 @@ class Solution:
6163
if grid[i][0] == 0:
6264
for j in range(n):
6365
grid[i][j] ^= 1
64-
65-
res = 0
66+
ans = 0
6667
for j in range(n):
67-
cnt = 0
68-
for i in range(m):
69-
cnt += grid[i][j]
70-
res += max(cnt, m - cnt) * (1 << (n - j - 1))
71-
return res
68+
cnt = sum(grid[i][j] for i in range(m))
69+
ans += max(cnt, m - cnt) * (1 << (n - j - 1))
70+
return ans
7271
```
7372

7473
### **Java**
@@ -86,15 +85,15 @@ class Solution {
8685
}
8786
}
8887
}
89-
int res = 0;
88+
int ans = 0;
9089
for (int j = 0; j < n; ++j) {
9190
int cnt = 0;
9291
for (int i = 0; i < m; ++i) {
9392
cnt += grid[i][j];
9493
}
95-
res += Math.max(cnt, m - cnt) * (1 << (n - j - 1));
94+
ans += Math.max(cnt, m - cnt) * (1 << (n - j - 1));
9695
}
97-
return res;
96+
return ans;
9897
}
9998
}
10099
```
@@ -108,16 +107,20 @@ public:
108107
int m = grid.size(), n = grid[0].size();
109108
for (int i = 0; i < m; ++i) {
110109
if (grid[i][0] == 0) {
111-
for (int j = 0; j < n; ++j) grid[i][j] ^= 1;
110+
for (int j = 0; j < n; ++j) {
111+
grid[i][j] ^= 1;
112+
}
112113
}
113114
}
114-
int res = 0;
115+
int ans = 0;
115116
for (int j = 0; j < n; ++j) {
116117
int cnt = 0;
117-
for (int i = 0; i < m; ++i) cnt += grid[i][j];
118-
res += max(cnt, m - cnt) * (1 << (n - j - 1));
118+
for (int i = 0; i < m; ++i) {
119+
cnt += grid[i][j];
120+
}
121+
ans += max(cnt, m - cnt) * (1 << (n - j - 1));
119122
}
120-
return res;
123+
return ans;
121124
}
122125
};
123126
```
@@ -134,22 +137,43 @@ func matrixScore(grid [][]int) int {
134137
}
135138
}
136139
}
137-
res := 0
140+
ans := 0
138141
for j := 0; j < n; j++ {
139142
cnt := 0
140143
for i := 0; i < m; i++ {
141144
cnt += grid[i][j]
142145
}
143-
res += max(cnt, m-cnt) * (1 << (n - j - 1))
146+
if cnt < m-cnt {
147+
cnt = m - cnt
148+
}
149+
ans += cnt * (1 << (n - j - 1))
144150
}
145-
return res
151+
return ans
146152
}
153+
```
147154

148-
func max(a, b int) int {
149-
if a > b {
150-
return a
151-
}
152-
return b
155+
### **TypeScript**
156+
157+
```ts
158+
function matrixScore(grid: number[][]): number {
159+
const m = grid.length;
160+
const n = grid[0].length;
161+
for (let i = 0; i < m; ++i) {
162+
if (grid[i][0] == 0) {
163+
for (let j = 0; j < n; ++j) {
164+
grid[i][j] ^= 1;
165+
}
166+
}
167+
}
168+
let ans = 0;
169+
for (let j = 0; j < n; ++j) {
170+
let cnt = 0;
171+
for (let i = 0; i < m; ++i) {
172+
cnt += grid[i][j];
173+
}
174+
ans += Math.max(cnt, m - cnt) * (1 << (n - j - 1));
175+
}
176+
return ans;
153177
}
154178
```
155179

‎solution/0800-0899/0861.Score After Flipping Matrix/README_EN.md

Lines changed: 45 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -52,14 +52,11 @@ class Solution:
5252
if grid[i][0] == 0:
5353
for j in range(n):
5454
grid[i][j] ^= 1
55-
56-
res = 0
55+
ans = 0
5756
for j in range(n):
58-
cnt = 0
59-
for i in range(m):
60-
cnt += grid[i][j]
61-
res += max(cnt, m - cnt) * (1 << (n - j - 1))
62-
return res
57+
cnt = sum(grid[i][j] for i in range(m))
58+
ans += max(cnt, m - cnt) * (1 << (n - j - 1))
59+
return ans
6360
```
6461

6562
### **Java**
@@ -75,15 +72,15 @@ class Solution {
7572
}
7673
}
7774
}
78-
int res = 0;
75+
int ans = 0;
7976
for (int j = 0; j < n; ++j) {
8077
int cnt = 0;
8178
for (int i = 0; i < m; ++i) {
8279
cnt += grid[i][j];
8380
}
84-
res += Math.max(cnt, m - cnt) * (1 << (n - j - 1));
81+
ans += Math.max(cnt, m - cnt) * (1 << (n - j - 1));
8582
}
86-
return res;
83+
return ans;
8784
}
8885
}
8986
```
@@ -97,16 +94,20 @@ public:
9794
int m = grid.size(), n = grid[0].size();
9895
for (int i = 0; i < m; ++i) {
9996
if (grid[i][0] == 0) {
100-
for (int j = 0; j < n; ++j) grid[i][j] ^= 1;
97+
for (int j = 0; j < n; ++j) {
98+
grid[i][j] ^= 1;
99+
}
101100
}
102101
}
103-
int res = 0;
102+
int ans = 0;
104103
for (int j = 0; j < n; ++j) {
105104
int cnt = 0;
106-
for (int i = 0; i < m; ++i) cnt += grid[i][j];
107-
res += max(cnt, m - cnt) * (1 << (n - j - 1));
105+
for (int i = 0; i < m; ++i) {
106+
cnt += grid[i][j];
107+
}
108+
ans += max(cnt, m - cnt) * (1 << (n - j - 1));
108109
}
109-
return res;
110+
return ans;
110111
}
111112
};
112113
```
@@ -123,22 +124,43 @@ func matrixScore(grid [][]int) int {
123124
}
124125
}
125126
}
126-
res := 0
127+
ans := 0
127128
for j := 0; j < n; j++ {
128129
cnt := 0
129130
for i := 0; i < m; i++ {
130131
cnt += grid[i][j]
131132
}
132-
res += max(cnt, m-cnt) * (1 << (n - j - 1))
133+
if cnt < m-cnt {
134+
cnt = m - cnt
135+
}
136+
ans += cnt * (1 << (n - j - 1))
133137
}
134-
return res
138+
return ans
135139
}
140+
```
136141

137-
func max(a, b int) int {
138-
if a > b {
139-
return a
140-
}
141-
return b
142+
### **TypeScript**
143+
144+
```ts
145+
function matrixScore(grid: number[][]): number {
146+
const m = grid.length;
147+
const n = grid[0].length;
148+
for (let i = 0; i < m; ++i) {
149+
if (grid[i][0] == 0) {
150+
for (let j = 0; j < n; ++j) {
151+
grid[i][j] ^= 1;
152+
}
153+
}
154+
}
155+
let ans = 0;
156+
for (let j = 0; j < n; ++j) {
157+
let cnt = 0;
158+
for (let i = 0; i < m; ++i) {
159+
cnt += grid[i][j];
160+
}
161+
ans += Math.max(cnt, m - cnt) * (1 << (n - j - 1));
162+
}
163+
return ans;
142164
}
143165
```
144166

‎solution/0800-0899/0861.Score After Flipping Matrix/Solution.cpp

Lines changed: 9 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -4,15 +4,19 @@ class Solution {
44
int m = grid.size(), n = grid[0].size();
55
for (int i = 0; i < m; ++i) {
66
if (grid[i][0] == 0) {
7-
for (int j = 0; j < n; ++j) grid[i][j] ^= 1;
7+
for (int j = 0; j < n; ++j) {
8+
grid[i][j] ^= 1;
9+
}
810
}
911
}
10-
int res = 0;
12+
int ans = 0;
1113
for (int j = 0; j < n; ++j) {
1214
int cnt = 0;
13-
for (int i = 0; i < m; ++i) cnt += grid[i][j];
14-
res += max(cnt, m - cnt) * (1 << (n - j - 1));
15+
for (int i = 0; i < m; ++i) {
16+
cnt += grid[i][j];
17+
}
18+
ans += max(cnt, m - cnt) * (1 << (n - j - 1));
1519
}
16-
return res;
20+
return ans;
1721
}
1822
};

0 commit comments

Comments
 (0)