Y_qwq

Y_qwq 查看完整档案

深圳编辑中山大学新华学院  |  软件工程 编辑llll  |  前端开发 编辑 github.com/Y-qwq 编辑
编辑

○( ^皿^)っHiahiahia…

个人动态

Y_qwq 赞了回答 · 1月12日

解决沿用jquery不转三大框架,会被淘汰吗?

你这一句界面都挺粗糙的
是看不上element饿了么的UI设计还是ant-design蚂蚁的UI设计?
大家都是前端,就算你是全栈,但是你说别人的界面粗糙,这可就忍不了了啊

关注 10 回答 12

Y_qwq 回答了问题 · 2019-12-05

HTML的video标签如何实现有声自动播放?

这个是受到浏览器限制的(不允许用户在没有交互的情况下自动有声播放视频)
根据限制条件,你可以静音播放,添加事件监听,当用户操作后添加声音。(参考youtube点击取消静音)

关注 2 回答 1

Y_qwq 回答了问题 · 2019-12-05

解决vscode cannot find module './styles.css'

React中,css样式引入方式是import "./styles.css"

关注 6 回答 6

Y_qwq 关注了用户 · 2019-12-05

Mongoing中文社区 @mongoing

欢迎关注微信公众号:mongoing-mongoing
MongoDB中文社区,线下活动(深圳,北京,上海),博客,讨论: http://www.mongoing.com

关注 320

Y_qwq 发布了文章 · 2019-11-03

函数提升的蜜汁行为

众所周知,JS里,变量有变量提升,函数有函数提升。ES6之前没有块级作用域。
然而,当用函数声明的方法定义function并遇到非ES6情况下的{}时,却有一些蜜汁行为。

一道题引发的惨案

    if (true) {
      a = 1
      function a() {}
      // a = 1
      console.log(a)
    }
    console.log(a)
    if (true) {
      // a = 1
      function a() {}
      a = 1
      console.log(a)
    }
    console.log(a)

理想状态下:
if(){}里不存在letconst。应该不会产生Block块级作用域。
再根据函数提升,以上两者相当于

    function a() {}
    a = 1
    console.log(a)
    console.log(a)

即输出11

实际情况却是:
前者11
后者1f a(){}

调试分析

debugger调试分析问题
先将问题简化下

    debugger
    console.log(a)
    if (true) {
      debugger
      function a() {}
      debugger
    }
    console.log(a)

输出undefinedf a(){}
第一个debugger,js开始执行时,全局声明了a但未定义。
1.png

第二个debuggera的函数提升提升到块级作用域Block上,而非全局。
2.png

第三个debugger,此处才将Block内的a赋值给全局a
3.png

为什么是强调说是赋值而非直接在全局声明呢。
现在将a=1补上即再看一遍过程即可说明

    debugger
    console.log(a)
    if (true) {
      debugger
      a = 1
      debugger
      function a() {}
      debugger
    }
    console.log(a)

第三个debuger时,1会覆盖掉Block里的f a(){}
4.png

第四个debuger时,执行到function的定义时,会发现全局a变成了1
5.png

最后这一步执行的前后,很明显可以看出,当执行当函数声明语句时,js会将块级里的函数名属性值赋给全局的函数名属性,即window.a = block.a
实际执行情况约等于如下

    var a;// 定义但未赋值,由function a(){}产生的。
    if (true) {
      let a = function a(){} // 函数提升到块级
      a = 1
      window.a = a // 声明语句时将块级a赋值给全局a
      console.log(a)
    }
    console.log(a)

个人理解总结

结论仅个人从结果推导,非查阅文档所得,所以未必准确。

(非es6情况下)当{}里存在函数声明(function a(){}这种类型)时,js执行情况如下:

  1. js开始执行,函数名全局声明但未定义
  2. 进入函数声明的{},产生临时Block,并且function函数提升到Block
  3. 直到执行该function的定义语句时,才会把Block里该函数名的属性赋值给全局(哪怕改变了该属性甚至类型),举例:window.a = a
查看原文

赞 0 收藏 0 评论 0

Y_qwq 收藏了文章 · 2019-10-24

mongoose学习笔记(超详细)

原文出处

名词解释

  • Schema: 一种以文件形式存储的数据库模型骨架,不具备数据库的操作能力
  • Model: 由Schema编译而成的假想(fancy)构造器,具有抽象属性和行为。Model的每一个实例(instance)就是一个document。document可以保存到数据库和从数据库返回。
  • Instance: 由Model创建的实例。

概念解析

SQL术语/概念MongoDB术语/概念解释/说明
rdatabasedatabase-
tablecollection数据库表/集合
rowdocument数据记录行/文档
columnindex数据记录行/文档
table joins-表连接,MongoDB不支持
primary keyprimary key 主键MongoDB自动将_id字段设置为主键

定义Schema

mongoose中任何任何事物都是从Schema开始的。每一个Schema对应MongoDB中的一个集合(collection)。Schema中定义了集合中文档(document)的样式。

var mongoose = require('mongoose');
var Schema = mongoose.Schema;
var blogSchema = new Schema({  
    title:  String,  
    author: String,  
    body:   String,  
    comments: [{ body: String, date: Date }],  
    date: { type: Date, default: Date.now },  
    hidden: Boolean, 
    meta: {    votes: Number,    favs:  Number  }
});

如果之后想要在Schema中添加键,可以使用Schema#add方法。

创造一个model

为了使用schema定义,我们需要转换blogSchema为一个Model。使用

mongoose.model(modelName, schema)
var BlogModel = mongoose.model('Blog', blogSchema);// 开始吧!

实例方法

Model的实例是document。实例有很多内置的方法,我们也可以给实例自定义方法。

var animalSchema = new Schema({ 
    name: String, type: String    
});
animalSchema.methods.findSimilarTypes = function (cb) {
    return this.model('Animal').find({ type: this.type }, cb);
}

现在所有的动物实例有findSimilarTypes方法。

var AnimalModel = mongoose.model('Animal', animalSechema);
var dog = new AnimalModel({ type: 'dog' });
dog.findSimilarTypes(function (err, dogs) { 
    console.log(dogs); // woof
});

重写一个默认的实例方法可能会导致不期待的结果。

Statics方法

给Model添加一个静态方法也是简单的。

animalSchema.statics.findByName = function (name, cb) {
    this.find({ name: new RegExp(name, 'i') }, cb);
}

var AnimalModel = mongoose.model('Animal', animalSchema);
AnimalModel.findByName('fido', function (err, animals) { 
    console.log(animals);
});

methods和statics的区别

区别就是一个给Model添加方法(statics),
一个给实例添加方法(methods)。

索引

MongoDB支持二级索引,定义索引有两种方式

路径级别 schema级别

var animalSchema = new Schema({  
    name: String,  
    type: String,  
    tags: { type: [String], index: true } // field level
    });

animalSchema.index({ name: 1, type: -1 }); // schema level, 1是正序,-1是倒序

如果要建立复合索引的话,在schema级别建立是必要的。

索引或者复合索引能让搜索更加高效,默认索引就是主键索引ObjectId,属性名为_id。

数据库中主要的就是CRUD操作,建立索引可以提高查询速度。但是过多的索引会降低CUD操作。深度好文如下

http://www.cnblogs.com/huangx...

虚拟属性

Schema中如果定义了虚拟属性,那么该属性将不写入数据库。写入数据库的还是原来的属性。

// 定义一个schema

var personSchema = new Schema({  
    name: {  first: String,    last: String  }
});

// 编译
var Person = mongoose.model('Person', personSchema);// 创造实例

var bad = new Person({ 
    name: { first: 'Walter', last: 'White' }
});

我们将名字分成名字和姓,如果要得到全名,我们需要

console.log(bad.name.first + ' ' + bad.name.last); // Walter White

这样无疑是麻烦的,我们可以通过虚拟属性的getter来解决这个问题。

personSchema.virtual('name.full').get(function () { 
    return this.name.first + ' ' + this.name.last;
});

那么就可以使用bad.name.full直接调用全名了。

反之,如果我们知道虚拟属性name.full,通过setter也可以得到组成name.full的每一项。

personSchema.virtual('name.full').set(function (name) {  
    var split = name.split(' ');  
    this.name.first = split[0];  
    this.name.last = split[1];
});
...
mad.name.full = 'Breaking Bad';
console.log(mad.name.first); // Breaking
console.log(mad.name.last);  // Bad

配置项

schema有一些配置项可以使用,有两种方式:

new Schema({…}, options)

var schema = new Schema({...});
schema.set(option, value);

有效的配置有:

  1. autoIndex(默认true)
  2. capped
  3. collection
  4. id _id(默认true)
  5. read safe(默认true)
  6. shardKey strict(默认true)
  7. toJSON
  8. toObject
  9. versionKey
  10. typeKey
  11. validateBeforeSave
  12. skipVersioning
  13. timestamps
  14. useNestedStrict
  15. retainKeyOrder

autoIndex–自动索引

应用开始的时候,Mongoose对每一个索引发送一个ensureIndex的命令。索引默认(_id)被Mongoose创建。

当我们不需要设置索引的时候,就可以通过设置这个选项。

var schema = new Schema({..}, { autoIndex: false });
var Clock = mongoose.model('Clock', schema);
Clock.ensureIndexes(callback);

bufferCommands

似乎是说这个(mongoose buffer)管理在mongoose连接关闭的时候重连,如果取消buffer设置,如下:(存疑)

var schema = new Schema({..}, { bufferCommands: false });

capped–上限设置

如果有数据库的批量操作,该属性能限制一次操作的量,例如:

new Schema({...},{capped:1024});  //一次操作上线1024条数据

当然该参数也可是对象,包含size、max、autiIndexId属性

new Schema({...},{capped:{size:1024,max:100,autoIndexId:true}});

collection–集合名字

在MongDB中默认使用Model的名字作为集合的名字,如过需要自定义集合的名字,可以通过设置这个选项。

var schema = new Schema({...}, {collection: 'yourName'});

id

mongoose分配给每一个schema一个虚拟属性id,它是一个getter。返回的是_id转换为字符串后的值。如果不需要为schema添加这个getter,可以通过id配置修改。

// 默认行为
var pageSchema = new Schema({ name: String });
var pageModel = mongoose.model('Page', pageSchema);
var p = new pageModel({ name: 'mongodb.org' });
console.log(p.id); // '50341373e894ad16347efe01'

// 禁止id
var pageSchema = new Schema({ name: String }, { id: false } );
var pageModel = mongoose.model('Page', pageSchema);
var p = new pageModel({ name: 'mongodb.org' });
console.log(p.id); // undefined

