数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究计算从二进制字符串中选择三个索引的方法，要求相邻数字不同
在这个问题中，我们将找到3个索引对的数量，这样在每一对中，任何相邻的索引的值都不相同。
我们可以通过检查每一对3个索引来获得输出，但这可能更耗时。解决这个问题的另一种方法是取当前索引，并取左侧和右侧的索引，这些索引不包含与当前索引值相同的值。这样，我们可以计算每个索引可以形成的总对数，并将它们相加以获得输出。
问题陈述 − 我们给定一个二进制字符串bin_str，需要找到3个索引对的数量（按递增顺序），使得相邻索引不包含相同的值。
示例
输入
bin_str = "0101";
输出
2
解释
我们可以取{0, 1, 2}和{1, 2, 3}索引对。因此，在010和101字符串中，任何两个相邻字符都不相同。
输入
bin_str = "110001";
输出
6
解释
我们可以取{0, 2, 5}，{0, 3, 5}，{0, 4, 5}，{1, 2, 5}，{1, 3, 5}和{1, 4, 5}。
输入
bin_str = “11111”
输出
0
解释
由于字符串的所有字符都相同，因此它不包含任何所需的索引对。
方法1
在这种方法中，我们将使用三个嵌套循环来查找3个索引对，以便相邻索引不包含相同的值。我们将检查每一对是否符合问题陈述中给出的条件。
算法
步骤1 − 将‘ans’初始化为0，以存储所需对的数量。
步骤2 − 使用第一个循环遍历从第0个索引到二进制字符串长度-3索引的字符串。
步骤3 − 使用嵌套循环从(p + 1)索引遍历到二进制字符串长度-2索引。
步骤4 − 使用另一个嵌套循环从(q + 1)索引遍历到二进制字符串长度-1索引。
步骤5 − 在嵌套循环中，如果p和q索引处的字符不相等，并且q和r索引处的字符不相等，则将‘ans’的值加1。
步骤6 − 返回‘ans’的值。
示例
以下是上述算法的示例：
#include <stdio.h>
#include <string.h>
long long findIndexSelection(char* bin_str) {
int bin_len = strlen(bin_str);
long long ans = 0;
// Creating the pair of 3 indexes
for (int p = 0; p < bin_len - 2; p++) {
for (int q = p + 1; q < bin_len - 1; q++) {
for (int r = q + 1; r < bin_len; r++) {
// Check whether adjacent characters are not the same
if (bin_str[p] != bin_str[q] && bin_str[q] != bin_str[r]) {
ans++;
}
}
}
}
// Final output
return ans;
}
int main() {
char bin_str[] = "0101";
printf("The maximum number of ways to select indexes such that two adjacent indexes don't have the same character is %lld\n", findIndexSelection(bin_str));
return 0;
}
输出
The maximum number of ways to select indexes such that two adjacent indexes don't have the same character is 2
#include <bits/stdc++.h>
using namespace std;
long long findIndexSelection(string bin_str) {
int bin_len = bin_str.size();
int ans = 0;
// Creating the pair of 3 indexes
for (int p = 0; p < bin_len - 2; p++) {
for (int q = p + 1; q < bin_len - 1; q++) {
for (int r = q + 1; r < bin_len; r++) {
// Check whether adjacent characters are the same or not
if (bin_str[p] != bin_str[q] && bin_str[q] != bin_str[r]) {
ans++;
}
}
}
}
// Final output
return ans;
}
int main() {
string bin_str = "0101";
cout << "The maximum number of ways to select indexes such that two adjacent indexes don't have the same character is " << findIndexSelection(bin_str) << endl;
return 0;
}
输出
The maximum number of ways to select indexes such that two adjacent indexes don't have the same character is 2
public class Main {
public static long findIndexSelection(String binStr) {
int binLen = binStr.length();
long ans = 0;
// Creating the pair of 3 indexes
for (int p = 0; p < binLen - 2; p++) {
for (int q = p + 1; q < binLen - 1; q++) {
for (int r = q + 1; r < binLen; r++) {
// Check whether adjacent characters are not the same
if (binStr.charAt(p) != binStr.charAt(q) && binStr.charAt(q) != binStr.charAt(r)) {
ans++;
}
}
}
}
// Final output
return ans;
}
public static void main(String[] args) {
String binStr = "0101";
System.out.println("The maximum number of ways to select indexes such that two adjacent indexes don't have the same character is " + findIndexSelection(binStr));
}
}
输出
The maximum number of ways to select indexes such that two adjacent indexes don't have the same character is 2
def find_index_selection(bin_str):
bin_len = len(bin_str)
ans = 0
# Creating the pair of 3 indexes
for p in range(bin_len - 2):
for q in range(p + 1, bin_len - 1):
for r in range(q + 1, bin_len):
# Check whether adjacent characters are not the same
if bin_str[p] != bin_str[q] and bin_str[q] != bin_str[r]:
ans += 1
return ans
if __name__ == "__main__":
bin_str = "0101"
print("The maximum number of ways to select indexes such that two adjacent indexes don't have the same character is", find_index_selection(bin_str))
输出
The maximum number of ways to select indexes such that two adjacent indexes don't have the same character is 2
时间复杂度 − O(N*N*N)，因为我们使用了三个嵌套循环。
空间复杂度 − O(1)，因为我们没有使用任何动态空间。
方法2
如果我们想使用当前索引组成一对，我们需要取一个左侧索引和一个右侧索引，因为我们需要按递增顺序选择索引。因此，我们可以取左侧和右侧的所有索引，这些索引不包含与当前索引相同的字符。
我们可以使用当前索引构造的对数如下所示。
Pairs = (number of left indexes have dissimilar value) * (number of right indexes have dissimilar value)
之后，我们可以将使用每个索引可以构造的对数相加。
算法
步骤1 − 初始化‘cnt1’和‘cnt0’变量，以存储给定二进制字符串中0和1的计数。
步骤2 − 遍历字符串并更新0和1的计数。
步骤3 − 将‘ans’初始化为0，以存储总对数。
步骤4 − 遍历字符串以查找总有效对数。
步骤5 − 如果当前字符是‘0’，则将(ones* (cnt1 - ones))添加到‘ans’。我们取左侧和右侧1的乘积，这形成了像101这样的对。同时，将‘zeros’加1。
步骤6 − 如果当前字符是‘1’，则将(zeros * (cnt0 – zeros))添加到‘ans’。它形成了像010这样的字符串。接下来，将‘ones’加1。
步骤7 − 返回‘ans’的值。
示例
以下是上述算法的示例：
#include <stdio.h>
#include <string.h>
long long findIndexSelection(char* bin_str) {
int bin_len = strlen(bin_str);
// Counting the number of zeros and ones
int cnt0 = 0, cnt1 = 0;
// To store zeros and ones till ith index
int zeros = 0, ones = 0;
// Traverse the string to count 0's and 1's
for (int p = 0; p < bin_len; p++) {
if (bin_str[p] == '0') {
cnt0++;
} else {
cnt1++;
}
}
// To store the maximum number of pairs
long long ans = 0;
// Finding pairs
for (int p = 0; p < bin_len; p++) {
if (bin_str[p] == '0') {
// Getting the number of pairs that can be formed with the current index
ans += (ones * (cnt1 - ones));
// Increase zeros
zeros++;
} else {
// Getting the number of pairs that can be formed with the current index
ans += (zeros * (cnt0 - zeros));
ones++;
}
}
return ans;
}
int main() {
char bin_str[] = "1010";
printf("The maximum number of ways to select indexes such that two adjacent indexes don't have the same character is %lld\n", findIndexSelection(bin_str));
return 0;
}
输出
The maximum number of ways to select indexes such that two adjacent indexes don't have the same character is 2
#include <bits/stdc++.h>
using namespace std;
long long findIndexSelection(string bin_str) {
int bin_len = bin_str.size();
// Counting the number of zeros and ones
int cnt0 = 0, cnt1 = 0;
// To store zeros and ones till ith index
int zeros = 0, ones = 0;
// Traverse the string to count 0's and 1's
for (int p = 0; p < bin_len; p++) {
if (bin_str[p] == '0') {
cnt0++;
} else {
cnt1++;
}
}
// To store the maximum number of pairs
long long ans = 0;
// Finding pairs
for (int p = 0; p < bin_len; p++) {
if (bin_str[p] == '0') {
// Getting the number of pairs can be formed with a current index
ans += (ones * (cnt1 - ones));
// Increase zeros
zeros++;
} else {
// Getting the number of pairs can be formed with a current index
ans += (zeros * (cnt0 - zeros));
ones++;
}
}
return ans;
}
int main() {
string bin_str = "1010";
cout << "The maximum number of ways to select indexes such that two adjacent indexes don't have the same character is " << findIndexSelection(bin_str) << endl;
return 0;
}
输出
The maximum number of ways to select indexes such that two adjacent indexes don't have the same character is 2
public class Main {
public static long findIndexSelection(String binStr) {
int binLen = binStr.length();
// Counting the number of zeros and ones
int cnt0 = 0, cnt1 = 0;
// To store zeros and ones till ith index
int zeros = 0, ones = 0;
// Traverse the string to count 0's and 1's
for (int p = 0; p < binLen; p++) {
if (binStr.charAt(p) == '0') {
cnt0++;
} else {
cnt1++;
}
}
// To store the maximum number of pairs
long ans = 0;
// Finding pairs
for (int p = 0; p < binLen; p++) {
if (binStr.charAt(p) == '0') {
// Getting the number of pairs that can be formed with the current index
ans += (ones * (cnt1 - ones));
// Increase zeros
zeros++;
} else {
// Getting the number of pairs that can be formed with the current index
ans += (zeros * (cnt0 - zeros));
ones++;
}
}
return ans;
}
public static void main(String[] args) {
String binStr = "1010";
System.out.println("The maximum number of ways to select indexes such that two adjacent indexes don't have the same character is " + findIndexSelection(binStr));
}
}
输出
The maximum number of ways to select indexes such that two adjacent indexes don't have the same character is 2
def find_index_selection(bin_str):
bin_len = len(bin_str)
# Counting the number of zeros and ones
cnt0 = 0
cnt1 = 0
# To store zeros and ones till ith index
zeros = 0
ones = 0
# Traverse the string to count 0's and 1's
for p in range(bin_len):
if bin_str[p] == '0':
cnt0 += 1
else:
cnt1 += 1
# To store the maximum number of pairs
ans = 0
# Finding pairs
for p in range(bin_len):
if bin_str[p] == '0':
# Getting the number of pairs that can be formed with the current index
ans += (ones * (cnt1 - ones))
# Increase zeros
zeros += 1
else:
# Getting the number of pairs that can be formed with the current index
ans += (zeros * (cnt0 - zeros))
ones += 1
return ans
if __name__ == "__main__":
bin_str = "1010"
print("The maximum number of ways to select indexes such that two adjacent indexes don't have the same character is", find_index_selection(bin_str))
输出
The maximum number of ways to select indexes such that two adjacent indexes don't have the same character is 2
时间复杂度 – O(N) 用于遍历字符串。
空间复杂度 – O(1)，因为我们没有使用任何动态空间。
我们学习了朴素方法和优化方法来解决这个问题。第一种方法的时间复杂度很高，不能用于大型输入。第二种方法使用1和0的前缀的概念来解决问题。
更新于：2023年10月16日
浏览量 101
广告