给定一个整数,写一个函数来判断它是否是 3 的幂次方。
进阶: 你能不使用循环或者递归来完成本题吗?
示例 1:
输入: 27输出: true
示例 2:
输入: 0输出: false
示例 3:
输入: 9输出: true
示例 4:
输入: 45输出: false
3 的幂,顾名思义,需要判断当前数字是否可以一直被 3 整除
特殊情况:如果 n === 1
,即 3 的 0 次幂的情况,应输出 true
思路
基本想法,可以利用循环解决。排除特殊情况后,用待确定的数字 n
,循环除以 3,看是否能被 3 整除。
详解
1、判断特殊情况,若待定值 n
小于 1 则直接返回 false
2、循环判断待定值 n
是否可以被 3 整除
3、若不可以被 3 整除则返回 false
,若可以则将该数字除以 3,直至循环结束
4、其余情况则返回 true
代码
/*** @param {number} n* @return {boolean}*/const isPowerOfThree = function (n) {if (n < 1) {return false;}while (n > 1) {// 如果该数字不能被 3 整除,则直接输出 falseif (n % 3 !== 0) {return false;} else {n = n / 3;}}return true;};
复杂度分析
时间复杂度:
该解法中, while
循环耗时 ,其余为 ,因此总时间复杂度为 。
空间复杂度:
该解法中,未申请额外的空间,因此空间复杂度为 。
思路
或许,我们可以考虑使用递归的方法实现。递归的思路类似于循环,只不过将循环体改为方法的递归调用。
详解
1、判断特殊情况 n === 1
时,直接返回 true
2、判断特殊情况 n <= 0
时,直接返回 false
3、若待定值 n
可以被 3 整除,则开始递归
4、若不满足上述条件,则返回 false
代码
/*** @param {number} n* @return {boolean}*/const isPowerOfThree = function (n) {// n === 1,即 3 的 0 次幂,返回 trueif (n === 1) {return true;}if (n <= 0) {return false;}if (n % 3 === 0) {// 递归调用 isPowerOfThree 方法return isPowerOfThree(n / 3);}return false;};
复杂度分析
时间复杂度:
该解法中,递归耗时 ,普通条件判断耗时 ,整个算法时间复杂度为
空间复杂度:
该解法中,由于递归依赖于栈,因此其空间复杂度为 。
方法三 神奇的解法
进阶!既无循环又无递归。
既然要判断输入值是否为 3 的幂,我们可以巧妙的依赖它是否能被 3 的幂的极大值整除来作为判断依据。因此首先要找到 3 的最大次幂。
计算机中最大的整数是 2147483647
,转换成 16 进制为 0x7fffffff
。Math.log(x) / Math.log(y)
方法可以求出以 y
为底,x
的对数,即 y
的多少次幂的值是 x
,我们称之为 maxPow
。由于该值不能被整除,此处 maxPow
只需取整数部分。最后,我们可以利用 Math.pow
求出 3 的幂的极大值 maxValue
,并检查该值是否能整除待确定的输入值。
详解
1、判断特殊情况 n <= 0
时,直接返回 false
2、求计算机允许情况下 3 的最大次幂, 记为 maxPow
3、求 3 的 maxPow
次幂值
4、判断 3 的 maxPow
次幂值是否能整除待定值 n
代码
/*** @param {number} n* @return {boolean}*/const isPowerOfThree = function (n) {if (n <= 0) {return false;}// 求 3 的最大次幂const maxPow = parseInt((Math.log(0x7fffffff) / Math.log(3)));// 求 3 的 maxPow 次幂值const maxValue = Math.pow(3, maxPow);// 判断该值是否能整除待定值 nreturn (maxValue % n === 0);};
复杂度分析
时间复杂度:
一般情况下, Math.pow
的时间复杂度为 ,取整和除法的复杂度也为 ,因此该解法的时间复杂度为 。
空间复杂度:
该解法中,仅申请了 2 个常量级的额外空间,因此空间复杂度为 。
给定一个Excel表格中的列名称,返回其相应的列序号。
示例
A -> 1B -> 2C -> 3...Z -> 26AA -> 27AB -> 28输入: "A",输出: 1输入: "AB",输出: 28
思路
从末尾开始取得每一个字符对应的数 cur = c.charCodeAt() - 64( 因为 A 的caarCode为 64) 因为有 26 个字母,所以相当于 26 进制,每 26 个数则向前进一位 数字总和 sum += 当前数 进制位数 进制位数 = 26,初始化进制位数 carry = 1
详解
创建临时变量 sum 和始化进制位数 carry
循环数组
数字总和 sum += 当前数 * 进制位数
进制位数 *= 26
/*** @param {string} s* @return {number}*/const titleToNumber = function (s) {let sum = 0;let i = s.length - 1;let carry = 1;while (i >= 0) {const cur = s[i].charCodeAt() - 64;sum += cur * carry;carry *= 26;i--;}return sum;};
复杂度分析
时间复杂度:
对于每个元素,通过一次遍历数组的其余部分来寻找它所对应的目标元素,这将耗费 的时间。
空间复杂度:
由于算法中临时变量得个数与循环次数无关,所以空间复杂度为
思路
因为有26个字母,相当于 26 进制转 10 进制
详解
26 进制 转化 10 进制公式,ans = ans * 26 + num
比如:AB = 12* 6 +2 = 28,ZY=26 * 26+25 = 701
/*** @param {string} s* @return {number}*/const titleToNumber = function (s) {const arr = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'];const len = s.length;let sum = 0;for (let i = 0; i < len; i++) {sum = (arr.indexOf(s[i]) + 1) * Math.pow(26, len - 1 - i) + sum;}return sum;};
复杂度分析
时间复杂度:
对于每个元素,通过一次遍历数组的其余部分来寻找它所对应的目标元素,这将耗费 的时间。
空间复杂度:
由于算法中临时变量得个数与循环次数无关,所以空间复杂度为
编写一个算法来判断一个数是不是“快乐数”。
一个“快乐数”定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是无限循环但始终变不到 1。如果可以变为 1,那么这个数就是快乐数。
示例
输入: 19输出: true解释:1^2 + 9^2 = 828^2 + 2^2 = 686^2 + 8^2 = 1001^2 + 0^2 + 0^2 = 1
根据示例来看,函数的执行过程是一个可递归的过程,首先,我们先写一个递归函数来模拟这个执行过程,然后按照示例 输入 19 来验证编写函数正确性, 然后 输入 任意数字(比方说 99999),这时,会发现报内存溢出的错误,那这道题就变成了如何解决堆栈溢出的问题: 首先,我们要考虑的是,为什么会内存溢出?从题目中,我们可以看到"也可能是无限循环但始终变不到 1",是"无限循环"导致内存溢出, 那我们就应该想一个方式去终结这个"死循环"。首先我们要找到这个循环的规律,怎么找?把递归内容打印(console.log)出来。这时,你会发现一个有规律的死循环。 那么,我们只要用一个变量(once)记录已经输入过的值,一旦出现第二次相同输入,就终止递归,并返回"非快乐数"的结果(false)。
申请一个变量来存放已经执行过函数的"输入",如果出现重复输入,则说明进入了死循环,从"示例"来看:{19:true,82:true,100:true}
将输入 19 转化为数组([1,9])
将[1,9]进行平方和运算()
判断平方和的结果是不是等于 1,若果是,则为"快乐数",否,则继续执行 fn 函数
直到平方和等于 1 或者判定为死循环。
const fn = function (n, once) {if (once[n]) {return false;}const list = n.toString().split('');let result = 0;once[n] = true;list.forEach(val => {result += Math.pow(parseInt(val, 10), 2);});if (result === 1) {return true;} else {return fn(result, once);}};/**** @param {number} n* @return {boolean}*/const isHappy = function (n) {const once = {};return fn(n, once);};
时间复杂度:
空间复杂度:
思路
其实和方法一类似,只不过终止循环的条件有所不同,输入 99,观察"函数一"执行时的输出可得,如果函数执行过程中出现 4,16,37,58,89,145,42,20 就不是快乐数, 为了稍微提高一下函数执行效率,你也可以简单的枚举以下特殊的快乐数,比方说:1,10,100。
// 函数一const isHappy = function (n) {console.log('n = ', n);let result = 0;const list = n.toString().split('');list.forEach(val => {result += Math.pow(parseInt(val, 10), 2);});if (result === 1) {return true;} else {return isHappy(result);}};
详解
已知非快乐数[4,16,37,58,89,145,42,20]
已知快乐数:1
将输入(19)转化为数组([1,9])
将[1,9]进行平方和运算()
判断平方和的结果是不是等于 1,若果是,则为"快乐数",否,则继续执行 fn 函数
直到平方和等于 1 或者判定为非快乐数。
const isHappy = function (n) {const unHappy = [4, 16, 37, 58, 89, 145, 42, 20];if (n === 1) {return true;}if (unHappy.indexOf(n) > -1) {return false;}let result = 0;const list = n.toString().split('');list.forEach(val => {result += Math.pow(parseInt(val, 10), 2);});if (result === 1) {return true;} else {return isHappy(result);}};
判断优化
可以从 unHappy 取任意一个数作为判断条件,可以减少 indexOf 函数带来的时间消耗。
const isHappy = function (n) {if (n === 1) {return true;}if (n === 4) {return false;}let result = 0;const list = n.toString().split('');list.forEach(val => {result += Math.pow(parseInt(val, 10), 2);});if (result === 1) {return true;} else {return isHappy(result);}};
复杂度分析
时间复杂度:
空间复杂度:
事先通过规律已经找到了所有非快乐数,unHappy 的内存空间的开辟是固定的,所以空间复杂度是 。
给定一个整数 n,返回 n! 结果尾数中零的数量。
示例1
输入: 3输出: 0解释: 3! = 6, 尾数中没有零。
示例2
输入: 5输出: 1解释: 5! = 120, 尾数中有 1 个零.
思路
尾数中有 0 必定是是 10 的倍数
尾数中有多少个 0 就就是整个数能有多少个因子 10
因子 10 又可以拆成 ,因此就是找整个数字可以拆分成多少了
因为在因子中 2 的数量一定比 5 多,所以实际上我们只要找到因子 5 的个数就可以找到尾数中 0 的个数了,所以这个问题就可以转换成找因子 5 的个数。
详解
循环 1 ~ n,找出能被 5 整除的数字
找到能被 5 整除的数字,找该数字能被拆分成多少个因子 5
所有的个数相加就是尾数 0 的个数
const trailingZeroes = function(n) {let count = 0;for(let i = 1; i <= n; i++) {let num = i;if (num % 5 === 0) {while(num % 5===0 && num !== 0) {count += 1;num = parseInt(num / 5);}}}return count;}
复杂度分析
时间复杂度为:
因为要进行两次循环,所以时间复杂度为,当数字比较大的时候有性能问题
空间复杂度:
没有申请额外空间,所以空间复杂度为
思路
整体思路和方法一基本一致,都是找因子5的个数,只是方法二是在找因子5的个数时做文章,用耗时更少的方法来找5的个数
详解
n! 这些乘数中,每隔 5 个数,肯定会有一个数至少能拆出一个 5 因子。所以 n / 5 = 至少会出现的 5 的个数。
因为 n / 5 并不能完全算出 5 因子的个数,比如若某个数 25 = 5 * 5,分解后得到的 5 也算一个,所以能被 25 因式分解相当于会出现 2 个 5 因子,而第一步中除以 5 算个数的时候已经算了一个了,所以相当于比之前会多一个 5 因子
依此类推,能被 25 5 = 125 因式分解的相当于比之前按 25 因式分解的时候又多出一个 5 因子。能被 125 5 = 625 因式分解的相当于比按 125 因式分解时又多出一个 5 因子。还有 625 * 5 ……
所以n! 的结果可以拆分为多少个 5 因子呢:
n/5 + n/25 + n /125 + n/625 + …
function trailingZeroes(n) {let count = 0;while (n > 0) {n = parseInt(n / 5);count += n;}return count;}
复杂度分析:
时间复杂度:,
遍历次数为 ;即 ,所以时间复杂度为
空间复杂度:
没有申请额外空间,所以空间复杂度为