面试助力，算法 101：JavaScript 描述
搜索文档…
面试助力，算法 101：JavaScript 描述
目录
写在前面
学习指南
开篇——复杂度
字符串
数学
罗马数字转整数、Fizz Buzz和计数质数
3的幂、Excel表列序号、快乐数和阶乘后的零
Pow(x, n)、两数相除、分数到小数和x的平方根
数组
链表
二叉树
动态规划
回溯算法
排序与搜索
栈和队列
结束篇
由 GitBook 提供支持
3的幂、Excel表列序号、快乐数和阶乘后的零

3的幂

给定一个整数，写一个函数来判断它是否是 3 的幂次方。
进阶： 你能不使用循环或者递归来完成本题吗？
示例 1：
1
输入: 27
2
输出: true
Copied!
示例 2：
1
输入: 0
2
输出: false
Copied!
示例 3：
1
输入: 9
2
输出: true
Copied!
示例 4：
1
输入: 45
2
输出: false
Copied!

题目分析

  • 3 的幂，顾名思义，需要判断当前数字是否可以一直被 3 整除
  • 特殊情况：如果 n === 1，即 3 的 0 次幂的情况，应输出 true

方法一 循环求解

思路
基本想法，可以利用循环解决。排除特殊情况后，用待确定的数字 n，循环除以 3，看是否能被 3 整除。
详解
1、判断特殊情况，若待定值 n 小于 1 则直接返回 false
2、循环判断待定值 n 是否可以被 3 整除
3、若不可以被 3 整除则返回 false，若可以则将该数字除以 3，直至循环结束
4、其余情况则返回 true
代码
1
/**
2
* @param {number} n
3
* @return {boolean}
4
*/
5
const isPowerOfThree = function (n) {
6
if (n < 1) {
7
return false;
8
}
9
while (n > 1) {
10
// 如果该数字不能被 3 整除，则直接输出 false
11
if (n % 3 !== 0) {
12
return false;
13
} else {
14
n = n / 3;
15
}
16
}
17
return true;
18
};
Copied!
复杂度分析
  • 时间复杂度：
    O(n)O(n)
    ​
    该解法中， while 循环耗时
    O(n)O(n)
    ，其余为
    O(1)O(1)
    ，因此总时间复杂度为
    O(n)O(n)
    。
  • 空间复杂度：
    O(1)O(1)
    ​
    该解法中，未申请额外的空间，因此空间复杂度为
    O(1)O(1)
    。

解法二 递归求解

思路
或许，我们可以考虑使用递归的方法实现。递归的思路类似于循环，只不过将循环体改为方法的递归调用。
详解
1、判断特殊情况 n === 1 时，直接返回 true
2、判断特殊情况 n <= 0 时，直接返回 false
3、若待定值 n 可以被 3 整除，则开始递归
4、若不满足上述条件，则返回 false
代码
1
/**
2
* @param {number} n
3
* @return {boolean}
4
*/
5
const isPowerOfThree = function (n) {
6
// n === 1，即 3 的 0 次幂，返回 true
7
if (n === 1) {
8
return true;
9
}
10
if (n <= 0) {
11
return false;
12
}
13
if (n % 3 === 0) {
14
// 递归调用 isPowerOfThree 方法
15
return isPowerOfThree(n / 3);
16
}
17
return false;
18
};
Copied!
复杂度分析
  • 时间复杂度：
    O(n)O(n)
    ​
    该解法中，递归耗时
    O(n)O(n)
     ，普通条件判断耗时
    O(1)O(1)
     ，整个算法时间复杂度为
    O(n)O(n)
    ​
  • 空间复杂度：
    O(n)O(n)
    ​
    该解法中，由于递归依赖于栈，因此其空间复杂度为
    O(n)O(n)
    。
方法三 神奇的解法

思路

