0%

1130. Minimum Cost Tree From Leaf Values

难度: Medium

刷题内容

原题连接

内容描述

给你一个正整数数组 arr,考虑所有满足以下条件的二叉树:

每个节点都有 0 个或是 2 个子节点。
数组 arr 中的值与树的中序遍历中每个叶节点的值一一对应。(知识回顾:如果一个节点有 0 个子节点,那么该节点为叶节点。)
每个非叶节点的值等于其左子树和右子树中叶节点的最大值的乘积。
在所有这样的二叉树中,返回每个非叶节点的值的最小可能总和。这个和的值是一个 32 位整数。

示例 1:

1
2
3
4
5
6
7
8
9
10
输入:arr = [6,2,4]
输出:32
解释:
有两种可能的树,第一种的非叶节点的总和为 36,第二种非叶节点的总和为 32。

24 24
/ \ / \
12 4 6 8
/ \ / \
6 2 2 4

提示:

  • 2 <= arr.length <= 40
  • 1 <= arr[i] <= 15
  • 答案保证是一个 32 位带符号整数,即小于 2^31

解题方案

思路
- 时间复杂度: O(N)

- 空间复杂度: O(N)

执行用时 :60 ms, 在所有 javascript 提交中击败了**92.86%**的用户

内存消耗 :33.5 MB, 在所有 javascript 提交中击败了**100.00%**的用户

代码:

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[]} arr
* @return {number}
*/
var mctFromLeafValues = function(arr) {
if (!arr.length || arr.length < 2) {
return 0
}
let res = 0;
let stack = [];
stack.unshift(Number.MAX_VALUE);
arr.forEach(num => {
while (stack[0] <= num) {
let mid = stack.shift()
res += mid * Math.min(stack[0], num);
}
stack.unshift(num);
})

while (stack.length > 2) {
res += stack.shift() * stack[0]
}
return res;
};

Node.js

特点

  • 属于单线程逻辑处理
  • 不会产生死锁
  • 适合做基于社交网络的大规模WEB应用

对比js

​ js运行在客户浏览器,存在多种解释器,有代码兼容性问题;Node.js运行在服务器,只有V8引擎一种解释器,不存在代码兼容性问题

​ 两者都有相同内置对象和自定义对象,不同的宿主对象

​ js用于开发就浏览器端的交互效果,Node.js用于服务器端功能开发,例如数据库的访问,其他服务器得到调用

运行方式

​ 脚本模式:node 文件的路径 回车

​ 交互模式:node 回车 进入交互模式

​ 退出:两次ctrl+c/ctrl+d/.exit

全局对象

​ global对象

​ (1),检测一个变量或函数是否为全局的

​ (2),在交互模式下属于全局作用域,里面的变量是和函数都是全局的

​ (3),在脚本模式下不属于全局作用域,里面的变量和函数都不是全局的,可以防止全局污染

​ console对象

​ console.log(1);//输出日志 console.info(2);//输出消息

​ console.warn(3);//输出警告 console.error(4);//输出错误

​ console.time()开始计时 console.timeEnd()结束计时

​ 开始计时和结束计时提供的值要保持一致

​ process对象

​ 进程:计算机在运行软件的时候,都会产生相应的进程

1
2
3
4
5
6
7
8
9
process.arch	查看当前CPU的架构

process.platfrom 查看当前的操作系统

process.version 查看当前Node.js版本

process.pid 查看当前进程的编号

process.kill(编号) 结束指定进程

​ Buffer缓冲区

1
2
3
4
5
6
7
缓冲区,是内存中临时存储的区域

let buf = Buffer.alloc(4,'root');

创建Buffer,设置大小为4个字节,并填充数据,每个字节占3个字节

String(buf)/buf.toString();//将Buffer数据转为字符串

​ 定时器函数

1
2
3
4
5
6
7
//一次性定时器:	setTimeout(回调函数,时间/毫秒);
//清除定时器: clearTimeout(定时器的变量);
//周期性定时器: setInterval(回调函数,时间/毫秒) 每隔一段时间,调用一次函数
//清除定时器 clear Interval(定时器的变量);
//立即执行定时器
//开启setImmediate(回调函数) 清除clearImmediate(timer)
//开启process.nextTick(回调函数) 宏任务

模块

​ 每文件是一个模块,每一个模块都是一个独立的功能

​ 一个模块引入其他的模块

​ 一个模块也可以被其他的模块引入

