Java 程式用於在常數時間內查詢給定字串的旋轉和第 K 個字元

---

在這個問題中，程式設計師需要對字串執行查詢。此外，還需要旋轉字串並列印更新後的字串的字元。解決此問題的最佳方法是不斷更新索引值，並在需要列印字元時訪問字串字元。

問題陳述 – 我們給定字串 alpha 和包含名為 'que' 的數字對的陣列。任務是在字串 alpha 上執行陣列中給出的查詢。

遵循以下查詢操作規則。

• (1, a) – 對給定字串進行總共左旋轉。

• (2, a) – 列印第 a 個位置的字元。

注意 – 這裡，a 的值是 1 到 N，其中 N 是字串的長度。

示例

輸入

que[][] = { { 1, 1 }, { 2, 1 }, { 2, 5 }, { 1, 3 } }, alpha = "wqedsdcs";

輸出

q, d

解釋 – 讓我們逐一在字串上執行所有查詢。

• 第一個查詢將字串旋轉 1 位，更新後的字串將為 'qedsdcsw'。

• 第二個查詢列印第 1 個位置的字元，即 'q'。

• 第三個查詢列印第 5 個位置的字元，即 'd'。

• 第四個查詢進行 3 次左旋轉。

輸入

que[][] = { { 1, 1 }, { 2, 3 }, { 1, 8 }, { 2, 7 } }, alpha = "tutorialspoint"

輸出

o, u

解釋

• 執行第一個查詢後，字串變為 'utorialspoint'。

• 更新後的字串中第 3 個位置的字元是 'o'。

• 執行第三個查詢後，字串變為 'pointtutorials'。

• 第 7 個位置的字元是 'u'。

方法 1

在這種方法中，我們定義索引指標來跟蹤當前索引。我們跟蹤最後一個索引以在最後一個索引上執行下一個查詢。

演算法

步驟 1 – 定義 'curr' 變數以跟蹤最新索引。

步驟 2 – 使用 for 迴圈遍歷查詢陣列。

步驟 3 – 從第 m 個索引獲取查詢，如果查詢對的第一個元素為 1，我們需要對最後更新的字串進行 'a' 次旋轉。

步驟 4 – 在這種情況下，我們將 'curr' 值更新為將對的第二個元素新增到 'curr' 並取其對 26 的模。

步驟 5 – 如果查詢對的第一個元素為 2，我們需要列印給定索引處的字元。

步驟 6 – 將 'curr' 變數的值更新為將查詢對的第二個元素新增到 'curr' 並取其對 26 的模。

步驟 7 – 訪問原始字串中 'curr' 索引處的字元。此外，在輸出中顯示字元。

示例

import java.util.*;

public class main {
    static void executeQueries(String alpha, int str_len, int que[][], int que_len) {
        // Current pointer pointing to the starting
        int curr = 0;
        // Traverse array
        for (int m = 0; m < que_len; m++) {
            // Query rotation
            if (que[m][0] == 1) {
                // Update value of curr
                curr = (curr + que[m][1]) % str_len;
            } else {
                int ch = que[m][1];
                // Get the index of the character in rotation
                int index = (curr + ch - 1) % str_len;
                // Show output
                System.out.println(alpha.charAt(index));
            }
        }
    }
    public static void main(String[] args) {
        String alpha = "wqedsdcs";
        int str_len = alpha.length();
        int que[][] = { { 1, 1 }, { 2, 1 },
                { 2, 5 }, { 1, 3 } };
        int que_len = que.length;
        executeQueries(alpha, str_len, que, que_len);
    }
}

輸出

q
d

時間複雜度 – O(M)，因為我們逐一執行所有查詢。

空間複雜度 – O(1)，因為我們沒有使用任何動態空間。

程式設計師也可以嘗試使用樸素方法來解決問題。在樸素方法中，程式設計師可以旋轉字串以執行第一個查詢，並訪問更新後的字串中的字元以執行第二個查詢。執行字串旋轉的方法有 1 到 2 種不同的方法；一種是將字串與其自身連線起來並獲取其子字串。