在給定字串中從任一端到達最大和最小字元的最小跳躍次數

---

在這個問題中，我們需要找到在給定字串中到達最大和最小字元所需的最小跳躍次數。我們可以在一次跳躍中移動到下一個或上一個字元。

我們可以透過在給定字串中找到字典序最大和最小字元的位置來解決這個問題。之後，我們可以找到從字串的左側和右側到達找到的索引所需的最小跳躍次數。

問題陳述 – 我們有一個長度為 N 的字串 str，其中包含大寫的字母字元。我們需要找到從字串的左側或右側到達字典序最小和最大字元所需的最小移動次數。

示例

輸入

alpha = "ASDFDJF";

輸出

2

解釋

• 字典序最小字元是 'A'，其索引為 0。

• 字典序最大字元是 'S'，其索引為 1。

因此，如果我們跳到索引 1，我們也可以到達索引 0。所以，我們需要兩次跳躍。一次是從左側到索引 0，另一次是從索引 0 到索引 1。

輸入

alpha = "OPQRSTUV";

輸出

2

解釋

• 字典序最小字元是 'O'，其索引為 0。

• 字典序最大字元是 'P'，其索引為 7。

我們可以從左側一步到達索引 0，從右側一步到達索引 7。因此，我們總共需要 2 步。

輸入

alpha = "CDABNFGH"

輸出

5

解釋 – 如果我們從左側跳躍 5 次，我們可以到達 'A' 和 'N'，它們分別是字典序最小和最大字元。

方法 1

只有三種方法可以到達這兩個字元。第一種方法是從左側到達這兩個字元。第二種方法是從右側到達這兩個字元。第三種方法是從左側到達一個字元，從右側到達另一個字元。我們需要取上述所有三種方案中的最小值。

演算法

步驟 1 – 定義 largeInd 和 smallInd 變數來儲存字典序最小和最大字元的索引。

步驟 2 – 使用迴圈遍歷字串。在迴圈中，如果第 p 個索引處的字元大於 ‘largeInd’ 索引處的字元，則將 ‘largeInd’ 更新為 p。

步驟 3 – 如果第 p 個索引處的字元小於 ‘smallInd’ 索引處的字元，則將 ‘smallInd’ 的值更新為 p。

步驟 4 – 宣告 ‘minMoves’ 和 ‘maxMoves’ 變數，並將 largeInd 和 smallInd 的最小值和最大值分別儲存在這兩個變數中。

步驟 5 – 宣告 sol1、sol2 和 sol3 變數來儲存所有三種方案。

步驟 6 – 在 sol1 中，儲存字串長度 – minMoves 以從右側到達這兩個索引。

步驟 7 – 在 sol2 中，儲存 maxMoves + 1 以從左側到達這兩個索引。

步驟 8 – 在 sol3 變數中，儲存 minMoves + 1 + str_len – maxMoves 以從左側到達一個索引，從右側到達另一個索引。

步驟 9 – 從 sol1、sol2 和 sol3 中取最小值並返回結果。

示例

#include <bits/stdc++.h>
using namespace std;

int totalMoves(string alpha, int str_len) {
    // To store positions of the largest and smallest character
    int largeInd = 0, smallInd = 0;
    // Find the index of the largest and smallest character
    for (int p = 0; p < str_len; p++) {
        if (alpha[p] > alpha[largeInd])
            largeInd = p;
        if (alpha[p] < alpha[smallInd])
            smallInd = p;
    }
    // Get the min and max moves
    int minMoves = min(largeInd, smallInd);
    int maxMoves = max(largeInd, smallInd);
    // Finding all possible solutions
    int sol1, sol2, sol3;
    // Jumping to both elements from the right side
    sol1 = str_len - minMoves;
    // Jumping to both elements from the left side
    sol2 = maxMoves + 1;
    // Jumping to min from the left and max from right
    sol3 = minMoves + 1 + str_len - maxMoves;
    // Take a minimum of all possible solutions
    int answer = min(sol1, min(sol2, sol3));
    return answer;
}
int main() {
    string alpha = "ASDFDJF";
    int str_len = alpha.length();
    cout << "The number of minimum moves required to reach the largest and smallest character is - " << totalMoves(alpha, str_len);
    return 0;
}

輸出

The number of minimum moves required to reach the largest and smallest character is - 2

時間複雜度 – O(N)，因為我們找到了字典序最大和最小字元的索引。

空間複雜度 – O(1)，因為我們使用常量空間來儲存解決方案。

程式設計師可以解決需要找到到達第二小和最大字元所需最小跳躍次數的問題。到達索引的邏輯相同，但查詢第二小和最大字元的索引會發生變化。