Skip to content

Commit ec28d54

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc/lcof2 problems
1 parent 1227cde commit ec28d54

File tree

15 files changed

+612
-335
lines changed

15 files changed

+612
-335
lines changed

‎lcof2/剑指 Offer II 119. 最长连续序列/README.md

Lines changed: 169 additions & 81 deletions
Original file line numberDiff line numberDiff line change
@@ -45,25 +45,23 @@
4545

4646
**方法一：排序**
4747

48-
设 res 表示连续序列的最大长度，t 表示当前合法连续序列的长度，初始时 `res = t = 1`。
48+
我们先将数组排序，然后用一个变量 $t$ 记录当前连续序列的长度，用一个变量 $ans$ 记录最长连续序列的长度。
4949

50-
先排序数组，然后从下标 1 开始遍历数组，判断 `nums[i]` 与前一个数 `nums[i - 1]` 的大小关系：
50+
接下来，我们从下标 $i=1$ 开始遍历数组，对于当前遍历到的元素 $nums[i]$：
5151

52-
- 若 `nums[i] == nums[i - 1]`，直接跳过；
53-
- 若 `nums[i] - nums[i - 1] == 1`，说明是连续序列，t 自增，利用 `res = max(res, t)` 更新最大长度；
54-
- 否则 t 重置为 1，继续往下遍历。
52+
- 如果 $nums[i]=nums[i-1]$，则说明当前元素重复，无需考虑；
53+
- 如果 $nums[i]=nums[i-1]+1$，则说明当前元素可以接在上一个连续序列后面以形成更长的连续序列，我们更新 $t = t + 1$，然后更新答案 $ans = \max(ans, t)$；
54+
- 否则，说明当前元素无法接在上一个连续序列后面，我们将 $t$ 重新置为 $1$。
5555

56-
时间复杂度 $O(nlogn)$，空间复杂度 $O(1)$。
56+
最终，我们返回答案 $ans$ 即可。
5757

58-
**方法二：哈希表**
59-
60-
设 res 表示连续序列的最大长度，初始为 0。哈希表 s 存放数组出现的每个元素。
58+
时间复杂度 $O(n \times \log n)$，空间复杂度 $O(\log n)$。其中 $n$ 是数组的长度。
6159

62-
遍历数组，以当前遍历到的元素 `nums[i]` 做为起点，循环判断 `nums[i] + 1`，`nums[i] + 2` ... 是否存在 s 中，并不断更新连续序列的最大长度。
60+
**方法二：哈希表**
6361

64-
在这个过程中，如果 `nums[i]`, `nums[i] + 1`, `nums[i + 2]`, ... 是一个连续序列，遍历下个元素 `nums[i] + 1` 时，其实无需再重复循环。因此，只需要判断 `nums[i] - 1` 是否在 s 中，是则直接跳过。
62+
我们用哈希表存储数组中的所有元素，然后遍历数组中的每个元素 $x$，如果当前元素的前驱 $x-1$ 不在哈希表中，那么我们以当前元素为起点，不断尝试匹配 $x+1, x+2, x+3, \dots$，直到匹配不到为止，此时的匹配长度即为以 $x$ 为起点的最长连续序列长度，我们更新答案即可。
6563

66-
时间复杂度 $O(n)$，空间复杂度 $O(n)$。
64+
时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是数组的长度。
6765

6866
<!-- tabs:start -->
6967

