函数式是一种很好用的编程方式，使用函数式编程一开始可能还不是很习惯，但在你习惯之后会发现这能帮你编写出简洁且充满表达能力的代码。下面介绍一下，日常开发中运用函数式的一些技巧以及函数式的原理。

compose

1

compose(...fns)

compose基本是大部分函数式都会用到的函数，他的作用是把传入的方法从右往左，把前一个的返回值返回给下一个，redux的中间件就是基于compose实现的。

源码

compose 的源码也比较简单，但是思维方式可能会比较绕。简单来说就是通过reduce让函数一层一层嵌套，传进的函数会嵌套在最里面，所以会最先执行。

1
2
3
4
5
6

function compose(...fns) {
  if (fns.length === 0) return args => args;
  if (fns.length === 1) return fns[0];
  return fns.reduce((f,g) => (...args) => f(g(...args)))
}

常见的用法，除了有reduce这种中间件的用法外，还可以是比方说我们有几个步骤，每个步骤需要把上一个步骤的值传进来，我们就可以利用compose来简化我们的写法。

1
2
3
4
5
6

compose(
  step3,
  step2,
  step1,
)('begin')

cancellable

开发中可能会碰到这样的需求，需要让一些函数变成可取消的。这部分的逻辑其实是可以复用的。下面看看可以如何去实现这样一个功能。

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

// 首先我们可以实现一个类似axios里的CancelToken
function createCancelToken() {
  let cancel;
  const promise = new Promise((_, reject) => {
    cancel = reject;
  });
  return {
    promise,
    cancel
  }
}

function cancellable(fn, cancelPromise) {
  return (...args) => {
    return Promise.race([fn.apply(null, ...args), cancelPromise]) 
  }
}

async function request() {}
const cancelToken = createCancelToken();
const cancellableRequest = cancellable(request, cancelToken.promise);

cancellableRequest();
// 调用这个函数即可取消上面的cancellableRequest
cancelToken.cancel();

concurrent

用来控制函数并发量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

function concurrent(count, fn) {
  const semaphore = new Semaphore(count);
  
  return async function (...args) {
    try {
      await semaphore.acquire();
      return await fn(...args);
    } finally {
      semaphore.release();
    }
  }
}

async function request() {}
// 并发量只有1的
const concurrentRequest = concurrent(1, request);
concurrentRequest().then(() => {})
// 只有等上一个结束了这个函数才会执行
concurrentRequest().then(() => {})

retryable

碰到错误就重试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

function retryable(fn, times) {
  return async (...args) => {
    let retryTimes = 0;
    while (true) {
      try {
        const res = await fn(...args);
        return res;
      } catch (e) {
        retryTimes++;
        if (retryTimes >= times) {
          throw e;
        }
      }
    }
  }
}

async function request(){}
const retryableRequest = retryable(request, 5);
// 重试5次后任然失败则会抛出错误
retryableRequest()

结合

稍微改造一下，我们就可以通过compose来结合上面几个函数最终生成一个功能强大的request

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

const cancellable = (cancelPromise) => (fn) => {
  return (...args) => {
    return Promise.race([fn.apply(null, ...args), cancelPromise]) 
  }
}

const concurrent = (count) => (fn) => {
  const semaphore = new Semaphore(count);

  return async function (...args) {
    try {
      await semaphore.acquire();
      return await fn(...args);
    } finally {
      semaphore.release();
    }
  }
}

const retryable = (times) => (fn) => {
  return async (...args) => {
    let retryTimes = 0;
    while (true) {
      try {
        const res = await fn(...args);
        return res;
      } catch (e) {
        retryTimes++;
        if (retryTimes >= times) {
          throw e;
        }
      }
    }
  }
}
const cancelToken = createCancelToken();

// 这样我们就可以得到一个同时拥有这三个能力的request函数了
const strongRequest = compose(
  cancellable(cancelToken.promise),
  concurrent(2),
  retryable(5),
)(request)

先面试或者实际开发的需求中，我们常常会碰到需要控制并发量的需求，那么如何才能优雅的去实现这个需求呢，下面简单介绍几种实现方式。

比方说我们有个需求是，需要去请求多个请求，但是并发的请求量不得超过5.

1
2

const requests = [request1, request2, request3, request4,request5, request6, request7, request8];

方式一

简单通过分组来实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// 切分数组
function chunk(array, size = 1) {
  size = Math.max(Number.parseInt(size), 0)
  const length = array == null ? 0 : array.length
  if (!length || size < 1) {
    return []
  }
  let index = 0
  let resIndex = 0
  const result = new Array(Math.ceil(length / size))

  while (index < length) {
    result[resIndex++] = slice(array, index, (index += size))
  }
  return result
}

async function concurrentRequest(requests, limit) {
  const chunks = chunk(requests, limit);
  for (let i = 0; i < chunks.length; i++) {
    const chunk = chunks[i];
    await Promise.all(chunk.map((request) => request()));
  }
}

