首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >20190503-汉明距离

20190503-汉明距离

作者头像
py3study
发布2020-01-16 14:50:59
3570
发布2020-01-16 14:50:59
举报
文章被收录于专栏:python3python3

难度分类

简单

题目描述

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。给出两个整数 x 和 y,计算它们之间的汉明距离

注意:

0 ≤ x, y < 231.

示例:

输入: x = 1, y = 4

输出: 2

解释:

1   (0 0 0 1)

4   (0 1 0 0)

       ↑   ↑

上面的箭头指出了对应二进制位不同的位置。

算法

1. 获取x,y的二进制的字符串

2. 使用zfill函数将x,y的二进制字符串中较短的字符串的长度用‘0’填充成与较长位字符串长度一样长

3. 使用zip函数一一遍历对比

考点

  1. 十进制与二进制的转换bin函数
  2. Zfill函数
  3. zip函数

代码

def hammingDistance(self, x, y):
        #step1:转换二进制
        binary_x = bin(x)[2:]
        binary_y = bin(y)[2:]
        #step2:调整长度
        if len(binary_x)>len(binary_y):
            binary_y = binary_y.zfill(len(binary_x))
        else:
            binary_x = binary_x.zfill(len(binary_y))
        result=0
        #step3:按位对比,统计不同的位数
        for i,j in zip(binary_x,binary_y):
            if i!=j:
                result+=1

进阶算法

统计二进制位不同的可使用二进制异或运算,然后统计结果二进制的1的个数。异或运算即二进制下不进位加法,二进制的异或运算法则如下:

1. 0+0=0

2. 0+1=1

3. 1+0=1

4. 1+1=0

示例中0001^0100=0101,统计0101中1的个数即为二进制位不同的总数

进阶考点

  1. 异或运算
  2. str.count()函数

进阶代码

def hammingDistance(self, x, y):
        """
        :type x: int
        :type y: int
        :rtype: int
        """
        return bin(x^y).count('1')

附-十进制转换二进制代码

 def binary_transfer(x):
            result = ''
            while x!=0:
                result+=str(x%2)
                x = x//2
            return result[::-1]
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2019-06-01 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 难度分类
  • 题目描述
  • 算法
  • 考点
  • 代码
  • 进阶算法
  • 进阶考点
  • 进阶代码
  • 附-十进制转换二进制代码
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档