_id

在一个schema中如果没有定义_id域(field),那么mongoose将会默认分配一个_id域(field)。类型是ObjectId。如果不需要使用这个默认的选择,可以通过设置这个选项。

通过在schema中设置这个字段可以阻止生成mongoose获得_id。但是在插入的时候仍然会生成_id。设置这个字段之后,如果再使用Schema.set(’_id’, false)将无效。

// 默认行为
var pageSchema = new Schema({ name: String });
var pageModel = mongoose.model('Page', pageSchema);
var p = new pageModel({ name: 'mongodb.org' });
console.log(p); // { _id: '50341373e894ad16347efe01', name: 'mongodb.org' }

// 禁用 _id
var pageSchema = new Schema({ name: String }, { _id: false });
// schema构造器设置之后,不要再像下面这样设置
// var schema = new Schema({ name: String });
// schema.set('_id', false);

var PageModel = mongoose.model('Page', pageSchema);
var p = new pageModel({ name: 'mongodb.org' });
console.log(p); // { name: 'mongodb.org' }
// 当插入的时候,MongoDB将会创建_id
p.save(function (err) {  
    if (err) return handleError(err);  
    pageModel.findById(p, function (err, doc) { 
        if (err) return handleError(err);   
        console.log(doc); 
        // { name: 'mongodb.org', _id: '50341373e894ad16347efe12' }  
    })
})

为什么不建议使用set

read

允许在schema级别设置query#read,对于所有的查询,提供给我们一种方法应用默认的ReadPreferences。

safe

这个配置会在MongoDB所有的操作中起作用。如果设置成true就是在操作的时候要等待返回的MongoDB返回的结果,比如update,要返回影响的条数,才往后执行,如果safe:false,则表示不用等到结果就向后执行了。
默认设置为true能保证所有的错误能通过我们写的回调函数。我们也能设置其它的安全等级如:

{ j: 1, w: 2, wtimeout: 10000 }

表示如果10秒内写操作没有完成,将会超时。
关于j和w,这里有很好的解释。

http://kyfxbl.iteye.com/blog/...

shardKey

需要mongodb做分布式,才会使用该属性。

strict

默认是enabled,如果实例中的域(field)在schema中不存在,那么这个域不会被插入到数据库。

var ThingSchema = new Schema({a:String});
var ThingModel = db.model('Thing',SchemaSchema);
var thing = new Thing({iAmNotInTheThingSchema:true});
thing.save();//iAmNotInTheThingSchema这个属性将无法被存储

// 通过doc.set()设置也会受到影响。
var thingSchema = new Schema({..})
var Thing = mongoose.model('Thing', thingSchema);
var thing = new Thing;
thing.set('iAmNotInTheSchema', true);
thing.save(); // iAmNotInTheSchema is not saved to the db

如果取消严格选项,iAmNotInTheThingSchema将会被存入数据库

var thingSchema = new Schema({..}, { strict: false });
var thing = new Thing({ iAmNotInTheSchema: true });
thing.save(); // iAmNotInTheSchema is now saved to the db!!

该选项也可以在Model级别使用,通过设置第二个参数,例如:

var ThingModel = db.model('Thing');
var thing1 = new ThingModel(doc,true);  //启用严格
var thing2 = new ThingModel(doc,false); //禁用严格

strict也可以设置为throw,表示出现问题将会抛出错误而不是抛弃不合适的数据。

注意:

  • 不要设置为false除非你有充分的理由。

在mongoose v2里默认是false。

在实例上设置的任何键值对如果再schema中不存在对应的,将会被忽视。

var thingSchema = new Schema({..})
var Thing = mongoose.model('Thing', thingSchema);
var thing = new Thing;
thing.iAmNotInTheSchema = true;
thing.save(); // iAmNotInTheSchema 不会保存到数据库。

toJSON

和toObject类似,选择这个选项为true后,但是只有当实例调用了toJSON方法后,才会起作用。

var schema = new Schema({ name: String });
schema.path('name').get(function (v) { 
    return v + ' is my name';
});

schema.set('toJSON', { getters: true, virtuals: false });
var M = mongoose.model('Person', schema);
var m = new M({ name: 'Max Headroom' });
console.log(m.toObject()); // { _id: 504e0cd7dd992d9be2f20b6f, name: 'Max Headroom' }
console.log(m.toJSON()); // { _id: 504e0cd7dd992d9be2f20b6f, name: 'Max Headroom is my name' }
console.log(JSON.stringify(m)); // { "_id": "504e0cd7dd992d9be2f20b6f", "name": "Max Headroom is my name" }

可以看出,配置属性name对toObject没影响,对toJSON有影响。

toObject

选择这个选项为true后,默认对这个schema所有的实例都有作用。不需要实例手动调用。

var schema = new Schema({ name: String });
schema.path('name').get(function (v) {  
    return v + ' is my name';
});

schema.set('toObject', { getters: true });
var M = mongoose.model('Person', schema);
var m = new M({ name: 'Max Headroom' });
console.log(m); // { _id: 504e0cd7dd992d9be2f20b6f, name: 'Max Headroom is my name' }

较上面不同的是,没有virtuals: false这个设置。

typeKey

在mongoose里,如果schema里有个对象,并且这个对象有个type键,mongoose将会将这个作为一种类型声明。

// Mongoose 认为loc字段的类型是一个字符串,而不是有type这个字段 
var schema = new Schema({ loc: { type: String, coordinates: [Number] } });

然而,对于一些应用来说,type字段是必要的。那么可以通过typeKey来设置。

var schema = new Schema({ 
    // Mongoose 这时候认为loc字段有两个键,一个是type,一个是coordinates  
    loc: { type: String, coordinates: [Number] },  
    // Mongoose 这时候认为name字段的类型是字符串。  
    name: { $type: String }
},{ typeKey: '$type' }); // '$type'键意味着这是一个类型宣告,而不是默认的type

validateBeforeSave

默认得,文档被保存到数据库的时候会自动验证,这是为了防止无效的文档。如果想要手动处理验证,并且能保存不通过验证的文档,可以设置这个选项为false。

var schema = new Schema({ name: String });
schema.set('validateBeforeSave', false);
schema.path('name').validate(function (value) {   
    return v != null;
});
var M = mongoose.model('Person', schema);
var m = new M({ name: null });
m.validate(function(err) { 
    console.log(err); // 将会告诉你null不被允许
});
m.save(); // 尽管数据无效,但是仍然可以保存。

versionKey

版本锁设置在每一个文档(document)上,由mogoose生成。默认的值是__v,但是可以自定义。

var schema = new Schema({ name: 'string' });
var Thing = mongoose.model('Thing', schema);
var thing = new Thing({ name: 'mongoose v3' });
thing.save(); // { __v: 0, name: 'mongoose v3' }

// 自定义版本锁
new Schema({..}, { versionKey: '_somethingElse' });
var Thing = mongoose.model('Thing', schema);
var thing = new Thing({ name: 'mongoose v3' });
thing.save(); // { _somethingElse: 0, name: 'mongoose v3' }

不要将这个选项设置为false除非你知道你在做什么。

skipVersioning

http://aaronheckmann.tumblr.c...

按照这里的说法,大致是说,加入在一个博客系统中,一个人所有的评论是一个数组,那么所有的评论是有索引的,比如某一条评论的body,comments.3.body,这里3是索引。假如一个评论者(A)想要修改自己的评论,但是此时另一个评论者(B)删除(或其他操作)了自己的评论,那么对A的索引可能会造成变化,此时对A的操作会发生错误。

为了改变这个问题,mongoose v3添加了version key配置。无论什么时候修改一个数组潜在地改变数组元素位置,这个version key(__V)的值会加1。在where条件中也需要添加__v条件,如果能通过(数组索引没改变),就可以修改,例如:

posts.update(
    { _id: postId, __v: verionNumber } ,
    { $set: { 'comments.3.body': updatedText }}
);

如果在更新之前删除了评论,那么就会发生错误。

post.save(function (err) { 
    console.log(err); // Error: No matching document found.
});

timestamps

如果在schema设置这个选项,createdAt和updatedAt域将会被自动添加的文档中。它们默认的类型是Date,默认的名字是createdAt和updatedAt,不过我们可以自己修改。

var thingSchema = new Schema({..}, { timestamps: { createdAt: 'created_at' } });
var Thing = mongoose.model('Thing', thingSchema);
var thing = new Thing();
thing.save(); // created_at & updatedAt将会被包含在文档。

useNestedStrict

在mongoos 4, update()和findOneAndUpdate()方法只检查顶级schema的strict的选项设置。

var childSchema = new Schema({}, { strict: false });// 这里parentSchema是topSchema,而childSchema是subSchema。
var parentSchema = new Schema({ child: childSchema }, { strict: 'throw' });
var Parent = mongoose.model('Parent', parentSchema);
Parent.update({}, { 'child.name': 'Luke Skywalker' }, function(error) {  
    // 发生错误因为parentSchema设置了strict: 'throw'}
    // 即使childSchema设置了{strict: false}
});
var update = { 'child.name': 'Luke Skywalker' };
var opts = { strict: false };
Parent.update({}, update, opts, function(error) { 
    // 这个可以通过因为重写了parentSchema的strict选项
});

如果设置了useNestedStrict为true,mogoose在更新时使用childSchema的strict选项。

var childSchema = new Schema({}, { strict: false });
var parentSchema = new Schema({ child: childSchema },  { strict: 'throw', useNestedStrict: true });
var Parent = mongoose.model('Parent', parentSchema);
Parent.update({}, { 'child.name': 'Luke Skywalker' }, function(error) { 
    // 可以更新
});

retainKeyOrder

默认得,mongoose会转换实体中键的顺序。比如

new Model({ first: 1, second: 2 })

将会在MongoDB中存储为{ second: 2, first: 1 };这带来了极大的不方便。

Mongoose v4.6.4 有一个retainKeyOrder选项确保mongoose不会改变键的顺序。

参考

http://cnodejs.org/topic/504b...

http://www.nodeclass.com/api/...

http://mongoosejs.com/docs/gu...

查看原文

Y_qwq 收藏了文章 · 2019-09-22

javascript背包问题详解

image_1c3ds1q091ubg5bm1gaj3vv1jm19.png-64.6kB

引子

