image frame

四月八日

underscore框架设计

JavaScript

立即执行函数

使用立即执行函数，创建局部作用域，隔离环境并初始化代码

1
2
3
(function (global, factory) {

}(this, function () {}))

判断采用那种模块化规范导出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// commomjs 规范
typeof exports === 'object' && typeof module !== 'undefined' ? module.exports = factory() :
// amd 规范
typeof define === 'function' && define.amd ? define('underscore', factory) :
// 如果都不是则 直接挂在this上
(global = global || self, (function () {
  var current = global._;
  var exports = global._ = factory();
  //防止多次引入冲突
  exports.noConflict = function () {
    global._ = current;
    return exports;
  };
}()));

创建根节点

1
2
3
4
5
// 建立根节点对象，self 在浏览器端， global 在服务端， this 在一些虚拟机中，使用self 代替 window 提供对 Webworker 的支持
var root = typeof self == 'object' && self.self === self && self ||
          typeof global == 'object' && global.global === global && global ||
          Function('return this')() ||
          {};

each方法

each 依赖的函数

一个内部函数，根据参数返回不同的回调函数的封装，一个复用的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function optimizeCb(func, context, argCount) {

  // 没有传入执行上下文， 直接返回函数
  if (context === void 0) return func;
  switch (argCount == null ? 3 : argCount) {
    case 1:
      return function (value) {
        return func.call(context, value);
      };
      // The 2-argument case is omitted because we’re not using it.
    case 3:
      return function (value, index, collection) {
        return func.call(context, value, index, collection);
      };
    case 4:
      return function (accumulator, value, index, collection) {
        return func.call(context, accumulator, value, index, collection);
      };
  }
  return function () {
    return func.apply(context, arguments);
  };
}

isArrayLike

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var MAX_ARRAY_INDEX = Math.pow(2, 53) - 1;


// 简单获取属性值
function shallowProperty(key) {
  return function (obj) {
    return obj == null ? void 0 : obj[key];
  };
}

var getLength = shallowProperty('length');

// 属性检查 数字格式，且不能超过数组最大值
function createSizePropertyCheck(getSizeProperty) {
  return function (collection) {
    var sizeProperty = getSizeProperty(collection);
    return typeof sizeProperty == 'number' && sizeProperty >= 0 && sizeProperty <= MAX_ARRAY_INDEX;
  }
}

var isArrayLike = createSizePropertyCheck(getLength);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function each(obj, iteratee, context) {
  iteratee = optimizeCb(iteratee, context);
  var i, length;
  if (isArrayLike(obj)) {
    for (i = 0, length = obj.length; i < length; i++) {
      iteratee(obj[i], i, obj);
    }
  } else {
    var _keys = keys(obj);
    for (i = 0, length = _keys.length; i < length; i++) {
      iteratee(obj[_keys[i]], _keys[i], obj);
    }
  }
  return obj;
}

挂载方法 混合模式

依赖的函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//内部方法，创建一个toString 基础测试器
  function tagTester(name) {
    var tag = '[object ' + name + ']';
    return function (obj) {
      return toString.call(obj) === tag;
    };
  }
  var isFunction = tagTester('Function');
  var isFunction$1 = isFunction;

  //返回一个排序的 所有工具函数名的数组
  function functions(obj) {
    var names = [];
    for (var key in obj) {
      if (isFunction$1(obj[key])) names.push(key);
    }
    return names.sort();
  }

定义underscore方法

  • 如果是underscore实例直接返回
  • 如果不是通过new操作符执行函数
  • 再次进入第二行的判断，这时已经是underscore的实例会继续往下执行
  • 在实例上挂在一个变量指向传入的对象
1
2
3
4
5
function _(obj) {
  if (obj instanceof _) return obj;
  if (!(this instanceof _)) return new _(obj);
  this._wrapped = obj;
}

核心mixin 方法

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
function mixin(obj) {

  // 循环所有导出方法的名称
  each(functions(obj), function (name) {
    // 每个名称对应的方法
    var func = _[name] = obj[name];
    //  在原型上挂载同样的方法
    _.prototype[name] = function () {
      //拿到上面挂载的 传入的对象
      var args = [this._wrapped];
      // 拼接为整个数组 
      Array.prototype.push.apply(args, arguments);
      //直接用定义的内置方法执行
      return chainResult(this, func.apply(_, args));
    };
  });
  return _;
}

var allExports = {
  each:each
}

var _$1 = mixin(allExports);
// Legacy Node.js API.
_$1._ = _$1;

return _$1;

所以可以用下面的方法执行方法

1
_([1,2,3]).each(function(item){console.log(item)});

测试环境karma

DevOps

初始化

1
yarn init -y

实现第一个测试用例

index.js

1
2
3
var add = function(a){
  return 1 + a
}

index.spec.js

1
2
3
4
5
describe('测试基本api',function(){
  it('add',function(){
    except(add(1)).toBe(2)
  })
})

如何让上面的代码运行

安装karma测试框架

1
yarn add -D karma

配置package.json可以执行karma命令，如果不想配置可以安装 karma-cli

1
2
3
"scripts":{
  "karma-init":"karma init"
}

执行命令初始化

1
yarn karma-init
  • Which testing framework do you want to use?

想要使用的单元测试框架 jasmine

  • Do you want to use Require.js

是否想要用Requirejs， 不需要

  • Do you want to capture any browsers automatically？

想要自动调用的浏览器 PhantomJS

PhantomJS是一个可编程的无头浏览器:一个完整的浏览器内核,包括js解析引擎,渲染引擎,请求处理等,但是不包括显示和用户交互页面的浏览器。

hantomJS的适用范围就是无头浏览器的适用范围。通常无头浏览器可以用于页面自动化，网页监控，网络爬虫等：

页面自动化测试：希望自动的登陆网站并做一些操作然后检查结果是否正常。
网页监控：希望定期打开页面，检查网站是否能正常加载，加载结果是否符合预期。加载速度如何等。
网络爬虫：获取页面中使用js来下载和渲染信息，或者是获取链接处使用js来跳转后的真实地址

  • What is the location of your source and test files

想要测试的文件位置，暂时留空

  • Should any of the files included by the previous patterns be excluded？

