Source: KEEP SWAPPING 2

Given a string of lowercase alphabets A of size N and two integers B and C.

You have to perform B swaps, Where i’th swap = swap(A[i % N], A[(i + C) % N]).

Return the final string A after B swaps.

NOTE: String A is 0 based indexed.

NOTE: Swaps are 0 based indexed.

Input Format

The first argument given is the string A.
The second argument given is the string representation of integer B.
The third argument given is the integer C.

Output Format

Return the final string A after B swaps.

Constraints

1 <= N <= 10^5
1 <= B <= 10^11
1 <= C <= N

For Example

Input 1:
    A = "interviewbit"
    B = "3"
    C = 3
Output 1:
    A = "ervintiewbit"
Explaination 1:
    After swap 0: swap(A[0%12], A[(0 + 3)%12]) A = "entirviewbit"
    After swap 1: swap(A[1%12], A[(1 + 3)%12]) A = "ertinviewbit"
    After swap 2: swap(A[2%12], A[(2 + 3)%12]) A = "ervintiewbit"
    After swap 3: swap(A[3%12], A[(3 + 3)%12]) A = "ervintiewbit"	
Input 2:
    A = "raman"
    B = "1"
    C = 4
Output 2:
    "anmar"
Explaination 2:
    After swap 0: swap(A[0%5], A[(0 + 4)%5]) A = "namar"
    After swap 1: swap(A[1%5], A[(1 + 4)%5]) A = "anmar"

解題：

  1. 這題是稍早在寫 Simple Queries 時因為實在看不懂解題的邏輯，點了網站提供的相似題型來試試看會不會寫完會不會比較懂那題到底在幹嘛。殊不知這卻是另一個深淵……
  2. 這題如果單純採用 for loop 的方式不斷重複執行調換，想當然在執行時一定會出現TLE。但這題有甚麼辦法可以執行簡化呢？首先我們要先確定這個依序不斷進行兩兩調換的方式存在怎樣的邏輯： 
    在執行調換的過程中，A[:C]會不斷被重複執行與其他元素之對調
舉例來說： A = "interviewBit", B = "10", C = 5, n = 12
Swap #1: A[0], A[5] = A[5], A[0], A = "vnteriiewBit"
......
Swap #6: A[5], A[10] = A[10], A[5]
（因 A[5] 已於 #1 被換成 A[0]，故其實本次對調的字母實為 A[0] 及 A[10]）
......

    因此要知道所有的對調過程結束後字串如何排列，找到 A[:C] 會改到甚麼位置便是切入點；

  3. 故要找 A[:C] 的新位置，首先自然是計算這些元素總共進行了幾次對調： 
    以上述例子繼續
A[0] 總共會經歷 (11//5 + (1 if 11%5 > 0 else 0))，共 3 次調換
位置會被換到 ((0 + 3*5) % n) = 3
故可以確定完成所有調換程序後，新字串 NA[3] = A[0]
  4. 在確定 A[:C] 的新位置之後，再來自然是找 A[C:] 會落在哪些地方： 
    A[C:] 的字母會被調換總共 B//n 次
（為什麼不考慮B<n的調整關係？
因為相關調換調整已在步驟3時被充分考量
此處進行計算只是為了找到剩下字母的排列先後順序）
每次移動 C 個位置
但必須考慮涉及首尾對調時字母填入次序會隨之改變的情形

完成後便僅是將剩下的字母依序填入新陣列的空白位置

Code:

class Solution:
    # @param A : string
    # @param B : string
    # @param C : integer
    # @return a strings
    def solve(self, A, B, C):
        n = len(A)
        if C == n: return A
        B = int(B) + 1 #swap int(B) +1 times in total
        sol = ['_'] * n
        #why the loop is narrowed to C, instead of B?
        #bcz only in this range we can make sure the characters
        #are just kept swapped while the loop is processing
        for i in range(C):
            #steps: compute how many times it would be swapped
            steps = B // C + (1 if B % C > i else 0)
            #loc: the final location after all swaps
            loc = (i + C * steps) % n
            sol[loc] = A[i]
        #So, how can we get the locations of the rest char?
        offset = B // n * C + max(0, B % n + C - n)
        #offset: how many times other chars get swapped
        j = 0
        #allocate the rest of chars
        A = A[C:]
        for i in range(n):
            if sol[i] == '_':
                sol[i] = A[(j + offset) % len(A)]
                j += 1
        return ''.join(sol)

這邏輯關係筆者覺得還蠻難想的，竟然只值200分啊……

GitHub: GitHub

發表留言