打算好好学一下算法,先拿背包问题入手。但是网上许多教程都是C++或java或python,大部分作者都是在校生,虽然算法很强,但是完全没有工程意识,全局变量满天飞,变量名不明所以。我查了许多资料,花了一个星期才搞懂,最开始的01背包耗时最多,以前只会枚举(就是普通的for循环,暴力地一步步遍历下去),递归与二分,而动态规划所讲的状态表与状态迁移方程为我打开一扇大门。

01背包问题

篇幅可能有点长,但请耐心看一下,你会觉得物有所值的。本文以后还会扩展,因为我还没有想到完全背包与多重背包打印物品编号的方法。如果有高人知道,劳烦在评论区指教一下。

注意,由于社区不支持LaTex数学公式,你们看到${xxxx}$,就自己将它们过滤吧。

1.1 问题描述:

有${n}$件物品和${1}$个容量为W的背包。每种物品均只有一件,第${i}$件物品的重量为${weights[i]}$,价值为${values[i]}$,求解将哪些物品装入背包可使价值总和最大。

对于一种物品,要么装入背包,要么不装。所以对于一种物品的装入状态只是1或0, 此问题称为01背包问题

1.2 问题分析:

数据:物品个数${n=5}$,物品重量${weights=[2,2,6,5,4]}$,物品价值${values=[6,3,5,4,6]}$,背包总容量${W=10}$。

我们设置一个矩阵${f}$来记录结果,${f(i, j)}$ 表示可选物品为 ${i...n}$ 背包容量为 ${j(0<=j<=W)}$ 时, 背包中所放物品的最大价值。

wvi\j012345678910
260
231
652
543
464

我们先看第一行,物品0的体积为2,价值为6,当容量为0时,什么也放不下,因此第一个格式只能填0,程序表示为${f(0,0) = 0}$或者${f[0][0] = 0}$。 当${j=1}$时,依然放不下${w_0}$,因此依然为0,${f(0, 1) = 0}$。 当${j=2}$时,能放下${w_0}$,于是有 ${f(0, 2)\ = \ v_0=6}$。 当${j=3}$时,也能放下${w_0}$,但我们只有一个物品0,因此它的值依然是6,于是一直到${j=10}$时,它的值都是${v_0}$。

wvi\j012345678910
26000666666666
231
652
543
464

根据第一行,我们得到如下方程

clipboard.png

当背包容量少于物品価积时,总价值为0,否则为物品的价值

然后我们看第二行,确定确定${f(1,0...10)}$这11个元素的值。当${j=0}$ 时,依然什么也放不下,值为0,但我们发觉它是上方格式的值一样的,${f(1,0)=0}$。 当${j=1}$时,依然什么也放不下,值为0,但我们发觉它是上方格式的值一样的,${f(1,1)=0}$. 当${j=2}$时,它可以选择放入物品1或不放。

如果选择不放物品1,背包里面有物品0,最大价值为6。

如果选择放入物品1,我们要用算出背包放入物品1后还有多少容量,然后根据容量查出它的价值,再加上物品1的价值,即${f(0,j-w_1)+v_1}$ 。由于我们的目标是尽可能装最值钱的物品, 因此放与不放, 我们需要通过比较来决定,于是有

clipboard.png

显然${v_1=2,v_0=6}$, 因此这里填${v_0}$。 当${j=3}$时, 情况相同。 当${j=4}$,能同时放下物品0与物品1,我们这个公式的计算结果也合乎我们的预期, 得到${f(1,4)=9}$。 当${j>4}$时, 由于背包只能放物品0与物品1,那么它的最大价值也一直停留在${v_0+v_1=9}$

wvi\j012345678910
26000666666666
23100669999999
652
543
464

我们再看第三行,当${j=0}$时,什么都放不下,${f(2,0)=0}$。当${j=1}$时,依然什么也放不下,${f(2,1)=0}$,当${j=2}$时,虽然放不下${w_2}$,但我们根据上表得知这个容号时,背包能装下的最大价值是6。继续计算下去,其实与上面推导的公式结果是一致的,说明公式是有效的。当${j=8}$时,背包可以是放物品0、1,或者放物品1、2,或者放物品0、2。物品0、1的价值,我们在表中就可以看到是9,至于其他两种情况我们姑且不顾,我们目测就知道是最优值是${6+5=11}$, 恰恰我们的公式也能正确计算出来。当${j=10}$时,刚好三个物品都能装下,它们的总值为14,即${f(2,10)=14}$

第三行的结果如下:

wvi\j012345678910
26000666666666
23100669999999
65200669999111114
543
464

整理一下第1,2行的适用方程:

clipboard.png

我们根据此方程,继续计算下面各列,于是得到

wvi\j012345678910
26000666666666
23100669999999
65200669999111114
543006699910111314
4640066991212151515

至此,我们就可以得到解为15.

我们最后根据0-1背包问题的最优子结构性质,建立计算${f(i,j)}$的递归式:

clipboard.png

//by 司徒正美
 function knapsack(weights, values, W){
    var n = weights.length -1
    var f = [[]]
    for(var j = 0; j <= W; j++){
        if(j < weights[0]){ //如果容量不能放下物品0的重量,那么价值为0
           f[0][j] = 0
        }else{ //否则等于物体0的价值
           f[0][j] = values[0]
        }
    }
    for(var j = 0; j <= W; j++){
        for(var i = 1; i <= n; i++ ){
            if(!f[i]){ //创建新一行
                f[i] = []
            }
            if(j < weights[i]){ //等于之前的最优值
                f[i][j] = f[i-1][j]
            }else{
                f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]] + values[i]) 
            }
        }
    }
    return f[n][W]
}
var a = knapsack([2,2,6,5,4],[6,3,5,4,6],10)
console.log(a)

1.3 各种优化:

合并循环

现在方法里面有两个大循环,它们可以合并成一个。

function knapsack(weights, values, W){
    var n = weights.length;
    var f = new Array(n)
    for(var i = 0 ; i < n; i++){
        f[i] = []
    }
   for(var i = 0; i < n; i++ ){
       for(var j = 0; j <= W; j++){
            if(i === 0){ //第一行
                f[i][j] = j < weights[i] ? 0 : values[i]
            }else{
                if(j < weights[i]){ //等于之前的最优值
                    f[i][j] = f[i-1][j]
                }else{
                    f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]] + values[i]) 
                }
            }
        }
    }
    return f[n-1][W]
}

然后我们再认真地思考一下,为什么要孤零零地专门处理第一行呢?f[i][j] = j < weights[i] ? 0 : values[i]是不是能适用于下面这一行f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]] + values[i]) 。Math.max可以轻松转换为三元表达式,结构极其相似。而看一下i-1的边界问题,有的书与博客为了解决它,会添加第0行,全部都是0,然后i再往下挪。其实我们也可以添加一个${-1}$行。那么在我们的方程中就不用区分${i==0}$与${0>0}$的情况,方程与其他教科书的一模一样了!

clipboard.png

function knapsack(weights, values, W){
    var n = weights.length;
    var f = new Array(n)
    f[-1] = new Array(W+1).fill(0)
    for(var i = 0 ; i < n ; i++){ //注意边界,没有等号
        f[i] = new Array(W).fill(0)
        for(var j=0; j<=W; j++){//注意边界,有等号
            if( j < weights[i] ){ //注意边界, 没有等号
                f[i][j] = f[i-1][j]
            }else{
                f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]]+values[i]);//case 3
            }
        }
    }
    return f[n-1][W]
}
wvi\j012345678910
XX-1000000000000
26000666666666
23100669999999
65200669999111114
543006699910111314
4640066991212151515

负一行的出现可以大大减少了在双层循环的分支判定。是一个很好的技巧。

注意,许多旧的教程与网上文章,通过设置二维数组的第一行为0来解决i-1的边界问题(比如下图)。当然也有一些思维转不过来的缘故,他们还在坚持数字以1开始,而我们新世代的IT人已经确立从0开始的编程思想。

image_1c3lm81p3gd09n5pjk1i4aif92d.png-110.2kB

选择物品

上面讲解了如何求得最大价值,现在我们看到底选择了哪些物品,这个在现实中更有意义。许多书与博客很少提到这一点,就算给出的代码也不对,估计是在设计状态矩阵就出错了。

仔细观察矩阵,从${f(n-1,W)}$逆着走向${f(0,0)}$,设i=n-1,j=W,如果${f(i,j)}$==${f(i-1,j-w_i)+v_i}$说明包里面有第i件物品,因此我们只要当前行不等于上一行的总价值,就能挑出第i件物品,然后j减去该物品的重量,一直找到j = 0就行了。

//by 司徒正美
function knapsack(weights, values, W){
    var n = weights.length;
    var f = new Array(n)
    f[-1] = new Array(W+1).fill(0)
    var selected = [];
    for(var i = 0 ; i < n ; i++){ //注意边界,没有等号
        f[i] = [] //创建当前的二维数组
        for(var j=0; j<=W; j++){ //注意边界,有等号
            if( j < weights[i] ){ //注意边界, 没有等号
                f[i][j] = f[i-1][j]//case 1
            }else{
                f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]]+values[i]);//case 2
            }
        }
    }
    var j = W, w = 0
    for(var i=n-1; i>=0; i--){
         if(f[i][j] > f[i-1][j]){
             selected.push(i)
             console.log("物品",i,"其重量为", weights[i],"其价格为", values[i])
             j = j - weights[i];
             w +=  weights[i]
         }
     }
    console.log("背包最大承重为",W," 现在重量为", w, " 总价值为", f[n-1][W])
    return [f[n-1][W], selected.reverse() ]
}
var a = knapsack([2,3,4,1],[2,5,3, 2],5)
console.log(a)
var b = knapsack([2,2,6,5,4],[6,3,5,4,6],10)
console.log(b)

image_1c3k62d511dtgo7gud815q866m16.png-22.8kB
image_1c3k617gc6jp10pn1ean1lv81boqp.png-28.5kB

使用滚动数组压缩空间

所谓滚动数组,目的在于优化空间,因为目前我们是使用一个${i*j}$的二维数组来储存每一步的最优解。在求解的过程中,我们可以发现,当前状态只与前一行的状态有关,那么更之前存储的状态信息已经无用了,可以舍弃的,我们只需要存储当前状态和前一行状态,所以只需使用${2*j}$的空间,循环滚动使用,就可以达到跟${i*j}$一样的效果。这是一个非常大的空间优化。

