浏览器发请求的几种方式

Ajax请求

传统的请求方式,不可异步请求。

1
2
3
4
let xhr = new XMLHttpRequest();
xhr.open(url);
xhr.send();
xhr.onload = function(){}

fetch请求

这是浏览器新增的且是浏览器内置的请求方式,默认为异步的promise请求。

1
fetch([url,options]).then(res = > {});

axios请求

别人封装的基于promise的异步请求。

一般会封装为http.js文件

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
// http.js文件
import axios from 'axios';
import qs from 'qs'; //请求格式的转换第三方库

// webpack中可配置在什么模式下对应的地址,生产模式有两种,默认为生产环境
/*
根据环境变量区分接口的默认地址
*/
switch(process.env.NODE_ENV){
case "production":
axios.default.baseURL = "上线地址"; //在路径前面统一加上该基本地址
break;
case "test":
axios.default.baseURL = "公司给的测试地址";
break;
defalut:
axios.default.baseURL = "localhost:8080";
}
/*
设置超时时间和跨域是否允许携带凭证,如果不能携带,则你的登录校验走不了session,cookie路径
*/
axios.defaults.timeout = 10000;
axios.defaults.withCredentials = true;
/*
设置请求传递的数据格式,有后端决定,因为get请求是这种数据格式(xxx=xxx&&sss=sss),所以数据格式类型设置为x-www-form-urlencoded
*/
axios.defaults.headers['Content-Type'] = 'application/x-www-form-urlencoded';
/*
以下这种请求格式的转换一般适用于post请求
*/
axios.defaults.transformRequest = data => {
qs.stringify(data); //将数据格式转为aaa=xxx的格式
};

/*
设置请求拦截器
客户端发送请求->[请求拦截器]->服务器
TOKEN校验【JWT】,接收服务器返回的TOKEN,存储到vuex/本地存储中,每次向服务器发起请求,我们都需要吧token带上
*/
axios.interceptors.request.use(config=> {
// 获取本地的token,有者带上本地token发给后端
let token = localStorage.getItem('token');
token && (config.headers.Aythorization = token);
//必须返回配置项,否则根本更改不了发给后端的头权限
return config;
},err => {
return Promise.reject(err);
});
/*
响应拦截器
服务器返回信息 -> 【拦截的统一处理】 -> 客户端js获取到信息
*/
axios.defaults.validateStatus = status => {
//自定义响应成功的HTTP状态码
return /^(2|3)\d{2}$/.test(status);
};
axios.interceptors.response.use( res => {},err ==> {})

TOKEN校验【JWT】

当我们第一次向服务器发起请求时,服务器会通过某种算法生成用于权限验证的TOKEN并发给客户端,随后服务器要求客户端每次向服务器发起请求时都需要将TOKEN带上,服务器收到客户端的TOKEN后,会比较是否符合之前服务器生成TOKEN时的规则,符合则将请求结果返回给客户端,不符告诉客户端这是非法访问并拒绝客户端的请求。同时TOKEN有日期限制,过期者需要重新发起请求。

API的分类

  1. REST API: restful
    • 发送请求进行CRUD哪个操作由请求方式来决定。
    • 同一个请求路径可以进行多个操作。
    • 请求方式会用到GET/POST/PUT/DELETE。
  2. 非REST API: restless
    • 请求方式不决定请求的CRUD操作。
    • 一个请求路径只对应2一个操作。
    • 一般只有GET/POST请求。

json-server创建接口

1
cnpm i -g json-server

在根目录下创建db.json文件。

1
2
3
4
5
6
7
8
9
{
"posts": [
{ "id": 1, "title": "json-server", "author": "typicode" }
],
"comments": [
{ "id": 1, "body": "some comment", "postId": 1 }
],
"profile": { "name": "typicode" }
}

json-server --watch db.json即可启动并更改时自动刷新。

封装axios函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Document</title>
</head>
<body>
<button onclick="testGet()">get请求</button>
<!-- <button onclick="testPost()">post请求</button>
<button onclick="testPut()">put请求</button>
<button onclick="testDelete()">delete请求</button> -->
<script>
function testGet(){
axios({
url: 'http://localhost:3000/posts',
method: 'POST',
data: {
"title": "json-server----",
"author": "typicode----"
}
}).then(
response => {
console.log(response);
},
error => {
console.log(error.message);
}
)
}
function axios({
url,
method="GET",
params={},
data={}
}){
// 返回一个promise对象
return new Promise((resolve,reject) => {

//处理query参数(拼接到url) id=1&xxx=abc
let queryString = '';
Object.keys(params).forEach(key => {
queryString += `${key}=${params[key]}&`;
})
if(queryString){
// 如果queryString有值,去除最后的&
queryString = queryString.substring(0,queryString.length);
// 拼接到url
url += '?' + queryString;
}

// 绑定状态改变的监听,放在请求send前面比较容易理解,放在后面也可以,因为请求是异步请求的,send之后立即执行onreadystatechange同步函数
request.onreadystatechange = function(){
//如果请求没有完成,直接结束
if(request.readyState != 4){
return
}
//如果响应状态码在[200,299]之间代表成功,否则失败
const {status,statusText} = request
// 如果请求成功了调用resolve()
if(status >= 200 && status <= 299){
const response = {
data: JSON.parse(request.response),
status,
statusText
}
resolve(response)
}else{
reject(new Error('request error status is' + status));
}
}

// 异步执行ajax请求
const request = new XMLHttpRequest();
request.open(method,url,true);
if(method == "GET"){
request.send();
}else if(method == "POST"){
// 设置请求头
request.setRequestHeader('Content-Type','application/json;charset=utf-8')
request.send(JSON.stringify(data)); //发送json格式请求参数

}
})
}
</script>
</body>
</html>

html技巧

meta标签:自动刷新/跳转

<meta http-equiv="Refresh" content="5;URL=page2.html">

要实现PPT自动播放的功能,只需要在每个页面的meta标签内设置好下一个页面的地址即可。

<meta http-equiv="Refresh" content="60">每个一分钟就需要刷新页面的大屏幕监控,也可以通过meta标签来实现,只需去掉后面的URL即可。

但是在使用它的时候,刷新和跳转是不可取消的,对刷新时间间隔或需要手动取消的,推荐使用JavaScript定时器来实现。

如果只想实现页面的定时跳转或刷新,比如某些页面缺乏访问权限,在x秒后跳回首页这样的场景,建议使用meta标签。

title标签与hack手段:消息提醒

B/S架构的优点:版本更新方便,跨平台,跨终端。

但在处理某些场景,比如即时通信时,会变得比较麻烦,因为前后端通信深度依赖HTTP协议,而HTTP协议采用“请求-响应”模式,一种低效的解决方案是客户端通过轮询机制获取最新的消息。(HTML5下可使用WebSocket协议)。

消息提醒功能实现比较困难,HTML5标准发布之前,浏览器没有开放图标闪烁,弹出系统消息之类的接口,只能借助一些Hack的手段,比如修改title标签来达到类似的效果。(HTML5下可使用Web Notifications API弹出系统消息)。

1
2
3
4
5
6
7
8
9
10
11
12
13
let msgNum = 1;  //消息条数
let cnt = 0; //计数器
const interval = setInterval(() => {
cnt = (cnt + 1) % 2;
if(msgNum === 0){
//通过DOM修改title
document.title += `聊天页面`;
clearInterval(interval);
return;
}
const prefix = cnt % 2 ? `新消息(${msgNum})`:'';
document.title = `${prefix}聊天页面`
},1000)

定时修改title标签内容,可以制作其他动画效果,比如文字滚动,但需要注意浏览器会对title标签文本进行去空格操作。

性能优化

性能优化的两方面原因:渲染速度慢,请求时间长,合理使用标签,可以在一定程度上提升渲染速度以及减少请求时间。

script标签:调整加载顺序提升渲染速度

渲染引擎在解析HTML时,若遇到script标签引用文件则会暂停解析过程,同时通知网络线程加载文件,文件加载后会切换至JavaScript引擎来执行对应代码,代码执行完成之后切换至渲染引擎继续渲染页面。

script标签的三个属性:

  1. async属性——立即请求文件,但不阻塞渲染引擎,文件加载完毕后阻塞渲染引擎并立即执行文件内容。
  2. defer属性——立即请求文件,但不阻塞渲染引擎,等到解析完HTML之后再执行文件内容。
  3. HTML5标准type属性——对应值为“module”,让浏览器按照ECMA Script6标准将文件当作模块进行解析,默认阻塞效果同defer,也可以配合async在请求完成后立即执行。

js技巧

String Skill

生成随机ID
1
2
const RandomId = len => Math.random().toString(36).substr(3,len);
const id = RandomId(10);
生成随机HEX色值
1
const RandomColor = () => '#' + Math.floor(Math.random() * 0xffffff).toString(16).padEnd(6,'0');
生成星级评分
1
const StarScore = rate => '★★★★★☆☆☆☆☆'.slice(5 - rate, 10 - rate);
操作URL查询参数
1
2
3
const params = new URLSearchParams(location.search.replace(/\?/ig,""));    //location.search="?name=young&sex=male"
params.has("young"); //true
params.get("sex"); //male

Number Skill

取整

代替正数的Math.floor(), 代替负数的Math.ceil()

1
2
3
4
5
6
7
8
const num1 = ~~1.69;
const nums2 = 1.69 | 0;
const num3 = 1.69 >> 0;
/*
num1 1
num2 1
num3 1
*/
补零
1
2
3
const FillZero = (num,len) => num.toString().padstart(len,"0");
const num = FillZero(152,5);
// num => "00152"
转数值

只对null,“”,false,数值字符串有效

1
2
3
4
5
const num1 = +null;
const num2 = +"";
const num3 = +false;
const num4 = +"169";
// num1 num2 num3 num4 => 0 0 0 169
精确小数
1
2
3
const RoundNum = (num,decimal) => Math.round(num * 10 ** decimal) / 10 ** decimal;
const num = RoundNum(1.69,1);
// num => 1.7
判断奇偶
1
2
3
const OddEven = num => !!(num & 1) ? 'odd' : "even";
const num = OddEven(2);
// num => "even"
生成范围随机数
1
2
const RandomNum = (min,max) => Math.floor(Math.random() * (max - min + 1)) + min;
const num = RandomNum(1 , 10);

