摘要:移位法復雜度時間空間思路最簡單的做法,原數不斷右移取出最低位,賦給新數的最低位后新數再不斷左移。代碼分段相或法復雜度時間空間思路標準的源碼。更好的優化方法是將其按照分成段存儲,節省空間。
Reverse Bits
移位法 復雜度Reverse bits of a given 32 bits unsigned integer.
For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).
Follow up: If this function is called many times, how would you optimize it?
時間 O(1) 空間 O(1)
思路最簡單的做法,原數不斷右移取出最低位,賦給新數的最低位后新數再不斷左移。
代碼public class Solution { // you need treat n as an unsigned value public int reverseBits(int n) { int res = 0; for(int i = 0; i < 32; i++, n >>= 1){ res = res << 1 | (n & 1); } return res; } }分段相或法 復雜度
時間 O(1) 空間 O(1)
思路Java標準的Integer.reverse()源碼。
代碼public class Solution { // you need treat n as an unsigned value public int reverseBits(int i) { i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555; i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333; i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f; i = (i << 24) | ((i & 0xff00) << 8) | ((i >>> 8) & 0xff00) | (i >>> 24); return i; } }后續 Follow Up
Q:如果該方法被大量調用,或者用于處理超大數據(Bulk data)時有什么優化方法?
A:這其實才是這道題的精髓,考察的大規模數據時算法最基本的優化方法。其實道理很簡單,反復要用到的東西記下來就行了,所以我們用Map記錄之前反轉過的數字和結果。更好的優化方法是將其按照Byte分成4段存儲,節省空間。參見這個帖子。
// cache private final Mapcache = new HashMap (); public int reverseBits(int n) { byte[] bytes = new byte[4]; for (int i = 0; i < 4; i++) // convert int into 4 bytes bytes[i] = (byte)((n >>> 8*i) & 0xFF); int result = 0; for (int i = 0; i < 4; i++) { result += reverseByte(bytes[i]); // reverse per byte if (i < 3) result <<= 8; } return result; } private int reverseByte(byte b) { Integer value = cache.get(b); // first look up from cache if (value != null) return value; value = 0; // reverse by bit for (int i = 0; i < 8; i++) { value += ((b >>> i) & 1); if (i < 7) value <<= 1; } cache.put(b, value); return value; }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/66161.html
摘要:在線網站地址我的微信公眾號完整題目列表從年月日起,每天更新一題,順序從易到難,目前已更新個題。這是項目地址歡迎一起交流學習。 這篇文章記錄我練習的 LeetCode 題目,語言 JavaScript。 在線網站:https://cattle.w3fun.com GitHub 地址:https://github.com/swpuLeo/ca...我的微信公眾號: showImg(htt...
摘要:月下半旬攻略道題,目前已攻略題。目前簡單難度攻略已經到題,所以后面會調整自己,在刷算法與數據結構的同時,攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題,目前已攻略 100 題。 一 目錄 不折騰的前端,和咸魚有什么區別...
摘要:微信公眾號記錄截圖記錄截圖目前關于這塊算法與數據結構的安排前。已攻略返回目錄目前已攻略篇文章。會根據題解以及留言內容,進行補充,并添加上提供題解的小伙伴的昵稱和地址。本許可協議授權之外的使用權限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一 目錄 不...
摘要:思路一比特位移動將比特位逆轉過來也就是將十進制數轉化為二進制數,再從右往左獲得每一位上的值,再將這個值添加至結果值中。根據分治思想,逆轉個比特位等價于分別將每個比特位進行逆轉。 題目要求 Reverse bits of a given 32 bits unsigned integer. For example, given input 43261596 (represented in...
摘要:思路一比特位移動將比特位逆轉過來也就是將十進制數轉化為二進制數,再從右往左獲得每一位上的值,再將這個值添加至結果值中。根據分治思想,逆轉個比特位等價于分別將每個比特位進行逆轉。 題目要求 Reverse bits of a given 32 bits unsigned integer. For example, given input 43261596 (represented in...
閱讀 3686·2021-09-07 10:19
閱讀 3627·2021-09-03 10:42
閱讀 3584·2021-09-03 10:28
閱讀 2548·2019-08-29 14:11
閱讀 809·2019-08-29 13:54
閱讀 1594·2019-08-29 12:14
閱讀 417·2019-08-26 12:12
閱讀 3614·2019-08-26 10:45