进阶！既无循环又无递归。
既然要判断输入值是否为 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
代码
1
/**
2
* @param {number} n
3
* @return {boolean}
4
*/
5
const isPowerOfThree = function (n) {
6
if (n <= 0) {
7
return false;
8
}
9
// 求 3 的最大次幂
10
const maxPow = parseInt((Math.log(0x7fffffff) / Math.log(3)));
11
// 求 3 的 maxPow 次幂值
12
const maxValue = Math.pow(3, maxPow);
13
// 判断该值是否能整除待定值 n
14
return (maxValue % n === 0);
15
};
Copied!
复杂度分析
  • 时间复杂度：
    O(1)O(1)
    ​
    一般情况下， Math.pow 的时间复杂度为
    O(1)O(1)
    ，取整和除法的复杂度也为
    O(1)O(1)
    ，因此该解法的时间复杂度为
    O(1)O(1)
    。
  • 空间复杂度：
    O(1)O(1)
    ​
    该解法中，仅申请了 2 个常量级的额外空间，因此空间复杂度为
    O(1)O(1)
    。

Excel表列序号

给定一个Excel表格中的列名称，返回其相应的列序号。
示例
1
A -> 1
2
B -> 2
3
C -> 3
4
...
5
Z -> 26
6
AA -> 27
7
AB -> 28
8
输入: "A",
9
输出: 1
10
输入: "AB",
11
输出: 28
Copied!

方法一

思路
从末尾开始取得每一个字符对应的数 cur = c.charCodeAt() - 64（ 因为 A 的caarCode为 64） 因为有 26 个字母，所以相当于 26 进制，每 26 个数则向前进一位 数字总和 sum += 当前数 进制位数 进制位数 = 26，初始化进制位数 carry = 1
详解
  1. 1.
    创建临时变量 sum 和始化进制位数 carry
  2. 2.
    循环数组
  3. 3.
    数字总和 sum += 当前数 * 进制位数
  4. 4.
    进制位数 *= 26
1
/**
2
* @param {string} s
3
* @return {number}
4
*/
5
const titleToNumber = function (s) {
6
let sum = 0;
7
let i = s.length - 1;
8
let carry = 1;
9
while (i >= 0) {
10
const cur = s[i].charCodeAt() - 64;
11
sum += cur * carry;
12
carry *= 26;
13
i--;
14
}
15
return sum;
16
};
Copied!
复杂度分析
  • 时间复杂度：
    O(n)O(n)
    ​
    对于每个元素，通过一次遍历数组的其余部分来寻找它所对应的目标元素，这将耗费
    O(n)O(n)
    的时间。
  • 空间复杂度：
    O(1)O(1)
    ​
    由于算法中临时变量得个数与循环次数无关，所以空间复杂度为
    O(1)O(1)
    ​

方法二

思路
因为有26个字母，相当于 26 进制转 10 进制
详解
  1. 1.
    26 进制 转化 10 进制公式，ans = ans * 26 + num
  2. 2.
    比如：AB = 12* 6 +2 = 28，ZY=26 * 26+25 = 701
1
/**
2
* @param {string} s
3
* @return {number}
4
*/
5
const titleToNumber = function (s) {
6
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'];
7
const len = s.length;
8
let sum = 0;
9
for (let i = 0; i < len; i++) {
10
sum = (arr.indexOf(s[i]) + 1) * Math.pow(26, len - 1 - i) + sum;
11
}
12
return sum;
13
};
Copied!
复杂度分析
  • 时间复杂度：
    O(n)O(n)
    ​
    对于每个元素，通过一次遍历数组的其余部分来寻找它所对应的目标元素，这将耗费
    O(n)O(n)
     的时间。
  • 空间复杂度：
    O(1)O(1)
    ​
    由于算法中临时变量得个数与循环次数无关，所以空间复杂度为
    O(1)O(1)
    ​

快乐数

编写一个算法来判断一个数是不是“快乐数”。
一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。
示例
1
输入: 19
2
输出: true
3
解释:
4
1^2 + 9^2 = 82
5
8^2 + 2^2 = 68
6
6^2 + 8^2 = 100
7
1^2 + 0^2 + 0^2 = 1
Copied!

方法一 尾递归

思路

