น้ำหนักหินก้อนสุดท้ายใน Python

สมมุติว่าเรามีหินอยู่บ้าง ก้อนหินแต่ละก้อนมีน้ำหนักเป็นจำนวนเต็มบวก ในแต่ละเทิร์น เราจะเอาหินที่หนักที่สุดสองก้อนมาทุบให้เข้ากัน พิจารณาว่าหินมีน้ำหนัก x และ y และ x <=y ผลลัพธ์ของการทุบนี้สามารถเป็นได้สองประเภท

• ถ้า x =y หินทั้งสองจะถูกทำลายโดยสิ้นเชิง
• มิฉะนั้นเมื่อ x !=y หินที่มีน้ำหนัก x จะถูกทำลายโดยสิ้นเชิง และหินที่มีน้ำหนัก y จะมีน้ำหนักใหม่ y-x

สุดท้ายเหลือหินอีกไม่เกิน 1 ก้อน เราต้องหาน้ำหนักของหินก้อนนี้ (0 เมื่อไม่มีหินเหลือ)

ดังนั้นถ้าน้ำหนักหินเป็น [2,7,4,1,8,1] ผลลัพธ์จะเป็น 1 ในตอนแรกเลือก 7 และ 8 แล้วได้ 1 ดังนั้นอาร์เรย์จะเป็น [2,4,1,1 ,1], ประการที่สอง เอา 2 และ 4 อาร์เรย์จะเป็น [2,1,1,1] หลังจากนั้นเลือก 2 และ 1 อาร์เรย์จะเป็น [1,1,1] จากนั้นเลือกหินสองก้อนที่มีน้ำหนัก 1 จากนั้นทั้งคู่จะถูกทำลาย ดังนั้นอาร์เรย์จะเป็น [1] นี่คือคำตอบ

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

• ถ้า stone Weight Array W ไม่มีองค์ประกอบ ให้คืนค่า 0
• หาก W มีองค์ประกอบเพียงตัวเดียว ให้คืนค่า W[0]
• ในขณะที่ W มีมากกว่าหนึ่งองค์ประกอบ −
  • เรียงลำดับ W
  • s1 :=องค์ประกอบสุดท้ายของ W, s2 :=องค์ประกอบสุดท้ายที่สองของ W
  • ถ้า s1 =s2 ให้ลบ s1 และ s2 ออกจาก W
  • มิฉะนั้น s1 :=|s1 – s2| ลบองค์ประกอบสุดท้ายออกจาก W จากนั้นตั้งค่า s1 เป็นองค์ประกอบสุดท้ายของ W
• ถ้า W มีองค์ประกอบเดียว ให้ส่งคืนองค์ประกอบนั้น ไม่เช่นนั้นให้คืนค่า 0

ตัวอย่าง

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

class Solution(object):
   def lastStoneWeight(self, stones):
      """
      :type stones: List[int]
      :rtype: int
      """
      if len(stones) ==0:
         return 0
      if len(stones) == 1:
         return 1
      while len(stones)>1:
         stones.sort()
         s1,s2=stones[-1],stones[-2]
         if s1==s2:
            stones.pop(-1)
            stones.pop(-1)
         else:
            s1 = abs(s1-s2)
            stones.pop(-1)
            stones[-1] = s1
      if len(stones):
         return stones[-1]
      return 0
ob1 = Solution()
print(ob1.lastStoneWeight([2,7,4,1,6,1]))

อินพุต

[2,7,4,1,6,1]

ผลลัพธ์

1