# 2020q3 Homework4 (quiz4) contributed by < `johnnycck` > ## 測驗一 此題需要完成可以實作出兩整數的 Hamming distance。 ```cpp int hammingDistance(int x, int y) { return __builtin_popcount(x OP y); } ``` * ans: OP = ^,因為要算 Hamming Distance,使用 ^ ,兩者相異才會顯示出來,再透過 __builtin_popcount( ),得到有幾個 '1',及是 Hamming Distance。 :::success 延伸問題: 練習 LeetCode 477. Total Hamming Distance,你應當提交 (submit) 你的實作 (C 語言實作),並確保執行結果正確且不超時 ::: * 我試圖提交上面程式碼的延伸,但卻得到 TLE (Time Limit Exceeded) ```c= int hammingDistance(int x, int y) { return __builtin_popcount(x ^ y); } int totalHammingDistance(int* nums, int numsSize){ int ans=0; for(int i=0; i<numsSize; i++) { for(int j=i+1; j<numsSize; j++) { ans += hammingDistance(*(nums+i),*(nums+j)); } } return ans; } ``` * 經過嘗試後,發現寫不出來,因此去看別人的 discussion,我參考了其中一個解答 ```c= int totalHammingDistance(int* nums, int numsSize) { /* record each bit 1's number, each bits total hamming distance: countone*(numsSize - countone) */ int count_one = 0; int number = 0; /*32(can decrease to least 30) bits is enough to repreent 10^9*/ for(int i = 0;i < 30;i++) { /*init count_one of each bits*/ count_one = 0; for(int j = 0;j < numsSize;j++) { if(nums[j]&1 == 1) { count_one++; } nums[j] = nums[j] >> 1; } number = number + count_one * (numsSize - count_one); } return number; } ``` * 解釋程式碼流程: 1. 他的解法是一次比對同一個 Bit Position 的全部 input,假設 input 是 4, 14, 2,以二進為表示就是 * | Input \ Bit Position | 3 | 2 | 1 |0 | | -------- | -------- | -------- |-------- |-------- | |4| 0 | 1 | 0 |0 | |14| 1 | 1 | 1 |0 | |2| 0 | 0 | 1 | 0 | 2. 先比對 Position 0,把有 '1' 的個數跟有 '0' 的個數相乘,最後再將每個 Position 的答案相加 (i 設為 32 是因為 input 最大是 10^9,不過 30 其實就可以表達 10^9) 1. 以此題為例,可以得到 2 + 2 + 2 + 0 * 原先我的思考流程就是要將所有的 input 都相互比過一次,但這樣時間複雜度會是 O(N^2),較佳的解法是以 position 的方式,將每個 input 的同一個 position 比對過,再相加起來,而這個動作可以由 '1' 的個數跟 '0' 的個數相乘得到,這是因為 '1' 的個數代表同一個 '0' 會跟幾個 1 產生 hamming distance,而 '0' 的個數就代表有幾個前述的 '0',所以相乘就會是某個 position 的總 hamming distance
×
Sign in
Email
Password
Forgot password
or
By clicking below, you agree to our
terms of service
.
Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
Wallet (
)
Connect another wallet
New to HackMD?
Sign up