根据示例来看，函数的执行过程是一个可递归的过程，首先，我们先写一个递归函数来模拟这个执行过程，然后按照示例 输入 19 来验证编写函数正确性， 然后 输入 任意数字（比方说 99999），这时，会发现报内存溢出的错误，那这道题就变成了如何解决堆栈溢出的问题： 首先，我们要考虑的是，为什么会内存溢出？从题目中，我们可以看到"也可能是无限循环但始终变不到 1"，是"无限循环"导致内存溢出， 那我们就应该想一个方式去终结这个"死循环"。首先我们要找到这个循环的规律，怎么找？把递归内容打印（console.log）出来。这时，你会发现一个有规律的死循环。 那么，我们只要用一个变量（once）记录已经输入过的值，一旦出现第二次相同输入，就终止递归，并返回"非快乐数"的结果（false）。

详解

  1. 1.
    申请一个变量来存放已经执行过函数的"输入",如果出现重复输入，则说明进入了死循环，从"示例"来看：{19:true,82:true,100:true}
  2. 2.
    将输入 19 转化为数组（[1,9]）
  3. 3.
    将[1,9]进行平方和运算（
    12+92=821^2 + 9^2 = 82
    ）
  4. 4.
    判断平方和的结果是不是等于 1，若果是，则为"快乐数",否，则继续执行 fn 函数
  5. 5.
    直到平方和等于 1 或者判定为死循环。
1
const fn = function (n, once) {
2
if (once[n]) {
3
return false;
4
}
5
const list = n.toString().split('');
6
let result = 0;
7
once[n] = true;
8
list.forEach(val => {
9
result += Math.pow(parseInt(val, 10), 2);
10
});
11
if (result === 1) {
12
return true;
13
} else {
14
return fn(result, once);
15
}
16
};
17
​
18
/**
19
*
20
* @param {number} n
21
* @return {boolean}
22
*/
23
const isHappy = function (n) {
24
const once = {};
25
return fn(n, once);
26
};
Copied!

复杂度分析

  • 时间复杂度：
    O(log(n))O(log(n))
    ​
  • 空间复杂度：
    O(1)O(1)
    ​

方法二 尾递归

思路
其实和方法一类似，只不过终止循环的条件有所不同，输入 99，观察"函数一"执行时的输出可得，如果函数执行过程中出现 4,16,37,58,89,145,42,20 就不是快乐数， 为了稍微提高一下函数执行效率，你也可以简单的枚举以下特殊的快乐数，比方说：1，10，100。
1
// 函数一
2
const isHappy = function (n) {
3
console.log('n = ', n);
4
let result = 0;
5
const list = n.toString().split('');
6
list.forEach(val => {
7
result += Math.pow(parseInt(val, 10), 2);
8
});
9
if (result === 1) {
10
return true;
11
} else {
12
return isHappy(result);
13
}
14
};
Copied!
详解
  1. 1.
    已知非快乐数[4,16,37,58,89,145,42,20]
  2. 2.
    已知快乐数：1
  3. 3.
    将输入（19）转化为数组（[1,9]）
  4. 4.
    将[1,9]进行平方和运算（
    12+92=821^2 + 9^2 = 82
    ）
  5. 5.
    判断平方和的结果是不是等于 1，若果是，则为"快乐数",否，则继续执行 fn 函数
  6. 6.
    直到平方和等于 1 或者判定为非快乐数。
1
const isHappy = function (n) {
2
const unHappy = [4, 16, 37, 58, 89, 145, 42, 20];
3
if (n === 1) {
4
return true;
5
}
6
if (unHappy.indexOf(n) > -1) {
7
return false;
8
}
9
let result = 0;
10
const list = n.toString().split('');
11
list.forEach(val => {
12
result += Math.pow(parseInt(val, 10), 2);
13
});
14
if (result === 1) {
15
return true;
16
} else {
17
return isHappy(result);
18
}
19
};
Copied!
判断优化
可以从 unHappy 取任意一个数作为判断条件，可以减少 indexOf 函数带来的时间消耗。
1
const isHappy = function (n) {
2
if (n === 1) {
3
return true;
4
}
5
if (n === 4) {
6
return false;
7
}
8
let result = 0;
9
const list = n.toString().split('');
10
list.forEach(val => {
11
result += Math.pow(parseInt(val, 10), 2);
12
});
13
if (result === 1) {
14
return true;
15
} else {
16
return isHappy(result);
17
}
18
};
Copied!
复杂度分析
  • 时间复杂度：
    O(log(n))O(log(n))
    ​
  • 空间复杂度：
    O(1)O(1)
    ​
    事先通过规律已经找到了所有非快乐数，unHappy 的内存空间的开辟是固定的，所以空间复杂度是
    O(1)O(1)
    。

