JS高级编程(三)-算法和设计模式

数据结构和算法

斐波那契数列

迭代版本

function fibonacciIterative(n) {
  if (n < 1) return 0;
  if (n <= 2) return 1;
    let fibNMinus2 = 0;
    let fibNMinus1 = 1;
    let fibN = n;
    for (let i = 2; i <= n; i++) { // n >= 2
      fibN = fibNMinus1 + fibNMinus2; // f(n-1) + f(n-2)
      fibNMinus2 = fibNMinus1;
      fibNMinus1 = fibN;
    }
    return fibN;
  }

递归版本

function fibonacci(n){
  if (n < 1) return 0; 
  if (n <= 2) return 1; 
  return fibonacci(n - 1) + fibonacci(n - 2); 
}

递归性能优化版本

在以上递归算法中，某些值会经过多次计算，以下是使用闭包将已经算过的值进行缓存的方式来优化的代码

function fibonacciMemoization() {
  const memo = [0, 1]; 
  const fibonacci = (n) => {
    if (memo[n] != null) return memo[n]; 
    return memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo); 
  };
  return fibonacci;
}
const f = fibonacciMemoization()
f(8) // 21

验证传入的二叉树是不是二叉查找树

二叉查找树(binary search tree, BST)的定义

若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值
若任意节点的右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值
任意节点的左、右子树也分别为二叉查找树

function TreeNode(val) {
  this.val = val;
  this.left = this.right = null;
}

示例

const isValidBST = function(root) {
  if (!root) {
    return true; 
  }
  function helper(root, min, max) {
    if (!root) {
      // 当递归至叶子节点的子节点时，递归退出	
      return true; 
    }

    if ((min !== null && root.val <= min) || (max !== null && root.val >= max)) {
      // 若不符合BST的定义规则，则返回false
      return false; 
    }
    // 缩小问题范围
    return helper(root.left, min, root.val) && helper(root.right, root.val, max);
  }
  return helper(root, null, null);
};

排序算法

详细参考

设计模式

发布-订阅模式

实现一个简易版的 Node.js 中的EventEmitter，用法如下

const emitter = new EventEmitter()
emitter.on('log', (param) => {
  console.log(param)
})
emitter.emit('log', 'Event Fire')

示例

class EventEmitter {
  constructor() {
    this._events = {};
  }
  // 订阅type类型的事件，listener为处理时间的监听器
  on(type, listener) {
    this._events[type] = listener;
  }
  // 发布信息
  emit(type, ...args) {
    if(this._events[type]) {
      this._events[type].apply(this, ...args);
    }
  }
}

观察者模式

使用示例

const ob1 = new Observer();
const ob2 = new Observer();
const sub = new Subject();
sub.add(ob1);
sub.add(ob2);
sub.notify('Event Fire');

实现示例

class Subject {
  constructor(){
    this.observers = [];
  }
  // 增加观察者
  add(observer) {
    this.observers.push(observer);
  }
  // 通知所有观察者
  notify(...args) {
    this.observers.forEach(abserver => abserver.log(...args))
  }
}

class Observer {
  log(...args){
    console.log(args);
  }
}

在观察者模式中，Subject 和 Observer 是互相耦合的 (Subject 要直接addObserver)，而在发布-订阅模式中，由于 Event Channel 扮演了一个数据通道的角色，Publisher 和 Subscriber 是解耦的，这也使得发布-订阅模式相对于观察者模式更加灵活。可以说，发布-订阅模式是一种特殊的观察者模式

装饰器模式

装饰模式的特点是不需要改变被装饰对象本身，而只是在外面套一个外壳接口来对其功能进行增强
react的高阶组件即使用了装饰器模式

function withWindowWidth(BaseComponent) {
  class DerivedClass extends React.Component {
    state = {
      windowWidth: window.innerWidth,
    }

    onResize = () => {
      this.setState({
        windowWidth: window.innerWidth,
      })
    }

    componentDidMount() {
      window.addEventListener('resize', this.onResize)
    }

    componentWillUnmount() {
      window.removeEventListener('resize', this.onResize);
    }

    render() {
      return <BaseComponent {...this.props} {...this.state}/>
    }
  }
  return DerivedClass;
}

// 原始的组件仅能做简单的信息展示
const MyComponent = (props) => {
  return <div>Window width is: {props.windowWidth}</div>
};

// 在使用了高阶组件后，高阶组件内部对原始的基础组件做了增强处理，使得新的组件可以自动根据窗口大小的变更在页面上显示最新的值
// 在本示例中，原始组件始终没有做任何改变，只是通过装饰使其功能得到了增强
export default withWindowWidth(MyComponent);

单例模式

在软件开发中，单体模式是指限制类只有一个实例，这样这个实例就可以被用在整个系统之中

在 JavaScript 中，我们只需要简单地声明：var g = {}就创建了一个单例

在前端开发中，单例模式是一种常用的模式，无论是window对象还是document对象，都是单例的

策略模式

在策略模式中，需要创建表示各种策略的对象和一个行为随着策略对象改变而改变的 context 对象，策略对象改变 context 对象的执行算法。做法是：定义一系列的算法，把它们一个个封装起来, 并且使它们可相互替换

使用策略模式优化如下 React 代码

function getEle(compName, value) {
  if (compName === 'input') {
    return <Input value={value}/>;
  } else if (compName === 'pic') {
    return <Image source={require(value)}/>;
  } else {
    return <View/>;
  }
}
const E = getEle('input', 123);

示例

const eleMap = {
  input: value => <Input value={value} />,
  pic: value => <Image source={require(value)} />,
  default: () => <View />,
};
const E = eleMap['input'](123);

代理模式

代理模式在真正执行逻辑的时候会调用被代理的对象的逻辑，在调用前后可以加入自己的逻辑来对功能进行增强

使用代理模式，实现图片懒加载，在图片加载完成之前先展示loading.gif

var myImage = (function () {
  var imgNode = document.createElement('img')
  document.body.appendChild(imgNode)

  return {
    setSrc: function (src) {
      imgNode.src = src
    }
  }
})()

示例

var proxyImage = (fucntion() {
  var img = new Image();
  img.onload = function() {
    myImage.setSrc(img.src);
  }

  return {
    setSrc: function(src) {
      myImage.setSrc('***.gif')
      img.src = src;
    }
  }
})()

proxyImage.setSrc('http://image.com')