主页 / 问题 / 1585419
Accepted
Vr1cK
Asked:2024-06-27 22:04:11 +0000 UTC2024-06-27 22:04:11 +0000 UTC

“选择建筑物的方法数”问题的解决方案如何运作？

  • 772

无论我如何努力，我都无法理解这段代码为何有效，更不用说我无法想象如何得出这样的解决方案。我无法从根本上理解所有操作之间的联系，为什么如果索引 i 的元素等于（例如零），那么从单元数数组到每个位置我们采用索引 i - 1 的元素，并乘以最后一个元素与索引为i的元素的差，其中这个公式有什么逻辑吗？我已经在心里用不同的台词重复了好几次这个循环，但我根本无法从这个词中理解任何逻辑。如果有任何解释，我将非常感激。

    public long NumberOfWays(string s) {
        int n = s.Length;
        int[] count0 = new int[n];
        int[] count1 = new int[n];
        long totalWays = 0;

        for (int i = 0; i < n; i++) {
            if (i > 0) {
                count0[i] = count0[i - 1];
                count1[i] = count1[i - 1];
            }
            if (s[i] == '0') {
                count0[i]++;
            } else {
                count1[i]++;
            }
        }

        for (int j = 1; j < n - 1; j++) {
            if (s[j] == '0') {
                totalWays += count1[j - 1] * (count1[n - 1] - count1[j]);
            } else {
                totalWays += count0[j - 1] * (count0[n - 1] - count0[j]);
            }
        }

        return totalWays;
    }
}

任务本身：给你一个 0 索引的二进制字符串 s，它代表街道上建筑物的类型，其中：

s[i] = '0' 表示第 i 栋大楼是办公室，s[i] = '1' 表示第 i 栋大楼是餐厅。作为一名城市官员，您希望选择 3 座建筑物进行随机检查。然而，为了确保多样性，所选择的建筑物中不能有两个连续的建筑物是同一类型的。

例如，给定 s =“001101”，我们无法选择第 1、第 3 和第 5 栋建筑物，因为这将形成“011”，这是不允许的，因为有两个相同类型的连续建筑物。返回选择 3 座建筑物的有效方式的数量。

массивы

2 个回答

  1. 该解决方案从中间的建筑物开始，迭代三座建筑物的不同组合。如果中间建筑物是办公室（s j = 0），则要检查的第一和第三建筑物应该是餐馆。直到位置j为止选择餐厅的方法有count1[j - 1]。位置j之后选择餐厅的方式有count1[n - 1] - count1[j]。如果将它们相乘，将得到s j = 0条件下所有有效组合的数量。

    中楼-餐厅的处理方式类似。

    如果我们知道如何计算平均位置j的不同检查的数量，我们就知道如何计算一般检查的数量 - 对j求和。

    • 2
  2. Best Answer

    考虑一串 1 和 0。三个元素的有效样本只能有两种类型 -1,0,1和0,1,0

    在每一步中，我们都会查看下一个元素。如果它为零，那么它可能是第一类样本的中心。左边的单位有多少种选择？ count1[j - 1]。右边是剩余的单位(count1[n - 1] - count1[j])。选项总数是这些数字的乘积。同样对于中央单元和count0[]

    PS 请注意，通过删除其中一个数组可以将内存需求减半（毕竟count0[i]=i+1-count1[i]）。或者，您可以完全不需要额外的内存，知道数组的大小和其中的单元数量，并在算法的主要过程中计算剩下的单元。

    • 2

相关问题