但是这样有个问题，虽然限制了最大的并发量，但是每次得等每个分片的请求都结束了才能进入到下一个循环，这样就不能最大效率的利用并发量了。

Semaphore

为了最大化的利用并发量，我们可以用一个叫做Semaphore的类，像java,c++,c#经常会使用它来实现并发量的控制

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

class Semaphore {
  resolves = [];
  limit = 0;
  cur = 0;
  constructor(limit) {
    this.limit = limit;
  }
  
  acquire() {
    return new Promise((resolve) => {
      this.cur++;
      if (this.cur < this.limit) {
        resolve();
      } else {
        this.resolves.push(resolve);
      }
    });
  }
  
  release() {
    this.cur --;
    if (this.resolves.length > 0) {
      this.resolves.shift()();
    }
  }
}

async function concurrentRequest(requests, limit) {
  const semaphore = new Semaphore(limit);
  await Promise.all(requests.map(async (request) => {
    await semaphore.acquire();
    await request().finally(() => {
      semaphore.release();
    })
  }))
}

这样相当于形成了一个并发池，先进入到池子里的方法会执行，当池子满了后，后面进入的方法，就会等待池子释放信号才能进入，先进入的方法在执行完后，调用 semaphore.release 通知池子有一个空位了，后面的方法通过 await semaphore.acquire 来接收这个信号并继续执行，我们可以看到这个用法的代码也是非常的简单直观，并且保证了并发量一直维持在这没有浪费

typescript 的基本使用方式基本已经可以覆盖到我们绝大部门的使用场景，但是我们也任会碰到一些特殊的场景需要我们使用一些高级的ts的用法，下面总结一下我常用的一些用法。

keyof

keyof 能够帮助我们快速生成 interface 的 key 的类型。

1
2
3
4
5
6
7

interface A {
  age: number;
  name: string;
}

type AKeys = keyof A; // age | name

利用 keyof 提取接口

有时候我们可能会碰到需要提取接口部门结构的需求，这时候我们可以利用 ts 提供的pick类型

1
2
3
4
5
6
7
8
9
10
11
12

type pick<T, K extends keyof T> = {
  [key in K]: T[key]
}

interface A {
  age: number;
  name: string;
  sex: string;
}

type C = pick<A, 'age' | 'sex'>; // { age: number; sex: string; }

多态

常用的使用场景就是我们可能需要根据传入值的类型来确定返回值的类型

1
2
3
4
5
6

interface Create {
  (val: number): number
  (val: string): string
  (val: Date): Date
}

有个典型的例子就是eventBus，我们可能需要在不同的事件监听不同的类型的数据和广播不同类型的数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

enum EventName {
  sayName,
  run,
}
interface EventBusOn {
  (event: EventName.sayName, cb: (params: {name: string}) => void): void
  (event: EventName.run, cb: (params: {duration: number}) => void): void
}

interface EventBusEmit {
  (event: EventName.sayName, params: {name: string}): void
  (event: EventName.run, params: {duration: number}): void
}

interface EventBus {
  on: EventBusOn;
  emit: EventBusEmit;
}

const eventBus: EventBus = new Vue();
eventBus.on(EventName.sayName, ({name}) => {
  console.log(name);
});
eventBus.emit(EventName.sayName, {name: 'sd'});

这样还有个问题，就是我们每次增加一个事件类型，都需要去修改 EventBusOn 和 EventBusEmit 两个接口，但是他们的修改模式基本是固定的，结合前面的两个技巧，我们也可以优化这个接口。

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

enum EventName {
  sayName,
  run,
}
interface EventParams {
  [EventName.sayName]: {
    name: string;
  };
  [EventName.run]: {
    duration: number;
  };
}
interface EventBusOn {
  <T extends EventName>(event: T, cb: (params: EventParams[T]) => void): void
}

interface EventBusEmit {
  <T extends EventName>(event: T, params: EventParams[T]): void
}
interface EventBus {
  on: EventBusOn;
  emit: EventBusEmit;
}

const eventBus: EventBus = new Vue();
eventBus.on(EventName.sayName, ({name}) => {
  console.log(name);
})
eventBus.emit(EventName.sayName, {name: 'name'})

利用 is 帮助类型推断

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

interface A {
  type: string;
  data: {
    name: string;
  }
}
interface B {
  type: string;
  data: boolean;
}
function isA(params: any) {
  return params.type === 'A';
}
// 这里能够帮助推断出类型
function isA2(params: any): params is A {
  return params.type === 'A';
}
function test(params: A | B) {
  if (isA(params)) {
    params.data
  }
  if ((isA2(params))) {
    params.data
  }
}

泛型的类型限制

1
2
3
4

interface A<T extends {length: number;}> {
  data:T;
}

