นับหน้าต่างที่เป็นไปตามกฎ
เทคนิค at-most-K ลบด้วย at-most-(K-1)
นับหน้าต่างที่เป็นไปตามกฎ เป็นบทเรียน Competitive Programming Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Competitive Programming Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
นับ ไม่ใช่วัดความยาว
บางครั้งคุณต้อง นับอาร์เรย์ย่อยที่ตรงตามกฎ แทนที่จะหาช่วงที่ยาวที่สุด มีเทคนิคเล็กน้อยที่เปลี่ยนโจทย์นี้ให้กลายเป็นงานหน้าต่างเลื่อนที่ง่ายขึ้น 🔢
ความท้าทายของ K แบบพอดี
การนับอาร์เรย์ย่อยที่มีบางสิ่ง พอดี K รายการโดยตรงเป็นเรื่องยุ่งยาก ขอบเขตของหน้าต่างเปลี่ยนไปมา ทำให้การใช้หน้าต่างเดียวที่ชัดเจนทำได้ยาก
ปรับโจทย์เป็นไม่เกิน
การนับอาร์เรย์ย่อยที่มีจำนวน ไม่เกิน K รายการทำได้ง่ายกว่ามากด้วยหน้าต่างเดียว เมื่อขยาย right ออกไป ค่า left ที่เป็นไปได้ทุกค่าจะทำให้เกิดอาร์เรย์ย่อยที่นับได้หนึ่งรายการ
เทคนิคการลบ
จำนวนที่มีพอดี K เท่ากับ atMost(K) ลบ atMost(K - 1) การนับที่ง่ายสองครั้งจะรวมกันเป็นคำตอบแบบพอดีที่คุณต้องการ
answer = at_most(k) - at_most(k - 1)สร้างฟังก์ชันช่วย
เขียนฟังก์ชันหนึ่งฟังก์ชันเพื่อแสดงจำนวนอาร์เรย์ย่อยที่มี ไม่เกิน k รายการ ฟังก์ชันนี้จะเลื่อนหน้าต่างและหดหน้าต่างทุกครั้งที่จำนวนเกิน k
def at_most(k):
left = 0
total = 0หดตัวเมื่อฝ่าฝืนเงื่อนไข
ขยาย right และอัปเดตหน้าต่าง ขณะที่หน้าต่างมีค่า มากกว่า k ให้เลื่อน left ไปข้างหน้าเพื่อทำให้ค่ากลับมาอยู่ในช่วง
while count > k:
# remove a[left]
left += 1เพิ่มจำนวนของหน้าต่าง
หลังจากปรับหน้าต่างแล้ว อาร์เรย์ย่อยทุกส่วนที่จบที่ right และมีจุดเริ่มต้นตั้งแต่ left เป็นต้นไปจะถูกต้อง ให้เพิ่มค่า right ลบ left บวกหนึ่ง
total += right - left + 1เหตุใดจำนวนนี้จึงถูกต้อง
เมื่อกำหนด right ไว้ จุดเริ่มต้นที่ถูกต้องคือ left, left+1 ไปจนถึง right ซึ่งเท่ากับอาร์เรย์ย่อย right - left + 1 รายการพอดี และทั้งหมดมีจำนวนไม่เกิน k
รวมการเรียกใช้สองครั้ง
เรียกใช้ฟังก์ชันช่วยสองครั้งแล้ว ลบผลลัพธ์ออกจากกัน แต่ละการเรียกใช้เวลา O(n) ดังนั้นการนับจำนวนที่มีพอดี K ทั้งหมดก็ยังมีเวลาเป็นเชิงเส้น
return at_most(k) - at_most(k - 1)จัดการกรณีขอบ
เมื่อ k เป็นศูนย์ atMost(k - 1) จะใช้ค่าลบหนึ่ง ต้องจัดการกรณีนี้เพื่อให้ฟังก์ชันช่วยยังคืนค่าจำนวนศูนย์ที่สมเหตุสมผล
กรณีที่นำไปใช้ได้
แนวคิด ไม่เกินลบไม่เกินนี้เหมาะกับการนับอาร์เรย์ย่อยที่มีค่าที่แตกต่างกันพอดี K รายการ มีจำนวนเลขคี่พอดี K ตัว หรือมีคุณสมบัติต่อหน้าต่างแบบโมโนโทนิกใด ๆ
ตรวจสอบอย่างรวดเร็ว
คุณต้องการนับอาร์เรย์ย่อยที่มีสมาชิกแตกต่างกันพอดี K ตัว
ทบทวน
การนับจำนวนที่มีพอดี K คือ atMost(K) ลบ atMost(K - 1) เท่านั้น ฟังก์ชันช่วยแต่ละตัวเลื่อนหน้าต่างด้วยเวลา O(n) ดังนั้นการนับทั้งหมดจึงยังเป็นเชิงเส้น ✅
คำถามที่พบบ่อย
บทเรียน “นับหน้าต่างที่เป็นไปตามกฎ” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “นับหน้าต่างที่เป็นไปตามกฎ” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Competitive Programming Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “นับหน้าต่างที่เป็นไปตามกฎ”
เทคนิค at-most-K ลบด้วย at-most-(K-1) คุณปฏิบัติ Competitive Programming Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Competitive Programming Academy หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Competitive Programming Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน
บทเรียน “นับหน้าต่างที่เป็นไปตามกฎ” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Competitive Programming Academy นี้ได้ไหม
ได้ บทเรียน Competitive Programming Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- ผลรวมหน้าต่างขนาดคงที่
- หน้าต่างแปรผันด้วยตัวชี้สองตัว
- สตริงย่อยที่ยาวที่สุดโดยไม่มีตัวซ้ำ
- นับหน้าต่างที่เป็นไปตามกฎ