其他命令

查找文件

find 命令功能非常强大,通常用来在 特定的目录下 搜索 符合条件的文件

序号 命令 作用
01 find [ 路径 ] -name “*.py” 查找指定路径下扩展名是 .py 的文件,包括子目录

如果省略路径,表示在当前文件夹下查找

之前学习的通配符,在使用 find 命令时同时可用

软链接

序号 命令 作用
01 ln -s 被链接的源文件 链接文件(名称) 建立文件的软链接,用通俗的方式讲类似于 Windows 下的快捷方式

注意:

  1. 没有 -s 选项建立的是一个 硬链接文件
  2. 两个文件占用相同大小的硬盘空间,工作中几乎不会建立文件的硬链接
  3. 源文件要使用绝对路径 ,不能使用相对路径,这样可以方便移动链接文件后,仍然能够正常使用

打包/解压

tar 是 Linux 中最常用的 备份 工具,此命令可以 把一系列文件 打包到 一个大文件中 ,也可以把一个 打包的大文件恢复成一系列文件

选项 含义
c 生成档案文件,创建打包文件
x 解开档案文件
v 列出归档解档的详细过程,显示进度
f 指定档案文件名称, f 后面一定是 .tar 文件,所以必须放选项最后

注意:f 选项必须放在最后,其他选项顺序可以随意

打包

1
tar -cvf 打包名称.tar 被打包的文件/路径 ...

解包

1
tar -xvf 打包文件.tar

解包到指定路径

1
tar -xvf [文件名].tar -C  /path

压缩

  • tar 与 gzip 命令结合可以使用实现文件 打包和压缩

  • tar 只负责打包文件,但不压缩

  • 用 gzip 压缩 tar 打包后的文件,其扩展名一般用 xxx.tar.gz

在 Linux 中,最常见的压缩文件格式就是 xxx.tar.gz

  • 在 tar 命令中有一个选项 -z 可以调用 gzip ,从而可以方便的实现压缩和解压缩的功能

压缩文件

1
tar -zcvf 打包文件.tar.gz 被压缩的文件/路径 ...

解压文件

1
tar -zxvf 打包文件.tar.gz

解压缩到指定路径

1
tar -zxvf 打包文件.tar.gz -C 目标路径 
选项 含义
-C 解压缩到指定目录,注意:要解压缩的目录必须存在

bzip2(two)

  • tar 与 bzip2 命令结合可以使用实现文件 打包和压缩 (用法和 gzip 一样)

  • tar 只负责打包文件,但不压缩,

  • 用 bzip2 压缩 tar 打包后的文件,其扩展名一般用 xxx.tar.bz2

  • 在 tar 命令中有一个选项 -j 可以调用 bzip2 ,从而可以方便的实现压缩和解压缩的功能

压缩

1
tar -jcvf 打包文件.tar.bz2 被压缩的文件/路径 ...

解压

1
tar -jxvf 打包文件.tar.bz2

软件安装

  • apt 是 Advanced Packaging Tool ,是 Linux 下的一款安装包管理工具

  • 可以在终端中方便的 安装 /卸载 / 更新软件包

安装软件

1
sudo apt install 软件包

卸载软件

1
sudo apt remove 软件名

升级软件

1
sudo apt upgrade

如果希望在 ubuntu 中安装软件,更加快速 ,可以通过设置镜像源 ,选择一个访问网速更快的服务器,来提供软件下载/安装服务
提示:更换服务器之后,需要一个相对比较长时间的更新过程,需要耐心等待。更新完成后,再安装软件都会从新设置的服务器下载软件了

下载

1
wget 下载地址

Reflect

概念

Object对象的一些明显属于语言内部的方法(比如Object.defineProperty),放到Reflect对象上。现阶段,某些方法同时在ObjectReflect对象上部署,未来的新方法将只部署在Reflect对象上。也就是说,从Reflect对象上可以拿到语言内部的方法。

