LeetCode
題目： 漢明距離
兩個(gè)整數(shù)之間的漢明距離指的是這兩個(gè)數(shù)字對(duì)應(yīng)二進(jìn)制位不同的位置的數(shù)目强挫。
給出兩個(gè)整數(shù) x 和 y，計(jì)算它們之間的漢明距離隆判。
注意：
0 ≤ x, y < 231.
示例:
輸入: x = 1, y = 4
輸出: 2
解釋:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
上面的箭頭指出了對(duì)應(yīng)二進(jìn)制位不同的位置犬庇。
方案一：最先印入腦海的方法----10進(jìn)制轉(zhuǎn)2進(jìn)制然后一一對(duì)比，那10進(jìn)制怎么轉(zhuǎn)2進(jìn)制侨嘀？
參考百度百科：10進(jìn)制轉(zhuǎn)2進(jìn)制
代碼一：
func hammingDistance(_ x: Int, _ y: Int) -> Int {
//初始化兩個(gè)空數(shù)組來(lái)裝各自對(duì)應(yīng)的二進(jìn)制
var dicX = [Int]()
var dicY = [Int]()
//將x,y改成可變的
var x = x
var y = y
if (x == 0) {
dicX.append(0)
}
if (y == 0) {
dicY.append(0)
}
//對(duì)2求余將10進(jìn)制轉(zhuǎn)換為2進(jìn)制
while x != 0 {
dicX.append(x%2)
x /= 2
}
while y != 0 {
dicY.append(y%2)
y /= 2
}
print(dicX)
print(dicY)
//區(qū)分長(zhǎng)短是為了方便后面對(duì)比
let short = dicX.count <= dicY.count ? dicX:dicY
let long = dicX.count <= dicY.count ? dicY:dicX
var count = 0
var index = 0
//一一對(duì)比
for i in 0..<short.count {
if short[i] != long[i] {
count += 1
}
index = i
}
// 統(tǒng)計(jì)長(zhǎng)的數(shù)組中 長(zhǎng)出來(lái)那部分的1的個(gè)數(shù)
if long.count > short.count {
for i in index+1..<long.count {
if long[i] == 1 {
count += 1
}
}
}
return count
}
執(zhí)行用時(shí)：36ms
這個(gè)方法是蠢了點(diǎn)臭挽、、咬腕、但是我也不怕寫(xiě)出來(lái)欢峰、、、這畢竟也算是一個(gè)正常的思路
方案二：位運(yùn)算：按位異或+右移運(yùn)算
參考百度百科：位運(yùn)算
x 和 y 異或得到的就是一個(gè)包含所求漢明距離的一個(gè)數(shù)赤赊，此時(shí)用右移運(yùn)算去做統(tǒng)計(jì)
代碼二：
func hammingDistance(_ x: Int, _ y: Int) -> Int {
var num : Int = x ^ y
var sum : Int = 0
while (num > 0) {
sum += num & 1 == 1 ? 1 : 0
num = num >> 1
}
return sum
}
