สมมติว่าเรามีสตริงตัวพิมพ์เล็ก s และอีกค่าหนึ่งคือ k ตอนนี้ให้พิจารณาการดำเนินการที่เราดำเนินการเข้ารหัสความยาวรันบนสตริงโดยใส่อักขระที่ต่อเนื่องกันซ้ำๆ เป็นจำนวนและอักขระ ดังนั้นหากสตริงที่เหมือนกับ "aaabbc" จะถูกเข้ารหัสเป็น "3a2bc" ที่นี่เราไม่ได้ใส่ "1c" สำหรับ "c" เนื่องจากปรากฏเพียงครั้งเดียวติดต่อกัน ดังนั้นเราจึงสามารถลบอักขระ k ติดต่อกันใน s ได้ก่อน จากนั้นจึงหาความยาวต่ำสุดที่เป็นไปได้ของการเข้ารหัสความยาวของการรันที่ได้
ดังนั้น หากอินพุตเป็น s ="xxxxxyyxxxxxzzxxx", k =2 เอาต์พุตจะเป็น 6 เนื่องจากสองตัวเลือกที่ชัดเจนคือการลบ "yy" หรือ "zz" หากเราลบ "yy" ออก เราจะได้ "10x2z3x" ซึ่งมีความยาวเท่ากับ 7 หากเราลบ "zz" ออก เราจะได้ "5x2y8x" ซึ่งมีความยาวเท่ากับ 6 ซึ่งเป็นค่าที่น้อยที่สุด
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดฟังก์ชัน calc_cost() นี่จะใช้เวลา l
-
ถ้า l เท่ากับ 0 แล้ว
-
คืนค่า 0
-
-
ถ้า l เท่ากับ 1 แล้ว
-
กลับ 1
-
-
มิฉะนั้น
-
ขนาดส่งคืนของ str(l) + 1
-
-
กำหนดคำนำหน้าฟังก์ชัน () นี่จะใช้เวลา s
-
ก่อน :=รายการเริ่มต้นด้วยคู่ [0, 0]
-
สุดท้าย :=null
-
สำหรับแต่ละ c ใน s ทำ
-
ถ้า c เหมือนกับครั้งสุดท้าย แล้ว
-
แทรกคู่ (องค์ประกอบที่ 0 ของรายการสุดท้ายของ pre, 1 + องค์ประกอบที่ 1 ของรายการสุดท้ายของ pre) ลงในรายการก่อนหน้า
-
-
มิฉะนั้น
-
แทรก (องค์ประกอบที่ 0 ของรายการสุดท้ายของ pre) + calc_cost (องค์ประกอบที่ 1 ของรายการสุดท้ายของ pre, 1) ลงในรายการก่อนหน้า
-
-
สุดท้าย :=c
-
-
กลับก่อน
-
-
จากวิธีหลัก ให้ทำดังนี้:
-
นำหน้า :=คำนำหน้า
-
suf :=ย้อนกลับคำนำหน้า (เรียงลำดับย้อนกลับ)
-
ตอบ :=อินฟินิตี้
-
สำหรับฉันในช่วง 0 ถึงขนาด s - k + 1 ทำ
-
เจ :=ผม + k
-
คู่ (ซ้าย, midl) :=pre[i]
-
คู่ (ขวา, midr) :=suf[j]
-
ราคา :=ซ้าย + ขวา
-
c1 :=s[i - 1] if i> 0 มิฉะนั้นจะเป็นโมฆะ
-
c2 :=s[j] ถ้า j <ขนาดของ s เป็นโมฆะ
-
ถ้า c1 เหมือนกับ c2 แล้ว
-
ราคา :=ต้นทุน + calc_cost(กลาง + กลาง)
-
-
มิฉะนั้น
-
ราคา :=ต้นทุน + calc_cost(กลาง) + calc_cost(กลาง)
-
-
ans :=ขั้นต่ำของ ans และค่าใช้จ่าย
-
-
กลับมาอีกครั้ง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
def calc_cost(l):
if l == 0:
return 0
if l == 1:
return 1
else:
return len(str(l)) + 1
class Solution:
def solve(self, s, k):
def prefix(s):
pre = [[0, 0]]
last = None
for c in s:
if c == last:
pre.append([pre[-1][0], pre[-1][1] + 1])
else:
pre.append([pre[-1][0] + calc_cost(pre[-1][1]),1])
last = c
return pre
pre = prefix(s)
suf = prefix(s[::-1])[::-1]
ans = float("inf")
for i in range(len(s) - k + 1):
j = i + k
left, midl = pre[i]
right, midr = suf[j]
cost = left + right
c1 = s[i - 1] if i > 0 else None
c2 = s[j] if j < len(s) else None
if c1 == c2:
cost += calc_cost(midl + midr)
else:
cost += calc_cost(midl) + calc_cost(midr)
ans = min(ans, cost)
return ans
ob = Solution()
s = "xxxxxyyxxxxxzzxxx"
print(ob.solve(s, 2)) อินพุต
s = "xxxxxyyxxxxxzzxxx"
ผลลัพธ์
6