//by 司徒正美
function knapsack(weights, values, W){
    var n = weights.length
    var lineA = new Array(W+1).fill(0)
    var lineB = [], lastLine = 0, currLine 
    var f = [lineA, lineB]; //case1 在这里使用es6语法预填第一行
    for(var i = 0; i < n; i++){ 
        currLine = lastLine === 0 ? 1 : 0 //决定当前要覆写滚动数组的哪一行
        for(var j=0; j<=W; j++){
            f[currLine][j] = f[lastLine][j] //case2 等于另一行的同一列的值
            if( j>= weights[i] ){                         
                var a = f[lastLine][j]
                var b = f[lastLine][j-weights[i]] + values[i]
                f[currLine][j] = Math.max(a, b);//case3
            }
           
        }
        lastLine = currLine//交换行
   }
   return f[currLine][W];
}

var a = knapsack([2,3,4,1],[2,5,3, 2],5)
console.log(a)
var b = knapsack([2,2,6,5,4],[6,3,5,4,6],10)
console.log(b)

我们还可以用更hack的方法代替currLine, lastLine

//by 司徒正美
function knapsack(weights, values, W){
    var n = weights.length
   
    var f = [new Array(W+1).fill(0),[]], now = 1, last //case1 在这里使用es6语法预填第一行
    for(var i = 0; i < n; i++){ 
        for(var j=0; j<=W; j++){
            f[now][j] = f[1-now][j] //case2 等于另一行的同一列的值
            if( j>= weights[i] ){                         
                var a = f[1-now][j]
                var b = f[1-now][j-weights[i]] + values[i]
                f[now][j] = Math.max(a, b);//case3
            }
         }
         last = f[now]
         now = 1-now // 1 - 0 => 1;1 - 1 => 0; 1 - 0 => 1 ....
   }
   return last[W];
}
var a = knapsack([2,3,4,1],[2,5,3, 2],5)
console.log(a)
var b = knapsack([2,2,6,5,4],[6,3,5,4,6],10)
console.log(b)

注意,这种解法由于丢弃了之前N行的数据,因此很难解出挑选的物品,只能求最大价值。

使用一维数组压缩空间

观察我们的状态迁移方程:

clipboard.png

weights为每个物品的重量,values为每个物品的价值,W是背包的容量,i表示要放进第几个物品,j是背包现时的容量(假设我们的背包是魔术般的可放大,从0变到W)。

我们假令i = 0

clipboard.png

f中的-1就变成没有意义,因为没有第-1行,而weights[0], values[0]继续有效,${f(0,j)}$也有意义,因为我们全部放到一个一维数组中。于是:

clipboard.png

这方程后面多加了一个限制条件,要求是从大到小循环。为什么呢?

假设有物体${\cal z}$容量2,价值${v_z}$很大,背包容量为5,如果j的循环顺序不是逆序,那么外层循环跑到物体${\cal z}$时, 内循环在${j=2}$时 ,${\cal z}$被放入背包。当${j=4}$时,寻求最大价值,物体z放入背包,${f(4)=max(f(4),f(2)+v_z) }$, 这里毫无疑问后者最大。 但此时${f(2)+v_z}$中的${f(2)}$ 已经装入了一次${\cal z}$,这样一来${\cal z}$被装入两次不符合要求, 如果逆序循环j, 这一问题便解决了。

javascript实现:

//by 司徒正美
function knapsack(weights, values, W){
    var n = weights.length;
    var f = new Array(W+1).fill(0)
    for(var i = 0; i < n; i++) {
        for(var j = W; j >= weights[i]; j--){  
            f[j] = Math.max(f[j], f[j-weights[i]] +values[i]);
        }
        console.log(f.concat()) //调试
    }
    return f[W];
}
var b = knapsack([2,2,6,5,4],[6,3,5,4,6],10)
console.log(b)

image_1c3k7lit11fkd1ufumfuovbidr1j.png-29.6kB

1.4 递归法解01背包

由于这不是动态规则的解法,大家多观察方程就理解了:

//by 司徒正美
function knapsack(n, W, weights, values, selected) {
    if (n == 0 || W == 0) {
        //当物品数量为0,或者背包容量为0时,最优解为0
        return 0;
    } else {
        //从当前所剩物品的最后一个物品开始向前,逐个判断是否要添加到背包中
        for (var i = n - 1; i >= 0; i--) {
            //如果当前要判断的物品重量大于背包当前所剩的容量,那么就不选择这个物品
            //在这种情况的最优解为f(n-1,C)
            if (weights[i] > W) {
                return knapsack(n - 1, W, weights, values, selected);
            } else {
                var a = knapsack(n - 1, W, weights, values, selected); //不选择物品i的情况下的最优解
                var b = values[i] + knapsack(n - 1, W - weights[i], weights, values, selected); //选择物品i的情况下的最优解
                //返回选择物品i和不选择物品i中最优解大的一个
                if (a > b) {
                    selected[i] = 0; //这种情况下表示物品i未被选取
                    return a;
                } else {
                    selected[i] = 1; //物品i被选取
                    return b;
                }
            }
        }
    }
}        
var selected = [], ws = [2,2,6,5,4], vs = [6,3,5,4,6]
var b = knapsack( 5, 10, ws, vs, selected)
console.log(b) //15
selected.forEach(function(el,i){
    if(el){
        console.log("选择了物品"+i+ " 其重量为"+ ws[i]+" 其价值为"+vs[i])
    }
})

image_1c3kfq8nhddj12m11eh1r68189520.png-16.8kB

完全背包问题

2.1 问题描述:

有${n}$件物品和${1}$个容量为W的背包。每种物品没有上限,第${i}$件物品的重量为${weights[i]}$,价值为${values[i]}$,求解将哪些物品装入背包可使价值总和最大。

2.2 问题分析:

最简单思路就是把完全背包拆分成01背包,就是把01背包中状态转移方程进行扩展,也就是说01背包只考虑放与不放进去两种情况,而完全背包要考虑 放0、放1、放2...的情况,

clipboard.png

这个k当然不是无限的,它受背包的容量与单件物品的重量限制,即${j/weights[i]}$。假设我们只有1种商品,它的重量为20,背包的容量为60,那么它就应该放3个,在遍历时,就0、1、2、3地依次尝试。

程序需要求解${n*W}$个状态,每一个状态需要的时间为${O(W/w_i)}$,总的复杂度为${O(nW*Σ(W/w_i))}$。

我们再回顾01背包经典解法的核心代码

for(var i = 0 ; i < n ; i++){ 
   for(var j=0; j<=W; j++){ 
       f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]]+values[i]))
      }
   }
}

现在多了一个k,就意味着多了一重循环

for(var i = 0 ; i < n ; i++){ 
   for(var j=0; j<=W; j++){ 
       for(var k = 0; k < j / weights[i]; k++){
          f[i][j] = Math.max(f[i-1][j], f[i-1][j-k*weights[i]]+k*values[i]))
        }
      }
   }
}

javascript的完整实现:

function completeKnapsack(weights, values, W){
    var f = [], n = weights.length;
    f[-1] = [] //初始化边界
    for(var i = 0; i <= W; i++){
        f[-1][i] = 0
    }
    for (var i = 0;i < n;i++){
        f[i] = new Array(W+1)
        for (var j = 0;j <= W;j++) {
            f[i][j] = 0;
            var bound = j / weights[i];
            for (var k = 0;k <= bound;k++) {
                f[i][j] = Math.max(f[i][j], f[i - 1][j - k * weights[i]] + k * values[i]);
            }
        }
    }
    return f[n-1][W];
}
//物品个数n = 3,背包容量为W = 5,则背包可以装下的最大价值为40.
var a = completeKnapsack([3,2,2],[5,10,20], 5) 
console.log(a) //40

2.3 O(nW)优化

我们再进行优化,改变一下f思路,让${f(i,j)}$表示出在前i种物品中选取若干件物品放入容量为j的背包所得的最大价值。

所以说,对于第i件物品有放或不放两种情况,而放的情况里又分为放1件、2件、......${j/w_i}$件

如果不放, 那么${f(i,j)=f(i-1,j)}$;如果放,那么当前背包中应该出现至少一件第i种物品,所以f(i,j)中至少应该出现一件第i种物品,即${f(i,j)=f(i,j-w_i)+v_i}$,为什么会是${f(i,j-w_i)+v_i}$?

因为我们要把当前物品i放入包内,因为物品i可以无限使用,所以要用${f(i,j-w_i)}$;如果我们用的是${f(i-1,j-w_i)}$,${f(i-1,j-w_i)}$的意思是说,我们只有一件当前物品i,所以我们在放入物品i的时候需要考虑到第i-1个物品的价值${f(i-1,j-w_i)}$;但是现在我们有无限件当前物品i,我们不用再考虑第i-1个物品了,我们所要考虑的是在当前容量下是否再装入一个物品i,而${(j-w_i)}$的意思是指要确保${f(i,j)}$至少有一件第i件物品,所以要预留c(i)的空间来存放一件第i种物品。总而言之,如果放当前物品i的话,它的状态就是它自己"i",而不是上一个"i-1"。

所以说状态转移方程为:

clipboard.png

与01背包的相比,只是一点点不同,我们也不需要三重循环了

clipboard.png

javascript的完整实现:

function unboundedKnapsack(weights, values, W) {
    var f = [],
        n = weights.length;
    f[-1] = []; //初始化边界
    for (let i = 0; i <= W; i++) {
        f[-1][i] = 0;
    }
    for (let i = 0; i < n; i++) {
        f[i] = [];
        for (let j = 0; j <= W; j++) {
            if (j < weights[i]) {
                f[i][j] = f[i - 1][j];
            } else {
                f[i][j] = Math.max(f[i - 1][j], f[i][j - weights[i]] + values[i]);
            }
        }
        console.log(f[i].concat());//调试
    }
    return f[n - 1][W];
}

var a = unboundedKnapsack([3, 2, 2], [5, 10, 20], 5); //输出40
console.log(a);
var b = unboundedKnapsack([2, 3, 4, 7], [1, 3, 5, 9], 10); //输出12
console.log(b);

我们可以继续优化此算法,可以用一维数组写

我们用${f(j)}$表示当前可用体积j的价值,我们可以得到和01背包一样的递推式:

clipboard.png

function unboundedKnapsack(weights, values, W) {
    var n = weights.length,
    f = new Array(W + 1).fill(0);
    for(var i=0; i< n; ++i){
        for(j = weights[i]; j <= W; ++j) {
          var tmp = f[j-weights[i]]+values[i];
          f[j] = (f[j] > tmp) ? f[j] : tmp;
        }
    }
    console.log(f)//调试
    return f[W];
}
var a = unboundedKnapsack([3, 2, 2], [5, 10, 20], 5); //输出40
console.log(a);
var b = unboundedKnapsack([2, 3, 4, 7], [1, 3, 5, 9], 10); //输出12
console.log(b);