修改某些Object方法的返回结果,让其变得更合理。比如,Object.defineProperty(obj, name, desc)在无法定义属性时,会抛出一个错误,而Reflect.defineProperty(obj, name, desc)则会返回false。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 老写法
try {
Object.defineProperty(target, property, attributes);
// success
} catch (e) {
// failure
}

// 新写法
if (Reflect.defineProperty(target, property, attributes)) {
// success
} else {
// failure
}

Object操作都变成函数行为。某些Object操作是命令式,比如name in objdelete obj[name],而Reflect.has(obj, name)Reflect.deleteProperty(obj, name)让它们变成了函数行为。

1
2
3
4
5
// 老写法
'assign' in Object // true

// 新写法
Reflect.has(Object, 'assign') // true

Reflect对象的方法与Proxy对象的方法一一对应,只要是Proxy对象的方法,就能在Reflect对象上找到对应的方法。这就让Proxy对象可以方便地调用对应的Reflect方法,完成默认行为,作为修改行为的基础。也就是说,不管Proxy怎么修改默认行为,你总可以在Reflect上获取默认行为。

Proxy

简介

Proxy 用于修改某些操作的默认行为,等同于在语言层面做出修改,所以属于一种“元编程”(meta programming),即对编程语言进行编程。

可以理解成 Proxy 代理了点运算符,和赋值运算符

通用用法: ES6 原生提供 Proxy 构造函数,用来生成 Proxy 实例。

1
var object = { proxy: new Proxy(target, handler) };

proxy对象是obj对象的原型,obj对象本身并没有time属性,所以根据原型链,会在proxy对象上读取该属性,导致被拦截。

1
2
3
4
5
6
7
8
var proxy = new Proxy({}, {
get: function(target, propKey) {
return 35;
}
});

let obj = Object.create(proxy);
obj.time // 35

get()

get 方法用于拦截某个属性的读取操作,可以接受三个参数,依次为目标对象、属性名和 proxy 实例本身(严格地说,是操作行为所针对的对象),其中最后一个参数可选。

如果一个属性不可配置(configurable)且不可写(writable),则 Proxy 不能修改该属性,否则通过 Proxy 对象访问该属性会报错。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const target = Object.defineProperties({}, {
foo: {
value: 123,
writable: false,
configurable: false
},
});

const handler = {
get(target, propKey) {
return 'abc';
}
};

const proxy = new Proxy(target, handler);

proxy.foo
// TypeError: Invariant check failed

set()

set方法用来拦截某个属性的赋值操作,可以接受四个参数,依次为目标对象、属性名、属性值和 Proxy 实例本身,其中最后一个参数可选。

严格模式下,set代理如果没有返回true,就会报错。

has()

如果原对象不可配置或者禁止扩展,这时has()拦截会报错。

has()拦截只对in运算符生效,对for…in循环不生

1
2
3
4
5
6
7
8
9
10
var obj = { a: 10 };
Object.preventExtensions(obj);

var p = new Proxy(obj, {
has: function(target, prop) {
return false;
}
});

'a' in p // TypeError is thrown

construct()

construct()方法返回的必须是一个对象,否则会报错。

1
2
3
4
5
6
7
8
const p = new Proxy(function() {}, {
construct: function(target, argumentsList) {
return 1;
}
});

new p() // 报错
// Uncaught TypeError: 'construct' on proxy: trap returned non-object ('1')

由于construct()拦截的是构造函数,所以它的目标对象必须是函数,否则就会报错。

1
2
3
4
5
6
7
8
const p = new Proxy({}, {
construct: function(target, argumentsList) {
return {};
}
});

new p() // 报错
// Uncaught TypeError: p is not a constructor

construct()方法中的this指向的是handler,而不是实例对象。

1
2
3
4
5
6
7
8
9
const handler = {
construct: function(target, args) {
console.log(this === handler);
return new target(...args);
}
}

let p = new Proxy(function () {}, handler);
new p() // true