Boolean Skill

短路运算
1
2
3
const a = d && 1;  //满足条件赋值:取假运算,从左到右依次判断,遇到假值返回假值,后面不再执行,否则返回最后一个真值。
const b = d || 1; //默认赋值:取真运算,从左到右依次运判断,遇到真值,后面不再执行,否则返回最后一个假值。
const c = !d; //取假赋值:单个表达式转换为true则返回false,否则返回true。
判断数据类型

可判断类型:undefined,null,string,number,boolean,array,object,symbol,date,regexp,function,asyncfunction,arguments,set,map,weakset,weakmap

1
2
3
4
5
6
7
8
9
function DateType(tgt,type){
const dataType = Object.prototype.toString.call(tgt).replace(/\[object (\w+)\]/,"$1").toLowerCase();
return type ? dataType === type : dataType;
}
DataType("young"); // "string"
DataType(20190214); // "number"
DataType(true); // "boolean"
DataType([], "array"); // true
DataType({}, "array"); // false
是否为空数组
1
2
3
const arr = [];
const flag = Array.isArray(arr) && !arr.length;
// flag => true
是否为空对象
1
2
3
const obj = {};
const flag = DataType(obj,"object") && !Object.keys(obj).length;
// flag => true
满足条件时执行
1
2
3
4
5
6
const flagA = true;
const flagB = false;
(flagA || flagB) && Func(); // 满足A或B时执行
(flagA || !flagB) && Func(); //满足A或不满足B时执行
flagA && flagB && Func(); //同时满足A和B时执行
flagA && !flagB && Func(); //满足A且不满足B时执行
数组不为空时执行
1
2
const flag = false; // undefined、null、""、0、false、NaN
!flag && Func();
对象不为空时执行
1
2
const obj = { a: 0, b: 1, c: 2 };
Object.keys(obj).length && Func();
函数退出代替条件分支退出
1
2
3
4
5
6
7
8
if (flag) {
Func();
return false;
}
// 换成
if (flag) {
return Func();
}
switch/case使用区间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const age = 26;
switch (true) {
case isNaN(age):
console.log("not a number");
break;
case (age < 18):
console.log("under age");
break;
case (age >= 18):
console.log("adult");
break;
default:
console.log("please set your age");
break;
}
Array Skill
克隆数组
1
2
3
const _arr = [0,1,2];
const arr = [...arr];
// arr => [0,1,2]
合并数组
1
2
3
4
const arr1 = [0,1,2];
const arr2 = [3,4,5];
const arr = [...arr1,arr2];
// arr => [0,1,2,3,4,5]
数组去重
1
2
const arr = [...new Set([0,1,0,1,null,null])];
// arr => [0,1,null]
混淆数组
1
2
const arr = [0,1,2,3,4,5].slice().sort(() => Math.random() - 0.5);
// arr => [1,0,2,5,3,4]
截断数组
1
2
3
const arr = [0,1,2];
arr.length = 2;
arr => [0,1]
交换赋值
1
2
3
4
let a = 0;
let b = 1;
[a,b] = [b,a];
// a b => 1 0
过滤空值

空值:undefined,null,“”,0,false,NaN

1
2
const arr = [undefined,null,“”,0,false,NaN,1,2].filter(Boolean);
// arr => [1,2]
异步累计
1
2
3
4
5
6
7
8
9
10
async function Func(deps) {
return deps.reduce(async(t, v) => {
const dep = await t;
const version = await Todo(v);
dep[v] = version;
return dep;
}, Promise.resolve({}));
}
const result = await Func(); // 需在async包围下使用
复制代码
数组首部插入成员
1
2
3
4
5
6
let arr = [1, 2]; // 以下方法任选一种
arr.unshift(0);
arr = [0].concat(arr);
arr = [0, ...arr];
// arr => [0, 1, 2]
复制代码
数组尾部插入成员
1
2
3
4
5
6
7
let arr = [0, 1]; // 以下方法任选一种
arr.push(2);
arr.concat(2);
arr[arr.length] = 2;
arr = [...arr, 2];
// arr => [0, 1, 2]
复制代码
统计数组成员个数
1
2
3
4
5
6
7
const arr = [0, 1, 1, 2, 2, 2];
const count = arr.reduce((t, v) => {
t[v] = t[v] ? ++t[v] : 1;
return t;
}, {});
// count => { 0: 1, 1: 2, 2: 3 }
复制代码
解构数组成员嵌套
1
2
3
4
const arr = [0, 1, [2, 3, [4, 5]]];
const [a, b, [c, d, [e, f]]] = arr;
// a b c d e f => 0 1 2 3 4 5
复制代码
解构数组成员别名
1
2
3
4
const arr = [0, 1, 2];
const { 0: a, 1: b, 2: c } = arr;
// a b c => 0 1 2
复制代码
解构数组成员默认值
1
2
3
4
const arr = [0, 1, 2];
const [a, b, c = 3, d = 4] = arr;
// a b c d => 0 1 2 4
复制代码
获取随机数组成员
1
2
3
4
const arr = [0, 1, 2, 3, 4, 5];
const randomItem = arr[Math.floor(Math.random() * arr.length)];
// randomItem => 1
复制代码
创建指定长度数组
1
2
3
const arr = [...new Array(3).keys()];
// arr => [0, 1, 2]
复制代码
创建指定长度且值相等的数组
1
2
3
const arr = new Array(3).fill(0);
// arr => [0, 0, 0]
复制代码
reduce代替map和filter
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
const _arr = [0, 1, 2];

// map
const arr = _arr.map(v => v * 2);
const arr = _arr.reduce((t, v) => {
t.push(v * 2);
return t;
}, []);
// arr => [0, 2, 4]

// filter
const arr = _arr.filter(v => v > 0);
const arr = _arr.reduce((t, v) => {
v > 0 && t.push(v);
return t;
}, []);
// arr => [1, 2]

// map和filter
const arr = _arr.map(v => v * 2).filter(v => v > 2);
const arr = _arr.reduce((t, v) => {
v = v * 2;
v > 2 && t.push(v);
return t;
}, []);
// arr => [4]
复制代码

Object Skill

克隆对象
1
2
3
4
5
const _obj = { a: 0, b: 1, c: 2 }; // 以下方法任选一种
const obj = { ..._obj };
const obj = JSON.parse(JSON.stringify(_obj));
// obj => { a: 0, b: 1, c: 2 }
复制代码
合并对象
1
2
3
4
5
const obj1 = { a: 0, b: 1, c: 2 };
const obj2 = { c: 3, d: 4, e: 5 };
const obj = { ...obj1, ...obj2 };
// obj => { a: 0, b: 1, c: 3, d: 4, e: 5 }
复制代码
对象字面量

获取环境变量时必用此方法,用它一直爽,一直用它一直爽

1
2
3
4
5
6
7
8
const env = "prod";
const link = {
dev: "Development Address",
test: "Testing Address",
prod: "Production Address"
}[env];
// link => "Production Address"
复制代码
对象变量属性
1
2
3
4
5
6
7
8
const flag = false;
const obj = {
a: 0,
b: 1,
[flag ? "c" : "d"]: 2
};
// obj => { a: 0, b: 1, d: 2 }
复制代码
创建纯空对象
1
2
3
const obj = Object.create(null);
Object.prototype.a = 0;
// obj => {}
删除对象无用属性
1
2
3
const obj = { a: 0, b: 1, c: 2 }; // 只想拿b和c
const { a, ...rest } = obj;
// rest => { b: 1, c: 2 }
解构对象属性嵌套
1
2
3
const obj = { a: 0, b: 1, c: { d: 2, e: 3 } };
const { c: { d, e } } = obj;
// d e => 2 3
解构对象属性别名
1
2
3
const obj = { a: 0, b: 1, c: 2 };
const { a, b: d, c: e } = obj;
// a d e => 0 1 2
解构对象属性默认值
1
2
3
const obj = { a: 0, b: 1, c: 2 };
const { a, b = 2, d = 3 } = obj;
// a b d => 0 1 3

Function Skill

函数自执行
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const Func = function() {}(); // 常用

(function() {})(); // 常用
(function() {}()); // 常用
[function() {}()];

+ function() {}();
- function() {}();
~ function() {}();
! function() {}();

new function() {};
new function() {}();
void function() {}();
typeof function() {}();
delete function() {}();

1, function() {}();
1 ^ function() {}();
1 > function() {}();
隐式返回值

只能用于单语句返回值箭头函数,如果返回值是对象必须使用()包住

1
2
3
4
5
const Func = function(name) {
return "I Love " + name;
};
// 换成
const Func = name => "I Love " + name;
一次性函数

适用于运行一些只需执行一次的初始化代码

1
2
3
4
5
6
function Func() {
console.log("x");
Func = function() {
console.log("y");
}
}
惰性载入函数

函数内判断分支较多较复杂时可大大节约资源开销

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function Func() {
if (a === b) {
console.log("x");
} else {
console.log("y");
}
}
// 换成
function Func() {
if (a === b) {
Func = function() {
console.log("x");
}
} else {
Func = function() {
console.log("y");
}
}
return Func();
}
检测非空参数
1
2
3
4
5
6
7
8
function IsRequired() {
throw new Error("param is required");
}
function Func(name = IsRequired()) {
console.log("I Love " + name);
}
Func(); // "param is required"
Func("You"); // "I Love You"
字符串创建函数
1
const Func = new Function("name", "console.log(\"I Love \" + name)");
优雅处理错误信息
1
2
3
4
5
try {
Func();
} catch (e) {
location.href = "https://stackoverflow.com/search?q=[js]+" + e.message;
}
优雅处理Async/Await参数
1
2
3
4
function AsyncTo(promise) {
return promise.then(data => [null, data]).catch(err => [err]);
}
const [err, res] = await AsyncTo(Func());
优雅处理多个函数返回值
1
2
3
4
5
6
7
function Func() {
return Promise.all([
fetch("/user"),
fetch("/comment")
]);
}
const [user, comment] = await Func(); // 需在async包围下使用

DOM Skill

显示全部DOM边框

调试页面元素边界时使用

1
2
3
[].forEach.call($$("*"), dom => {
dom.style.outline = "1px solid #" + (~~(Math.random() * (1 << 24))).toString(16);
});
自适应页面