想要排除哪些文件暂时留空

  • Do you want Karma to watch all the files and run the tests on change？

是否需要监听文件改变， 暂时选no,不监听

下一步

打开生成的karma.conf.js文件

1
2
3
4
5
6
7
8
9
10
11
12
{
  // 测试框架名称
  frameworks: ['jasmine'],

  //测试文件目录
  files: [
    "./test/unit/**/*.js",
    "./test/unit/**/*.spec.js"
  ],

  singleRun:true
}

在package.json中添加运行命令

1
2
3
4
 "scripts": {
  "karma-init": "karma init",
  "karma-start": "karma start"
}

安装无头浏览器和jasmine适配器

1
yarn add -D karma-jasmine karma-phantomjs-launcher phantomjs

编写测试用例

index.js

1
2
3
4
5
6
7
function add(a) {
  if (a == 1) {
    return a + 1;
  } else {
    return a + 2;
  }
}

index.spec.js

1
2
3
4
5
describe('单元测试',function(){
  it("contains spec with an expectation", function() {
    expect(add(1)).toBe(2);
  })
})

执行 karma-start 进行单元测试

覆盖率测试

安装 karma-coverage

1
yarn add -D karma-coverage

修改配置项

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
{
  preprocessors: {
    "./test/unit/**/*.js":"coverage"
  },

  reporters: ['progress','coverage'],

  coverageReporter: {
    dir: 'doc/coverage',
    reporters: [
      // reporters not supporting the `file` property
      { type: 'html', subdir: 'report-html' },
    ]
  }
}

执行再次执行 karma-start

UI测试

安装 backstop

1
yarn add -D backstop

添加 package.json 命令行

1
2
3
4
5
6
7
{
  "scripts": {
    "backstop-init": "backstop init",
    "backstop-start": "backstop test"
  }
}

执行 backstop-init 生成文件目录

修改文件目录配置

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
{
  "id": "baidu",

  // 设计图分辨率设置
  "viewports": [
    {
      "label": "phone",
      "width": 375,
      "height": 667
    },
    {
      "label": "tablet",
      "width": 1024,
      "height": 768
    }
  ],

  //调用 puppeteer 库的脚本
  "onBeforeScript": "puppet/onBefore.js",
  "onReadyScript": "puppet/onReady.js",
  "scenarios": [
    {
      "label": "baidu home",
      "cookiePath": "backstop_data/engine_scripts/cookies.json",
      "url": "https://garris.github.io/BackstopJS/",
      "referenceUrl": "",
      "readyEvent": "",
      "readySelector": "",
      "delay": 0,
      "hideSelectors": [],
      "removeSelectors": [],
      "hoverSelector": "",
      "clickSelector": "",
      "postInteractionWait": 0,
      "selectors": [],
      "selectorExpansion": true,
      "expect": 0,
      "misMatchThreshold" : 0.1,
      "requireSameDimensions": true
    }
  ],
  "paths": {
    "bitmaps_reference": "backstop_data/bitmaps_reference",
    "bitmaps_test": "backstop_data/bitmaps_test",
    "engine_scripts": "backstop_data/engine_scripts",
    "html_report": "doc/backstop_data/html_report",
    "ci_report": "backstop_data/ci_report"
  },
  "report": ["browser"],
  "engine": "puppeteer",
  "engineOptions": {
    "args": ["--no-sandbox"]
  },
  "asyncCaptureLimit": 5,
  "asyncCompareLimit": 50,
  "debug": false,
  "debugWindow": false
}

单元测试理论

DevOps

TDD 测试驱动开发

  • 首先，开发者在码业务前写一些测试用例
  • 运行这些测试用例。结果肯定是运行失败，因为测试用例中的业务逻辑还没实现嘛
  • 开发者实现测试用例中的业务逻辑
  • 再运行测试用例， 如果开发者代码能力不错，这些测试用例应该可以跑通了(pass)
  • 对业务代码及时重构，包括增加注释，清理重复等。因为没人比开发者自己更了解哪些代码会对哪些部分造成影响从而导致测试失败(fail)

我们通过举例来了解一下如何实践TDD。例子中的代码可以从github上获取tdd-vs-bdd。将代码clone下来，执行命令npm install && grunt

假设我们想写一个计算阶乘的函数(这是一个很刻意的例子，但是这个例子对我们指出TDD和BDD的区别很有帮助)。TDD的常用方式是运行某函数，然后断言结果满足某个值。

在阶乘的例子中，我们使用的javascript测试框架是Mocha。废话不说，上代码：

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
var assert = require('assert'),
    factorial = require('../index');
 
suite('Test', function (){
    setup(function (){
        // Create any objects that we might need
    });
 
    suite('#factorial()', function (){
        test('equals 1 for sets of zero length', function (){
            assert.equal(1, factorial(0));
        });
 
        test('equals 1 for sets of length one', function (){
            assert.equal(1, factorial(1));
        });
 
        test('equals 2 for sets of length two', function (){
            assert.equal(2, factorial(2));
        });
 
        test('equals 6 for sets of length three', function (){
            assert.equal(6, factorial(3));
        });
    });
});

显然上述测试会失败，因为我们尚未实现函数功能。所以接下来我们需要实现满足上述测试用例的阶乘函数。代码如下

