โปรแกรมหาจำนวนสี่เหลี่ยมที่สามารถสร้างสี่เหลี่ยมจัตุรัสที่ใหญ่ที่สุดใน Python

สมมติว่าเรามีอาร์เรย์ที่เรียกว่า rect โดยที่ rect[i] มีสององค์ประกอบ [len_i, wid_i] โดยที่ len_i และ wid_i แทนความยาวและความกว้างของสี่เหลี่ยมผืนผ้า ith ตามลำดับ ตอนนี้ เราสามารถตัดสี่เหลี่ยม ith ให้เป็นสี่เหลี่ยมจัตุรัสที่มีความยาวด้านเป็น k ถ้าทั้ง k <=lenn_i และ k <=wid_i ตัวอย่างเช่น ถ้าเรามีสี่เหลี่ยม [4,6] เราก็สามารถตัดมันให้ได้สี่เหลี่ยมจัตุรัสที่มีความยาวด้านที่มากที่สุด 4 ทีนี้ ให้พิจารณาพารามิเตอร์ที่เรียกว่า maxLen คือความยาวด้านของสี่เหลี่ยมจัตุรัสที่ใหญ่ที่สุดที่เราหาได้ จากสี่เหลี่ยมใดๆ ที่กำหนด เราต้องหาจำนวนสี่เหลี่ยมที่เราสามารถสร้างสี่เหลี่ยมที่มีความยาวด้านเป็น maxLen ได้

ดังนั้น หากอินพุตเป็นเหมือน rect =[[6,9],[4,10],[6,13],[17,6]] ผลลัพธ์จะเป็น 3 เนื่องจากเราจะได้กำลังสองด้านที่ใหญ่ที่สุด [ 6, 4, 6, 6] จึงมีสี่เหลี่ยมสามอันที่ใหญ่ที่สุด

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

• m :=รายการใหม่

• สำหรับแต่ละ r ให้ทำ

  • ใส่ค่าต่ำสุดของ r ที่ส่วนท้ายของ m

• นับ (สูงสุด m) มีหน่วยเป็น m และส่งคืน

ตัวอย่าง (Python)

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

def solve(rect):
   m = []
   for r in rect:
      m.append(min(r))

   return m.count(max(m))

rect = [[6,9],[4,10],[6,13],[17,6]]
print(solve(rect))

อินพุต

[[6,9],[4,10],[6,13],[17,6]]

ผลลัพธ์

3