页面基于一张设计图但需做多款机型自适应,元素尺寸使用rem进行设置

1
2
3
4
5
6
function AutoResponse(width = 750) {
const target = document.documentElement;
target.clientWidth >= 600
? (target.style.fontSize = "80px")
: (target.style.fontSize = target.clientWidth / width * 100 + "px");
}
过滤XSS
1
2
3
4
5
6
7
function FilterXss(content) {
let elem = document.createElement("div");
elem.innerText = content;
const result = elem.innerHTML;
elem = null;
return result;
}
存取LocalStorage

反序列化取,序列化存

1
2
const love = JSON.parse(localStorage.getItem("love"));
localStorage.setItem("love", JSON.stringify("I Love You"));
一个键盘!
1
2
(_=>[..."`1234567890-=~~QWERTYUIOP[]\\~ASDFGHJKL;'~~ZXCVBNM,./~"].map(x=>(o+=`/${b='_'.repeat(w=x<y?2:' 667699'[x=["Bs","Tab","Caps","Enter"][p++]||'Shift',p])}\\|`,m+=y+(x+'    ').slice(0,w)+y+y,n+=y+b+y+y,l+=' __'+b)[73]&&(k.push(l,m,n,o),l='',m=n=o=y),m=n=o=y='|',p=l=k=[])&&k.join`
`)()

######

css技术技巧

layout skill

使用vw定制rem自适应布局
  • 要点:移动端使用rem布局需要通过JS设置不同屏幕宽高比的font-size,结合vw单位和calc()可脱离JS的控制。

  • 场景:rem页面布局(不兼容低版本移动端系统)

  • 兼容:vw,calc()

    1
    2
    3
    4
    /* 基于UI width=750px DPR=2的页面 */
    html{
    font-size: calc(100vw / 7.5);
    }
使用:nth-child()筛选指定元素
  • 要点:通过:nth-child()筛选指定的元素设置样式。
  • 场景:表格着色,边界元素排版(首元素,尾元素,左右两边元素)
使用writing-mode排版竖文
  • 要点:通过writing-mode调整文本排版方向。
  • 场景:竖行文字,文言文,诗词。
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
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Document</title>
<style>
html{
background-color: #000;
}
.vertical-text{
writing-mode: vertical-rl;
}
.vertical-text h3{
padding-left: 20px;
font-weight: bold;
font-size: 18px;
color: #f66;
}
.vertical-text p{
line-height: 30px;
color: #66f;
}
</style>
</head>
<body>
<div class="vertical-text">
<h3></h3>
<p>我见犹怜,<br>爱不释手。<br>雅俗共赏,<br>君子好逑。</p>
</div>
</body>
</html>

数组中的reduce

reduce

reduce作为es5新增的常规数组方法之一,却比forEach,filter和map更强大。

  • 它是对数组中的每个元素执行一个自定义的累计器,将结果汇总为单个返回值。
  • 形式:array.reduce((t, v, i, a) => {}, initValue)
  • 参数
    • callback:回调函数(必选)
    • initValue:初始值(可选)
  • 回调函数的参数
    • total(t):累计器完成计算的返回值(必选)
    • value(v):当前元素(必选)
    • index(i):当前元素的索引(可选)
    • array(a):当前元素所属的数组对象(可选)
  • 过程
    • t作为累计结果的初始值,不设置t则以数组第一个元素为初始值
    • 开始遍历,使用累计器处理v,将v的映射结果累计到t上,结束此次循环,返回t
    • 进入下一次循环,重复上述操作,直至数组最后一个元素
    • 结束遍历,返回最终的t

reduce的精华所在是将累计器逐个作用于数组成员上,把上一次输出的值作为下一次输入的值。下面举个简单的例子,看看reduce的计算结果。

1
2
3
4
const arr = [3, 5, 1, 4, 2];
const a = arr.reduce((t, v) => t + v);
// 等同于
const b = arr.reduce((t, v) => t + v, 0);

贴一个reduce的作用动图

reduce

reduce实质上是一个累计器函数,通过用户自定义的累计器对数组成员进行自定义累计,得出一个由累计器生成的值。另外reduce还有一个胞弟reduceRight,两个方法的功能其实是一样的,只不过reduce是升序执行,reduceRight是降序执行。

对空数组调用reduce()和reduceRight()是不会执行其回调函数的,可认为reduce()对空数组无效

高级用法

累加累乘
1
2
3
4
5
6
7
8
9
10
11
function Accumulation(...vals){
return vals.reduce((total,value) => {
total + value
},0);
}

function Multiplication(...vals){
return vals.reduce((total,value) => {
total * value
},1);
}
权重求和
1
2
3
4
5
6
const scores = [
{ score: 90, subject: "chinese", weight: 0.5 },
{ score: 95, subject: "math", weight: 0.3 },
{ score: 85, subject: "english", weight: 0.2 }
];
const result = scores.reduce((t, v) => t + v.score * v.weight, 0); // 90.5
代替reverse
1
2
3
4
5
function Reverse(arr = []) {
return arr.reduceRight((t, v) => (t.push(v), t), []);
}

Reverse([1, 2, 3, 4, 5]); // [5, 4, 3, 2, 1]

(t.push(v), t),逗号最后面的t 代表的啥意思?

这是用到了逗号操作符,返回t的意思

代替map和filter
1
2
3
4
5
6
7
8
9
10
11
12
13
const arr = [0,1,2,3];

// 代替map:[0, 2, 4, 6]
const a = arr.map(v => v * 2);
const b = arr.reduce((t, v) => [...t, v * 2], []);

// 代替filter:[2, 3]
const c = arr.filter(v => v > 1);
const d = arr.reduce((t, v) => v > 1 ? [...t, v] : t, []);

// 代替map和filter:[4, 6]
const e = arr.map(v => v * 2).filter(v => v > 2);
const f = arr.reduce((t, v) => v * 2 > 2 ? [...t, v * 2] : t, []);
代替some和every
1
2
3
4
5
6
7
8
9
10
11
const scores = [
{ score: 45, subject: "chinese" },
{ score: 90, subject: "math" },
{ score: 60, subject: "english" }
];

// 代替some:至少一门合格
const isAtLeastOneQualified = scores.reduce((t, v) => t || v.score >= 60, false); // true

// 代替every:全部合格
const isAllQualified = scores.reduce((t, v) => t && v.score >= 60, true); // false
数组分割
1
2
3
4
5
6
function Chunk(arr = [], size = 1) {
return arr.length ? arr.reduce((t, v) => (t[t.length - 1].length === size ? t.push([v]) : t[t.length - 1].push(v), t), [[]]) : [];
}

const arr = [1, 2, 3, 4, 5];
Chunk(arr, 2); // [[1, 2], [3, 4], [5]]
数组过滤
1
2
3
4
5
6
7
function Difference(arr = [], oarr = []) {
return arr.reduce((t, v) => (!oarr.includes(v) && t.push(v), t), []);
}

const arr1 = [1, 2, 3, 4, 5];
const arr2 = [2, 3, 6]
Difference(arr1, arr2); // [1, 4, 5]
数组填充
1
2
3
4
5
6
7
8
9
10
11
function Fill(arr = [], val = "", start = 0, end = arr.length) {
if (start < 0 || start >= end || end > arr.length) return arr;
return [
...arr.slice(0, start),
...arr.slice(start, end).reduce((t, v) => (t.push(val || v), t), []),
...arr.slice(end, arr.length)
];
}

const arr = [0, 1, 2, 3, 4, 5, 6];
Fill(arr, "aaa", 2, 5); // [0, 1, "aaa", "aaa", "aaa", 5, 6]
数组扁平
1
2
3
4
5
6
function Flat(arr = []) {
return arr.reduce((t, v) => t.concat(Array.isArray(v) ? Flat(v) : v), [])
}

const arr = [0, 1, [2, 3], [4, 5, [6, 7]], [8, [9, 10, [11, 12]]]];
Flat(arr); // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
数组去重
1
2
3
4
5
6
function Uniq(arr = []) {
return arr.reduce((t, v) => t.includes(v) ? t : [...t, v], []);
}

const arr = [2, 1, 0, 3, 2, 1, 2];
Uniq(arr); // [2, 1, 0, 3]
数组最大最小值
1
2
3
4
5
6
7
8
9
10
11
function Max(arr = []) {
return arr.reduce((t, v) => t > v ? t : v);
}

function Min(arr = []) {
return arr.reduce((t, v) => t < v ? t : v);
}

const arr = [12, 45, 21, 65, 38, 76, 108, 43];
Max(arr); // 108
Min(arr); // 12
数组成员独立拆解
1
2
3
4
5
6
7
8
9
function Unzip(arr = []) {
return arr.reduce(
(t, v) => (v.forEach((w, i) => t[i].push(w)), t),
Array.from({ length: Math.max(...arr.map(v => v.length)) }).map(v => [])
);
}
js
const arr = [["a", 1, true], ["b", 2, false]];
Unzip(arr); // [["a", "b"], [1, 2], [true, false]]
数组成员个数统计
1
2
3
4
5
6
function Count(arr = []) {
return arr.reduce((t, v) => (t[v] = (t[v] || 0) + 1, t), {});
}

const arr = [0, 1, 1, 2, 2, 2];
Count(arr); // { 0: 1, 1: 2, 2: 3 }

此方法是字符统计和单词统计的原理,入

参时把字符串处理成数组即可