1
2
3
4
5
6
7
require( ) //是一个函数,用于引入其他的模块

module.exports //导出的对象,默认是一个空对象,如果要导出哪些内容需要放入到这个对象

__dirname: //是一个局部变量,当前模块 的绝对路径

__filename: //是一个叫局部变量,当前模块的绝对路径+模块名称
模块分类
1.自定义模块,第三方模块,核心模块
以路径开头 不以路径开头
文件形式 require(‘./文件名.js’)用于引入自定义模块 require(‘querystring’)用于引入官方提供的核心模块
目录形式 require(‘./文件名’)首先会找到目录下寻找package.json文件中main对应的文件,如果找不到则会寻找index.js require(‘tao’)首先会找到同一级目录下的node_modules目录中寻找tao,如果没找到会一直往上一级的node_modules目录中寻找;用于引入第三方模块
2.包和npm

​ CommonJS:是一种规范,制定了Node.js的模块化概念

​ 包:通常指的是目录模块

​ npm:是用于管理包的工具模块

​ 网址:https://www/npmjs.com

​ 使用npm:npm init -y 生成package.json文件,作为项目文件,可以用于记录下载安装的包的信息

​ 下载包:npm install 包的名称 ;下载安装指定的包,将包放入到node_modules目录中,如果目录不存在会先创建,同时生成package-lock.json,用于记录所有包的版本号

​ npm install 自动下载package.json和package-lock.json中记录的包

​ 下载或运行其他版本文件:npx -p node@8 node 拖拽文件 下载指定版本的Node.js运行文件,运行完以后再把下载的Node.js删除

3.查询字符串模块(querystring)

​ 查询字符串:浏览器向WEB服务器发送请求,传递的数据的一种方式,位于浏览器的地址栏中

keyword=笔记本&enc=utf-8

查询字符串模块用于操作查询字符串的工具

​ parse( )将查询字符串解析为对象

4.URL模块

​ URL:统一资源定位,互联网上的任何资源都有对应的URL

​ new URL( ) 将一个URL解析为对象,获取URL的各个部分

5.文件系统模块

​ 用于操作服务器端的文件,例如文件的读取,写入,删除……

​ 文件分为目录形式和文件形式 同步加Sync

​ (1)fs.statSync(文件的路径) / fs.stat(文件的路径,回调函数)

​ 查看是否为文件形式 isFile() 返回true或false

​ 查看是否为目录文件 isDirectory() 返回true或false

​ (2)创建目录 fs.mkdirSync(‘目录的路径’)

​ (3)移除目录 fs.rmdirSync(‘目录的路径’) //只能移除空目录

​ (4)读取目录 fs.readdirSync(‘../上级目录文件名’) / readdir(目录的路径,回调函数)

​ (5)覆盖写入文件 writeFileSync(文件的路径,数据) / writeFile(文件的路径,数据,回调函数)

​ 如果文件不存在,则先创建文件然后写入数据

​ 如果文件已经存在,会清空文件内容然后写入文件

​ (6)追加写入文件 appendFileSync(文件的路径,数据) / appendFile(文件的路径,数据,回调函数)

​ 如果文件不存在,则先创建文件然后写入文件

​ 如果文件已经存在,会在文件的末尾追加写入数据

​ (7)读取文件数据 readFileSync(文件的路径) / readFile(文件的路径,回调函数)

​ 读取的数据结果为buffer数据格式

​ (8)删除文件 unlinkSync(文件的路径) / unlink(文件的路径,回调函数)

​ fs模块

​ (9)判断文件是否存在 existsSync(文件/目录) 存在–>true 不存在–>false

​ (10)拷贝文件 copyFileSync(源文件路径,目标文件路径) / copyFile(源文件路径,目标文件路径,回调函数)

6.*同步和异步

​ 同步:在主程序中执行,会阻止后续代码的执行,通过返回值来获取结果

​ 异步:在一个独立的线程执行,不会阻止主程序后续代码的执行,将结果以会低矮函数的形式放入到事件队列

文件流

1
2
3
4
5
6
7
createReadStream()	创建可读取的文件流

createWriteStream() 创建可写入的文件流

on(事件名称,回调函数) 添加事件,事件名称是固定的字符串,一旦坚挺到事件呼呼自动执行回调函数

pipe()管道,可以将读取的流添加到写入的流

HTTP协议

​ 浏览器和WEB服务器之间的通信协议

​ (1)通信头信息