阶乘后的零

给定一个整数 n，返回 n! 结果尾数中零的数量。
示例1
1
输入: 3
2
输出: 0
3
解释: 3! = 6, 尾数中没有零。
Copied!
示例2
1
输入: 5
2
输出: 1
3
解释: 5! = 120, 尾数中有 1 个零.
Copied!

方法一 暴力法

思路
  1. 1.
    尾数中有 0 必定是是 10 的倍数
  2. 2.
    尾数中有多少个 0 就就是整个数能有多少个因子 10
  3. 3.
    因子 10 又可以拆成
    2∗52* 5
     ，因此就是找整个数字可以拆分成多少了
    2∗52 * 5
  4. 4.
    因为在因子中 2 的数量一定比 5 多，所以实际上我们只要找到因子 5 的个数就可以找到尾数中 0 的个数了，所以这个问题就可以转换成找因子 5 的个数。
详解
  1. 1.
    循环 1 ~ n，找出能被 5 整除的数字
  2. 2.
    找到能被 5 整除的数字，找该数字能被拆分成多少个因子 5
  3. 3.
    所有的个数相加就是尾数 0 的个数
1
const trailingZeroes = function(n) {
2
let count = 0;
3
for(let i = 1; i <= n; i++) {
4
let num = i;
5
if (num % 5 === 0) {
6
while(num % 5===0 && num !== 0) {
7
count += 1;
8
num = parseInt(num / 5);
9
}
10
}
11
}
12
return count;
13
}
Copied!
复杂度分析
  • 时间复杂度为:
    O(n2)O(n^2)
    ​
    因为要进行两次循环，所以时间复杂度为
    O(n2)O(n^2)
    ，当数字比较大的时候有性能问题
  • 空间复杂度：
    O(1)O(1)
    ​
    没有申请额外空间，所以空间复杂度为
    O(1)O(1)
    ​

方法二

思路
整体思路和方法一基本一致，都是找因子5的个数，只是方法二是在找因子5的个数时做文章，用耗时更少的方法来找5的个数
详解
  1. 1.
    n! 这些乘数中，每隔 5 个数，肯定会有一个数至少能拆出一个 5 因子。所以 n / 5 = 至少会出现的 5 的个数。
  2. 2.
    因为 n / 5 并不能完全算出 5 因子的个数，比如若某个数 25 = 5 * 5，分解后得到的 5 也算一个，所以能被 25 因式分解相当于会出现 2 个 5 因子，而第一步中除以 5 算个数的时候已经算了一个了，所以相当于比之前会多一个 5 因子
  3. 3.
    依此类推，能被 25 5 = 125 因式分解的相当于比之前按 25 因式分解的时候又多出一个 5 因子。能被 125 5 = 625 因式分解的相当于比按 125 因式分解时又多出一个 5 因子。还有 625 * 5 ……
    所以n! 的结果可以拆分为多少个 5 因子呢：
    n/5 + n/25 + n /125 + n/625 + …
1
function trailingZeroes(n) {
2
let count = 0;
3
while (n > 0) {
4
n = parseInt(n / 5);
5
count += n;
6
}
7
return count;
8
}
Copied!
复杂度分析：
  • 时间复杂度：
    O(log(n))O(log(n))
    ，
    遍历次数为
    n/5x=1n / 5^x = 1
    ；即
    x=log⁡5(n)x = \log_5(n)
    ，所以时间复杂度为
    O(log(n))O(log(n))
    ​
  • 空间复杂度：
    O(1)O(1)
    ​
    没有申请额外空间，所以空间复杂度为
    O(1)O(1)
    ​
以前
罗马数字转整数、Fizz Buzz和计数质数
下一个
Pow(x, n)、两数相除、分数到小数和x的平方根
最近更新 2yr ago
复制链接
内容
3的幂
Excel表列序号
快乐数
阶乘后的零