数组成员位置记录
1
2
3
4
5
function Position(arr = [], val) {
return arr.reduce((t, v, i) => (v === val && t.push(i), t), []);
}
const arr = [2, 1, 5, 4, 2, 1, 6, 6, 7];
Position(arr, 2); // [0, 4]
数组成员特性分组
1
2
3
4
5
6
7
8
9
10
11
12
function Group(arr = [], key) {
return key ? arr.reduce((t, v) => (!t[v[key]] && (t[v[key]] = []), t[v[key]].push(v), t), {}) : {};
}
复制代码
const arr = [
{ area: "GZ", name: "YZW", age: 27 },
{ area: "GZ", name: "TYJ", age: 25 },
{ area: "SZ", name: "AAA", age: 23 },
{ area: "FS", name: "BBB", age: 21 },
{ area: "SZ", name: "CCC", age: 19 }
]; // 以地区area作为分组依据
Group(arr, "area"); // { GZ: Array(2), SZ: Array(2), FS: Array(1) }
数组成员所含关键字统计
1
2
3
4
5
6
7
8
9
10
11
function Keyword(arr = [], keys = []) {
return keys.reduce((t, v) => (arr.some(w => w.includes(v)) && t.push(v), t), []);
}
const text = [
"今天天气真好,我想出去钓鱼",
"我一边看电视,一边写作业",
"小明喜欢同桌的小红,又喜欢后桌的小君,真TM花心",
"最近上班喜欢摸鱼的人实在太多了,代码不好好写,在想入非非"
];
const keyword = ["偷懒", "喜欢", "睡觉", "摸鱼", "真好", "一边", "明天"];
Keyword(text, keyword); // ["喜欢", "摸鱼", "真好", "一边"]
字符串翻转
1
2
3
4
5
function ReverseStr(str = "") {
return str.split("").reduceRight((t, v) => t + v);
}
const str = "reduce最牛逼";
ReverseStr(str); // "逼牛最ecuder"
数字千分化
1
2
3
4
5
6
7
8
9
10
11
function ThousandNum(num = 0) {
const str = (+num).toString().split(".");
const int = nums => nums.split("").reverse().reduceRight((t, v, i) => t + (i % 3 ? v : `${v},`), "").replace(/^,|,$/g, "");
const dec = nums => nums.split("").reduce((t, v, i) => t + ((i + 1) % 3 ? v : `${v},`), "").replace(/^,|,$/g, "");
return str.length > 1 ? `${int(str[0])}.${dec(str[1])}` : int(str[0]);
}

ThousandNum(1234); // "1,234"
ThousandNum(1234.00); // "1,234"
ThousandNum(0.1234); // "0.123,4"
ThousandNum(1234.5678); // "1,234.567,8"
异步累计
1
2
3
4
5
6
7
8
9
async function AsyncTotal(arr = []) {
return arr.reduce(async(t, v) => {
const at = await t;
const todo = await Todo(v);
at[v] = todo;
return at;
}, Promise.resolve({}));
}
const result = await AsyncTotal(); // 需要在async包围下使用
斐波那契数列
1
2
3
4
5
6
function Fibonacci(len = 2) {
const arr = [...new Array(len).keys()];
return arr.reduce((t, v, i) => (i > 1 && t.push(t[i - 1] + t[i - 2]), t), [0, 1]);
}

Fibonacci(10); // [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
URL参数反序列化
1
2
3
4
5
6
7
8
9
10
function ParseUrlSearch() {
return location.search.replace(/(^\?)|(&$)/g, "").split("&").reduce((t, v) => {
const [key, val] = v.split("=");
t[key] = decodeURIComponent(val);
return t;
}, {});
}

// 假设URL为:https://www.baidu.com?age=25&name=TYJ
ParseUrlSearch(); // { age: "25", name: "TYJ" }
URL参数序列化
1
2
3
4
5
6
7
function StringifyUrlSearch(search = {}) {
return Object.entries(search).reduce(
(t, v) => `${t}${v[0]}=${encodeURIComponent(v[1])}&`,
Object.keys(search).length ? "?" : ""
).replace(/&$/, "");
}
StringifyUrlSearch({ age: 27, name: "YZW" }); // "?age=27&name=YZW"
返回对象指定键值
1
2
3
4
5
6
7
function GetKeys(obj = {}, keys = []) {
return Object.keys(obj).reduce((t, v) => (keys.includes(v) && (t[v] = obj[v]), t), {});
}
复制代码
const target = { a: 1, b: 2, c: 3, d: 4 };
const keyword = ["a", "d"];
GetKeys(target, keyword); // { a: 1, d: 4 }
数组转对象
1
2
3
4
5
6
7
8
9
const people = [
{ area: "GZ", name: "YZW", age: 27 },
{ area: "SZ", name: "TYJ", age: 25 }
];
const map = people.reduce((t, v) => {
const { name, ...rest } = v;
t[name] = rest;
return t;
}, {}); // { YZW: {…}, TYJ: {…} }
Redux Compose函数原理
1
2
3
4
5
6
7
8
9
function Compose(...funs) {
if (funs.length === 0) {
return arg => arg;
}
if (funs.length === 1) {
return funs[0];
}
return funs.reduce((t, v) => (...arg) => t(v(...arg)));
}

###

‘力扣简单题’

数组

数组取交集

1
const duplicatedValues = [...new Set(arr1)].filter(item => arr2.includes(item))

数组取差集

1
const diffValues = [...new Set([...arr1,...arr2])].filter(item => !b.includes(item) || !a.includes(item))

数组转对象

1
2
3
4
5
6
7
const arr = [1, 2, 3, 4]
const newObj = {...arr} // {0: 1, 1: 2, 2: 3, 3: 4}
const obj = {0: 0, 1: 1, 2: 2, length: 3}
// 对象转数组不能用展开操作符,因为展开操作符必须用在可迭代对象上
let newArr = [...obj] // Uncaught TypeError: object is not iterable...
// 可以使用Array.form()将类数组对象转为数组
let newArr = Array.from(obj) // [0, 1, 2]

数组摊平

1
2
3
4
5
6
7
8
[1, 2, [3, [4, 5]]].flat()
// [1, 2, 3, [4, 5]]
[1, 2, [3, [4, 5]]].flat(2)
// [1, 2, 3, 4, 5]
//上面代码中,flat()的参数为2,表示要拉平两层的嵌套数组。
//如果不管有多少层嵌套,都要转成一维数组,可以用Infinity关键字作为参数。
[1, [2, [3]]].flat(Infinity)
// [1, 2, 3]

数组去重

原地修改原数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* @param {number[]} nums
* @return {number}
*/
var removeDuplicates = function(nums) {
// 记录nums元素个数
let len = nums.length;
let count = 0;
//遍历数组元素,若后一项与前一项相同,则复制后面元素到重复位上
for(var i = 1; i < nums.length; i++){
if(nums[i] != nums[i-1]){
nums[i - count] = nums[i];
}else{
count ++;
}
}
return len - count;
};

不修改原数组

1
2
3
4
5
//数据结构Set数据结构去重。
function removeDuplicates(nums){
let arr = [...new Set(nums)];
return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12
//利用object对象键值唯一性去重
function removeDuplicates(nums){
let obj = {};
let arr = [];
for(let item of nums){
obj[item] = 1;
}
for(let key in obj){
arr.push(key);
}
return arr;
}
1
2
3
4
5
6
7
8
9
10
// 利用indexOf判断
function removeDuplicates(nums){
let arr = [];
for(let i = 0; i < nums.length; i++){
if(arr.indexOf(nums[i]) == -1){
arr.push(nums[i]);
}
}
return arr;
}
1
2


数组移除元素

给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。

不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
var removeElement = function (nums, val) {
// 记录数组元素个数,当匹配到,将最后的元素填到前面来
var ans = nums.length;
for(var i = 0; i< ans;){
if(nums[i] == val){
nums[i] = nums[ans -1];
ans --;
}else{
i++;
}
}
return ans;
};
1
2
3
4
5
6
7
8
9
10
11
//最优解
var removeElement = function (nums, val) {
// for...of循环数组,不等于val的值的存入nums数组中
let count = 0;
for(var num of nums){
if(num != val){
nums[ count++] = num;
}
}
return count;
};

移除数组中的元素

移除数组 arr 中的所有值与 item 相等的元素,直接在给定的 arr 数组上进行操作,并将结果返回

示例1

输入

1
[1, 2, 2, 3, 4, 2, 2], 2

输出

1
[1, 3, 4]
1
2
3
4
5
6
7
8
9
10
function removeWithoutCopy(arr, item) {
for(let i = 0; i < arr.length;i++){
if(arr.indexOf(item) == -1) break;
if(arr[i] == item){
arr.splice(i,1);
i--;
}
}
return arr;
}

数组搜索插入位置

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

1
2
3
4
5
6
7
 var searchInsert = function (nums, target) {
if (nums.indexOf(target) == -1) {
nums.push(target);
nums.sort((a,b) => a-b);
}
return nums.indexOf(target);
};

合并两个数组

改变原数组

给你两个有序整数数组 nums1nums2*,请你将 *nums2 合并到 nums1使 num1 成为一个有序数组。

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

输出: [1,2,2,3,5,6]

1
2
3
4
5
6
7
8
9
10
11
12
/**
* @param {number[]} nums1
* @param {number} m
* @param {number[]} nums2
* @param {number} n
* @return {void} Do not return anything, modify nums1 in-place instead.
*/
//从返回值为空可知,必须修改nums1中的参数
var merge = function(nums1, m, nums2, n) {
nums1.splice(m,n,...nums2);
nums1.sort((a,b) => a-b)
};

不改变原数组

1
2
3
4
5
var merge = function(nums1, m, nums2, n) {
let arr = [...nums1,...nums2];
arr.splice(m,n);
return arr;
};

和为s的两个数字

输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多对数字的和等于s,则输出任意一对即可。

示例 1:

输入:nums = [2,7,11,15], target = 9
输出:[2,7] 或者 [7,2]

示例 2:

输入:nums = [10,26,30,31,47,60], target = 40
输出:[10,30] 或者 [30,10]

限制:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
let left = 0,
right = nums.length - 1;
while (left < right) {
if (nums[left] + nums[right] == target) {
return [nums[left], nums[right]];
} else if (nums[left] + nums[right] < target) {
left++;
} else {
right--;
}
}
};
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
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
//nums已经排序了,二分法
let avg= target/2;
let j;//接近avg的索引下标
for(let i = 0; i< nums.length; i++){
if(avg >= nums[i]){
j=i;
break;
}
}
let left=j;
for(let right=j;right<nums.length;right++){
let x = target - nums[right];
while(left>=0 && nums[left] > x){
left--;
}
if(left < 0)break;
if(nums[left] === x && left!==right)return [nums[left],nums[right]];
left++;
}
return [];
};

和为s的连续正数序列

输入一个正整数 target ,输出所有和为 target 的连续正整数序列(至少含有两个数)。

序列内的数字由小到大排列,不同序列按照首个数字从小到大排列。

示例 1:

输入:target = 9
输出:[[2,3,4],[4,5]]

