Skip to content

Commit 4e75425

Browse files
yanglbmeyanglbme
authored
feat: add solutions to lcci problems: No.16.10,16.11 (doocs#1769)
* No.16.10.Living People * No.16.11.Diving Board
1 parent 3ff3994 commit 4e75425

11 files changed

Lines changed: 392 additions & 208 deletions

File tree

‎lcci/16.10.Living People/README.md‎

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

77
<!-- 这里写题目描述 -->
8+
89
<p>给定N个人的出生年份和死亡年份，第<code>i</code>个人的出生年份为<code>birth[i]</code>，死亡年份为<code>death[i]</code>，实现一个方法以计算生存人数最多的年份。</p>
910
<p>你可以假设所有人都出生于1900年至2000年（含1900和2000）之间。如果一个人在某一年的任意时期都处于生存状态，那么他们应该被纳入那一年的统计中。例如，生于1908年、死于1909年的人应当被列入1908年和1909年的计数。</p>
1011
<p>如果有多个年份生存人数相同且均为最大值，输出其中最小的年份。</p>
@@ -24,13 +25,15 @@ death = {1948, 1951, 2000}
2425

2526
<!-- 这里可写通用的实现逻辑 -->
2627

27-
不在乎某个区间，而是某一年的最多存活人数。
28+
**方法一：差分数组**
29+
30+
题目实际上是对一个连续的区间进行加减操作，然后求最大值。这种情况下可以使用差分数组来解决。
2831

29-
可以使用哈希表来统计每年的存活人数，当 `birth[i] >= year && year <= death[i]`，该年份的存活人数加一。
32+
由于题目中的年份范围是固定的，所以可以使用一个长度为 $102$ 的数组来表示 $1900$ 年到 $2000$ 年的人口变化情况。数组中的每个元素表示该年份的人口变化，正数表示出生人数，负数表示死亡人数。
3033

31-
> 只有 `birth` 和 `death` 当中的出现过的年份才是有效年份，或者说，可能成为返回值的年份。
34+
遍历每个人的出生年份和死亡年份，对应的年份的人口变化加一和减一。然后遍历差分数组，求出差分数组的前缀和的最大值，最大值对应的年份即为答案。
3235

33-
题目当中已说明年份范围是 `1900 ~ 2000`，对此也可以使用数组进行计数（`year - 1900`）。
36+
时间复杂度 $O(n)$，空间复杂度 $O(C)$。其中 $n$ 是出生年份和死亡年份的长度，而 $C$ 是年份的范围。
3437

3538
<!-- tabs:start -->
3639

@@ -41,19 +44,19 @@ death = {1948, 1951, 2000}
4144
```python
4245
class Solution:
4346
def maxAliveYear(self, birth: List[int], death: List[int]) -> int:
44-
years = [0] * 101
45-
for i in range(len(birth)):
46-
start = birth[i] - 1900
47-
end = death[i] - 1900
48-
for j in range(start, end + 1):
49-
years[j] += 1
50-
max_v = years[0]
51-
res = 0
52-
for i in range(1, 101):
53-
if years[i] > max_v:
54-
max_v = years[i]
55-
res = i
56-
return 1900 + res
47+
base = 1900
48+
d = [0] * 102
49+
for a, b in zip(birth, death):
50+
d[a - base] += 1
51+
d[b + 1 - base] -= 1
52+
s = mx = 0
53+
ans = 0
54+
for i, x in enumerate(d):
55+
s += x
56+
if mx < s:
57+
mx = s
58+
ans = base + i
59+
return ans
5760
```
5861

5962
### **Java**
@@ -63,58 +66,101 @@ class Solution:
6366
```java
6467
class Solution {
6568
public int maxAliveYear(int[] birth, int[] death) {
66-
int[] years = new int[101];
67-
int n = birth.length;
68-
for (int i = 0; i < n; ++i) {
69-
int start = birth[i] - 1900;
70-
int end = death[i] - 1900;
71-
for (int j = start; j <= end; ++j) {
72-
++years[j];
69+
int base = 1900;
70+
int[] d = new int[102];
71+
for (int i = 0; i < birth.length; ++i) {
72+
int a = birth[i] - base;
73+
int b = death[i] - base;
74+
++d[a];
75+
--d[b + 1];
76+
}
77+
int s = 0, mx = 0;
78+
int ans = 0;
79+
for (int i = 0; i < d.length; ++i) {
80+
s += d[i];
81+
if (mx < s) {
82+
mx = s;
83+
ans = base + i;
7384
}
7485
}
75-
int max = years[0];
76-
int res = 0;
77-
for (int i = 1; i < 101; ++i) {
78-
if (years[i] > max) {
79-
max = years[i];
80-
res = i;
86+
return ans;
87+
}
88+
}
89+
```
90+
91+
### **C++**
92+
93+
```cpp
94+
class Solution {
95+
public:
96+
int maxAliveYear(vector<int>& birth, vector<int>& death) {
97+
int base = 1900;
98+
int d[102]{};
99+
for (int i = 0; i < birth.size(); ++i) {
100+
int a = birth[i] - base;
101+
int b = death[i] - base;
102+
++d[a];
103+
--d[b + 1];
104+
}
105+
int s = 0, mx = 0;
106+
int ans = 0;
107+
for (int i = 0; i < 102; ++i) {
108+
s += d[i];
109+
if (mx < s) {
110+
mx = s;
111+
ans = base + i;
81112
}
82113
}
83-
return 1900 + res;
114+
return ans;
84115
}
116+
};
117+
```
118+
119+
### **Go**
120+
121+
```go
122+
func maxAliveYear(birth []int, death []int) (ans int) {
123+
base := 1900
124+
d := [102]int{}
125+
for i, a := range birth {
126+
a -= base
127+
b := death[i] - base
128+
d[a]++
129+
d[b+1]--
130+
}
131+
mx, s := 0, 0
132+
for i, x := range d {
133+
s += x
134+
if mx < s {
135+
mx = s
136+
ans = base + i
137+
}
138+
}
139+
return
85140
}
86141
```
87142

88143
### **TypeScript**
89144

90145
```ts
91146
function maxAliveYear(birth: number[], death: number[]): number {
92-
const n = birth.length;
93-
const counter = new Map<number, number>();
94-
for (let i = 0; i < n; i++) {
95-
counter.set(birth[i], 0);
96-
counter.set(death[i], 0);
147+
const base = 1900;
148+
const d: number[] = Array(102).fill(0);
149+
for (let i = 0; i < birth.length; ++i) {
150+
const [a, b] = [birth[i] - base, death[i] - base];
151+
++d[a];
152+
--d[b + 1];
97153
}
98-
for (let i = 0; i < n; i++) {
99-
const start = birth[i];
100-
const end = death[i];
101-
for (const key of counter.keys()) {
102-
if (key >= start && key <= end) {
103-
counter.set(key, (counter.get(key) ?? 0) + 1);
104-
}
105-
}
106-
}
107-
let res = 0;
108-
let max = 0;
109-
for (const [key, val] of counter) {
110-
if (val === max) {
111-
res = Math.min(res, key);
112-
} else if (val > max) {
113-
res = key;
114-
max = Math.max(max, val);
154+
let [s, mx] = [0, 0];
155+
let ans = 0;
156+
for (let i = 0; i < d.length; ++i) {
157+
s += d[i];
158+
if (mx < s) {
159+
mx = s;
160+
ans = base + i;
115161
}
116162
}
117-
return res;
163+
return ans;
118164
}
119165
```
120166

@@ -124,22 +170,23 @@ function maxAliveYear(birth: number[], death: number[]): number {
124170
impl Solution {
125171
pub fn max_alive_year(birth: Vec<i32>, death: Vec<i32>) -> i32 {
126172
let n = birth.len();
127-
let mut counter = vec![0; 101];
173+
let mut d = vec![0; 102];
174+
let base = 1900;
128175
for i in 0..n {
129-
let (start, end) = (birth[i] - 1900, death[i] - 1900);
130-
for j in start..=end {
131-
counter[j as usize] += 1;
132-
}
176+
d[(birth[i] - base) as usize] += 1;
177+
d[(death[i] - base + 1) as usize] -= 1;
133178
}
134-
let mut res = 0;
135-
let mut max = 0;
136-
for (i, count) in counter.iter().enumerate() {
137-
if *count > max {
138-
res = i;
139-
max = *count;
179+
let mut ans = 0;
180+
let mut mx = 0;
181+
let mut s = 0;
182+
for i in 0..102 {
183+
s += d[i];
184+
if mx < s {
185+
mx = s;
186+
ans = base + i as i32;
140187
}
141188
}
142-
(res + 1900) as i32
189+
ans
143190
}
144191
}
145192
```

0 commit comments

Comments
 (0)