deleteProperty()

目标对象自身的不可配置(configurable)的属性,不能被deleteProperty方法删除,否则报错。

系统信息

时间和日期

序号 命令 作用
01 date 查看系统时间
02 cal calendar 查看日历,-y 选项可以查看一年的日历

磁盘信息

序号 命令 作用
01 df -h disk free 显示磁盘剩余空间
02 du -h [目录名] disk usage 显示目录下的文件大小

-h 以人性化的方式显示文件大小

进程信息

所谓 进程,通俗地说就是 当前正在执行的一个程序

序号 命令 作用
01 ps aux process status 查看进程的详细状况
02 top 动态显示运行中的进程并且排序
03 kill [-9] 进程代号 终止指定代号的进程,-9 表示强行终止

ps 默认只会显示当前用户通过终端启动的应用程序

ps 选项说明

选项 含义
a 显示终端上的所有进程,包括其他用户的进程
u 显示进程的详细状态
x 显示没有控制终端的进程

提示:使用 kill 命令时,最好只终止由当前用户开启的进程,而不要终止 root 身份开启的进程,否则可能导致系统崩溃
要退出 top 可以直接输入 q

用户管理

创建用户/设置密码/删除用户

提示:创建用户 / 删除用户 / 修改其他用户密码 的终端命令都需要通过 sudo 执行

序号 命令 作用 说明
01 useradd -m -g 组 新建用户名 添加新用户 -m 自动建立用户家目录-g 指定用户所在的组,否则会建立一个和同名的组
02 passwd 用户名 设置用户密码 使用sudo运行,如果是普通用户,直接用 passwd 可以修改自己的账户密码
03 userdel -r 用户名 删除用户 -r 选项会自动删除用户家目录
04 cat /etc/passwd | grep 用户名 确认用户信息 新建用户后,用户信息会保存在 /etc/passwd 文件中

提示:

  • 创建用户时,如果忘记添加 -m 选项指定新用户的家目录,最简单的方法就是删除用户

  • 重新创建创建用户时,默认会创建一个和用户名同名的组名,用户信息保存在 /etc/passwd 文件中

查看用户信息

序号 命令 作用
01 id [用户名] 查看用户 UID 和 GID 信息,没写用户名默认是当前用户信息
02 who 查看当前所有登录的用户列表
03 whoami 查看当前登录用户的账户名

passwd 文件

  • /etc/passwd 文件存放的是用户的信息,由 6 个分号组成的 7 个信息,分别是
  1. 用户名
  2. 密码(x,表示加密的密码)
  3. UID(用户标识)
  4. GID(组标识)
  5. 用户全名或本地帐号
  6. 家目录
  7. 登录使用的 Shell,就是登录之后,使用的终端命令,ubuntu 默认是 dash

usermod

  • usermod 可以用来设置 用户 的 主组 / 附加组 和 登录 Shell

  • 主组:通常在新建用户时指定,在 etc/passwd 的第 4 列 GID 对应的组

  • 附加组:在 etc/group 中最后一列表示该组的用户列表,用于指定 用户的附加权限

提示:设置了用户的附加组之后,需要重新登录才能生效!

修改用户的主组(passwd 中的 GID)

1
usermod -g 组 用户名

修改用户的附加组

1
usermod -G 组 用户名

修改用户登录 Shell

由于新建用户默认使用的shell是dash,会导致windows下终端中没有文件高亮,不能使用方向键,所以要修改新建用户的默认shell

提示:设置了用户登录 Shell之后,需要重新登录才能生效!

1
usermod -s /bin/bash 用户名

which

/etc/passwd 是用于保存用户信息的文件

/usr/bin/passwd 是用于修改用户密码的程序

which 命令可以查看执行命令所在位置,例如:

1
which ls
1
2
which useradd
///usr/sbin/useradd