这里就会限制了类型A的data属性必须是有length属性，且length类型为number

infer 关键字

ts 官方是有提供相关的几个工具类型，也有用到 infer

1
2
3
4
5
6
7
8
9
10

/**
 * Obtain the parameters of a constructor function type in a tuple
 */
type ConstructorParameters<T extends new (...args: any) => any> = T extends new (...args: infer P) => any ? P : never;

/**
 * Obtain the return type of a function type
 */
type ReturnType<T extends (...args: any) => any> = T extends (...args: any) => infer R ? R : any;

这里我们可以通过 infer 关键字做类型推断，意思有点想，比方说 ReturnType 中我们如果传入的函数的返回值类型是R，则我们把R返回，这个关键字目前来看使用场景还比较少

之前在 leetcode 上看到了一道题 Super Egg Drop, 刚好之前看到过一到很类似的题，就是 google 的一道经典的面试题。这里记录一下自己整个的解题思路。

google 原题

给你两个鸡蛋，它们有可能都在某一层楼往下摔就会摔碎，也可能从一百层楼摔下来没事。有座100层的建筑，要你用这两个鸡蛋通过最少的次数确定哪一层是鸡蛋摔碎的临界点。每次实验即使没摔碎也不会对鸡蛋有损耗。

思路

这是一道很经典的需要用到动态规划的题目，我们每一次扔鸡蛋的结果都会影响我们后续扔的次数，比方说我们上来就从 90 层扔，如果碎了，我们就得从1楼一层一层往上扔到90层才能试出结果，如果没碎，我们只需要在 90 ~ 100 这 10 层做实验即可。

要用动态规划的来解这道题，我们首先要列出问题中的状态
每次我们扔鸡蛋的时候，可能会出现两种状态

• 摔碎，这时下一个鸡蛋就要从最底层一个一个往上试才能试出结果
• 没碎，则我们需要根据剩余的楼层数来决策出我们下一次丢鸡蛋的楼层数

我们假设第一次我们从 x 层楼往下扔，如果鸡蛋没碎，下一次我们往上走 k 层楼再扔，根据我们的假设我们可以绘制出一个这样的决策树。

为了让最坏的情况不太坏，我们必须要保证每一次的决策最后所需要的次数都尽可能的相等。也就是
1 + k = x。所以每次鸡蛋没碎，我们都要再上一次上升楼层数的基础减少1。

如何确认第一次扔的高度

我们假设我们每次扔鸡蛋都没有碎，第一次从x层开始扔,我们最后一次就必须在100层楼扔了。可以得到式子 x + x - 1 + x - 2 … + 1 >= 100,根据等差数列求和，我们可以得到 x * (x + 1)/2 >= 100,
得到 x >= 13.45,因为 x 只能取整数，所以第一次我们从14层楼开始扔，得到最坏情况下，我最多需要扔14次可以确认临界点。

放宽到一般情况，n 层楼 2 个鸡蛋，我们可以得到 x + x - 1 + x - 2 … + 1 >= n
最后算出 x >=

Super Egg Drop

Super Egg Drop 这道题是 google 这道题的升级版。这里的是给定 K 个鸡蛋，N层楼让你求出最小的次数是多少。

我们还是按照动态规划的思路来列出问题中的状态：

• K = 0的时候，我们是试不出来的
• K = 1时，我们只能从1楼一层一层往上试，次数为楼层高度 n
• K = 2时，情况和上面一样
• k > 2时，需要我们单独分析了

我们设 dp[k][n] 为 k 个鸡蛋，n 层楼时的最优次数。

• k = 0 , dp[k][n] = 0
• k = 1, dp[k][n] = n
• k = 2, dp[k][n] =

当 k > 2时

假设我们还剩 m 个鸡蛋，还需要实验 n 层楼，此时 1 <= n <= h, 假设我们已经知道了 1 ~ n 层最优解，假设这时候第一次丢的高度为 y ，丢的时候会出现两种情况, 然后可以列出动态方程

碎了

则此时的最优解为 dp(m - 1, y - 1) + 1

没碎

则此时的最优解为 dp(m, n - y) + 1

由此我们可以得到 dp(m, n) = min(max(dp(m - 1, y - 1), dp(m, n - y)) + 1), 1<=y< n，由此我们可以递推的得到 dp(K,N)

JS 实现源码

这题后面还需要优化，由于复杂度较高，需要一定的基础，暂时没有继续优化下去

推荐一个人的博客，把这题分析的非常透彻，有兴趣的可以看看
博客地址

很多人可能都做过 html 的拖动，但是估计做 react-native 的拖动的人就不是特别多了。这里分享一下之前做的一个组件的设计思路。后面主要写了一些伪代码，主要是提供一个写这个组件的思路，具体的源码可以查看下面这个地址。

源码地址：
react-native-draggable-grid

关键 api

在讲关键算法之前先说一下需要用的几个关键方法和参数