多重背包问题

3.1 问题描述:

有${n}$件物品和${1}$个容量为W的背包。每种物品最多有numbers[i]件可用,第${i}$件物品的重量为${weights[i]}$,价值为${values[i]}$,求解将哪些物品装入背包可使价值总和最大。

3.2 问题分析:

多重背包就是一个进化版完全背包。在我们做完全背包的第一个版本中,就是将它转换成01背包,然后限制k的循环

直接套用01背包的一维数组解法

function knapsack(weights, values, numbers,  W){
    var n = weights.length;
    var f= new Array(W+1).fill(0)
    for(var i = 0; i < n; i++) {
        for(var k=0; k<numbers[i]; k++)//其实就是把这类物品展开,调用numbers[i]次01背包代码  
         for(var j=W; j>=weights[i]; j--)//正常的01背包代码  
             f[j]=Math.max(f[j],f[j-weights[i]]+values[i]);  
    }
    return f[W];
}
var b = knapsack([2,3,1 ],[2,3,4],[1,4,1],6)
console.log(b)

3.3 使用二进制优化

其实说白了我们最朴素的多重背包做法是将有数量限制的相同物品看成多个不同的0-1背包。这样的时间复杂度为${O(W*Σn(i))}$, W为空间容量 ,n(i)为每种背包的数量限制。如果这样会超时,我们就得考虑更优的拆分方法,由于拆成1太多了,我们考虑拆成二进制数,对于13的数量,我们拆成1,2,4,6(有个6是为了凑数)。 19 我们拆成1,2,4,8,4 (最后的4也是为了凑和为19)。经过这个样的拆分我们可以组合出任意的小于等于n(i)的数目(二进制啊,必然可以)。j极大程度缩减了等效为0-1背包时候的数量。 大概可以使时间复杂度缩减为${O(W*log(ΣN(i))}$;

定理:一个正整数n可以被分解成1,2,4,…,2^(k-1),n-2^k+1(k是满足n-2^k+1>0的最大整数)的形式,且1~n之内的所有整数均可以唯一表示成1,2,4,…,2^(k-1),n-2^k+1中某几个数的和的形式。

证明如下:

(1) 数列1,2,4,…,2^(k-1),n-2^k+1中所有元素的和为n,所以若干元素的和的范围为:[1, n];

(2)如果正整数t<= 2^k – 1,则t一定能用1,2,4,…,2^(k-1)中某几个数的和表示,这个很容易证明:我们把t的二进制表示写出来,很明显,t可以表示成n=a0*2^0+a1*2^1+…+ak*2^(k-1),其中ak=0或者1,表示t的第ak位二进制数为0或者1.

(3)如果t>=2^k,设s=n-2^k+1,则t-s<=2^k-1,因而t-s可以表示成1,2,4,…,2^(k-1)中某几个数的和的形式,进而t可以表示成1,2,4,…,2^(k-1),s中某几个数的和(加数中一定含有s)的形式。

(证毕!)

function mKnapsack(weights, values, numbers, W) {
    var kind = 0; //新的物品种类
    var ws = []; //新的物品重量
    var vs = []; //新的物品价值
    var n = weights.length;
    /**
     * 二进制分解
     * 100=1+2+4+8+16+32+37,观察可以得出100以内任何一个数都可以由以上7个数选择组合得到,
     * 所以对物品数目就不是从0都100遍历,而是0,1,2,4,8,16,32,37遍历,时间大大优化。
     */
    for (let i = 0; i < n; i++) {
        var w = weights[i];
        var v = values[i];
        var num = numbers[i];
        for (let j = 1; ; j *= 2) {
            if (num >= j) {
                ws[kind] = j * w;
                vs[kind] = j * v;
                num -= j;
                kind++;
            } else {
                ws[kind] = num * w;
                vs[kind] = num * v;
                kind++;
                break;
            }
        }
    }
    //01背包解法
    var f = new Array(W + 1).fill(0);
    for (let i = 0; i < kind; i++) {
        for (let j = W; j >= ws[i]; j--) {
            f[j] = Math.max(f[j], f[j - ws[i]] + vs[i]);
        }
    }
    return f[W];
}

var b = mKnapsack([2,3,1 ],[2,3,4],[1,4,1],6)
console.log(b) //9

参考链接

查看原文

Y_qwq 赞了文章 · 2019-09-22

javascript背包问题详解

image_1c3ds1q091ubg5bm1gaj3vv1jm19.png-64.6kB

引子

打算好好学一下算法,先拿背包问题入手。但是网上许多教程都是C++或java或python,大部分作者都是在校生,虽然算法很强,但是完全没有工程意识,全局变量满天飞,变量名不明所以。我查了许多资料,花了一个星期才搞懂,最开始的01背包耗时最多,以前只会枚举(就是普通的for循环,暴力地一步步遍历下去),递归与二分,而动态规划所讲的状态表与状态迁移方程为我打开一扇大门。

01背包问题

篇幅可能有点长,但请耐心看一下,你会觉得物有所值的。本文以后还会扩展,因为我还没有想到完全背包与多重背包打印物品编号的方法。如果有高人知道,劳烦在评论区指教一下。

注意,由于社区不支持LaTex数学公式,你们看到${xxxx}$,就自己将它们过滤吧。

1.1 问题描述:

有${n}$件物品和${1}$个容量为W的背包。每种物品均只有一件,第${i}$件物品的重量为${weights[i]}$,价值为${values[i]}$,求解将哪些物品装入背包可使价值总和最大。

对于一种物品,要么装入背包,要么不装。所以对于一种物品的装入状态只是1或0, 此问题称为01背包问题

1.2 问题分析:

数据:物品个数${n=5}$,物品重量${weights=[2,2,6,5,4]}$,物品价值${values=[6,3,5,4,6]}$,背包总容量${W=10}$。

我们设置一个矩阵${f}$来记录结果,${f(i, j)}$ 表示可选物品为 ${i...n}$ 背包容量为 ${j(0<=j<=W)}$ 时, 背包中所放物品的最大价值。

wvi\j012345678910
260
231
652
543
464

我们先看第一行,物品0的体积为2,价值为6,当容量为0时,什么也放不下,因此第一个格式只能填0,程序表示为${f(0,0) = 0}$或者${f[0][0] = 0}$。 当${j=1}$时,依然放不下${w_0}$,因此依然为0,${f(0, 1) = 0}$。 当${j=2}$时,能放下${w_0}$,于是有 ${f(0, 2)\ = \ v_0=6}$。 当${j=3}$时,也能放下${w_0}$,但我们只有一个物品0,因此它的值依然是6,于是一直到${j=10}$时,它的值都是${v_0}$。

wvi\j012345678910
26000666666666
231
652
543
464

根据第一行,我们得到如下方程

clipboard.png

当背包容量少于物品価积时,总价值为0,否则为物品的价值

然后我们看第二行,确定确定${f(1,0...10)}$这11个元素的值。当${j=0}$ 时,依然什么也放不下,值为0,但我们发觉它是上方格式的值一样的,${f(1,0)=0}$。 当${j=1}$时,依然什么也放不下,值为0,但我们发觉它是上方格式的值一样的,${f(1,1)=0}$. 当${j=2}$时,它可以选择放入物品1或不放。

如果选择不放物品1,背包里面有物品0,最大价值为6。

如果选择放入物品1,我们要用算出背包放入物品1后还有多少容量,然后根据容量查出它的价值,再加上物品1的价值,即${f(0,j-w_1)+v_1}$ 。由于我们的目标是尽可能装最值钱的物品, 因此放与不放, 我们需要通过比较来决定,于是有

clipboard.png

显然${v_1=2,v_0=6}$, 因此这里填${v_0}$。 当${j=3}$时, 情况相同。 当${j=4}$,能同时放下物品0与物品1,我们这个公式的计算结果也合乎我们的预期, 得到${f(1,4)=9}$。 当${j>4}$时, 由于背包只能放物品0与物品1,那么它的最大价值也一直停留在${v_0+v_1=9}$

wvi\j012345678910
26000666666666
23100669999999
652
543
464

我们再看第三行,当${j=0}$时,什么都放不下,${f(2,0)=0}$。当${j=1}$时,依然什么也放不下,${f(2,1)=0}$,当${j=2}$时,虽然放不下${w_2}$,但我们根据上表得知这个容号时,背包能装下的最大价值是6。继续计算下去,其实与上面推导的公式结果是一致的,说明公式是有效的。当${j=8}$时,背包可以是放物品0、1,或者放物品1、2,或者放物品0、2。物品0、1的价值,我们在表中就可以看到是9,至于其他两种情况我们姑且不顾,我们目测就知道是最优值是${6+5=11}$, 恰恰我们的公式也能正确计算出来。当${j=10}$时,刚好三个物品都能装下,它们的总值为14,即${f(2,10)=14}$

第三行的结果如下:

wvi\j012345678910
26000666666666
23100669999999
65200669999111114
543
464

整理一下第1,2行的适用方程:

clipboard.png

我们根据此方程,继续计算下面各列,于是得到

wvi\j012345678910
26000666666666
23100669999999
65200669999111114
543006699910111314
4640066991212151515

至此,我们就可以得到解为15.

我们最后根据0-1背包问题的最优子结构性质,建立计算${f(i,j)}$的递归式:

clipboard.png

//by 司徒正美
 function knapsack(weights, values, W){
    var n = weights.length -1
    var f = [[]]
    for(var j = 0; j <= W; j++){
        if(j < weights[0]){ //如果容量不能放下物品0的重量,那么价值为0
           f[0][j] = 0
        }else{ //否则等于物体0的价值
           f[0][j] = values[0]
        }
    }
    for(var j = 0; j <= W; j++){
        for(var i = 1; i <= n; i++ ){
            if(!f[i]){ //创建新一行
                f[i] = []
            }
            if(j < weights[i]){ //等于之前的最优值
                f[i][j] = f[i-1][j]
            }else{
                f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]] + values[i]) 
            }
        }
    }
    return f[n][W]
}
var a = knapsack([2,2,6,5,4],[6,3,5,4,6],10)
console.log(a)

1.3 各种优化:

合并循环

现在方法里面有两个大循环,它们可以合并成一个。

function knapsack(weights, values, W){
    var n = weights.length;
    var f = new Array(n)
    for(var i = 0 ; i < n; i++){
        f[i] = []
    }
   for(var i = 0; i < n; i++ ){
       for(var j = 0; j <= W; j++){
            if(i === 0){ //第一行
                f[i][j] = j < weights[i] ? 0 : values[i]
            }else{
                if(j < weights[i]){ //等于之前的最优值
                    f[i][j] = f[i-1][j]
                }else{
                    f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]] + values[i]) 
                }
            }
        }
    }
    return f[n-1][W]
}

