Tìm số chuỗi có thể có trong một mảng, với các điều kiện bổ sung

Question

Có một chuỗi {a1, a2, a3, a4, ..... aN}. Chạy là phần cực đại tăng hoặc giảm nghiêm ngặt phần liên tục của chuỗi. Ví dụ. Nếu chúng ta có một chuỗi {1,2,3,4,7,6,5,2,3,4,1,2} Chúng ta có 5 lần chạy {1,2,3,4,7}, {7, 6,5,2}, {2,3,4}, {4,1} và {1,2}.

Cho bốn số N, M, K, L. Đếm số lượng các số N có thể có M chính xác, mỗi số trong chuỗi nhỏ hơn hoặc bằng K và chênh lệch giữa các số liền kề nhỏ hơn L

Câu hỏi được đặt ra trong cuộc phỏng vấn.

Tôi chỉ có thể nghĩ ra giải pháp bạo lực. Giải pháp hiệu quả cho vấn đề này là gì?

Answer 1

Tôi cho rằng ý của bạn là 'giải pháp lực lượng vũ phu', điều tôi có ý nghĩa bằng 'giải pháp đơn giản liên quan đến vòng lặp lồng nhau trên N, M, K, L'? Đôi khi giải pháp đơn giản là đủ tốt. Một trong những lần khi giải pháp đơn giản là đủ tốt là khi bạn không có giải pháp tốt hơn. Một lần khác là khi các con số không quá lớn.

Với điều đó ra khỏi ngực của tôi, tôi sẽ viết các vòng theo hướng ngược lại, hoặc một cái gì đó như thế. Ý tôi là:

1. Tạo 2 cấu trúc dữ liệu phụ trợ, một để chứa các chỉ số của số < = K, một cho các chỉ số của các số có sự khác biệt với các nước láng giềng của họ là < = L.
2. Chạy qua danh sách các số và điền các cấu trúc dữ liệu phụ được đề cập ở trên.
3. Tìm giao điểm của các giá trị trong hai cấu trúc dữ liệu đó; đây sẽ là những chỉ số của những nơi thú vị để bắt đầu tìm kiếm cho chạy.
4. Nhìn vào từng địa điểm thú vị.

Cho đến khi ai đó chứng minh đây là giải pháp hiệu quả nhất.

Answer 2

Sử dụng lập trình động. Đối với mỗi số trong chuỗi con, hãy duy trì số lượng riêng biệt các chuỗi tăng tối đa và tối đa giảm. Khi bạn từng bước thêm một số mới vào cuối, bạn có thể sử dụng các số này để cập nhật số đếm cho số mới. Mức độ phức tạp: O (n^2)

Answer 3

Điều này có thể được lặp lại như là sự cố lặp lại. Nhìn vào vấn đề của bạn khi tìm kiếm # (N, M) (giả sử K và L là cố định, chúng được sử dụng trong các điều kiện lặp lại, do đó truyền bá cho phù hợp). Bây giờ bắt đầu với các hàm đếm hạn chế hơn A (N, M; a) và D (N, M, a), trong đó A đếm các tập hợp đó với lần chạy cuối cùng tăng dần, D đếm số lần chạy cuối cùng giảm dần, và a là giá trị của phần tử cuối cùng trong tập hợp.

Express # (N, M) theo A (N, M; a) và D (N, M; a) (là tổng của tất cả cho phép a). Bạn có thể lưu ý rằng có mối quan hệ giữa hai (giống như sự phản chiếu A (N, M; a) = D (N, M; K-a)) nhưng điều đó sẽ không quan trọng nhiều đối với phép tính ngoại trừ tốc độ điền bảng.

Bây giờ A (N, M; a) có thể được biểu diễn theo A (N-1, M; w), A (N-1, M-1; x), D (N-1, M) ; y) và D (N-1, M-1; z). Ý tưởng là nếu bạn bắt đầu với một tập hợp kích thước N-1 và biết hướng của lần chạy cuối cùng và giá trị của phần tử cuối cùng, bạn biết liệu thêm phần tử sẽ thêm vào một lần chạy hiện tại hay thêm chạy. Vì vậy, bạn có thể đếm số lượng các cách có thể để có được những gì bạn muốn từ các khả năng của trường hợp trước đó.

Tôi sẽ cho phép bạn viết đệ quy này xuống. Lưu ý rằng đây là nơi bạn chiếm L (chỉ thêm những người tuân theo giới hạn khoảng cách L) và K (tìm trường hợp kết thúc).

Chấm dứt đệ quy bằng cách sử dụng thực tế là A (1, 1; a) = 1, A (1, x> 1; a) = 0 (và tương tự cho D).

Bây giờ, vì đây là lần đệ quy nhiều lần, hãy đảm bảo triển khai lưu trữ kết quả trong bảng và bắt đầu bằng cách thử tra cứu (thường được gọi là lập trình động).