Skip to content

Commit af6edcf

Browse files
yanglbmeyanglbme
authored
feat: add solutions to lcci problems (doocs#1773)
* No.10.11.Peaks and Valleys * No.16.01.Swap Numbers * No.16.02.Words Frequency * No.16.05.Factorial Zeros * No.16.07.Maximum * No.16.11.Diving Board * No.16.14.Best Line * No.16.15.Master Mind * No.16.16.Sub Sort * No.16.17.Contiguous Sequence * No.16.18.Pattern Matching * No.16.19.Pond Sizes * No.16.20.T9 * No.16.21.Sum Swap * No.16.22.Langtons Ant * No.16.24.Pairs With Sum
1 parent 5774816 commit af6edcf

File tree

30 files changed

+364
-289
lines changed

30 files changed

+364
-289
lines changed

‎.github/workflows/pretter-lint.yml

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,8 @@
11
name: prettier-linter
22

33
on:
4-
push: {}
5-
pull_request: {}
4+
push: {}
5+
pull_request: {}
66

77
jobs:
88
prettier:

‎lcci/10.11.Peaks and Valleys/README_EN.md

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -20,6 +20,12 @@
2020

2121
## Solutions
2222

23+
**Solution 1: Sorting**
24+
25+
We first sort the array, and then traverse the array and swap the elements at even indices with their next element.
26+
27+
The time complexity is $O(n \times \log n)$, and the space complexity is $O(\log n)$. Here, $n$ is the length of the array.
28+
2329
<!-- tabs:start -->
2430

2531
### **Python3**

‎lcci/16.01.Swap Numbers/README.md

Lines changed: 19 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -19,7 +19,25 @@
1919

2020
<!-- 这里可写通用的实现逻辑 -->
2121

22-
异或运算。
22+
**方法一：位运算**
23+
24+
我们可以使用异或运算 $\oplus$ 来实现两个数的交换。
25+
26+
异或运算有以下三个性质。
27+
28+
- 任何数和 $0$ 做异或运算，结果仍然是原来的数，即 $a \oplus 0=a$。
29+
- 任何数和其自身做异或运算，结果是 $0$，即 $a \oplus a=0$。
30+
- 异或运算满足交换律和结合律，即 $a \oplus b \oplus a=b \oplus a \oplus a=b \oplus (a \oplus a)=b \oplus 0=b$。
31+
32+
因此，我们可以对 $numbers$ 中的两个数 $a$ 和 $b$ 进行如下操作：
33+
34+
- $a=a \oplus b$，此时 $a$ 中存储了两个数的异或结果；
35+
- $b=a \oplus b$，此时 $b$ 中存储了原来 $a$ 的值；
36+
- $a=a \oplus b$，此时 $a$ 中存储了原来 $b$ 的值；
37+
38+
这样，我们就可以实现在不使用临时变量的情况下对两个数进行交换。
39+
40+
时间复杂度 $O(1)$，空间复杂度 $O(1)$。
2341

2442
<!-- tabs:start -->
2543

‎lcci/16.01.Swap Numbers/README_EN.md

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -24,6 +24,26 @@
2424

2525
## Solutions
2626

27+
**Solution 1: Bitwise Operation**
28+
29+
We can use the XOR operation $\oplus$ to implement the swap of two numbers.
30+
31+
The XOR operation has the following three properties:
32+
33+
- Any number XORed with $0$ remains unchanged, i.e., $a \oplus 0=a$.
34+
- Any number XORed with itself results in $0$, i.e., $a \oplus a=0$.
35+
- The XOR operation satisfies the commutative and associative laws, i.e., $a \oplus b \oplus a=b \oplus a \oplus a=b \oplus (a \oplus a)=b \oplus 0=b$.
36+
37+
Therefore, we can perform the following operations on two numbers $a$ and $b$ in the array $numbers$:
38+
39+
- $a=a \oplus b$, now $a$ stores the XOR result of the two numbers;
40+
- $b=a \oplus b$, now $b$ stores the original value of $a$;
41+
- $a=a \oplus b$, now $a$ stores the original value of $b$;
42+
43+
In this way, we can swap two numbers without using a temporary variable.
44+
45+
The time complexity is $O(1)$, and the space complexity is $O(1)$.
46+
2747
<!-- tabs:start -->
2848

2949
### **Python3**

‎lcci/16.02.Words Frequency/README.md

Lines changed: 10 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,7 @@
55
## 题目描述
66

77
<!-- 这里写题目描述 -->
8+
89
<p>设计一个方法，找出任意指定单词在一本书中的出现频率。</p>
910
<p>你的实现应该支持如下操作：</p>
1011
<ul>
@@ -33,9 +34,11 @@ wordsFrequency.get("pen"); //返回1
3334

3435
**方法一：哈希表**
3536

36-
我们用哈希表 `cnt` 统计每个单词出现的次数，`get` 函数直接返回 `cnt[word]` 即可。
37+
我们用哈希表 $cnt$ 统计 $book$ 中每个单词出现的次数。
38+
39+
调用 `get` 函数时，我们只需要返回 $cnt$ 中对应的单词的出现次数即可。
3740

38-
初始化哈希表 `cnt` 的时间复杂度为 $O(n)$，其中 $n$ 为 `book` 的长度。`get` 函数的时间复杂度为 $O(1)$。空间复杂度为 $O(n)$。
41+
时间复杂度方面，初始化哈希表 $cnt$ 的时间复杂度为 $O(n)$，其中 $n$ 为 $book$ 的长度。`get` 函数的时间复杂度为 $O(1)$。空间复杂度为 $O(n)$。
3942

4043
<!-- tabs:start -->
4144

@@ -194,7 +197,7 @@ class WordsFrequency {
194197
```rust
195198
use std::collections::HashMap;
196199
struct WordsFrequency {
197-
counter: HashMap<String, i32>
200+
cnt: HashMap<String, i32>
198201
}
199202

200203

@@ -205,15 +208,15 @@ struct WordsFrequency {
205208
impl WordsFrequency {
206209

207210
fn new(book: Vec<String>) -> Self {
208-
let mut counter = HashMap::new();
211+
let mut cnt = HashMap::new();
209212
for word in book.into_iter() {
210-
*counter.entry(word).or_insert(0) += 1;
213+
*cnt.entry(word).or_insert(0) += 1;
211214
}
212-
Self { counter }
215+
Self { cnt }
213216
}
214217

215218
fn get(&self, word: String) -> i32 {
216-
*self.counter.get(&word).unwrap_or(&0)
219+
*self.cnt.get(&word).unwrap_or(&0)
217220
}
218221
}
219222

‎lcci/16.02.Words Frequency/README_EN.md

Lines changed: 13 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -42,6 +42,14 @@ wordsFrequency.get(&quot;pen&quot;); //returns 1
4242

4343
## Solutions
4444

45+
**Solution 1: Hash Table**
46+
47+
We use a hash table $cnt$ to count the number of occurrences of each word in $book$.
48+
49+
When calling the `get` function, we only need to return the number of occurrences of the corresponding word in $cnt$.
50+
51+
In terms of time complexity, the time complexity of initializing the hash table $cnt$ is $O(n)$, where $n$ is the length of $book$. The time complexity of the `get` function is $O(1)$. The space complexity is $O(n)$.
52+
4553
<!-- tabs:start -->
4654

4755
### **Python3**
@@ -195,7 +203,7 @@ class WordsFrequency {
195203
```rust
196204
use std::collections::HashMap;
197205
struct WordsFrequency {
198-
counter: HashMap<String, i32>
206+
cnt: HashMap<String, i32>
199207
}
200208

201209

@@ -206,15 +214,15 @@ struct WordsFrequency {
206214
impl WordsFrequency {
207215

208216
fn new(book: Vec<String>) -> Self {
209-
let mut counter = HashMap::new();
217+
let mut cnt = HashMap::new();
210218
for word in book.into_iter() {
211-
*counter.entry(word).or_insert(0) += 1;
219+
*cnt.entry(word).or_insert(0) += 1;
212220
}
213-
Self { counter }
221+
Self { cnt }
214222
}
215223

216224
fn get(&self, word: String) -> i32 {
217-
*self.counter.get(&word).unwrap_or(&0)
225+
*self.cnt.get(&word).unwrap_or(&0)
218226
}
219227
}
220228

‎lcci/16.02.Words Frequency/Solution.py

Lines changed: 11 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,11 @@
1-
class WordsFrequency:
2-
def __init__(self, book: List[str]):
3-
self.cnt = Counter(book)
4-
5-
def get(self, word: str) -> int:
6-
return self.cnt[word]
7-
8-
9-
# Your WordsFrequency object will be instantiated and called as such:
10-
# obj = WordsFrequency(book)
11-
# param_1 = obj.get(word)
1+
class WordsFrequency:
2+
def __init__(self, book: List[str]):
3+
self.cnt = Counter(book)
4+
5+
def get(self, word: str) -> int:
6+
return self.cnt[word]
7+
8+
9+
# Your WordsFrequency object will be instantiated and called as such:
10+
# obj = WordsFrequency(book)
11+
# param_1 = obj.get(word)

‎lcci/16.02.Words Frequency/Solution.rs

Lines changed: 29 additions & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -1,30 +1,30 @@
1-
use std::collections::HashMap;
2-
struct WordsFrequency {
3-
counter: HashMap<String, i32>
4-
}
5-
6-
7-
/**
8-
* `&self` means the method takes an immutable reference.
9-
* If you need a mutable reference, change it to `&mut self` instead.
10-
*/
11-
impl WordsFrequency {
12-
13-
fn new(book: Vec<String>) -> Self {
14-
let mut counter = HashMap::new();
15-
for word in book.into_iter() {
16-
*counter.entry(word).or_insert(0) += 1;
17-
}
18-
Self { counter }
19-
}
20-
21-
fn get(&self, word: String) -> i32 {
22-
*self.counter.get(&word).unwrap_or(&0)
23-
}
24-
}
25-
26-
/**
27-
* Your WordsFrequency object will be instantiated and called as such:
28-
* let obj = WordsFrequency::new(book);
29-
* let ret_1: i32 = obj.get(word);
1+
use std::collections::HashMap;
2+
struct WordsFrequency {
3+
cnt: HashMap<String, i32>
4+
}
5+
6+
7+
/**
8+
* `&self` means the method takes an immutable reference.
9+
* If you need a mutable reference, change it to `&mut self` instead.
10+
*/
11+
impl WordsFrequency {
12+
13+
fn new(book: Vec<String>) -> Self {
14+
let mut cnt = HashMap::new();
15+
for word in book.into_iter() {
16+
*cnt.entry(word).or_insert(0) += 1;
17+
}
18+
Self { cnt }
19+
}
20+
21+
fn get(&self, word: String) -> i32 {
22+
*self.cnt.get(&word).unwrap_or(&0)
23+
}
24+
}
25+
26+
/**
27+
* Your WordsFrequency object will be instantiated and called as such:
28+
* let obj = WordsFrequency::new(book);
29+
* let ret_1: i32 = obj.get(word);
3030
*/

‎lcci/16.05.Factorial Zeros/README_EN.md

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -27,6 +27,19 @@
2727

2828
## Solutions
2929

30+
**Solution 1: Mathematics**
31+
32+
The problem is actually asking for the number of factors of $5$ in $[1,n]$.
33+
34+
Let's take $130$ as an example:
35+
36+
1. Divide $130$ by $5$ for the first time, and get $26$, which means there are $26$ numbers containing a factor of $5$.
37+
2. Divide $26$ by $5$ for the second time, and get $5$, which means there are $5$ numbers containing a factor of $5^2$.
38+
3. Divide $5$ by $5$ for the third time, and get $1$, which means there is $1$ number containing a factor of $5^3$.
39+
4. Add up all the counts to get the total number of factors of $5$ in $[1,n]$.
40+
41+
The time complexity is $O(\log n)$, and the space complexity is $O(1)$.
42+
3043
<!-- tabs:start -->
3144

3245
### **Python3**

‎lcci/16.07.Maximum/README_EN.md

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -16,6 +16,14 @@
1616

1717
## Solutions
1818

19+
**Solution 1: Bitwise Operation**
20+
21+
We can extract the sign bit $k$ of $a-b$. If the sign bit is $1$, it means $a \lt b$; if the sign bit is $0$, it means $a \ge b$.
22+
23+
Then the final result is $a \times (k \oplus 1) + b \times k$.
24+
25+
The time complexity is $O(1)$, and the space complexity is $O(1)$.
26+
1927
<!-- tabs:start -->
2028

2129
### **Python3**

0 commit comments

Comments
 (0)