1
2
3
4
5
6
module.exports = function (n) {
    if (n < 0) return NaN;
    if (n === 0) return 1;
 
    return n * factorial(n - 1);

现在我们再次运行测试用例，所有的case都跑通了! 这就是TDD的使用方式。

BDD 行为驱动开发

BDD旨在消除TDD过程中可能造成的问题。

与TDD相比，BDD是通过编写行为和规范来驱动软件开发。 行为和规范可能看起来与测试非常相似，但是它们之间却有着微妙但重要的区别。

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
var assert = require('assert'),
    factorial = require('../index');
 
describe('Test', function (){
    before(function(){
        // Stuff to do before the tests, like imports, what not
    });
 
    describe('#factorial()', function (){
        it('should return 1 when given 0', function (){
            factorial(0).should.equal(1);
        });
 
        it('should return 1 when given 1', function (){
            factorial(1).should.equal(1);
        });
 
        it('should return 2 when given 2', function (){
            factorial(2).should.equal(2);
        });
 
        it('should return 6 when given 3', function (){
            factorial(3).should.equal(6);
        });
    });
 
    after(function () {
        // Anything after the tests have finished
    });
});

敏捷开发

敏捷开发以用户的需求进化为核心，采用迭代、循序渐进的方法进行软件开发。在敏捷开发中，软件项目在构建初期被切分成多个子项目，各个子项目的成果都经过测试，具备可视、可集成和可运行使用的特征。换言之，就是把一个大项目分为多个相互联系，但也可独立运行的小项目，并分别完成，在此过程中软件一直处于可使用状态。

偏函数和函数柯里化

JavaScript

偏函数 (Partial application)

In computer science, partial application (or partial function application) refers to the process of fixing a number of arguments to a function, producing another function of smaller arity.

在计算机科学中，局部应用是指固定一个函数的一些参数，然后产生另一个更小元的函数。（什么是元？元是指函数参数的个数，比如一个带有两个参数的函数被称为二元函数。）

没有上下文的偏函数
1
2
3
4
5
6
7
const partial = (fn, ...args) => {
  return (...args2) =>  fn.call(this, ...args, ...args2)
}

console.log(partial(function (a, b, c, d) {
  return a + b + c + d
}, 1, 2)(3, 4))
bind 实现
  • 类型判断，错误处理
  • 缓存一级参数
  • 定义返回的新函数
  • 处理原型链
  • 绑定新函数的执行上下文，判断是否通过new调用
1
2
3
4
5
6
7
8
9
10
11
12
13
Function.prototype.bind = function (ctx) {
  if (typeof this !== 'function') throw new Error();
  var args = Array.prototype.slice.call(arguments, 1);
  var toBind = this;
  var fn = function _fn() {
    args = args.concat(Array.prototype.slice.call(arguments, 0))
    toBind.apply(this instanceof _fn ? this : ctx, args)
  }
  if (toBind.prototype) {
    fn.prototype = Object.create(toBind.prototype)
  }
  return fn;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Function.prototype.bind = function (ctx) {
  if (typeof this !== 'function') throw new Error();
  var args = Array.prototype.slice.call(arguments, 1);
  var toBind = this;
  var noop = function(){}
  var fn = function _fn() {
    args = args.concat(Array.prototype.slice.call(arguments, 0))
    toBind.apply(noop.prototype.isPrototypeOf(this) ? this : ctx, args)
  }
  if (toBind.prototype) {
    noop.prototype = toBind.prototype;
  }
  fn.prototype = new noop()
  return fn;
}

柯里化 (Currying)

In mathematics and computer science, currying is the technique of translating the evaluation of a function that takes multiple arguments (or a tuple of arguments) into evaluating a sequence of functions, each with a single argument.

在数学和计算机科学中，柯里化是一种将使用多个参数的一个函数转换成一系列使用一个参数的函数的技术

ES6实现
1
2
const curry = (fn, args = []) =>
  fn.length === args.length ? fn(...args) : (...args2) => curry(fn, [...args, ...args2])
反柯理化

使用箭头函数不能绑定函数的this

1
const uncurry = (fn) => (...args) => fn.apply(this, args)
1
2
3
4
5
6
Function.prototype.uncurring = function () {
  var self = this;
  return function () {
    return self.apply(this, arguments);
  };
};

偏函数与柯里化区别

柯里化是将一个多参数函数转换成多个单参数函数，也就是将一个 n 元函数转换成 n 个一元函数。

局部应用则是固定一个函数的一个或者多个参数，也就是将一个 n 元函数转换成一个 n - x 元函数。

.bashr 和 .profile的区别

Linux / 常见问题

要搞清bashrc与profile的区别，首先要弄明白什么是交互式shell和非交互式shell，什么是login shell 和non-login shell。

交互式模式

shell等待你的输入，并且执行你提交的命令。这种模式被称作交互式是因为shell与用户进行交互。

这种模式也是大多数用户非常熟悉的：登录、执行一些命令、签退。当你签退后，shell也终止了

非交互式模式

shell不与你进行交互，而是读取存放在文件中的命令,并且执行它们。当它读到文件的结尾，shell也就终止了。

bashrc与profile都用于保存用户的环境信息，bashrc用于非交互式non-loginshell，而profile用于交互式login shell。

系统中存在许多bashrc和profile文件：

  • /etc/profile 此文件为系统的每个用户设置环境信息,当第一个用户登录时,该文件被执行.并从/etc/profile.d目录的配置文件中搜集shell的设置.

    每个用户都可使用该文件输入专用于自己使用的shell信息,当用户登录时,该文件仅仅执行一次!默认情况下,它设置一些环境变量,然后执行用户的.bashrc文件.

  • /etc/bashrc:为每一个运行bash shell的用户执行此文件.当bash shell被打开时,该文件被读取。有些linux版本中的/etc目录下已经没有了bashrc文件。

    该文件包含专用于某个用户的bash shell的bash信息,当该用户登录时以及每次打开新的shell时,该文件被读取.另外,/etc/profile中设定的变量(全局)的可以作用于任何用户,而~/.bashrc等中设定的变量(局部)只能继承/etc/profile中的变量,他们是”父子”关系.

/etc/profile，/etc/bashrc 是系统全局环境变量设定

/.profile，/.bashrc用户家目录下的私有环境变量设定

当登入系统时候获得一个shell进程时，其读取环境设定档有三步

  1. 首先读入的是全局环境变量设定档/etc/profile，然后根据其内容读取额外的设定的文档，如/etc/profile.d和/etc/inputrc

  2. 然后根据不同使用者帐号，去其家目录读取/.bash_profile，如果这读取不了就读取/.bash_login，这个也读取不了才会读取~/.profile，这三个文档设定基本上是一样的，读取有优先关系

  3. 然后在根据用户帐号读取/.bashrc至于/.profile与~/.bashrc的不区别都具有个性化定制功能

~/.profile可以设定本用户专有的路径，环境变量，等，它只能登入的时候执行一次
~/.bashrc也是某用户专有设定文档，可以设定路径，命令别名，每次shell script的执行都会使用它一次

你不知道的JavaScript

JavaScript
变量提升

如果在函数声明后有同名的变量被定义，但是没有赋值，则不会被覆盖，如果同名变量被赋值这函数声明被覆盖

1
2
3
4
5
6
7
function a() {
    alert(10)
}
var a;
console.log(a);//function a(){}
a = 1;
console.log(a)//1
1
2
3
4
5
6
7
8
9
10
alert(a)
a();
var a = 3;

function a() {
    alert(10)
}
alert(a)
a = 6;
a();

等价于

1
2
3
4
5
6
7
8
9
10
var a
function a() {
    alert(10)
}
alert(a)//function a(){}
a();
a = 3;
alert(a)//3
a = 6;
a();//TypeError

alert会把函数转为字符串function a(){...},对象会调用toString方法转为[object Object]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var x = 1,
    y = 0,
    z = 0;

function add(x) {
    return (x = x + 1);
}
y = add(x);
console.log(y)

function add(x) {
    return (x = x + 3);
}
z = add(x);
console.log(z)

等价于

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function add(x) {
    return (x = x + 1);
}
// 上面函数被覆盖
function add(x) {
    return (x = x + 3);
}      
var x = 1,
    y = 0,
    z = 0;
y = add(x);
console.log(y)
z = add(x);
console.log(z)
this指向

在构造函数中，如果在this指定属性前访问，会返回undefined

1
2
3
4
5
function go() {
    console.log(this.a);
    this.a = 30;
}
new go()//undefined

如果在原型连上定义，则会去原型链上查找，找不到会返回undefined,但是不会去查找全局作用域，因为通过 new 操作符，this 指向生成的对象实例

1
2
3
4
5
6
function go() {
    console.log(this.a);
    this.a = 30;
}
go.prototype.a = 40
new go()//40
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
this.a = 20;

function go() {
    console.log(this.a);
    this.a = 30;
}
go.prototype.a = 40;
var test = {
    a: 50,
    init: function (fn) {
        fn();
        console.log(this.a);
        return fn;
    }
};

//在执行new构造函数时，this.a还没有被赋值，所以去原型链上查找返回40
//在读取对象实例的a属性时，this.a 已经被赋值，所以返回30
console.log((new go()).a); //40 30

//在init方法中fn没有被具体对象调用，所以fn执行时，go方法中this指向全局，返回20
//在下一步中对this.a赋值，this指向window对象所以把全局的a修改为30
//init中的this指向调用init方法的test对象返回50
test.init(go);//20 50

//再次执行fn即go方法，这时this.a已经被修改为30
//init中的this还是指向test对象返回test.a = 50
var p = test.init(go);//30 50

//用一个p变量接受最后返回的go方法，在调用时相当于window调用，最终返回被修改后的a属性为30
p();//30

一些常见的变量

可以通过self判断时否时windows环境

1
self.self===self

由于self变量经常被修改所以又创建了一个新变量表示全局对象 globalThis,也是为了和 Node 环境靠拢

1
2
3
self === globalThis
top === globalThis
parent===globalThis
严格模式

函数中的严格模式只对函数作用域生效，如果在函数中调用其他函数，其他函数不受严格模式影响 ES6不建议使用局部严格模式

参数传递

js中基本类型时按值传递的，引用类型是按地址传递的，形参和实参没有关系

1
2
3
4
5
6
7
8
9
10
function test(m) {
    m = {
        v: 5
    }
}
var m = {
    k: 30
};
test(m);
alert(m.v);//undefined
块级作用域
1
2
3
4
5
{
    function init(){}
    init = 4
}
console.log(init);// function init(){}
1
2
3
4
5
6
7
8
9
10
11
// 在块级作用域中，如果在函数声明前变量已经定义，则函数声明和后面的赋值都不会执行
{
    init = 6
    function init() {}
    init = 4
    // 如果重新定义会报错Identifier 'init' has already been declared
    // const init = 7
    init = 7
    console.log(init); //7
}
console.log(init);//6

类似于函数的声明不能覆盖变量的定义

1
2
3
var init = 1;
function init() {}
console.log(init)
条件语句中的函数声明
1
2
3
4
5
6
7
8
9
function init(){
    console.log(1);
}
if(false){
    function init(){
        console.log(2);
    }
}
init()

变量被提升，函数不会被提升，等价于：

1
2
3
4
5
6
7
8
9
10
function init(){
    console.log(1);
}
var init;
if(false){
    function init(){
        console.log(2);
    }
}
init()

如果在函数体内部，会被提升至作用域顶端

1
2
3
4
5
6
7
8
9
10
11
function init(){
    console.log(1);
}
(function(){
  if(false){
      function init(){
          console.log(2);
      }
  }
  init()
})

等价于

1
2
3
4
5
6
7
8
9
10
11
12
function init(){
    console.log(1);
}
(function(){
  var init;
  if(false){
      function init(){
          console.log(2);
      }
  }
  init() //TypeError
})
继承
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function extend(sup, sub) {
    var F = function () {}
    F.prototype = sup.prototype;
    F.prototype.constructor = sub;
    sub.prototype = new F();
    const stck = Object.keys(Super);
    for (var i = 0; i < stck.length; i++) {
        sub[stck[i]] = sup[stck[i]]
    }
}

function Super() {
    this.color = 'red'
}
Super.prototype.init = function () {}
Super.time = Date.now();

function Sub() {
    Super.call(this);
}
extend(Super, Sub);
console.log(new Sub())
正则的拷贝
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/** Used to match `RegExp` flags from their coerced string values. */
var reFlags = /\w*$/;

/**
 * @private
 * @param {Object} regexp The regexp to clone.
 * @returns {Object} Returns the cloned regexp.
 */
function cloneRegExp(regexp) {
    var result = new regexp.constructor(regexp.source, reFlags.exec(regexp));
    result.lastIndex = regexp.lastIndex;
    return result;
}
const reg = /foo/g
let reg2 = cloneRegExp(reg) // /foo/g
console.log(reg2);
柯理化

实现 before after

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
function test(a, b, c) {
  console.log('test', a, b, c);
  return 'test';
}

Function.prototype.after = function (cb) {
  const _this = this;
  return function _after() {
    if (_this.name !== '_before') {
      cb();
      const res = _this.apply(_this, arguments);
      return res;
    }
    const res = _this.apply(_this, arguments);
    cb(res);
  }
}

Function.prototype.before = function (cb) {
  const _this = this;
  function _before() {
    if (_this.name === '_after') {
      const res = _this.apply(_this, arguments);
      cb(res);
      return
    }
    const res = cb();
    _this.apply(_this, arguments);
    return res;
  }
  return _before
}

test
  .before(function () {
    console.log('before');
    return 10;
  })
  .after(function (res) {
    console.log('after');
  })
  (1, 2, 3)
反柯理化

从字面讲，意义和用法跟函数柯里化相比正好相反，扩大适用范围，创建一个应用范围更广的函数。使本来只有特定对象才适用的方法，扩展到更多的对象。或者说让一个对象去借用一个原本不属于他的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//简单实现
var uncurrying = (fn) => (context,...rest)=>fn.apply(context,rest);

//使用call.apply省略context参数
//调用fn的call方法，和Funcion的call方法是同理的，省略了一步原型链查找的过程
//call方法需要执行call执行时候的上下文即fn函数，并把其他参数分别传入
//加上apply方法，重指定call执行时候的上下文，并且call方法的参数可以用数组的形式传入 也就是rest包含[context,...rest]
var uncurrying = fn => (...rest)=> fn.call.apply(fn,rest)

var uncurrying = fn => (...rest)=> Function.prototype.call.apply(fn,rest)

//也可以直接挂载在Function上面
Function.prototype.uncurrying = function (){
    return this.call.bind(this)
}

使用场景

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//借用自己
var un = Function.prototype.uncurrying.uncurrying();
var a = un(Array.prototype.map)([1,2],function(i){console.log(i)});

//改变函数的执行上下文
function sayHi () {
    return "Hello " + this.value +" "+[].slice.call(arguments);
}
var sayHiuncurrying=sayHi.uncurrying();
console.log(sayHiuncurrying({value:'world'},"hahaha"));

//借用方法
var obj = {
    push:function(v){
          return  Array.prototype.push.uncurrying()(this,v)
    } 
}
obj.push('first');

基于流式布局的轮播图实现思路

JavaScript

布局

这是一个流式布局下得轮播图案例，问题还比较多，可以提供一种不错的思路

通过让父元素禁止换行，每个图片子元素设置inline-block,流式排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
* {
  padding: 0;
  margin: 0;
}

#root {
  width: 500px;
  height: 280px;
  margin:auto;
  white-space: nowrap;
  overflow: hidden;
}

#root>div {
  width: 500px;
  height: 280px;
  display: inline-block;
  transition: .5s linear;
}
1
2
3
4
5
6
<div id='root'>
  <div style='background: url(./assets/1b809d9a2bdf3ecc481322d7c9223c21)'></div>
  <div style='background: url(./assets/1b809d9a2bdf3ecc481322d7c9223c21)'></div>
  <div style='background: url(./assets/1b809d9a2bdf3ecc481322d7c9223c21)'></div>
  <div style='background: url(./assets/1b809d9a2bdf3ecc481322d7c9223c21)'></div>