示例 2:

输入:target = 15
输出:[[1,2,3,4,5],[4,5,6],[7,8]]

限制:

1 <= target <= 10^5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* @param {number} target
* @return {number[][]}
*/
var findContinuousSequence = function(target) {
////由规律得,序列中最大值是target的一半+ 或 - 1
let index = target % 2 ? (target + 1)/2 : target/2;

let res = []; //存储结果
let temp = []; //存储从下标值
let sum = 0; //与target作比较
for(let i = 1; i <= index; i++){
temp.push(i);
sum += i;
while(sum > target){
sum -= temp[0];
temp.shift();
}
if(sum == target){
temp.length >= 2 && res.push([...temp]);
}
}
return res;
};

最大子序和

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* @param {number[]} nums
* @return {number}
*/
//动态规划法(缺点:突然中断,算出来的是已经遍历过的数)
// 定义一个回调方法ans保存结果值,sum为求和后的值,将ans和sum中的最大值赋给ans
var maxSubArray = function(nums){
let ans = nums[0];
let sum = 0;
for(let num of nums){
if(sum > 0){
sum += num;
}else{
sum = num;
}
ans = Math.max(ans,sum);
}
return ans;
};

滑动窗口最大值

给定一个数组 nums 和滑动窗口的大小 k,请找出所有滑动窗口里的最大值。

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:

滑动窗口的位置 最大值


[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSlidingWindow = function(nums, k) {
if(nums.length===0)return []; //边界值
let max=[];
for(let i=0; i+k-1<nums.length;i++){
let m=Math.max(...nums.slice(i,i+k));
max.push(m);
}
return max;
};

旋转数组

给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。

示例 1:

输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]

说明:

尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。
要求使用空间复杂度为 O(1) 的 原地 算法。

1
2
3
4
5
6
7
8
9
//改变数组,利用数组的splice的增加删除操作原地操作
/**
* @param {number[]} nums
* @param {number} k
* @return {void} Do not return anything, modify nums in-place instead.
*/
var rotate = function(nums,k){
nums.splice(0,0,...nums.splice(nums.length-k));
};

字符异位词分组

给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。

示例:

输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
输出:
[
[“ate”,”eat”,”tea”],
[“nat”,”tan”],
[“bat”]
]

说明:

所有输入均为小写字母。
不考虑答案输出的顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* @param {string[]} strs
* @return {string[][]}
*/
var groupAnagrams = function(strs) {
// 利用哈希表存储,键值唯一
let hash = new Map();
for(let i = 0; i < strs.length;i++){
if(hash.has(str)){
let temp = hash.get(str);
temp.push(strs[i]);
hash.set(str,temp);
}else{
hash.set(str,[strs]);
}
}
return [...hash.values()]
};

####

罗马数字转整数

罗马数字包含以下七种字符: IVXLCDM

1
2
3
4
5
6
7
8
字符          数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

例如, 罗马数字 2 写做 II ,即为两个并列的 1。12 写做 XII ,即为 X + II 。 27 写做 XXVII, 即为 XX + V + II

通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:

  • I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。
  • C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。

给定一个罗马数字,将其转换成整数。输入确保在 1 到 3999 的范围内。

将可能出现的情况存到map中,定义一个变量存返回值。优先判断是否符合两个的字符。

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
/**
* @param {string} s
* @return {number}
*/

var romanToInt = function (s) {
let map = {
I : 1,
IV: 4,
V: 5,
IX: 9,
X: 10,
XL: 40,
L: 50,
XC: 90,
C: 100,
CD: 400,
D: 500,
CM: 900,
M: 1000
}
let ans = 0;
for(var i = 0; i < s.length;){
if(i + 1 < s.length && map[s.substring(i,i+2)]){
ans += map[s.substring(i,i+2)];
i += 2;
}else{
ans += map[s.substring(i,i+1)];
i++;
}
}
return ans;
};

数组中重复数字

在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1:

输入:
[2, 3, 1, 0, 2, 5, 3]
输出:2 或 3

1
2
3
4
5
6
7
8
9
10
11
12
/**
* @param {number[]} nums
* @return {number}
*/
var findRepeatNumber = function(nums) {
for(let i = 0; i < nums.length; i++){
// 利用向前遍历的与向后遍历的下标值不同找出重复值
if(nums.lastIndexOf(nums[i]) != i){
return nums[i];
}
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 使用set,因为set自动忽略重复元素,遍历数组中元素,若长度未增加,则输出当前元素
/**
* @param {number[]} nums
* @return {number}
*/
var findRepeatNumber = function(nums) {
let s=new Set();
for(var i in nums){
var curLenth=s.size;
s.add(nums[i]);
if(s.size==curLenth)
return nums[i];
}
};

二维数组的查找

在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

示例:

现有矩阵 matrix 如下:

[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]

给定 target = 5,返回 true。

给定 target = 20,返回 false。

1
2
3
4
5
6
7
8
/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
var findNumberIn2DArray = function(matrix, target) {
return matrix.flat(Infinity).includes(target);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
// 从左上角看,其上的数值都比该值小,右边的数值都比该值大
var findNumberIn2DArray = function (matrix, target) {
if (matrix.length == 0) return false;
let x = 0;
let y = matrix.length - 1;
while (x < matrix[0].length && y >= 0) {
if (matrix[y][x] > target) {
y--;
} else if (matrix[y][x] < target) {
x++;
} else {
return true;
}
}
return false;
};
在排序数组中查找数字

统计一个数字在排序数组中出现的次数。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: 2

示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: 0

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
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function (nums, target) {
// 第一种方法
// var count = 0;
// for(let val of nums){
// if(val == target){
// count++;
// }
// }
// return count;
// 第二种方法
// let left = 0,
// len = nums.length;
// right = len - 1;
// while(left < len && nums[left] != target){
// left++;
// }
// while(right > 0 && nums[right] != target){
// right--;
// }
// return left <= right ? right - left + 1 : 0;

// 第三种方法
let left = nums.indexOf(target);
let right = nums.lastIndexOf(target);
if(left != -1 && right != -1){
return right - left + 1;
}
return 0;
};

字符串

字符串数组中的最长公共前缀

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
编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀,返回空字符串 ""。

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"
示例 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

/**
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function(strs) {
if(strs.length == 0) return '';
let ans = strs[0];
for(let i = 0;i < strs.length;i++){
let j = 0;
for(;j < ans.length && j < strs[i].length;j++){
if(ans[j] != strs[i][j]) break;
}
ans = ans.substr(0,j);
}
return ans;
};
let strs = ["dog","racecar","car"]
console.log(longestCommonPrefix(strs));

有效字符串

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
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。

有效字符串需满足:

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

/*
边遍历便匹配,即遇到的第一个右括号必须与数组中最后一个元素匹配,否则无效。
匹配完成后从数组中删除此元素。
@param {string} s
@return {boolean}
*/
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s){
//构建一个map结构的对象
let map = {
"(": ")",
"{": "}",
"[": "]"
};
let leftArr = []; //用于存放左括号
for(let ch of s){
if(ch in map) leftArr.push(ch);
else{
if(ch != map[leftArr.pop()]){
return false;
}
}
}
return !leftArr.length; //避免都是左括号
}

字符串中找最大数字

输入一串只有数字和字母的字符串,输出该字符串中最大的数字

输入:hellowolrd520hellowor

ld1314

输出:1314

1
2
3
4
5
6
7
8
9
10
11
let str = 'hellowolrd520helloworld1314';

let reg = /\d+/g;

let arr = str.match(reg);

console.log(arr);

let max = Math.max(...arr);

console.log(max);
1
2
3
4
5
6
7
8
9
let str = 'hellowolrd520helloworld1314';

let reg = /[a-z]+/g;

let arr = str.split(reg);

let max = Math.max(...arr);

console.log(max);

最后一个单词的长度

给定一个仅包含大小写字母和空格 ‘ ‘ 的字符串 s,返回其最后一个单词的长度。如果字符串从左向右滚动显示,那么最后一个单词就是最后出现的单词。

如果不存在最后一个单词,请返回 0 。

说明:一个单词是指仅由字母组成、不包含任何空格字符的 最大子字符串。

1
2
3
4
5
6
7
8
var lengthOfLastWord = function(s) {
// 去除字符串两边的空格
s = s.trim();
let arr = s.split(' ');
let len = arr.length;
if(len == 0) return 0;
return arr[len - 1].length;
};

翻转单词顺序

输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变。为简单起见,标点符号和普通字母一样处理。例如输入字符串”I am a student. “,则输出”student. a am I”。

示例 1:

输入: “the sky is blue”
输出: “blue is sky the”

示例 2:

输入: “ hello world! “
输出: “world! hello”
解释: 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。

示例 3:

输入: “a good example”
输出: “example good a”
解释: 如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个。

说明:

无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。
如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个。
1
2
3
4
//先去空格(此步可省),分割为字符串数组,去除多余空格,翻转后转为字符串
var reverseWords = function(s) {
return s.trim().split(' ').filter(x => !!x).reverse().join(' ');
};

颠倒二进制

颠倒给定的 32 位无符号整数的二进制位。

示例 1:

输入: 00000010100101000001111010011100
输出: 00111001011110000010100101000000
解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596,
因此返回 964176192,其二进制表示形式为 00111001011110000010100101000000。

示例 2:

输入:11111111111111111111111111111101
输出:10111111111111111111111111111111
解释:输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293,
因此返回 3221225471 其二进制表示形式为 10101111110010110010011101101001。

提示:

请注意,在某些语言(如 Java)中,没有无符号整数类型。在这种情况下,输入和输出都将被指定为有符号整数类型,并且不应影响您的实现,因为无论整数是有符号的还是无符号的,其内部的二进制表示形式都是相同的。
在 Java 中,编译器使用二进制补码记法来表示有符号整数。因此,在上面的 示例 2 中,输入表示有符号整数 -3,输出表示有符号整数 -1073741825。

进阶:
如果多次调用这个函数,你将如何优化你的算法?

1
2
3
4
5
//利用字符串的toString方法转为二进制数
var reverseBits = function(n) {
//二进制以0b开头
return +('0b'+n.toString(2).padStart(32,0).split('').reverse().join(''))
};

替换空格

请实现一个函数,把字符串 s 中的每个空格替换成”%20”。

示例 1:

输入:s = “We are happy.”
输出:”We%20are%20happy.”

1
2
3
4
5
6
7
/**
* @param {string} s
* @return {string}
*/
var replaceSpace = function(s) {
return s.replace(/\s/g,'%20')
};

因为字符串是不可变的,所以如果直接采用从头到尾遍历原字符串检查空格,并且做替换。那么每次检查到空格后,都需要重新生成字符串。整个过程时间复杂度是 O(N^2)。

优化的关键:提前计算替换后的字符串的长度,避免每次都对字符串做改动。

整体思路如下:

遍历原字符串,统计空格和非空格字符个数,计算替换后的新字符的长度
准备两个指针,指针 i 指向原字符串,指针 j 指向新字符串
i 从头开始遍历原字符串
    str[i]是非空格,那么将 i 指向的字符放入新字符串的 j 位置。i 和 j 都增加 1。
    str[i]是空格,那么 j 指向的位置依次填入%20。i 增加 1,j 增加 3。

时间复杂度是 O(N)。因为需要对新字符串开辟容器,空间复杂度是 O(N)。

链表

1
2
3
4
function ListNode(val){
this.val = val;
this.next = null;
}

合并两个排序链表

输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。

1
2
3
> 输入:1->2->4, 1->3->4
> 输出:1->1->2->3->4->4
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var mergeTwoLists = function(l1,l2){
if(l1 == null){
return l2;
}
if(l2 == null){
return l1;
}
if(l1.val < l2.val){
l1.next = mergeTwoLists(l1.next,l2);
return l1;
}else{
l2.next = mergeTwoLists(l1,l2.next);
return l2;
}
}

删除排序列表中的重复元素

1
2
3
4
5
6
7
8
9
10
11
var deleteDuplicates = function(head) {
let cur = head;
while(cur && cur.next){
if(cur.val == cur.next.val){
cur.next = cur.next.next;
}else{
cur = cur.next;
}
}
return head;
};

反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var reverseList = function(head) {
let prev = null;
let curr = head;
let cnext = null;
while (curr !== null) {
cnext = curr.next;
if (prev === null) {
curr.next = null;
} else {
curr.next = prev;
}
prev = curr;
curr = cnext;
}
return prev
};

迭代法

从前到后开始反转,我们需要三个指针,第一个指针指向当前头结点 head,第二个指针指向第二个节点 curP(当前结点),第三个指针为保存下一个节点的临时节点 temp。

1、反转顺序为,先保存下一节点。

2、然后让当前结点的指向前一节点。

3、最后移动当前结点到下一结点。(head 头节点一开始初始化指向 null)。

4、重复该循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
var reverseList = function(head){
if(head == null && head.next) return head;
let curNode = head.next;
head.next = null;
let temp = null;
while(curNode != null){
temp = curNode.next;
curNode.next = head;
head = curNode;
curNode = temp;
}
return head;
}

删除链表中的值

给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点。

返回删除后的链表的头节点。

注意:此题对比原题有改动

示例 1:

输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9.

示例 2:

输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点,那么在调用了你的函数之后,该链表应变为 4 -> 5 -> 9.

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
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} val
* @return {ListNode}
*/
var deleteNode = function(head, val) {
let current = head;
let prev = null;
while(current.val != val){
prev = current;
current = current.next;
}
if(current == head){
head = current.next;
}else{
prev.next = current.next;
}
return head;
};

链表中倒数第k个节点

输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。例如,一个链表有6个节点,从头节点开始,它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

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
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var getKthFromEnd = function(head, k) {
let length = 0;
let current = head;
let count = 0;
while(current){
length++;
current = current.next;
}
current = head;
while(count != length - k){
count++;
current = current.next;
}
return current;
};

平衡二叉树

给定一个二叉树,判断它是否是高度平衡的二叉树。

本题中,一棵高度平衡二叉树定义为:

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

3

/
9 20
/
15 7

返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

   1
  / \
 2   2
/ \

3 3
/
4 4

返回 false 。

核心思路:
1,从左到右递归树的节点,记录节点的最大深度
2,在记录节点的同时对该树的节点的左子树与右子树的最大深度做一次对比,如果差值超过1则返回false

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
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
function isNodeBalance(node){
if(!node) return 0;
let left = isNodeBalance(node.left);
let right = isNodeBalance(node.right);
if(left < 0 || right < 0){
// 短路机制,有一个子树不满足情况就返回
return -1;
}else{
if(Math.abs(left - right) > 1){
return -1;
}else{
return Math.max(left,right) + 1;
}
}
}
var isBalanced = function(root){
let ret = isNodeBalance(root);
if(ret >= 0) return true;
return false;
}

判断B树是否为A的子树

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
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} A
* @param {TreeNode} B
* @return {boolean}
*/
var isSubStructure = function(A, B) {
// 题目约定:约定空树不是任意一个树的子结构
if (!A || !B) {
return false;
}

return (
isSubTree(A, B) ||
isSubStructure(A.left, B) ||
isSubStructure(A.right, B)
);
};

