Abo

关于n的幂次方问题

收录一些见到的比较耐人寻味的leetcode上的算法题(⓿_⓿)


programmer-1653351_1280

(●’◡’●) 希望一周至少更新两次

按照算法题类型会逐步更新



        

n的幂问题

LeetCode 第 231 号问题:2 的幂

题目描述

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

示例 1:

1
2
3
输入: 1
输出: true
解释: 20 = 1

示例 2:

1
2
3
输入: 16
输出: true
解释: 24 = 16

示例 3:

1
2
输入: 218
输出: false

题目解析

首先,先来分析一下 2 的次方数的二进制写法:

表格

仔细观察,可以看出 2 的次方数都只有一个 1 ,剩下的都是 0 。根据这个特点,只需要每次判断最低位是否为 1 ,然后向右移位,最后统计 1 的个数即可判断是否是 2 的次方数。

代码很简单:

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
bool isPowerOfTwo(int n) {
int cnt = 0;
while (n > 0) {
cnt += (n & 1);
n >>= 1;
}
return cnt == 1;
}
};

该题还有一种巧妙的解法。再观察上面的表格,如果一个数是 2 的次方数的话,那么它的二进数必然是最高位为1,其它都为 0 ,那么如果此时我们减 1 的话,则最高位会降一位,其余为 0 的位现在都为变为 1,那么我们把两数相与,就会得到 0。

比如 2 的 3 次方为 8,二进制位 1000 ,那么 8 - 1 = 7,其中 7 的二进制位 0111。

图片描述

代码实现

利用这个性质,只需一行代码就可以搞定。

1
2
3
4
5
6
class Solution {
public:
bool isPowerOfTwo(int n) {
return (n > 0) && (!(n & (n - 1)));
}
};

LeetCode 第 326 号问题:3 的幂

题目描述

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

示例 1:

1
2
输入: 27
输出: true

示例 2:

1
2
输入: 0
输出: false

进阶:
你能不使用循环或者递归来完成本题吗?

题目解析

正常的思路是不停地去除以 3,看最后的迭代商是否为 1。这种思路的代码使用到了循环,逼格不够高。

这里取巧的方法 用到了数论的知识:3 的幂次的质因子只有 3

题目要求输入的是 int 类型,正数范围是 0 - 231,在此范围中允许的最大的 3 的次方数为 319 = 1162261467 ,那么只要看这个数能否被 n 整除即可。

动画描述

待补充

代码实现

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

LeetCode 第 342 号问题:4 的幂

题目描述

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

示例 1:

1
2
输入: 16
输出: true

示例 2:

1
2
输入: 5
输出: false

进阶:
你能不使用循环或者递归来完成本题吗?

题目解析

这道题最直接的方法就是不停的去除以 4 ,看最终结果是否为 1 ,参见代码如下:

1
2
3
4
5
6
7
8
class Solution {
public boolean isPowerOfFour(int num) {
while ( (num != 0) && (num % 4 == 0)) {
num /= 4;
}
return num == 1;
}
}

不过这段代码使用了 循环 ,逼格不够高。

对于一个整数而言,如果这个数是 4 的幂次方,那它必定也是 2 的幂次方。

我们先将 2 的幂次方列出来找一下其中哪些数是 4 的幂次方。

十进制 二进制
2 10
4 100 (1 在第 3 位)
8 1000
16 10000(1 在第 5 位)
32 100000
64 1000000(1 在第 7 位)
128 10000000
256 100000000(1 在第 9 位)
512 1000000000
1024 10000000000(1 在第 11 位)

找一下规律: 4 的幂次方的数的二进制表示 1 的位置都是在奇数位

之前在小吴的文章中判断一个是是否是 2 的幂次方数使用的是位运算 n & ( n - 1 )。同样的,这里依旧可以使用位运算:将这个数与特殊的数做位运算。

这个特殊的数有如下特点:

  • 足够大,但不能超过 32 位,即最大为 1111111111111111111111111111111( 31 个 1)

  • 它的二进制表示中奇数位为 1 ,偶数位为 0

    符合这两个条件的二进制数是:

1
1010101010101010101010101010101

如果用一个 4 的幂次方数和它做与运算,得到的还是 4 的幂次方数

将这个二进制数转换成 16 进制表示:0x55555555 。有没有感觉逼格更高点。。。

snap2

图片描述

snap

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public boolean isPowerOfFour(int num) {
if (num <= 0)
return false;
//先判断是否是 2 的幂
if ((num & num - 1) != 0)
return false;
//如果与运算之后是本身则是 4 的幂
if ((num & 0x55555555) == num)
return true;
return false;
}
}

有趣的动态规划题目

稳定婚姻算法(Stable Matching Problem)

问题的引出

有N男N女,每个人都按照他对异性的喜欢程度排名。现在需要写出一个算法安排这N个男的、N个女的结婚,要求两个人的婚姻应该是稳定的。

何为稳定

有两对夫妻M1 F2,M2 F1。M1心目中更喜欢F1,但是他和F2结婚了,M2心目中更喜欢F2,但是命运( ̄︶ ̄)↗ 却让他和F1结婚了,显然这样的婚姻是不稳定的,随时都可能发生M1和F1私奔或者M2和F2私奔的情况。所以在做出匹配选择的时候(也就是结婚的时候),我们需要做出稳定的选择,以防这种情况的发生。

算法步骤

算法中采用了男生主动追求女孩的形式。

第一轮,每个男人都选择自己名单上排在首位的女人,并向她表白。

这种时候会出现两种情况:

(1)该女士还没有被男生追求过,则该女士接受该男生的请求。

