สมมติว่าเรามีกองตัวเลข เราต้องตรวจสอบว่าค่าใน stack นั้นเรียงกันเป็นคู่หรือไม่ คู่เหล่านี้สามารถเพิ่มขึ้นหรือลดลงได้ หากสแต็กมีค่าเป็นเลขคี่ องค์ประกอบบนสุดจะถูกแยกออกจากคู่ และเราควรเก็บเนื้อหาสแต็กเดิมไว้หลังจากตรวจสอบแล้ว
เพื่อแก้ปัญหานี้ เราสามารถใช้สามการดำเนินการบนสแต็กที่เรียกว่า push, pop และตรวจสอบว่าสแต็กว่างเปล่าหรือไม่
ดังนั้น หากอินพุตเป็น stk =[5, 6, -4, -5, 12, 11, 6, 7, 22] ผลลัพธ์จะเป็น True หลังจากลบองค์ประกอบบนสุด 22 คู่จะเป็น [(5 , 6), (-4, -5), (12, 11), (6, 7)] ทั้งหมดติดต่อกัน
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- temp :=ป๊อปองค์ประกอบจาก stk และดันเป็น temp
- ล้างสแต็ก stk
- flag :=จริง
- ในขณะที่ขนาดอุณหภูมิ> 1 ทำ
- item_first, item_second :=สององค์ประกอบบนสุดของ temp แล้วป๊อปอัป
- ถ้า |item_first - item_second| ไม่ใช่ 1 แล้ว
- ธง :=เท็จ
- ดัน item_first และ item_second ไปที่ stk
- ถ้าขนาดอุณหภูมิเท่ากับ 1 แล้ว
- ดันอุณหภูมิสูงสุดไปที่ stk
- ธงกลับ
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
โค้ดตัวอย่าง
def solve(stk): temp = stk[::-1] stk.clear() flag = True while len(temp) > 1: item_first = temp[-1] temp.pop() item_second = temp[-1] temp.pop() if abs(item_first - item_second) != 1: flag = False stk.append(item_first) stk.append(item_second) if len(temp) == 1: stk.append(temp[-1]) return flag stk = [5, 6, -4, -5, 12, 11, 6, 7, 22] print(solve(stk))
อินพุต
[5, 6, -4, -5, 12, 11, 6, 7, 22]
ผลลัพธ์
True