bin 和 sbin

  • 在 Linux 中,绝大多数可执行文件都是保存在 /bin、/sbin、/usr/bin、/usr/sbin

  • /bin(binary)是二进制执行文件目录,主要用于具体应用

  • /sbin(system binary)是系统管理员专用的二进制代码存放目录,主要用于系统管理

  • /usr/bin(user commands for applications)后期安装的一些软件

  • /usr/sbin(super user commands for applications)超级用户的一些管理程序

cd 这个终端命令是内置在系统内核中的,没有独立的文件,因此用 which 无法找到 cd 命令的位置

切换用户

序号 命令 作用 说明
01 su - 用户名 切换用户,并且切换目录 - 可以切换到用户家目录,否则保持位置不变
02 exit 退出当前登录账户
  • su 不接用户名,可以切换到 root,但是不推荐使用,因为不安全

  • exit 示意图如下:

队列和双端队列

队列数据结构

队列是遵循先进先出(FIFO,也称为先来先服务)原则的一组有序的项。队列在尾部添加元素,并从顶部移除元素。最新添加的元素必须排在队列的末尾。

创建队列

通过双指针标明队列的头尾

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
class Queue {
constructor() {
this.count = 0;
this.lowestCount = 0;
this.items = {};
}
enqueue(element) {
this.items[this.count] = element;
this.count++;
}
dequeue() {
if (this.isEmpty()) {
return undefined;
}
const result = this.items[this.lowestCount];
delete this.items[this.lowestCount];
this.lowestCount++;
return result;
}
peek() {
if (this.isEmpty()) {
return undefined;
}
return this.items[this.lowestCount];
}
isEmpty() {
return this.count - this.lowestCount === 0;
}
size() {
return this.count - this.lowestCount;
}
clear() {
this.items = {};
this.count = 0;
this.lowestCount = 0;
}
toString() {
if (this.isEmpty()) {
return '';
}
let objString = `${this.items[this.lowestCount]}`;
for (let i = this.lowestCount + 1; i < this.count; i++) {
objString = `${objString},${this.items[i]}`;
}
return objString;
}
}

双端队列数据结构

双端队列(deque,或称double-ended queue)是一种允许我们同时从前端和后端添加和移除元素的特殊队列。

双端队列的一个常见应用是存储一系列的撤销操作

在头部插入的时候为了保证头部索引为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
35
36
37
38
39
40
41
42
43
44
45
46
class Deque {
constructor() {
this.count = 0;
this.lowestCount = 0;
this.items = {};
}
addFront(element) {
this.lowestCount--;
this.items[this.lowestCount] = element;
}
addBack(element) {
this.items[this.count] = element;
this.count++;
}
removeFront() {
if (this.isEmpty()) return;
const ele = this.items[this.lowestCount];
delete this.items[this.lowestCount];
this.lowestCount++;
return ele;
}
removeBack() {
if (this.isEmpty()) return;
const ele = this.items[this.count];
delete this.items[this.count];
this.lowestCount--;
return ele;
}
peekFront() {
return this.items[this.lowestCount];
}
peekBack() {
return this.items[this.count - 1];
}
isEmpty() {
return this.count === this.lowestCount
}
size() {
return this.count - this.lowestCount
}
clear() {
this.count = 0;
this.lowestCount = 0;
this.items = {};
}
}

循环队列

队列模拟循环队列,击鼓传花问题

规则:有五位玩家,从第一位开始游戏,每轮游戏传7次,结束后花在谁手里,谁就被淘汰,从下一个人继续开始

  • 把玩家加入到上面创建好的队列中
1
2
3
4
5
6
const player = ['John', 'Jack', 'Camila', 'Ingrid', 'Carl'];
const queue = new Queue();

for (let p of player) {
queue.enqueue(p);
}
  • game函数执行,表示游戏开始,输入每轮传花次数7,最终返回获胜玩家

    每次传花经过的人,添加到队列尾部,形成一个循环队列,循环停止时,队列头部的就是拿到花的人,被淘汰即从头部移除

