微营销的方式有哪些_线上编程_沈阳网站关键词优化公司_搜狗官网

Hamming Distance（汉明距离）是用于衡量两个等长字符串在相同位置上不同字符的个数的度量。它通常用于比较两个二进制字符串或编码序列的差异。

定义

给定两个长度相同的字符串 $A$ 和 $B$，它们的汉明距离 $D(A,B)$ 是在相同位置上字符不同的位置的数量。

示例

1. 二进制字符串：
   • A=1011101
   • B=1001001
   • 汉明距离 $D(A,B)=2$（第3位和第5位不同）。
2. 字符串：
   • A=“karolin”
   • B=“kathrin”
   • 汉明距离 $D(A,B)=3$（第3、4、5位不同）。

应用

• 错误检测与纠正：在通信和编码理论中，汉明距离用于检测和纠正数据传输中的错误。
• 生物信息学：用于比较 DNA 序列的相似性。
• 机器学习：在分类算法中，用于计算样本之间的距离。

计算步骤

• 比较两个字符串的每一位。
• 统计不同位的数量。
• 返回统计结果作为汉明距离。

公式

对于长度为 $n$ 的两个字符串 $A$ 和 $B$，汉明距离为：
$$D(A,B)=\sum _{i=1}^n\delta (A_i,B_i)$$
其中，$\delta (A_i,B_i)$ 是指示函数，当 $A_i\ne B_i$ 时为1，否则为0。

461. Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Given two integers x and y, return the Hamming distance between them.

Example 1:

Input: x = 1, y = 4
Output: 2
Explanation:
1   (0 0 0 1)
4   (0 1 0 0)↑   ↑
The above arrows point to positions where the corresponding bits are different.

Example 2:

Input: x = 3, y = 1
Output: 1

C++ 实现

int totalHammingDistance(vector<int>& nums) {int total = 0; // 总汉明距离int n = nums.size(); // 数组长度// 遍历每一位（0到31）for (int i = 0; i < 32; i++) {int count = 0; // 统计当前位为1的数的个数for (int num : nums) {// 检查当前位是否为1if ((num >> i) & 1) {count++;}}// 当前位的贡献为 count * (n - count)total += count * (n - count);}return total;
}

复杂度分析

• 时间复杂度：$O(n\cdot 32)=O(n)$，其中 $n$ 是数组的长度。
• 空间复杂度：$O(1)$，只使用了常数空间。