react-native 提供了一个 PanResponder 用于识别手势操作

onPanResponderMove

onPanResponderMove: (event, gestureState) => {}

gestureState

• x0 当响应器产生时的屏幕横坐标, 响应器一直没释放的话，这个值是一直不变的
• y0 当响应器产生时的屏幕纵坐标，响应器一直没释放的话，这个值是一直不变的
• moveX 最近一次移动时，手指在屏幕上相对于屏幕的x坐标，屏幕最左上角坐标为0，0
• moveY 最近一次移动时，手指在屏幕上相对于屏幕的y坐标，屏幕最左上角坐标为0，0

开始

我们这个组件有一个需要注意的是，组件会被限制在只能在一定的区域内拖动，不能超过这个区域。

第一步

首先我们需要在组件构造函数里实例化一个 panResponder

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

this.panResponderCapture = false;
this.panResponder = PanResponder.create({
      //否在触摸开始时想成为响应器？
      onStartShouldSetPanResponder:() => true,

      // 这两个用于设置是否成为响应器，当手指在视图上移动的时候回不断的调用者两个方法
      onMoveShouldSetPanResponder:() => this.panResponderCapture,
      onMoveShouldSetPanResponderCapture:() => this.panResponderCapture,

      // 返回一个布尔值，决定当前组件是否应该阻止原生组件成为JS响应者
      // 默认返回true。目前暂时只支持android。
      onShouldBlockNativeResponder:() => false,

      //其他组件想成为响应器。这个视图应该释放应答吗？返回 true 就是允许释放
      onPanResponderTerminationRequest:() => false,

      // 手势相应开始时触发的
      onPanResponderGrant:this.onStartDrag.bind(this),

      // 手势移动时触发的
      onPanResponderMove:this.onHandMove.bind(this),

      // 手指释放时触发
      onPanResponderRelease:this.onHandRelease.bind(this),
    });

第二步

将 GestureResponderHandlers 赋给对应的组件，为了较简单的去定位元素，我们选择了用 absolute 定位。

1
2
3
4
5
6

<View
  ref={'test'}
  style={{width:100,height:100,position:'absolute',backgroundColor:'red'}}
  {...this.panResponder.panHandlers}
/>

第三步

这一步主要是设置 currentPosition.setOffset({x,y,});, 这个的作用是，以后每次我们调用 setValue 的时候都会调用在其基础上加上x,y,后面会详细讲解为什么要这样设置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

private onStartDrag(nativeEvent:GestureResponderEvent, gestureState:PanResponderGestureState) {
   const activeItem = this.getActiveItem();
   if (!activeItem) return false;
   this.props.onDragStart && this.props.onDragStart(activeItem.itemData);
   const {x0, y0, moveX, moveY} = gestureState;
   const activeOrigin = this.blockPositions[this.orderMap[activeItem.key].order];
   const x = activeOrigin.x - x0;
   const y = activeOrigin.y - y0;

   activeItem.currentPosition.setOffset({
     x,
     y,
   });
   this.activeBlockOffset = {
     x,
     y
   };
   activeItem.currentPosition.setValue({
     x:moveX,
     y:moveY,
   })
 }

第四步

这一步主要是计算出手指拖动的位置，然后重新设置 view 的left和right，后面详细讲解一下整个的计算思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

private onHandMove(nativeEvent:GestureResponderEvent, gestureState:PanResponderGestureState) {
    const activeItem = this.getActiveItem();
    if (!activeItem) return false;
    const {moveX, moveY} = gestureState;

    const yChokeAmount = Math.max(0, (this.activeBlockOffset.y + moveY) - (this.state.gridLayout.height - this.state.blockHeight));
    const xChokeAmount = Math.max(0, (this.activeBlockOffset.x + moveX) - (this.state.gridLayout.width - this.state.blockWidth));
    const yMinChokeAmount = Math.min(0, this.activeBlockOffset.y + moveY);
    const xMinChokeAmount = Math.min(0, this.activeBlockOffset.x + moveX);

    const dragPosition = {
      x:moveX - xChokeAmount - xMinChokeAmount,
      y:moveY - yChokeAmount - yMinChokeAmount,
    };
    activeItem.currentPosition.setValue(dragPosition);
  }

我们来看一下我们从下面这个位置，移动到上面这个这个位置是如何计算出新的位置的坐标。新的y等于 y - (moveY1 - moveY2) = y -moveY1 + moveY2,我们onStartDrag的setOffset做的其实就是先把y - moveY1 这部分算出来缓存起来。后面我们只需要直接加上最新moveY即为最终结果。

现在再来看一下如何把组件限制在一定区域内移动：

最上边界

我们先看纵坐标我们能移动到的最上面的位置。y的值最小为0，即要控制offsetY + moveY >= 0

如果组件移动超过了限制区域，newY = moveY + offsetY，newY 是个负值，此时我们需要把newY向下偏移到0