1
2
3
4
5
Request URL:请求的服务器端的资源

Request Method: 请求的方法,对资源的操作方式 get/post/detele/put

Status Code: 响应的状态码

​ 100:接受到了请求,还没有做出响应

​ 200:成功的响应

​ 300:响应的重定向,跳转到另一个url

​ 400:客户端错误

​ 500:服务器错误

​ (2)响应头信息 response

1
2
Content-Type:响应的内容类型   text/html; charset=UTF-8
Location:设置要跳转的url

​ (3)请求头信息 request

​ (4)请求主题

​ 显示传递的数据,不是每一次都出现

HTTP模块

​ 可以用来创建WEB服务器

(1)创建服务器

1
2
3
4
5
引入HTTP模块const http = require('http');

创建WEB服务器const app = http.createServer();

设置端口app.listen(80,()=>{ });

(2)接收请求作出相应

1
2
3
4
5
6
7
8
9
10
//给服务器添加事件
app.on('request',(req,res)=>{
req 请求对象
req.url 获取请求的url,显示的端口号后的部分,
req.method 获取请求的方法
res 响应对象
*res.writeHead(状态码,头信息) 设置响应的状态码和头信息,第二个参数可以为空
*res.write() 设置响应到浏览器的内容
*res.end() 结束并发送响应
})

框架

​ 框架:是一整套解决方案,简化了已有的功能,添加了之前没有的功能

​ Node.js框架:express,koa,egg

​ 1.express框架

​ express是基于 Node.js 平台,快速、开放、极简的 Web 开发框架

​ 属于是第三方模块,需要先下载安装 npm install express

(1)创建WEB服务器
1
2
3
引入express模块	const express = require('express');
创建WEB服务器 const app = express();
设置端口 app.listen(8080,()=>{ })

(2)路由

​ 根据请求的URL和请求的方法来做出特定的响应

​ 包含三部分:请求的URL,请求的方法,回调函数

1
2
3
4
req请求对象
req.url 获取请求的URL
req.method 获取请求的方法
req.query 获取get传递的数据。格式为对象

1
2
3
4
5
res响应对象
res.send( ) 设置响应的内容并发送
res.redirect( ) 设置响应的重定向并发送
res.sendFile( ) 设置响应的文件并发送
//以上三个方法在路由中只能执行一次

数据传递的方式

名称 格式 获取
get方式 http://127.0.0.1:8080/mysearch?keyword=传递的值 req.query
post方式 URL中不可见,在http协议的请求主体 req.on(‘data’,(chunk)=>{chunk.toString() 需要使用查询字符串解析为对象})
路由传参 http://127.0.0.1:8080/package/mysql app.get(‘/package/:pname’,(req,res)=>{req.params})
(3)路由器

​ 路由器可以统一管理路由,还额可以给一组路由器添加统一的前缀

1
2
3
//路由器
const r = express.Router(); 创建路由器对象
module.exports = r; 导出路由器对象

​ WEB服务器

1
2
//引入
app.use('/produck',perduckRouter) 挂载路由器到WEB服务器

中间件

​ 拦截对服务端的请求,也可以做出响应

​ express下中间件分为应用级中间件,路由级中间件,内置中间件,第三方中间件,错误处理中间件

​ (1)应用级中间件

​ 也成为自定义中间件,本质上就是一个函数

​ app.use(URL,回调函数)

​ app.use(回调函数)

​ (2)路由级中间件

​ app.use(拦截的url,回调函数)

​ (3)内置中间件

​ 托管静态资源

​ 客户端请求静态资源(html,css ,js,图像…)不在创建路由,让客户端自动到指定的目录下查找

​ app.use(express.static(‘要托管的目录’))

​ (4)第三方中间件

​ 第三方中间件以第三方模块的形式出现,需要先下载安装

1
2
3
4
5
6
7
8
//1.引入中间件
const bodyParser = require('body-Parser')
//2.使用中间件,将所有post请求的数据解析为对象
app.use(bodyParser.urlencoded({
extended:false //false 不使用第三方的查询字符串模块,就会使用核心querystring
}))
//3.在路由中获取数据,格式为对象
req.body

MySQL模块

​ Node.js下,专门用于操作MySQL数据库的第三方模块

​ node install mysql 下载安装

​ mysql命令

