⭐️个人主页：摸鱼の文酱博客主页?‍♂️
?博客领域：java编程基础,mysql
?写作风格：干货,干货,还是tmd的干货
?精选专栏：【Java】【mysql】 【算法刷题笔记】
?博主的码云gitee，平常博主写的程序代码都在里面。
?支持博主：点赞?、收藏⭐、留言?
?作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

今日学习内容:第1讲 幂和对数

由于这个系列的博客内容是参照博主英雄哪里出来的付费专栏《算法零基础100讲》
为避免侵犯博主权益 ,本章学习内容参考《算法零基础100讲》(第1讲) 幂和对数

收获

本章学习主要是利用数学知识:幂和对数的概念来解决一些类似判断某个数是否是另一个数的幂的题目

例如:
给你一个整数 n ,要求写一个函数来判断它是否是 3 的幂.n 是 3 的幂要求有整数 x ,使得 3 ^x= n.

以前的思路一般都会用循环或者是递归的方式去处理 n ,看最后得到的数是否是1(x⁰=0)
像这样:

bool isPowerOfThree(int n){
    if(n==0){
        return false;
    }
//送进来的数是0，返回false
    if(n==1){
        return true;
    }
//送进来的数是1，返回true
    int a=n%3;
    if(a!=0){
    return false;
}
//新建一个变量a用来存储n除3的余数，余数不为0就没有被整除，返回false
return isPowerOfTwo(n/3);
//把该循环中的n/3送进下一循环
}

但是今天的学习给我提供了一个新的思路:利用换底公式

x是以 3 为底, n 的对数,也就是log₃n,可以利用换底公式将其换为以 2 为底的式子计算
源码如下:

bool isPowerOfThree(int n){
    if(n == 0) {
        return false;                          
    }
    int x = (int)(log2(n) / log2(3) + 1e-8);   
    return fabs(n - pow(3, x)) < 1e-8;       
}

练习题目:

?231. 2 的幂

问题描述:
给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。

如果存在一个整数 x 使得 n == 2^x ，则认为 n 是 2 的幂次方。

? 思路一:递归

bool isPowerOfTwo(int n){
    if(n==0){
        return false;
    }
    if(n==1){
        return true;
    }
    if(n%2 !=0){
    return false;
}
return isPowerOfTwo(n/2);
}

? 思路二:换底公式

这道题其实用递归就可以的,底数本来就是2,也不需要换底的,这里就当是练习一下

bool isPowerOfTwo(int n){
    if(n == 0) {
        return false;                         
    }
    int x = (int)(log2(n) / log2(2) + 1e-8);  
    return fabs(n - pow(2, x)) < 1e-8;        
}

? 思路三:位运算

由于 2 的幂的特点:n & (n-1) = 0

bool isPowerOfTwo(int n){
     return n > 0 and n & (n - 1) == 0     
}

?231. 3 的幂

问题描述:
给你一个整数 n，请你判断该整数是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。

如果存在一个整数 x 使得 n == 3^x ，则认为 n 是 3 的幂次方。

? 思路一:循环

bool isPowerOfThree(int n){
	if (n <= 0) return false;
        while (n % 3 == 0) n /= 3;
        return n == 1;
}

? 思路二:换底公式

bool isPowerOfThree(int n){
      if(n == 0) {
        return false;                          
    }
    int x = (int)(log2(n) / log2(3) + 1e-8);   
    return fabs(n - pow(3, x)) < 1e-8;    
}

?231. 4 的幂

问题描述:
给你一个整数 n，请你判断该整数是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。

如果存在一个整数 x 使得 n == 4^x ，则认为 n 是 4 的幂次方。

? 思路一:循环

bool isPowerOfThree(int n){
	if (n <= 0) return false;
        while (n % 4 == 0) n /= 4;
        return n == 1;
}

? 思路二:换底公式

bool isPowerOfThree(int n){
      if(n == 0) {
        return false;                          
    }
    int x = (int)(log2(n) / log2(4) + 1e-8);   
    return fabs(n - pow(4, x)) < 1e-8;    
}