โซลูชั่น LeetCode ในรูปแบบที่ดี

เอกสารนี้ให้ภาพรวมที่ครอบคลุมของ LeetCode-Solutions-in-Good-Style ซึ่งเป็นแหล่งข้อมูลที่นำเสนอบทช่วยสอนที่เป็นมิตรต่อผู้เริ่มต้นและโซลูชันวิดีโอสำหรับปัญหาอัลกอริทึมและโครงสร้างข้อมูล โดยนำเสนอแนวทางที่มีโครงสร้างพร้อมโค้ดที่ชัดเจน คำอธิบายโดยละเอียด และมุ่งเน้นไปที่การสร้าง มีความเข้าใจแนวคิดพื้นฐานมากกว่าการเขียนโค้ดเพื่อการแข่งขัน

LeetCode-โซลูชั่นในรูปแบบที่ดี

คำอธิบาย: เช่นเดียวกับเพื่อนร่วมชั้นส่วนใหญ่ ฉันศึกษาและสรุปไปพร้อมๆ กัน ฉันจะพยายามแบ่งปันมากขึ้นและนำความรู้ที่เป็นประโยชน์มาให้คุณ ขอขอบคุณสำหรับการสนับสนุนอย่างต่อเนื่อง

สวัสดีทุกคน นี่เป็นบทเรียนระดับเริ่มต้นเกี่ยวกับ "อัลกอริทึมและโครงสร้างข้อมูล" เหมาะสำหรับนักเรียนที่ไม่มีพื้นฐานด้านอัลกอริทึมและนักเรียนที่เปลี่ยนอาชีพ ไม่เหมาะสำหรับการเตรียมตัวสำหรับการแข่งขันอัลกอริทึม ประเด็นที่ผมอยากสื่อคือ เขียนโค้ดด้วยตรรกะที่ชัดเจน ดังนั้นโค้ดที่ผมเขียนจะต้องผ่านการคิดอย่างเข้มงวด รูปแบบที่ได้มาตรฐานมาก ไม่มีสไตล์ส่วนตัว และฉันจะไม่เขียนบรรทัดว่างหรือแสดงความคิดเห็นเพื่อลดขนาดลง จำนวนบรรทัดของโค้ด นี่คือ:

คุณสามารถเรียกฉันว่า weiwei ได้ ฉันจะพยายามตอบคำถามที่ฉันรู้ภายในความสามารถและเวลาที่อนุญาต หากคุณมีคำถามใด ๆ ที่ไม่สามารถตอบได้ทันอาจเป็นเพราะฉันไม่เห็นการแจ้งเตือนบนเว็บไซต์ คุณสามารถส่งอีเมลถึงฉันได้ที่ [email protected]

โซลูชันวิดีโอที่ฉันบันทึกไว้

ฉันเริ่มบันทึกวิดีโอโซลูชันในเดือนกันยายน 2019 ในตอนแรก ฉันจะบันทึกเนื้อหาที่ฉันต้องการพูดถึงหลายครั้ง ตอนนี้ให้เขียนแบบร่างคำต่อคำเมื่ออธิบายประเด็นความรู้ มีวิดีโอมากมายที่ได้รับการสะสมไว้ ซึ่งเป็นหลักสูตรเล็กๆ น้อยๆ ที่เป็นระบบ ตอนนี้วิดีโอเหล่านั้นได้รวบรวมไว้ที่นี่แล้ว ฉันหวังว่าจะเป็นประโยชน์กับทุกคน

0. ผู้ใช้อัลกอริทึมมือใหม่สามารถใช้ LeetCode ได้อย่างไร? 【แบ่งปันข้อมูลที่เป็นประโยชน์】

1. ความซับซ้อนของเวลาและความซับซ้อนของพื้นที่

วิดีโอนี้กล่าวถึงความซับซ้อนของเวลาเป็นแนวคิดเชิงเส้นกำกับ และจำเป็นต้องเข้าใจจากมุมมองแบบไดนามิก และมีการอธิบายคำจำกัดความที่เข้มงวด (รูปแบบจำกัด) ของความซับซ้อนของเวลา เพื่อให้ทุกคนสามารถเข้าใจกฎการคำนวณของความซับซ้อนของเวลาได้ นอกจากนี้ยังชี้ให้เห็นว่า: ความซับซ้อนของเวลาไม่ใช่เวลาทำงานของโปรแกรม ควรใช้ "พื้นที่สำหรับเวลา" และควรให้ความสนใจมากขึ้นในการปรับ "ความซับซ้อนของเวลา" ให้เหมาะสม

2. การค้นหาแบบไบนารี

