算法一 - 简书

重要的Math函数：

Math.ceil() 向上取整
Math.floor() 向下取整
Math.abs 求绝对值
Math.max() 最大值
Math.min() 求最小值
Math.random() 0-1之间的随机数
Math.sqrt() 平方根
Math.pow() 求幂
Math.round() 四舍五入

集合Set一些操作

new Set()
add(element） // 添加、去重
has(element) // 判断是否存在
delete(element) // 删除
values() //返回ierator

例1:

在一个分页表格中，给定每页显示条数pageSize和元素index的序号，求页码。

const page= Math.ceil((index+1)/pageSize)

例2：

数组最值

const A=[1, 2, 3 ,5, 6]
const max= Math.max(...A)

例3:

判断一个数是否素数(N2 <= n <=(N+1)2)

function is_prime(n){
  if(n<=1) return false
  const N = Math.floor(Math.sqrt(n))
  let is_prime = true
  for(let i =2; i<=N;i++){
      if(n%i === 0)
      is_prime = false
      break
  }
  return is_prime
}

例4：

括号匹配问题：给定括号表达式，中间只有[]和(),判断是否平衡
基于栈的解法：先入先出

function is_balance(str) {
  const [first, ...others] = str;
  const stack = [first];
  while (others.length > 0) {
    const c = stack[stack.length - 1];
    const n = other.shift(); //取剩余数组中的第一个
    if (!match(n === c)) {
      stack.push(n);
    } else {
      stack.pop();
    }
  }
  return stack.length === 0;
}

function match(n, c) {
  return (c == "[" && n == "]") || (c == "(" && n == ")");
}

例5：

子数组和整除：写一个函数，给定一个数组，判断数组中某一项或者任意多项的和，是否被另外一个整数整除。
比如： solve([3,5,8], 13) = true 、//solve([3,9], 15)=false
相当于判断子数组的余数和：求数组的全部组合，求余数，然后去重
solve([7, 8 ,2], 7)等价于([0, 1, 2],7)

//方法一
function solve(arr, N) {
  const s = new Set();
  for (let i = 0; i <= arr.length; i++) {
    for (let j = i + 1; j <= arr.length; j++) {
      const remain = arr.slice(i, j).reduce((x, y) => x + y, 0) % N;
      s.add(remain)
    }
  }
  return s.has(0);
}
//方法2

子问题结构：

数组a1,a2,...an对数字N的子数组和余数集合定义为Sn={S1, S2, S3,...,Sm}.比如[1,2,3] 的S3={1, 2, 3, 4, 5, 6}, S2={1,2,3},Sk和S(k+1)存在子问题关系
S(k-1)有px项，Sk= S(k-1) U ak%N U {1<= i <= p|(si +ak)% N}
N = 6S2 = [1,2,3]S3=[1, 2, 3]U[4,5,6]

例6：

分组

const studentInGroups = students.reduce((groups, student) => {
  groups[student.group_id] = [...(groups[student.group_id] || []), student];
  return groups;
}, {});  //返回三数组项

补充数组操作Ramda

npm install ramda
import R from 'ramda'

zip 两两对齐

R.zip([1, 2, 3], [a, b,c]) ---> [[1, 'a'], [2, 'b'], [3, 'c']]
flatten 展平
高维数组：[1, [2,3,[4]]] => [1, [2,3,[4]]] + '' ---> 1,2,3,4----> eval(${[1, [2,3,[4]]] + ' ' })---> [1, 2,3,4]

converge 汇聚

var average = R.converge(R.divide, [R.sum, R.length])
average([1,2,3,4,5,6,7]) // =>4
var strangeConcat = R.converge(R.concat, [R.toUpper, R.toLower])
strangeConcat('yodel') //=> 'YODALyodal'

innerJoin 联合

R.innerJoin((record, id) => record.id === id, [{id: 824, name:'aaa'}, {id: 956, name:'bbb'}, {id: 177, name: 'ccc'}], [177]) ===> [{id: 177, name: 'ccc'}]

interSperse 间隔插入

R.intersperse('n', ['ba', 'a', 'a']) ==> ['ba', 'n', 'a', 'n', 'a']

groupBy 分组成对象

R.groupBy(student => student.group_id, students)

groupWith 分组成数组

迭代器和生成器

迭代器Iterator是一种设计模式，提供了一种遍历内容的方法，而不需要关心内部构造，生成器Generator本身也是一种设计模式，用于构造复杂对象。js中的生成器，用于构造迭代器

1. 迭代器的遍历一
const  val = null
while(!(val = it.next()).done){
 console.log(val)
}
// {value: 1, done:false}
// {value: 2, done:false}
// {value: 3, done:false}

2. 迭代器的遍历二
Array.from(arrayLike, mapFn, thisArg);
// * arrayLike: 想要转换成数组的伪数组对象或可迭代对象
// * mapFn: 如果指定了该参数, 新数组中的每个元素会执行该回调函数
// * thisArg: 可选参数， 执行回调函数mapFn时的this对象
const it3 = s.values();
const arr = Array.from(Array(5), it3.next, it3).map((x) => x.value);
console.log(arr); //=>[1,2,3,4,5]


3. 构造斐波拉契数列
function fibonacci(){
    let a = 1, b =1
    yield a;
    yield b;
    while(true){
      const t = b;
      b = a +b;
      a =t
      yield b
    }
}
const it = fibonacci()
const feb10 = Array.from(Array(10), it.next, it).map(x => console.value)
console.log(feb10) //=>[1,1,2,3,5,8,11,13,21,34,55]

Genarator处理异步逻辑

节省空间、分散执行片段（节省单位时间的处理量）

笛卡尔积

集合X和Y的笛卡尔积可以表示为：X X Y= {(x, y) | x 属于 y}, 写一个函数，求数组的笛卡尔积
例如：[1, 2]X['a', 'b'] =[[1, 'a'], [1, 'b'],[2, 'a'],[2,'b]]

function cartesian_product(...Matrix) {
  if (Matrix.length === 0) return;
  if (Matrix.length === 1) return Matrix[0];
  return Matrix.reduce((A, B) => {
    const product = [];
    for (let i = 0; i < A.length; i++) {
      for (let j = 0; j < B.length; j++) {
        product.push(Array.isArray(A[i] ? [...A[i], B[j]] : [A[i], B[j]]));
      }
    }
    return product;
  });
}

中文排序

将含有中文字符的数组按照拼音排序

['王成成'，'王峰', '蒋雪', '李敏'].sort((a, b) => a.localeCompare(b, 'zh')

链式操作

数组中很多操作可以构成链式操作，类似...map(...).filter(...).sort(...).map(...)

链式操作的对象方法返回类型是自身的。比如map是属于数组的方法，他返回了数组，所以可以构成链式结构。语义清晰、思考方便，但是需要考虑性能以及空间问题。

拷贝数组

js中的push/pop/shift/unshift/splice等在原始数据的基础上进行修改，concat/slice/map/reduce都会对原始数据进行浅拷贝