1
2
3
4
5
6
7
mysql -uroot //登录数据库
mysql.exe -h127.0.0.1 -p3306 -uroot -p
mysql -uroot<拖拽脚本 //
insert into 表名 values(.....);
delete from 表名 where 列名=值;
update 表名 set 列名=修改的值,....where 列名=值;
select * from 表名;

SQL注入:在让用于提供的值中,并拼接了其他的SQL注入。

占位符( ? ):先对数据进行过滤,过滤完以后在替换占位符

1
2
3
4
5
6
7
8
9
10
mysql.createConnection({
host:'127.0.0.1',
port:'3306',
user:'root',
password:'',
database:'xz', //数据库名
connectionLimit:15 //默认15
}) //创建连接对象
connect() //测试连接
query(SQL命令,要过滤的数据,回调函数)

连接池

​ 开始的时候创建一批的链接,可以被反复的使用,用完后会归还

1
2
mysql.createPool( ) 创建连接池对象
query( ) 执行SQL命令

RESTful接口

​ 接口:后端为前端提供的动态资源(对数据的增删改查)

​ RESTful:是一种接口的设计规范

​ ①URL

1
2
3
4
5
6
7
8
9
员工资源 
http://127.0.0.1:8080 /v1 /emps 多个资源
版本 资源名称(复数形式)
http://127.0.0.1:8080 /v1 /emps /5 单个资源

编号
http://127.0.0.1:8080 /v1 /login 对资源特殊操作

登录

​ ②请求的方法

​ 对资源的操作方式

1
2
3
4
get		获取资源
delete 删除资源
put 修改资源
post 新建资源

​ ③过滤数据

1
2
3
//针对于多个资源的操作
http://127.0.0.1:8080/v1/emps?pno=1&count=9
//通过分页过滤的数据 当前页码 每页数据量
1
2
http://127.0.0.1:8080/v1/emps?*salary1=6000&salary2=8000*
//过滤一组区间的数据

​ ④返回结果

​ 格式为json对象:字符串形式的对象,实姓名必须用双引号,属性值是字符串也得是双引号

​ 包含状态码(人为规定),消息,数据

正则表达式

1
2
3
4
5
6
7
test( )	检测字符串是否符合规则	

​ replace(规则,替换的字符串) 查找并替换

​ search(规则) 查找符合规则的第一个,返回下标,找不到返回-1

​ match(规则) 查找符合规则的所有,返回数组

​ 修饰符

1
g - global 全局查找			i - ignore 忽略大小写

Long Term Cache

使用 webpack 等打包器进行打包时,每个资源都可生成一个带有 hash 的路径。如

  • build/main.071b73.js
  • build/main.94474e.css
  • build/logo.18bac8.png

此处对添加 hash 的资源设置永久缓存,可大幅度提高该网站的缓存能力,从而大幅度提高网站的二次加载性能。

通过在服务器端/网关端对资源设置以下 Response Header,进行强缓存一年时间,称为永久缓存,即 Long Term Cache

1
Cache-Control: public,max-age=31536000,immutable

而当源文件内容发生变更时,资源的 hash 发生变化,生成新的可永久缓存的资源地址。

因此在实践中,可对打包处理后带有 hash 资源的所有文件设置永久缓存。

如果前端通过 docker/k8s/helm 进行部署,可由团队人员自行在构建 nginx 镜像时进行添加响应头字段。此处可作为前端性能优化的 kpi/okr。

可在浏览器控制台 Network 中查看响应头来验证所属项目是否已成功添加永久缓存。

image

一个问题与更强的永久缓存

假设有两个文件: index.jslib.js,且 index 依赖于 lib,其内容如下。

index.js

1
2
// index.js
import('./lib').then(o => console.log(o))

lib.js

1
export const a = 3

由 webpack 等打包器打包后将会生生两个 chunk (为了方便讲解,以下 aaaaaa 为 hash 值)

  • index.aaaaaa.js
  • lib.aaaaaa.js

问: 假设 lib.js 文件内容发生变更,index.js 由于引用了 lib.js,可能包含其文件名,那么它的 hash 是否会发生变动

答: 不一定。打包后的 index.js 中引用 lib 时并不会包含 lib.aaaaaa.js,而是采用 chunkId 的形式,如果 chunkId 是固定的话,则不会发生变更。

1
2
3
4
5
// 打包前
import('./lib')

// 打包后,201 为固定的 chunkId (chunkIds = deterministic 时)
__webpack_require__.e(/* import() | lib */ 201)