然后我们再认真地思考一下,为什么要孤零零地专门处理第一行呢?f[i][j] = j < weights[i] ? 0 : values[i]是不是能适用于下面这一行f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]] + values[i]) 。Math.max可以轻松转换为三元表达式,结构极其相似。而看一下i-1的边界问题,有的书与博客为了解决它,会添加第0行,全部都是0,然后i再往下挪。其实我们也可以添加一个${-1}$行。那么在我们的方程中就不用区分${i==0}$与${0>0}$的情况,方程与其他教科书的一模一样了!

clipboard.png

function knapsack(weights, values, W){
    var n = weights.length;
    var f = new Array(n)
    f[-1] = new Array(W+1).fill(0)
    for(var i = 0 ; i < n ; i++){ //注意边界,没有等号
        f[i] = new Array(W).fill(0)
        for(var j=0; j<=W; j++){//注意边界,有等号
            if( j < weights[i] ){ //注意边界, 没有等号
                f[i][j] = f[i-1][j]
            }else{
                f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]]+values[i]);//case 3
            }
        }
    }
    return f[n-1][W]
}
wvi\j012345678910
XX-1000000000000
26000666666666
23100669999999
65200669999111114
543006699910111314
4640066991212151515

负一行的出现可以大大减少了在双层循环的分支判定。是一个很好的技巧。

注意,许多旧的教程与网上文章,通过设置二维数组的第一行为0来解决i-1的边界问题(比如下图)。当然也有一些思维转不过来的缘故,他们还在坚持数字以1开始,而我们新世代的IT人已经确立从0开始的编程思想。

image_1c3lm81p3gd09n5pjk1i4aif92d.png-110.2kB

选择物品

上面讲解了如何求得最大价值,现在我们看到底选择了哪些物品,这个在现实中更有意义。许多书与博客很少提到这一点,就算给出的代码也不对,估计是在设计状态矩阵就出错了。

仔细观察矩阵,从${f(n-1,W)}$逆着走向${f(0,0)}$,设i=n-1,j=W,如果${f(i,j)}$==${f(i-1,j-w_i)+v_i}$说明包里面有第i件物品,因此我们只要当前行不等于上一行的总价值,就能挑出第i件物品,然后j减去该物品的重量,一直找到j = 0就行了。

//by 司徒正美
function knapsack(weights, values, W){
    var n = weights.length;
    var f = new Array(n)
    f[-1] = new Array(W+1).fill(0)
    var selected = [];
    for(var i = 0 ; i < n ; i++){ //注意边界,没有等号
        f[i] = [] //创建当前的二维数组
        for(var j=0; j<=W; j++){ //注意边界,有等号
            if( j < weights[i] ){ //注意边界, 没有等号
                f[i][j] = f[i-1][j]//case 1
            }else{
                f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]]+values[i]);//case 2
            }
        }
    }
    var j = W, w = 0
    for(var i=n-1; i>=0; i--){
         if(f[i][j] > f[i-1][j]){
             selected.push(i)
             console.log("物品",i,"其重量为", weights[i],"其价格为", values[i])
             j = j - weights[i];
             w +=  weights[i]
         }
     }
    console.log("背包最大承重为",W," 现在重量为", w, " 总价值为", f[n-1][W])
    return [f[n-1][W], selected.reverse() ]
}
var a = knapsack([2,3,4,1],[2,5,3, 2],5)
console.log(a)
var b = knapsack([2,2,6,5,4],[6,3,5,4,6],10)
console.log(b)

image_1c3k62d511dtgo7gud815q866m16.png-22.8kB
image_1c3k617gc6jp10pn1ean1lv81boqp.png-28.5kB

使用滚动数组压缩空间

所谓滚动数组,目的在于优化空间,因为目前我们是使用一个${i*j}$的二维数组来储存每一步的最优解。在求解的过程中,我们可以发现,当前状态只与前一行的状态有关,那么更之前存储的状态信息已经无用了,可以舍弃的,我们只需要存储当前状态和前一行状态,所以只需使用${2*j}$的空间,循环滚动使用,就可以达到跟${i*j}$一样的效果。这是一个非常大的空间优化。

//by 司徒正美
function knapsack(weights, values, W){
    var n = weights.length
    var lineA = new Array(W+1).fill(0)
    var lineB = [], lastLine = 0, currLine 
    var f = [lineA, lineB]; //case1 在这里使用es6语法预填第一行
    for(var i = 0; i < n; i++){ 
        currLine = lastLine === 0 ? 1 : 0 //决定当前要覆写滚动数组的哪一行
        for(var j=0; j<=W; j++){
            f[currLine][j] = f[lastLine][j] //case2 等于另一行的同一列的值
            if( j>= weights[i] ){                         
                var a = f[lastLine][j]
                var b = f[lastLine][j-weights[i]] + values[i]
                f[currLine][j] = Math.max(a, b);//case3
            }
           
        }
        lastLine = currLine//交换行
   }
   return f[currLine][W];
}

var a = knapsack([2,3,4,1],[2,5,3, 2],5)
console.log(a)
var b = knapsack([2,2,6,5,4],[6,3,5,4,6],10)
console.log(b)

我们还可以用更hack的方法代替currLine, lastLine

//by 司徒正美
function knapsack(weights, values, W){
    var n = weights.length
   
    var f = [new Array(W+1).fill(0),[]], now = 1, last //case1 在这里使用es6语法预填第一行
    for(var i = 0; i < n; i++){ 
        for(var j=0; j<=W; j++){
            f[now][j] = f[1-now][j] //case2 等于另一行的同一列的值
            if( j>= weights[i] ){                         
                var a = f[1-now][j]
                var b = f[1-now][j-weights[i]] + values[i]
                f[now][j] = Math.max(a, b);//case3
            }
         }
         last = f[now]
         now = 1-now // 1 - 0 => 1;1 - 1 => 0; 1 - 0 => 1 ....
   }
   return last[W];
}
var a = knapsack([2,3,4,1],[2,5,3, 2],5)
console.log(a)
var b = knapsack([2,2,6,5,4],[6,3,5,4,6],10)
console.log(b)

注意,这种解法由于丢弃了之前N行的数据,因此很难解出挑选的物品,只能求最大价值。

使用一维数组压缩空间

观察我们的状态迁移方程:

clipboard.png

weights为每个物品的重量,values为每个物品的价值,W是背包的容量,i表示要放进第几个物品,j是背包现时的容量(假设我们的背包是魔术般的可放大,从0变到W)。

我们假令i = 0

clipboard.png

f中的-1就变成没有意义,因为没有第-1行,而weights[0], values[0]继续有效,${f(0,j)}$也有意义,因为我们全部放到一个一维数组中。于是:

clipboard.png

这方程后面多加了一个限制条件,要求是从大到小循环。为什么呢?

假设有物体${\cal z}$容量2,价值${v_z}$很大,背包容量为5,如果j的循环顺序不是逆序,那么外层循环跑到物体${\cal z}$时, 内循环在${j=2}$时 ,${\cal z}$被放入背包。当${j=4}$时,寻求最大价值,物体z放入背包,${f(4)=max(f(4),f(2)+v_z) }$, 这里毫无疑问后者最大。 但此时${f(2)+v_z}$中的${f(2)}$ 已经装入了一次${\cal z}$,这样一来${\cal z}$被装入两次不符合要求, 如果逆序循环j, 这一问题便解决了。

javascript实现:

//by 司徒正美
function knapsack(weights, values, W){
    var n = weights.length;
    var f = new Array(W+1).fill(0)
    for(var i = 0; i < n; i++) {
        for(var j = W; j >= weights[i]; j--){  
            f[j] = Math.max(f[j], f[j-weights[i]] +values[i]);
        }
        console.log(f.concat()) //调试
    }
    return f[W];
}
var b = knapsack([2,2,6,5,4],[6,3,5,4,6],10)
console.log(b)

image_1c3k7lit11fkd1ufumfuovbidr1j.png-29.6kB

1.4 递归法解01背包

由于这不是动态规则的解法,大家多观察方程就理解了:

//by 司徒正美
function knapsack(n, W, weights, values, selected) {
    if (n == 0 || W == 0) {
        //当物品数量为0,或者背包容量为0时,最优解为0
        return 0;
    } else {
        //从当前所剩物品的最后一个物品开始向前,逐个判断是否要添加到背包中
        for (var i = n - 1; i >= 0; i--) {
            //如果当前要判断的物品重量大于背包当前所剩的容量,那么就不选择这个物品
            //在这种情况的最优解为f(n-1,C)
            if (weights[i] > W) {
                return knapsack(n - 1, W, weights, values, selected);
            } else {
                var a = knapsack(n - 1, W, weights, values, selected); //不选择物品i的情况下的最优解
                var b = values[i] + knapsack(n - 1, W - weights[i], weights, values, selected); //选择物品i的情况下的最优解
                //返回选择物品i和不选择物品i中最优解大的一个
                if (a > b) {
                    selected[i] = 0; //这种情况下表示物品i未被选取
                    return a;
                } else {
                    selected[i] = 1; //物品i被选取
                    return b;
                }
            }
        }
    }
}        
var selected = [], ws = [2,2,6,5,4], vs = [6,3,5,4,6]
var b = knapsack( 5, 10, ws, vs, selected)
console.log(b) //15
selected.forEach(function(el,i){
    if(el){
        console.log("选择了物品"+i+ " 其重量为"+ ws[i]+" 其价值为"+vs[i])
    }
})

image_1c3kfq8nhddj12m11eh1r68189520.png-16.8kB

完全背包问题

2.1 问题描述:

有${n}$件物品和${1}$个容量为W的背包。每种物品没有上限,第${i}$件物品的重量为${weights[i]}$,价值为${values[i]}$,求解将哪些物品装入背包可使价值总和最大。

2.2 问题分析:

最简单思路就是把完全背包拆分成01背包,就是把01背包中状态转移方程进行扩展,也就是说01背包只考虑放与不放进去两种情况,而完全背包要考虑 放0、放1、放2...的情况,

clipboard.png

这个k当然不是无限的,它受背包的容量与单件物品的重量限制,即${j/weights[i]}$。假设我们只有1种商品,它的重量为20,背包的容量为60,那么它就应该放3个,在遍历时,就0、1、2、3地依次尝试。