1
2
3
4
5
6
7
8
9
10
function game(queue, nums) {
while (queue.size() > 1) {
for (let i = 0; i < nums; i++) {
queue.enqueue(queue.dequeue());
}
console.log("淘汰==" + queue.dequeue())
}
console.log('获胜==' + queue.peek());
}
game(queue, 7)

解决回文数

可以通过栈这种数据结构解决

本章也可以使用双端队列解决,先把字符串插入到双端队列中,通过while循环检查头部元素和尾部元素是否相同,不同则跳出

JavaScript 任务队列

在浏览器中打开新标签时,就会创建一个任务队列。这是因为每个标签都是单线程处理所有的任务,称为事件循环。

浏览器要负责多个任务,如渲染HTML、执行JavaScript 代码、处理用户交互(用户输入、鼠标点击等)、执行和处理异步请求

Object新增方法

Object.is()

用来比较两个值是否严格相等,与严格比较运算符(===)的行为基本一致。

不同之处只有两个:一是+0不等于-0,二是NaN等于自身。

1
2
3
4
5
6
7
8
9
10
11
12
13
Object.defineProperty(Object, 'is', {
value: function(x, y) {
if (x === y) {
// x===y 是前提,x!==0排除为零的情况,如果xy为0通过转为Infinity判断
return x !== 0 || 1 / x === 1 / y;
}
// 针对NaN的情况, NaN!==NaN
return x !== x && y !== y;
},
configurable: true,
enumerable: false,
writable: true
});

Object.assign()

将源对象(source)的所有可枚举属性,复制到目标对象(target)。Object.assign()方法的第一个参数是目标对象,后面的参数都是源对象。并不会返回新对象

只拷贝源对象的自身属性(不拷贝继承属性),也不拷贝不可枚举的属性(enumerable: false)。Symbol属性虽然不能被 Object.keys 等方法枚举,但是可以被拷贝

由于undefinednull无法转成对象,所以如果它们作为参数,就会报错。 如果非对象参数出现在源对象的位置(即非首参数),那么处理规则有所不同。首先,这些参数都会转成对象,如果无法转成对象,就会跳过。这意味着,如果undefinednull不在首参数,就不会报错。

1
2
3
4
5
6
Object.assign(undefined) // 报错
Object.assign(null) // 报错

let obj = {a: 1};
Object.assign(obj, undefined) === obj // true
Object.assign(obj, null) === obj // true

其他类型的值(即数值、字符串和布尔值)不在首参数,也不会报错。但是,除了字符串会以数组形式,拷贝入目标对象,其他值都不会产生效果。因为只有字符串的包装对象,会产生可枚举属性。

1
2
3
Object(true) // {[[PrimitiveValue]]: true}
Object(10) // {[[PrimitiveValue]]: 10}
Object('abc') // {0: "a", 1: "b", 2: "c", length: 3, [[PrimitiveValue]]: "abc"}

注意点

  • 浅拷贝

  • 同名属性的替换

  • 数组的处理

    Object.assign() 可以用来处理数组,但是会把数组视为对。Object.assign()把数组视为属性名为 0、1、2 的对象,因此源数组的 0 号属性4覆盖了目标数组的 0 号属性1。

1
2
Object.assign([1, 2, 3], [4, 5])
// [4, 5, 3]
  • 取值函数的处理

Object.assign() 只能进行值的复制,如果要复制的值是一个取值函数,那么将求值后再复制。

1
2
3
4
5
6
7
const source = {
get foo() { return 1 }
};
const target = {};

Object.assign(target, source)
// { foo: 1 }

Object.create()

Object.create() 是一个ES5的方法,经常与 Object.assign 混用

Object.create() 创建一个新对象,使用现有的对象来提供新创建的对象的__proto__。

1
2
3
4
5
Object.create(proto[, propertiesObject])

// proto 新创建对象的原型对象。

