js算法题随手记

1.判断一个数组是否有重复元素,如果重复则返回true,反之返回false

如[1, 2, 3, 4, 5] -> false,[1, 2, 3, 1] -> true。

1
2
3
4
5
6
7
8
9
10
11
// best
function judge (arr) {
let _obj = {};

for(let i in arr) {
if(_obj[arr[i]]) return true;
hash[arr[i]] = true;
}

return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// other
function judge1 (arr) {
let _nary = arr.sort();

for(let i = 0, len = arr.length; i < len; i++){
if (_nary[i] === _nary[i + 1]) return true;
}

return false;
}

function judge2 (arr) {
return /(\x0f[^\x0f]+)\x0f[\s\S]*\1/.test("\x0f" + arr.join("\x0f\x0f") + "\x0f");
}

function judge3 (arr) {
let _str = arr.join(',') + ',';
for (let i = 0, len = arr.length; i < len; i++) {
if (~_str.replace(arr[i] + ',', '').indexOf(arr[i] + ',')) return true;
}

return false;
}

2.计算n以内素数的个数(n为非负自然数)

如 3 -> 1, 30 -> 10。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function count (num) {
let pHash = {};
let count = 0;

for (let k = 2; k < n; k++) {
pHash[k] = true;
}

for (let i = 2; i * i < n; i++) {
if (!pHash[i]) continue;
for (let j = i * i; j < n; j += i) {
pHash[j] = false;
}
}

for (let l = 2; l < n; l++) {
if (pHash[l]) count++;
}

return count;
}

3.阶乘(n为非负自然数)

1
2
3
4
5
6
7
function factorial (num) {
if(num <= 1) {
return 1;
} else {
return num * arguments.callee(num - 1);
}
}

尾递归优化

1
2
3
4
function factorial(n, total = 1) {
if (n === 1) return total;
return factorial(n - 1, n * total);
}

4.将字符串转换为 spinal case。Spinal case 是 all-lowercase-words-joined-by-dashes 这种形式的,也就是以连字符连接所有小写单词。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function spinalCase(str) {
// "It's such a fine line between stupid, and clever."
// --David St. Hubbins
function replacer(match){
return ' ' + match;
}
if (str[0] <= 'z'&& str[0] >= 'a'){
str = str.replace(/[A-Z]+/g, replacer); //这里是调用了上面加空格的方法
}
str = str.replace(/[^a-zA-Z]/g, "-").toLowerCase();
return str;
}

spinalCase('This Is Spinal Tap');
spinalCase('thisIsSpinalTap');
spinalCase('The_Andy_Griffith_Show');
spinalCase('Teletubbies say Eh-oh');

5.给一个正整数num,返回小于或等于num的斐波纳契奇数之和。

斐波纳契数列中的前几个数字是 1、1、2、3、5 和 8,随后的每一个数字都是前两个数字之和。
例如,sumFibs(4)应该返回 5,因为斐波纳契数列中所有小于4的奇数是 1、1、3;

1
2
3
4
5
6
7
8
9
10
11
12
function sumFibs(num) {
var total = 1,
i = 0,
a = 0,
b = 1;
while(i < num){
a = [b, b = a + b][0];
if(b <= num && b % 2 == 1) total += b;
i++;
}
return total;
}

6.两数之和

给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

思路一:暴力破解法

function twoSum(nums, target) {
for (let i = 0; i < nums.length; i++) {
for (let j = 0; j < nums.length; j++) {
if (i !== j && nums[i] + nums[j] === target) {
return [i, j]
}
}
}
}
由于进行了双重循环,时间复杂度是O(n^2), 空间复杂度O(1)

思路二:两趟哈希表

function twoSum(nums, target) {
const map = {}
for (const [i, n] of nums.entries()) {
map[n] = i
}
for (const [i, n] of nums.entries()) {
let number = target - n
if (number in map) {
return [i, map[number]]
}
}
}
先用一个哈希表存储数组的值于对应数组下标,然后再遍历数组寻找结果
时间复杂度O(n), 空间复杂度O(n)

思路三:一趟哈希表

var twoSum = function(nums, target) {
const map = {}
for (let i = 0; i < nums.length; i++) {
const n = nums[i]
if (target - n in map) {
return [map[target - n], i]
} else {
map[n] = i
}
}
}
在给哈希表添加元素的同时寻找有没有符合目标的答案,如果有就直接返回,没有就继续构造哈希表。
时间复杂度O(n), 空间复杂度O(n)

7.数组降维


[[1, 2], [3, [4, [5, 6]]]]
->
[1, 2, 3, 4, 5, 6]

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
57
58
59
60
/*
* @Author: Mr.live
* @Date: 2018-01-23 14:55:22
* @Last Modified by: Mr.live
* @Last Modified time: 2018-01-23 14:56:20
*/

// 多维数组扁平化
var arr=[1,2,[3,4,[5,6,7]],9,[10,11]]

// 1) 方法一 循环数组+递归调用
function steamroller (arr){
// 1.创建一个新数组,保存扁平后的数据
var newArr=[];
// 2.for循环原数组
for(var i=0;i<arr.length;i++){
if(Array.isArray(arr[i])){
// 如果是数组,调用steamroller 将其扁平化
// 然后在push 到newArr中
newArr.push.apply(newArr,steamroller(arr[i]))
}else {
// 反之 不是数组,直接push进newArr
newArr.push(arr[i])
}
}
// 3.返回新的数组
return newArr
}
console.log(steamroller(arr)) // [ 1, 2, 3, 4, 5, 6, 7, 9, 10, 11 ]

// 2) 方法二 利用apply+some
// 利用arr.some判断当数组中还有数组的话,递归调用steamroller2扁平函数(利用apply扁平), 用concat连接,最终返回arr;
function steamroller2(arr){
while(arr.some(item=> Array.isArray(item))){
arr=[].concat.apply([],arr)
}
return arr
}
console.log(steamroller2(arr))

// 3) 方法三 reduce方法
// 当数组中还有数组的话,递归调用steamroller3扁平函数(利用reduce扁平), 用concat连接,最终返回arr.reduce的返回值;
function steamroller3(arr){
return arr.reduce((prev,next)=>{
return prev.concat(Array.isArray(next)?steamroller3(next):next)
},[])
}
console.log(steamroller3(arr))

// 4) 方法四 es6 展开运算符
// 利用arr.some判断当数组中还有数组的话,递归调用flatten扁平函数(利用es6展开运算符扁平), 用concat连接,最终返回arr;

function steamroller4(arr){
while(arr.some(item=> Array.isArray(item))){
// arr=[].concat.apply([],arr)
arr=[].concat(...arr)
}
return arr
}
console.log(steamroller4(arr))

更多方式可见

8.请实现一个 add 函数,满足以下功能

1
2
3
4
5
6
add(1); 	// 1
add(1)(2); // 3
add(1)(2)(3); // 6
add(1)(2, 3); // 6
add(1, 2)(3); // 6
add(1, 2, 3); // 6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 实现 1:

function currying(fn, length) {
length = length || fn.length; // 注释 1
return function (...args) { // 注释 2
return args.length >= length // 注释 3
? fn.apply(this, args) // 注释 4
: currying(fn.bind(this, ...args), length - args.length) // 注释 5
}
}

// 实现 2:
const currying = fn =>
judge = (...args) =>
args.length >= fn.length
? fn(...args)
: (...arg) => judge(...args, ...arg)

其中注释部分

  • 注释 1:第一次调用获取函数 fn 参数的长度,后续调用获取 fn 剩余参数的长度
  • 注释 2:currying 包裹之后返回一个新函数,接收参数为 …args
  • 注释 3:新函数接收的参数长度是否大于等于 fn 剩余参数需要接收的长度
  • 注释 4:满足要求,执行 fn 函数,传入新函数的参数
  • 注释 5:不满足要求,递归 currying 函数,新的 fn 为 bind 返回的新函数(bind 绑定了 …args 参数,未执行),新的 length 为 fn 剩余参数的长度

9.「移动零」,给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序

示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

说明:

  • 必须在原数组上操作,不能拷贝额外的数组。
  • 尽量减少操作次数。
1
2
3
4
5
6
7
8
9
10
11
12
13
function zeroMove(array) {
let len = array.length;
let j = 0;
for(let i=0;i<len-j;i++){
if(array[i]===0){
array.push(0);
array.splice(i,1);
i --;
j ++;
}
}
return array;
}

10.打印出 1 - 10000 之间的所有对称数 例如:121、1331 等

1
2
3
[...Array(10000).keys()].filter((x) => { 
return x.toString().length > 1 && x === Number(x.toString().split('').reverse().join(''))
})