วิดีโอนี้แนะนำวิธีเขียนอัลกอริทึมการค้นหาแบบไบนารี แม้ว่าจะมีรายละเอียดมากมายเกี่ยวกับการค้นหาแบบไบนารี ตราบใดที่เราเชี่ยวชาญแนวคิดในการแก้ปัญหาที่ถูกต้อง ฝึกฝนมากขึ้น คิดอย่างขยันขันแข็ง และสรุปมากขึ้น ปัญหาของการค้นหาแบบไบนารีจะไม่เกิดขึ้น ลำบากอีกต่อไป.

วิดีโอต่อไปนี้จะอธิบายคำถามตัวอย่างต่างๆ ของการค้นหาแบบไบนารี เรามุ่งเน้นที่การวิเคราะห์ความหมายของคำถามและวิธีใช้เงื่อนไขที่กำหนดในคำถามเพื่อค่อยๆ จำกัดขอบเขตการค้นหาให้แคบลง

จากการวิเคราะห์คำถามที่ 4 ของ "Likou" (การหาค่ามัธยฐานของอาร์เรย์ลำดับที่เป็นบวกสองตัว) เราได้แนะนำเทคนิคนี้แก่คุณ: หากคุณสมบัติขององค์ประกอบเป้าหมายที่คุณกำลังมองหาซับซ้อนมากขึ้น คุณสามารถกลับคุณสมบัตินี้ได้ แล้วเขียนข้อความเชิงตรรกะที่สามารถลดช่วงปัญหาได้อย่างง่ายดาย

3.ประเด็นที่เกี่ยวข้องกับการเรียงลำดับ

"การเรียงลำดับแบบผสาน" และ "การเรียงลำดับแบบด่วน" เป็นอัลกอริธึมการเรียงลำดับที่สำคัญมาก ความเข้าใจอย่างลึกซึ้งเกี่ยวกับสิ่งเหล่านี้มีประโยชน์มากในการทำความเข้าใจกลไกการทำงานของฟังก์ชัน "แบบเรียกซ้ำ" ในเวลาเดียวกัน สิ่งเหล่านี้ยังเป็นแอปพลิเคชันทั่วไปของการ "แบ่งและพิชิตการคิด" ". "คู่ลำดับย้อนกลับ" และ "ปัญหาธงดัตช์ (การจำแนกสี)" ก็เป็นปัญหาอัลกอริทึมแบบคลาสสิกเช่นกัน

การคำนวณ "คู่ลำดับย้อนกลับ" ขึ้นอยู่กับแนวคิดของ "การเรียงลำดับแบบผสาน" ทั้งหมด

ในการอธิบายปัญหา "การจำแนกสี" เราได้แนะนำ "ค่าคงที่ของลูป" ให้กับทุกคน ในกระบวนการเขียนโค้ด เราควรปฏิบัติตามความหมายของตัวแปรที่ใช้เสมอ "ก่อนการทำงานของโปรแกรม" และ "ระหว่างการดำเนินการ" ยังคงไม่เปลี่ยนแปลงหลังจาก "การดำเนินการสิ้นสุดลง" การปฏิบัติตามคำจำกัดความของเราเองว่า "ค่าคงที่ของลูป" เป็นวิธีสำคัญสำหรับเราในการเขียนโค้ดที่ถูกต้อง

"จำนวนบวกแรกที่หายไป" เป็นปัญหาอัลกอริทึมแบบคลาสสิก แนวคิดที่ใช้คือ "การแฮชแบบแทนที่" ซึ่งสามารถเข้าใจได้ว่าเป็นแอปพลิเคชันพิเศษของอัลกอริทึม "การเรียงลำดับถัง": หนึ่งแครอท หนึ่งหลุม และหนึ่งถัง เก็บองค์ประกอบ ฉันต้องการเน้นว่าความจริงที่ว่าคุณสามารถทำได้มีความเกี่ยวข้องอย่างใกล้ชิดกับค่าขององค์ประกอบของอาร์เรย์อินพุต

4. หน้าต่างบานเลื่อน

ปัญหา "หน้าต่างบานเลื่อน" เป็นปัญหาทั่วไปที่แก้ไขได้โดยใช้ "ค่าคงที่ของลูป" ซึ่งจะทดสอบความสามารถในการเขียนโค้ดและแก้ไขจุดบกพร่องของเรา

5. ปัญหาที่เกี่ยวข้องกับกองซ้อน

ปัญหาที่แก้ไขได้โดยใช้ "สแต็ค" ทำให้เราต้องใช้ตัวอย่างที่เฉพาะเจาะจงเพื่อค้นหาว่าการแก้ปัญหานั้นเกิดขึ้นพร้อมกับกฎ "เข้าก่อน ออกก่อน":

