สมมติว่าเรามีอาร์เรย์ของตัวเลขที่เรียกว่า nums และยังมีอีกค่าหนึ่งคือ K เราต้องตรวจสอบว่าเราสามารถแบ่งจำนวนอาร์เรย์เป็นอาร์เรย์ย่อยที่ต่อเนื่องกันของ K ได้หรือไม่ เพื่อให้ผลรวมขององค์ประกอบของแต่ละอาร์เรย์ย่อยมีค่าเท่ากัน
ดังนั้น หากอินพุตเป็น nums =[2, 5, 3, 4, 7] k =3 ผลลัพธ์จะเป็น True เนื่องจากเราสามารถสร้างสามพาร์ติชั่นเช่น [(2, 5), (3, 4), (7)] ทั้งหมดมีค่าเท่ากับ 7.
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- n :=ขนาดของ nums
- cumul_sum :=ผลรวมสะสมขององค์ประกอบทั้งหมดเป็น nums
- total_sum :=cumul_sum[n - 1]
- ถ้า Total_sum ไม่หารด้วย k แล้ว
- คืนค่าเท็จ
- นับ :=0, ตำแหน่ง :=-1
- สำหรับฉันในช่วง 0 ถึง n - 1 ทำ
- ถ้า pos เหมือนกับ -1 แล้ว
- ย่อย :=0
- มิฉะนั้น
- sub :=cumul_sum[pos]
- ถ้า cumul_sum[i] - ย่อยเหมือนกับ (total_sum / K) แล้ว
- ตำแหน่ง :=ผม
- นับ :=นับ + 1
- มิฉะนั้น เมื่อ cumul_sum[i] - cumul_sum[pos]> (total_sum / K) แล้ว
- ออกมาจากลูป
- ถ้า pos เหมือนกับ -1 แล้ว
- คืนค่า จริง เมื่อนับเหมือนกับ K มิฉะนั้น เท็จ
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def solve(nums, k): n = len(nums) cumul_sum = [0 for i in range(n)] cumul_sum[0] = nums[0] for i in range(1, n): cumul_sum[i] = cumul_sum[i - 1] + nums[i] total_sum = cumul_sum[n - 1] if total_sum % k != 0: return False count = 0 pos = -1 for i in range(n): if pos == -1: sub = 0 else: sub = cumul_sum[pos] if cumul_sum[i] - sub == total_sum / k: pos = i count += 1 elif cumul_sum[i] - cumul_sum[pos] > total_sum / k: break return count == k nums = [2, 5, 3, 4, 7] k = 3 print(solve(nums, k))
อินพุต
[2, 5, 3, 4, 7], 3
ผลลัพธ์
True