在 webpack 中,通过 optimization.chunkIds 可设置确定的 chunId,来增强 Long Term Cache 能力。

1
2
3
4
5
{
optimization: {
chunkIds: 'deterministic'
}
}

设置该选项且 lib.js 内容发生变更后,打包 chunk 如下,仅仅 lib.js 路径发生了变更。

  • index.aaaaaa.js
  • lib.bbbbbb.js

使用 CDN 加速你的网站

前端面试过程中有一个万能的面试题,当他们想不到还有什么面试题要问的时候,就会问这个: 如何优化你们的网站性能。

而其中 CDN 就是其中一条,而在我看来,它是最重要的一条: 配置CDN可以使网站性瞬时得到质的提升,即使静态资源打包体积过大,并且缓存策略很差。

那什么是 CDN 呢?

CDN,全称 Content Delivery Network,内容发布网络。将网站的内容发布到最接近用户的边缘网络,使用户可以以更低的网络时延接收到网站内容,避免网络拥塞状况,提高用户访问网站的响应速度。

image

CDN 原理简述

简单来说,CDN 可以理解为 负载均衡服务器 + 缓存代理服务器,虽然实际原理以及实现算法会复杂很多。

image

如上图所示,当我们提及 CDN 时,特别是运维人员或者开发负责人时配置 CDN 时,我们可以把 CDN 划分为三个主体:

  • 用户,即你我他,每一个正在使用该网站的人
  • CDN,可理解为一个缓存节点,在当前节点可以快速响应给用户内容
  • 源站,内容的原始站点,CDN 上缓存未击中后,会回源到源站

那用户请求网站内容的具体步骤是什么?根据上图所示:

  1. 用户请求网站内容时,通过 Local DNS 进行域名解析
  2. Local DNS 请求 CDN 专用的 DNS 权威服务器 (因此当选择某家 CDN 厂商时,有时需要去域名提供商手动调整域名的 DNS 权威服务器)
  3. CDN专用DNS服务器负责负载均衡,为用户选择一个合适的 CDN 节点,作为目标节点
  4. CDN专用DNS服务器向用户返回目标节点 IP 地址
  5. 用户向目标节点的 IP 发起请求
  6. 目标节点 IP 地址如果没有响应内容,则向源站发送请求
  7. 目标节点从源站获取到内容,缓存,并返回给用户

另外由于 CDN 上存在多个节点为你提供服务,并且隐藏了源站,因此你的网站安全性大大提高,更好地避免了由于一些恶意攻击而导致源站的服务器集群宕机。

如何查看网站是否上了 CDN

如果你的网站静态资源上了 CDN,你的网络内容会被 CDN 的负载均衡系统分发到最接近用户的边缘节点。负载策略的策略可能会涉及到节点的,节点的拥塞成都,节点的运营商是否与用户网络一致,

假设当你在北京访问你的网站时,DNS 会解析你的网络内容到北京的 IP 节点,你在上海访问你的网站时,DNS 会解析到上海的 IP。而且为了解决拥塞,还会对网站内容负载均衡到多个 IP 地址。

那么此时问题就很简单了,如果你想知道某一网站是否上了 CDN,那就直接对域名进行 DNS 解析。

以下对知乎的静态资源所在的域名 static.zhihu.com 为例,使用 dig 命令进行 DNS 解析:

1
2
3
4
5
6
7
8
9
10
$ dig static.zhihu.com +short
static.zhihu.com.w.alikunlun.com.
183.201.230.244
183.201.230.248
183.201.230.240
183.201.230.242
183.201.230.245
183.201.230.241
183.201.230.246
183.201.230.243

从以上命令可以看到知乎采用了 CDN,并且根据 CNAME 记录可知采用了阿里的 CDN 服务: 对域名 CNAME 到 *.w.alikunlun.com

为你的网站配置 CDN

由于国内大部分网站采用阿里的CDN,这里以CDN为例讲解如何配置 CDN。详细配置可以参考

如何在网站上更好地利用 CDN

如果你需要更好地利用 CDN 提高网站性能,你不需要了解 CDN 的原理,但你更需要更好地了解 HTTP Cache。了解了 http 缓存的运作后,才能更好地充分利用缓存来降低网站的时延。

以下是 CDN 的缓存配置策略:

image

我们从图中可以获知:

  1. 源站和CDN(缓存服务器)均可以配置缓存策略
  2. 如果CDN没有配置缓存策略,则以源站缓存策略为主

