将所有大写字符移动到所有小写字符之前的最小操作次数

给定一个字符串 'str'，其中包含大写和小写字母。任何小写字符都可以通过单个操作更改为大写字符，反之亦然。目标是打印此过程中所需的最小操作次数，以生成一个至少包含一个小写字符，然后至少包含一个大写字符的字符串。

输入输出场景

第一种可能的解决方案：前 4 个字符可以转换为大写字符，即“TUTORial”，需要 4 次操作。

输入

str = “tutoRial”

输出

1

第二种可能的解决方案：第三个字符可以转换为小写字符，即“tutorial”，需要 1 次操作。

输入

str = “point”

输出

0

字符串已采用指定的格式。

有两种可能的结果

  • 通过确定最后一个大写字符的索引，字符串中的所有小写字符都应转换为大写字符。

  • 或者，获取字符串中第一个小写字符的索引，并将之后的所有大写字母转换为小写字母。

选择操作次数最少的方案。

Java 实现

让我们了解一下这种方法的 Java 实现

示例

public class Main {
    public static int minOperationsLower(String str, int n) {
        // Store the indices of the last uppercase character and the first lowercase character
        int i, lastUpperCase = -1, firstLowerCase = -1;

        for (i = n - 1; i >= 0; i--) {  //finding uppercase
            if (Character.isUpperCase(str.charAt(i))) {
                lastUpperCase = i;
                break;
            }
        }
        for (i = 0; i < n; i++) {  //finding lowercase
            if (Character.isLowerCase(str.charAt(i))) {
                firstLowerCase = i;
                break;
            }
        }       
        if (lastUpperCase == -1 || firstLowerCase == -1)
            return 0;

        // Counting of uppercase characters that appear after the first lowercase character
        int countUpperCase = 0;
        for (i = firstLowerCase; i < n; i++) {
            if (Character.isUpperCase(str.charAt(i))) {
                countUpperCase++;
            }
        }

        // Count of lowercase characters that appear before the last uppercase character
        int countLowerCase = 0;
        for (i = 0; i < lastUpperCase; i++) {
            if (Character.isLowerCase(str.charAt(i))) {
                countLowerCase++;
            }
        }

        // Return the minimum operations required
        return Math.min(countLowerCase, countUpperCase);
    }

    // main method
    public static void main(String args[])  {
        String str = "tutoRIalsPoinT";
        int n = str.length();
        System.out.println("Operations Required: "+minOperationsLower(str, n));
    }
}

输出

Operations Required: 4

时间复杂度：O(N)，其中 N 是字符串的长度

空间复杂度：O(1)，未使用额外空间。

更新于： 2023年8月22日

116 次查看

启动您的 职业生涯

通过完成课程获得认证

开始
广告