資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究透過僅設定一個大小為 K 的子字串的位來最小化二進位制字串中的漢明距離
兩個等長字串之間的漢明距離是在所有位置上，一個字串在對應位置上與另一個字串具有不同值的個數。我們可以透過以下示例來理解這一點：
S = “ramanisgoing” T = “dishaisgoing”
這裡，5 是兩個字串 S 和 T 之間的漢明距離，因為 raman 和 disha 是兩個單詞，它們使字串發生變化以變得相等。
問題陳述
然而，在這個問題中，我們需要找到兩個僅包含二進位制數字的字串之間的漢明距離。一個字串將由使用者提供，例如 S，另一個字串，例如 T，並且最初，我們將假設它只包含“0”位，並且其大小與給定字串的大小相同。我們將得到一個數字“k”，其值將表示一個子字串可以包含的元素個數，這些元素僅包含 1 作為其元素，以便我們將該大小為 k 的子字串放在我們字串 (T) 的任何位置，以最小化兩個子字串 S 和 T 之間的漢明距離。
讓我們嘗試藉助一些示例來理解這個問題。
輸入
S = "100111” K = 5
輸出
3
解釋
由於初始字串 T 將等於“000000”，並且字串 T 將更改為與字串 S 進行比較，以在 k=5 時找到最小漢明距離，如下所示：“111110”和“011111”。
100111 和 000000 將給出 4 作為它們的漢明距離。100111 和 111110 將為我們提供 3 作為它們的漢明距離，而 100111 和 011111 將給出 3 作為它們的漢明距離。
但最小漢明距離將為 3，因為 3 小於 4。因此，3 是我們的答案。
− S = "100101” K = 5 − 3
由於初始字串 T 將等於“000000”，並且字串 T 將更改為與字串 S 進行比較，以在 k=5 時找到最小漢明距離，如下所示：“111110”和“011111”。
100101 和 000000 將給出 3 作為它們的漢明距離。100101 和 111110 將為我們提供 4 作為它們的漢明距離，而 100101 和 011111 將給出 4 作為它們的漢明距離。
但最小漢明距離將為 3，因為 3 小於 4。因此，3 是我們的答案。
問題解釋
讓我們嘗試理解問題並找到它的解決方案。
方法 1：暴力解法
我們將透過更改子字串在不同初始點和結束點的位置來更改字串 T，以便我們可以在所有可能的字串中獲得最小的漢明距離。
示例
以下是各種程式語言中暴力解法的實現：
#include <stdio.h>
#include <string.h>
// Function to get minimum hamming distance through iteration
int helper(char* S, int k) {
// n is the size of the string
int n = strlen(S);
// Take another string T and initiate it with zero bits size equal to that of S
char T[n+1];
memset(T, '0', sizeof(T));
T[n] = '\0';
// Take another string v to initiate it same as T
char v[n+1];
memset(v, '0', sizeof(v));
v[n] = '\0';
// Define mini as the hamming distance between T and S
int mini = 0;
int l = 0;
while (l < n) {
if (S[l] != T[l])
mini++;
l++;
}
for (int i = 0; i < n - k + 1; i++) {
int j = 0, a = 0, l = 0;
// Alter string v by changing bits of size k
while (j < k) {
v[j + i] = '1';
j++;
}
// Calculate hamming distance
while (l < n) {
if (S[l] != v[l])
a++;
l++;
}
// Check if the previous hamming distance is greater than the current hamming distance, if yes, then replace that distance element
if (mini > a) {
mini = a;
}
// Again assign v as the T string
strcpy(v, T);
}
// Return the minimum hamming distance found through the above iterations
return mini;
}
int main() {
// Give input string S
char S[] = "100101";
// Give the value of k that is the substring size
int K = 5;
// Call the helper function
printf("The minimum hamming distance is: %d\n", helper(S, K));
return 0;
}
輸出
The minimum hamming distance is: 3
#include <bits/stdc++.h>
using namespace std;
// Make a function to get minimum hamming distance through iteration
int helper(string S,int k){
// n is the size of the string
int n=S.size();
// Take another string T and initiate it with zero bits size equal to that of S
string T;
for(int i=0; i<n; i++) {
T+="0";
}
// Take another string v to initiate it same as T
string v=T;
// Define mini as the hamming distance between T and S
int mini=0;
int l=0;
while(l<n) {
if(S[l]!=T[l])mini++;
l++;
}
for(int i=0; i<n-k+1; i++) {
int j=0,a=0,l=0;
// alter string v by changing bits of size k
while(j<k) {
v[j+i]='1';
j++;
}
// calculate hamming distance
while(l<n) {
if(S[l]!=v[l])a++;
l++;
}
// Check if the previous hamming distance is greater than the current hamming distance, if yes then replace that distance element
if(mini>a) {
mini=a;
}
// Again assign v as the T string
v=T;
}
// return the minimum hamming distance found through the above iterations
return mini;
}
int main(){
// Give input string S
string S = "100101";
// Give the value of k that is the substring size
int K = 5;
// Call the helper function
cout << "The minimum hamming distance is: "<< helper(S,K);
return 0;
}
輸出
The minimum hamming distance is: 3
public class Main {
// Function to get minimum hamming distance through iteration
static int helper(String S, int k) {
// n is the size of the string
int n = S.length();
// Take another string T and initiate it with zero bits size equal to that of S
StringBuilder T = new StringBuilder();
for (int i = 0; i < n; i++) {
T.append('0');
}
// Take another string v to initiate it same as T
StringBuilder v = new StringBuilder(T);
// Define mini as the hamming distance between T and S
int mini = 0;
int l = 0;
while (l < n) {
if (S.charAt(l) != T.charAt(l))
mini++;
l++;
}
for (int i = 0; i < n - k + 1; i++) {
int j = 0, a = 0;
// Alter string v by changing bits of size k
while (j < k) {
v.setCharAt(j + i, '1');
j++;
}
// Calculate hamming distance
l = 0; // Reinitialize l
while (l < n) {
if (S.charAt(l) != v.charAt(l))
a++;
l++;
}
// Check if the previous hamming distance is greater than the current hamming distance, if yes, then replace that distance element
if (mini > a) {
mini = a;
}
// Again assign v as the T string
v = new StringBuilder(T);
}
// Return the minimum hamming distance found through the above iterations
return mini;
}
public static void main(String[] args) {
// Give input string S
String S = "100101";
// Give the value of k that is the substring size
int K = 5;
// Call the helper function
System.out.println("The minimum hamming distance is: " + helper(S, K));
}
}
輸出
The minimum hamming distance is: 3
def helper(S, k):
n = len(S)
# Take another string T and initiate it with zero bits size equal to that of S
T = '0' * n
# Take another string v to initiate it same as T
v = T
# Define mini as the hamming distance between T and S
mini = 0
l = 0
while l < n:
if S[l] != T[l]:
mini += 1
l += 1
for i in range(n - k + 1):
j, a, l = 0, 0, 0
# Alter string v by changing bits of size k
while j < k:
v = v[:j + i] + '1' + v[j + i + 1:]
j += 1
# Calculate hamming distance
while l < n:
if S[l] != v[l]:
a += 1
l += 1
# Check if the previous hamming distance is greater than the current hamming distance, if yes, then replace that distance element
if mini > a:
mini = a
# Again assign v as the T string
v = T
# Return the minimum hamming distance found through the above iterations
return mini
# Give input string S
S = "100101"
# Give the value of k that is the substring size
K = 5
# Call the helper function
print("The minimum hamming distance is:", helper(S, K))
輸出
The minimum hamming distance is: 3
方法 2：最佳化解法
演算法
使用字首和陣列計算存在的 1 的個數，並將其儲存為我們的最小漢明距離
遍歷 S 字串以查詢字串 S 中 K 個不同子字串之間 1 的值。
如果 (i-1<0) 將值 v 作為 arr[i+K-1]，否則，將值 v 作為 (arr[i+K-1]-arr[i-1])
透過找到先前漢明距離和當前漢明距離之間的最小值來儲存最小值。
當前漢明距離可以透過對來自 K 個子字串的零元素個數 (K - v) 和當前 S 子字串中存在的零元素個數 (cnt - v) 的加法進行操作來找到
最後，返回總的最小距離。
示例
以下是各種程式語言中最佳化解法的實現：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Make a helper function to get minimum hamming distance through iteration
int helper(char *S, int K){
// n is the size of the string
int n = strlen(S);
// initialize an array of size 'n'
int arr[n];
if(S[0]=='0')arr[0]=0;
else arr[0]=1;
// Count the number of 1's in the string S
for (int i = 1; i < n; i++) {
if(S[i]=='0')arr[i]=arr[i-1];
else arr[i]=arr[i-1]+1;
}
int cnt = arr[n - 1];
// Define mini as the hamming distance between T and S
int mini = cnt;
// Traverse through S to find the minimum
for (int i = 0; i < n - K; i++) {
int v;
if(i-1==-1)v=arr[i+K-1];
else v= arr[i+K-1]-arr[i-1];
// Store the minimum
if (cnt - v + (K - v) < mini)
mini = cnt - v + (K - v);
}
// Return the minimum hamming distance
return mini;
}
int main(){
// Give input string S
char *S = "100101";
// Give the value of k that is the substring size
int K = 5;
// Call the helper function
printf("The minimum hamming distance is: %d", helper(S,K));
return 0;
}
輸出
The minimum hamming distance is: 3
#include <bits/stdc++.h>
using namespace std;
// Make a helper function to get minimum hamming distance through iteration
int helper(string S, int K){
// n is the size of the string
int n = S.size();
// initialize an array of size 'n'
int arr[n];
if(S[0]=='0')arr[0]=0;
else arr[0]=1;
// Count the number of 1's in the string S
for (int i = 1; i < n; i++) {
if(S[i]=='0')arr[i]=arr[i-1];
else arr[i]=arr[i-1]+1;
}
int cnt = arr[n - 1];
// Define mini as the hamming distance between T and S
int mini = cnt;
// Traverse through S to find the minimum
for (int i = 0; i < n - K; i++) {
int v;
if(i-1==-1)v=arr[i+K-1];
else v= arr[i+K-1]-arr[i-1];
// Store the minimum
mini = min(mini, cnt - v + (K - v));
}
// Return the minimum hamming distance
return mini;
}
int main(){
// Give input string S
string S = "100101";
// Give the value of k that is the substring size
int K = 5;
// Call the helper function
cout << "The minimum hamming distance is: "<< helper(S,K);
return 0;
}
輸出
The minimum hamming distance is: 3
public class Main {
// Make a helper function to get the minimum hamming distance through iteration
static int helper(String S, int K) {
// n is the size of the string
int n = S.length();
// Initialize an array of size 'n'
int[] arr = new int[n];
if (S.charAt(0) == '0') {
arr[0] = 0;
} else {
arr[0] = 1;
}
// Count the number of 1's in the string S
for (int i = 1; i < n; i++) {
if (S.charAt(i) == '0') {
arr[i] = arr[i - 1];
} else {
arr[i] = arr[i - 1] + 1;
}
}
int cnt = arr[n - 1];
// Define mini as the hamming distance between T and S
int mini = cnt;
// Traverse through S to find the minimum
for (int i = 0; i < n - K; i++) {
int v;
if (i - 1 == -1) {
v = arr[i + K - 1];
} else {
v = arr[i + K - 1] - arr[i - 1];
}
// Store the minimum
mini = Math.min(mini, cnt - v + (K - v));
}
// Return the minimum hamming distance
return mini;
}
public static void main(String[] args) {
// Give input string S
String S = "100101";
// Give the value of K, which is the substring size
int K = 5;
// Call the helper function
System.out.println("The minimum hamming distance is: " + helper(S, K));
}
}
輸出
The minimum hamming distance is: 3
def helper(S, K):
# n is the size of the string
n = len(S)
# Initialize an array of size 'n'
arr = [0] * n
# Initialize the first element of the array based on the first character of S
if S[0] == '0':
arr[0] = 0
else:
arr[0] = 1
# Count the number of 1's in the string S
for i in range(1, n):
if S[i] == '0':
arr[i] = arr[i - 1]
else:
arr[i] = arr[i - 1] + 1
# Calculate the total count of 1's in the string
cnt = arr[n - 1]
# Initialize mini as the total count
mini = cnt
# Traverse through S to find the minimum hamming distance
for i in range(n - K):
v = 0
# Calculate the difference in counts for the sliding window
if i - 1 == -1:
v = arr[i + K - 1]
else:
v = arr[i + K - 1] - arr[i - 1]
# Update mini with the minimum hamming distance
mini = min(mini, cnt - v + (K - v))
# Return the minimum hamming distance
return mini
# Input string S
S = "100101"
# Value of K, which is the substring size
K = 5
# Call the helper function and display the result
print("The minimum hamming distance is:", helper(S, K))
輸出
The minimum hamming distance is: 3
結論
在本文中，為了找到最小漢明距離，我們將首先看到一種樸素的方法，但為了提高其時間複雜度，我們將使用字首和陣列的概念，透過該概念，我們可以在一個迴圈中避免在不同迴圈中重複計數。
更新於： 2024-01-22
瀏覽量 135 次
廣告