js算法题随手记

todo: 归类整理

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 countPrime (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]

思路一：暴力破解法

1
2
3
4
5
6
7
8
9
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)

思路二：两趟哈希表

1
2
3
4
5
6
7
8
9
10
11
12
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)

思路三：一趟哈希表

1
2
3
4
5
6
7
8
9
10
11
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
// 多维数组扁平化 
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('')) 
})

11.single number: 有一个非空数字数组，其中只有一个数字出现了奇数次，其他均出现偶数次，问如何使用优秀的时空复杂度快速找到这个数字

示例：
输入：[1,2,2]
输出：1

1
2
3
4
5
6
7
8
9
function singleNumber (arr) {
    let n = arr.length;
    let result = 0;

    for (; n--;) {
        result ^= arr[n];
    }
    return result
}

关键点：异或
异或的性质：两个数字异或的结果a^b是将 a 和 b 的二进制每一位进行运算，得出的数字。 运算的逻辑是 如果同一位的数字相同则为 0，不同则为 1。

异或的规律：

  • 任何数和本身异或则为0
  • 任何数和 0 异或是本身

12.设计一个函数，从一个不重复数组中随机取n个元素，返回所有可能。比如arr = [1,2,3,4], n = 3, 返回: [1,2,3], [1,2,4], [2,3,4], [1, 3, 4]

如果是[1,2,3,4,5]取出3个，那么可能性就有10种 C(5,3)= C(5,2)
公式：
全排列 P(n,m)=n!/(n-m)!
组合排列 P(n,m)=n!/m!/(n-m)!
C(5,2)=5!/2!3!=54321/[(21)(32*1)]=10
这是使用了循环加递归做出了组合排序

1
2
3
4
5
6
7
8
9
10
function getCombination (arr, num) {
    let res = [];
    (function f(t, a, n){
        if (n == 0) return res.push(t);
        for (let i = 0, len = a.length; i <= len - n; i++) {
              f(t.concat(a[i]), a.slice(i + 1), n - 1);
        }
    })([], arr, num);
    return res;
}

13.不用+、-、*、/实现加减乘除运算

通过位运算。

加

比如2 add 3，转为二进制：

1
2
10    // 2
11  // 1

10 ^ 11 -> 01，结果正好是相加后非进制的值，10 & 11 -> 10，结果是进制的值，因此可以：

1
2
3
4
5
6
7
8
function add (num1, num2) {
    while (num2 !== 0) {
        let temp = num1;
        num1 = (num1 ^ num2) 
        num2 = (temp & num2) << 1;
    }
    return num1;
}

递归的写法：

1
2
3
function add (num1, num2) {
    return num2 === 0 ? num1 : add(num1 ^ num2, (num1 & num2) << 1);
}

减

加法知道了减法就很简单了。2 sub 3 -> 2 add -3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function minus (num1, num2) {
    return add(num1, ~num2);
}

// or
function minu2 (num1, num2) {
    num2 = ~num2;
    while (num2 !== 0) {
        let temp = num1;
        num1 = (num1 ^ num2) 
        num2 = (temp & num2) << 1;
    }
    return num1;
}

乘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function multi(num1, num2){
    let i = 0;
    let res = 0;
    while (num2 !== 0) {    // 乘数为0则结束
        // 处理乘数当前位
        if((num2 & 1) === 1){
            res += (num1 << i);
            num2 = num2 >> 1;
            i++; // i记录当前位是第几位
        } else {
            num2 = num2 >> 1;
            i++;
        }
    }
    return res;
}

除

1
2
3
4
5
6
7
8
9
function sub(num1, num2) {
        let res = -1;
        if (num1 < num2) {
            return 0;
        } else {
            res = sub(minus(num1, num2), num2) + 1;
        }
        return res;
    }

14.大数相乘

leetcode >>

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
/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
let multiply = function(num1, num2) {
    //判断输入是不是数字
  if(isNaN(num1) || isNaN(num2)) return ''
  let len1 = num1.length,
    len2 = num2.length
  let ans = []
  
  //这里倒过来遍历很妙,不需要处理进位了
  for (let i = len1 - 1; i >= 0; i--) {   
    for (let j = len2 - 1; j >= 0; j--) {
      let index1 = i + j, 
          index2 = i + j + 1
      let mul = num1[i] * num2[j] + (ans[index2] || 0)
      ans[index1] = Math.floor(mul / 10) + (ans[index1] || 0)
      ans[index2] = mul % 10
    }
  }
    
    //去掉前置0
  let result = ans.join('').replace(/^0+/,'')
    
    //不要转成数字判断，否则可能会超精度！
  return !result ? '0' : result
}

15.数组转为树结构

如：['a', 'b', 'c', 'd', 'e'] -> {"e":{"d":{"c":{"b":{"a":"a"}}}}}

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
/**
 * @function getArrTree1
 * @description 数组转为树结构，递归版
 * @param {string[]} arr
 * @return {object}
 */
function getArrTree1 (arr) {
    if (!arr || !arr.length) return {};
    if (arr.length === 1) {
        return {
            [arr[0]]: arr[0]
        }
    }
    
    let last = arr.pop();
    return {
        [last]: getArrTree1(arr)
    }
}
/**
 * @function getArrTree2
 * @description 数组转为树结构，遍历版
 * @param {string[]} arr
 * @return {object}
 */
function getArrTree2 (arr) {
    if (!arr || !arr.length) return {};
    let i = arr.length - 1;
    let resObj = {},
        temp = resObj;
    while (i) {
        temp = temp[arr[i]] = {};
        i--;
    }
    temp[arr[i]] = arr[i];
    return resObj
}

// getArrTree2([]) -> {}
// getArrTree2(['a', 'b', 'c', 'd', 'e']) -> {"e":{"d":{"c":{"b":{"a":"a"}}}}}
// getArrTree2(['a']) -> {"a":"a"}

16.找两个数最大公约数

1
2
3
function mygcd(x,y){
  return y == 0 ? x : mygcd(y, x % y)
}