@@ -78,31 +76,30 @@ class Solution:
7876
if n < 2:
7977
return n
8078
nums.sort()
81-
res = t = 1
82-
for i in range(1, n):
83-
if nums[i] == nums[i - 1]:
79+
ans = t = 1
80+
for a, b in pairwise(nums):
81+
if a == b:
8482
continue
85-
if nums[i] - nums[i - 1] == 1:
83+
if a + 1 == b:
8684
t += 1
87-
res = max(res, t)
85+
ans = max(ans, t)
8886
else:
8987
t = 1
90-
return res
88+
return ans
9189
```
9290

9391
```python
9492
class Solution:
9593
def longestConsecutive(self, nums: List[int]) -> int:
96-
s, res = set(nums), 0
97-
for num in nums:
98-
if num - 1 not in s:
99-
t = 1
100-
next = num + 1
101-
while next in s:
102-
t += 1
103-
next += 1
104-
res = max(res, t)
105-
return res
94+
s = set(nums)
95+
ans = 0
96+
for x in nums:
97+
if x - 1 not in s:
98+
y = x + 1
99+
while y in s:
100+
y += 1
101+
ans = max(ans, y - x)
102+
return ans
106103
```
107104

108105
### **Java**
@@ -113,23 +110,22 @@ class Solution:
113110
class Solution {
114111
public int longestConsecutive(int[] nums) {
115112
int n = nums.length;
116-
if (n < 1) {
113+
if (n < 2) {
117114
return n;
118115
}
119116
Arrays.sort(nums);
120-
int res = 1, t = 1;
117+
int ans = 1, t = 1;
121118
for (int i = 1; i < n; ++i) {
122119
if (nums[i] == nums[i - 1]) {
123120
continue;
124121
}
125-
if (nums[i] - nums[i - 1] == 1) {
126-
t += 1;
127-
res = Math.max(res, t);
122+
if (nums[i] == nums[i - 1] + 1) {
123+
ans = Math.max(ans, ++t);
128124
} else {
129125
t = 1;
130126
}
131127
}
132-
return res;
128+
return ans;
133129
}
134130
}
135131
```
@@ -138,20 +134,20 @@ class Solution {
138134
class Solution {
139135
public int longestConsecutive(int[] nums) {
140136
Set<Integer> s = new HashSet<>();
141-
for (int num : nums) {
142-
s.add(num);
137+
for (int x : nums) {
138+
s.add(x);
143139
}
144-
int res = 0;
145-
for (int num : nums) {
146-
if (!s.contains(num - 1)) {
147-
int t = 1, next = num + 1;
148-
while (s.contains(next++)) {
149-
++t;
140+
int ans = 0;
141+
for (int x : nums) {
142+
if (!s.contains(x - 1)) {
143+
int y = x + 1;
144+
while (s.contains(y)) {
145+
++y;
150146
}
151-
res = Math.max(res, t);
147+
ans = Math.max(ans, y - x);
152148
}
153149
}
154-
return res;
150+
return ans;
155151
}
156152
}
157153
```
@@ -163,21 +159,22 @@ class Solution {
163159
public:
164160
int longestConsecutive(vector<int>& nums) {
165161
int n = nums.size();
166-
if (n < 2)
162+
if (n < 2) {
167163
return n;
164+
}
168165
sort(nums.begin(), nums.end());
169-
int res = 1, t = 1;
166+
int ans = 1, t = 1;
170167
for (int i = 1; i < n; ++i) {
171-
if (nums[i] == nums[i - 1])
168+
if (nums[i] == nums[i - 1]) {
172169
continue;
173-
if (nums[i] - nums[i - 1] == 1) {
174-
++t;
175-
res = max(res, t);
170+
}
171+
if (nums[i] == nums[i - 1] + 1) {
172+
ans = max(ans, ++t);
176173
} else {
177174
t = 1;
178175
}
179176
}
180-
return res;
177+
return ans;
181178
}
182179
};
183180
```
@@ -186,19 +183,18 @@ public:
186183
class Solution {
187184
public:
188185
int longestConsecutive(vector<int>& nums) {
189-
unordered_set<int> s;
190-
for (int num : nums)
191-
s.insert(num);
192-
int res = 0;
193-
for (int num : nums) {
194-
if (!s.count(num - 1)) {
195-
int t = 1, next = num + 1;
196-
while (s.count(next++))
197-
++t;
198-
res = max(res, t);
186+
unordered_set<int> s(nums.begin(), nums.end());
187+
int ans = 0;
188+
for (int x : nums) {
189+
if (!s.count(x - 1)) {
190+
int y = x + 1;
191+
while (s.count(y)) {
192+
y++;
193+
}
194+
ans = max(ans, y - x);
199195
}
200196
}
201-
return res;
197+
return ans;
202198
}
203199
};
204200
```
@@ -212,17 +208,19 @@ func longestConsecutive(nums []int) int {
212208
return n
213209
}
214210
sort.Ints(nums)
215-
res, t := 1, 1
216-
for i := 1; i < n; i++ {
217-
if nums[i] == nums[i-1] {
211+
ans, t := 1, 1
212+
for i, x := range nums[1:] {
213+
if x == nums[i] {
218214
continue
219215
}
220-
if nums[i]-nums[i-1] == 1 {
216+
if x == nums[i]+1 {
221217
t++
222-
res = max(res, t)
218+
ans = max(ans, t)
219+
} else {
220+
t = 1
223221
}
224222
}
225-
return res
223+
return ans
226224
}
227225

228226
func max(a, b int) int {
@@ -234,23 +232,21 @@ func max(a, b int) int {
234232
```
235233

236234
```go
237-
func longestConsecutive(nums []int) int {
238-
s := make(map[int]bool)
239-
for _, num := range nums {
240-
s[num] = true
235+
func longestConsecutive(nums []int) (ans int) {
236+
s := map[int]bool{}
237+
for _, x := range nums {
238+
s[x] = true
241239
}
242-
res := 0
243-
for _, num := range nums {
244-
if !s[num-1] {
245-
t, next := 1, num+1
246-
for s[next] {
247-
next++
248-
t++
240+
for _, x := range nums {
241+
if !s[x-1] {
242+
y := x + 1
243+
for s[y] {
244+
y++
249245
}
250-
res = max(res, t)
246+
ans = max(ans, y-x)
251247
}
252248
}
253-
return res
249+
return
254250
}
255251

256252
func max(a, b int) int {
@@ -261,6 +257,98 @@ func max(a, b int) int {
261257
}
262258
```
263259

260+
### **JavaScript**
261+
262+
```js
263+
/**
264+
* @param {number[]} nums
265+
* @return {number}
266+
*/
267+
var longestConsecutive = function (nums) {
268+
const n = nums.length;
269+
if (n < 2) {
270+
return n;
271+
}
272+
nums.sort((a, b) => a - b);
273+
let ans = 1;
274+
let t = 1;
275+
for (let i = 1; i < n; ++i) {
276+
if (nums[i] === nums[i - 1]) {
277+
continue;
278+
}
279+
if (nums[i] === nums[i - 1] + 1) {
280+
ans = Math.max(ans, ++t);
281+
} else {
282+
t = 1;
283+
}
284+
}
285+
return ans;
286+
};
287+
```
288+
289+
```js
290+
/**
291+
* @param {number[]} nums
292+
* @return {number}
293+
*/
294+
var longestConsecutive = function (nums) {
295+
const s = new Set(nums);
296+
let ans = 0;
297+
for (const x of nums) {
298+
if (!s.has(x - 1)) {
299+
let y = x + 1;
300+
while (s.has(y)) {
301+
y++;
302+
}
303+
ans = Math.max(ans, y - x);
304+
}
305+
}
306+
return ans;
307+
};
308+
```
309+
310+
### **TypeScript**
311+
312+
```ts
313+
function longestConsecutive(nums: number[]): number {
314+
const n = nums.length;
315+
if (n < 2) {
316+
return n;
317+
}
318+
let ans = 1;
319+
let t = 1;
320+
nums.sort((a, b) => a - b);
321+
for (let i = 1; i < n; ++i) {
322+
if (nums[i] === nums[i - 1]) {
323+
continue;
324+
}
325+
if (nums[i] === nums[i - 1] + 1) {
326+
ans = Math.max(ans, ++t);
327+
} else {
328+
t = 1;
329+
}
330+
}
331+
return ans;
332+
}
333+
```
334+
335+
```ts
336+
function longestConsecutive(nums: number[]): number {
337+
const s: Set<number> = new Set(nums);
338+
let ans = 0;
339+
for (const x of s) {
340+
if (!s.has(x - 1)) {
341+
let y = x + 1;
342+
while (s.has(y)) {
343+
y++;
344+
}
345+
ans = Math.max(ans, y - x);
346+
}
347+
}
348+
return ans;
349+
}
350+
```
351+
264352
### **...**
265353

266354
```

‎lcof2/剑指 Offer II 119. 最长连续序列/Solution.cpp

Lines changed: 10 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -1,18 +1,17 @@
11
class Solution {
22
public:
33
int longestConsecutive(vector<int>& nums) {
4-
unordered_set<int> s;
5-
for (int num : nums)
6-
s.insert(num);
7-
int res = 0;
8-
for (int num : nums) {
9-
if (!s.count(num - 1)) {
10-
int t = 1, next = num + 1;
11-
while (s.count(next++))
12-
++t;
13-
res = max(res, t);
4+
unordered_set<int> s(nums.begin(), nums.end());
5+
int ans = 0;
6+
for (int x : nums) {
7+
if (!s.count(x - 1)) {
8+
int y = x + 1;
9+
while (s.count(y)) {
10+
y++;
11+
}
12+
ans = max(ans, y - x);
1413
}
1514
}
16-
return res;
15+
return ans;
1716
}
1817
};

0 commit comments

Comments
 (0)