最下边界

要控制vie移动的最下面区域之上，我们需要控制 offsetY + moveY <= parentHeight - blockHeight

如果区域超出了最下边的底线，超出值等于 (offsetY + moveY - (parentHeight - blockHeight)), 如果超出的话这个值为正值，我们的offsetY + moveY需要减去这个值，不超出的话则是负值

偏移算法

上面接触到最上边界和最下边界同时只会发生一个，我们可以通过修正offsetY + moveY来达到把y限制在一定区域内。

1
2
3
4
5
6
7
8

// 上偏移调整值
const yMinChokeAmount = Math.min(0, this.activeBlockOffset.y + moveY);

// 下偏移调整值
const yChokeAmount = Math.max(0, (this.activeBlockOffset.y + moveY) - (this.state.gridLayout.height - this.state.blockHeight));

// 偏移调整后的y
const y = moveY - yChokeAmount - yMinChokeAmount;

x 的偏移调整也是同理。

最后

最后就是在手指释放的时候将 panResponderCapture 设置回 false

1
2
3
4

private onHandRelease() {
    this.panResponderCapture = false;
}

组件还有涉及到数据同步，定位，排序等算法，这里就不做细讲了，有兴趣的可以去看源码研究一下。-

概念

协议

1、HTTP 协议（HyperText Transfer Protocol，超文本传输协议）：是客户端浏览器或其他程序与Web服务器之间的应用层通信协议 。

2、HTTPS 协议（HyperText Transfer Protocol over Secure Socket Layer）：可以理解为HTTP+SSL/TLS， 即 HTTP 下加入 SSL 层，HTTPS 的安全基础是 SSL，因此加密的详细内容就需要 SSL，用于安全的 HTTP 数据传输。

加密算法

1、对称加密

有流式、分组两种，加密和解密都是使用的同一个密钥。

2、非对称加密

加密使用的密钥和解密使用的密钥是不相同的，分别称为：公钥、私钥，公钥和算法都是公开的，私钥是保密的。非对称加密算法性能较低，但是安全性超强，由于其加密特性，非对称加密算法能加密的数据长度也是有限的。

3、哈希算法

将任意长度的信息转换为较短的固定长度的值，通常其长度要比信息小得多，且算法不可逆。例如：MD5、SHA-1、SHA-2、SHA-256 等

4、数字签名

签名就是在信息的后面再加上一段内容（信息经过hash后的值），可以证明信息没有被修改过。hash值一般都会加密后（也就是签名）再和信息一起发送，以保证这个hash值不被修改。

https 流程

数字证书和数字签名

数字证书是由权威机构颁发给服务器方，通常包含名称，过期时间，发布者等信息，服务器通过提供证书证明自己身份，就像人出示身份证一样

为了证明证书的可靠性，需要用到数字签名技术。证书颁发方将证书中的版本号，序列号，签名算法描述，颁发机构，对象名称，对象公钥等通过颁发者的私钥加密后生成数字签名

当客户端(浏览器)接收到服务器发来的证书后，根据颁发方的公钥(通常已预装在浏览器，对于非权威证书颁发者会出现警告)，解密签名与证书对照，确认证书没有变化。

通常 SSL 证书中包含的具体内容有：

-（1）证书的发布机构CA
-（2）证书的有效期
-（3）公钥
-（4）证书所有者
-（5）签名

SSL握手通过4次完成

1.ClientHello

客户端向服务器提供

1. 支持的协议版本, TLS1.0-1.3/SSL
2. 一个用于生成对称加密的随机数
3. 支持的加密方法
4. 压缩算法

ServerHello

服务器回复

1. 确认使用的协议版本
2. 第二个用于生成对称加密的随机数
3. 确认使用的加密方法，比如RSA公钥加密
4. 服务器证书

客户端响应

客户端回复

1. 最后一个用于生成对称加密的随机数
2. 编码改变通知，表示随后的信息都将用双方商定的加密方法和密钥发送
3. 客户端握手结束通知，表示客户端的握手阶段已经结束。这一项同时也是前面发送的所有内容的hash值，用来供服务器校验

服务器响应

1. 编码改变通知，表示随后的信息都将用双方商定的加密方法和密钥发送
2. 服务器握手结束通知，表示服务器的握手阶段已经结束。这一项同时也是前面发送的所有内容的hash值，用来供客户端校验

之后所有内容就交由SSL层使用对称密钥加密后传递

题目链接：518. Coin Change 2

我的源码：源码

最近看到这道题，但是看网大部分教程感觉思路都写的不是特别的详细。分享一下个人的解题思路。

题目：

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

示例 1:

1
2
3
4
5
6
7

输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

一开始，我想到的是用动态规划的思路去解决这道题，假设dp[n] 为凑成 n 的组合数，最后发现思维上无法找到动态方程。参考了，别人的解决方案发现需要用两个变量来解决这个问题。

