สมมติว่าผู้ควบคุมอาหารบริโภค calories[i] ซึ่งบ่งบอกแคลอรี่ในวันที่ i หากเรามีจำนวนเต็ม k สำหรับลำดับต่อเนื่องของ k วัน คือ (calories[i], calories[i+1], ..., calories[i+k-1] สำหรับทุก 0 <= i <= n-k) พวกเขาจะหา T ซึ่งคือแคลอรี่รวมที่บริโภคในลำดับ k วันนั้น (calories[i] + calories[i+1] + ... + calories[i+k-1]): แต่มีเงื่อนไขดังนี้ −
- ถ้า T < lower bound แสดงว่าประสิทธิภาพแผนอาหารแย่ จึงเสีย 1 คะแนน
- ถ้า T > upper bound แสดงว่าประสิทธิภาพดี จึงได้ 1 คะแนน
- มิฉะนั้น ประสิทธิภาพปกติ คะแนนไม่เปลี่ยน
เริ่มต้นผู้ควบคุมอาหารมีศูนย์คะแนน เราต้องหาจำนวนคะแนนรวมที่ผู้ควบคุมอาหารได้รับ
ถ้าอาร์เรย์คือ [6,5,0,0] และ k = 2 และ lower := 1 และ upper := 5 ผลลัพธ์จะเป็น 0 C[0] + C[1] > upper จึงเพิ่ม 1 คะแนน lower <= C[1] + C[2] <= upper จึงไม่เปลี่ยน หลังจากนั้น C[2] + C[3] < lower จึงลด 1 คะแนน ดังนั้นผลลัพธ์คือ 0
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนต่อไปนี้ −
- temp := 0
- for i ในช่วง 0 ถึง k
- temp := temp + C[k]
- right := k - 1, left := 0, points := 0
- while right < ความยาวของ C ทำ
- ถ้า temp < lower ให้ลด points ลง 1 ถ้า temp > upper ให้เพิ่ม points ขึ้น 1
- temp := temp - C[left]
- เพิ่ม left และ right ขึ้น 1
- ถ้า right >= ความยาวของ C ให้ออกจากลูป
- temp := temp + C[right]
- คืนค่า points
ตัวอย่าง
มาดูการนำไปใช้เพื่อความเข้าใจที่ดีขึ้น −
class Solution(object):
def dietPlanPerformance(self, c, k, l, u):
temp = 0
for i in range(k):
temp += c[i]
right = k - 1
left = 0
points = 0
while right < len(c):
if temp < l:
points -= 1
elif temp > u:
points += 1
temp -= c[left]
left += 1
right += 1
if right >= len(c):
break
temp += c[right]
return points
ob1 = Solution()
print(ob1.dietPlanPerformance([6, 5, 0, 0], 2, 1, 5))
อินพุต
[6,5,0,0] 2 1 5
ผลลัพธ์
0
