首页 > 其他分享 >leetcode 461. Hamming Distance

leetcode 461. Hamming Distance

时间:2023-05-30 18:03:17浏览次数:50  
标签:Distance return int res 461 ans type leetcode out

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note:
0 ≤ xy < 231.

Example:

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.

解法1:
class Solution(object):
    def hammingDistance(self, x, y):
        """
        :type x: int
        :type y: int
        :rtype: int
        out(0, 0)=0
        out(0, 1)=1
        out(1, 0)=1
        out(1, 1)=0
        out(2, 1)=2
        out(4, 1)=2
        out(0xffffffff, 0)=31?
        1100 & 1011 = 1000
        """
        z = x ^ y
        res = 0
        while z:            
            res += 1
            z = z & (z-1)
        return res

解法2:

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

因为:

>>> bin(12)
'0b1100'
>>> '0b1100'.count('1')
2
>>> 'abcb'.count('b')
2

 

解法3:

We can find the i-th bit (from the right) of a number by dividing by 2 i times, then taking the number mod 2.

Using this, lets compare each of the i-th bits, adding 1 to our answer when they are different.

Code:

ans = 0
while x or y:
  ans += (x % 2) ^ (y % 2)
  x /= 2
  y /= 2
return ans

比较笨拙,其实 (x & 1) ^ (y & 1), x>>1,y>>1 更好!单独判断某位是否为1移位即可,当然用%2也可以。

res = 0
        while x or y:
            res += (x&1) ^ (y&1)
            x = x>>1
            y = y>>1
        return res

 

标签:Distance,return,int,res,461,ans,type,leetcode,out
From: https://blog.51cto.com/u_11908275/6381161

相关文章

  • leetcode 771. Jewels and Stones
    You'regivenstrings J representingthetypesofstonesthatarejewels,and S representingthestonesyouhave. Eachcharacterin Sisatypeofstoneyouhave. Youwanttoknowhowmanyofthestonesyouhavearealsojewels.Thelettersin J areg......
  • leetcode 378. Kth Smallest Element in a Sorted Matrix
    Givenanxnmatrixwhereeachoftherowsandcolumnsaresortedinascendingorder,findthekthsmallestelementinthematrix.Notethatitisthekthsmallestelementinthesortedorder,notthekthdistinctelement.Example:matrix=[[1,5,9......
  • leetcode 617. Merge Two Binary Trees
    Giventwobinarytreesandimaginethatwhenyouputoneofthemtocovertheother,somenodesofthetwotreesareoverlappedwhiletheothersarenot.Youneedtomergethemintoanewbinarytree.Themergeruleisthatiftwonodesoverlap,thensumn......
  • leetcode 257. Binary Tree Paths
    Givenabinarytree,returnallroot-to-leafpaths.Forexample,giventhefollowingbinarytree: 1/\23\5Allroot-to-leafpathsare:["1->2->5","1->3"]#Definitionforabinarytreenode.#classTreeNode(obje......
  • leetcode 202. Happy Number
    Writeanalgorithmtodetermineifanumberis"happy".Ahappynumberisanumberdefinedbythefollowingprocess:Startingwithanypositiveinteger,replacethenumberbythesumofthesquaresofitsdigits,andrepeattheprocessuntilthe......
  • leetcode 671. Second Minimum Node In a Binary Tree
    Givenanon-emptyspecialbinarytreeconsistingofnodeswiththenon-negativevalue,whereeachnodeinthistreehasexactlytwoorzerosub-node.Ifthenodehastwosub-nodes,thenthisnode'svalueisthesmallervalueamongitstwosub-nodes.G......
  • leetcode 409. Longest Palindrome
    Givenastringwhichconsistsoflowercaseoruppercaseletters,findthelengthofthelongestpalindromesthatcanbebuiltwiththoseletters.Thisiscasesensitive,forexample"Aa"isnotconsideredapalindromehere.Note:Assumethelength......
  • leetcode 747. Largest Number At Least Twice of Others
    Inagivenintegerarraynums,thereisalwaysexactlyonelargestelement.Findwhetherthelargestelementinthearrayisatleasttwiceasmuchaseveryothernumberinthearray.Ifitis,returntheindexofthelargestelement,otherwisereturn-1.Ex......
  • leetcode 107. Binary Tree Level Order Traversal II
    Givenabinarytree,returnthebottom-uplevelordertraversalofitsnodes'values.(ie,fromlefttoright,levelbylevelfromleaftoroot).Forexample:Givenbinarytree[3,9,20,null,null,15,7],3/\920/\157returnits......
  • leetcode 674. Longest Continuous Increasing Subsequence
    Givenanunsortedarrayofintegers,findthelengthoflongestcontinuousincreasingsubsequence(subarray).Example1:Input:[1,3,5,4,7]Output:3Explanation:Thelongestcontinuousincreasingsubsequenceis[1,3,5],itslengthis3.Eventhough[1,3,5......