思路

设dp[i][j] 为用前 i 种硬币达到总金额 j 的硬币组合数。对于dp[i][j],我们可能会出现两种情况达到效果，第一种是我们没有使用第i种硬币达到j元的组合数，第二种是使用了第i种硬币达到j的组合数。

• 没用使用第i种硬币的组合数: dp[i - 1][j]
• 使用了第i种硬币的组合数:dp[i][j - conin[i]], j >= conin[i]

得到动态方程: dp[i][j] = dp[i-1][j] + j >= coin[i] ? dp[i][j - coin[i]] : 0

优化

其实我们并不需要记录所有的状态，我们只需要记录每增加一枚硬币带来的改变。
以 amount = 5，coins = [1,2,5] 为例。我们可以用 dp[n] 记录当前使用硬币对应钱组合数。显然dp[0] = 1是一直成立的。

当我们什么硬币都不使用的时候

使用硬币 1，只用 n >= 1 会受到影响

加上使用硬币 2，只用 n >= 2 会受到影响

加上使用硬币 5，只用 n >= 5 会受到影响

如何求dp[n]

假设我们要求加上使用第j种币时的dp[n], 当前的dp[n]可以看做是不使用第j种币得到 n 的组合数。根据前面的公式我们可以知道，我们只需要加上使用第j种币时的组合数即可，即加上dp[n - coin[j]];代码也非常精炼。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

