C++ 从字符串中跳到最大和最小字符所需的最小跳数

在这个问题中，我们需要找到到达给定字符串中最大和最小字符所需的最小跳数。我们可以在一次跳跃中移动到下一个或前一个字符。

我们可以通过找到给定字符串中字典顺序最大和最小字符的位置来解决这个问题。之后，我们可以找到从左边和右边到达找到的索引所需的最小跳数。

问题描述 - 我们有一个长度为N的字符串str，其中包含大写字母字符。我们需要找到从字符串的左边或右边到达字典顺序最小和最大字符所需的最小移动次数。

示例示例

输入

alpha = "ASDFDJF";

输出

2

解释

• 字典序最小的字符是‘A’，它位于索引0。

• 字典序最大的字符是‘S’，它位于索引1。

所以，如果我们跳到索引1，我们也可以到达索引0。所以，我们需要两次跳跃。一次是从左侧跳到索引0，另一次是从索引0跳到索引1。

输入

alpha = "OPQRSTUV";

输出结果

2

说明

• 字典顺序最小的字符是’O’，在索引0处。

• 字典顺序最大的字符是’P’，在索引7处。

我们可以从左侧通过1次移动到达索引0，从右侧通过1次移动到达索引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），因为我们使用恒定的空间来存储解决方案。

程序员可以解决问题，我们需要找到到达第二小和第二大字符所需的最小跳数。到达索引的逻辑相同，但是在找到第二个最小和最大字符的索引时会发生变化。