程序需要求解${n*W}$个状态,每一个状态需要的时间为${O(W/w_i)}$,总的复杂度为${O(nW*Σ(W/w_i))}$。

我们再回顾01背包经典解法的核心代码

for(var i = 0 ; i < n ; i++){ 
   for(var j=0; j<=W; j++){ 
       f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]]+values[i]))
      }
   }
}

现在多了一个k,就意味着多了一重循环

for(var i = 0 ; i < n ; i++){ 
   for(var j=0; j<=W; j++){ 
       for(var k = 0; k < j / weights[i]; k++){
          f[i][j] = Math.max(f[i-1][j], f[i-1][j-k*weights[i]]+k*values[i]))
        }
      }
   }
}

javascript的完整实现:

function completeKnapsack(weights, values, W){
    var f = [], n = weights.length;
    f[-1] = [] //初始化边界
    for(var i = 0; i <= W; i++){
        f[-1][i] = 0
    }
    for (var i = 0;i < n;i++){
        f[i] = new Array(W+1)
        for (var j = 0;j <= W;j++) {
            f[i][j] = 0;
            var bound = j / weights[i];
            for (var k = 0;k <= bound;k++) {
                f[i][j] = Math.max(f[i][j], f[i - 1][j - k * weights[i]] + k * values[i]);
            }
        }
    }
    return f[n-1][W];
}
//物品个数n = 3,背包容量为W = 5,则背包可以装下的最大价值为40.
var a = completeKnapsack([3,2,2],[5,10,20], 5) 
console.log(a) //40

2.3 O(nW)优化

我们再进行优化,改变一下f思路,让${f(i,j)}$表示出在前i种物品中选取若干件物品放入容量为j的背包所得的最大价值。

所以说,对于第i件物品有放或不放两种情况,而放的情况里又分为放1件、2件、......${j/w_i}$件

如果不放, 那么${f(i,j)=f(i-1,j)}$;如果放,那么当前背包中应该出现至少一件第i种物品,所以f(i,j)中至少应该出现一件第i种物品,即${f(i,j)=f(i,j-w_i)+v_i}$,为什么会是${f(i,j-w_i)+v_i}$?

因为我们要把当前物品i放入包内,因为物品i可以无限使用,所以要用${f(i,j-w_i)}$;如果我们用的是${f(i-1,j-w_i)}$,${f(i-1,j-w_i)}$的意思是说,我们只有一件当前物品i,所以我们在放入物品i的时候需要考虑到第i-1个物品的价值${f(i-1,j-w_i)}$;但是现在我们有无限件当前物品i,我们不用再考虑第i-1个物品了,我们所要考虑的是在当前容量下是否再装入一个物品i,而${(j-w_i)}$的意思是指要确保${f(i,j)}$至少有一件第i件物品,所以要预留c(i)的空间来存放一件第i种物品。总而言之,如果放当前物品i的话,它的状态就是它自己"i",而不是上一个"i-1"。

所以说状态转移方程为:

clipboard.png

与01背包的相比,只是一点点不同,我们也不需要三重循环了

clipboard.png

javascript的完整实现:

function unboundedKnapsack(weights, values, W) {
    var f = [],
        n = weights.length;
    f[-1] = []; //初始化边界
    for (let i = 0; i <= W; i++) {
        f[-1][i] = 0;
    }
    for (let i = 0; i < n; i++) {
        f[i] = [];
        for (let j = 0; j <= W; j++) {
            if (j < weights[i]) {
                f[i][j] = f[i - 1][j];
            } else {
                f[i][j] = Math.max(f[i - 1][j], f[i][j - weights[i]] + values[i]);
            }
        }
        console.log(f[i].concat());//调试
    }
    return f[n - 1][W];
}

var a = unboundedKnapsack([3, 2, 2], [5, 10, 20], 5); //输出40
console.log(a);
var b = unboundedKnapsack([2, 3, 4, 7], [1, 3, 5, 9], 10); //输出12
console.log(b);

我们可以继续优化此算法,可以用一维数组写

我们用${f(j)}$表示当前可用体积j的价值,我们可以得到和01背包一样的递推式:

clipboard.png

function unboundedKnapsack(weights, values, W) {
    var n = weights.length,
    f = new Array(W + 1).fill(0);
    for(var i=0; i< n; ++i){
        for(j = weights[i]; j <= W; ++j) {
          var tmp = f[j-weights[i]]+values[i];
          f[j] = (f[j] > tmp) ? f[j] : tmp;
        }
    }
    console.log(f)//调试
    return f[W];
}
var a = unboundedKnapsack([3, 2, 2], [5, 10, 20], 5); //输出40
console.log(a);
var b = unboundedKnapsack([2, 3, 4, 7], [1, 3, 5, 9], 10); //输出12
console.log(b);

多重背包问题

3.1 问题描述:

有${n}$件物品和${1}$个容量为W的背包。每种物品最多有numbers[i]件可用,第${i}$件物品的重量为${weights[i]}$,价值为${values[i]}$,求解将哪些物品装入背包可使价值总和最大。

3.2 问题分析:

多重背包就是一个进化版完全背包。在我们做完全背包的第一个版本中,就是将它转换成01背包,然后限制k的循环

直接套用01背包的一维数组解法

function knapsack(weights, values, numbers,  W){
    var n = weights.length;
    var f= new Array(W+1).fill(0)
    for(var i = 0; i < n; i++) {
        for(var k=0; k<numbers[i]; k++)//其实就是把这类物品展开,调用numbers[i]次01背包代码  
         for(var j=W; j>=weights[i]; j--)//正常的01背包代码  
             f[j]=Math.max(f[j],f[j-weights[i]]+values[i]);  
    }
    return f[W];
}
var b = knapsack([2,3,1 ],[2,3,4],[1,4,1],6)
console.log(b)

3.3 使用二进制优化

