Chúng ta cần viết một hàm JavaScript nhận vào một mảng số nguyên làm đối số đầu tiên và duy nhất.
Hàm nên tìm và trả về độ dài của chuỗi liên tiếp tăng dần dài nhất tồn tại trong mảng (liên tiếp hoặc không liên tiếp).
Ví dụ:
Nếu mảng đầu vào là:
const arr = [4, 6, 9, 1, 2, 8, 5, 3, -1];
Thì đầu ra nên là 6 vì chuỗi liên tiếp tăng dần dài nhất là 1, 2, 3, 4, 5, 6.
Ví dụ
Dưới đây là mã nguồn:
const arr = [4, 6, 9, 1, 2, 8, 5, 3, -1]; const consecutiveSequence = (arr = []) => { const consecutiveRight = {}; let max = 0; for (let i = 0; i < arr.length; i += 1) { let curr = arr[i]; if (consecutiveRight[curr] !== undefined) { continue; // We already have this number. consecutiveRight[curr] = 1 + (consecutiveRight[curr + 1] || 0); while (consecutiveRight[curr - 1] !== undefined) { consecutiveRight[curr - 1] = consecutiveRight[curr] + 1; curr -= 1; } max = Math.max(max, consecutiveRight[curr]); } return max; }; console.log(consecutiveSequence(arr));Kết quả
Đầu ra trên console:
6
Giải thích: Longest Consecutive Sequence (LeetCode 128). Dùng hashmap lưu độ dài chuỗi consecutive bắt đầu từ số đó. Khi xử lý x, set length[x] = 1 + length[x+1], rồi update ngược length[x-1], length[x-2]... O(n) time average. Cách chuẩn: dùng Set, chỉ bắt đầu đếm từ số không có predecessor (x-1 not in set).