而就我在多个项目的实践经验而言,很少为 CDN 专门配置缓存策略,因此如果想要更好地利用 CDN,则需要

为你的源站配置一个不错的缓存策略

更好的缓存策略

image

image

此时我们可以对资源进行分层次缓存的打包方案,这是一个建议方案:

  1. webpack-runtime: 应用中的 webpack 的版本比较稳定,分离出来,保证长久的永久缓存
  2. react/react-dom: react 的版本更新频次也较低
  3. vendor: 常用的第三方模块打包在一起,如 lodashclassnames 基本上每个页面都会引用到,但是它们的更新频率会更高一些。另外对低频次使用的第三方模块不要打进来
  4. pageA: A 页面,当 A 页面的组件发生变更后,它的缓存将会失效
  5. pageB: B 页面
  6. echarts: 不常用且过大的第三方模块单独打包
  7. mathjax: 不常用且过大的第三方模块单独打包
  8. jspdf: 不常用且过大的第三方模块单独打包

随着 http2 的发展,特别是多路复用,初始页面的静态资源不受资源数量的影响。因此为了更好的缓存效果以及按需加载,也有很多方案建议把所有的第三方模块进行单模块打包。

TypeScript常用类型速查手册

JavaScript是一个天生的弱类型语言,即变量申明的时候不需要指定类型,不同类型的变量之间也可以相互赋值。如果你已经习惯了这种写法,用起来也是挺爽的,因为不需要特意关心变量类型,直接写就行。但是这样做也很容易导致BUG,而且这些BUG基本都是运行时才出现,因为没有类型,静态检查是查不出问题的,只有运行时报错,可能直接一来就是个线上BUG。

TypeScript就是为JavaScript加上了类型检查,可以用静态检查排查出类型相关的问题,从而避免了线上的BUG。现在TypeScript已经很流行了,我们的新项目也引入了他,但是我用的不是很熟练,经常遇到不知道怎么定义类型的问题。所以我整理了这一份速查手册,从基本类型到interface,泛型这些都有,分享给大家~

基本类型

JavaScript的数据类型主要分为值类型和引用类型两大类。

值类型有string, number, boolean, undefined, 另外ES6引入了symbol, ES2020引入了bigint。这些类型都可以直接作为TS类型使用:

1
2
3
4
5
6
7
let a: string = 'hello';
let b: number = 1234;
let c: boolean = true;
let d: undefined = undefined;
let e: symbol = Symbol('world');
let f: bigint = 1234567123456123n;
let g: null = null; // null也可以作为一个基本类型使用

另外一大类是引用类型,主要是objectfunction,当然你可以将他们直接作为TS类型使用,但是我们不推荐这么做,object最好使用接口或者类来定义,而function最好给出详细的参数定义。我们先来个最简单的写法,后面单独看详细的推荐做法:

1
2
let a: object = {};
let b: Function = () => {};

一个变量可能有多个值的话,可以使用联合类型定义:

1
2
3
let a: string | number | null = 123;
a = 'hello';
a = null;

上面这样申明一个变量是最常见的:

1
let/const 名称: 类型 = 初始值;

但是如果你有了初始值也可以不写类型,比如:

1
2
let a = 'str';    // TS自动推导a是string类型
a = 123; // 报错:因为number不能赋值给string类型

数组

长度不确定的数组

  1. 可以使用T[]这种形式:

    1
    let a: number[] = [1, 2, 3];
  2. 也可以使用Array<T>这种形式:

    1
    let a: Array<number> = [1, 2, 3];

长度确定的数组或者元素类型不一样的数组

可以使用元组[string, number]这种形式:

1
let a: [string, number] = ['hello', 123];

不确定的类型

