Skip to content

Commit 25448d6

Browse files
yanglbmeyanglbme
authored
feat: add solutions to lc problems: No.3226,3227 (doocs#3298)
* No.3226.Number of Bit Changes to Make Two Integers Equal * No.3227.Vowels Game in a String
1 parent e13c2c2 commit 25448d6

File tree

14 files changed

+280
-16
lines changed

14 files changed

+280
-16
lines changed

‎solution/3200-3299/3226.Number of Bit Changes to Make Two Integers Equal/README.md

Lines changed: 41 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -71,32 +71,69 @@ edit_url: https://github.com/doocs/leetcode/edit/main/solution/3200-3299/3226.Nu
7171

7272
<!-- solution:start -->
7373

74-
### 方法一
74+
### 方法一：位运算
75+
76+
如果 $n$ 和 $k$ 的按位与结果不等于 $k$，说明 $k$ 存在某一位为 $1$，而 $n$ 对应的位为 $0$，此时无法通过改变 $n$ 的某一位使得 $n$ 等于 $k$，返回 $-1$；否则，我们统计 $n \oplus k$ 的二进制表示中 $1$ 的个数即可。
77+
78+
时间复杂度 $O(\log n)$，空间复杂度 $O(1)$。
7579

7680
<!-- tabs:start -->
7781

7882
#### Python3
7983

8084
```python
81-
85+
class Solution:
86+
def minChanges(self, n: int, k: int) -> int:
87+
return -1 if n & k != k else (n ^ k).bit_count()
8288
```
8389

8490
#### Java
8591

8692
```java
87-
93+
class Solution {
94+
public int minChanges(int n, int k) {
95+
return (n & k) != k ? -1 : Integer.bitCount(n ^ k);
96+
}
97+
}
8898
```
8999

90100
#### C++
91101

92102
```cpp
93-
103+
class Solution {
104+
public:
105+
int minChanges(int n, int k) {
106+
return (n & k) != k ? -1 : __builtin_popcount(n ^ k);
107+
}
108+
};
94109
```
95110
96111
#### Go
97112
98113
```go
114+
func minChanges(n int, k int) int {
115+
if n&k != k {
116+
return -1
117+
}
118+
return bits.OnesCount(uint(n ^ k))
119+
}
120+
```
99121

122+
#### TypeScript
123+
124+
```ts
125+
function minChanges(n: number, k: number): number {
126+
return (n & k) !== k ? -1 : bitCount(n ^ k);
127+
}
128+
129+
function bitCount(i: number): number {
130+
i = i - ((i >>> 1) & 0x55555555);
131+
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
132+
i = (i + (i >>> 4)) & 0x0f0f0f0f;
133+
i = i + (i >>> 8);
134+
i = i + (i >>> 16);
135+
return i & 0x3f;
136+
}
100137
```
101138

102139
<!-- tabs:end -->

‎solution/3200-3299/3226.Number of Bit Changes to Make Two Integers Equal/README_EN.md

Lines changed: 41 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -68,32 +68,69 @@ It is not possible to make <code>n</code> equal to <code>k</code>.</p>
6868

6969
<!-- solution:start -->
7070

71-
### Solution 1
71+
### Solution 1: Bit Manipulation
72+
73+
If the bitwise AND result of $n$ and $k$ is not equal to $k$, it indicates that there exists at least one bit where $k$ is $1$ and the corresponding bit in $n$ is $0$. In this case, it is impossible to modify a bit in $n$ to make $n$ equal to $k$, and we return $-1$. Otherwise, we count the number of $1$s in the binary representation of $n \oplus k$.
74+
75+
The time complexity is $O(\log n)$, and the space complexity is $O(1)$.
7276

7377
<!-- tabs:start -->
7478

7579
#### Python3
7680

7781
```python
78-
82+
class Solution:
83+
def minChanges(self, n: int, k: int) -> int:
84+
return -1 if n & k != k else (n ^ k).bit_count()
7985
```
8086

8187
#### Java
8288

8389
```java
84-
90+
class Solution {
91+
public int minChanges(int n, int k) {
92+
return (n & k) != k ? -1 : Integer.bitCount(n ^ k);
93+
}
94+
}
8595
```
8696

8797
#### C++
8898

8999
```cpp
90-
100+
class Solution {
101+
public:
102+
int minChanges(int n, int k) {
103+
return (n & k) != k ? -1 : __builtin_popcount(n ^ k);
104+
}
105+
};
91106
```
92107
93108
#### Go
94109
95110
```go
111+
func minChanges(n int, k int) int {
112+
if n&k != k {
113+
return -1
114+
}
115+
return bits.OnesCount(uint(n ^ k))
116+
}
117+
```
96118

119+
#### TypeScript
120+
121+
```ts
122+
function minChanges(n: number, k: number): number {
123+
return (n & k) !== k ? -1 : bitCount(n ^ k);
124+
}
125+
126+
function bitCount(i: number): number {
127+
i = i - ((i >>> 1) & 0x55555555);
128+
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
129+
i = (i + (i >>> 4)) & 0x0f0f0f0f;
130+
i = i + (i >>> 8);
131+
i = i + (i >>> 16);
132+
return i & 0x3f;
133+
}
97134
```
98135

99136
<!-- tabs:end -->

‎solution/3200-3299/3226.Number of Bit Changes to Make Two Integers Equal/Solution.cpp

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
class Solution {
2+
public:
3+
int minChanges(int n, int k) {
4+
return (n & k) != k ? -1 : __builtin_popcount(n ^ k);
5+
}
6+
};

‎solution/3200-3299/3226.Number of Bit Changes to Make Two Integers Equal/Solution.go

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
func minChanges(n int, k int) int {
2+
if n&k != k {
3+
return -1
4+
}
5+
return bits.OnesCount(uint(n ^ k))
6+
}

‎solution/3200-3299/3226.Number of Bit Changes to Make Two Integers Equal/Solution.java

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
class Solution {
2+
public int minChanges(int n, int k) {
3+
return (n & k) != k ? -1 : Integer.bitCount(n ^ k);
4+
}
5+
}

‎solution/3200-3299/3226.Number of Bit Changes to Make Two Integers Equal/Solution.py

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
class Solution:
2+
def minChanges(self, n: int, k: int) -> int:
3+
return -1 if n & k != k else (n ^ k).bit_count()

‎solution/3200-3299/3226.Number of Bit Changes to Make Two Integers Equal/Solution.ts

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
function minChanges(n: number, k: number): number {
2+
return (n & k) !== k ? -1 : bitCount(n ^ k);
3+
}
4+
5+
function bitCount(i: number): number {
6+
i = i - ((i >>> 1) & 0x55555555);
7+
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
8+
i = (i + (i >>> 4)) & 0x0f0f0f0f;
9+
i = i + (i >>> 8);
10+
i = i + (i >>> 16);
11+
return i & 0x3f;
12+
}

‎solution/3200-3299/3227.Vowels Game in a String/README.md

Lines changed: 61 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -75,32 +75,89 @@ edit_url: https://github.com/doocs/leetcode/edit/main/solution/3200-3299/3227.Vo
7575

7676
<!-- solution:start -->
7777

78-
### 方法一
78+
### 方法一：脑筋急转弯
79+
80+
我们不妨记字符串中元音字母的个数为 $k$。
81+
82+
如果 $k = 0$，即字符串中没有元音字母，那么小红无法移除任何子字符串，小明直接获胜。
83+
84+
如果 $k$ 为奇数，那么小红可以移除整个字符串，小红直接获胜。
85+
86+
如果 $k$ 为偶数，那么小红可以移除 $k - 1$ 个元音字母，此时剩下一个元音字母，小明无法移除任何子字符串，小红直接获胜。
87+
88+
综上所述，如果字符串中包含元音字母，那么小红获胜，否则小明获胜。
89+
90+
时间复杂度 $O(n)$，其中 $n$ 为字符串 $s$ 的长度。空间复杂度 $O(1)$。
7991

8092
<!-- tabs:start -->
8193

8294
#### Python3
8395

8496
```python
85-
97+
class Solution:
98+
def doesAliceWin(self, s: str) -> bool:
99+
vowels = set("aeiou")
100+
return any(c in vowels for c in s)
86101
```
87102

88103
#### Java
89104

90105
```java
91-
106+
class Solution {
107+
public boolean doesAliceWin(String s) {
108+
for (int i = 0; i < s.length(); ++i) {
109+
if ("aeiou".indexOf(s.charAt(i)) != -1) {
110+
return true;
111+
}
112+
}
113+
return false;
114+
}
115+
}
92116
```
93117

94118
#### C++
95119

96120
```cpp
97-
121+
class Solution {
122+
public:
123+
bool doesAliceWin(string s) {
124+
string vowels = "aeiou";
125+
for (char c : s) {
126+
if (vowels.find(c) != string::npos) {
127+
return true;
128+
}
129+
}
130+
return false;
131+
}
132+
};
98133
```
99134
100135
#### Go
101136
102137
```go
138+
func doesAliceWin(s string) bool {
139+
vowels := "aeiou"
140+
for _, c := range s {
141+
if strings.ContainsRune(vowels, c) {
142+
return true
143+
}
144+
}
145+
return false
146+
}
147+
```
103148

149+
#### TypeScript
150+
151+
```ts
152+
function doesAliceWin(s: string): boolean {
153+
const vowels = 'aeiou';
154+
for (const c of s) {
155+
if (vowels.includes(c)) {
156+
return true;
157+
}
158+
}
159+
return false;
160+
}
104161
```
105162

106163
<!-- tabs:end -->

‎solution/3200-3299/3227.Vowels Game in a String/README_EN.md

Lines changed: 61 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -73,32 +73,89 @@ There is no valid play for Alice in her first turn, so Alice loses the game.</p>
7373

7474
<!-- solution:start -->
7575

76-
### Solution 1
76+
### Solution 1: Brain Teaser
77+
78+
Let's denote the number of vowels in the string as $k$.
79+
80+
If $k = 0$, meaning there are no vowels in the string, then Little Red cannot remove any substring, and Little Ming wins directly.
81+
82+
If $k$ is odd, then Little Red can remove the entire string, resulting in a direct win for Little Red.
83+
84+
If $k$ is even, then Little Red can remove $k - 1$ vowels, leaving one vowel in the string. In this case, Little Ming cannot remove any substring, leading to a direct win for Little Red.
85+
86+
In conclusion, if the string contains vowels, then Little Red wins; otherwise, Little Ming wins.
87+
88+
The time complexity is $O(n)$, where $n$ is the length of the string $s$. The space complexity is $O(1)$.
7789

7890
<!-- tabs:start -->
7991

8092
#### Python3
8193

8294
```python
83-
95+
class Solution:
96+
def doesAliceWin(self, s: str) -> bool:
97+
vowels = set("aeiou")
98+
return any(c in vowels for c in s)
8499
```
85100

86101
#### Java
87102

88103
```java
89-
104+
class Solution {
105+
public boolean doesAliceWin(String s) {
106+
for (int i = 0; i < s.length(); ++i) {
107+
if ("aeiou".indexOf(s.charAt(i)) != -1) {
108+
return true;
109+
}
110+
}
111+
return false;
112+
}
113+
}
90114
```
91115

92116
#### C++
93117

94118
```cpp
95-
119+
class Solution {
120+
public:
121+
bool doesAliceWin(string s) {
122+
string vowels = "aeiou";
123+
for (char c : s) {
124+
if (vowels.find(c) != string::npos) {
125+
return true;
126+
}
127+
}
128+
return false;
129+
}
130+
};
96131
```
97132
98133
#### Go
99134
100135
```go
136+
func doesAliceWin(s string) bool {
137+
vowels := "aeiou"
138+
for _, c := range s {
139+
if strings.ContainsRune(vowels, c) {
140+
return true
141+
}
142+
}
143+
return false
144+
}
145+
```
101146

147+
#### TypeScript
148+
149+
```ts
150+
function doesAliceWin(s: string): boolean {
151+
const vowels = 'aeiou';
152+
for (const c of s) {
153+
if (vowels.includes(c)) {
154+
return true;
155+
}
156+
}
157+
return false;
158+
}
102159
```
103160

104161
<!-- tabs:end -->

‎solution/3200-3299/3227.Vowels Game in a String/Solution.cpp

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
class Solution {
2+
public:
3+
bool doesAliceWin(string s) {
4+
string vowels = "aeiou";
5+
for (char c : s) {
6+
if (vowels.find(c) != string::npos) {
7+
return true;
8+
}
9+
}
10+
return false;
11+
}
12+
};

0 commit comments

Comments
 (0)