資料結構
網路
關係資料庫管理系統 (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
廣告