ETH官方钱包

前往
大廳
主題

LeetCode - 1342. Number of Steps to Reduce a Number to Zero 解題心得

Not In My Back Yard | 2021-04-13 00:00:16 | 巴幣 0 | 人氣 273

題目連結:


題目意譯:
給定一個非負整數 num,回傳要將該數變為 0 所需的步驟數。如果目前數字為偶數,則你可以將該數除以 2;反之,你需要將其減 1。

限制:
0 ≦ num ≦ 10 ^ 6



範例測資:
範例 1:
輸入: num = 14
輸出: 6
解釋:
步驟 1) 14 為偶數; 除以 2 得到 7。
步驟 2) 7 為奇數; 減去 1 得到 6。
步驟 3) 6 為偶數; 除以 2 得到 3。
步驟 4) 3 為奇數; 減去 1 得到 2。
步驟 5) 2 為偶數; 除以 2 得到 1。
步驟 6) 1 為奇數; 減去 1 得到 0。

範例 2:
輸入: num = 8
輸出: 4
解釋:
步驟 1) 8 為偶數; 除以 2 得到 4。
步驟 2) 4 為偶數; 除以 2 得到 2。
步驟 3) 2 為偶數; 除以 2 得到 1。
步驟 4) 1 為奇數; 減去 1 得到 0。

範例 3:
輸入: num = 123
輸出: 12


解題思維:
不難看出所求 = (位數 - 1) + (1 的數量),其中的位數是指 num 用二進位制表示時(且除了數字 0 本身以外沒有任何前導 0)的位數長。而 1 的數量也同理,指的是二進位制下有多少位數為 1。

而上面的值可以藉由掃過 num 的位元「一次」便可以統計出來(掃過的方式可以參見這題)。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作