LeetCode解題鏈接
7. Reverse Integer
Reverse digits of an integer.
Example1: x = 123, return 321
Example2: x = -123, return -321
click to show spoilers.
Note:
The input is assumed to be a 32-bit signed integer. Your function should return 0 when the reversed integer overflows.
思路
要考慮的問題：
- 負(fù)數(shù)
- 溢出
對于溢出問題，因為是int型榴捡，在計算的過程中血柳，我們只需要將計算的臨時變量定義成long即可虎锚！這樣在判斷溢出時會非常簡單覆糟。
代碼
public class Solution {
public int reverse(int x) {
long ans = 0;
while(x != 0) {
ans = ans * 10 + x % 10;
x /= 10;
if(ans > Integer.MAX_VALUE || ans < Integer.MIN_VALUE)
return 0;
}
return (int)ans;
}
}
231. Power of Two
Given an integer, write a function to determine if it is a power of two.
思路
- 可以根據(jù)
(n & (n - 1)) == 0來判斷猛遍，這是因為2的冪僅有1位是1，其余位全部是0而晒；如果-1蝇狼，那么1的那位會變成0，后面的位全部為1倡怎。 - 可以根據(jù)
(n & -n) == n來判斷，這是 JDK 中 Ingeger 中使用的判斷方法贱枣。因為 -n 的二進(jìn)制表示监署，恰好相當(dāng)于（n - 1）取反，而符號位本來就是不同的纽哥。本質(zhì)上和上一種解放是一樣的钠乏。
代碼
代碼1：
public class Solution {
public boolean isPowerOfTwo(int n) {
if(n <= 0) return false;
return (n & (n - 1)) == 0;
}
}
代碼2：
public class Solution {
public boolean isPowerOfTwo(int n) {
if(n <= 0) return false;
return (n & -n) == n;
}
}
326. Power of Three
Given an integer, write a function to determine if it is a power of three.
Follow up:
Could you do it without using any loop / recursion?
思路
如果n是3的冪，那么 n % 3 == 0
代碼
public class Solution {
public bool IsPowerOfThree(int n) {
// 1162261467 是小于 Integer.MAX_VALUE 的3的最大冪數(shù)
return n > 0 && (1162261467 % n == 0);
}
}
342. Power of Four
Given an integer (signed 32 bits), write a function to check whether it is a power of 4.
Example:
Given num = 16, return true. Given num = 5, return false.
Follow up: Could you solve it without loops/recursion?
思路
可以和上一題：Power of Three一樣春塌，使用作弊的方法……但是這道題顯然是根Power of Two有關(guān)晓避。思考一下，4的冪相對于2的冪只壳，有哪些特點呢俏拱？
答案就是：在2的冪的基礎(chǔ)上，位數(shù)為1的位置僅出現(xiàn)在奇數(shù)的位置上吼句，例如
- 0000 0001 = 1锅必，是4的冪
- 0000 0010 = 2，不是4的冪
- 0000 0100 = 4惕艳，是4的冪
那么如何判斷位數(shù)為1的位置僅出現(xiàn)在奇數(shù)的位置上呢搞隐？與上0x55（0101 0101）就好了驹愚！
代碼
public class Solution {
public boolean isPowerOfFour(int n) {
if(n <= 0) return false;
return ((n & (n - 1)) == 0) && ((n & 0x55555555) != 0);
}
}
172. Factorial Trailing Zeroes
Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.
分析
在面試時，曾遇到這樣的一道題：
30!結(jié)果轉(zhuǎn)換成3進(jìn)制劣纲，結(jié)尾有多少個連續(xù)的0逢捺？
第一次做的話，感覺沒有思路癞季，但是換個角度想蒸甜，轉(zhuǎn)換成3進(jìn)制，那么十進(jìn)制中的1~30余佛，哪些因子相乘柠新，才會貢獻(xiàn)出三進(jìn)制結(jié)尾的0呢？當(dāng)然是：3的倍數(shù)辉巡。
3恨憎， 6， 9郊楣， 12憔恳， 15 ，18净蚤， 21钥组， 24， 27今瀑， 30
那么程梦，每一個因子貢獻(xiàn)了多少個0呢？
貢獻(xiàn)了1個0的因子
3 = 3 * 1
6 = 3 * 2
12 = 3 * 4
15 = 3 * 5
21 = 3 * 7
24 = 3 * 8
30 = 3 * 10
貢獻(xiàn)了2個0的因子
9 = 3 * 3
18 = 3 * 3 * 2
貢獻(xiàn)了3個0的因子
27 = 3 * 3 * 3
30/3+30/9+30/27所代表的橘荠，就是最終結(jié)果屿附。
這是因為：30/3把所有貢獻(xiàn)了0的因子都算了一次，9哥童、18挺份、27已經(jīng)被算過一次了，但是9和18還有一個因子沒有算贮懈，27中還有兩個因子沒有算匀泊。
30/9則計算了一次9、18朵你、27各聘，但是27中還有一個因子沒有算。
30/27計算了一次27撬呢，至此伦吠，所有的因子都計算完畢。
答案就是
30/3+30/9+30/27=10+3+1=14
分析本題
n!中，結(jié)尾有多少個連續(xù)的0
不能像上題一樣毛仪，直接除以10……因為10可以拆分成兩個因子搁嗓，2和5。但是也不能除以2箱靴，因為在任何情況下腺逛，2的個數(shù)都會多余5的個數(shù)，所以衡怀，最終除以5就好啦棍矛！
100！中抛杨，結(jié)尾有多少個連續(xù)的0够委？
100/5 + 100/25 + 100/125 = 20 + 4 + 0 = 24
計算公式
在代碼中，一定要注意溢出的問題怖现，如下代碼（我的第一個代碼）就不能通過測試茁帽。因為在n很大時，比如Integer.MAX_VALUE屈嗤，i *= 5溢出了潘拨，i一直是小于等于n，所以是死循環(huán)饶号！
public int trailingZeroes2(int n) {
int rt = 0;
for (int i = 5; i <= n; i *= 5) {
rt += n / i;
}
return rt;
}
解決方法铁追，把n定義成long型。注意i也要定義成long型茫船，否則在n很大時琅束，主要是i * 5 > Integer.MAX_VALUE后會出錯。
代碼
public class Solution {
public int trailingZeroes(int n) {
int rt = 0;
for (long i = 5; i <= n; i *= 5) {
rt += n / i;
}
return rt;
}
}
總結(jié)
對于數(shù)字的問題透硝，本質(zhì)上還是要回歸到對數(shù)字本身的分析上狰闪，考察了數(shù)學(xué)的基本功。