有时候我们确实会遇到类型不确定的情况,这时候我们可能会用到anynevervoid, unknown。他们的主要作用和区别是:

  1. any:放弃TS的类型检查和保护,可以是任意值,跟普通JS一样,一般不推荐使用这个:

    1
    2
    3
    let a: any = ['hello', 123];
    a = 'hello';
    a = 123;
  2. never:申明函数返回值,表示这个函数永远不会返回,一般用不到。因为一个函数你即使不写return也会默认返回undefined,永远不返回的是指无限循环之类,或者肯定抛出错误的:

    1
    2
    3
    4
    5
    6
    7
    let a: () => never = () => {
    throw new Error();
    }

    let b: () => never = () => {
    while (true) {}
    }
  3. void: 表示函数没有返回值,其实就是默认返回undefined:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    let a: () => void = () => {
    let b = 1;
    console.log(b);
    }

    let c: () => void = () => {
    let b = 1;
    console.log(b);

    return undefined;
    }
  4. unknown:安全的未知类型,在可以使用any的地方,推荐换成unknown,会有类型保护。具体来说就是unknown只能被赋值,而不能赋值给别人,而且不能直接使用,要想使用必须自己先做动态类型检测。

    比如下面这样直接用会报错:

    1
    2
    3
    let a: (b: unknown) => void = (b) => {
    let c:number = b + 1; // 报错:Object is of type 'unknown'.ts(2571)
    }

    但是如果你使用前先检测一下就没问题:

    1
    2
    3
    4
    5
    let a: (b: unknown) => void = (b) => {
    if(typeof b === 'number') {
    let c:number = b + 1;
    }
    }

    所以unknown说直白点就是逼你在使用前先检测类型,自己保障类型安全

函数

一般函数的定义是这样的:

1
2
3
function intro(name: string, age: number): string {
return `My name is ${name}, I am ${age} years old`;
}

相较于普通的JS函数来说,只是给参数和返回值规定了类型而已。

函数是可以赋值给变量的,这个变量的类型应该是被赋值函数的签名,比如将上面的函数赋值给一个变量:

1
const introFun: (name: string, age: number) => string = intro;

这里的introFun的签名就是

1
(name: string, age: number) => string

这也是一个函数签名的标准格式:

1
(参数1: 参数1类型, 参数2: 参数2类型 ...) => 返回值类型

这种函数变量我们也经常作为参数传递,比如另一个函数接收introFun作为参数,那可能就是这样的:

1
2
3
4
5
function wrapper(place: string, introFun: (name: string, age: number) => string): string {
console.log(`I am in ${place}`);

return introFun('Dennis', 18);
}

这里的introFun的函数签名太长了,我们可以用type给他定义个别名:

1
type TIntroFun = (name: string, age: number) => string;

然后就可以用TIntroFun替换那个长长的签名了:

1
2
3
4
5
function wrapper(place: string, introFun: TIntroFun): string {
console.log(`I am in ${place}`);

return introFun('Dennis', 18);
}

可选参数

上面那样写的函数参数都是必须要传的,不传就报错,但是有时候我们有些参数是可选的,可选参数需要在参数名字后面加?:

1
2
3
4
5
6
7
8
9
function intro(name: string, age?: number): string {
if (!age) {
return `My name is ${name}.`;
}

return `My name is ${name}, I am ${age} years old`;
}

intro('Dennis'); // age是可选的,可以不传

age?: number这种可选参数,TS其实是自动联合了undefined类型,等价于age: string | undefined

参数默认值

函数的参数是可以给默认值的,比如上面的name可以给一个默认值小飞

1
2
3
4
5
6
7
function intro(name: string = '小飞', age?: number): string {
if (!age) {
return `My name is ${name}.`;
}

return `My name is ${name}, I am ${age} years old`;
}

根据我们前面变量那里说的,一个变量有了初始值,其类型TS是可以自动推导的,所以name的类型可以省略,变成这样:

1
2
3
4
5
6
7
function intro(name = '小飞', age?: number): string {
if (!age) {
return `My name is ${name}.`;
}

return `My name is ${name}, I am ${age} years old`;
}

但是可选参数不能给默认值,给了就会报错

参数不确定

JS函数非常灵活,一个函数是可以支持不确定个数的参数的,比如这个加法函数:

1
2
3
4
5
function add(...args) {
return args.reduce((prev, item) => prev + item, 0);
}

console.log(add(1,2,3,4)); // 输出10

这个函数接收任意多个数字,返回他们的和,这种函数类型怎么定义呢?args其实是一个数组,按照数组类型给他就行了:

1
2
3
function add(...args: number[]): number {
return args.reduce((prev, item) => prev + item, 0);
}

那如果参数的前面几个是确定的,剩余参数不确定怎么写呢?结合我们前面的函数参数类型和...args就行了:

1
2
3
4
5
6
7
function add(name: string, ...args: number[]): string {
const total = args.reduce((prev, item) => prev + item, 0);

return `${name}: ${total}`;
}

console.log(add('Dennis', 1, 2, 3, 4, 5)); // 输出:Dennis: 15

303. Range Sum Query Immutable

难度: Easy

刷题内容

