บทความนี้ส่วนใหญ่ศึกษาเนื้อหาที่เกี่ยวข้องกับ submatrix ที่ใหญ่ที่สุดในอาร์เรย์การเขียนโปรแกรม Java ตามรายละเอียดด้านล่าง
การพบปะกับคนดีสามารถเปลี่ยนชีวิตของคุณได้ พบกับหนังสือดีๆใช่มั้ย
เมื่อเร็ว ๆ นี้ฉันมีข้อมูลเชิงลึกมากมายเมื่อฉันอ่าน " โซลูชั่นที่ดีที่สุดสำหรับอัลกอริทึมและโครงสร้างข้อมูลของ Mr. Zuo Chengyun " ขอแนะนำให้บล็อกเกอร์ที่มีงานอดิเรกในพื้นที่นี้ก็ไปดู
อัลกอริทึมของเมทริกซ์ที่ใหญ่ที่สุดของอาร์เรย์ที่ใช้สแต็กอธิบายไว้ในหนังสือเล่มนี้คลาสสิกมาก แต่บล็อกเกอร์มีความสามารถที่ จำกัด และไม่สามารถเข้าใจสาระสำคัญของอัลกอริทึมได้อย่างละเอียด อย่างไรก็ตามจากความคิดนี้บล็อกเกอร์เกิดขึ้นกับอัลกอริทึมที่เรียบง่ายเพื่อจัดการกับปัญหาประเภทนี้ซึ่งสรุปได้ดังนี้
ความคิดหลัก
มาดูภาพก่อนแล้วเราจะเข้าใจได้อย่างคร่าวๆ
ดังที่แสดงในรูปแต่ละรอบคือการดำเนินการและแกนกลางของเราคือการดำเนินการภายในสำหรับแต่ละรอบ
คำนวณความยาวสูงสุดของแต่ละชั้นอย่างต่อเนื่องและต่อเนื่อง
กล่าวอีกนัยหนึ่งเราเป็นอาร์เรย์ที่สำคัญที่สุดในการคำนวณรอบด้านล่างถึงด้านบนและจากนั้นเราสามารถคำนวณพื้นที่ของ submatrix สูงสุดอย่างต่อเนื่องที่สามารถรับได้ในรอบนี้สำหรับแต่ละรอบ จากนั้นคุณจะต้องเปรียบเทียบข้อมูลที่ใหญ่ที่สุดสำหรับแต่ละรอบและกลับไปหาพื้นที่ของเรือย่อยต่อเนื่องที่ใหญ่ที่สุดของอาร์เรย์
รหัส
โอเคด้วยแนวคิดหลักข้างต้นที่วางไว้เราสามารถเริ่มเขียนโค้ดได้ (แม้ว่าฉันจะไม่คิดว่าฉันพูดอย่างชัดเจน แต่โปรดยกโทษให้ฉัน)
แพ็คเกจ stack_and_queue;/*** @author guo pu <br>* คำนวณพื้นที่ของพื้นที่สี่เหลี่ยมต่อเนื่องที่ใหญ่ที่สุดตามอาร์เรย์*/คลาสสาธารณะ maxrectangle {โมฆะคงที่สาธารณะหลัก (สตริง [] args) {integer [] arr = {2, 1, 3, 7, 7, 6, 4 maxrectangleaa (arr); system.out.println ("พื้นที่ของพื้นที่สี่เหลี่ยมต่อเนื่องที่ใหญ่ที่สุดในอาร์เรย์คือ:" + maxrectangle);}/*** @param arr* @return พื้นที่สูงสุดของพื้นที่สี่เหลี่ยมผืนผ้าอย่างต่อเนื่อง int [arr.length]; // คำนวณอาร์เรย์โดยการสำรวจความยาวอย่างต่อเนื่องจากด้านล่างไปด้านบนสำหรับ (int i = 1; i <= arr.length; i ++) {// ค่าชั่วคราวของความยาวอย่างต่อเนื่องที่สะสมในรอบปัจจุบัน การเริ่มต้นจากตัวห้อยเลเยอร์แรกจะทำให้การสูญเสียส่วนก่อนหน้าของข้อมูลสำหรับ (int j = 1; j <= arr.length; j ++) {ถ้า (arr [j - 1]> = i) {templen+= 1; templen_max = templen; + i + "ความยาวต่อเนื่องและความยาวสูงสุดของเลเยอร์คือ:" + templen_max);} // ค้นหาตัวเลขที่มีค่าตัวเลขที่ใหญ่ที่สุดในอาร์เรย์ชุดผลลัพธ์นั่นคือพื้นที่ของโดเมนที่ใหญ่ที่สุดในพื้นที่ Maxarea: ผลลัพธ์ [i];} // ส่งคืนพื้นที่ของสนามสี่เหลี่ยมต่อเนื่องสูงสุดที่ได้รับจากการส่งคืน maxarea;}}}ความคิดเห็นในรหัสนั้นค่อนข้างครอบคลุมดังนั้นฉันจะไม่เข้าไปดูรายละเอียดมากเกินไป
ทดสอบ
ต่อไปนี้คือการทดสอบอาร์เรย์ ก่อนอื่นให้ทดสอบกับอาร์เรย์ที่แสดงในรูปภาพที่จุดเริ่มต้นของบทความนี้
จำนวนเต็ม [] arr = {2,1,3,5,7,6,4} ・・・・พื้นที่ของพื้นที่สี่เหลี่ยมต่อเนื่องที่ใหญ่ที่สุดในอาร์เรย์คือ: 16
จากนั้นเราแก้ไขค่าขององค์ประกอบในอาร์เรย์เพื่อทดสอบเพิ่มเติมเพื่อดูว่าผลลัพธ์ถูกต้องหรือไม่
จำนวนเต็ม [] arr = {2,1,3,1,7,6,6,4} ・・・・พื้นที่ของพื้นที่สี่เหลี่ยมต่อเนื่องที่ใหญ่ที่สุดในอาร์เรย์คือ: 12
หลังจากบล็อกเกอร์ทดสอบตัวเองอัลกอริทึมจะทำงานได้ตามปกติ -
ส่วนเพิ่มประสิทธิภาพ
การพูดถึงส่วนการเพิ่มประสิทธิภาพสิ่งแรกที่เราเห็นคือการค้นหาค่าสูงสุดในอาร์เรย์ชุดผลลัพธ์ในขั้นตอนสุดท้าย
อันที่จริงเราสามารถใช้ตัวแปรอื่นเพื่อบันทึกพื้นที่ของ submatrix ที่ใหญ่ที่สุดของรอบจนถึงตอนนี้ อย่างไรก็ตามการเพิ่มประสิทธิภาพนี้ไม่ได้มีบทบาทสำคัญและไม่มีการปรับปรุงอย่างมีนัยสำคัญในความซับซ้อนของเวลา
อีกประเด็นหนึ่งฉันคิดว่าจุดเริ่มต้นที่ดีกว่าคือการเพิ่มการตัดสินเมื่อทำการคำนวณสำหรับแต่ละรอบเพื่อตัดสินใจว่าจะหมุนเวียนลงก่อนรอบปัจจุบันหรือไม่ หากองค์ประกอบในอาเรย์ผันผวนอย่างมากระดับการเพิ่มประสิทธิภาพยังคงดีมาก
สรุป
อัลกอริทึมขนาดเล็กนี้มีความงดงามมากกว่าและสิ่งเดียวที่มีข้อบกพร่องมากขึ้นคือความซับซ้อนของเวลานั้นรุนแรงขึ้นเล็กน้อย หากผู้อ่านกำลังมองหาอัลกอริทึมที่มีความซับซ้อนค่อนข้างต่ำโปรดใช้ทางอ้อม
มันค่อนข้างดีถ้าคุณแค่ต้องการค้นหาผลลัพธ์ อย่างน้อยก็มีประสิทธิภาพมากกว่าวิธีการคำนวณที่รุนแรง
ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้เกี่ยวกับวิธีการแก้ปัญหาง่าย ๆ สำหรับ submatrix สูงสุดในอาร์เรย์การเขียนโปรแกรม Java ฉันหวังว่ามันจะเป็นประโยชน์กับทุกคน เพื่อนที่สนใจสามารถอ้างถึงหัวข้ออื่น ๆ ที่เกี่ยวข้องในเว็บไซต์นี้ต่อไป หากมีข้อบกพร่องใด ๆ โปรดฝากข้อความไว้เพื่อชี้ให้เห็น ขอบคุณเพื่อนที่ให้การสนับสนุนเว็บไซต์นี้!