// propertiesObject 可选。需要传入一个对象,该对象的属性类型参照Object.defineProperties()的第二个参数。如果该参数被指定且不为 undefined,该传入对象的自有可枚举属性(即其自身定义的属性,而不是其原型链上的枚举属性)将为新创建的对象添加指定的属性值和对应的属性描述符。

propertiesObject参数是 null 或非原始包装对象,则抛出一个 TypeError 异常。

常见用途

  • 为对象添加属性

  • 为对象添加方法

  • 克隆对象

    如果想要保持继承链

1
2
3
4
function clone(origin) {
let originProto = Object.getPrototypeOf(origin);
return Object.assign(Object.create(originProto), origin);
}
  • 合并多个对象
1
2
const merge =
(target, ...sources) => Object.assign(target, ...sources);
  • 属性指定默认值
1
Object.assign({}, DEFAULTS, options);

Object.getOwnPropertyDescriptors()

返回指定对象所有自身属性(非继承属性)的描述对象。

1
2
3
4
5
6
7
function getOwnPropertyDescriptors(obj) {
const result = {};
for (let key of Reflect.ownKeys(obj)) {
result[key] = Object.getOwnPropertyDescriptor(obj, key);
}
return result;
}

该方法的引入目的,主要是为了解决Object.assign()无法正确拷贝get属性和set属性的问题。Object.getOwnPropertyDescriptors()方法配合Object.defineProperties()方法,就可以实现正确拷贝。

1
2
3
4
const merge = (target, source) => Object.defineProperties(
target,
Object.getOwnPropertyDescriptors(source)
)

Object.getOwnPropertyDescriptors()方法的另一个用处,是配合Object.create()方法,将对象属性克隆到一个新对象。这属于浅拷贝。

1
2
3
4
const shallowClone = (obj) => Object.create(
Object.getPrototypeOf(obj),
Object.getOwnPropertyDescriptors(obj)
);
1
2
3
4
5
6
let mix = (object) => ({
with: (...mixins) => mixins.reduce(
(c, mixin) => Object.create(
c, Object.getOwnPropertyDescriptors(mixin)
), object)
});

__proto__属性

__proto__ 本质上是一个内部属性,而不是一个正式的对外的 API,只是由于浏览器广泛支持,才被加入了 ES6.

无论从语义的角度,还是从兼容性的角度,都不要使用这个属性,而是使用下面的Object.setPrototypeOf()(写操作)、Object.getPrototypeOf()(读操作)、Object.create()(生成操作)代替。

实现上,__proto__调用的是Object.prototype.__proto__,具体实现如下。

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
Object.defineProperty(Object.prototype, '__proto__', {
get() {
let _thisObj = Object(this);
return Object.getPrototypeOf(_thisObj);
},
set(proto) {
if (this === undefined || this === null) {
throw new TypeError();
}
if (!isObject(this)) {
return undefined;
}
if (!isObject(proto)) {
return undefined;
}
let status = Reflect.setPrototypeOf(this, proto);
if (!status) {
throw new TypeError();
}
},
});

function isObject(value) {
return Object(value) === value;
}

如果一个对象本身部署了__proto__属性,该属性的值就是对象的原型。

1
Object.getPrototypeOf({ __proto__: null })

Object.setPrototypeOf()

1
2
3
4
function setPrototypeOf(obj, proto) {
obj.__proto__ = proto;
return obj;
}

如果第一个参数不是对象,会自动转为对象。但是由于返回的还是第一个参数,所以这个操作不会产生任何效果。

1
2
3
Object.setPrototypeOf(1, {}) === 1 // true
Object.setPrototypeOf('foo', {}) === 'foo' // true
Object.setPrototypeOf(true, {}) === true // true

Object.getPrototypeOf()

如果参数不是对象,会被自动转为对象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 等同于 Object.getPrototypeOf(Number(1))
Object.getPrototypeOf(1)
// Number {[[PrimitiveValue]]: 0}