function isSubTree(pRoot1, pRoot2) {
// B树遍历完了,说明B是A的子结构
if (!pRoot2) {
return true;
}
// A遍历完了,但是B还没有遍历完,那么B肯定不是A的子结构
if (!pRoot1) {
return false;
}

if (pRoot1.val !== pRoot2.val) {
return false;
}

return (
isSubTree(pRoot1.left, pRoot2.left) &&
isSubTree(pRoot1.right, pRoot2.right)
);
}

层序遍历二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//层序遍历
let levelOrderTraversal = function(root){
if(!root) return false; //头节点为空返回false
let result = []; //创建一个数组存放结果
let tree = []; //创建一个数组存放二叉树
tree.push(root); //先传入头节点
while(tree.length){ //当tree数组长度不为空
let node = tree.shift(); //将数组中的第一个节点放到node中
result.push(node.key); // 将node节点的值放入result中
if(node.left){ //如果node的左节点不为空,就将左节点压入tree数组中
tree.push(node.left);
}
if(node.right){ //如果node的右节点不为空,就将左节点压入tree数组中
tree.push(node.right);
}
}
return result;
}

之字形遍历

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
借助 level 变量标记层数,当 level 为偶数的时候,镜像翻转遍历结果。代码实现如下:
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function(root) {
if (!root) return [];
const queue = [root];
const res = [];
let level = 0; // 代表当前层数
while (queue.length) {
res[level] = []; // 第level层的遍历结果

let levelNum = queue.length; // 第level层的节点数量
while (levelNum--) {
const front = queue.shift();
res[level].push(front.val);
if (front.left) queue.push(front.left);
if (front.right) queue.push(front.right);
}
// 行号是偶数时,翻转当前层的遍历结果
if (level % 2) {
res[level].reverse();
}

level++;
}
return res;
};

二叉树的镜像

请完成一个函数,输入一个二叉树,该函数输出它的镜像。

例如输入:

4

/
2 7
/ \ /
1 3 6 9
镜像输出:

4

/
7 2
/ \ /
9 6 3 1

示例 1:

输入:root = [4,2,7,1,3,6,9]
输出:[4,7,2,9,6,3,1]

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
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var mirrorTree = function(root) {
if(!root) return root;

// 交换左右节点
let leftCopy = root.left;
root.left = root.right;
root.right = leftCopy;

// 对左右节点进行同样的操作
mirrorTree(root.left);
mirrorTree(root.right);

return root;
};

对称的二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isSymmetric = function(root) {
return isMirror(root,root);
};

var isMirror = function(node1,node2){
// 如果两个节点都是null的,势必是对称的
if(!node1 && !node2) return true;
// 如果其中一个为null,另一个不为null,则不是对称的
if(!node1 || !node2) return false;

return node1.val == node2.val && isMirror(node1.left,node2.right) && isMirror(node1.right,node2.left);
}

正则

正则表达式匹配

请实现一个函数用来匹配包含’. ‘和’‘的正则表达式。模式中的字符’.’表示任意一个字符,而’‘表示它前面的字符可以出现任意次(含0次)。在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串”aaa”与模式”a.a”和”abaca”匹配,但与”aa.a”和”ab*a”均不匹配。

示例 1:

输入:
s = “aa”
p = “a”
输出: false
解释: “a” 无法匹配 “aa” 整个字符串。

1
2
3
var isMatch = function(s, p) {
return new RegExp("^" + p + "$", "g").test(s);
};

表示数值的字符串

请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。例如,字符串”+100”、”5e2”、”-123”、”3.1416”、”0123”及”-1E-16”都表示数值,但”12e”、”1a3.14”、”1.2.3”、”+-5”及”12e+5.4”都不是。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var isNumber = function(s) {
var point = s.match(/\./g);
if((point && point.length>1) || !/\d/.test(s)){
return false;
}
s = s.replace(/^\s*|\s*$/g,""); //消除前后空格

if(!/e/i.test(s)){ //不含e的: 正负+整数+点+小数随意搭配
return /^[\+\-]?(\d*\.?\d*)$/i.test(s);
}else{ //含e的: 正负+ (整数+点+小数) 随意搭配 +e+ 正负可带可不带+ 数字一定要带
return /^[\+\-]?((\d+\.?\d*)|(\d*\.?\d+))e[\+\-]?\d+$/i.test(s)
}
return false;
};

简单排序

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
实现数组的sort((a,b) => a-b);
function Bubble_sort(arr){
let len = arr.length;
for(let p = len - 1; p >= 0;p--){
let flag = 0; //标记交换
for(let i = 0; i < p; i++){ //一趟冒泡
if(arr[i] > arr[i+1]){
swap(arr[i],arr[i+1]);
}
}
if(flag == 0) break; //全程无交换
}
}

最好情况:顺序 T = O(N)

最坏情况: 逆序 T = O(pow(N,2))

从上到下打印二叉树

从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。

例如:
给定二叉树: [3,9,20,null,null,15,7],

3

/
9 20
/
15 7

返回:

[3,9,20,15,7]

提示:

节点总数 <= 1000
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
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var levelOrder = function(root) {
//判断是否为空树
if(!root){
return [];
}
let data = [];
//将头节点放到队列中
let queue = [root];
while(queue.length != 0){
let first = queue.shift();
data.push(first.val);
first.left && queue.push(first.left);
first.right && queue.push(first.right);
}
return data;
};

