Python3程式：常數時間內查詢給定字串的旋轉和第K個字元

---

在這個問題中，我們需要根據給定的規則執行查詢，並列印更新後的字串中的字元。我們將使用兩種不同的方法來解決這個問題。第一種方法將使用字串旋轉的概念，第二種方法將使用索引定製的方法。

問題陳述 – 給我們的任務是對字串執行給定的查詢。我們得到一個查詢陣列，每個查詢包含兩個整數。

按照以下步驟對字串執行給定的查詢。

• (1, l) – 需要將字串左旋轉l次。

• (2, l) – 需要訪問第l個位置的字元。這裡，1 <= l <= n。

示例

輸入

queries = [[1, 3], [2, 3], [2, 4], [2, 2]], s = "vdflkmng"

輸出

m, n, k

解釋 – 讓我們執行陣列中給定的四個查詢。

• 在第一個查詢中對字串進行3次左旋轉。最終字串將是’lkmngvdf’。

• 列印第三個字元，即’m’。

• 列印第四個字元，即’n’。

• 列印第二個字元，即’k’。

輸入

queries = [[1, 3], [1, 2], [1, 3], [2, 2]], s = "welcome"

輸出

l

解釋

• 第一個查詢後，字串將變為’comewel’。

• 第二個查詢後，字串將變為’mewelco’。

• 第三個查詢後，字串將變為’elcomew’。

• 在最後一個查詢中，它列印第二個字元，即’l’。

方法1

在這種方法中，我們將給定的字串分成兩部分，然後再次連線起來以執行N次左旋轉。之後，我們在第二個查詢中訪問給定索引處的字元。

演算法

步驟1 – 第一步，我們需要迭代所有查詢的陣列。

步驟2 – 如果que[m][0] == 1，則對字串s進行總共que[m][1]次左旋轉，並將其儲存到s中。

步驟2.1 – 為了進行que[m][1]次左旋轉，我們可以從m索引處將字串分成兩部分，並將右部分和左部分連線起來。

步驟3 – 如果que[m][0] == 2，我們需要列印que[m][1]索引處的字元。

步驟4 – 從給定索引訪問字元，並在輸出中顯示。

示例

def executeQueries(s, str_len, que, que_len):
    # Traverse query
    for m in range(que_len):
        # String rotation
        if que[m][0] == 1:
            # Rotate the string by que[m][1] to the left
            s = s[que[m][1]:] + s[:que[m][1]]
        else:
            index = que[m][1] - 1
            # Show character
            print(s[index])
# Driver code
if __name__ == "__main__":
    s = "vdflkmng"
    length = len(s)
    queries = [[1, 3], [2, 3], [2, 4], [2, 2]]
    queries_length = len(queries)
    executeQueries(s, length, queries, queries_length)

輸出

m
n
k

時間複雜度 – O(M*N)，因為我們將字串分成兩部分並遍歷列表。

空間複雜度 – O(N)，因為我們儲存旋轉後的字串。

方法2

此方法是上述方法的最佳化版本。在這裡，我們定義一個指標指向最後一個索引。當我們執行查詢時，我們更新指標值，這有助於我們節省時間和空間。

演算法

步驟1 – 定義’ind_ptr’變數並初始化為零，表示索引指標。

步驟2 – 使用迴圈遍歷列表。

步驟3 – 如果que[m][0]等於1，我們需要操作索引指標的值。

步驟3.1 – 將que[m][1]新增到ind_ptr，取結果值對26取模，然後再次將其賦值給ind_ptr變數。

步驟4 – 如果que[m][0]等於2，我們需要列印位於que[m][1]索引處的字元。

步驟5 – 將que[m][1] – 1新增到ind_ptr變數，並對其取模26。之後，將結果值賦給index變數。

步驟6 – 從索引訪問字元，並將其列印到輸出中。

示例

def executeQueries(s, str_len, que, que_len):
    # Starting pointer
    ind_ptr = 0
    # Traverse query
    for m in range(que_len):
        # String rotation
        if que[m][0] == 1:
            # Change index pointer value
            ind_ptr = (ind_ptr + que[m][1]) % str_len
        else:
            index = que[m][1]
            # Get the rotational index of the character
            index = (ind_ptr + index - 1) % str_len
            # Show character
            print(s[index])
if __name__ == "__main__":
    s = "vdflkmng"
    length = len(s)
    queries = [[1, 3], [2, 3], [2, 4], [2, 2]]
    queries_length = len(queries)
    executeQueries(s, length, queries, queries_length)

輸出

m
n
k

時間複雜度 – O(M)，因為我們遍歷給定的查詢列表。

空間複雜度 – O(1)，因為我們使用常量空間。

我們根據給定的條件執行字串的左旋轉。程式設計師也可以嘗試執行包含右字串旋轉的查詢。