// 等同于 Object.getPrototypeOf(String('foo'))
Object.getPrototypeOf('foo')
// String {length: 0, [[PrimitiveValue]]: ""}

// 等同于 Object.getPrototypeOf(Boolean(true))
Object.getPrototypeOf(true)
// Boolean {[[PrimitiveValue]]: false}

Object.getPrototypeOf(1) === Number.prototype // true
Object.getPrototypeOf('foo') === String.prototype // true
Object.getPrototypeOf(true) === Boolean.prototype // true

Object.keys(),Object.values(),Object.entries()

Object.entries实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Generator函数的版本
function* entries(obj) {
for (let key of Object.keys(obj)) {
yield [key, obj[key]];
}
}

// 非Generator函数的版本
function entries(obj) {
let arr = [];
for (let key of Object.keys(obj)) {
arr.push([key, obj[key]]);
}
return arr;
}
Object.from

Object.fromEntries()

Object.fromEntries()方法是Object.entries()的逆操作,用于将一个键值对数组转为对象。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 例一
const entries = new Map([
['foo', 'bar'],
['baz', 42]
]);

Object.fromEntries(entries)
// { foo: "bar", baz: 42 }

// 例二
const map = new Map().set('foo', true).set('bar', false);
Object.fromEntries(map)
// { foo: true, bar: false }

O60.n个骰子的点数

LeetCode

注意: 请仔细理解骰子点数,和点数和的概念。骰子点数表示当前第 n 个骰子的点数,为 1 到 6 之间的一个数。 点数和表示投出的 n 个骰子的点数之和。

暴力解法

只有一个骰子的情况,循环每一个点数,存到数组中

数组的位置即数组的索引表示的是点数和,只有一个骰子的时候点数和为骰子点数本身,每种点数和出现的次数为1

1
2
3
4
var arr = [];
for (var i = 1; i <= 6; i++) {
arr[i] = 1;
}

当有两个骰子的时候,点数和最大为 12,即两个骰子都取最大点数 6 的时候

统计每种点数和出现的次数,需要两个嵌套循环,表示在两个骰子中各取一个点数加和

如果数组索引等于点数和的位置为 undefined,表示还没有这种点数和的情况,那就把当前位置赋值为1,表示这种点数和出现的次数为1

如果已经存在,就在原有的值上加1,表示又找到一种点数和相同的情况

1
2
3
4
5
6
7
8
var arr = [];
for (var i = 1; i <= 6; i++) {
for (var j = 1; j <= 6; j++) {
var sum = i + j;
if (arr[sum] === undefined) arr[sum] = 0;
arr[sum] += 1;
}
}

对于n个骰子,我们需要n层嵌套的循环,所以使用递归来实现不定层数的嵌套循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var arr = [];
var n = 2;

function recursion(loop, sum) {
if (loop <= n) {
for (var i = 1; i <= 6; i++) {
recursion(loop + 1, sum + i);
if (loop !== n) continue;
if (arr[sum + i] === undefined) arr[sum + i] = 0;
arr[sum + i]++;
}
}
}
recursion(1, 0)

需要注意的是如果当前层数不是第n层是不需要向数组中添加个数的

也就是递归到最底层,之后才开始计算各点数和

注意不能使用 return 而需要使用 continue 因为return使得函数直接退出,for 循环不能全部执行

下面的写法也可以写成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var arr = [];
var n = 2;

function recursion(loop, sum) {
if (loop > n) {
if (arr[sum] === undefined) arr[sum] = 0;
arr[sum]++;
return arr;
}
for (var i = 1; i <= 6; i++) {
recursion(loop + 1, sum + i);
}
}
recursion(1, 0)

最后只要计算数组中的每个值,即点数和对应的次数在总次数中的占比就可以了

