[LeetCode] Number of 1 Bits & Reverse Integer - 整數問題系列

目錄：

1.Number of 1 Bits  - 計算二進制1的個數 [與運算]

2.Contains Duplicate - 是否存在重複數字 [周遊]

3.Reverse Integer - 翻轉整數 [int邊界問題]

4.Excel Sheet Column Number - Excel字元串轉整數 [簡單]

5.Power of Two & Happy Number - 計算各個位數字 [%10 /10]

題目概述：

For example, the 32-bit integer ’11' has binary representation 

<code>00000000000000000000000000001011</code>so the function should return 3.

解題方法：

三種方法包括：

        1.依次和0x1進行&amp;與運算，若結果為1則加1，表示1個數，再右移；

        2.推薦的方法，n&amp;(n-1)，直到為0，次數為1的個數；

        3.n取2模，依次判斷個位是否為1，在n/2移位，正常方法。

Power of Two題目也可以通過return (n &gt; 0) &amp;&amp; (!(n &amp; (n - 1)))一句話實作。

Reverse Bits題目也可以&lt;&lt;移位實作。

我的代碼：

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the

array, and it should return false if every element is distinct.

題目解析：

題目是給定一個整數數組，判斷該數組中是否存在重複的數字。簡單AC的方法比較簡單，兩層循環判斷；但是如果要求是O(n)的時間和O(1)的空間，怎樣實作呢？騰訊的筆試題就考到了。又見重複判斷II III題。

推薦代碼：

Reverse digits of an integer.

Example1: x

= 123, return 321

Example2: x

= -123, return -321

解題思路：

該題主要是考察整數的翻轉問題，最簡單的方法就是：通過"%10"計算個位數字和"/10"循環進行，直到整數為結果0；但是你需要注意的是：

        1.負數的轉換x=x*(-1)

        2.整數越界，int型範圍是(-2147483648~2147483647)，4位元組。當x=1534236469時，應該輸出0而不是9646324351或溢出後的數

        3.需要注意一個特殊的用例：x=-2147483648。此時x=x*(-1)=2147483648溢出，結果應是0。

故此處需要把整數範圍的判斷指定出來講解，沒考慮整數溢出的代碼如下：

正确代碼：

重點是類似于Java的Integer.MAX_VALUE 這種直接可用的數值型的最大值定義，C語言采用#include &lt;limits.h&gt;裡面的INT_MIN和INT_MAX，而不是寫一長串數字。

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

該類題目比較簡單，主要考察字元串周遊和整數進制問題(26進制)，自己一次AC。

判斷數字是否是2的次數數

判斷數字是否是happy數，結果為1則傳回true

Example: 19 is a happy number

        1^2 + 9^2 = 82

        8^2 + 2^2 = 68

        6^2 + 8^2 = 100

        1^2 + 0^2 + 0^2 = 1

主要考察計算數字每個位數的方法，即n%10和n=n/10的方法。

Power of Two

強推位操作判斷16=10000即高位為1其他為0，或通過一句話即可： 

return (n &gt;0)

&amp;&amp; (!(n &amp; (n -1)))

<a target="_blank" href="http://www.bubuko.com/infodetail-953320.html">http://www.bubuko.com/infodetail-953320.html</a>

Happy Number

PS：最後希望文章對您有所幫助，這都是自己A題的一些筆記和心得，同時真心建議你自己動手做做LeetCode。以前我也不信邪，現在信了~