การเรียนรู้คำถามสองข้อต่อไปนี้จะแยกจากการศึกษาตัวอย่างที่เฉพาะเจาะจงแล้วสรุปกฎทั่วไปไม่ได้

หนึ่งในแอปพลิเคชัน "สแต็ก" ที่ใช้กันอย่างแพร่หลายที่สุดคือการสนับสนุนโครงสร้างข้อมูลสำหรับ "การเรียกซ้ำ" "การสำรวจเชิงลึกก่อน" และ "อัลกอริธึมการแบ่งและพิชิต"

6. การค้นหาแบบรวม

ปัจจุบันโครงสร้างข้อมูล "Union Search Set" ไม่ค่อยถูกใช้ในการสัมภาษณ์ หากคุณกำลังเตรียมตัวสำหรับการสัมภาษณ์อัลกอริทึม คุณสามารถข้ามไปได้

7. ต้นไม้

ปัญหาต้นไม้จำนวนมากสามารถแก้ไขได้โดยใช้ "การแวะผ่านเชิงลึกก่อน" หรือ "การแวะผ่านทางกว้างก่อน"

8. อัลกอริธึมการย้อนรอย

"อัลกอริธึมการย้อนรอย" จริงๆ แล้วเป็นการสำรวจเชิงลึกของ "โครงสร้างต้นไม้" ที่มีอยู่ในคำถาม เมื่อแก้ไขปัญหาประเภทนี้ สิ่งสำคัญคือต้องวาดแผนภาพโครงสร้างต้นไม้บนกระดาษขูด

9. การเขียนโปรแกรมแบบไดนามิก

10. การสำรวจเส้นทางแบบกว้างก่อนและการเรียงลำดับทอพอโลยี

11. ตารางแฮช

12. การดำเนินการบิตที่เกี่ยวข้อง

เว็บไซต์ส่วนตัวและบันทึกการศึกษาอัลกอริทึมของฉัน

กลุ่ม WeChat และกลุ่ม QQ

หากคุณต้องการเพื่อนที่จะตอบคำถามด้วยกัน คุณสามารถเข้าร่วมกลุ่ม WeChat และกลุ่ม QQ ได้

MyLeetBook

