Giả sử chúng ta có dãy số num và hai mảng khác l và r có kích thước m, những l và r này đại diện cho các truy vấn phạm vi như [l [i], r [i]]. Chúng ta phải tìm một dãy Boolean ans, trong đó ans [i] là true khi dãy con nums [l [i]], nums [l [i] + 1], ... nums [r [i] - 1], nums [r [i]] có thể được sắp xếp để tạo ra một chuỗi số học, nếu không thì sai.
Một dãy số được cho là cấp số cộng, nếu nó bao gồm ít nhất hai phần tử và hiệu của mỗi hai phần tử liên tiếp là như nhau. Ví dụ:một số chuỗi số học là:[2, 4, 6, 8, 10], [5, 5, 5, 5], [4, -2, -8, -14], nhưng không phải [2, 2, 3, 6, 9].
Vì vậy, nếu đầu vào giống như nums =[6,8,7,11,5,9], l =[0,0,2], r =[2,3,5], thì đầu ra sẽ là [True , Sai, Đúng] bởi vì -
-
đối với truy vấn [0, 2], trình tự là [6,8,7], có thể được sắp xếp lại thành [6,7,8], điều này hợp lệ
-
đối với truy vấn [0, 3], trình tự là [6,8,7,11], không thể được sắp xếp lại theo trình tự số học
-
đối với truy vấn [2, 5], trình tự là [7,11,5,9], có thể được sắp xếp lại thành [5,7,9,11], điều này hợp lệ
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
new:=một danh sách có kích thước giống như l và điền với tất cả các giá trị đúng
-
đối với tôi trong phạm vi từ 0 đến kích thước l - 1, thực hiện
-
data:=danh sách con gồm các số từ chỉ mục l [i] đến r [i]
-
sắp xếp dữ liệu danh sách
-
d:=một danh sách mới
-
đối với j trong phạm vi 0 đến kích thước của dữ liệu - 2, thực hiện
-
chèn dữ liệu [j + 1] - dữ liệu [j] vào cuối d
-
-
d:=một danh sách mới từ một tập hợp mới từ d
-
nếu kích thước của d không bằng 1, thì
-
new [i]:=False
-
-
-
trả lại mới
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
def solve(nums, l, r): new = [True]*len(l) for i in range(len(l)): data = nums[l[i]:r[i]+1] data.sort() d = [] for j in range(len(data) - 1): d.append(data[j+1] - data[j]) d = list(set(d)) if len(d) != 1: new[i] = False return new nums = [6,8,7,11,5,9] l = [0,0,2] r = [2,3,5] print(solve(nums, l, r))
Đầu vào
[6,8,7,11,5,9], [0,0,2], [2,3,5]
Đầu ra
[True,False,True]