(2)若该女生已经接受过其他男生的追求,那么该女生会将该男士与她的现任男友进行比较,若更喜欢她的男友,那么拒绝这个人的追求,否则,抛弃其男友(´▽`ʃ♡ƪ)……

第一轮结束后,有些男人已经有女朋友了,有些男人仍然是单身

在第二轮追女行动中,每个单身男都从所有还没拒绝过他的女孩中选出自己最中意的那一个,并向她表白,不管她现在是否是单身。这种时候还是会遇到上面所说的两种情况,还是同样的解决方案。直到所有人都不在是单身。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
#include <stack>

using namespace std;

#define NUM 4
#define NIL -1

int GetPositionFromLaday(int ladayArray[][NUM], int laday, int man)
{
for(int i=0; i<NUM; i++)
if(ladayArray[laday][i] == man)
return i;
return NIL;
}

void ChoosePartener(stack<int>& manStack, int manPos, int manArray[][NUM], int ladayArray[][NUM], int manPerfer[], int manStartPos[], int ladayNow[])
{
//选择自己名单上排在首位的女人
int perferLaday = manArray[manPos][manStartPos[manPos]];
//如果该女孩没有接受过表白,则接受该男孩的表白
if(ladayNow[perferLaday] == NIL)
{
ladayNow[perferLaday] = manPos;
manPerfer[manPos] = perferLaday;
}
//如果已经有人向她表白,则判断其现在拥有的有没有现在追求的好
else
{
int oldPos = GetPositionFromLaday(ladayArray, perferLaday, ladayNow[perferLaday]);
int newPos = GetPositionFromLaday(ladayArray, perferLaday, manPos);
if(oldPos < newPos)
{
manStartPos[manPos]++;//说明该女生更喜欢现在拥有的,选心目中第二位
//加入单身行列
manStack.push(manPos);
}
else //换男友
{
//被甩的男友恢复自由身份
manStartPos[ladayNow[perferLaday]]++;
//加入单身行列
manStack.push(ladayNow[perferLaday]);
//将追求的男士改为现任男友
ladayNow[perferLaday] = manPos;
manPerfer[manPos] = perferLaday;
}
}
}

int main()
{
int manArray[NUM][NUM] ={{2,3,1,0},{2,1,3,0},{0,2,3,1},{1,3,2,0}};
int ladayArray[NUM][NUM] = {{0,3,2,1},{0,1,2,3},{0,2,3,1},{1,0,3,2}};

}

算法总结

祝大家早日找到自己的婚姻匹配

杨辉三角(Pascal Triangle)

前些天看了杨永乐老师的视频,其中提到了杨辉三角,有兴趣的可以去看看。

问题的引出

(●’◡’●) 老师所提到的生活中的弹珠抽奖模型

杨辉三角应该是大家很早就接触到的一个数学知识,它有很多有趣的性质:

  • 每个数字等于上一行的左右两个数字之和,即 C(n+1,i) = C(n,i) + C(n,i-1)
  • 每行数字左右对称,由 1 开始逐渐变大
  • 第 n 行的数字有 n 项
  • 第 n 行的第 m 个数和第 n - m + 1 个数相等 ,为组合数性质之一
  • ( a + b )n的展开式中的各项系数依次对应杨辉三角的第 ( n + 1 ) 行中的每一项
  • 。。。

题目来源于 LeetCode 上第 118 号问题:杨辉三角。题目难度为 Easy,目前通过率为 61.8% 。

题目描述

给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。

img

在杨辉三角中,每个数是它左上方和右上方的数的和。

示例:

1
2
3
4
5
6
7
8
9
输入: 5
输出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]

题目解析

这道题目在各大高校的习题中经常出现。

对于本题而言,利用性质 1 :每一行的首个和结尾一个数字都是 1,从第三行开始,中间的每个数字都是上一行的左右两个数字之和。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public List<List<Integer>> generate(int numRows) {

List<List<Integer>> result = new ArrayList<>();
if (numRows < 1) return result;

for (int i = 0; i < numRows; ++i) {
//扩容
List<Integer> list = Arrays.asList(new Integer[i+1]);
list.set(0, 1); list.set(i, 1);
for (int j = 1; j < i; ++j) {
//等于上一行的左右两个数字之和
list.set(j, result.get(i-1).get(j-1) + result.get(i-1).get(j));
}
result.add(list);
}
return result;

}
}

杨辉三角II

题目来源于 LeetCode 上第 119 号问题:杨辉三角II。题目难度为 Easy,目前通过率为 55.5% 。

题目描述

给定一个非负索引 k,其中 k ≤ 33,返回杨辉三角的第 k 行。

img

在杨辉三角中,每个数是它左上方和右上方的数的和。

示例:

1
2
输入: 3
输出: [1,3,3,1]

进阶:

你可以优化你的算法到 O(k) 空间复杂度吗?

题目解析

这道题目的难点与思考点在于题目有额外限制条件,程序只能使用 O(k) 的额外空间,因此无法通过累加的方式将每一行都输出打印。

这里依旧使用杨辉三角的规律,很隐藏的规律:对于杨辉三角的同一行,第 ( i + 1) 项是第 i 项的( k - i ) /( i + 1 ) 倍。

比如:

  • 第 k 索引行的第 0 项:1
  • 第 k 索引行的第 1 项:1 * k
  • 第 k 索引行的第 2 项:1 k ( k - 1) / 2
  • 第 k 索引行的第 3 项:[1 k ( k - 1) / 2 ] * ( k - 2 ) / 3

代码实现

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> res = new ArrayList<>(rowIndex + 1);
long index = 1;
for (int i = 0; i <= rowIndex; i++) {
res.add((int) index);
index = index * ( rowIndex - i ) / ( i + 1 );
}
return res;
}
}

扫雷算法