Skip to content

Commit c993d20

Browse files
yanglbmeyanglbme
authored
feat: add solutions to lcci problems: No.05.03,05.07 (doocs#2671)
1 parent 98a06a8 commit c993d20

File tree

10 files changed

+117
-94
lines changed

10 files changed

+117
-94
lines changed

‎lcci/05.03.Reverse Bits/README.md

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -91,6 +91,21 @@ func reverseBits(num int) (ans int) {
9191
}
9292
```
9393

94+
```ts
95+
function reverseBits(num: number): number {
96+
let ans = 0;
97+
let cnt = 0;
98+
for (let i = 0, j = 0; i < 32; ++i) {
99+
cnt += ((num >> i) & 1) ^ 1;
100+
for (; cnt > 1; ++j) {
101+
cnt -= ((num >> j) & 1) ^ 1;
102+
}
103+
ans = Math.max(ans, i - j + 1);
104+
}
105+
return ans;
106+
}
107+
```
108+
94109
```swift
95110
class Solution {
96111
func reverseBits(_ num: Int) -> Int {

‎lcci/05.03.Reverse Bits/README_EN.md

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -97,6 +97,21 @@ func reverseBits(num int) (ans int) {
9797
}
9898
```
9999

100+
```ts
101+
function reverseBits(num: number): number {
102+
let ans = 0;
103+
let cnt = 0;
104+
for (let i = 0, j = 0; i < 32; ++i) {
105+
cnt += ((num >> i) & 1) ^ 1;
106+
for (; cnt > 1; ++j) {
107+
cnt -= ((num >> j) & 1) ^ 1;
108+
}
109+
ans = Math.max(ans, i - j + 1);
110+
}
111+
return ans;
112+
}
113+
```
114+
100115
```swift
101116
class Solution {
102117
func reverseBits(_ num: Int) -> Int {

‎lcci/05.03.Reverse Bits/Solution.ts

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
function reverseBits(num: number): number {
2+
let ans = 0;
3+
let cnt = 0;
4+
for (let i = 0, j = 0; i < 32; ++i) {
5+
cnt += ((num >> i) & 1) ^ 1;
6+
for (; cnt > 1; ++j) {
7+
cnt -= ((num >> j) & 1) ^ 1;
8+
}
9+
ans = Math.max(ans, i - j + 1);
10+
}
11+
return ans;
12+
}

‎lcci/05.06.Convert Integer/README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -31,7 +31,7 @@
3131

3232
### 方法一：位运算
3333

34-
我们将 A 和 B 进行异或运算，得到的结果中 $1$ 的个数即为需要改变的位数。
34+
我们将 A 和 B 进行异或运算，得到的结果的二进制表示中 $1$ 的个数即为需要改变的位数。
3535

3636
时间复杂度 $O(\log n)$，其中 $n$ 为 A 和 B 的最大值。空间复杂度 $O(1)$。
3737

‎lcci/05.07.Exchange/README.md

Lines changed: 14 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -29,7 +29,11 @@
2929

3030
## 解法
3131

32-
### 方法一
32+
### 方法一：位运算
33+
34+
我们可以将 $\text{num}$ 与 $\text{0x55555555}$ 进行与运算，得到的结果是 $\text{num}$ 的偶数位，然后将其左移一位。再将 $\text{num}$ 与 $\text{0xaaaaaaaa}$ 进行与运算，得到的结果是 $\text{num}$ 的奇数位，然后将其右移一位。最后将两个结果进行或运算，即可得到答案。
35+
36+
时间复杂度 $O(1)$，空间复杂度 $O(1)$。
3337

3438
<!-- tabs:start -->
3539

@@ -62,21 +66,17 @@ func exchangeBits(num int) int {
6266
}
6367
```
6468

69+
```ts
70+
function exchangeBits(num: number): number {
71+
return ((num & 0x55555555) << 1) | ((num & 0xaaaaaaaa) >>> 1);
72+
}
73+
```
74+
6575
```rust
6676
impl Solution {
67-
pub fn exchange_bits(mut num: i32) -> i32 {
68-
let mut res = 0;
69-
let mut i = 0;
70-
while num != 0 {
71-
let a = num & 1;
72-
num >>= 1;
73-
let b = num & 1;
74-
num >>= 1;
75-
res |= a << (i + 1);
76-
res |= b << i;
77-
i += 2;
78-
}
79-
res
77+
pub fn exchange_bits(num: i32) -> i32 {
78+
let num = num as u32;
79+
(((num & 0x55555555) << 1) | ((num & 0xaaaaaaaa) >> 1)) as i32
8080
}
8181
}
8282
```

‎lcci/05.07.Exchange/README_EN.md

Lines changed: 14 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -35,7 +35,11 @@
3535

3636
## Solutions
3737

38-
### Solution 1
38+
### Solution 1: Bit Manipulation
39+
40+
We can perform a bitwise AND operation between `num` and `0x55555555` to get the even bits of `num`, and then shift them one bit to the left. Then, we perform a bitwise AND operation between `num` and `0xaaaaaaaa` to get the odd bits of `num`, and then shift them one bit to the right. Finally, we perform a bitwise OR operation on the two results to get the answer.
41+
42+
The time complexity is $O(1)$, and the space complexity is $O(1)$.
3943

4044
<!-- tabs:start -->
4145

@@ -68,21 +72,17 @@ func exchangeBits(num int) int {
6872
}
6973
```
7074

75+
```ts
76+
function exchangeBits(num: number): number {
77+
return ((num & 0x55555555) << 1) | ((num & 0xaaaaaaaa) >>> 1);
78+
}
79+
```
80+
7181
```rust
7282
impl Solution {
73-
pub fn exchange_bits(mut num: i32) -> i32 {
74-
let mut res = 0;
75-
let mut i = 0;
76-
while num != 0 {
77-
let a = num & 1;
78-
num >>= 1;
79-
let b = num & 1;
80-
num >>= 1;
81-
res |= a << (i + 1);
82-
res |= b << i;
83-
i += 2;
84-
}
85-
res
83+
pub fn exchange_bits(num: i32) -> i32 {
84+
let num = num as u32;
85+
(((num & 0x55555555) << 1) | ((num & 0xaaaaaaaa) >> 1)) as i32
8686
}
8787
}
8888
```

‎lcci/05.07.Exchange/Solution.rs

Lines changed: 3 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -1,16 +1,6 @@
11
impl Solution {
2-
pub fn exchange_bits(mut num: i32) -> i32 {
3-
let mut res = 0;
4-
let mut i = 0;
5-
while num != 0 {
6-
let a = num & 1;
7-
num >>= 1;
8-
let b = num & 1;
9-
num >>= 1;
10-
res |= a << (i + 1);
11-
res |= b << i;
12-
i += 2;
13-
}
14-
res
2+
pub fn exchange_bits(num: i32) -> i32 {
3+
let num = num as u32;
4+
(((num & 0x55555555) << 1) | ((num & 0xaaaaaaaa) >> 1)) as i32
155
}
166
}

‎lcci/05.07.Exchange/Solution.ts

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
function exchangeBits(num: number): number {
2+
return ((num & 0x55555555) << 1) | ((num & 0xaaaaaaaa) >>> 1);
3+
}

‎lcci/08.01.Three Steps Problem/README.md

Lines changed: 20 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -200,6 +200,26 @@ class Solution:
200200
return sum(pow(a, n - 4)[0]) % mod
201201
```
202202

203+
```python
204+
import numpy as np
205+
206+
207+
class Solution:
208+
def waysToStep(self, n: int) -> int:
209+
if n < 4:
210+
return 2 ** (n - 1)
211+
mod = 10**9 + 7
212+
factor = np.mat([(1, 1, 0), (1, 0, 1), (1, 0, 0)], np.dtype("O"))
213+
res = np.mat([(4, 2, 1)], np.dtype("O"))
214+
n -= 4
215+
while n:
216+
if n & 1:
217+
res = res * factor % mod
218+
factor = factor * factor % mod
219+
n >>= 1
220+
return res.sum() % mod
221+
```
222+
203223
```java
204224
class Solution {
205225
private final int mod = (int) 1e9 + 7;
@@ -388,30 +408,4 @@ function pow(a, n) {
388408

389409
<!-- tabs:end -->
390410

391-
### 方法三
392-
393-
<!-- tabs:start -->
394-
395-
```python
396-
import numpy as np
397-
398-
399-
class Solution:
400-
def waysToStep(self, n: int) -> int:
401-
if n < 4:
402-
return 2 ** (n - 1)
403-
mod = 10**9 + 7
404-
factor = np.mat([(1, 1, 0), (1, 0, 1), (1, 0, 0)], np.dtype("O"))
405-
res = np.mat([(4, 2, 1)], np.dtype("O"))
406-
n -= 4
407-
while n:
408-
if n & 1:
409-
res = res * factor % mod
410-
factor = factor * factor % mod
411-
n >>= 1
412-
return res.sum() % mod
413-
```
414-
415-
<!-- tabs:end -->
416-
417411
<!-- end -->

‎lcci/08.01.Three Steps Problem/README_EN.md

Lines changed: 20 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -202,6 +202,26 @@ class Solution:
202202
return sum(pow(a, n - 4)[0]) % mod
203203
```
204204

205+
```python
206+
import numpy as np
207+
208+
209+
class Solution:
210+
def waysToStep(self, n: int) -> int:
211+
if n < 4:
212+
return 2 ** (n - 1)
213+
mod = 10**9 + 7
214+
factor = np.mat([(1, 1, 0), (1, 0, 1), (1, 0, 0)], np.dtype("O"))
215+
res = np.mat([(4, 2, 1)], np.dtype("O"))
216+
n -= 4
217+
while n:
218+
if n & 1:
219+
res = res * factor % mod
220+
factor = factor * factor % mod
221+
n >>= 1
222+
return res.sum() % mod
223+
```
224+
205225
```java
206226
class Solution {
207227
private final int mod = (int) 1e9 + 7;
@@ -390,30 +410,4 @@ function pow(a, n) {
390410

391411
<!-- tabs:end -->
392412

393-
### Solution 3
394-
395-
<!-- tabs:start -->
396-
397-
```python
398-
import numpy as np
399-
400-
401-
class Solution:
402-
def waysToStep(self, n: int) -> int:
403-
if n < 4:
404-
return 2 ** (n - 1)
405-
mod = 10**9 + 7
406-
factor = np.mat([(1, 1, 0), (1, 0, 1), (1, 0, 0)], np.dtype("O"))
407-
res = np.mat([(4, 2, 1)], np.dtype("O"))
408-
n -= 4
409-
while n:
410-
if n & 1:
411-
res = res * factor % mod
412-
factor = factor * factor % mod
413-
n >>= 1
414-
return res.sum() % mod
415-
```
416-
417-
<!-- tabs:end -->
418-
419413
<!-- end -->

0 commit comments

Comments
 (0)