主页 / 问题 / 1594797
Accepted
Kiawem
Asked:2024-09-25 02:36:13 +0000 UTC2024-09-25 02:36:13 +0000 UTC

请解释一下算法的逻辑

  • 772

这是问题陈述：

在她的生日那天，Mila 收到了一个字符串 S，由字符“0”和“1”组成。但米拉觉得这条线不美，所以她决定改正！ Mila 对美丽线条的定义如下：

  1. 让我们将字符串拆分为由相同字符组成的最长可能的子字符串。
  2. 如果所有这些子串的长度相同，则原始字符串被认为是漂亮的，否则被认为是丑陋的。

例如，字符串 '010101' 被拆分为子字符串 '0', '1', '0', '1', '0', '1' 因此很漂亮，而字符串 '000101' 被拆分为子字符串'000', '1', '0', '1' 因此很难看。漂亮字符串的其他示例：“1”、“110011”、“00001111”、“00000000”。丑陋字符串的其他示例：“011”、“010011”、“00110100”。 Mila 要求您计算字符串 S 中需要更改的最少字符数才能使其美观。

这是解决问题的代码：


public class Main {
    public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       String line = sc.next();
       int ans = Integer.MAX_VALUE;
       for (int i = 1; i <= line.length(); i++) {
           if (line.length() % i == 0) {
               int minChanges = minChanges(i, line);
               ans = Math.min(ans, minChanges);
           }
       }
        System.out.println(ans);
    }

    private static int minChanges(int rangeLength, String line) {
        int rangeCount = line.length() / rangeLength;
        int startWithOnes = 0;
        int startWithZeroes = 0;
        for (int i = 0; i < rangeCount; i++) {
            int zeros = 0;
            int ones = 0;
            for (int j = 0; j < rangeLength; j++) {
                char c = line.charAt(j + i * rangeLength);

                if (c == '0') {
                    zeros++;
                }

                if (c == '1') {
                    ones++;
                }

                startWithZeroes += (i % 2 == 0 ? zeros : ones);
                startWithOnes += (i % 2 == 0 ? ones : zeros);
            }
        }
        return Math.min(startWithOnes, startWithZeroes);
    }
}

我无法弄清楚 startWithZeroes 和 startWithOnes 变量到底算什么。我相信它计算一条线需要执行多少个操作，以便每个小节（变量 i）以 0 或 1 开头。如果我们让 i 将线分成 1 个元素的段，那么它与手动计算一致（您可以从例子中看出）。 000101是第一行，据我了解，每个偶数段都需要以 0 开头，并且由于该段最初是基于段中的一个数字来考虑的，因此我们得到 010101 （花费了 1 个替换）。如果它以 1 开头，那么我们得到 101010（花费了 5 个替换）。一切都汇聚到了这里。

接下来我们取一段 2(i = 2)。如果偶数段为零。我们将通过花费 3 次行动来获得 001100。如果有偶数段1，则110011，花费4，通过查看调试将是startWithOnes = 3，startWithZeroes = 6。请告诉我如何继续以匹配算法。

java

1 个回答

  1. Best Answer
    $ javac Main.java

$ echo 000111 | java Main
0

$ echo 100111 | java Main
2

    在这两个示例中，行相差一个字符，答案相差两个单位。第二个答案是错误的。

    因此，该程序存在错误；解释算法的逻辑是没有用的。

    如果从内部循环中删除语句+=，错误就会消失：

    ------
< 
<                 startWithZeroes += (i % 2 == 0 ? zeros : ones);
<                 startWithOnes += (i % 2 == 0 ? ones : zeros);
<             }
======
> 
>             }
>             startWithZeroes += (i % 2 == 0 ? zeros : ones);
>             startWithOnes += (i % 2 == 0 ? ones : zeros);
------

    通过此更改，算法即可运行。但还是没有效果。您可以给出程序在二次时间内运行的线的示例（长度）。一个好问题就是比正方形更快地解决它。

    PS抱歉，这并不是您问题的答案。而是对问题本身的缺点的解释。

    外循环中具有最小值的PPS程序善于隐藏内循环中的错误。即使这是一个谎言，该程序在大多数情况下仍会继续产生可信的结果。通常，您只能通过编写正确的程序并比较结果来捕获此类错误。

    PPPS不要把时间浪费在别人的代码上，首先研究任务本身。

    • 1

相关问题