Как не пытался не могу понять почему этот код работает, не говоря о том, что не представляю как к такому решению вообще можно прийти. Не могу принципиально понять связи между всеми действиями, почему если элемент с индексом 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;
}
}
Сама задача : You are given a 0-indexed binary string s which represents the types of buildings along a street where:
s[i] = '0' denotes that the ith building is an office and s[i] = '1' denotes that the ith building is a restaurant. As a city official, you would like to select 3 buildings for random inspection. However, to ensure variety, no two consecutive buildings out of the selected buildings can be of the same type.
For example, given s = "001101", we cannot select the 1st, 3rd, and 5th buildings as that would form "011" which is not allowed due to having two consecutive buildings of the same type. Return the number of valid ways to select 3 buildings.