</div>

开始拖动

通过CSS的transform属性来改变图片的位置，这里我们不让如父元素一起滚动，而是控制每一个元素的滚动，来看一下实现的思路

在鼠标按下的时候加一个标识，表示正在拖动,并且记录下鼠标点击的位置

1
2
3
4
root.addEventListener('mousedown', event => {
  mark = true;
  startX= event.clientX;
})

在鼠标移动的时候,判断是否，已经开始移动

1
2
3
document.addEventListener('mousemove', function (event) {
  if (!mark) return false
});

由于是使用流式布局，每一个元素都在自己的位置上，而且偏移量为0

那么当前正在窗口中的图片的索引标记为pos,初始化为0

再滑动的时候需要知道当前窗口内的图片索引，当滑动距离的绝对值超过500，则pos切换为上一张图片，或下一张图片，

1
2
3
4
5
//错误，不能直接向下取整，因为向左滑动的时候不足500不能算作前一张，向上也同理
let current = position - Math.floor(x / 500);

// 需要去掉偏移量之后，看是否超过了500
let current = position - Math.ceil((x-x % 500) / 500);

下面，我们只关心pos左侧和右侧的图片是哪一张

如果是右边的一张图片，那索引就会 +1, 按照[1,2,3,0,1,2,3,0,...]的顺序循环，需要让他在到达最后索引的时候归零，这里可以通过取余实现

