โจทย์: มีรหัสเป็น Circular Array code ความยาว n และ Key k ต้องถอดรหัสโดยแทนที่ทุกตัวเลขพร้อมกัน:
- k > 0: แทนที่ตัวที่ i ด้วยผลรวมของ k ตัวถัดไป
- k < 0: แทนที่ตัวที่ i ด้วยผลรวมของ |k| ตัวก่อนหน้า
- k = 0: แทนที่ทุกตัวด้วย 0
Circular: ตัวถัดไปของ code[n-1] คือ code[0], ตัวก่อนหน้าของ code[0] คือ code[n-1]
ตัวอย่าง
- Input:
code = [8, 2, 3, 5], k = 3 - Output:
[10, 16, 15, 13]
i=0: next 3 = code[1]+code[2]+code[3] = 2+3+5 = 10 i=1: next 3 = code[2]+code[3]+code[0] = 3+5+8 = 16 i=2: next 3 = code[3]+code[0]+code[1] = 5+8+2 = 15 i=3: next 3 = code[0]+code[1]+code[2] = 8+2+3 = 13
โค้ด Python (O(n) Sliding Window)
def decrypt(code, k):
"""
ถอดรหัส Circular Array
Args:
code: List[int] - รหัสต้นฉบับ
k: int - Key (บวก = ถัดไป, ลบ = ก่อนหน้า, 0 = ทั้งหมดเป็น 0)
Returns:
List[int] - รหัสที่ถอดแล้ว
"""
n = len(code)
if k == 0:
return [0] * n
result = [0] * n
if k > 0:
# Sliding Window สำหรับ Next k elements
# เริ่มต้น: ผลรวมของ code[1] ถึง code[k]
window_sum = sum(code[1:k+1])
for i in range(n):
result[i] = window_sum
# เลื่อน Window: ลบ code[i+1], เพิ่ม code[i+k+1]
window_sum -= code[(i + 1) % n]
window_sum += code[(i + k + 1) % n]
else: # k < 0
# Sliding Window สำหรับ Previous |k| elements
k_abs = -k
# เริ่มต้น: ผลรวมของ code[n-k_abs] ถึง code[n-1]
window_sum = sum(code[n - k_abs:])
for i in range(n):
result[i] = window_sum
# เลื่อน Window: ลบ code[i-k_abs], เพิ่ม code[i]
window_sum -= code[(i - k_abs) % n]
window_sum += code[i % n]
return result
# ทดสอบ
if __name__ == "__main__":
# Test Case 1
code = [8, 2, 3, 5]
k = 3
print(f"code={code}, k={k} => {decrypt(code, k)}")
# Expected: [10, 16, 15, 13]
# Test Case 2: k < 0
code = [8, 2, 3, 5]
k = -2
print(f"code={code}, k={k} => {decrypt(code, k)}")
# i=0: prev 2 = code[3]+code[2] = 5+3=8? Wait...
# Previous 2 of index 0: indices (0-1)%4=3, (0-2)%4=2 => code[3]+code[2]=5+3=8
# i=1: indices 0,3 => 8+5=13
# i=2: indices 1,0 => 2+8=10
# i=3: indices 2,1 => 3+2=5
# Expected: [8, 13, 10, 5]
# Test Case 3: k = 0
code = [1, 2, 3, 4]
k = 0
print(f"code={code}, k={k} => {decrypt(code, k)}")
# Expected: [0, 0, 0, 0]
# Test Case 4: Single element
code = [5]
k = 1
print(f"code={code}, k={k} => {decrypt(code, k)}")
# Expected: [5] (next 1 is itself)
ผลลัพธ์
code=[8, 2, 3, 5], k=3 => [10, 16, 15, 13] code=[8, 2, 3, 5], k=-2 => [8, 13, 10, 5] code=[1, 2, 3, 4], k=0 => [0, 0, 0, 0] code=[5], k=1 => [5]
Complexity Analysis
- Time: O(n) - Single pass ด้วย Sliding Window
- Space: O(n) สำหรับ Result Array
- ดีกว่า Naive O(n×|k|) มากเมื่อ |k| ใหญ่
การอธิบาย Sliding Window
แทนที่จะคำนวณผลรวมใหม่ทุกครั้ง (O(k)) ให้รักษา Window Sum และอัปเดตโดย:
- ลบ Element ที่ออกจาก Window
- บวก Element ที่เข้า Window ใหม่
- ใช้ Modulo
% nจัดการ Circular Index
LeetCode Reference
Problem 1652: "Defuse the Bomb" - Medium
