@Yano
2019-09-20T10:54:09.000000Z
字数 2896
阅读 2292
LeetCode
coding 笔记、点滴记录,以后的文章也会同步到公众号(Coding Insight)中,希望大家关注^_^
https://github.com/LjyYano/Thinking_in_Java_MindMapping
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;
}
}
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;
}
}
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);
}
}
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的位置仅出现在奇数的位置
上,例如
那么如何判断位数为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);
}
}
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;
}
}
对于数字的问题,本质上还是要回归到对数字本身的分析上,考察了数学的基本功。