1
const right = (pos+1)%length

但是左边的一张图片，是按倒叙排列的 [3,2,1,0,3,2,1,0,...] 当pos===0左边一张图片的索引为3，也就是让位置[-1]和 图片索引[3]对应，这里我们还是通过取余操作，但是要先加上子元素的长度length,把它转为整数，对于右边的图片来说，对于多加的长度没有影响，因为加了一倍的长度，最终取余的时候还是可以约调

1
const index = (pos+ offset + lenth) % length

下面是如何把中间位置，和左右两张图片放到对应的位置

首先减去偏移量，把图片移动到窗口位置，类似绝对定位的效果,500为图片的宽度

1
let dx = - index * 500

在加上左右位置的偏移量，和鼠标滑动的偏移量

注意：为了学习理解，滑动的事件实在document上面的，所以滑动距离可能会超过500px,这里需要取余计算剩余偏移量

1
let dx  = -index * 500 + offset * 500 + x % 500

最终滑动事件为

1
2
3
4
5
6
7
8
9
10
11
document.addEventListener('mousemove', function (event) {
  if (!mark) return false
  let x = event.clientX - startX;
  let current = position - Math.ceil((x - x % 500) / 500);
  for (let offset of [-1, 0, 1]) {
    let pos = current + offset;
    pos = (pos + children.length) % children.length
    children[pos].style.transition = 'none';
    children[pos].style.transform = `translateX(${- pos * 500 + offset * 500 + x % 500}px)`
  }
});

结束拖动

鼠标松开的时候，需要知道偏移量是否超过组件宽度的一半，如果偏移量大于250就是下一张，如果小于-250就是前一张,有四种情况可以画数轴感受一下