/*
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
var change = function(amount, coins) {
    const dp = Array.from({length:amount + 1}).map(() => 0);
    dp[0] = 1;
    for (let i = 0; i < coins.length; i++) {
        for (let j = coins[i]; j <= amount; j++) {
            dp[j] += dp[j - coins[i]];
        }
    }
    return dp[amount];
};

有一个笑话，世界上有10种人，一种是看得懂二进制的，一种是看不懂的。
如果你看懂了这个笑话，这篇文章就是适合你读的了

Single Number

leetcode 上有一道这样的题，Single Number，题目是要你要找到数组中唯一只存在一个的数字，其他数字都出现两次。这道题目非常的简单，我们可以用 hash 表来记录所有数字的次数，然后找到次数为1的那个数字。如果用二进制来解决这道题效率会快很多。

二进制的解法

二进制中有一个操作符叫做位异或，他的作用是两个位数字相同则为0，不同则为1，即 1^1=0，0^0=0，1^0=1，0^1=1；

通过这个运算符的特点我们可以知道，任何一个数对自己位异或操作，得到的结果都是 00000000，00000000对任意数字位异或得到的都是那个数字。并且 A ^ B ^ C = C ^ B ^A，这个操作符是满足交换律的。下面看一下 js 的简单解法：

1
2
3
4
5
6
7
8

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    return nums.reduce((res, cur) => res ^ cur);
};

毒药问题

有 8 个一模一样的瓶子，其中有 7 瓶是普通的水，有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在，你只有 3 只小白鼠和一星期的时间，如何检验出哪个瓶子里有毒药？

解决思路

我们用二进制给每瓶水进行编号，编号分别为，000,001,010,011,100,101,110,111,分别对应1-8的瓶子，然后让第一只老鼠喝第一位为1的，第二只老鼠喝第二位为1的，第三只老鼠喝第三位为1的，假设第四瓶水有毒，即011有毒

• 第一只老鼠喝了 100，101，110，111，结果：没死，记作0
• 第二只老鼠喝了 010，011，110，111，结果：死了，记作1
• 第三只老鼠喝了 001，011，101，111，结果：死了，记作1

根据死亡结果，刚好是第四瓶水011，这只是一个巧合吗，恐怕不是的，我们可以用数学的思维来证明一下这个问题

证明

每只老鼠喝了毒药只会出现两种情况死或者不死，一只老鼠可以验证两瓶药有没毒，即2^1,两只老鼠可以验证2^2瓶药，三只老鼠可以验证2^3瓶药，那么要怎么去验药呢

• 我们让每只老鼠喝某一位为1的的所有药，如果那只老鼠死了则说明毒药的某一位编号为1，比方说第一只老鼠喝了所有第一位为1的毒药死了，则说明毒药的第一位编号为1，如果没死，则说明毒药的那一位编号为0
• 这里如果三只老鼠都没死，则说明毒药的三位编号都为0，刚好是三只老鼠都每没喝的第一瓶。

拓展问题

有 1000 个一模一样的瓶子，其中有 999 瓶是普通的水，有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在，你只有 10 只小白鼠和一星期的时间，如何检验出哪个瓶子里有毒药？

根据上面的问题，我们能够知道 2 ^ 10 = 1024 > 1000,也是通过对每个瓶子进行二进制编号即可检验出哪个瓶子有毒。

问题升级

现在，有意思的问题来了：如果你有两个星期的时间，为了从 1000 个瓶子中找出毒药，你最少需要几只老鼠？注意，在第一轮实验中死掉的老鼠，就无法继续参与第二次实验了。

拓展问题思路

我们要达到的目的是用尽可能少的老鼠，在两周之内找到结果，所以我们必须要进行两轮的实验，那么每只老鼠可能就会出现三种情况，第一轮死掉，第二轮死掉，第二轮活着，上面一题老鼠会出现两种情况用的是二进制，那么这一题很明显我们需要用到三进制。3 ^ 6 = 729, 3 ^ 7 = 2187, 很明我们至少是需要7只老鼠。

如何喂药

• 还是和前面一样，第一轮的时候，我们让每只老鼠喝某一位为编号为2的药，如果某只老鼠死了，则说明毒药的那一位编号为2，如果老鼠全死了，我们连第二轮都不用了，直接可以确定毒药的编号为2222222。
• 第二轮如果还剩多少只老鼠，则说明毒药有多少位的编号为0或者1，我们剩k只老鼠，k位二进制数需要确认，因为那几位数已经排除了是2的可能性。则由回到了上一题，我们继续用上一轮的喂法即可。

称重问题

27个小球。其中一个比其他小球都要重一点。给你一个天平，最多称3次，找出这个特殊的小球。

思路

这题也是需要用到三进制的思路来解决的，我们每次称可能出现三种状态左边重，右边重，一样重，3 ^ 3 刚好27，所以我们是可以在3次内找到这个小球。

如何称

先给每个球编号000,001,002,010,…,222

• 第一次称第一位为2的和第一位为1的所有小球，他们同样都是9个，哪边重则说明，较重的小球的第1为几，如果一样重则说名第一位为0
• 第二次称第二位为2的和第二位为1的所有小球，他们也同样都是9个，哪边重则说明，较重的小球的第2位为几，如果一样重则说名第二位为0
• 第三次称第三位为2的和第三位为1的所有小球，他们也同样都是9个，哪边重则说明，较重的小球的第3位为几，如果一样重则说名第三位为0

经过三次称重我们就可以找到较重的哪一个小球了。

总结

面对这种问题，其实解决思路都大通小异，都是需要找到问题关键状态，通过关键状态的数量我们可以知道需要用到多少进制来解决问题。然后根据题目制定方案，来确定每一位的状态码最终得到结果。

hash 表

哈希表也叫散列表，我们在中使用的对象就是一种hash结构。哈希表根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

hash表的结构

hash表的结构本质上是结合了数组和链表两种结构。

数组：寻址容易，插入和删除困难，需要预先给定数组的大小
链表：寻址困难，插入和删除容易，不需要预先给定空间

hash 表的可以看做是一个存储链表的数组。

hash 函数

我们对哈希表进行put操作的时候，底层会对 key 用hash函数映射到数组中。哈希函数需要具有以下几个特点：

• 运算过程要尽量简单高效，以提高哈希表的插入和检索效率；
• 哈希函数应该具有较好的散列型，以降低哈希冲突的概率；
• 哈希函数应具有较大的压缩性，以节省内存。

常用的方法有以下几种：

• 直接地址法：以关键字的某个线性函数值为哈希地址，可以表示为hash(K)=aK+C;优点是不会产生冲突，缺点是空间复杂度可能会较高，适用于元素较少的情况
• 除留余数法：它是由数据元素关键字除以某个常数所留的余数为哈希地址，该方法计算简单，适用范围广，是经常使用的一种哈希函数
• 数字分析法：该方法是取数据元素关键字中某些取值较均匀的数字来作为哈希地址的方法，这样可以尽量避免冲突，但是该方法只适合于所有关键字已知的情况，对于想要设计出更加通用的哈希表并不适用
• 平方求和法：对当前字串转化为Unicode值，并求出这个值的平方，去平方值中间的几位为当前数字的hash值，具体取几位要取决于当前哈希表的大小。
• 分段求和法：根据当前哈希表的位数把所要插入的数值分成若干段，把若干段进行相加，舍去调最高位结果就是这个值的哈希值。

hash 冲突

当两个不同key通过hash函数映射到了数组同一个地址中，此时就存在了hash冲突。

哈希冲突主要与两个因素有关：

• 填装因子，填装因子是指哈希表中已存入的数据元素个数与哈希地址空间的大小的比值，a=n/m ; a越小，冲突的可能性就越小，相反则冲突可能性较大；但是a越小空间利用率也就越小，a越大，空间利用率越高，为了兼顾哈希冲突和存储空间利用率，通常将a控制在0.6-0.9之间，
• 与所用的哈希函数有关，如果哈希函数得当，就可以使哈希地址尽可能的均匀分布在哈希地址空间上，从而减少冲突的产生，但一个良好的哈希函数的得来很大程度上取决于大量的实践，

解决 hash冲突

一般使用拉链法来解决这个问题。即不在数组中直接存储value而是存储一个链表，当存在hash冲突的时候只需要在冲突的位置的结尾加多一个节点。

扩容

一般我们会预先设定一个临界值，当达到临界值会对hash表进行扩容操作，不过扩容操作是非常损耗性能的

随着前端工程越来越复杂化，简单的设计模式已经无法满足我们急剧扩张的功能需求。
在后端的开发中我们经常会听到IOC容器，而前端中却很少看到使用。学习 IOC 容器，其实本质上就是在学习依赖倒置这一设计原则。

依赖倒置

首先我们先来了解一下什么是依赖倒置，比方说我们要开发一辆车子,我们先设计轮子，然后设计底盘，然后设计车身，然后设计车子，
这时, 底盘依赖轮子，车身依赖底盘，车子依赖车身，我们看看伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Wheel {
    constructor() {
    }
}
class Chassis {
    constructor() {
        this.wheel = new Wheel();
    }
}
class Body {
    constructor() {
        this.chassis = new Chassis();
    }
}
class Car {
    constructor() {
        this.body = new Body();
    }
}

这时我们突然需要实例车子的时候能够修改车子轮子的大小，代码就会变成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Wheel {
    constructor(size) {
        this.size = size;
    }
}
class Chassis {
    constructor(size) {
        this.wheel = new Wheel(size);
    }
}
class Body {
    constructor(size) {
        this.chassis = new Chassis(size);
    }
}
class Car {
    constructor(size) {
        this.body = new Body(size);
    }
}

这样代码牵一发而动全身，对我来说代码的可维护性就非常差了

如何解决这个问题呢，我们反过来设计，先设计车子在设计车身，底盘，轮子。
这样依赖就倒转过来了，车身依赖与车子，底盘依赖与车身，轮子依赖与底盘，下面看看伪代码

这里我们通过依赖注入的方式来实现依赖倒置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Wheel {
    constructor(size) {
        this.size = size;
    }
}
class Chassis {
    constructor(instance:Wheel) {
        this.wheel = instance;
    }
}
class Body {
    constructor(instance:Chassis) {
        this.chassis = instance;
    }
}
class Car {
    constructor(instance:Body) {
        this.body = instance;
    }
}

这样当我们需要修改轮子的时候就不用再去修改底盘，车身，车子了，我们只需要单独修改轮子就可以了
但是这样还有一个问题，就是我们构建车子实例的时候回非常麻烦,我们需要先构建轮子，底盘，车身，才能构建好车子，实际开发中这样重复的工作量也是非常大的

1
2
3
4

const my_wheel = new Wheel(2);
const my_chassis = new Chassis(my_wheel);
const my_body = new Body(my_chassis);
const my_car = new Car(my_body);

IOC 容器就可以帮我们解决这样一个问题

IOC 通过配置，和注入的方式可以帮助我们完成上面这一个过程，我们只需要告诉 IOC 容器我们需要的类他就会根据配置自动帮我们完成依赖注入这一步。
我们大概可以像这样子去获取车子实例 const my_车子 = ioc_container.get(车子)

这里有个实现的非常好的js的ioc容器 InversifyJS

具体的用法可以参考下面的伪代码

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74

// 第一步： 先申明接口和类型

interface IWheel {
    private size:number;
}

interface IChassis {
    private wheel:IWheel;
}

interface Ibody {
    private chassis:IChassis;
}

interface ICar {
    private body:IBody;
}

const TYPES = {
    wheel:Symbol.for('wheel'),
    chassis:Symbol.for('chassis'),
    body:Symbol.for('body'),
    car:Symbol.for('car'),
};

// 第二步：申明依赖关系
import { injectable, inject } from "inversify";
import "reflect-metadata";

@injectable()
class Wheel implements IWheel {
    constructor(size) {
        this.size = size;
    }
}

@injectable()
class Chassis implements IChassis{
    constructor(@inject(TYPES.wheel)instance:IWheel) {
        this.wheel = instance;
    }
}

@injectable()
class Body implements IBody{
    constructor(@inject(TYPES.chassis)instance:IChassis) {
        this.chassis = instance;
    }
}

@injectable()
class Car implements Icar{
    constructor(@inject(TYPES.body)instance:body) {
        this.body = instance;
    }
}
// 或者可以这样写
@injectable()
class Car implements ICar{
    @inject(TYPES.body) private body: body;
}

// 第三步：创建容器的配置

import { Container } from "inversify";

const myContainer = new Container();
myContainer.bind<IWheel>(TYPES.wheel).to(Wheel);
myContainer.bind<IChassis>(TYPES.chassis).to(Chassis);
myContainer.bind<IBody>(TYPES.body).to(Body);
myContainer.bind<ICar>(TYPES.car).to(Car);

// 第四步：从容器获取实例
const car = myContainer.get<ICar>(TYPES.car);