ลดองค์ประกอบเพื่อสร้างอาร์เรย์ซิกแซกใน Python

สมมติว่าเรามีจำนวนเต็มอาร์เรย์ การดำเนินการย้ายคือการเลือกองค์ประกอบใดๆ ก็ตามและลดลง 1 อาร์เรย์ A เป็นอาร์เรย์ซิกแซกหากพอใจกับ 1 หรือ 2 −

• องค์ประกอบที่จัดทำดัชนีคู่ทั้งหมดมีค่ามากกว่าองค์ประกอบที่อยู่ติดกัน ดังนั้น A[0]> A[1] A[3] ... และอื่นๆ

• องค์ประกอบดัชนีคี่ทุกตัวมีค่ามากกว่าองค์ประกอบที่อยู่ติดกัน ดังนั้น A[0] A[2] A[4] <... เป็นต้น

เราต้องหาจำนวนการเคลื่อนไหวขั้นต่ำเพื่อแปลงจำนวนอาร์เรย์ที่กำหนดให้เป็นอาร์เรย์ซิกแซก

ดังนั้นหากอาร์เรย์เป็นเหมือน [1,2,3] ผลลัพธ์จะเป็น 2 เนื่องจากเราสามารถลด 2 เป็น 0 หรือ 3 เป็น 1

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดวิธีการที่เรียกว่าแก้ปัญหา () ซึ่งจะใช้เวลา nums และเริ่มการทำงานดังต่อไปนี้ −

• k :=0

• สำหรับฉันอยู่ในช่วงเริ่มต้นถึงความยาวของ nums เพิ่มขึ้น 2

  • ซ้าย :=100000 เมื่อ i – 1 <0 มิฉะนั้น nums[i - 1]

  • right :=100000 เมื่อ i + 1>=ความยาวของ nums มิฉะนั้น nums[i + 1]

  • temp :=(ค่าต่ำสุดของซ้ายและขวา) – 1 – nums[i]

  • ถ้า temp <0 แล้ว k :=k + |temp|

• กลับ k

• โดยวิธีหลักก็จะเป็น

• ตอบ :=แก้ (nums, 0)

• ans :=ขั้นต่ำของ ans และแก้ (nums, 1)

• กลับมาอีกครั้ง

ตัวอย่าง(Python)

ให้เราดูการใช้งานต่อไปนี้เพื่อทำความเข้าใจ −

class Solution(object):
   def solve(self,nums,start):
      k = 0
      for i in range(start,len(nums),2):
         left = 100000 if i-1<0 else nums[i-1]
         right = 10000 if i+1>=len(nums) else nums[i+1]
         temp= (min(left,right)-1 - nums[i])
         if temp<0:
            k+=abs(temp)
      return k
   def movesToMakeZigzag(self, nums):
      ans = self.solve(nums,0)
      ans = min(ans,self.solve(nums,1))
      return ans
ob = Solution()
print(ob.movesToMakeZigzag([1,2,3]))

อินพุต

[1,2,3]

ผลลัพธ์

2