1
2
3
4
if (x % 500 >= -250 && x % 500 <= 0) c = 1;
if (x % 500 <= 250 && x % 500 >= 0) c = -1
if (x % 500 < -250) c = -1
if (x % 500 > 250) c = 1

最终滚动时候开启动画，并且忽略鼠标拖动的偏移量，通过css动画让图片恢复到对应的位置上

1
2
3
4
5
6
7
8
9
10
11
document.addEventListener('mouseup', function (event) {
  mark = false;
  let x = event.clientX - startX;
  position = position - Math.round(x / 500);
  for (let offset of [0, c]) {
    let pos = position + offset;
    pos = (pos + children.length) % children.length
    children[pos].style.transition = '';
    children[pos].style.transform = `translateX(${- pos * 500 + offset * 500}px)`
  }
});

上面判断前后哪一张的条件语句可以用数学的算法优化

1
2
3
4
5
6
7
8
9
10
11
document.addEventListener('mouseup', function (event) {
  mark = false;
  let x = event.clientX - startX;
  position = position - Math.round(x / 500);
  for (let offset of [0, Math.sign(x % 500 - Math.sign(x) * 250)]) {
    let pos = position + offset;
    pos = (pos + children.length) % children.length
    children[pos].style.transition = '';
    children[pos].style.transform = `translateX(${- pos * 500 + offset * 500}px)`
  }
});

5.针对复杂应用的设计模式

JavaScript

命令式处理异常方式的问题
使用容器，以防访问无效数据
用Functor的实现来做数据转换
利于组合的Monad数据类型
使用Monadic类型来巩固错误处理策略
Monadic类型的组合与交错

命令式错误处理的不足

函数式编程其实可以把错误处理得比任何其他开发风格更为优雅，软件中的许多问题都是由于数据不经意地变成了null或undefined、出现了异常、失去网络连接等情况造成的。所以需要大量得错误捕获代码，在每一个使用引用得地方判断null或undefined,是的代码得逻辑越来月复杂

try catch

我们尝试使用try,catch来捕获错误

1
2
3
4
5
try {
  var student = findStudent('444-44-4444');
} catch (e) {
  console.log('ERROR' + e.message);
}

但这样会与函数式的设计有兼容性问题。

  • 难以与其他函数组合或链接。
  • 违反了引用透明性，因为抛出异常会导致函数调用出现另一出口，所以不能确保单一的可预测的返回值。
  • 会引起副作用，因为异常会在函数调用之外对堆栈引发不可预料的影响。
  • 违反非局域性的原则，因为用于恢复异常的代码与原始的函数调用渐行渐远。当发生错误时，函数离开局部栈与环境。即 try 中的逻辑会在遇到错误时停止执行，转移到catch处理错误逻辑
  • 不能只关注函数的返回值，调用者需要负责声明catch块中的异常匹配类型来管理特定的异常。
  • 当有多个异常条件时会出现嵌套的异常处理块

其中一个常见的场景是JavaScript中因在null对象上调用函数所产生的TypeError。

空值（null）检查问题

本来可以简单地创建一个lens来获取该属性，若是null即返回undefined，但它并不会打印任何错误信息。

这使代码需要大量的判空检查代码。不管是使用try-catch还是null检查，都是被动的解决方式。

Functor 一种更好得解决方案

思想说起来也非常简单，创建一个安全的容器，来存放危险代码

包裹不安全的值

map可以是一个更广义的map的概念，而不仅仅是数组。在函数式JavaScript中，map只不过是一个函数，由于引用透明性，只要输入相同，map永远会返回相同的结果。当然，还可以认为map是可以使用lambda表达式变换容器内的值的途径。比如，对于数组，就可以通过map转换值，返回包含新值的新数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Wrapper {
  constructor(value) {//存储任意类型值的简单类型
    this._value = value;
  }
  // map :: (A -> B) -> A -> B
  map(f) { //用一个函数来 map 该类型（就像数组一样）
    return f(this.val);
  };
  toString() {
    return 'Wrapper (' + this.value + ')';
  }
}
const wrap = (val) => new Wrapper(val); //能够根据值快速创建Wrapper 的帮助函数

Wrapper类型使用map安全地访问和操作值。在这种情况下，通过映射 identity 函数就能在容器中提取值

取值得方法

1
2
const wrappedValue = wrap('Get Functional');
wrappedValue.map(R.identity); //-> 'Get Functional' <--- 值的提取

映射任何函数到该容器，比如记录日志或是变换该值：

1
2
wrappedValue.map(log);
wrappedValue.map(R.toUpper); //-> 'GET FUNCTIONAL' <--- 对内部值应用函数

现在所有得对值操作都与要通过map方法先伸入到容器中取值，可以说得到了一定得保护，但现在还没有对null,和undefined得处理

当初始化一个空值得时候

1
2
const wrappedNull = wrap(null);
wrappedNull.map(doWork); // doWork 被赋予了空值检查的责任

不应该通过dowork来检查，完全可以交给Wrapper类型来做错误处理。换句话说，可以在调用函数之前，检查null、空字符串或者负数，等等。因此，Wrapper.map的语义就由具体的Wrapper类型来确定。

map的变种——fmap

1
2
3
4
// fmap :: (A -> B) -> Wrapper[A] -> Wrapper[B]
Wrapper.prototype.fmap = function (f) {
  return wrap(f(this.val)); // 先将返回值包裹到容器中，再返回给调用者
};

fmap知道如何在上下文中应用函数值。它会先打开该容器，应用函数到值，最后把返回的值包裹到一个新的同类型容器中。拥有这种函数的类型称为Functor。

Functor定义

Functor 只是一个可以将函数应用到它包裹的值上，并将结果再包裹起来的数据结构。下面是fmap的一般定义：

1
fmap :: (A -> B) -> Wrapper(A) -> Wrapper(B) // Wrapper 可以是任何容器类型

fmap函数接受一个从A->B的函数，以及一个Wrapper(A) Functor，然后返回包裹着结果的新FunctorWrapper(B)。下图显示了用increment函数作为A->B的映射函数，只是这里的A和B为同一类型。

一个简单得例子

通过柯里化初始化一个求和函数

1
2
const plus = R.curry((a, b) => a + b);
const plus3 = plus(3);