其他

圆圈中最后剩下的数字

0,1,,n-1这n个数字排成一个圆圈,从数字0开始,每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

例如,0、1、2、3、4这5个数字组成一个圆圈,从数字0开始每次删除第3个数字,则删除的前4个数字依次是2、0、4、1,因此最后剩下的数字是3。

1
2
3
4
5
6
7
8
9
10
11
12
/**
* @param {number} n
* @param {number} m
* @return {number}
*/
var lastRemaining = function(n, m) {
let ans = 0;
for(let i = 2; i <= n; i++){
ans = (ans + m) % i;
}
return ans;
};

股票最大利润

假设把某股票的价格按照时间先后顺序存储在数组中,请问买卖该股票一次可能获得的最大利润是多少?

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
//此问题的实质就是找到两个差值最大的数,前提是小的在前,大的在后
//要把此问题的时间复杂度控制在O(n-1)并不难
let profits = 0;
let min = prices[0];
const len = prices.length;
for(let i = 1; i < len; i ++) {
min = Math.min(min, prices[i]);
profits = Math.max(profits, prices[i] - min);
}
return profits;
};

游戏必败问题

你和你的朋友,两个人一起玩 Nim 游戏:桌子上有一堆石头,每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。

你们是聪明人,每一步都是最优解。 编写一个函数,来判断你是否可以在给定石头数量的情况下赢得游戏。

示例:

输入: 4
输出: false
解释: 如果堆中有 4 块石头,那么你永远不会赢得比赛;
因为无论你拿走 1 块、2 块 还是 3 块石头,最后一块石头总是会被你的朋友拿走。

Nim 游戏

如果堆中石头的数量 nnn 不能被 444 整除,那么你总是可以赢得 Nim 游戏的胜利。

推理

让我们考虑一些小例子。显而易见的是,如果石头堆中只有一块、两块、或是三块石头,那么在你的回合,你就可以把全部石子拿走,从而在游戏中取胜。而如果就像题目描述那样,堆中恰好有四块石头,你就会失败。因为在这种情况下不管你取走多少石头,总会为你的对手留下几块,使得他可以在游戏中打败你。因此,要想获胜,在你的回合中,必须避免石头堆中的石子数为 4 的情况。

同样地,如果有五块、六块、或是七块石头,你可以控制自己拿取的石头数,总是恰好给你的对手留下四块石头,使他输掉这场比赛。但是如果石头堆里有八块石头,你就不可避免地会输掉,因为不管你从一堆石头中挑出一块、两块还是三块,你的对手都可以选择三块、两块或一块,以确保在再一次轮到你的时候,你会面对四块石头。

显然,它以相同的模式不断重复 n=4,8,12,16,…n=4,8,12,16,\dotsn=4,8,12,16,…,基本可以看出是 4的倍数。

1
2
3
4
5
6
7
/**
* @param {number} n
* @return {boolean}
*/
var canWinNim = function(n) {
return !!(n % 4);
};

