สมมติว่าเราต้องการพัฒนาโครงสร้างข้อมูลที่สร้างขึ้นพร้อมกับลิสต์จำนวนเต็ม และมีฟังก์ชันสำหรับหาผลรวมขององค์ประกอบจากดัชนี i ถึง j-1 อย่างมีประสิทธิภาพ มีฟังก์ชันสองฟังก์ชัน:
- Constructor สร้างอินสแตนซ์ใหม่พร้อมอาร์เรย์จำนวนเต็ม
get_sum(i, j)คืนผลรวมของอิลีเมนต์อาร์เรย์จากดัชนีเริ่มต้นiถึงดัชนีสิ้นสุดj-1
เช่น ถ้าอินพุตคือ array = [5,2,3,6,4,7,8,9,3,2] สร้างอ็อบเจกต์ obj เรียก obj.get_sum(1,5) และ obj.get_sum(4,8) ผลลัพธ์จะเป็น 15 และ 28 ตามลำดับ ช่วงแรกคือ [2,3,6,4] ผลรวม 15 ช่วงที่สองคือ [4,7,8,9] ผลรวม 28
ขั้นตอนการแก้ปัญหา
- กำหนด Constructor รับ
array - สร้าง
sumsเป็นลิสต์ เริ่มต้นด้วย 0 - วนลูปแต่ละ
xในarrayให้เพิ่ม(x + sums[-1])เข้าsums - เมธอด
get_sum(i, j)คืนsums[j] - sums[i]
ตัวอย่างโค้ด
class RangeSum:
def __init__(self, array):
self.sums = [0]
for x in array:
self.sums.append(x + self.sums[-1])
def get_sum(self, i, j):
return self.sums[j] - self.sums[i]
array = [5,2,3,6,4,7,8,9,3,2]
obj = RangeSum(array)
print(obj.get_sum(1,5))
print(obj.get_sum(4,8))
อินพุต
[5,2,3,6,4,7,8,9,3,2] obj.get_sum(1,5) obj.get_sum(4,8)
เอาต์พุต
15 28