把数字2放到wrap中

1
const two = wrap(2);

再调用fmap把plus3映射到容器上

1
2
const five = two.fmap(plus3); //-> Wrapper(5) <--- 返回一个具有上下文包裹的值
five.map(R.identity); //-> 5

fmap返回同样类型的结果，可以通过映射R.identity来提取它的值。不过需要注意的是，值会一直在容器中，因此可以 fmap 任意次函数来转换值。

1
two.fmap(plus3).fmap(plus10); //-> Wrapper(15)

Functor有如下一些重要的属性约束。

  • 必须是无副作用的。若映射R.identity函数可以获得上下文中相同的值，即可证明Functor是无副作用的：
1
wrap('Get Functional').fmap(R.identity); //-> Wrapper('Get Functional')
  • 必须是可组合的。这个属性的意思是fmap 函数的组合，与分别fmap函数是一样的
1
two.fmap(R.compose(plus3, R.tap(infoLogger))).map(R.identity); //-> 5

Functor的这些属性并不奇怪。遵守这些规则，可以免于抛出异常、篡改元素或者改变函数的行为。其实际目的只是创建一个上下文或一个抽象，以便可以安全地应用操作到值，而又不改变原始值。这也是map可以将一个数组转换到另一个数组，而不改变原数组的原因。而Functor就是这个概念的推广。

使用Monad函数式地处理错误

Functor本身并不需要知道如何处理null。例如Ramda中的R.compose，在收到为null的函数引用时就会抛出异常。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const findStudent = R.curry(function(db, ssn) {
return wrap(find(db, ssn)); //包裹对象获取逻辑，以避免找不到对象所造成的问题
});
const getAddress = function(student) {
return wrap(student.fmap(R.prop('address'))); //用 Ramda 的 R.prop()函数来map 对象以获取其地址， 再将结果包裹起来
}

const studentAddress = R.compose(
  getAddress,
  findStudent(DB('student'))
);

//返回的值是被包裹了两层的address对象

studentAddress('444-44-4444').map(R.identity).map(R.identity)
Monad：从控制流到数据流
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
const R = ramda;
const Wrap = function (value) {
    this._value = value
}
Wrap.of = (value) => new Wrap(value)
Wrap.prototype.fmap = function (f) {
    return Wrap.of(f(this._value))
}
Wrap.prototype.map = function (f) {
    return f(this._value)
}
// console.log(wrap)
// console.log(wrap.map(R.identity))

const Empty = function () {}
Empty.of = () => new Empty();
Empty.prototype.fmap = function () {
    return this
}
Empty.prototype.map = function () {
    return this
}
const empty = Empty.of()

const add = R.curry((a, b) => a + b);
const plus10 = add(10);
const isEven = (num) => Number.isFinite(num) && num % 2 === 0;
const half = (num) => isEven(num) ? Wrap.of(num / 2) : empty;

console.log(half(10).fmap(plus10).map(R.identity)) //15
console.log(half(9).fmap(plus10).map(R.identity)) // Empty

Monad——为Monadic操作提供抽象接口。
Monadic类型——该接口的具体实现。

Monadic类型类似于本章介绍的Wrapper对象。不过每个Monad都有不同的用途，可以定义不同的语义便于确定其行为（例如map或fmap）。使用这些类型可以进行链式或嵌套操作，但都应遵循下列接口定义。

  • 类型构造函数——创建Monadic类型（类似于Wrapper的构造函数）。
  • unit函数——可将特定类型的值放入Monadic结构中（类似于wrap和前面看到的empty函数）。对于Monad的实现来说，该函数也被称为of函数。
  • bind函数——可以链式操作（这就是Functor的fmap，也被称为flatmap）
  • join函数——将两层Monadic结构合并成一层。这会对嵌套返回Monad的函数特别有用。
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
class Wrapper {
    //类型构造器
    constructor(value) {
        this._value = value;
    }
    static of (a) {
        //unit 函数
        return new Wrapper(a);
    }
    map(f) {
        //bind 函数（ Functor）
        return Wrapper.of(f(this.value));
    }
    join() {
        //压平嵌套的Wrapper
        if (!(this.value instanceof Wrapper)) {
            return this;
        }
        return this.value.join();
    }
    toString() {
        //返回一个当前结构的文本描述
        return `Wrapper (${this.value})`;
    }
}

join函数用于逐层扁平化嵌套结构，就像剥洋葱一样。这可以用来消除之前用functor时发现的问题

1
2
3
4
5
6
7
8
9
10
// findObject :: DB -> String -> Wrapper
const findObject = R.curry(function(db, id) {
return Wrapper.of(find(db, id));
});
// getAddress :: Student -> Wrapper
const getAddress = function(student) {
return Wrapper.of(student.map(R.prop('address')));
}
const studentAddress = R.compose(getAddress, findObject(DB('student')));
studentAddress('444-44-4444').join().get(); // Address

Monad通常有更多的操作，这里提及的最小接口只是其整个API的子集。一个Monad本身只是抽象，没有任何实际意义。只有实际的实现类型才有丰富的功能。幸运的是，大多数函数式编程的代码只用一些常用的类型就可以消除大量的样板代码，同时还能完成同样的工作。下面来看丰富的Monad实例：Maybe、Either和IO。

使用Maybe Monad和Either Monad来处理异常

除了用来包装有效值，Monadic的结构也可用于建模null或undefined。函数式编程通常使用Maybe和Either来做下列事情。

  • 隔离不纯。
  • 合并判空逻辑。
  • 避免异常。
  • 支持函数组合。
  • 中心化逻辑，用于提供默认值。
用Maybe合并判空