url解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function parseUrl(url) {
let s = url.split('?')[0];
let str = url.split('?')[1];
let items = str.split('&');
let res = {};
let result = {};
let arr = s.split("://");
result['protocol'] = arr[0];
result['host'] = arr[1].substr(0, arr[1].indexOf('/'));
if(arr[1].indexOf('/') != arr[1].length - 1){
result['path'] = arr[1].substr(arr[1].indexOf('/'));
}
for (let i = 0, len = items.length; i < len; ++i) {
res = items[i].split('=');
result[res[0]] = res[1];
if(res[1].split('#').length > 1){
result[res[0]] = res[1].split('#')[0];
result['hash'] = res[1].split('#')[1];
}
}
return JSON.stringify(result).replace(/\"/g,"'");
}

读取一行输入:read_line(),输出一行:print(something),注意使用print函数输出时,末尾自动带有换行符,无需自己添加;

  • 读取size个字符:gets(size)
    将读取至多size个字符,当还未达到size个时如果遇到回车或结束符,会提前结束。回车符可能会包含在返回值中。
  • 输出信息:printsth(sth, …)
    往控制台输出sth,当有多个参数时,空格分隔;最后加回车。
  • 输出一行:print(sth, …) console.error(sth, …) console.debug(sth, …) console.info(sth, …) console.log(sth, …)
    往控制台输出sth,当有多个参数时,空格分隔;最后加回车。
  • 读取一个(长)整数:readInt()
    从控制台读取一个(长)整数。
  • 读取一个浮点型:readDouble()
    从控制台读取一个浮点型。
  • 读取一行输入:read_line()

Math

模拟 sqrt的整数部分

计算并返回 x 的平方根,其中 x 是非负整数。

由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

1
2
3
4
5
6
var mySqrt = function(x){
return Math.trunc(Math.sqrt(x));
}
//es6新增的去除一个数的小数部分,
非数值的话会先将其转为数值,
控制和无法截取整数的值,返回NaN

判断素数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function sushu(n){
if(n == 0 || n == 1){
return false;
}
if(n == 2){
return true;
}
for(var i = 2; i <= Math.round(Math.sqrt(n));i++){
if(n % i == 0){
return false;
}
}
return true;
}

遍历n内的素数

1
2
3
4
5
6
7
8
9
10
function getSushu(n){
//存放素数的数组
var arr = [];
for(var i = 2; i < n; i++){
if(sushu(i)){
arr.push(i);
}
}
console.log(...arr);
}

值加一

给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。

最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外,这个整数不会以零开头。

示例 1:

输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。

示例 2:

输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。

1
2
3
4
5
6
7
8
9
10
/**
* @param {number[]} digits
* @return {number[]}
*/
var plusOne = function(digits) {
let str = Number(digits.join('')) + 1;
let arr = str.toString().split('');
return arr;
};
//当数字位达32位及以上时,数值相加有问题
1
2
3
4
5
var plusOne = function(digits) {
return BigInt(BigInt(digits.join('')) + 1n).toString().split('')
};
//利用BigInt解决数字边界问题
//要创建BigInt,只需在整数的末尾追加n即可

递增求和

1
2
3
var sumNums = function(n) {
return (1+n)*n/2;
};

1+2+...+n ,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。

1
2
3
4
5
6
7
8
9
10
var sumNums = function(n) {
return multi(n, n+1, 0) >> 1
};

function multi(a, b, sum) {
if (b === 0) return sum

if (b & 1) return multi(a, b-1, sum + a)
return multi(a + a, b >> 1, sum)
}

斐波那契数列

写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项。斐波那契数列的定义如下:

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例 1:

输入:n = 2
输出:1

示例 2:

输入:n = 5
输出:5

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
/**
* @param {number} n
* @return {number}
*/
var fib = function(n){
// 1.非常普通,没有优化的递归
//优点:非常容易想到,fib在不加额外参 数且不引入外部变量的情况下只能这么调用自身
//缺点:fib会重复计算之前的项,计算结果是一次性的,极其浪费时间和空间,在本题必定超时,完全无法通过
/*
if(n<=1) return n;
return (fib(n-1) + fib(n-2)) % 1000000007;
*/
// 2.普通的尾递归+ES6尾调用优化解法
// 优点:不创建心得栈帧,现有栈帧被重复利用,不会爆栈,性能比未经优化的递归明显提高
// 缺点:需要反复清除栈帧的数据,性能不如下面的循环解法。
/* 'use strict';
function f(n,a=1,b=1){
if(n <= 1) return n;
if(n == 2) return b;
return f(n-1,b,(a+b)%100000007); //最后一步调用自身,将数据处理的步骤变成参数的变化
}
return f(n);
*/
//4.很好的循环计算解法

//优点:每一次计算结果都能得到利用,易于理解,只保存前两个计算结果,性能最优
//缺点:没有明显的缺点,在本题中记得看清题目中取模的要求

//注:其他题解有提到,但这题不需要用到新的BigInt类型,取模就是为了防止结果溢出,
//而且中间计算结果也达不到 Number.MAX_SAFE_INTEGER (9007199254740991) 的量级
//变量c不是必要的,可以直接用代数方法或ES6解构赋值做进一步优化,这种循环解法也可以看做是一种动态规划解法


if(n<=1)return n;
let a=b=1,c=0;
while(n-->0){

a = b;
b = c;
c = (a + b) % 1000000007;

}
return c;
}

青蛙跳台阶问题

题目:一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个n级的台阶总共有多少种跳法?

答题思路

  1. 如果只有1级台阶,那显然只有一种跳法
  2. 如果有2级台阶,那么就有2种跳法,一种是分2次跳。每次跳1级,另一种就是一次跳2级
  3. 如果台阶级数大于2,设为n的话,这时我们把n级台阶时的跳法看成n的函数,记为f(n),第一次跳的时候有2种不同的选择:一是第一次跳一级,此时跳法的数目等于后面剩下的n-1级台阶的跳法数目,即为f(n-1),二是第一次跳二级,此时跳法的数目等于后面剩下的n-2级台阶的跳法数目,即为f(n-2),因此n级台阶的不同跳法的总数为f(n) = f(n-1) + f(n-2),不难看出就是斐波那契数列

数学函数表示如下f(x)=\left\{ \begin{aligned} & 0 & n=0 \\ & 1 & n=1 \\ & 2 & n=2 \\ & f(n-1)+f(n-2) & n > 2 \end{aligned} \right.

1
2
3
4
5
6
7
8
9
var numWays = function(n){
if( n<= 1) return 1;
let dp = [1,1,2];
const ModNum = 1e9+7;
for(let i = 2;i <= n;i ++){
dp[i] = (dp[i - 1] + dp[i - 2]) % ModNum;
}nx
return dp[n];
}

vue小技巧

v-for设置键值缘由
1
2
3
4
5
6
7
8
9
<!--模板部分-->
<div id="app">
<div v-for="item in arr">
{{item}}
<input/>
</div>

<button @click="deleteData">删除第二个元素</button>
</div>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// js 部分
new Vue({
el: '#app',
data() {
return {
arr: [1,2,3]
}
},
methods:{
deleteData() {
this.arr.splice(1,1)
}
}
})

若要删除第二个元素,不使用key值或使用索引值作为key的情况都是一样。即索引值正确,但输入框前面的数字显示不正确。

img

而使用唯一值作为key值则是正确的。为什么v-for需要设置key,原因很简单。 对比数组 [1,2,3]和[1,3],我们很容易发现删掉了2,但是计算机不是这样的逻辑:

  1. 计算机对比新旧数组,发现1 === 1,保持不变。
  2. 然后再对比2,发现2变成了3,便直接将2改为3,原来第二行的input元素可以复用。
  3. 然后再对比3和undefined,发现3被删了,索引把第三行的元素删除。

那么为什么不能用索引作为key呢? 当删掉[1,2,3]中的2之后,数组的长度由3变成了2,那么原来数字3的索引就变成了数字2的索引了。

  1. 计算机对比key为0的值,发现都是1,保持不变
  2. 计算机对比key为1的值,发现从2变成了3,元素复用, 修改元素上面的文字
  3. 计算机对比key为2的值,发现被删掉了,所以删掉第三行元素

而对于使用id作为key,那么每条数据都有了唯一的标识,当删掉[{id:'1',value: 1},{id: '2',value: 2}, {id: '3', value:3}]中的第二个,整个过程如下

  1. 计算机取出新数据第一项的id,然后在原来数据里面寻找,发现存在相同id的数据,而且数据没有变化,所以保持不变
  2. 计算机继续取第二项的id,发现是3,然后从原来数据里面也找到了3,所以3保留
  3. 这时候旧数据里面剩了id为2的数据,而新的里面没有了,所以删掉。
vue的数据必须返回一个函数

假设我们现在开发了一个组件,组件上面的data是一个普通的对象,那么当我们实例化多个组件的时候,所有的实例将共享引用同一个数据对象,任何一个实例对数据的修改都会影响到其他实例。而将组件上面的数据定义为一个函数之后,当实例化多个组件的时候,每个实例通过调用 data 函数,从而返回初始数据的一个全新副本数据对象,这时候就避免了对象引用。

学习vuex

Vuex概述

Vuex实现组件全局状态(数据)管理的一种机制,可以方便的实现组件间的数据共享。

组件间共享数据的方式

父向子传值:v-bind属性绑定

子向父传值:v-on事件绑定

兄弟组件间共享数据:EventBus

  • $on 接受数据的那个组件
  • $emit 发送数据的那个组件
vuex的优点
  1. 能够在vuex中集中管理共享的数据,易于开发和后期维护。
  2. 能够高效的实现组件间的数据共享,提高开发效率。
  3. 存储在vuex中的数据都是响应式的,能够实时保持数据与页面的同步。
vuex的使用
  1. 安装

    cnpm i vuex --save

  2. 导入vuex包

    1
    2
    import Vuex from 'vuex'
    Vue.use(Vuex);
  3. 创建store对象

    1
    2
    3
    4
    const store = new Vuex.Store({
    // state 中存放的就是全局共享的数据
    state: { count: 0 }
    })
  4. 将store对象挂载到vue实例中。

    1
    2
    3
    4
    5
    6
    7
    new Vue({
    el: '#app',
    render: h => h(app),
    router,
    // 所有组件都可以从store中获取全局的数据了
    store
    })

另一种方式

1
2
3
4
5
6
7
8
9
10
11
12
13
// store.js文件
import Vue from 'vue'
import Vuex from 'vuex'

Vue.use(Vuex)

export default new Vuex.Store({
state: {
count: 0
},
mutations: {},
actions: {}
})
1
2
3
4
5
6
7
8
9
10
11
12
// main.js文件
import Vue from 'vue'
import App from './App.vue'
import store from './store'


Vue.config.productionTip = false

new Vue({
store,
render: h => h(App),
}).$mount('#app')

在组件中通过this.$store.state操作数据。

State

State提供唯一的公共资源,所有共享的数据都要统一放到Store的State中进行存储。

1
2
3
4
// 创建store数据源,提供唯一的公共数据
const store = new Vuex.Store({
state: { count: 0 }
})

组件访问State中数据的第一种方式:

1
this.$store.state.全局数据名称

组建访问State中的数据的第二种方式:

1
2
// 1.从vuex中按需导入mapState函数
import { mapState } from 'vuex'

通过刚才导入的mapState函数,将当前组件需要的全局数据,映射为当前组件的computed计算属性:

1
2
3
4
// 2.将全局数据映射为当前组件的计算属性
computed: {
...mapState(['count'])
}
Mutation

vuex不推荐直接在组件中通过$store修改state里面的值,推荐使用mutation变更Store中的数据。

通过这种方式虽然操作起来繁琐一些,但是可以集中监控所有数据的变化。

1
2
3
4
5
6
7
8
9
10
11
12
// 定义Mutation
const store = new Vuex.Store({
state: {
count: 0
},
mutations: {
add(state,step){
//变更状态
state.count += step;
}
}
})
1
2
3
4
5
6
7
8
// 触发mutation
methods: {
handle(){
// commit的作用是触发mutation中的函数
//触发mutation的第一种方式,携带数值3的参数
this.$store.commit('add',3)
}
}

触发mutations的第二种方式:

1
2
// 1.从vuex中按需导入mapMutations函数
import { mapMutations } from 'vuex';

通过刚才导入的mapMutations函数,将需要的mutations函数映射为当前组件的methods方法:

1
2
3
4
// 2.将指定的mutations函数映射为当前组件的methods函数
methods: {
...mapMutations(['add','addN'])
}

注意:在mutations中不能使用异步函数,否则页面的数据变化了,vuex中的调试器中的数据没变。

Action

Action用于处理异步任务。

如果通过异步操作变更数据必须通过Action,而不能使用Mutation,但是在Action中还是需要通过触发Mutation的方式间接变更数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 定义Action
const store = new Vuex.Store({
mutations: {
add(state){
state.count++;
}
},
actions: {
addAsync(context){
setTimeout(() => {
context.commit('add')
},10000);
}
}
})
1
2
3
4
5
6
// 通过dispatch触发actions的函数
methods: {
handler(){
this.$store.dispatch('addAsync')
}
}
Getter

Getter用于对Store中的数据进行加工处理形成新的数据。

  1. Getter可以对Store中已有的数据加工处理之后处理之后形成新的数据,类似Vue的计算属性。
  2. Store中数据发生变化,Getter的数据也会跟着变化。
1
2
3
4
5
6
7
8
9
10
11
// 定义Getter
const store = new Vuex.Store({
state: {
count: 0
},
getters: {
showNum: state => {
return '当前最新的数量是【' + state.count +'】'
}
}
})

使用getters的第一种方式:

this.$store.getters.名称

使用getters的第二种方式:

1
2
3
4
import { mapGetters } from 'vuex'
computed: {
...mapGetters(['showNum'])
}

getter不会修改state中的数据,只进行包装作用。

vuex小项目

1
2
vue create vuex-todo
cnpm i vuex axios ant-design-vue -S

同源策略

跨域方式实现原理

前后端请求经常需要跨域,拿什么是跨域,什么是同域?

同源策略

同源策略是跨越问题的源头,在客户端编程语言中,如javascript和ActionScript,同源策略是一个很重要的安全理念,他的目的是为了保证用户信息的安全,防止恶意的网站窃取数据。如:A网站是一家银行,用户登录后又去浏览其他网站,若其他网站可读取A网站的Cookie,信息可能会泄露。若Cookie包含隐私(比如存款总额),这些可能会泄露。更可怕的是,Cookie往往用来保存用户的登录状态,如果用户没有退出登录,其他网站就可以冒充用户,为所欲为。因为浏览器同时还规定,提交表单不受同源策略的限制。由此可见,“同源策略”是必须的,否则Cookie可以共享,互联网就毫无安全可言。

同源策略是一种约定,他是浏览器最核心也是最基本的安全功能,如果缺少同源策略,则浏览器的正常功能可能都会受到影响。可以说web是创建在同源策略基础上的。浏览器只是针对同源策略的一种实现。

所谓同源是指,域名,协议,端口号都相同。

当一个浏览器的两个tab页中分别打开百度和谷歌的页面,若浏览器的百度tab执行一个脚本时检查出这个脚本是同源时才会被执行。若非同源,那么在请求数据时,浏览器会在控制台中报一个异常,提示拒绝访问。

同源策略是浏览器的行为,是为了保护本地数据不被JavaScript代码获取回来的数据污染,因此拦截的是客户端发出的请求回来的数据接收,即请求发送了,服务器响应了,但是无法被浏览器接收。

非同源

url的组成

图片描述

同源策略限制内容有:

  • Cookie、LocalStorage、IndexedDB 等存储性内容
  • DOM 节点
  • AJAX 请求发送后,结果被浏览器拦截了

补充:同源策略还应该对一些特殊情况做处理,比如限制file协议下脚本的访问权限。本地的HTML文件在浏览器中是通过file协议打开的,如果脚本能通过file协议访问到硬盘上其它任意文件,就会出现安全隐患,目前IE8还有这样的隐患。

但是有三个标签是允许跨域加载资源:

  • <img src=XXX>
  • <link href=XXX>
  • <script src=XXX>

特别说明两点:

第一:如果是协议和端口造成的跨域问题“前台”是无能为力的。

第二:在跨域问题上,仅仅是通过“URL的首部”来识别而不会根据域名对应的IP地址是否相同来判断。“URL的首部”可以理解为“协议, 域名和端口必须匹配”。

跨域并不是请求发不出去,请求能发出去,服务端能收到请求并正常返回结果,只是结果被浏览器拦截了你可能会疑问明明通过表单的方式可以发起跨域请求,为什么 Ajax 就不会?因为归根结底,跨域是为了阻止用户读取到另一个域名下的内容,Ajax 可以获取响应,浏览器认为这不安全,所以拦截了响应。但是表单并不会获取新的内容,所以可以发起跨域请求。同时也说明了跨域并不能完全阻止 CSRF,因为请求毕竟是发出去了。

作者:浪里行舟
链接:https://juejin.im/post/5c23993de51d457b8c1f4ee1
来源:掘金
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

跨域方式

JSONP

JSONP是JSON with Padding的简写,是应用JSON实现服务器与客户端跨域通信常用的方法,最大特点是简单实用,老式浏览器全部支持,服务器改造非常小。但是只支持get方法,且易遭受XSS攻击。

它的基本思想是,网页通过添加一个

|