其实说白了我们最朴素的多重背包做法是将有数量限制的相同物品看成多个不同的0-1背包。这样的时间复杂度为${O(W*Σn(i))}$, W为空间容量 ,n(i)为每种背包的数量限制。如果这样会超时,我们就得考虑更优的拆分方法,由于拆成1太多了,我们考虑拆成二进制数,对于13的数量,我们拆成1,2,4,6(有个6是为了凑数)。 19 我们拆成1,2,4,8,4 (最后的4也是为了凑和为19)。经过这个样的拆分我们可以组合出任意的小于等于n(i)的数目(二进制啊,必然可以)。j极大程度缩减了等效为0-1背包时候的数量。 大概可以使时间复杂度缩减为${O(W*log(ΣN(i))}$;

定理:一个正整数n可以被分解成1,2,4,…,2^(k-1),n-2^k+1(k是满足n-2^k+1>0的最大整数)的形式,且1~n之内的所有整数均可以唯一表示成1,2,4,…,2^(k-1),n-2^k+1中某几个数的和的形式。

证明如下:

(1) 数列1,2,4,…,2^(k-1),n-2^k+1中所有元素的和为n,所以若干元素的和的范围为:[1, n];

(2)如果正整数t<= 2^k – 1,则t一定能用1,2,4,…,2^(k-1)中某几个数的和表示,这个很容易证明:我们把t的二进制表示写出来,很明显,t可以表示成n=a0*2^0+a1*2^1+…+ak*2^(k-1),其中ak=0或者1,表示t的第ak位二进制数为0或者1.

(3)如果t>=2^k,设s=n-2^k+1,则t-s<=2^k-1,因而t-s可以表示成1,2,4,…,2^(k-1)中某几个数的和的形式,进而t可以表示成1,2,4,…,2^(k-1),s中某几个数的和(加数中一定含有s)的形式。

(证毕!)

function mKnapsack(weights, values, numbers, W) {
    var kind = 0; //新的物品种类
    var ws = []; //新的物品重量
    var vs = []; //新的物品价值
    var n = weights.length;
    /**
     * 二进制分解
     * 100=1+2+4+8+16+32+37,观察可以得出100以内任何一个数都可以由以上7个数选择组合得到,
     * 所以对物品数目就不是从0都100遍历,而是0,1,2,4,8,16,32,37遍历,时间大大优化。
     */
    for (let i = 0; i < n; i++) {
        var w = weights[i];
        var v = values[i];
        var num = numbers[i];
        for (let j = 1; ; j *= 2) {
            if (num >= j) {
                ws[kind] = j * w;
                vs[kind] = j * v;
                num -= j;
                kind++;
            } else {
                ws[kind] = num * w;
                vs[kind] = num * v;
                kind++;
                break;
            }
        }
    }
    //01背包解法
    var f = new Array(W + 1).fill(0);
    for (let i = 0; i < kind; i++) {
        for (let j = W; j >= ws[i]; j--) {
            f[j] = Math.max(f[j], f[j - ws[i]] + vs[i]);
        }
    }
    return f[W];
}

var b = mKnapsack([2,3,1 ],[2,3,4],[1,4,1],6)
console.log(b) //9

参考链接

查看原文

赞 83 收藏 135 评论 8

Y_qwq 发布了文章 · 2019-09-21

字节跳动前端校招一二面凉经

字节跳动一面、二面凉经

笔试

题忘了,四道算法题120分钟。难度一般。

一面

  1. 自我介绍
  2. 项目介绍
  3. new 的过程
  4. 给几个setTimeOut,问你输出
  5. es5的继承 实现一下
  6. es6新特性
  7. let、const和var区别
  8. const obj 的属性如何不可变
  9. 说一下浏览器事件,各种父类子类设置冒泡或者捕获,哪个先哪个后
  10. 说一下箭头函数
  11. 你说箭头函数没有自己的this,那(()=>{}).bind(this)可?
  12. new Queue().task(1000,console.log(1)).task(2000,console.log(2)).task(3000,console.log(3)).start()实现该函数,start()后等1秒输出1,再等2秒2,再等3秒3.
  13. 居中方式
  14. position有那些,各自效果
  15. TCP、UDP区别
  16. https、http区别
  17. React/Vue哪个熟悉
  18. React16新特性
  19. 说一下diff
  20. 说一下类数组,数据结构是怎么样的,怎么转换为数组
  21. ab-cd-ef=》ab-Cd-Ef(来个简单的题(你菜给你来个简单的嘤嘤嘤))

二面

  1. document.ready和window.onload的区别
  2. onload怎么用
  3. https和http的区别
  4. 渐进jpg了解过吗
  5. 关于this和prototype上添加属性,问你输出。具体忘了
  6. [1,2,3,4,6,7,9,13,15]=>['1->4',6->7,'9','13','15']实现一下
  7. 实现一个类,可以on,emit,off,once,注册、调用、取消、注册仅能使用一次的事件
  8. 文件上传如何实现?,除了input还有什么别的方法?
  9. 浏览器如何预览图片,假设我要上传图片,未上传前我想在浏览器看到我待上传的图片
  10. base64 前端如何转化
  11. 假设有130个苹果,你我轮流拿,每次可拿1-5个,如何保证你拿到最后一个苹果
不全,仅记录个人有印象....

总结

算法算法算法emmmm,算法真的很重要(对大厂面试)
大厂对算法真的有要求的,无论什么岗位。至于前端基础这就不用说了。
字节的一面很简单,没什么难度,都是常规题+简单算法吧,一些地方卡住了面试官还会各种提示。
二面按道理其实也不太难。刚好面试官问的方向我都了解不多(我说了这方面不太了解仅以前看过相关文章还继续追问emmmm),加上最后算法题GG了。直接被挂掉了。
字节对学历卡的没那么严,本人渣二本都给面甚至二面了。
最后,菜是原罪啊!

查看原文

赞 0 收藏 0 评论 0

Y_qwq 收藏了文章 · 2019-09-15

Javascript中字符串方法总结

原文链接:https://mrzhang123.github.io/...

字符方法

chartAt()与charCodeAt()

参数:基于0的字符位置

chartAt()以单字符字符串的形式返回给定位置的那个字符。而charCodeAt()返回的是字符编码。

var stringValue = 'hello world';
/*chartAt()*/
console.log(stringValue.chartAt(1));    // 'e'

字符串操作方法

concat()(数组中也有该方法)

参数:一个或多个字符串

将一个会多个字符串拼接起来,当然更常用的是使用 “+” 进行拼接

substring()与slice()(数组中也有此方法)

参数:指定子字符串的开始位置子字符串到哪里结束

作用:创建新的子字符串(可以理解为字符串截取)

substr()

参数:指定子字符串的开始位置返回的子字符串的字符个数

作用:创建新的子字符串(可以理解为字符串截取)

repeat()(ES6新增)

参数:数字(表示重复的次数)

作用:将原字符串重复n次

如果传入负数,则报错,传入小数和NaN等同于传入0

substring,slice,substr,repeat均返回子字符串,不会修改原来的字符串

var stringValue = "hello world"; 
alert(stringValue.slice(3));          //"lo world" 
alert(stringValue.substring(3));      //"lo world" 
alert(stringValue.substr(3));         //"lo world" 
alert(stringValue.slice(3, 7));       //"lo w" 
alert(stringValue.substring(3,7));    //"lo w" 
alert(stringValue.substr(3, 7));      //"lo worl" 
/*repeat()*/
var a = 'he';
var b = a.repeat(3);
console.log(`${a}---${b}`); /          //"he---hehehe"

当给这三个方法传入负值的时候,三个的表现不同:

  • slice()会将传入的负值与字符串的长度相加

  • substr()会将第一个位置的负值参数加上字符串长度后转为正数,而第二个位置的负值将转化为0

  • substring()会把所有的负参数转化为0

  • repeat()会报错

字符串位置方法

indexOf()和lastIndexOf()(数组中也有该方法)

参数:要搜索的子字符串开始搜索的位置(可选)

搜索给定的子字符串,如果找到则返回位置,否则返回-1

var stringValue = "hello world"; 
alert(stringValue.indexOf("o"));             //4 
alert(stringValue.lastIndexOf("o"));         //7 

这两个方法在搜索到第一个匹配的子字符串后就停止运行,所以如果想找到字符串中所有的
子字符串出现的位置,可以循环调用indexOflastIndexOf

var stringValue = "Lorem ipsum dolor sit amet, consectetur adipisicing elit"; 
var positions = new Array(); 
var pos = stringValue.indexOf("e"); 
 
while(pos > -1){ 
    positions.push(pos); 
    pos = stringValue.indexOf("e", pos + 1); 
} 
     
alert(positions);    //"3,24,32,35,52"

ES6新增includes()、startsWith()、endsWith()

  • includes():返回布尔值,表示是否找到了参数字符串

  • startsWith():返回布尔值,表示参数字符串是否在源字符串的头部

  • endsWith():返回布尔值,表示参数字符串是否在源字符串的尾部

这三个方法的参数与indexOf()lastIndexOf()一样

var s = 'Hello world';
s.startsWith('world',6);    // true
s.endsWith('Hello',5);        // true
s.includes('Hello',6);        //false

注意:
使用第2个参数n时,endsWith的行为与其他两个方法有所不同。它针对前面n个字符,而其他两个方法针对从第n个位置开始直到字符串结束的字符。

去空格--trim()

ES5中新增trim()方法用于去除字符串的左右空格,该方法会创建一个字符串的副本,不会改变原有的字符串,此外,Firefox 3.5+、Safari 5+
和 Chrome 8+还支持非标准的 trimLeft()和 trimRight()方法,分别用于删除字符串开头和末尾的
空格。

其实去空格可以使用正则去匹配的去掉,这里写一个去空格函数

/*trim    去掉空白
str要处理的字符串        
[type]     类型:l 去除左边的空白    r去除右边空白    b去掉两边的空白        a去除所有空白*/
function trim (str,type) {
    var type=type||"b";
    if(type=="b"){
        return str.replace(/^\s*|\s*$/g,"");
    }else if(type=="l"){
        return str.replace(/^\s*/g,"");
    }else if(type=="r"){
        return str.replace(/\s*$/g,"");
    }else if(type=="a"){
        return str.replace(/\s*/g,"");
    }
}

字符串大小写转换

toLowerCase()、toLocaleLowerCase()、toUpperCase()和 toLocaleUpperCase()

字符串的模式匹配方法

match()

参数:一个正则表达式或RegExp对象

返回一个数组。在字符串上调用这个方法本质上与调用RegExp的exec()方法相同。

var text = "cat, bat, sat, fat";  
var pattern = /.at/; 
 
//与 pattern.exec(text)相同 
var matches = text.match(pattern);         
alert(matches.index);             //0 
alert(matches[0]);                 //"cat" 
alert(pattern.lastIndex);          //0 

search()

参数:一个正则表达式或RegExp对象

返回字符串中第一个匹配项的索引,如果没有找到,则返回-1

var text = "cat, bat, sat, fat";  
var pos = text.search(/at/); 
alert(pos);   //1 

replace()

参数:一个RegExp对象或者一个字符串(这个字符串不会被转换成正则表达式)一个字符串或一个函数

利用replace()进行替换的时候,如果传入的是字符串,则只会替换第一个子字符串,要想替换所有的子字符串,则需要传入一个正则表达式,而且要指定全局(g)标志

var text = 'cat , bat , sat , fat';
var result = text.replace('at','ond');
console.log(result); // =>'cont , bat , sat , fat'

result = text.replace(/at/g,'ond');
console.log(result); //=>'cont , bont , sont , font'

该方法并不改变调用它的字符串本身,只是返回一个新的替换后的字符串。

当第二个参数为函数时函数的返回值作为替换字符串。与第二个参数是字符串一样,如果第一个参数是正则表达式,并且全局匹配,则这个函数的方法将被多次调用,每次匹配都会被调用。

该函数的参数:

  • match:匹配的子串

  • p1,p2...:假如replace()方法的第一个参数是RegExp对象,则代表第n个括号匹配的字符串。

  • offset:匹配到的子字符串在原字符串中的偏移量。(比如,如果原字符串是“abcd”,匹配到的子字符串时“bc”,那么这个参数是1)

  • 被匹配的原字符串

function replacer(match , p1 , p2 , p3 , offset , string){
    // p1 is nondigits, p2 digits, and p3 non-alphanumerics
    console.log(`${match}
                 ${p1}
                 ${p2}
                 ${p3}
                 ${offset}
                 ${string}`); 
    /* => abc12345#$*%
         abc
         12345
         #$*%
         0
         abc12345#$*%"    */         
    console.log([p1, p2, p3].join(' - ')); // => "abc - 12345 - #$*%"
    return [p1, p2, p3].join(' - ');
}
var newString = 'abc12345#$*%'.replace(/([^\d]*)(\d*)([^\w]*)/, replacer); // =>"abc - 12345 - #$*%"

split()

参数:用于分隔字符串的分隔符数字(可选,用于指定数组的大小)

作用:基于指定的分隔符将一个字符串分割成多个子字符串,并将结果放在一个数组中,分隔符可以是字符串,也可以是RegExp对象

var color = 'red,blue,yellow,black';
var color1 = color.split(',');        // =>['red','blue','yellow','black']
var color2 = color.split(',',2);    // =>['red','blue']
var color3 = color.split(/[^\,]+/); // =>["", ",", ",", ",", ""] 

最后一个调用split的时候,出现了前后的两个空白,是因为通过正则表达式指定的分隔符出现在了字符串的开头和结尾。

localeCompare()

这个方法用于比较两个字符串,并返回下列值中的一个:

  • 如果字符串在字母表中应该排在字符串参数之前,则返回负数(大多情况下为-1)

  • 如果相等,则返回0

  • 如果排在字符串参数之前,则返回正数(大多数情况下为1)

fromCharCode()

String构造函数的一个静态方法

参数:一个或多个字符串编码

作用:将接收到的一个或多个字符串编码转换成一个字符串,这个方法与实例方法charCodeAt()执行相反的操作。

/*fromCharCode*/
String.fromCharCode(104,101,108,108,111);    // =>hello
/*charCodeAt*/
let s = 'hello';
for(let i=0;i<s.length;i++){
  console.log(`${s[i]}----${s[i].charCodeAt()}`);
}
/*
"h----104"
"e----101"
"l----108"
"l----108"
"o----111"
*/

最后写一个字符串与数组方法应用的一个例子,熟悉它们方法的话很简单,不熟悉就会觉得有点儿乱。

let s = 'hello';
let news = s.split('').reverse().join('');
console.log(news); // => "olleh"

另附js中String和Array方法的总结图:

图片描述

查看原文

认证与成就

  • 获得 9 次点赞
  • 获得 5 枚徽章 获得 0 枚金徽章, 获得 1 枚银徽章, 获得 4 枚铜徽章

擅长技能
编辑

开源项目 & 著作
编辑

  • 网易云第三方pc客户端

    Y-Music是基于 React、Redux、Nedb、Electron 开发的网易云第三方桌面音乐客户端,数据API源自 Binaryify/NeteaseCloudMusicApi。

注册于 2018-10-09
个人主页被 477 人浏览