นี่คือโปรโมชั่นสำหรับตัวเอง เมื่อเร็วๆ นี้ผมได้เปิดตัว LeetBook ของตัวเองใน "LeetBook": Learning Algorithms from Zero (เดิมชื่อ "Learning Algorithms and Data Structures with "LeetCoin")" ซึ่งเน้นสำหรับเพื่อนๆ ที่เปลี่ยนอาชีพและมี รากฐานเป็นศูนย์ อธิบายความรู้พื้นฐานของอัลกอริทึมและโครงสร้างข้อมูล

แสดงให้เห็น:

สองบทแรกของ LeetBook (ความซับซ้อนของเวลา, การค้นหาแบบไบนารี) สามารถอ่านได้ฟรี บทต่อไปนี้ต้องชำระเงินเพื่ออ่าน ราคาที่ไม่ใช่สมาชิกคือ 99 หยวน และราคาสมาชิกคือ 69 หยวน เช่นเดียวกับ LeetBook เท่านั้น ส่วนเสริมไม่น้อย

ชื่อหลักสูตร ตัวอย่าง แบบฝึกหัด และที่เก็บโค้ดสนับสนุนของ LeetBook (ที่เก็บที่คุณกำลังดูอยู่) นั้นเป็นแบบสาธารณะโดยสมบูรณ์ หากคุณเชี่ยวชาญเนื้อหา (รวมถึงแบบฝึกหัด) ที่ออกแบบใน LeetBook แล้ว ไม่แนะนำให้ซื้อ

พลังงานที่ลงทุนไปก็เหมือนกับการเขียน Solution ปกติ ยกเว้น LeetBook จะมีรายละเอียดในการทำ Chart มากกว่า เนื้อหาที่ต้องชำระเงินคือ เวลาและพลังงานที่ใช้ในการทำแบบฝึกหัด และการมีส่วนร่วมของพนักงานและผู้เชี่ยวชาญ "Likou" ในการผลิตและการทบทวน ประสบการณ์การอ่านจะดีขึ้น ไม่มีการปฏิเสธว่าฉันมักจะเขียนคะแนนความรู้ในการแก้ปัญหามากกว่า LeetBook

ผู้ใช้ระดับกลางและขั้นสูงโปรดซื้อด้วยความระมัดระวัง

คุณสามารถปรึกษาฉันเกี่ยวกับเนื้อหาหลักสูตรบนเว็บไซต์ "Likou" หรือบัญชีโซเชียลอื่น ๆ ของฉัน หรือคุณสามารถส่งปัญหาไปที่คลังสินค้านี้ได้ ไม่ว่าฉันจะซื้อหลักสูตรหรือไม่ก็ตาม ฉันจะพยายามตอบคำถามที่ฉันรู้ให้ดีที่สุด (ตามเวลาที่เอื้ออำนวยและอยู่ในความสามารถของฉัน) ขอขอบคุณทุกท่านที่ให้การสนับสนุนฉันอย่างต่อเนื่อง ยินดีต้อนรับทุกคนเพื่อสื่อสารกับฉันหากคุณมีข้อเสนอแนะและความคิดเห็น

ความรู้ที่ฉันอธิบายอยู่ในหนังสือที่ฉันแนะนำให้ทุกคน บล็อก วิธีแก้ไขปัญหา และบันทึกที่ฉันเขียน วิธีการแก้ไขปัญหา บล็อก และบันทึกที่เผยแพร่จะถูกแบ่งปันเสมอ และตราบใดที่ฉันมีเวลาและกำลัง ฉันจะทำเช่นนั้นต่อไป แบ่งปันและถาม & ตอบ;

ฉันรู้สึกขอบคุณ "หลี่โข่ว" มากที่ให้โอกาสฉันได้เรียนหลักสูตรและช่วยฉันเติมเต็มความปรารถนาเล็กๆ น้อยๆ

ไดเรกทอรีการจำแนกประเภทและการแก้ปัญหา "Lekou" (จัดเรียงตามบท LeetBook บทที่ 16 ขึ้นไปเป็นบทที่ปัจจุบันไม่รวมอยู่ใน LeetBook)

หมายเหตุ: หมวดหมู่คำถามสอดคล้องกับบท LeetBook ของฉัน

บทที่ 1 ความซับซ้อนของเวลา

ส่วนนี้แนะนำแนวคิดเรื่องความซับซ้อนของเวลา คุณสามารถรับชม [คำอธิบายวิดีโอ] ซึ่งไม่มีค่าใช้จ่ายใด ๆ ทั้งสิ้น ไม่มีแบบฝึกหัดสำหรับบทนี้

บทที่ 2 การค้นหาแบบไบนารี

คำถามประเภทที่ 1: ค้นหาตัวห้อยในสองจุด

แสดงให้เห็น:

ฝึกฝน:

คำถามประเภทที่ 2: กำหนดจำนวนเต็มที่มีช่วงสองจุด (ตอบสองจุด)

การคิดอัลกอริทึม: ลดและพิชิต หากคำถามต้องการให้เราค้นหาจำนวนเต็ม และจำนวนเต็มนี้มีช่วงที่แน่นอน เราสามารถค่อยๆ จำกัดช่วงให้แคบลงด้วยการค้นหาแบบไบนารี่ และสุดท้ายเข้าใกล้เป็นตัวเลข

คำถามประเภทที่ 3: ฟังก์ชันจำแนกเชิงซ้อน (ปัญหาการขยายใหญ่สุด)

หมายเหตุ: คำถามประเภทนี้โดยพื้นฐานแล้วคือ "คำถามประเภท 2" (คำตอบสองประเด็น) แต่อาจรู้สึกสับสนเล็กน้อยเมื่อคุณเรียนรู้ครั้งแรก คำถามประเภทนี้จะถูกถามในลักษณะเดียวกัน คำสำคัญคือ "ต่อเนื่อง" และ "จำนวนเต็มบวก" โปรดใส่ใจในการรวบรวมข้อมูลสำคัญดังกล่าวในคำถาม

บทที่ 3 อัลกอริธึมการเรียงลำดับพื้นฐาน

ส่วนนี้ประกอบด้วยอัลกอริธึมการเรียงลำดับพื้นฐานสี่แบบ ได้แก่ การเรียงลำดับการเลือก การเรียงลำดับการแทรก การเรียงลำดับแบบ Hill และการเรียงลำดับแบบฟอง

คำถาม "Likou" 912: วิธีแก้ปัญหาการเรียงลำดับ: นี่เป็นการสรุปประเด็นสำคัญและสื่อการเรียนรู้สำหรับการเรียงลำดับปัญหา คุณสามารถเริ่มเรียนรู้อัลกอริทึมจากการเรียงลำดับปัญหา

ปัญหาเกี่ยวกับอาร์เรย์สามารถใช้เป็น "ฟิลด์ของมือใหม่" ในอัลกอริทึมได้ เนื่องจากปัญหาเหล่านี้สามารถดำเนินการให้เสร็จสิ้นได้โดยการเรียนรู้ความรู้พื้นฐานของภาษาการเขียนโปรแกรมเท่านั้น เป็นเรื่องง่ายที่จะคิดวิธีแก้ไขปัญหาต่อไปนี้ แม้ว่าคุณจะไม่ได้เรียนรู้ความรู้เกี่ยวกับโครงสร้างข้อมูลและอัลกอริทึมที่เกี่ยวข้องก็ตาม

ประเด็นความรู้: ค่าคงที่ของลูป

บทที่ 4 อัลกอริทึมการเรียงลำดับขั้นสูง (สำคัญ)

ส่วนนี้ต้องมุ่งเน้นไปที่การเรียนรู้อัลกอริธึมการเรียงลำดับขั้นสูงสามแบบ ได้แก่ การเรียงลำดับแบบผสาน การเรียงลำดับแบบด่วน และการเรียงลำดับแบบฮีป

แสดงให้เห็น:

บทที่ 5 การเรียงลำดับแบบไม่เปรียบเทียบ (ไม่บังคับ)

ส่วนนี้ประกอบด้วยการเรียงลำดับแบบไม่เปรียบเทียบสามประเภท: การเรียงลำดับการนับ การเรียงลำดับ Radix และการเรียงลำดับบัคเก็ต การแก้ปัญหาเหล่านี้จำเป็นต้องเข้าใจแนวคิดของการแฮชแบบแทนที่

บทที่ 6 หน้าต่างบานเลื่อนและพอยน์เตอร์คู่

1.หน้าต่างบานเลื่อน

วิธีการเขียนอ้างอิงของหน้าต่างบานเลื่อน (ไม่ใช่เทมเพลต โปรดอย่าคัดลอกตามที่เป็นอยู่ มีไว้สำหรับการอ้างอิงเท่านั้น สิ่งสำคัญคือต้องเข้าใจแนวคิดการออกแบบอัลกอริทึม):

คำเตือนที่เป็นมิตร: คำถามที่ 3 และ 76 เป็นคำถามพื้นฐานที่คุณต้องทำได้ เมื่อคุณเข้าใจคำถามข้างต้นอย่างถ่องแท้แล้ว คุณก็สามารถตอบคำถามต่อไปนี้ได้ง่ายขึ้น

คำถามสำคัญ:

แสดงให้เห็น:

ฝึกฝน:

แสดงให้เห็น:

คำถาม 209: ข้อมูลสำคัญที่ให้ไว้ในคำถาม: องค์ประกอบทั้งหมดในอาร์เรย์เป็นจำนวนเต็มบวก มีทั้งหมด 3 วิธี ดังนี้

วิธีที่ 1: วิธีแก้ปัญหาที่รุนแรง

วิธีที่ 2: หน้าต่างบานเลื่อน (วิเคราะห์สาเหตุที่สามารถใช้หน้าต่างบานเลื่อนได้)

วิธีที่ 3: สร้างคำนำหน้าและอาร์เรย์ และจากนั้น ใช้การค้นหาแบบไบนารี

คำถาม 438: เช่นเดียวกับคำถาม 76;

คำถาม 567: เช่นเดียวกับคำถาม 76 ยกเว้นว่าการรวบรวมประโยคที่มีคุณสมบัติจะแตกต่างกัน

2. พอยน์เตอร์คู่

ปัญหา "ตัวชี้คู่" จริงๆ แล้วเป็นการเพิ่มประสิทธิภาพของอัลกอริทึมไร้เดียงสา ยังคงมีความสำคัญมากกว่าในการวิเคราะห์ว่าเหตุใดจึงสามารถใช้พอยน์เตอร์คู่ได้

อัลกอริธึมการค้นหาแบบไบนารี่ที่ใช้ค้นหาตัวห้อยก็ถือเป็นโซลูชันตัวชี้คู่ได้เช่นกัน

บทที่ 7 รายการที่เชื่อมโยง

เทคนิคที่ใช้งานได้จริงในการแก้ปัญหาลิงค์ลิสต์คือ "การวาด" เช่นเดียวกับการวิเคราะห์และการอธิบายปัญหาอัลกอริทึมอื่นๆ (อธิบายให้ผู้สัมภาษณ์ฟัง)

คุณสามารถเขียนฟังก์ชันทดสอบสำหรับรายการที่เชื่อมโยงเพื่ออำนวยความสะดวกในการดีบัก วิธีการนำไปใช้ที่แนะนำคือ: 1 สร้างรายการเชื่อมโยงเดี่ยวผ่านอาร์เรย์ 2 พิมพ์โหนดปัจจุบันและโหนดที่ตามมาตามโหนดปัจจุบัน ทั้งสองวิธีนี้สามารถช่วยเราดีบักโปรแกรมที่เกี่ยวข้องกับรายการที่เชื่อมโยงได้อย่างสะดวกมาก

คำถามประเภทที่ 1: ปัญหาการชี้รายการลิงค์พื้นฐาน

หมายเหตุ: ปัญหาบางอย่างจำเป็นต้องใช้ "โหนดส่วนหัวเสมือน" เพื่อหลีกเลี่ยงตรรกะการอภิปรายการจำแนกประเภทที่ซับซ้อนสำหรับโหนดแรกของรายการที่เชื่อมโยง เราได้เห็นแนวคิดนี้ในอาร์เรย์ที่เรียกว่า "ยามรักษาการณ์"

ใช้ฟังก์ชันแบบเรียกซ้ำเพื่อหลีกเลี่ยงการดำเนินการที่ซับซ้อนในการเปลี่ยนตัวแปรตัวชี้ ทำให้การแก้ปัญหาเป็นเรื่องง่าย

แสดงให้เห็น:

คำถามประเภทที่ 2: ทักษะตัวชี้เร็วและช้า

ถ้าให้เจาะจงกว่านี้ เรียกว่า "ตัวชี้แบบซิงโครไนซ์" จะดีกว่า

การใช้ตัวแปรพอยน์เตอร์สองตัวจะอยู่ที่โหนดแรกของรายการที่เชื่อมโยงที่จุดเริ่มต้น ตัวแปรหนึ่งจะใช้เวลาครั้งละหนึ่งก้าวเท่านั้น และอีกตัวแปรหนึ่งจะใช้เวลาเพียงครั้งละสองขั้นตอนเท่านั้น ตัวแรกอยู่ข้างหน้าและอีกตัวอยู่ใน กลับในเวลาเดียวกัน ด้วยวิธีนี้ เมื่อตัวชี้แบบเร็วเดินเสร็จ ตัวชี้แบบช้าจะไปถึงตำแหน่งตรงกลางของรายการที่เชื่อมโยง

คุณลักษณะทั่วไปในการแก้ปัญหาเหล่านี้คือการใช้ตัวแปรตัวชี้สองตัวเพื่อเคลื่อนที่พร้อมกัน พอยน์เตอร์ที่เร็วและช้าจะเคลื่อนที่ไปในทิศทางเดียวกัน และ "ความแตกต่าง" ระหว่างขั้นตอนต่างๆ จะคงที่ ขึ้นอยู่กับความมั่นใจนี้ ปัญหาบางอย่างในรายการที่เชื่อมโยงสามารถแก้ไขได้ การใช้แนวคิดนี้ยังสามารถแก้ไขปัญหาต่อไปนี้ของรายการที่เชื่อมโยงได้:

แสดงให้เห็น:

คำถามประเภทที่สาม: การออกแบบโครงสร้างข้อมูล

บทที่ 8 กองและคิว

1. สแต็ค

คำถามประเภทที่ 1: ปัญหาพื้นฐานแก้ไขได้โดยใช้สแต็ก

คำถามต่อไปนี้เป็นคำถามพื้นฐานมากและต้องเข้าใจให้เชี่ยวชาญ:

ฝึกฝน:

คำถามประเภทที่ 2: กองเสียงเดียว

สแต็กแบบโมโนโทนิกคือสแต็กธรรมดาซึ่งเกิดขึ้นเพื่อให้เป็นไปตามหลักการ "เข้าก่อนออกก่อน" ในระหว่างการใช้งาน และองค์ประกอบในสแต็กเป็นแบบโมโนโทนิก ปัญหาของ "คิวเสียงเดียว" และ "คิวเสียงเดียว" มักจะพิเศษมาก เพียงแค่ฝึกฝนตัวอย่างและแบบฝึกหัดบางส่วนให้เชี่ยวชาญ

ประสบการณ์: โดยทั่วไปตัวห้อยจะถูกจัดเก็บไว้ในสแต็กแบบโมโนโทนิก

แสดงให้เห็น:

ฝึกฝน:

2. คิว

คำถามประเภทที่ 1: ปัญหาพื้นฐานแก้ไขได้โดยใช้คิว

ปัญหาทั้งหมดได้รับการแก้ไขโดยใช้คิวการใช้การแวะผ่านแบบกว้างก่อน

คำถามประเภทที่ 2: คิวเสียงเดียว

คิวแบบโมโนโทนิคเป็นเพียงคิวธรรมดา ขณะนี้ปัญหานี้พบในคิวแบบโมโนโทนิกบน "Likou" สิ่งสำคัญคือต้องวิเคราะห์ให้ชัดเจนว่าเหตุใดอัลกอริทึมที่ออกแบบไว้จึงทำให้คิวเป็นแบบโมโนโทนิก นอกจากนี้ยังมีตัวอย่างการใช้คิวแบบโมโนโทนิคเพื่อเพิ่มประสิทธิภาพใน "ปัญหากระเป๋าเป้สะพายหลัง" อีกด้วย เพื่อนๆ ที่สนใจสามารถเรียนรู้เกี่ยวกับเรื่องนี้ซึ่งเป็นความรู้ด้านการแข่งขัน

ประสบการณ์: โดยทั่วไปตัวห้อยจะถูกจัดเก็บไว้ในคิวแบบโมโนโทนิก

บทที่ 9 คิวลำดับความสำคัญ

หมายเหตุ: จำเป็นต้องเข้าใจการใช้งาน "ฮีป" เป็น "คิวลำดับความสำคัญ" ซึ่งจะช่วยให้เข้าใจรายละเอียดการเข้ารหัสของการลบ () และแทนที่ () เพื่อที่คุณจะได้มีประสิทธิภาพมากขึ้นเมื่อใช้ฮีป

แอปพลิเคชัน: เลือกองค์ประกอบที่มีลำดับความสำคัญสูงสุดในคิวปัจจุบันแบบไดนามิก โดยมุ่งเน้นที่การทำความเข้าใจความหมายของ "ไดนามิก"

บทที่ 10: การค้นหาแบบรวม

และตรวจสอบ [คำอธิบายวิดีโอ] ของประเด็นความรู้ในโซลูชันวิดีโอของคำถาม 990 คำถามพื้นฐานและคำถามทั่วไป ได้แก่:

คำถามเพิ่มเติม:

บทที่ 11 ต้นไม้ (ต้นไม้ไบนารีและต้นไม้ค้นหาไบนารี)

บทที่ 12 อัลกอริธึมการย้อนรอย

คำถามประเภทที่ 1: ปัญหาการย้อนรอยขั้นพื้นฐาน

จากคำถามเหล่านี้ คุณสามารถเข้าใจแนวคิดของอัลกอริทึมการย้อนรอยได้ จุดความรู้ของอัลกอริธึมการย้อนรอยมีการอธิบายไว้ในโซลูชันวิดีโอและโซลูชันข้อความของคำถามที่ 46 ของ "Likou"

การย้อนรอยคือการใช้การสำรวจเชิงลึกก่อนเพื่อค้นหาคำตอบทั้งหมดของแผนภูมิต้นไม้ (กราฟ) การสำรวจเชิงลึกก่อนมีโครงสร้างแบบเรียกซ้ำที่ชัดเจน

เคล็ดลับสำหรับการแก้ปัญหาต่อไปนี้: 1 วาด วาด วาด 2 ทำความเข้าใจกับการสำรวจเชิงลึกและการเรียกซ้ำ 3 ดีบั๊กมากขึ้น ดีบั๊กมากขึ้น

คำถามประเภทที่ 2: ปัญหาการย้อนรอยบนสตริง

ประเด็นสำคัญที่ต้องทำความเข้าใจ: เนื่องจากสตริงสร้างอักขระใหม่ทุกครั้ง จึงไม่จำเป็นต้องรีเซ็ตสถานะ

คำถามประเภทที่สาม: การเติมน้ำท่วม

คำถามประเภทที่ 4: คำถามบางเกม

แสดงให้เห็น:

บทที่ 13 การเขียนโปรแกรมแบบไดนามิก (ตอนที่ 1)

แนวคิดที่สำคัญสองประการของการเขียนโปรแกรมแบบไดนามิก:

การคิดสองทิศทางในการเขียนโปรแกรมแบบไดนามิก:

ต้องปฏิบัติตามเงื่อนไขสามประการเพื่อแก้ไขปัญหาโดยใช้การเขียนโปรแกรมแบบไดนามิก:

แนวคิดที่สำคัญสองประการของการเขียนโปรแกรมแบบไดนามิก:

การอ้างอิงการจำแนกประเภทคำถาม:

หมายเหตุ: เราจะเพิ่มคำถามทั่วไปที่ให้ไว้ด้านล่าง (2 ธันวาคม 2020)

1. การเริ่มต้นใช้งาน

ทำความเข้าใจวิธีการเขียนโปรแกรมแบบไดนามิกสองวิธีของการเรียกซ้ำหน่วยความจำ "จากบนลงล่าง" และการเรียกซ้ำ "จากล่างขึ้นบน"

2. ปัญหาย่อยที่เกิดซ้ำ

ส่วนนี้จำเป็นต้องใช้ "หลักการคูณการนับก้าว" และ "หลักการบวกการนับแบบแบ่งหมวดหมู่"

คำถาม 70: นี่เป็นคำถามเดียวกับตัวเลขฟีโบนัชชี โจทย์การนับจะใช้หลักการนับการจำแนกประเภทและหลักการนับก้าว

3. โครงสร้างย่อยที่เหมาะสมที่สุด

แสดงให้เห็น:

คำถาม 377: โปรดทราบว่าการคัดกรองไม่ใช่ปัญหากระเป๋าเป้สะพายหลัง

4. ไม่มีผลที่ตามมา

ฝึกฝน:

ต่อไปนี้เป็นปัญหา "การเขียนโปรแกรมแบบไดนามิก" แบบคลาสสิก เนื่องจากปัญหาเหล่านี้มีความสำคัญมาก จึงรวมอยู่ในหมวดหมู่แยกต่างหาก

5. ผลรวมส่วนย่อยสูงสุด

ฝึกฝน:

6. ลำดับที่เพิ่มขึ้นที่ยาวที่สุด

หมายเหตุ: คำถาม 300 เป็นปัญหาการเขียนโปรแกรมแบบไดนามิกที่คลาสสิกมาก คำตอบของ $O(N log N)$ จะกำหนดสถานะตามลักษณะของปัญหา และพิสูจน์ว่าอาร์เรย์สถานะเป็นอาร์เรย์ที่ได้รับการจัดลำดับ ซึ่งจะช่วยลดความซับซ้อนของเวลา

ฝึกฝน:

7. สตริงย่อยทั่วไปที่ยาวที่สุด

8. ช่วงเวลา DP และ DP ที่แบ่งพาร์ติชัน

ช่วงเวลา DP:

DP แบบแบ่งพาร์ติชัน:

9. ทรี DP

บทที่ 14 การเขียนโปรแกรมแบบไดนามิก (ตอนที่ 2)

1. ปัญหาเกี่ยวกับกระเป๋าเป้สะพายหลัง

เก้าบรรยายเรื่องเป้: https://github.com/tianyicui/pack

("ประเภทเกม DP", "State Compression DP", "Digital DP" ฯลฯ จะถูกเพิ่ม)

คำถามอื่นๆ

บทที่ 15 อัลกอริธึมโลภ

บทที่ 17 ตารางแฮช

บทที่ 18 ผลรวมคำนำหน้าและตารางแฮช

บทที่ 19 การสำรวจเส้นทางกว้างครั้งแรก

ปัญหาบางประการเกี่ยวกับการข้ามต้นไม้ในแนวกว้างและปัญหาบางอย่างใน LeetBook

บทที่ 20 อัลกอริธึมทฤษฎีกราฟ (แผนผังการขยายขั้นต่ำ)

บทที่ 21 อัลกอริธึมทฤษฎีกราฟ (เส้นทางที่สั้นที่สุดแหล่งเดียว)

บทที่ 22 แบ่งแยกและพิชิตอัลกอริทึม

แนวคิดการแบ่งแยกและพิชิต (แบ่งและพิชิต) แบ่งปัญหาใหญ่ออกเป็นปัญหาย่อยย่อยประเภทเดียวกันหลายปัญหา แล้วจึงแก้ไขปัญหาย่อยเหล่านี้แบบวนซ้ำ หลังจากแต่ละปัญหาย่อยเสร็จสิ้นแล้ว วิธีแก้ไข ปัญหาเดิมก็ได้รับ

อัลกอริธึมการแบ่งแยกและพิชิตสามารถดำเนินการแบบคู่ขนานได้ แต่ในสาขาอัลกอริธึมพื้นฐาน อัลกอริธึมการแบ่งแยกและพิชิตจะดำเนินการในลักษณะการสำรวจเส้นทางเชิงลึกก่อน

อัลกอริธึมทั่วไปที่ใช้แนวคิดการแบ่งแยกและพิชิต: การเรียงลำดับแบบผสาน การเรียงลำดับแบบด่วน

ปัญหาทั่วไปของการแบ่งแยกและพิชิตความคิด: "คำถามที่ 51 ของดาบชี้ไปที่ข้อเสนอ": "คำถามที่ 51 ของดาบชี้ไปที่ข้อเสนอ" 51. คู่ลำดับย้อนกลับในอาร์เรย์ (คำอธิบายวิดีโอ)

คำถามทั่วไปอื่นๆ (จะเพิ่ม)

จะมีการอัปเดตต่อไป และเพื่อนๆ ก็สามารถแสดงความคิดเห็นอันมีค่าได้!