Maybe Monad侧重于有效整合null -判断逻辑。Maybe是一个包含两个具体字类型的空类型（标记类型）。

  • Just(value)——表示值的容器。
  • Nothing()——表示要么没有值或者没有失败的附加信息。当然，还可以应用函数到Nothing上。
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
const R = ramda;
class Maybe { //容器类型（父类）
    static just(a) {
        return new Just(a);
    }
    static nothing() {
        return new Nothing();
    }
    static fromNullable(a) {
        return a != null ? Maybe.just(a) :
            Maybe.nothing(); //由一个可为空的类型创建 Maybe（即构造函数）。如果值为空，则 建一个 Nothing； 否则， 将值存储在 Just 子类型中来表示其存在性
    }
    static of (a) {
        return Maybe.just(a);
    }
    get isNothing() {
        return false;
    }
    get isJust() {
        return false;
    }
}
class Just extends Maybe { //Just 子类型用于处理存在的值
    constructor(value) {
        super();
        this._value = value;
    }
    get value() {
        return this._value;
    }
    map(f) {
        return Just.of(f(this.value)); //将映射函数应用于 Just，变换其中的值，并存储回容器中
    }
    getOrElse() {
        return this.value; //Monad 提供默认的一元操
    }
    filter(f) {
        Maybe.fromNullable(f(this.value) ? this.value : null);
    }
    get isJust() {
        return true;
    }
    toString() { //返回该结构的文本描述
        return `Maybe.Just(${this.value})`;
    }
}
class Nothing extends Maybe { //Nothing子类型用于为无值的情况提供保护
    map(f) {
        return this;
    }
    get value() {
        throw new TypeError(
            'Can"t extract the valueof a Nothing.'); //任何试图从 Nothing 类型中取值的操作会引发表征错误使用 Monad的异常（后文会予以介绍）
    }
    getOrElse(other) {
        return other; //忽略值，返回 other
    }
    filter() {
        return this.value; //如果存在的值满足所给的断言，则返回包含值的 Just，否则，返回 Nothing
    }
    get isNothing() {
        return true;
    }
    toString() {
        return 'Maybe.Nothing'; //返回结构的文本描述
    }
}

Maybe显式地抽象对“可空”值（null和undefined）的操作，可让开发者关注更重要的事情。如上述代码所示，Maybe是Just和Nothing的抽象，Just和Nothing各自包含自己的Monadic的实现。正如前面提到的，对于Monadic操作的实现最终取决于具体类型给予的语义。例如，map的行为具体取决于该类型是 Nothing 还是Just

1
2
3
4
5
6
7
8
9
10
11
12
13
const find = (db, id) => (id ? {
    name: '小红',
    address: '北京'
} : undefined)
const findStudent = R.curry((db, id) => Maybe.fromNullable(find(db, id)))
const findStudentByDB = findStudent('DB');
// 如果有意义得值传入会生成just
console.log(findStudentByDB('id').map(R.prop('address')).value)

// 如果没有意义得值会生成nothing,如果使用value取值会报错
console.log(findStudentByDB(undefined).map(R.prop('address')).getOrElse(123))
//赋值时需要注意
document.querySelector('#student-firstname').value = username.getOrElse('Enter first name');

提升函数

很明显，Maybe擅长于集中管理的无效数据的检查，但它没有（双关Nothing）提供关于什么地方出了错的信息。我们需要一个更积极的，可以知道失败原因的解决方案。解决这个问题，要最好的工具是Either monad。

使用Either

Either跟Maybe略有不同。Either代表的是两个逻辑分离的值a和b，它们永远不会同时出现。这种类型包括以下两种情况。

Left(a)——包含一个可能的错误消息或抛出的异常对象。
Right(b)——包含一个成功的值。

Either通常操作右值，这意味着在容器上映射函数总是在Right(b)子类型上执行。它类似于Maybe的Just分支。

Either的常见用法是为失败的结果提供更多的信息。在不可恢复的情况下，左侧可以包含一个合适的异常对象

与MayBe 类似，合法值也是主右的

IO Monad

3. 无重复字符的最长子串

算法 / 关联题目

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
var lengthOfLongestSubstring = function (s) {
    if (s.length == 0) return 0;
    var len = 1;
    for (var i = 0; i < s.length; i++) {
        var str = s[i];
        for (var j = i + 1; j < s.length; j++) {
            var nstr = s[j];
            var mark = false;
            for (var k = 0; k < str.length; k++) {
                if (str[k] === nstr) {
                    mark = true;
                    break
                }
            }
            if (mark === false) {
                str += nstr;
                if (str.length > len) len = str.length;
            } else {
                break;
            }

        }
    }
    return len;
};

复杂度分析

  • 时间复杂度：

  • 空间复杂度：

暴力解法优化

通过map缓存已经查找过的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 */
var lengthOfLongestSubstring = function (s) {
    if (s.length == 0) return 0;
    var len = 1;
    for (var i = 0; i < s.length; i++) {
        var map = {
            length: 1
        };
        map[s[i]] = true;
        for (var j = i + 1; j < s.length; j++) {
            var nstr = s[j];
            if (!map[nstr]) {
                map[nstr] = true;
                map.length++;
                if (map.length > len) len = map.length
            } else {
                break;
            }
        }
    }
    return len;
};

复杂度分析

  • 时间复杂度：,

  • 空间复杂度：,时间换空间

窗口移动

  • 如果下一个字符和之前的字符重复，则重复字符之前的字符都被舍弃

  • 每次读取新字符，判断一次当前位置到舍弃位置的长度是否比之前的总长度大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var lengthOfLongestSubstring = function (s) {
    if (s == '') return 0;
    if (s == ' ') return 1;
    var map = {
        start: 0,
        end: 0,
        len: 0
    }
    for (var i = 0; i < s.length; i++) {
        if (map[s[i]] !== undefined && map[s[i]] > map.start) {
            map.start = map[s[i]];
        }
        map[s[i]] = i + 1;
        map.end = i + 1;
        map.len = Math.max(map.end - map.start, map.len)
    }
    return map.len;
};

复杂度分析

  • 时间复杂度：,

  • 空间复杂度：,时间换空间

优化窗口移动

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var lengthOfLongestSubstring = function (s) {
    let map = new Map(),
        //i为上面方法的start指针
        i = 0,
        j = 0,
        max = 0;
    for (j = 0; j < s.length; j++) {
        if (map.has(s[j])) {
            //如果存在，当前这个值对应的索引不能比start指针小
            i = Math.max(map.get(s[j]) + 1, i)
        }
        map.set(s[j], j);
        max = Math.max(max, j - i + 1)
        console.log(map, i, max);

    }
    return max;
};
  • Copyrights © 2015-2025 SunZhiqi

此时无声胜有声！

支付宝
微信