สมมติว่าเรามีสตริง s ที่มีตัวเลขเท่านั้น และมีค่า a และ b สองค่า เราสามารถใช้หนึ่งในสองการดำเนินการต่อไปนี้กี่ครั้งก็ได้และเรียงลำดับตาม s −
-
เพิ่ม 'a' ให้กับรายการตำแหน่งคี่ทั้งหมดของ s (0-indexed) หากหลักเป็น 9 การเพิ่มบางอย่างด้วยจะวนกลับเป็น 0
-
หมุน 's' ไปทางขวาโดยตำแหน่ง b
ดังนั้น เราต้องหาสตริงที่เล็กที่สุดเกี่ยวกับศัพท์เฉพาะที่เราหาได้จากการดำเนินการข้างต้นจำนวนครั้งใน s
ดังนั้น หากอินพุตเป็น s ="5323" a =9 b =2 ผลลัพธ์จะเป็น 2050 เพราะหากเราติดตาม
- หมุน:"5323"
- เพิ่ม:"5222"
- เพิ่ม:"5121"
- หมุน:"2151"
- เพิ่ม:"2050"
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- เห็นแล้ว :=ชุดใหม่
- deq :=คิวใหม่ที่มีหนึ่งองค์ประกอบ 's'
- ในขณะที่ deq ไม่ว่างเปล่า ทำ
- curr :=องค์ประกอบที่ถูกลบครั้งแรกของ deq
- ใส่เคอร์เซอร์ในชุดที่เห็น
- โฆษณา :=ดำเนินการเพิ่มที่กำหนดในสกุลเงิน
- ถ้าไม่เห็นโฆษณาก็
- แทรกโฆษณาที่ส่วนท้ายของ deq
- แทรกโฆษณาในชุดที่เห็น
- ro :=ดำเนินการหมุนเวียนกับสกุลเงิน
- ถ้าไม่เห็น ro ก็
- ใส่ ro ที่ส่วนท้ายของ deq
- ใส่ ro ในชุดที่เห็น
- คืนขั้นต่ำที่เห็น
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
from collections import deque def add_(s,a): res = '' for idx, i in enumerate(s): if idx % 2 == 1: num = (int(i) + a) % 10 res += str(num) else: res += i return res def rotate_(s, b): idx = len(s)-b res = s[idx:] + s[0:idx] return res def solve(s, a, b): seen = set() deq = deque([s]) while deq: curr = deq.popleft() seen.add(curr) ad = add_(curr, a) if ad not in seen: deq.append(ad) seen.add(ad) ro = rotate_(curr, b) if ro not in seen: deq.append(ro) seen.add(ro) return min(seen) s = "5323" a = 9 b = 2 print(solve(s, a, b))
อินพุต
"5323", 9, 2
ผลลัพธ์
2050