因为次嵌套,所以 总次数为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function twoSum(n) {
var arr = [];
var mount = Math.pow(6, n)

function recursion(loop, sum) {
if (loop > n) {
if (arr[sum] === undefined) arr[sum] = 0;
arr[sum]++;
return arr;
}
for (var i = 1; i <= 6; i++) {
recursion(loop + 1, sum + i);
}
}
recursion(1, 0);
var res = [];
for (var i = 0; i < arr.length; i++) {
if (arr[i] !== undefined) {
res.push(Number((arr[i] / mount).toFixed(5)))
}
}
return res;
}

复杂度分析

  • 时间复杂度:,指数时间复杂度而且容易超时。

  • 空间复杂度: 点数和共有

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function twoSum(n) {
var arr = [];
var mount = Math.pow(6, n)

function recursion(loop, sum) {
if (loop > n) {
if (arr[sum] === undefined) arr[sum] = 0;
arr[sum]++;
return arr;
}
for (var i = 1; i <= 6; i++) {
recursion(loop + 1, sum + i);
}
}
recursion(1, 0);
var res = [];
for (var i = 0; i < arr.length; i++) {
if (arr[i] !== undefined) {
res.push(Number((arr[i] / mount).toFixed(5)))
}
}
return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function twoSum(n) {
var sum = Math.pow(6, n);
var f = [];
f.push([], new Array(6 + 1).fill(1, 1));
for (var i = 2; i <= n; i++) {
if (f[i] === undefined) f[i] = [];
for (var j = i; j <= 6 * i; j++) {
if (f[i][j] === undefined) f[i][j] = 0
for (var k = 1; k <= 6; k++) {
f[i][j] += f[i - 1][j - k] || 0
}
}
}
var res = []
var arr = f[n];
var len = f[n].length
for (var i = 0; i < len; i++) {
if (arr[i] == undefined) continue;
res.push(Number((arr[i] / sum).toFixed(5)));
}
return res;
}

43.字符串相乘

LeetCode

BigInt

不能和Math对象中的方法一起使用;不能和任何Number实例混合运算。

1
2
3
var multiply = function(num1, num2) {
return BigInt(num1) * BigInt(num2) + '';
}

竖向相乘

算法是通过两数相乘时,乘数某位与被乘数某位相乘,与产生结果的位置的规律来完成。具体规律如下:

  • 乘数 num1 位数为 M,被乘数 num2 位数为 Nnum1 * num2 结果 res 最大总位数为 M+N

  • num1[i] * num2[j] 的结果为 tmp(位数为两位,”0x”,”xy”的形式),其第一位位于 res[i+j],第二位位于 res[i+j+1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var multiply = function (num1, num2) {
const stack = new Array(num1.length + num2.length).fill(0);
let res = '';
for (let i = num1.length - 1; i >= 0; i--) {
for (let j = num2.length - 1; j >= 0; j--) {
const sum = stack[i + j + 1] + num1[i] * num2[j];
stack[i + j + 1] = sum % 10;
stack[i + j] += sum / 10 >> 0;
}
}
let make = false;
for (let i = 0; i < stack.length; i++) {
if (!make && stack[i] === 0) {
continue;
}
make = true;
res += stack[i];
}
return res || '0'
};

把边界情况与0相乘单独处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var multiply = function (num1, num2) {
if (num1 === '0' || num2 === '0') {
return '0'
}
const stack = new Array(num1.length + num2.length).fill(0);
let res = '';
for (let i = num1.length - 1; i >= 0; i--) {
for (let j = num2.length - 1; j >= 0; j--) {
const sum = stack[i + j + 1] + num1[i] * num2[j];
stack[i + j + 1] = sum % 10;
stack[i + j] += sum / 10 >> 0;
}
}
for (let i = 0; i < stack.length; i++) {
if (i == 0 && stack[i] === 0) {
continue;
}
res += stack[i];
}
return res;
};

复杂度分析

  • 时间复杂度:, 分别为 num1num2 的长度。

  • 空间复杂度: 用于存储计算结果。

多项式相乘

  • Copyrights © 2015-2025 SunZhiqi

此时无声胜有声!

支付宝
微信