/ 算法  

智力算法和一些有趣的算法题(LeetCode)

记录一些有意思的智力算法和一些有趣的算法题。

除数博弈

题目描述:

爱丽丝和鲍勃一起玩游戏,他们轮流行动。爱丽丝先手开局。

最初,黑板上有一个数字 N 。在每个玩家的回合,玩家需要执行以下操作:

选出任一 x,满足 0 < x < N 且 N % x == 0 。
用 N - x 替换黑板上的数字 N 。
如果玩家无法执行这些操作,就会输掉游戏。

只有在爱丽丝在游戏中取得胜利时才返回 True,否则返回 false。假设两个玩家都以最佳状态参与游戏。

题解思路:

可以依次举例数字N的值,以及爱丽丝获胜的的情况,比如:

N的值 1 2 3 4 5 6 7
A先手 x (2)1 (3)1 (4)1-(2)1 (5)1-(3)1 (6)1 (7)1
B后手 x x (2)1 (3)1 (4)1 (5)1 (6)1
A获胜 false true false true false true false

由已知的数学规律:奇数的因子(约数)只能是奇数,偶数的因子(约数)可以是奇数或偶数。然后举几个例子就能够发现一些其他规律:当N为奇数的时候,先手(A)只能够选择奇数,此时奇数-奇数=偶数,则一下个玩家面对的数据就为偶数,当玩家面对偶数时,可能会选择偶数因子也可能选择奇数因子,由规律发现只有先手数据为偶数时,A才能够获胜,相反情况则B获胜,所以在玩家最佳状态选择除数因子都会遵循:N-除数因子 = 奇数,这样对手就不会获胜了。

代码实现:

1
2
3
4
5
class Solution {
public boolean divisorGame(int N) {
return N % 2 == 0;
}
}

2的幂

题目描述:

给定一个整数,编写一个函数来判断它是否是 2 的幂次方。

解题思路:

传统解法:不停地去除以 2,看最后的迭代商是否为 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public boolean isPowerOfTwo(int n) {
if(n ==1)
return true;
while(n % 2==0){
n=n/2;
}
if(n == 1)
return true;
else
return false;
}
}

利用二进制的解法:如果一个数是 2 的次方数的话,那么它的二进数必然是最高位为 1,其它都为 0 ,那么如果此时我们减 1 的话,则最高位会降一位,其余为 0 的位现在都为变为 1,那么我们把两数相与,就会得到 0。

1
2
3
4
5
class Solution {
public boolean isPowerOfTwo(int n) {
return n > 0 && ((n & (n - 1)) == 0);
}
}

3的幂

题目描述:

给定一个整数,写一个函数来判断它是否是 3 的幂次方。

解题思路:

与上面2的幂的解法类似,第一个方法是不停地去除以 3,看最后的迭代商是否为 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public boolean isPowerOfThree(int n) {
if (n <= 0){
return false;
}
if (n == 1){
return true;
}
while (true){
if (n == 1){
return true;
}
else if (n % 3 > 0){
return false;
}
else{
n = n / 3;
}
}
}
}

另外一种思路是将整数转换为3进制数的字符串,然后判断最高是否为1,其余位为0,但是3进制转换需要写一个转换方法,有点麻烦。

所以可以再换一个思路,因为3的次幂的质因子只有3,因为根据数论相关定理,不考虑排列顺序的情况下,每个正整数都能够以唯一的方式表示成它的质因数的乘积。比如:1没有质因子。2、4、8、16等只有1个质因子:2(2是质数,4 = 2^2,8 = 2^3,如此类推),3的次幂的质因子只有3(3、9、27、81…)。

又因为给定的是整数,故而题目中所给整数范围内最大的 3 的幂次的因子只能是 3 的幂次,而1162261467 是 3 的 19 次幂,是整数范围内最大的3的幂次。

1
2
3
4
5
class Solution {
public boolean isPowerOfThree(int n) {
return n > 0 && 1162261467 % n == 0;
}
}

4的幂

题目描述:

给定一个整数 (32 位有符号整数),请编写一个函数来判断它是否是 4 的幂次方。

解题思路:

直观思路,循环num=num/4检测num%4是否为0,直到num为1为止。注意,需考虑num为0的情况,否则会陷入死循环,码代码多考虑一些边界特殊情况.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public boolean isPowerOfFour(int n) {
if(num == 0)
return false;

while(num != 1){
if(num%4 != 0)
return false;
num = num/4;
}
return true;
}
}

不使用循环的解法:我们知道num & (num - 1)可以用来判断一个数是否为2的幂,其中4的幂是2的幂的一个子集,所以对2的幂做一些限制条件,4的幂都是在16进制下的第1和4位,即0101,所以我们只需和数(0x55555555) 进按位与,得到的数还是其本身,则可以肯定其为4的次方数。

1
2
3
4
5
class Solution {
public boolean isPowerOfFour(int num) {
return num > 0 && (num&(num-1)) == 0 && ((num&0x55555555)==num);
}
}