数学运算
About 27 min
常用的位操作
Java中的位操作符
注意
Java中位操作符的操作数只能是整型（byte、short、int、long）和字符型数据（char）。Java中位操作符一共有7个，其中4个是位逻辑运算符，3个是移位运算符。- 使用按位操作符时要注意：相等
（==）与不相等（!=）的优先级在按位操作符之上！这意味着，位运算符的优先级极小，所以使用位运算符时，最好加上括号。
4个位逻辑运算符
- 位逻辑运算符包括按位取反
（~）、按位与（&）、按位或（|）和按位异或（^）4种。- 与操作符
“&”，如果两个输入位都是 1，那么输出位是 1，否则输入位是 0。【对应位全都为1，则为1】 - 或操作符
“|”，如果两个输入位有一个是 1，那么输出位是 1，只有两个输入位都是 0，输出位才是 0。【对应位含有1，则为1】 - 异或运算符
“^”，如果两个输入位都为 1 或者都为 0，那么输出位是 0，否则输出位是 1。【对应位相同，则为0，反之为1】 - 非运算符
“~”，这个一元操作符，只能对一个数操作，规则是输出位与输入位相反。【一元操作符，输入1，则输出0；输入0，则输出1】
- 与操作符
@Test
public void test() {
//转化为二进制：0101
int num1 = 5;
//转化为二进制：1001
int num2 = 9;
//与运算，二进制结果为 0001，打印结果为 1
System.out.println(num1 & num2);
//或运算，二进制结果为 1101，打印结果为 13
System.out.println(num1 | num2);
//异或运算，二进制结果为 1100，打印结果为 12
System.out.println(num1 ^ num2);
//非运算，打印结果 -6
System.out.println((~num1));
//非运算，二进制结果为 11111111 11111111 11111111 11111010
System.out.println(Integer.toBinaryString(~num1));
}
补充
- 数字的二进制表现形式为 “有符号的二进制补码”。
- 原码：数字的二进制表示法，最高位为符号位，“ 0 ” 为正，“ 1 ” 为负。
- 反码：正数的反码与原码相同，负数的反码对原码逐位取反，符号位除外。
- 补码：正数的补码与原码相同，负数的补码在其反码末位加 1。
- 负数的二进制算法（以
-6为例，int类型占4个字节，1个字节是8位）：- 求
-6的原码，即：10000000 00000000 00000000 00000110 - 求该二进制数的反码，即：
11111111 11111111 11111111 11111001 - 对以上求得的二进制数加
1，即：11111111 11111111 11111111 11111010
- 求
说明
位逻辑运算符用来操作整数的二进制位，会对两个参数中对应的位执行布尔代数运算，并最终生成一个结果。
3个移位运算符
- 移位运算符包括左移
（<<）、右移（>>）和无符号右移（>>>）3种。- 左移位操作符 “
<<” 按照操作符右侧指定的位数将操作符左边的操作数向左移动（低位补零）。【左移之后，低位补0】 - “有符号”右移位操作符 “
>>” 按照操作符右侧指定的位数将操作符左边的操作数向右移动。该操作符使用 “符号扩展”：若符号为正，则高位插入 0；若符号为负，则高位插入 1。【右移之后，高位进行符号扩展】 - “无符号”右移位操作符 “
>>>”，该操作符使用 “零扩展”，无论正负，都在高位插入 0。【右移之后，高位进行零扩展】
- 左移位操作符 “
@Test
public void test() {
//二进制 1111;
int i = 15;
//向右边移动两位，二进制结果为 0011，打印结果为 3
System.out.println(i >> 2);
//向左边移动两位，二进制结果为 111100，打印结果为 60
System.out.println(i << 2);
}
- 移位运算符可以与等号组合使用（
<<=或>>=或>>>=），表示操作符左边的值会移动由右边数值指定的位数，再将得到的结果赋给左边的变量。 - 在数字没有溢出的前提下，对于正数和负数，左移一位都相当于乘以2的1次方，左移
n位就相当于乘以2的n次方，右移一位相当于除2，右移n位相当于除以2的n次方。
@Test
public void test() {
int i = 10;
// 左移1位，相当于乘2的1次方
System.out.println(i << 1);// 20
// 左移4位，相当于乘2的4次方
System.out.println(i << 4);// 160
// 右移1位，相当于除2的1次方
System.out.println(i >> 1);// 5
// 左移3位，相当于除2的3次方
System.out.println(i >> 3);// 1
}
说明
移位操作符的运算对象也是二进制的 “位”，但是只能用来处理整数类型。
注意
- 逻辑运算符包括逻辑与
（&&）、逻辑或（||）和逻辑非（!），前两个是二元运算符，后一个是一元运算符。
几个有趣的位操作
- 利用或操作
|和空格将英文字符转换为小写
('a' | ' ') = 'a'
('A' | ' ') = 'a'
- 利用与操作
&和下划线将英文字符转换为大写
('b' & '_') = 'B'
('B' & '_') = 'B'
- 利用异或操作
^和空格进行英文字符大小写互换
('d' ^ ' ') = 'D'
('D' ^ ' ') = 'd'
以上操作能够产生奇特效果的原因在于 ASCII码。字符的ASCII码其实就是数字，恰巧这些字符对应的数字通过位运算就能得到正确的结果。
@Test
public void test() {
// 测试和空格进行按位或操作转为小写字母
int i1 = 'a' | ' ';
int j1 = 'A' | ' ';
log.debug("{},{}", (char) i1, (char) j1);//a,a
// 测试和下划线进行按位与操作转为大写字母
int i2 = 'a' & '_';
int j2 = 'A' & '_';
log.debug("{},{}", (char) i2, (char) j2);//A,A
// 测试和空格进行按位异或操作进行大小写转换
int i3 = 'a' ^ ' ';
int j3 = 'A' ^ ' ';
log.debug("{},{}", (char) i3, (char) j3);//A,a
}
- 判断两个数是否异号
int x = -1, y = 2;
boolean f = ((x ^ y) < 0); // true
int x = 3, y = 2;
boolean f = ((x ^ y) < 0); // false
- 不用临时变量交换两个数
int a = 1, b = 2;
a ^= b;
b ^= a;
a ^= b;
// 现在 a = 2, b = 1
// 或者
b ^= a;
a ^= b;
b ^= a;
- 加一
int n = 1;
n = -~n;
// 现在 n = 2
- 减一
int n = 2;
n = ~-n;
// 现在 n = 1
位操作的黑科技玩法
- 有一个叫做
Bit Twiddling Hacks的外国网站收集了几乎所有位操作的黑科技玩法。 - 网址：http://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel
n&(n-1)的运用
n & (n-1)是算法中常见的位操作，作用是消除数字n的二进制表示中的最后一个 1。其核心逻辑就是，
n - 1一定可以消除最后一个 1，同时把其后的 0 都变成 1，这样再和n做一次&运算，就可以仅仅把最后一个 1 变成 0 了。
1、计算汉明权重（Hamming Weight）
LeetCode相关题目：位1的个数
- 就是让你返回
n的二进制表示中有几个 1。因为n & (n - 1)可以消除最后一个 1，所以可以用一个循环不停地消除 1 同时计数，直到n变成 0 为止。
public int hammingWeight(int n) {
int sum = 0;
while (n != 0) {
n = n & (n - 1);
sum++;
}
return sum;
}
2、判断一个数是不是 2 的指数
LeetCode相关题目：2的幂
一个数如果是 2 的指数，那么它的二进制表示一定只含有一个 1：
2^0 = 1 = 0b0001
2^1 = 2 = 0b0010
2^2 = 4 = 0b0100
如果使用 n & (n-1) 的技巧就很简单了（注意运算符优先级，括号不可以省略）：
public boolean isPowerOfTwo(int n) {
if (n <= 0) return false;
n = n & (n - 1);
return n == 0;
}
//或者
public boolean isPowerOfTwo(int n) {
// 一句代码解决问题
return n > 0 && ((n & (n - 1)) == 0);
}
a^a=0的运用
异或运算的性质
- 一个数和它本身做异或运算结果为 0，即
a ^ a = 0；一个数和 0 做异或运算的结果为它本身，即a ^ 0 = a。 - 满足结合律和交换律。
- 由于异或运算满足交换律和结合律，所以总是能把成对儿的数字消去，留下缺失的那个元素。
1、查找只出现一次的元素
LeetCode相关题目：只出现一次的数字
- 把所有数字进行异或，成对儿的数字就会变成 0，落单的数字和 0 做异或还是它本身，所以最后异或的结果就是只出现一次的元素。
// 满足结合律和交换律
// 以[4, 1, 2, 1, 2]为例
0 ^ 4 ^ 1 ^ 2 ^ 1 ^ 2
0 ^ 4 ^ (1 ^ 1) ^ (2 ^ 2)
0 ^ 4 ^ (0 ^ 0)
0 ^ 4 ^ 0
(0 ^ 0) ^ 4
0 ^ 4
4
public int singleNumber(int[] nums) {
int res = 0;
for (int n : nums) {
res ^= n;
}
return res;
}
2、寻找缺失的元素
LeetCode相关题目：丢失的数字
- 给一个长度为
n的数组，其索引应该在[0,n)，但是现在你要装进去n + 1个元素[0,n]，那么肯定有一个元素装不下，请找出这个缺失的元素。 - 思路一：把这个数组排个序，然后遍历一遍，就可以很容易的找到缺失的那个元素
public int missingNumber(int[] nums) {
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
if (i != nums[i]) {
return i;
}
}
return nums.length;
}
- 思路二：利用数据结构的特性，用一个
HashSet把数组里出现的数字都储存下来，再遍历[0,n]之间的数字，去HashSet中查询，也可以很容易查出那个缺失的元素。
public int missingNumber(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
for (int i = 0; i <= nums.length; i++) {
if (!set.contains(i)) {
return i;
}
}
return 0;
}
- 思路三：利用等差数列求和公式，题目的意思可以这样理解：现在有个等差数列
0, 1, 2,..., n，其中少了某一个数字，那这个数字就是sum(0,1,..n) - sum(nums)。
public int missingNumber(int[] nums) {
int sum1 = (1 + nums.length) * nums.length / 2;
int sum2 = 0;
for (int num : nums) {
sum2 += num;
}
return sum1 - sum2;
}
- 思路四：利用一个数和它本身做异或运算结果为 0，一个数和 0 做异或运算还是它本身的性质。
异或运算满足交换律和结合律
2 ^ 3 ^ 2 = 3 ^ (2 ^ 2) = 3 ^ 0 = 3
比如说 nums = [0,3,1,4]：
假设先把索引补一位，然后让每个元素和自己相等的索引相对应：
通过上图可以发现：只要把所有的元素和索引做异或运算，成对儿的数字都会消为 0，只有这个落单的元素会剩下。
public int missingNumber(int[] nums) {
// 时间复杂度O(N)
// 空间复杂度O(1)
int result = 0;
// 把索引全都异或一遍，范围是[0,n]，左右都包括，即n+1个数
for (int i = 0; i <= nums.length; i++) {
result ^= i;
}
// 把nums中的值全都异或一遍，即n个数
for (int num : nums) {
result ^= num;
}
return result;
}
public int missingNumber(int[] nums) {
// 时间复杂度O(N)
// 空间复杂度O(N)
// list放置索引和nums中的所有值，后续依次对list中的数据进行异或操作
ArrayList<Integer> list = new ArrayList<>();
// 把索引全都加入list
for (int i = 0; i <= nums.length; i++) {
list.add(i);
}
// 把nums中的值全都加入list
for (int num : nums) {
list.add(num);
}
// 对list中的所有值进行异或操作
int result = 0;
for (Integer integer : list) {
result ^= integer;
}
return result;
}
// 本思路直接将题目演变成了LeetCode的第136题目，即只出现一次的数字。
两道常考的阶乘算法题
题一
LeetCode相关题目：阶乘后的零
输入一个非负整数
n，请你计算阶乘n!的结果末尾有几个 0。比如说输入
n = 5，算法返回 1，因为5! = 120，末尾有一个 0。两个数相乘结果末尾有 0，一定是因为两个数中有因子 2 和 5，因为 10 = 2 x 5。
- 问题转化为：
n!最多可以分解出多少个因子 2 和 5？ - 比如说
n = 25，那么25!最多可以分解出几个 2 和 5 相乘？这个主要取决于能分解出几个因子 5，因为每个偶数都能分解出因子 2，因子 2 肯定比因子 5 多得多。25!中 5 可以提供一个，10 可以提供一个，15 可以提供一个，20 可以提供一个，25 可以提供两个，总共有 6 个因子 5，所以25!的结果末尾就有 6 个 0。 - 问题转化为：
n!最多可以分解出多少个因子 5？ - 难点在于像 25，50，125 这样的数，可以提供不止一个因子 5，怎么才能不漏掉呢？
- 问题转化为：
假设
n = 125，来算一算125!的结果末尾有几个 0：- 首先，125 / 5 = 25，这一步就是计算有多少个像 5，15，20，25 这些 5 的倍数，它们一定可以提供一个因子 5。
- 然后，像 25，50，75 这些 25 的倍数，可以提供两个因子 5，那么我们再计算出
125!中有 125 / 25 = 5 个 25 的倍数，它们每人可以额外再提供一个因子 5。 - 最后，我们发现 125 = 5 x 5 x 5，像 125，250 这些 125 的倍数，可以提供 3 个因子 5，那么我们还得再计算出
125!中有 125 / 125 = 1 个 125 的倍数，它还可以额外再提供一个因子 5。 125!最多可以分解出 25 + 5 + 1 = 31 个因子 5，也就是说阶乘结果的末尾有 31 个 0。
public int trailingZeroes(int n) {
/*
n / 5
n / 5 / 5
n / 5 / 5 / 5
*/
int result = 0;
// d有可能越界
long d = 5;
// n可以分解出多少个因子5
while (d <= n) {
result += (n / d);
d *= 5;
}
// d>n的时候退出循环，n如果是int的最大值，那么d使用int类型有可能越界，所以使用long类型
return result;
}
public int trailingZeroes(int n) {
/*
n / 5
n / 5 / 5
n / 5 / 5 / 5
*/
int result = 0;
for (int i = 1; Math.pow(5, i) <= n; i++) {
result += (n / Math.pow(5, i));
}
return result;
}
public int trailingZeroes(int n) {
/*
n / 5
n / 5 / 5
n / 5 / 5 / 5
*/
int res = 0;
for (int d = n; d / 5 > 0; d = d / 5) {
res += d / 5;
}
return res;
}
- 时间复杂度是底数为 5 的对数，也就是
O(logN)。
题二
LeetCode相关题目：阶乘函数后K个零
输入一个非负整数
K，请你计算有多少个n，满足n!的结果末尾恰好有K个 0。比如说输入
K = 1，算法返回 5，因为5!,6!,7!,8!,9!这 5 个阶乘的结果最后只有一个 0，即有 5 个n满足条件。一个直观地暴力解法就是穷举，因为随着
n的增加，n!肯定是递增的，trailingZeroes(n!)肯定也是递增的，伪码逻辑如下：
int res = 0;
for (int n = 0; n < +inf; n++) {
if (trailingZeroes(n) < K) {
continue;
}
if (trailingZeroes(n) > K) {
break;
}
if (trailingZeroes(n) == K) {
res++;
}
}
return res;
- 对于这种具有单调性的函数，用
for循环遍历，可以用二分查找进行降维打击。 - 搜索有多少个
n满足trailingZeroes(n) == K，其实就是在问，满足条件的n最小是多少，最大是多少，最大值和最小值一减，就可以算出来有多少个n满足条件，这就是二分查找中搜索左侧边界和搜索右侧边界。
寻找上界和下界
因为二分查找需要给一个搜索区间，也就是上界和下界，上述伪码中 n 的下界显然是 0，但上界是 +inf，这个正无穷应该如何表示出来呢？
- 首先，数学上的正无穷肯定是无法编程表示出来的，我们一般的方法是用一个非常大的值，大到这个值一定不会被取到。比如说
int类型的最大值INT_MAX（2^31 - 1），还不够的话就long类型的最大值LONG_MAX（2^63 - 1）。 - 需要多大才能一定不会被取到呢？这就需要认真读题，看看题目给的数据范围有多大。
- 这道题目实际上给了限制，
K是在[0, 10^9]区间内的整数，也就是说，trailingZeroes(n)的结果最多可以达到10^9。然后我们可以反推，当trailingZeroes(n)结果为10^9时，n为多少？这个不需要你精确计算出来，你只要找到一个数hi，使得trailingZeroes(hi)比10^9大，就可以把hi当做正无穷，作为搜索区间的上界。 trailingZeroes函数是单调函数，那可以先算一下trailingZeroes(INT_MAX)的结果，比10^9小一些，那再用LONG_MAX算一下，远超10^9了，所以LONG_MAX可以作为搜索的上界。
- 在区间
[0, LONG_MAX]中寻找满足trailingZeroes(n) == K的左侧边界和右侧边界。
/* 主函数 */
public int preimageSizeFZF(int K) {
// 左边界和右边界之差 + 1 就是答案
return (int) (right_bound(K) - left_bound(K) + 1);
}
/* 搜索 trailingZeroes(n) == K 的左侧边界 */
public long left_bound(int target) {
long lo = 0, hi = Long.MAX_VALUE;
while (lo < hi) {
long mid = lo + (hi - lo) / 2;
if (trailingZeroes(mid) < target) {
lo = mid + 1;
} else if (trailingZeroes(mid) > target) {
hi = mid;
} else {
hi = mid;
}
}
return lo;
}
/* 搜索 trailingZeroes(n) == K 的右侧边界 */
public long right_bound(int target) {
long lo = 0, hi = Long.MAX_VALUE;
while (lo < hi) {
long mid = lo + (hi - lo) / 2;
if (trailingZeroes(mid) < target) {
lo = mid + 1;
} else if (trailingZeroes(mid) > target) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo - 1;
}
// 全都改成long类型，避免整型溢出
public long trailingZeroes(long n) {
long result = 0;
long d = 5;
while (d <= n) {
result += n / d;
d *= 5;
}
return result;
}
- 时间复杂度主要是二分搜索，从数值上来说
LONG_MAX是2^63 - 1，虽然大得离谱，但是二分搜索是对数级的复杂度，log(LONG_MAX)是一个常数； - 每次二分的时候都会调用一次
trailingZeroes函数，复杂度O(logK)； - 所以总体的时间复杂度就是
O(logK)。
规律和优化
- 这个题的答案其实不是
0就是5，所以其实只需要判断阶乘结果末尾恰好有K个0的值是否存在即可，如果存在，那么我们直接return 5；如果不存在，则直接return 0即可。 - 此优化效率提升明显。
public int preimageSizeFZF(int K) {
long lo = 0, hi = Long.MAX_VALUE;
while (lo < hi) {
long mid = lo + (hi - lo) / 2;
if (trailingZeroes(mid) < K) {
lo = mid + 1;
} else if (trailingZeroes(mid) > K) {
hi = mid;
} else {
// 找到之后直接返回结果5
return 5;
}
}
return 0;
}
// 全都改成long类型，避免整型溢出
public long trailingZeroes(long n) {
long result = 0;
long d = 5;
while (d <= n) {
result += n / d;
d *= 5;
}
return result;
}
高效寻找素数
高效进行模幂运算
LeetCode相关题目：超级次方
- 要求你的算法返回幂运算
a^b的计算结果与 1337 取模（mod，也就是余数）后的结果，这个b是一个非常大的正整数且会以数组形式给出。- 一是如何处理用数组表示的指数。现在
b是一个数组，也就是说b可以非常大，没办法直接转成整型，否则可能溢出。 - 二是如何得到求模之后的结果。先把幂运算结果算出来，然后做
% 1337，但指数运算的真实结果肯定会大得吓人，也就是说，算出来真实结果也没办法表示，早都溢出报错了。 - 三是如何高效进行幂运算。
- 一是如何处理用数组表示的指数。现在
如何处理数组指数
首先明确问题：现在
b是一个数组，不能表示成整型，而且数组的特点是随机访问，删除最后一个元素比较高效。- 以
b = [1,5,6,4]来举例，结合指数运算的法则，我们可以发现这样的一个规律：
- 以
问题规模缩小，这是递归的标志。
先不考虑取模的情况：
// 手动实现pow(a,b)-不使用递归
public int myPow(int a, int b) {
if (b < 0) return -1;//非法情况
if (b == 0) return 1;//不能丢掉，否则会遗漏b=0的情况【仔细分析，由于res的值为1，实际上可以丢掉】
int res = 1;
for (int i = 1; i <= b; i++) {
res *= a;
}
return res;
}
// 手动实现pow(a,b)-使用递归
public int myPow(int a, int b) {
if (b < 0) return -1;//非法情况
if (b == 0) return 1;//能丢掉，实际上走不到这
if (b == 1) return a;
return a * myPow(a, b - 1);
}
// 递归
public int superPow(int a, int[] b) {
// 递归终止条件
if (b.length == 0) return 1;
// 将原问题化简，缩小规模递归求解
// 计算第一部分
int part1 = myPow(a, b[b.length - 1]);
// 计算第二部分
int part2 = myPow(superPow(a, Arrays.copyOf(b, b.length - 1)), 10);
// 合并结果
return part1 * part2;
}
如何处理mod运算
- 首先明确问题：由于计算机的编码方式，形如
(a * b) % base这样的运算，乘法的结果可能导致溢出，我们希望找到一种技巧，能够化简这种表达式，避免溢出同时得到结果。- 比如在二分查找中，我们求中点索引时用
(l+r)/2转化成l+(r-l)/2，避免溢出的同时得到正确的结果。
- 比如在二分查找中，我们求中点索引时用
- 快速进行
mod运算公式：(a * b) % k = [(a % k)(b % k)] % k- 对乘法的结果求模，等价于先对每个因子都求模，然后对因子相乘的结果再求模。
完整代码：
public int base = 1337;
// 手动实现pow(a,b)
// 函数返回的是pow(a,b)取模之后的结果
public int myPow(int a, int b) {
// 1*a*a*a*a...
if (b < 0) return -1;//非法情况
if (b == 0) return 1;//不能丢掉，否则会遗漏b=0的情况【仔细分析，由于res的值为1，实际上可以丢掉】
int res = 1;
a %= base;
for (int i = 1; i <= b; i++) {
res *= a;
res %= base;
}
return res;
}
// 递归
public int superPow(int a, int[] b) {
// 递归终止条件
if (b.length == 0) return 1;
// 将原问题化简，缩小规模递归求解
// 计算第一部分
int part1 = myPow(a, b[b.length - 1]);
// 计算第二部分
int part2 = myPow(superPow(a, Arrays.copyOf(b, b.length - 1)), 10);
// 合并结果
return (part1 * part2) % base;
}
myPow函数先对因子 a 求模，然后每次都对乘法结果 res 求模，这样可以保证 res *= a 这句代码执行时两个因子都是小于 base 的，也就一定不会造成溢出，同时结果也是正确的。
myPow函数也可以通过递归方式进行优化，完整代码如下（推荐使用高级的快速幂算法，时间复杂度可以达到O(logN)对数级别）：
// 手动实现pow(a,b)
// 函数返回的是pow(a,b)取模之后的结果
public int myPow(int a, int b) {
/**
* 以a^4为例，则b=4，该函数返回的是a^4取模之后的结果
* 即：(a^4)%base
* (a*a^3)%base
* (a%base)((a^3)%base)%base
* 其中：(a^3)%base是(a^4)%base规模缩小的问题
* 所以可以使用递归进行求解
*/
if (b < 0) return -1;//非法情况
if (b == 0) return 1;//能丢掉，实际上走不到这
if (b == 1) return a % base;
return ((a % base) * (myPow(a, b - 1))) % base;
}
// 时间复杂度为O(N)
如何高效求幂（快速幂）
快速幂（快速的进行幂运算）是一种简单而有效的小算法，它能够以O(logN)的时间复杂度进行幂运算，快速幂不仅本身非常常见，而且后续很多算法也都会用到快速幂。举个例子：7的10次方，怎样算比较快？
- 最朴素的想法：
7*7=49、49*7=343，依次一步一步算，共进行了9次乘法。 - 先算7的5次方，即
7*7*7*7*7，再算它的平方，共进行了5次乘法。 - 先算
7*7得49，则7的5次方为49*49*7，再算它的平方，共进行了4次乘法。 - 模仿这样的过程，我们得到一个在
O(logN)时间内计算出幂的算法，也就是快速幂。
- 最朴素的想法：
递归快速幂【 重点掌握 】
// 递归快速幂
public int recursionPow(int a, int b) {
if (b < 0) return -1;// 非法情况
if (b == 0) {// 0
return 1;// 相当于是递归的结束条件
} else if (b % 2 == 1) {// 奇数
return recursionPow(a, b - 1) * a;
} else {// 偶数
// tmp变量是必要的
// 如果写成recursionPow(a, b / 2)*recursionPow(a, b / 2)
// 则计算机会计算两次，那么算法退化成O(N)的时间复杂度
int tmp = recursionPow(a, b / 2);
return tmp * tmp;
}
}
注意
- 在实际问题中，题目常常会要求对一个大数取模，这是因为幂运算的计算结果可能会非常巨大。
- 快速幂也应当进行取模，此时应当注意：三种情况都需要考虑取模，如果取模的
base较大，还应当使用long类型进行定义。
// 递归快速幂
// 返回的是取模之后的结果
public int recursionPow(int a, int b) {
if (b < 0) return -1;// 非法情况
if (b == 0) {// 0
return 1;// 相当于是递归的结束条件
} else if (b % 2 == 1) {// 奇数
return (recursionPow(a, b - 1) * (a % base)) % base;
} else {// 偶数
// tmp变量是必要的
// 如果写成recursionPow(a, b / 2)*recursionPow(a, b / 2)
// 则计算机会计算两次，那么算法退化成O(N)的时间复杂度
int tmp = recursionPow(a, b / 2);
return (tmp * tmp) % base;
}
}
- 递归虽然简洁且运算速度快，但会产生额外的空间开销，可以把递归改写为循环，来避免对栈空间的大量占用，也就是非递归快速幂。
- 时间复杂度：
O(logN)，即为递归的层数。 - 空间复杂度：
O(logN)，即为递归的层数。这是由于递归的函数调用会使用栈空间。
- 时间复杂度：
- 非递归快速幂【 重点掌握 】
引入
- 换一个角度来引入非递归的快速幂，还是7的10次方，但这次，把10写成二进制的形式，也就是
0b1010。 - 要计算 70b1010 ，可以怎么做？
- 很自然地想到可以把它拆分为 70b1000*70b10 。
- 实际上，对于任意的整数，都可以把它拆成若干个 70b100...的形式相乘。
- 而这些70b100...，恰好就是 71 、72、74等等，我们只需不断把底数平方就可以算出它们。
不考虑取模的情况：
// 非递归快速幂
public int unRecursionPow(int a, int n) {
if (n < 0) return -1;//非法情况
if (n == 0) return 1;//不能丢掉，否则会遗漏b=0的情况【仔细分析，由于res的值为1，实际上可以丢掉】
int ans = 1;
while (n != 0) {
if ((n & 1) == 1) //如果n的当前末位为1
ans *= a; //ans乘上当前的a
a *= a; //a自乘
n >>= 1; //n往右移一位
}
return ans;
}
考虑取模的情况：
// 非递归快速幂
// 返回的是取模之后的结果
public int unRecursionPow(int a, int n) {
if (n < 0) return -1;//非法情况
if (n == 0) return 1;//不能丢掉，否则会遗漏b=0的情况【仔细分析，由于res的值为1，实际上可以丢掉】
int ans = 1;
a %= base;
while (n != 0) {
if ((n & 1) == 1) {//如果n的当前末位为1
ans *= a; //ans乘上当前的a
ans %= base;
}
// 潜在的整型溢出
a *= a; //a自乘
a %= base;
n >>= 1; //n往右移一位
}
return ans;
}
- 复杂度分析
- 时间复杂度：
O(logN)，即为对n进行二进制拆分的时间复杂度。 - 空间复杂度：
O(1)。
- 时间复杂度：
- 总结
- 空间复杂度要求的不是太高的话，建议还是使用递归快速幂。
参考：
https://zhuanlan.zhihu.com/p/95902286
https://leetcode.cn/problems/powx-n/solutions/238559/powx-n-by-leetcode-solution/
LeetCode相关题目：
Pow(x, n)：考虑指数为负数的情况。
// 主函数
public double myPow(double x, int n) {
long N = n;
if (N == 0) return 1;
return N < 0 ? 1 / unRPow(x, -N) : unRPow(x, N);
}
// 使用非递归快速幂
public double unRPow(double a, long b) {
if (b < 0) return -1;// 非法情况
if (b == 0) return 1;
double res = 1.0;
while (b != 0) {
if ((b & 1) == 1) {//末位是1
res *= a;
}
a *= a;
b >>= 1;
}
return res;
}
注意
Java中int类型的范围是[-2147483648,2147483647]，即最大值是231-1，最小值是-231。- 所以在测试用例
x=1，n=-2147483648运行时，使用下面的代码会出现问题：
// 主函数
public double myPow(double x, int n) {
if (n == 0) return 1;
return n < 0 ? 1 / unRPow(x, -n) : unRPow(x, n);
// 当n=-2147483648时候，取相反数应该是2147483648，但int类型最大值才是2147483647，所以取相反数是不变的，还是原值-2147483648。
// 解决办法是将其转为long类型
}
同时寻找缺失和重复的元素
LeetCode相关题目：错误的集合
给一个长度为
N的数组nums，其中本来装着[1..N]这N个元素，无序。但是现在出现了一些错误，nums中的一个元素出现了重复，也就同时导致了另一个元素的缺失。正常思路：首先记录每一个元素出现的次数，找到重复的元素，然后在找缺失的元素。
import java.util.*;
class Solution {
public int[] findErrorNums(int[] nums) {
int[] res = new int[2];
// 存储每一个元素出现的此次数
Hashtable<Integer, Integer> hashtable = new Hashtable<>();
for (int num : nums) {
if (!hashtable.containsKey(num)) {
hashtable.put(num, 1);
} else {
hashtable.put(num, hashtable.get(num) + 1);
}
}
Set<Integer> set = hashtable.keySet();
for (Integer integer : set) {
if (hashtable.get(integer) != 1)
res[0] = integer;
}
for (int i = 1; i <= nums.length; i++) {
if (set.contains(i))
continue;
else
res[1] = i;
}
return res;
}
}
复杂度分析
- 时间复杂度：
O(N) - 空间复杂度：
O(N) O(N)的时间复杂度遍历数组是无法避免的，所以可以想想办法如何降低空间复杂度，是否可以在O(1)的空间复杂度之下找到重复和缺失的元素？
- 思路分析（优化空间复杂度到
O(1)）- 每个元素和数组索引有一定的对应关系。
- 暂且将
nums中的元素变为[0..N-1]，这样每个元素就和一个数组索引完全对应了，这样方便理解一些。 - 如果说
nums中不存在重复元素和缺失元素，那么每个元素就和唯一一个索引值对应。 - 有一个元素重复了，同时导致一个元素缺失了，会导致有两个元素对应到了同一个索引，而且会有一个索引没有元素对应过去。
- 找到这个重复对应的索引，就找到了那个重复的元素；找到那个没有元素对应的索引，就找到了那个缺失的元素。
思路分析
- 用数组元素的绝对值做下标，然后让这个下标对应的元素置为负的，相当于把它标记为已访问过的元素，如果某个元素做下标时对应的元素值为负，则这个数是重复值。再次遍历数组寻找唯一没有置为负的那个元素，它的下标就是缺失的元素值。
- 假设元素是
[0..N-1]，但题目要求是[1..N]，所以需要修改部分的值才能得到正确结果。 - 时间复杂度：
O(N) - 空间复杂度：
O(1)
原理图如下：
完整代码如下：
public int[] findErrorNums(int[] nums) {
int[] res = new int[2];
// 寻找重复的元素
int length = nums.length;
for (int i = 0; i < length; i++) {
int index = Math.abs(nums[i]) - 1;
if (nums[index] >= 0) {
nums[index] *= -1;
} else {
res[0] = index+1;
}
}
// 寻找缺失的元素
for (int i = 0; i < length; i++) {
if (nums[i] > 0) {
res[1] = i + 1;
break;
}
}
return res;
}
- 对于这种数组问题，关键点在于元素和索引是成对儿出现的，常用的方法是
排序、异或、映射。 LeetCode相关题目：