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.
思路
要考虑的问题：
- 负数
- 溢出
对于溢出问题，因为是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.
思路
- 可以根据
(n & (n - 1)) == 0来判断，这是因为2的幂仅有1位是1，其余位全部是0；如果-1，那么1的那位会变成0，后面的位全部为1。 - 可以根据
(n & -n) == n来判断，这是 JDK 中 Ingeger 中使用的判断方法。因为 -n 的二进制表示，恰好相当于（n - 1）取反，而符号位本来就是不同的。本质上和上一种解放是一样的。
代码
代码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的最大幂数
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有关。思考一下，4的幂相对于2的幂，有哪些特点呢？
答案就是：在2的幂的基础上，位数为1的位置仅出现在奇数的位置上，例如
- 0000 0001 = 1，是4的幂
- 0000 0010 = 2，不是4的幂
- 0000 0100 = 4，是4的幂
那么如何判断位数为1的位置仅出现在奇数的位置上呢？与上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!结果转换成3进制，结尾有多少个连续的0？
第一次做的话，感觉没有思路，但是换个角度想，转换成3进制，那么十进制中的1~30，哪些因子相乘，才会贡献出三进制结尾的0呢？当然是：3的倍数。
3， 6， 9， 12， 15 ，18， 21， 24， 27， 30
那么，每一个因子贡献了多少个0呢？
贡献了1个0的因子
3 = 3 * 1
6 = 3 * 2
12 = 3 * 4
15 = 3 * 5
21 = 3 * 7
24 = 3 * 8
30 = 3 * 10
贡献了2个0的因子
9 = 3 * 3
18 = 3 * 3 * 2
贡献了3个0的因子
27 = 3 * 3 * 3
30/3+30/9+30/27所代表的，就是最终结果。
这是因为：30/3把所有贡献了0的因子都算了一次，9、18、27已经被算过一次了，但是9和18还有一个因子没有算，27中还有两个因子没有算。
30/9则计算了一次9、18、27，但是27中还有一个因子没有算。
30/27计算了一次27，至此，所有的因子都计算完毕。
答案就是
30/3+30/9+30/27=10+3+1=14
分析本题
n!中，结尾有多少个连续的0
不能像上题一样，直接除以10……因为10可以拆分成两个因子，2和5。但是也不能除以2，因为在任何情况下，2的个数都会多余5的个数，所以，最终除以5就好啦！
100！中，结尾有多少个连续的0？
100/5 + 100/25 + 100/125 = 20 + 4 + 0 = 24
计算公式
在代码中，一定要注意溢出的问题，如下代码（我的第一个代码）就不能通过测试。因为在n很大时，比如Integer.MAX_VALUE，i *= 5溢出了，i一直是小于等于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;
}
}
总结
对于数字的问题，本质上还是要回归到对数字本身的分析上，考察了数学的基本功。
网友评论