Hexo

simple but delicate theme for Hexo

函数式编程

2021/07/06

函数是一等公民

函数是一等公民的表现：

  1. 函数可以储存为变量
    1
    let four = () => 4
  2. 函数可作为数组的一个元素
    1
    let four = [4, () => 4]
  3. 函数可作为对象的成员
    1
    let four = {num: 4, func: () => 4}
  4. 函数可以在使用时直接创造出来
    1
    let four = 2 + (() => 2)()
  5. 函数可作为参数传递给另一个函数
    1
    2
    3
    let four = (num, f) => num + f()

    four(2, () => 2)
  6. 函数可以被另一函数返回
    1
    let four = () => () => 4

其实，满足第5点或第6点的函数被称为 高阶函数

Applicative编程

Applicative编程是函数式编程的一部分(特殊的函数式编程形式)，其典型的代表就是 map 、reduce 以及 filter 函数。

Applicative编程的其它实例:

  • reduceRight
  • find
  • reject
  • all
  • any
  • sortBy | groupBy | countBy

函数柯里化

函数柯里化可以保存某些需要多次调用的操作，还可以将多个参数分割，每次只传递一个参数，让函数看起来就像是在一步步的操作数据。

一阶柯里化：

1
2
3
function curry(func) {
    return arg => func(arg)
}

使用示例：

1
2
const add3 = curry((a) => a+3)
add3(2)

二阶柯里化（这里选择从右到左）：

1
2
3
function curry2(func) {
  return first => last => func(last, first);
}

使用示例：

1
2
3
const add = curry2((a, b) => a+b)
add(2)(3) // 5
add('curry!')('hello ') // 'hello curry!'

三阶柯里化（从右到左调用参数）：

1
2
3
function curry3(func) {
  return first => middle => last => func(last, middle, first);
}

使用示例：

1
2
3
const splice = curry3((a, b, c) => c + b + a)
splice(2)(3)(4) // 9
splice('hello ')('curry')('!') // 'hello curry!'

curry => partial => compose

递归

相互递归

实现判断奇偶性就是一个相互递归的很好的例子：

1
2
3
4
5
6
7
8
function odd(n) {
    if(n === 0) return false;
    return even(Math.abs(n) - 1);
}
function even(n) {
    if(n === 0) return true;
    return odd(Math.abs(n) - 1);
}

递归实现深克隆

简单版本：

1
2
3
4
5
6
7
8
9
10
function deepClone(obj) {
    if(x == null || typeof obj !== 'object') {
        return obj;
    }
    let temp = new obj.constructor();
    for(let key in obj) 
        if(obj.hasOwnProperty(key))
            temp[key] = deepClone(obj[key])
    return temp;
}

JS函数式库

可编译为js的函数式编程语言

775. 全局倒置与局部倒置

kartjim | 2021/07/04

暴力法+维护最小值+数学法=循序渐进

暴力法

看到题目，没有任何技巧，直接暴力！🐶 :dog:

1
2
3
4
5
6
7
8
var isIdealPermutation = function(nums) {
    for(let i = 0;i<nums.length-2;i++) {
        for(let j = i+2;j<nums.length;j++) {
            if(nums[i] > nums[j]) return false;
        }
    }
    return true;
};

维护最小值法

稍微分析一下，我们在 i 位置上，只要找到从 i+2 往后的值中有小于 i 位上的值即可；那么只需要从 i+2 往后的值中最小的值与 nums[i] 比较即可！

可以从后往前遍历，有利于保存后缀最小值。

1
2
3
4
5
6
7
8
var isIdealPermutation = function(nums) {
    let min = nums[nums.length-1];
    for(let i = nums.length-3;i>=0;i--) {
        if(nums[i] > min) return false;
        min = Math.min(min, nums[i+1]);
    }
    return true;
};

数学证明

接着分析：

  • 在 i=0 的位置上，只要其大于等于 2，那就一定能在 i=2 及往后的位置中找到小于 i 的值。
  • 在 i=1 的位置上，只要其大于等于 3，那就一定能在 i=3 及往后的位置中找到小于 i 的值。
  • 以此类推，可以看到，只要保证 nums[i] <= i+2 即可！
1
2
3
4
5
6
7
8
9
10
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var isIdealPermutation = function(nums) {
    for(let i = 0;i<nums.length;i++) {
        if(Math.abs(nums[i] - i) >= 2) return false;
    }
    return true;
};

547. 省份数量

2021/06/04

题目来源：LeetCode 547. 省份数量

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

示例1：

输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2

示例2：

输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出：3

限制：

  • 1 <= n <= 200
  • n == isConnected.length
  • n == isConnected[i].length
  • isConnected[i][j] 为 1 或 0
  • isConnected[i][i] == 1
  • isConnected[i][j] == isConnected[j][i]

并查集解法

使用quick find

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
class UnionFind {
  constructor(len) {
    this.root = Array(len).fill(0).map((_, i) => i);
  }
  find(x) {
    return this.root[x];
  }
  union(x, y) {
    let rootx = this.find(x), rooty = this.find(y);
    if(rootx !== rooty) {
      for(let i = 0;i<this.root.length;i++) {
        if(this.root[i] === rootx) this.root[i] = rooty;
      }
    }
  }
  getNums() {
    return new Set(this.root).size;
  }
}

var findCircleNum = function(isConnected) {
    // quick find
    const uf = new UnionFind(isConnected.length);
    for(const [i, vals] of isConnected.entries()) {
        for(const [j, val] of vals.entries()) {
            if(val === 1) uf.union(i, j);
        }
    }
    return uf.getNums();
};

基于路径压缩的按秩合并优化的「并查集」

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
class UnionFind {
  constructor(len) {
    this.root = Array(len)
      .fill(0)
      .map((_, i) => i);
    this.rank = Array(len).fill(1);
    this.size = len;
  }
  // 路径压缩优化版本的 find 函数
  find(x) {
    if (x === this.root[x])  return x;
    return this.root[x] = this.find(this.root[x]);
  }
  // 按秩合并优化的 union 函数
  union(x, y) {
    let rootx = this.find(x), rooty = this.find(y);
    if(rootx !== rooty) {
      if(this.rank[rootx] > this.rank[rooty]) {
        this.root[rooty] = rootx;
      } else if(this.rank[rootx] < this.rank[rooty]) {
        this.root[rootx] = rooty;
      } else { // ===
        this.root[rootx] = rooty;
        this.rank[rooty] += 1;
      }
      this.size--;
    }
  }
}

var findCircleNum = function(isConnected) {
    const n = isConnected.length;
    const uf = new UnionFind(n);
    for(let i = 0;i<n;i++) {
        for(let j = 0;j<isConnected[i].length;j++) {
            if(isConnected[i][j] === 1) uf.union(i, j);
        }
    }
    return uf.size;
};

DFS解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {number[][]} isConnected
 * @return {number}
 */
var findCircleNum = function(isConnected) {
    let visited = new Set(),re = 0;
    for(let i = 0;i<isConnected.length;i++){
        if(!visited.has(i)){
            dfs(isConnected,visited,i);
            re++;
        }
    }
    return re;
};
function dfs(data,visited,i){
    for(let j = 0;j<data.length;j++){
        if(data[i][j] === 1 && !visited.has(j)){
            visited.add(j);
            dfs(data,visited,j);
        }
    }
}
长风破浪会有时，直挂云帆济沧海