溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
小編給大家分享一下leetcod如何實現比特位計數，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！
給定一個非負整數 num。對于 0 ≤ i ≤ num 范圍中的每個數字 i ，計算其二進制數中的 1 的數目并將它們作為數組返回。
示例 1:
輸入: 2
輸出: [0,1,1]
示例 2:
輸入: 5
輸出: [0,1,1,2,1,2]
進階:
給出時間復雜度為O(n*sizeof(integer))的解答非常容易。但你可以在線性時間O(n)內用一趟掃描做到嗎？
要求算法的空間復雜度為O(n)。
你能進一步完善解法嗎？要求在C++或任何其他語言中不使用任何內置函數（如 C++ 中的 __builtin_popcount）來執行此操作。
動態規劃，i>>1指的是i右移一位，這樣的話i的最低位會被去掉，因此i與i>>1相當于比較最后一位是否為1；
當 i 的最低位為0，則 i 和i >> 1中1的個數是一樣的，因為0不算進計算1的個數；
否則，最低位為1，1相當于被抹掉了，因此 i >> 1中1的個數加1就是i 中1的個數；
class Solution: def countBits(self, num: int) -> list: dp = [0 for _ in range(num + 1)] for i in range(num + 1): i_last_num = i & 1 # 得到i的末位數字 if i_last_num == 0: dp[i] = dp[i >> 1] else: dp[i] = dp[i >> 1] + i_last_num return dp if __name__ == '__main__': s = Solution() num = 5 ans = s.countBits(num) print(ans)
以上是“leetcod如何實現比特位計數”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
