时间戳

首页 > 解决方案 > 使字符串连续 x 没有所需的最小更改。A，然后在 (nx) 个 B 之后

java - 使字符串连续 x 没有所需的最小更改。A，然后在 (nx) 个 B 之后

问题描述

我陷入了Java中与问题相关的字符串之一。我的逻辑在某些测试用例中运行良好，但不适用于所有测试用例。请建议我以下问题的实际逻辑：

我得到一个包含 n 个字符的字符串 s，仅包含 A's 和 B's 。我可以选择任何索引 i 并将 s(i) 更改为 A 或 B。找到最小的编号。您必须对字符串 S 进行更改，以使结果字符串的格式为：AAAAA.....BBBBB。换句话说，我的任务是确定最小数量。的变化使得字符串 s 有 x 没有。A 的开头，然后是剩余的 (nx) 没有。B 的。

样本输入如下 4 3 AAB 5 AABAA 1 B 4 BABA

第一行：一个整数，表示测试用例的数量 对于每个测试用例：第一行包含一个整数，表示字符串的大小 第二行包含字符串

我的代码如下

import java.util.*;
class TestClass {
    public static void main(String args[] ) throws Exception {
        Scanner s = new Scanner(System.in);
        TestClass t = new TestClass();
        int test_case = s.nextInt();
        for(int i = 0; i < test_case; i++){
            int len = s.nextInt();
            String none = s.nextLine();
            String str = s.nextLine();
            int cnta = t.count_ab(str,'A');
            int cntb = t.count_ab(str,'B');
            char c1 = '1';
            if(cnta > cntb){
                c1 = 'A';
            }
            else{
                c1 = 'B';
            }
            int count = 0;
            int c1_count = 0;
            int c2_count = 0;
            if(str.length() > 1){
                String rev = "";
                c1_count = t.cnt_init_a(str, 'A');
                StringBuilder sb = new StringBuilder(str);
                rev = sb.reverse().toString();
                c2_count = t.cnt_init_a(rev, 'B');
                int rem_len = str.length() - c2_count;
                for(int h = c1_count; h < rem_len; h++){
                    if(Character.compare(str.charAt(h), c1) != 0){
                        count = count + 1;
                    }
                }

            }
            System.out.println(count);
        }
    }

    public int cnt_init_a(String str, char c){
        int cnt = 0;
        for(int l = 0; l < str.length(); l++){
            if(Character.compare(str.charAt(l), c) == 0){
                cnt = cnt + 1;
            }
            else{
                break;
            }
        }
        return cnt;
    }

    public int count_ab(String str, char c){
        int cnt = 0;
        for(int g = 0; g < str.length(); g++){
            if(Character.compare(str.charAt(g), c) == 0){
                cnt = cnt + 1;
            }
        }
        return cnt;
    }

标签： javajava-8

解决方案

您的逻辑对于例如"BAAAAAAAAAABBBBBBBBBB"和失败"AAAAAAAAAABBBBBBBBBBA"。

您应该首先忽略所有前导 A 和所有尾随 B，因为它们永远不应更改。

"BAAAAAAAAAABBBBBBBBBB"-> "BAAAAAAAAAA"（删除尾随 B）
"AAAAAAAAAABBBBBBBBBBA"-> "BBBBBBBBBBA"（删除前导 A）

然后将前导 B 更改为 A，或将尾随 A 更改为 B，以较短者为准。

然后重复这个过程。

推荐阅读