原题连接

https://leetcode-cn.com/problems/range-sum-query-immutable/

内容描述

给定一个整数数组 nums,求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和,包含 i, j 两点。

示例:

 给定 nums = [-2, 0, 3, -5, 2, -1],求和函数为 sumRange()
 
 sumRange(0, 2) -> 1
 sumRange(2, 5) -> -1
 sumRange(0, 5) -> -3

说明:

  1. 你可以假设数组不可变。
  2. 会多次调用 sumRange 方法。

解题方案

思路
**- 时间复杂度: O(1)**- 空间复杂度: O(N)**

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* @param {number[]} nums
*/
var NumArray = function(nums) {
this.value = nums
};

/**
* @param {number} i
* @param {number} j
* @return {number}
*/
NumArray.prototype.sumRange = function(i, j) {
return this.value.slice(i, j + 1).reduce((total, current) => total + current, 0)
};

/**
* Your NumArray object will be instantiated and called as such:
* var obj = new NumArray(nums)
* var param_1 = obj.sumRange(i,j)
*/

001. Two Sum

难度: Easy

刷题内容

原题连接

内容描述

1
2
3
4
5
6
7
8
9
10
Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

解题方案

思路 1
**- 时间复杂度: O(N)**- 空间复杂度: O(N)**

算法来源于知乎文章——趣味算法思想

先定义一个Object类型的数据结构obj,它的key为target - numbers[i](比如数组第一项为2),value为索引。然后每次都看看obj[numbers[i]] 是否存在,如果存在,那我们就找到了这样的一组数据,返回当前索引以及obj[numbers[i]]。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
var obj = {};

for(var i=0; i< nums.length;i++) {
const item = nums[i];
if(obj[item] >= 0) {
return [obj[item], i]
} else {
obj[target - item] = i;
}
}
};

002. Add Two Numbers

难度: Medium

刷题内容

原题连接

内容描述

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

解题方案

思路 1
**- 时间复杂度: O(max(m,n))**- 空间复杂度: O(max(m,n))**

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
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
let addTwoNumbers = function (l1,l2) {
let result = new ListNode(0),
node = result;
while(l1 || l2){
let r = node.val,
i = (l1 && l1.val) || 0,
j = (l2 && l2.val) || 0,
sum = r + i + j,
m,n;
if(sum >= 10){
m = 1;
n = sum - 10;
}else{
m = 0;
n = sum;
}
l1 = l1 && l1.next;
l2 = l2 && l2.next;
node.val = n;
if(m || l1 || l2){
node.next = new ListNode(m);
node = node.next
}
}
return result;
};

function ListNode(val) {
this.val = val;
this.next = null;
}

003. Longest Substring Without Repeating Characters

难度: Medium

刷题内容

原题连接

内容描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

解题方案

思路 1
**- 时间复杂度: O(N^2)**- 空间复杂度: O(N)**

暴力解法

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* @param {string} s
* @return {number}
*/
let lengthOfLongestSubstring = function (s) {
let result = 0;
for (let i = 0, len = s.length; i < len; i++) {
let set = new Set();
set.add(s.charAt(i));
for (let j = i + 1; j < len; j++) {
if (set.has(s.charAt(j))) {
break;
}
set.add(s.charAt(j));
}
result = Math.max(result,set.size);
}
return result;
};

0005. Longest Palindromic Substring

难度: Medium

刷题内容

原题连接

https://leetcode-cn.com/problems/longest-palindromic-substring/

内容描述

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例1:

 输入: "babad"
 输出: "bab"
 注意: "aba" 也是一个有效答案。

示例2:

 输入: "cbbd"
 输出: "bb"
 
 

进阶:

如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。

解题方案

思路
**- 时间复杂度: O(N)**- 空间复杂度: O(2N)**

解法DP

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 {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
let len = s.length;
if (len < 2) {
return s;
}

dp = Array.from({length:len}).map(() => []);

// 初始化
for (let i = 0; i < len; i++) {
dp[i][i] = true;
}

let maxLen = 1;
let start = 0;

for (let j = 1; j < len; j++) {
for (let i = 0; i < j; i++) {

if (s[i] === s[j]) {
if (j - i < 3) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
} else {
dp[i][j] = false;
}

if (dp[i][j]) {
let curLen = j - i + 1;
if (curLen > maxLen) {
maxLen = curLen;
start = i;
}
}
}
}
return s.substring(start, start + maxLen)
};