前言

本来是想做成视频的，结果花了一天也没录制上，到处是毛病，所以还是写文章吧。

先说一下这个工具解决了什么问题。

他可以结合Github的WebHook功能，当你在本地git push 后，更具你设置的编译命令，自动编译/部署，省去了你上传的时间。

clone

项目地址：

1

c复制代码https://github.com/houxinlin/CoolDeploy

首先把他clone下来，由于是gradle的项目，所以打包命令是./gradlew bootJar。

之后就可以直接运行了，默认端口是5993，默认密码是cooldeploy。

配置

首先做的是生成公钥，当系统拉去你的项目时需要，然后把这个公钥复制到你的github下，这是必须的一步。

添加项目

这里以我的博客为例，点击主页增加，输入你的项目路径，注意只能是ssh路径。

点击加载后会在后台异步加载，结果会通过WebSocket通知你，下面是加载成功后。

添加构建/部署命令

vue的项目打包分为两步，通过npm build命令打包，然后吧他复制到nginx目录下。

而shell脚本就是执行最后的一些操作，比如复制，在这里，你可以使用{Project_Home}，表示你项目的根路径。

增加WebHook

进入到你项目的WebHook设置下，输入推送路径，推送路径就是这个系统的地址+webhook/。

设置后。你本地push时，Github会推送具体信息给我们的系统，然后我们的系统会根据你设置的编译命令，自动执行。

测试

比如我的博客中间位置显示的是Blog，我们要改为博客。

在本地修改后，通过git push提交，此时只需耐心等待即可，过一会就可以刷新看到效果了。

Gradle项目

如果你的项目是Gradle的，可以通过系统执行某个Task，他可以识别出你项目中所有Task。

二次开发

这个项目是使用SpringBoot+(Vue+Vite)开发的，Vue的项目在下面这个地址。

1

java复制代码git@github.com:houxinlin/CoolDeploy-Web.git

而我们不再使用Nginx，因为部署的时候多了一步，有些麻烦，把Vue打包后，直接放到SpringBoot项目的static目录下即可，让Tomcat去处理他。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

我们之前提到Docker容器是利用操作系统的Namespace和Cgroup机制来实现资源的隔离与限制，Namespace实现隔离已经在上一讲中说过了，本讲主要探讨使用Cgropu实现资源的限制。那么如何理解资源的隔离与限制呢？举个不一定严谨但通俗的例子，假如在公路上开车，资源隔离把公路划了多个子车道，你跑在其中一个子车道上，且你不知道有其它车道存在，你以为整条路都是你的，这时你就会“飘”，要超速，这时候就要限制你的资源，限制你的速度。那么在服务器资源上，就是对内存，CPU等资源进行限制了，防止一个进程占用所有资源。

那这里就可以引出今天要讲的重点: Cgroup, 它的全称是Control Group, 主要作用是限制进程可以使用的资源上限，如内存、CPU、磁盘、网络等。Cgroup对外暴露的操作接口是文件系统， 也就是使用Cgroup的方式是通过操作目录和文件，下面我们就手动模拟Docker的进程资源限制。

查看所有Cgroup信息：

1
2
3
4
5
6
7
8
9
10
11
12

bash复制代码# mount -t cgroup
cgroup on /sys/fs/cgroup/systemd type cgroup (rw,nosuid,nodev,noexec,relatime,xattr,release_agent=/usr/lib/systemd/systemd-cgroups-agent,name=systemd)
cgroup on /sys/fs/cgroup/cpu,cpuacct type cgroup (rw,nosuid,nodev,noexec,relatime,cpuacct,cpu)
cgroup on /sys/fs/cgroup/blkio type cgroup (rw,nosuid,nodev,noexec,relatime,blkio)
cgroup on /sys/fs/cgroup/perf_event type cgroup (rw,nosuid,nodev,noexec,relatime,perf_event)
cgroup on /sys/fs/cgroup/pids type cgroup (rw,nosuid,nodev,noexec,relatime,pids)
cgroup on /sys/fs/cgroup/devices type cgroup (rw,nosuid,nodev,noexec,relatime,devices)
cgroup on /sys/fs/cgroup/net_cls,net_prio type cgroup (rw,nosuid,nodev,noexec,relatime,net_prio,net_cls)
cgroup on /sys/fs/cgroup/memory type cgroup (rw,nosuid,nodev,noexec,relatime,memory)
cgroup on /sys/fs/cgroup/cpuset type cgroup (rw,nosuid,nodev,noexec,relatime,cpuset)
cgroup on /sys/fs/cgroup/freezer type cgroup (rw,nosuid,nodev,noexec,relatime,freezer)
cgroup on /sys/fs/cgroup/hugetlb type cgroup (rw,nosuid,nodev,noexec,relatime,hugetlb)

由上面输出可以看到/sys/fs/cgroup目录下有很子目录，如cpuset、memory等，这些子目录被称为子系统，子系统下面还有相应的配置文件，Cgroup通过不同子系统来限制不同的资源，每种子系统限制资源的方式都是类似的，下面列出几种常用的子系统。

• cpu子系统：控制一个容器里的所有进程（进程组）的CPU最大使用量。
• memory子系统：控制一个进程组的内存最大使用量。

• pids子系统：限制一个控制组里最多可以运行多少个进程。
• cpuset子系统：限制一个控制组里的进程可以在哪几个物理CPU上运行。

• blkio子系统：限制磁盘等块设备使用的I/O。

拿cpu子系统来说，/sys/fs/cgroup/cpu下面又有多个配置文件：

1
2
3
4

python复制代码# ls /sys/fs/cgroup/cpu
assist                 cgroup.procs          cpuacct.usage         cpu.cfs_quota_us   cpu.shares  docker             system.slice
cgroup.clone_children  cgroup.sane_behavior  cpuacct.usage_percpu  cpu.rt_period_us   cpu.stat    notify_on_release  tasks
cgroup.event_control   cpuacct.stat          cpu.cfs_period_us     cpu.rt_runtime_us  default     release_agent      user.slice

稍后我们要用到的配置文件是cpu.cfs_period_us和cpu.cfs_quota_us，它们的默认如下：

1
2
3
4

shell复制代码# cat cpu.cfs_period_us
100000
# cat cpu.cfs_quota_us
-1

cpu.cfs_period_us 默认值是 100 ms（100000 us），cpu.cfs_quota_us的值为-1，代表不限制。

这两个配置文件是组合使用的，它们可以表示的意思是，进程在指定时间内（period）可以使用的cpu配额（quota）,下面我们就用实例来把这两个配置用起来。

在/sys/fs/cgroup/cpu下新建一个目录my-test-container, 这个my-test-container就可以理解成一个控制组，当目录被创建后，里面会自动生成了其资源限制文件，如下所示：

1
2
3
4
5

shell复制代码# cd /sys/fs/cgroup/cpu && mkdir my-test-container && ls my-test-container/

output:
cgroup.clone_children  cgroup.procs  cpuacct.usage         cpu.cfs_period_us  cpu.rt_period_us   cpu.shares  notify_on_release
cgroup.event_control   cpuacct.stat  cpuacct.usage_percpu  cpu.cfs_quota_us   cpu.rt_runtime_us  cpu.stat    tasks

下面我们写个程序，跑个死循环把cpu占满，并找到它的进程号。

1
2
3
4

python复制代码# cat run_to_die.py
#!/usr/bin/env python
while True:
    pass

当运行此程序的时候，可以看到CPU被占满了，它的进程号是31909。

1
2
3
4
5
6
7
8
9

bash复制代码# python run_to_die.py

top:
%Cpu1  :100.0 us,  0.0 sy,  0.0 ni,  0.0 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st

[root@iZ2zec5wzaupsrdu55oeaiZ ~]# ps -ef | grep python
root       910     1  0 7月14 ?       00:07:44 /usr/bin/python2 -Es /usr/sbin/tuned -l -P
root     31909 31612 99 08:16 pts/3    00:01:01 python run_to_die.py
root     31963 31777  0 08:17 pts/4    00:00:00 grep --color=auto python

它把我们的CPU占满了，我们现在就利用Cgroup来限制它只能使用20%的CPU，向 container 组里的 cpu.cfs_quota_us 文件写入 20 ms（20000 us），含义是在每 100 ms 的时间里，被该控制组限制的进程只能使用 20 ms 的 CPU 时间。

1

shell复制代码# echo 20000 > /sys/fs/cgroup/cpu/my-test-container/cpu.cfs_quota_us

下面把run_to_die.py程序的进程号写入my-test-container下的task文件中。

1

shell复制代码# echo 31909 > /sys/fs/cgroup/cpu/my-test-container/tasks

用top指令查看我们的run_to_die.py程序只能用到20%的CPU了。

1
2

less复制代码top:
%Cpu1  : 20.0 us,  0.0 sy,  0.0 ni, 80.0 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st

所以现在可以知道，Docker对于资源限制这里，要做的东西也非常简单，它只需要在指定的目录里建目录，再把相关的参数写到相应的文件里就可以了，下面我们实际启动一个docker容器，并指定相关参数，去相关目录下看看，是不是像我们期待一的一样。

用busybox启动一个镜像，依然限制它使用20%的CPU。

1

shell复制代码# docker run -it --cpu-quota=20000 busybox /bin/sh

查看/sys/fs/cgroup下相关文件内容，是不是我们输入的20000。

1
2

shell复制代码# cat /sys/fs/cgroup/cpu/docker/5ee9d255d1191fac0cfdb6f052aeeea788df1f20de9244c3793d204ecfb0f6f2/cpu.cfs_quota_us
20000

一切都在意料之中。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

大家好，我是肖恩，源码解析每周见

近期我们公司做架构升级，调研了一下各种语言, 包括TypeScript，c#，rust, 还有java和go。这个过程中有一些个人看法，可能会有些偏颇或者不正确的地方，我就简单一说，大家一乐，无意引战。

在上篇中，我简单介绍了一下游戏行业的一些技术栈特点，以及python，Typescript和c#三种语言的使用感受，没有看过的同学可以去看看链接。本文继续介绍go和java，rust的故事。

go 语言

Go 是一种开源编程语言，可以轻松构建 简单、可靠且高效的软件。Go 语言诞生于 2009 年，由google开源，发展到今天已经有过去了10 多年。伴随着云原生的发展，Go语言也是轰轰烈烈红红火火；许多知名的框架，docker，Kubernetes，etcd等都是使用go实现。国内最近的新闻是字节这样的大厂全面拥抱，很多培训机构也在推各种go课程，一切看着都很不错。

我们先简单感受一下，编写下面的的main.go:

1
2
3
4
5
6
7

go复制代码package main

import "fmt"

func main() {
	fmt.Println("Hello, 世界")
}

直接运行这个hello程序:

1
2

go复制代码# go run main.go
Hello, 世界

分别使用下面3个命令，将hello编译成对应操作系统的可执行程序:

1
2
3

ini复制代码GOOS=darwin GOARCH=amd64 go build -o hello_mac
GOOS=linux GOARCH=amd64 go build
GOOS=windows GOARCH=amd64 go build

查看各自的编译结果:

1
2
3
4
5
6

makefile复制代码➜  file hello
hello: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), statically linked, Go BuildID=YPrL0x5YX4DVXlh5kkKE/Y2HJXrRQkDsOpEXTVASf/NrLBfe3AB23u7MFL1ITI/GpLRUEatK4FJEmJ8Q5mW, not stripped
➜  file hello.exe
hello.exe: PE32+ executable (console) x86-64 (stripped to external PDB), for MS Windows
➜  file hello_mac
hello_mac: Mach-O 64-bit executable x86_64

在mac下可以直接执行hello_mac:

1
2
3
4
5
6

bash复制代码➜  hello ./hello
zsh: exec format error: ./hello
➜  hello ./hello.exe
zsh: exec format error: ./hello.exe
➜  hello ./hello_mac
Hello, 世界

这种不需要虚拟机/解释器环境，可以直接执行的能力非常强大。

我自己接触go大概是14年的样子，那时候大概看的是beego的作者Asta谢的书吧。可惜在当时看来感觉go是一个很语法诡异的语言，还不如php/java省事。第二次接触是19年，因为要临时支援一个项目，同时又因为对docker，k8s的学习，了解了go的社区发展，觉得这会是一个很有前景的语言。奈何后来项目变动，又没有继续深入下去。最近算是第三次接触吧，先是写了一些小工具和小服务，计划会写一点网关服务，应该有机会深入下去。无独有偶，发现也有和我感觉类似的同学，我直接摘录在下面:

from draveness

作者目前也使用 Go 语言作为日常开发的主要语言，虽然 Go 语言没有 Lisp 系语言的开发效率和强大表达能力，但是却是一门非常容易使用并且大规模运用的工程语言，这也是作者学习和使用 Go 语言的主要原因。

作者是从 2018 年才开始学习和使用 Go 语言的，刚刚接触 Go 语言时是有些排斥和拒绝的，一度认为 Go 语言 GOPATH 的设计非常诡异，而简单的语法也导致了低下的表达能力并且影响开发效率。但是随着对 Go 语言的深入学习和理解，作者的这一观念也在不断改变。

到了今天，作者认为我们在工业界需要这么一门语法简单的编译型语言，它能够提供简单的抽象和概念，虽然目前 Go 语言也有很多问题，但是语言以及周边工具的不断完善也让作者感受到了社区的活力，也坚定地认为这门语言未来的发展会越来愈好。

学go时候需要一定的适应期。比如下面一段代码:

1
2
3
4
5
6
7
8

go复制代码# gin/context.go

func (c *Context) GetString(key string) (s string) {
	if val, ok := c.Get(key); ok && val != nil {
		s, _ = val.(string)
	}
	return
}

代码理解起来不难，从一个context中取一个key的值后转换成字符串返回。不同的地方在:

• if val, ok := c.Get(key); ok && val != nil {...} 这样的三段式结构，这种语法几乎遍布在go的任何函数。这是因为go没有try/catch语法，所有的函数都要做异常判断。
• (c *Context) 这样的接口实现方式，和面向对象的接口实现有很大的差别。

初期看go的代码，会感觉非常别扭，渡过适应期后，就觉得这种实现方式也没什么问题。然后再陷入go并发不要通过共享内存的方式进行通信，而是应该通过通信的方式共享内存的坑中。

go的学习过程，大概就像是windows电脑使用简单还是mac电脑使用简单的争论，是一个打破先入为主印象的问题。

java和rust

java不用介绍了，工业界的霸主，大厂的最爱。优点非常多，缺点嘛，主要就是个人不精通，已经放弃。

Rust是一门赋予每个人构建可靠且高效软件能力的语言。Rust 速度惊人且内存利用率极高。由于没有运行时和垃圾回收，它能够胜任对性能要求特别高的服务。Rust 丰富的类型系统和所有权模型保证了内存安全和线程安全，让您在编译期就能够消除各种各样的错误。看着是真棒。

我对rust的了解只是浅尝辄止，因为大家都说它上手难度极高。其中所有权的概念，是其核心功能也是核心阻碍。简单举例一下:

1
2
3
4

ini复制代码let s1 = String::from("hello");
let s2 = s1;

println!("{}, world!", s1);

类似上面代码在其它语言中都可以正常运行，就是把s1赋值给s2，然后打印s1。不管是浅拷贝还是深拷贝，只会涉及性能问题，不会执行错误。但是在rust中却是无法执行成功的，因为rust认为s1赋值s2后，s1不再使用了，应该被销毁，这大概就是所有权的概念。

语言生态

语言的学习，前面介绍的内容，都是语法层面。一般来说还涉及语言的生态或者社区，我自己简单归纳语言生态包括下面几个部分:

学习语言的语法后，需要了解语言如何执行。比如python，就需要了解cpython的解释器，了解GIL，了解GC；java需要做JVM的调优，要熟练掌握某种编程语言，仅仅会语法显然是不够的。不同的语言，一般还有不同的IDE工具，比如c#大家惯用的是Visual Studio，熟练使用IDE工具，才可以提高研发效率。虽然现在VSCode，也还不错，但是如果不安装插件，不太好用，安装插件，对新手又不够友好。最好的办法，还是使用jetbrains家的工具，pycharm，rider，goland都是神器。我们还需要学习语言的包管理工具，这样才可以利用于同语言的各种库，站在开源的肩膀上。

语言的社区也是非常重要的一环。首先就是文档，是否有足量的文档去介绍各种语法细节，并且是否有中文文档，对语言学习入门有很大的帮助。我个人比较习惯，中英文文档对照着看，中文看的快，对一些感觉中文介绍不太顺的地方，再从英文中对比理解。然后就是是否有足够多的开源项目，可以去使用，有杀手级的应用可以去参考。开源项目够足，编程实现的时候才会便捷，一般工作都是搬砖，不用从沙子开始造起。

学习语言也是为了工作，除了语言自身的情况，还要考虑一下招聘市场和人才市场。招聘市场可以从岗位的数量和薪资情况反映，下面是一个语言及工资情况的统计数据:

注意: 贴图仅仅示意，并不代表真实的数据

人才市场可以从语言的流行度反映, 比如TIOBE2019-2020年的语言流行度排名:

从上图看Java和Python都还不赖。我个人把各种语言总结成下表:

在学习和了解各种语言的语法，对自己的编程能力提升有帮助，可以开阔不少视野。大家关注不同语言应该重点放在这一块, 对于语言的生态，除非打算用来工作，否则不建议深入，因为不用就会忘记，简单了解即可。带着思考去学习不同语法，比如下面一个python函数:

1
2
3
4
5
6
7
8
9

css复制代码def readme(a, b):
    with open('README.rst', 'w') as f:
        c = 1
        a = a+c;
        b.append("b2")
        f.write(a)
        f.write(b)
    print(a, c)
    return b

我们可以思考下面几个问题:

• 参数a和b的类型
• 入参和出参
• 参数的值传递和引用传递
• b的值和引用
• f,c,a的作用域
• 函数是否有返回值，可以返回几个值
• 如果函数是一个类/接口的实现，语法上又应该如何表示?

上面这几个问题，在不同的语言上，都有不同的实现或者表达方式，多看看就会更加理解函数的本质。

最后的最后，还是推荐大家学习一下c，毕竟这个是鼻祖，是历史，其它语言都是从这个根上派生而来。

参考链接

• Go 语言设计与实现 draveness.me/golang/
• Rust 程序设计语言 kaisery.github.io/trpl-zh-cn/…

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

「这是我参与11月更文挑战的第14天，活动详情查看：2021最后一次更文挑战」。

详细介绍了栈这种数据结构的基本概念，并且介绍了Java的两种不同的实现栈的方式，最后介绍了栈的应用，包括方法的递归调用和四则表达式的运算。

1 栈的概述

栈也是一种数据呈线性排列的数据结构，不过在这种结构中，我们只能访问最新添加的数据。常见的例子就是手枪弹夹，后放进弹夹的子弹将会最先被打出去。

定义中说是在线性表的表尾进行插入和删除操作，这里表尾是指栈顶，而不是栈底。

我们把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），不含任何数据元素的栈称为空栈。栈又称为后进先出（Last In First Out）的线性表，简称LIFO结构。

栈的插入操作，叫作进栈，也称压栈、入栈；栈的删除操作，叫作出栈，也有的叫作弹栈。

由于栈本身就是一个线性表，那么对于线性表的顺序存储和链式存储，对于栈来说，也是同样适用的。

2 入栈和出栈的关系

对于一系列元素，即使规定了入栈的顺序，它们的出栈的顺序也不一定是压栈顺序的倒序。

举例来说，如果我们现在是有3个整型数字元素1、2、3依次进栈，会有哪些出栈次序呢？

1. 第一种：1、2、3进，再3、2、1出。出栈次序为321。
2. 第二种：1进，1出，2进，2出，3进，3出。出栈次序为123。
3. 第三种：1进，2进，2出，1出，3进，3出。出栈次序为213。
4. 第四种：1进，1出，2进，3进，3出，2出。出栈次序为132。
5. 第五种：1进，2进，2出，3进，3出，1出。出栈次序为231。

从这个简单的例子就能看出，只是3个元素，就有5种可能的出栈次序，如果元素数量多，其实出栈的变化将会更多的。

3 栈的顺序存储结构及实现

3.1 栈的顺序存储结构概述

栈的顺序存储其实也是线性表顺序存储的简化，我们简称为顺序栈。 顺序存储结构一般都是使用的数组来实现，栈也不例外。只是，这里需要考虑，用数组的哪一端来作为栈顶和栈底比较好？

当然是数组的起点，即0索引处作为栈底比较好。后续的元素入栈操作就很自然的顺序向后存储，不需要移动元素位置，而栈顶自然选在最大元素索引处，这样元素的出栈也不需要移动其他元素的位置，这样，入栈和出栈的时间复杂度都是O(1)，非常快捷。

Java的JVM就是采用的栈空间结构来进行运行时方法的调用的，方法的入栈和出栈类似于元素的入栈和出栈，只有栈顶的方法才算有效方法。Java的递归的调用，也依赖于栈空间的实现。

3.2 栈的顺序存储结构简单实现

我们的JDK中已经有了栈的实现类，那就是Stack类，它的内部就是采用数组实现的。这里提供一个更加简单的实现。

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

java复制代码/**
 * 栈的顺序存储实现,为了方便,这里底层数组设计为不可扩展
 */
public class MyArrayStack<E> {

    /**
     * 底层使用数组来存储数据
     */
    private final Object[] elements;

    /**
     * 当前栈存储的元素个数
     */
    private int size;


    /**
     * 栈的总容量,数组长度
     */
    private final int capcity;

    /**
     * 构造器中初始化数组
     *
     * @param capcity
     */
    public MyArrayStack(int capcity) {
        this.capcity = capcity;
        elements = new Object[capcity];
    }


    /**
     * 入栈,从0索引处开始存放
     *
     * @param element 添加的元素
     * @return 添加成功返回true，添加失败返回false
     */
    public boolean push(E element) {
        //线性表是否容量已满
        if (size == capcity) {
            // 添加失败返回false
            return false;
        }
        //添加元素到size索引，并且size自增1
        elements[size++] = element;
        //返回true，添加成功
        return true;
    }


    /**
     * 出栈,从元素最大索引处开始出栈
     *
     * @return 返回出栈的元素或者返回null
     */
    public E pop() {
        //如果栈为空,则返回空
        if (size == 0) {
            return null;
        }
        //获取元素最大索引处的元素
        Object e = elements[size - 1];
        //出栈，元素最大索引处的位置置空，并且size自减1
        elements[--size] = null;
        return (E) e;
    }


    /**
     * 获取栈顶元素，但不出栈
     *
     * @return 返回出栈的元素或者返回null
     */
    public E peek() {
        //如果栈为空,则返回空
        if (size == 0) {
            return null;
        }
        //获取元素最大索引处的元素
        Object e = elements[size - 1];
        return (E) e;
    }

    /**
     * 清空栈
     */
    public void clear() {
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
    }


    /**
     * 重写了toString方法
     *
     * @return
     */
    @Override
    public String toString() {
        if (size == 0) {
            return "[ ]";
        }
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[ ");
        for (int i = 0; i < size; i++) {
            stringBuilder.append(elements[i]);
            if (i != size - 1) {
                stringBuilder.append(", ");
            }
        }
        stringBuilder.append(" ]");
        return stringBuilder.toString();
    }
}

3.2.1 测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

java复制代码MyArrayStack<Object> objectMyArrayStack = new MyArrayStack<>(5);

System.out.println("入栈========>");
objectMyArrayStack.push(111);
System.out.println(objectMyArrayStack);

System.out.println("出栈========>");
Object pop = objectMyArrayStack.pop();
System.out.println(pop);
System.out.println(objectMyArrayStack);

System.out.println("入栈========>");
objectMyArrayStack.push(222);
objectMyArrayStack.push(333);


System.out.println("返回栈顶元素但是不出栈========>");
System.out.println(objectMyArrayStack.peek());
System.out.println(objectMyArrayStack);

4 栈的链式存储结构及实现

4.1 栈的链式存储结构概述

栈的链式存储结构，简称为链栈。

栈只是栈顶来做插入和删除操作，栈顶放在链表的头部还是尾部呢？当然是放在链表头部，因为链表通常只保存了头部的指针，如果栈顶放在链表尾部，那么在出栈和入栈时，还需要从链表头部开始遍历到链表的尾部进行操作，比较麻烦。而如果栈顶在链表头部，那么只需要更改链表头部指针就行了，非常轻松。

相比于顺序栈，对于链栈来说，基本不存在栈满的情况，除非内存已经没有可以使用的空间。

4.2 栈的链式存储结构的简单实现

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

java复制代码/**
 * 链栈的简单实现
 */
public class MyLinkedStack<E> {
    /**
     * 空构造器
     */
    public MyLinkedStack() {
    }


    /**
     * 元素个数
     */
    private int size;

    /**
     * 指向头结点的引用,同时也是指向栈顶的引用
     */
    private Node<E> first;

    /**
     * 链栈内部的节点
     */
    private static class Node<E> {
        //下一个结点的引用
        Node<E> next;
        //结点数据
        E data;

        //节点构造器
        public Node(E data, Node<E> next) {
            this.data = data;
            this.next = next;
        }
    }

    /**
     * 入栈,添加元素到链表头部
     *
     * @param element 添加的元素
     * @return 入栈成功返回true，入栈失败返回false
     */
    public boolean push(E element) {
        //改变头结点的
        first = new Node<>(element, first);
        size++;
        return true;
    }

    /**
     * 出栈,移除链表头部元素
     *
     * @return 被出栈的元素
     */
    public E pop() {
        //表示空栈
        if (first == null) {
            throw new NoSuchElementException();
        }
        //如果头结点不为空,表示栈里面有元素
        E e = first.data;
        //改变头结点的引用
        first = first.next;
        size--;
        return e;
    }

    /**
     * 获取栈顶元,素但不出栈
     *
     * @return 被出栈的元素
     */
    public E peek() {
        //表示空栈
        if (first == null) {
            throw new NoSuchElementException();
        }
        //返回栈顶元素
        return first.data;
    }


    /**
     * 清空栈,这里需要,遍历整个栈,一一清理
     */
    public void clear() {
        for (Node<E> x = first; x != null; ) {
            Node<E> next = x.next;
            x.next = null;
            x.data = null;
            x = next;
        }
        first = null;
        size = 0;
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        if (size > 0) {
            Node<E> f = first;
            stringBuilder.append("[ ");
            for (int i = 0; i < size; i++) {
                stringBuilder.append(f.data.toString());
                if (i != size - 1) {
                    stringBuilder.append(" , ");
                }
                f = f.next;
            }
            stringBuilder.append(" ]");
            return stringBuilder.toString();
        }
        return "[]";
    }
}

4.2.1 测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

java复制代码MyLinkedStack<Object> objectMyStack = new MyLinkedStack<>();

System.out.println("入栈========>");
objectMyStack.push(111);
System.out.println(objectMyStack);

System.out.println("出栈========>");
Object pop = objectMyStack.pop();
System.out.println(pop);
System.out.println(objectMyStack);

System.out.println("入栈========>");
objectMyStack.push(222);
objectMyStack.push(333);


System.out.println("返回栈顶元素但是不出栈========>");
System.out.println(objectMyStack.peek());
System.out.println(objectMyStack);

5 栈的应用-递归

5.1 递归的概述

栈有一个很重要的应用：那就是在程序设计语言中实现了递归。比如Java中的递归，就是通过栈来实现的。

方法定义中调用方法本身的现象，称做递归。把一个直接调用自己或通过一系列的调用语句间接地调用自己的方法，称做递归方法。

对于方法中调用方法本身，可以把它理解为在调另一个方法，只不过，这个方法和自己长得一样而已。

使用注意：

1. 构造方法不能递归使用。
2. 应该定义递归的结束条件，满足时递归不再进行，否则就是无限循环递归调用。
3. 要避免内存溢出，递归深度太深容易造成栈内存溢出。

5.2 递归和栈的关系

我们以一个简单的例子，来讲解方法栈是如何实现递归调用方法的。

求一个数的阶乘：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

java复制代码public class Recursive {
    public static void main(String[] args) {
        //这里求5的阶乘    5*((5-1)*((5-1-1)*((5-1-1-1)*(5-1-1-1-1))))
        int factorial = factorial(5);
        System.out.println(factorial);
    }
    /**
     * 递归方法，求n的阶乘  n*((n-1)*((n-1-1)*((n-1-1-1)*…………)))
     *
     * @param n
     * @return
     */
    private static int factorial(int n) {
        //n大于1,则继续递归调用
        if (n > 1) {
            return n * factorial(n - 1);
        } else {
            //n小于等于1,则返回,结束递归
            return 1;
        }
    }
}

5.2.1 方法调用

由于栈的后进先出结构，方法也有入栈和出栈，调用该方法时，方法将会入栈，在栈空间顶部简历一个栈帧，方法执行完毕返回时将会出栈，栈帧被销毁。

在递归的方法中，第一层方法入栈之后，就是当前方法（栈顶的方法，JVM只有当前方法会被执行，只有当前方法是有效的）。

然后开始执行方法中的代码，当执行到调用第二层的方法时，JVM会将调用的方法入栈，同样压入栈顶，成为“当前方法”。同时第一层方法并没有结束，而是它的后续代码将被暂时“搁置”，直到内部调用的方法返回。

同理，在执行第二层方法调用时，又会执行到方法内部的第三层递归调用处，前几层方法都被冻结了，因为内部调用的方法都没有返回，而是继续调用了其他方法。

从上面的步骤可以看出来，方法在调用的时候总是从最外层方法开始一层层向里调用的。

那么，这个递归方法什么时候能够返回呢？

5.2.2 方法返回

我们注意到，每一次递归调用，方法参数n就减少1，这正是该递归方法能够正常结束的关键，当执行到第五层时，n参数变为1，根据代码，n不大于1，执行else逻辑，那么这个递归就可以返回了，并且返回1。

第五层方法由于返回而结束，这也导致第四层方法可以结束，第四层方法结束为：

return 2*(1)

第四层方法由于返回而结束，这也导致第三层方法可以结束，第三层方法结束为：

return 3*(2*1)

第三层方法由于返回而结束，这也导致第二层方法可以结束，第二层方法结束为：

return 4*(3*(2*1))

第二层方法由于返回而结束，这也导致第一层方法可以结束，第一层方法结束为：

return 5*(4*(3*(2*1)))

我们看最终返回的结果，正是第一层方法返回的结果，而这个结果正是5的阶乘。

从上面的步骤可以看出来，返回的时候总是从最底层的方法开始一层层向外返回的。

5.2.3 总结

看看了上面递归的步骤，我们知道递归利用的就是栈的特性，出栈和入栈都是操作栈顶的元素。在JVM中，规定栈顶的方法被称为当前方法，只有当前方法能够执行。关于Java中更多的递归案例可以看这篇文章：Java递归的原理以及各种案例演示。

在方法递归调用阶段：第一层方法调用第二层方法之后，第二层方法入栈，变成栈顶的当前方法，然后继续调用第三层方法入栈……先调用的方法则被渐渐的压入栈底：

在方法返回阶段：最顶部的方法先返回——即出栈，然后是上一层方法返回——出栈，最终是最外层的方法返回。这样就完成了方法的调用的全部逻辑！

6 栈的应用-四则表达式运算

6.1 后缀表达式

我们常见的标准四则运算的表达式，比如1+ 2 * 3 + (4 * 5 + 6) * 7，这样的表达式被称为中缀表达式，因为它的运算符号都在数字之间。

这样的表达式对我们人类来说是非常简单的和容易理解的，但是对于计算机来说，想要解析这样的表达式却是非常的困难，“先乘除后加减，右括号先算括号”这样的简单的口诀对于计算机就如同天书。

后来，20世纪50年代，波兰逻辑学家Jan·ukasiewicz发明了一种不需要括号的后缀表达式，也被称为逆波兰表达式。这种后缀表示法，是表达式的一种新的显示方式，非常巧妙地解决了程序实现四则运算的难题。

对于中缀表达式1+ 2 * 3 + (4 * 5 + 6) * 7，使用后缀表示法应该为：1 2 3 * + 4 5 * 6 + 7 * + 。这样的表达式称为后缀表达式，叫后缀的原因在于所有的符号都是在要运算数字的后面出现。这样的表达式，没有了括号，对于人类来说看起来比较麻烦，但是对于计算机来说则是非常简单了。

6.2 后缀表达式的计算

后缀表达式的计算规则为：从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。

下面来计算上面的后缀表达式：1 2 3 * + 4 5 * 6 + 7 * +

后缀表达式中前三个都是数字，所以1、2、3进栈：

接下来是“*”，所以将栈中的3和2出栈，相乘，结果再入栈：

接下来是“+”，所以将栈中的6和1出栈，相加，结果再入栈：

接下来两个都是数字，所以4、5进栈：

接下来是“*”，所以将栈中的5和4出栈，相乘，结果再入栈：

接下来是数字，6进栈：

接下来是“+”，所以将栈中的6和20出栈，相加，结果再入栈：

接下来是数字，7进栈：

接下来是“*”，所以将栈中的7和26出栈，相乘，结果再入栈：

最后一个是“+”，所以将栈中的162和7出栈，相加，结果再入栈：

最终189出栈，即位后缀表达式的计算结果。这个结果刚好和中缀表达式的计算结果一致。

6.3 中缀表达式转后缀表达式

中缀表达式转后缀表达式规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级不高于栈顶符号（乘除优先加减）则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。

下面来看看中缀表达式1 + 2 * 3 + (4 * 5 + 6) * 7 如何转换为后缀表达式1 2 3 * + 4 5 * 6 + 7 * +

初始化一空栈，用来对符号进出栈使用：

第1个字符是数字1，输出1，第2个字符是符号“+”，进栈：

第3个字符是数字2，输出2，第4个字符是符号“*”，优先级高于栈顶的+，进栈：

第5个字符是数字3，输出3，第6个字符是符号“+”，优先级低于栈顶的*，栈内元素依次出栈，+入栈，此时后缀表达式为：1 2 3 * +

第7个字符是符号“(”，是左括号，进栈：

第8个字符是数字4，输出，第9个字符是符号“*”， 入栈。此时后缀表达式为：1 2 3 * + 4

第10个字符是数字5，输出，第11个字符是符号“+”， 优先级小于栈顶的*，栈顶元素依次出栈，直到匹配到(为止，但是括号符不出栈，+入栈。此时后缀表达式为：1 2 3 * + 4 5 *

第12字符是数字6，输出，第13个字符是符号“)”， 是右括号，栈顶元素依次出栈，直到匹配到(为止，+入栈，括号符全都出栈。此时后缀表达式为：1 2 3 * + 4 5 * 6 +

第16字符是符号“*”，优先级高于栈顶符号，入栈，第17个字符是数字7，输出：

由于所有的字符解析完毕，栈里面剩下的符号依次出栈、输出。最终后缀表达式为：1 2 3 * + 4 5 * 6 + 7 * + 。和前面的后缀表达式一致。

6.3 总结

要想让计算机具有处理我们通常的标准（中缀）表达式的能力，最重要的就是两步：

1. 将中缀表达式转化为后缀表达式（栈用来进出运算的符号）。
2. 将后缀表达式进行运算得出结果（栈用来进出运算的数字）。

整个过程，都充分利用了栈的后进先出特性来处理，理解好它其实也就理解好了栈这个数据结构。

7 总结

本次我们介绍了栈这种数据结构的基本概念，并且介绍了Java的两种不同的实现栈的方式，最后介绍了栈的应用，包括方法的递归调用和四则表达式的运算。

对于方法的递归调用可能还需要一定的JVM的只是，如果对Java的JVM的运行时栈结构不太了解，可以看这篇博客：Java的JVM运行时栈结构和方法调用详解。如果对于线性表这个基本概念还不是很熟悉的同学，可以看这篇博客：Java中的线性表数据结构详解以及实现案例。

相关文章：

1. 《大话数据结构》
2. 《深入理解Java虚拟机》
3. 《算法图解》

如果有什么不懂或者需要交流，可以留言。另外希望点赞、收藏、关注，我将不间断更新各种Java学习博客！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

这是我参与11月更文挑战的第20天，活动详情查看：2021最后一次更文挑战」

1、题目

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

示例 1：

1
2

ini复制代码输入：s = "3+2*2"
输出：7

示例 2：

1
2

ini复制代码输入：s = " 3/2 "
输出：1

示例 3：

1
2

ini复制代码输入：s = " 3+5 / 2 "
输出：5

提示：

• 1 <= s.length <= 3 * 105
• s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开
• s 表示一个 有效表达式
• 表达式中的所有整数都是非负整数，且在范围 [0, 2^31 - 1] 内
• 题目数据保证答案是一个 32-bit 整数

2、思路

(栈,表达式求值) O(n)O(n)O(n)

对于表达式求值这类问题，我们维护两个栈，一个num栈用来记录数字，一个op栈用来记录操作符，遍历表达式，遇到操作符时进行数的相应计算。

首先我们定义一个eval()函数，用于从数字栈num中弹出两个数字a和b，再从操作符栈op中弹出操作符号，进行计算后将结果数字加入到数字栈num中。

具体定义如下：

1
2
3
4
5
6
7
8
9
10
11
12

c复制代码void eval() 
{
    int b = num.top(); num.pop();
    int a = num.top(); num.pop();
    char c = op.top(); op.pop();
    int r;
    if (c == '+') r = a + b;
    else if (c == '-') r = a - b;
    else if (c == '*') r = a * b;
    else r = a / b;
    num.push(r);
}

然后我们从前往后扫描整个表达式：

• 1、当遇到空格 ' '时，跳过。
• 2、当遇到数字时，则读取一个连续的完整数字，再将其加入到数字栈num中。
• 3、当遇到'+'，'-'，'*'，'/' 运算符时，需要考虑优先级：

+ 如果操作符栈`op`的栈顶元素的优先级比当前遇到的操作符优先级高，则`while`循环进行`eval()`操作，即将数字栈`num`栈顶的两个元素取出来，然后和操作符栈`op`的栈顶操作符进行相应计算，并将计算结果压回数字栈`num`中。
+ 否则，将当前运算符压入操作符栈`op`中。

• 4、扫描完整个表达式后，如果操作符栈op中还存在元素，则while循环进行eval()操作。
• 5、最终返回数字栈num的栈顶元素值。

图示过程：

细节处理：

• 1、由于运算符有优先级，所以设计一个哈希表来存储'+'，'-'，'*'，'/' 优先级，我们将'+'和'-'设为1级优先级，将'*'和'/'设为2级优先级。
• 2、考虑到表达式s的第一个数字可能为负数，因此我们给s开头添加一个字符0。

时间复杂度分析： 每个数字和操作进栈出栈一次，所以总的时间复杂度是 O(n)O(n)O(n) 。

3、c++代码

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

c复制代码class Solution {
public:
    stack<int> num;  //存贮数字
    stack<char> op;  //存贮操作

    void eval() 
    {
        int b = num.top(); num.pop();
        int a = num.top(); num.pop();
        char c = op.top(); op.pop();
        int r;
        if (c == '+') r = a + b;
        else if (c == '-') r = a - b;
        else if (c == '*') r = a * b;
        else r = a / b;
        num.push(r);
    }

    int calculate(string s) {
        s = '0' + s;  // 对开头是负数的处理 
        unordered_map<char, int> pr; 
        pr['+'] = pr['-'] = 1, pr['*'] = pr['/'] = 2; //定义运算符的优先级
        for(int i = 0; i < s.size(); i++)
        {
            char c = s[i]; 
            if(c == ' ') continue;  //跳过空格
            if(isdigit(c))     //c是数字,读取一个连续的数字
            {
                int x = 0, j = i;
                while(j < s.size() && isdigit(s[j])) x = x * 10 + (s[j++] - '0');
                num.push(x);    //加入数字栈中
                i = j - 1;        
            }
            else  //c是操作符 
            {     //op栈非空并且栈顶操作符优先级大于等于当前操作符c的优先级，进行eval()计算
                while(op.size() && pr[op.top()] >= pr[c]) eval(); 
                op.push(c);
            }
        }
        while(op.size()) eval(); 
        return num.top();
    }
};

4、java代码

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

java复制代码class Solution {
    static Stack<Integer> num = new Stack<Integer>();
    static Stack<Character> op = new Stack<Character>();
    static HashMap<Character, Integer> map = new HashMap<Character, Integer>();
    static void eval()
    {
        int b = num.pop();
        int a = num.pop();
        char c = op.pop();
        int r = 0;
        if(c == '+') r = a + b;
        else if(c == '-') r = a - b;
        else if(c == '*') r = a * b;
        else r = a / b;
        num.add(r); 
    }
    public int calculate(String s) {
        s = '0' + s; // 对开头是负数的处理 
        map.put('+', 1);   //定义运算符的优先级
        map.put('-', 1);
        map.put('*', 2);
        map.put('/', 2);
        for(int i = 0; i < s.length();i ++)
        {
            char c = s.charAt(i);
            if(c == ' ') continue;  //跳过空格
            if(c >= '0' && c <= '9')  //c是数字,读取一个连续的数字
            {
                int x = 0, j = i;
                while(j < s.length() && s.charAt(j) >= '0' && s.charAt(j) <= '9')
                {
                    x = x * 10 + s.charAt(j) - '0';
                    j ++;
                }
                i = j - 1;
                num.add(x);
            }
            else  //c是操作符 
            {     //op栈非空并且栈顶操作符优先级大于等于当前操作符c的优先级，进行eval()计算
                while(!op.isEmpty() && map.get(op.peek()) >= map.get(c)) eval();
                op.add(c); 
            }
        }
        while(!op.isEmpty()) eval();
        return num.pop();
    }
}

原题链接： 227. 基本计算器 II

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

「这是我参与11月更文挑战的第20天，活动详情查看：2021最后一次更文挑战」。

Go语言学习查缺补漏ing Day2

本文收录于我的专栏：《让我们一起Golang》

一、函数返回参数命名的一个注意事项

请大家观察下面这个函数有什么问题吗？

1
2
3

go复制代码func fun(x, y int) (s int, error) {
    return x * y, nil
}

虽然这个错误，在集成开发环境Goland中会有提示，但是其他的开发工具，比如VS Code就不知道会不会提示了。

我们可以看到这个提示：函数有命名的返回参数，也有没有命名的返回参数。

这就说明函数有多个返回值参数时，如果你给一个参数命了名，那么其他参数也必须命名。而且如果给参数命名，那么必须给参数加上括号，无论参数个数是一个还是多个。这里给第一个参数命名为s，而没有给第二个参数命名，所以有错误。

二、new()和make()有什么不同？

在Go SDK中，对new的描述是这样的：

1
2
3
4

go复制代码// The new built-in function allocates memory. The first argument is a type,
// not a value, and the value returned is a pointer to a newly
// allocated zero value of that type.
func new(Type) *Type

它是一个用于分配内存的内置函数，只有一个参数。如果使用这个函数，那么就会返回一个指向一块新开辟内存的指针，这块内存是第一个参数表示的类型的零值。

我们再来看一看make：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

go复制代码// The make built-in function allocates and initializes an object of type
// slice, map, or chan (only). Like new, the first argument is a type, not a
// value. Unlike new, make's return type is the same as the type of its
// argument, not a pointer to it. The specification of the result depends on
// the type:
//  Slice: The size specifies the length. The capacity of the slice is
//  equal to its length. A second integer argument may be provided to
//  specify a different capacity; it must be no smaller than the
//  length. For example, make([]int, 0, 10) allocates an underlying array
//  of size 10 and returns a slice of length 0 and capacity 10 that is
//  backed by this underlying array.
//  Map: An empty map is allocated with enough space to hold the
//  specified number of elements. The size may be omitted, in which case
//  a small starting size is allocated.
//  Channel: The channel's buffer is initialized with the specified
//  buffer capacity. If zero, or the size is omitted, the channel is
//  unbuffered.
func make(t Type, size ...IntegerType) Type

我们可以了解，make也是分配内存的，但是只能给slice, map 或者 chan分配内存。而且这个make也不返回指针，而是返回你第一个参数代表的类型的值。

经过上面的介绍，我们再来看一看这段代码能否通过编译。

1
2
3
4
5
6
7
8
9

go复制代码​
import "fmt"
​
func main() {
    l := new([]int)
    l = append(l, 0)
    fmt.Println(l)
}
​

显然是不能的，下面是报错信息：

我们前面讲了，new函数new出来的是指针，而指针是不能进行append操作的。所以我们建立slice, map 或者 chan最好使用make函数，而不要使用new函数。

三、切片追加切片问题

如果有两个切片，如何使用append把它们拼凑在一个切片里面呢？

这样行不行？

1
2
3
4
5
6
7
8
9
10
11

go复制代码package main
​
import "fmt"
​
func main() {
    slice := []int{8, 8, 8}
    append_slice := []int{2, 8}
    slice = append(slice, append_slice)
    fmt.Println(slice)
}
​

看一看Goland怎么提示的吧。

好像是不行吧。

这时我们就要使用...这种语法糖。

它有多个功能，其中的一个功能就是可以把切片打散进行传递。还有就是在定义函数时使用，可以接收任意个参数。

下面是运行结果：

四、简短模式声明变量的限制

我们来看一看下面这一段代码，你觉得有没有什么问题？

1
2
3
4
5
6
7
8
9
10
11
12
13

go复制代码package main
​
import "fmt"
​
​
var(
    two = 200
)
one := 100
​
func main() {
    fmt.Println(one,two)
}

是有问题的。

就得来谈一谈变量的简短模式声明有哪些限制：

0. 必须使用显示初始化，也就是手工给予初值。
1. 不能指定数据类型，编译器会根据你指定的初值自动推理变量的类型。
2. 只能在函数内部使用简短模式来声明变量。

我们这里出现错误的原因就是触发了上述第三点限制：未在函数内部使用简短模式来声明变量。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

前言

一年一度的“双11”结束了，截止11月12日零点，天猫GMV定格在5403亿元，再次位居榜首。

其实像这种购物场景，本质上叫秒杀。秒杀什么特点？量少、折扣大、稀缺，因此这种价值势必会吸引一群大聪明来用特殊手段抢购：

比如借助这种物理外挂抢购：

我肯定单身20多年的人手速都比不过它。（别问我为什么知道，我一个朋友说的，他说中国人不骗中国人）

比如通过第三方外挂，按时准点帮忙触发App内的抢购按钮的。

还有抓取并分析抢购接口，通过程序来模拟抢购过程的。

不光是双11，比如你过年抢火车票啊，抢周杰伦演唱会的票，还有去年抢茅台，肯定也有一些人这么就是干的，低买高卖，你不要有人要。

那这种行为有什么影响呢?

首先，这会破坏公平的抢购环境，让正常买家觉得不爽：明明我是手点的，你给我搞这些花里胡哨的不讲武德是吧？

其次，如果他们频繁尝试还会让整个后台系统受到不同程度的性能损耗，此时这就属于一种黑客行为了。

接下来我就说一下程序员应该如何”反击”，包含两部分：

• 如何防止他们利用非法途径比别人快，此时我们一般利用风控去做。
• 如何防止他们一直频繁请求，此时我们会有很多防刷措施。

风控

刚才说了，有些人他是在活动后再搞那些小聪明的，但其实进来的流量我们都无法将其定义为非法流量，这个只能借助像风控这种多维度校验，才能将其识别出来，除非它跳步骤。

什么是风控？其实就是针对某个用户，在不同的业务场景下，检查用户画像中的某些数据，是否触碰了红线。

一个用户画像的基础要素包括手机号、设备号、身份、IP、地址等。一些延展的信息还包括信贷记录、购物记录、履信记录、工作信息、社保信息等等。

这些数据的收集，仅仅依靠单平台是无法做到的，这也是为什么风控的建立需要多平台、广业务、深覆盖，因为只有这样，才能够尽可能多地拿到用户数据。

像阿里腾讯这种大厂，其涵盖非常多的业务线与业务场景，正因为有这些大量数据的支撑，其风控才可能做得更好。

但对于小公司来说，建立一个风控系统是非常困难且不切实际的。但话又回来了，小公司可能也不会太在意谁下单快，先保证流量再说吧。

防刷

限流

我们可以利用一些简单的限流措施，比如Nginx限流：1秒内只允许你请求一次。这种方式可以有效解决黑产流量对单个接口的高频请求。

关于限流内容较多，我会在之后单独出一篇文章详细讲解。

Token机制

Token 我想你是知道的，一般都是用来做鉴权的。放到秒杀的业务场景就是，对于有先后顺序的接口调用，我们要求进入下个接口之前，要在上个接口获得令牌，不然就认定为非法请求。同时这种方式也可以防止多端操作对数据的篡改，如果我们在 Nginx 层做 Token 的生成与校验，可以做到对业务流程主数据的无侵入。

黑名单

黑名单分为本地黑名单和集群黑名单两种，顾名思义，就是通过黑名单的方式来拦截非法请求的。

那黑名单从哪里来呢？总体来说有两个来源：

一个是从外部导入，可以是风控，也可以是别的渠道。

另一个就是自己生成自己用。前面介绍了 Nginx 有条件限流会过滤掉超过阈值的流量，但不能完全拦截，所以索性就不限流，直接全部放进来。

随后我们实现一套”逮捕机制“，可以利用缓存，比如Redis去统计 1 秒内这个用户或者 IP 的请求频率，如果达到了我们设定的阈值，我们就认定其为黑产，然后将其放入到本地缓存黑名单。

黑名单可以被所有接口共享，这样用户一旦被认定为黑产，其针对所有接口的请求，都将直接被全部拦截，实现刷子流量的 0 通过。

总结

这篇文章主要介绍了秒杀系统的黑产问题：通过外部工具、第三方软件参与抢购活动，因为其速度更快、发出请求的频率更高，使得黑产用户获得了比普通用户更大的抢购成功率，这种行为不仅严重破坏了公平的抢购环境，同时也给秒杀系统带来了巨大的额外负担。

在对抗”快人一步”的问题上，我们简单介绍了风控系统。在对抗刷子流量的问题上，我们介绍了Nginx限流、Token机制、黑名单机制。

其实一个完整的秒杀系统是非常复杂的，要考虑非常多的问题，今天介绍的也只是冰山一角。后续我会持续输出干货，介绍更多关于秒杀的核心问题和具体解决方案。

最后

如果感觉这篇文章对你有帮助，欢迎点赞评论，也欢迎大家关注我的公众号：沐晨聊编程。

我是沐晨，咱们下期见。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

什么是 Metrics

在 flink 任务运行的过程中，用户通常想知道任务运行的一些基本指标，比如吞吐量、内存和 cpu 使用情况、checkpoint 稳定性等等。而通过 flink metrics 这些指标都可以轻而易举地获取到，避免任务的运行处于黑盒状态，通过分析这些指标，可以更好的调整任务的资源、定位遇到的问题、对任务进行监控。接下来本文将介绍 flink metrics 的一些基本概念与原理以及实践。

Flink 对于指标监测有一套自己的实现，同时 flink 自身系统有一些固定的 metric 数据，　包括系统的一些指标，CPU,内存, IO 　或者各个 task 运行的一些指标。指标的统计方式有四种，这些指标都实现了 Metric 这个接口，而 Metric 这个接口只是一个标识，本身并没有定义如何方法接口，部分子类的继承关系如下所示。

从图中可以看出，Metric 这个接口有四个直接子类，分别是：

• Gauge —— 最简单的度量指标，只是简单的返回一个值，比如返回一个队列中当前元素的个数；
• Counter —— 计数器，在一些情况下，会比 Gauge 高效，比如通过一个 AtomicLong 变量来统计一个队列的长度；
• Meter —— 吞吐量的度量，也就是一系列事件发生的速率，例如 TPS；
• Histogram —— 度量值的统计结果，如最大值、最小值、平均值，以及分布情况等。

Metrics 使用

下面以 Counter 为例，说明 Metric 的具体用法，Counters 通常用来计数，可以通过 inc 或 dec 方法来对计数值进行增加或减少。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

java复制代码public class MyMapper extends RichMapFunction<String, String> {
  private transient Counter counter;

  @Override
  public void open(Configuration config) {
    this.counter = getRuntimeContext()
      .getMetricGroup()
      .counter("myCounter");
  }

  @Override
  public String map(String value) throws Exception {
    this.counter.inc();
    return value;
  }
}

Metric Reporter

获取 Metrics 有三种方法，首先可以在 WebUI 上看到；其次可以通过 RESTful API 获取，RESTful API 对程序比较友好，比如写自动化脚本或程序，自动化运维和测试，通过 RESTful API 解析返回的 Json 格式对程序比较友好；最后，还可以通过 Metric Reporter 获取，监控主要使用 Metric Reporter 功能。

flink 提供了很多外部监控系统的支持：JMX(java 自带的技术，不严格属于第三方)、Graphite、InfluxDB、Prometheus、StatsD、Datadog、Slf4j（直接打 log 里）等，也可以通过实现 org.apache.flink.metrics.reporter.MetricReporter 接口来编写自己的 Reporter。如果想要定期发送报告，可以实现 Scheduled 接口。

Metric Reporter 是如何配置的？首先 Metrics Reporters 的名字用逗号分隔，然后通过 metrics.reporter.jmx.class 的 classname 反射找 reporter，还需要拿到 metrics.reporter.jmx.port 的配置，比如向第三方系统通过网络发送的比较多，但要知道往哪里发，ip 地址、port 信息是比较常见的。

1
2
3
4
5
6
7
8
9
10
11
12

makefile复制代码vim flink/conf/flink-conf.yaml

metrics.reporters: my_jmx_reporter,my_other_reporter

metrics.reporter.my_jmx_reporter.factory.class: org.apache.flink.metrics.jmx.JMXReporterFactory
metrics.reporter.my_jmx_reporter.port: 9020-9040
metrics.reporter.my_jmx_reporter.scope.variables.excludes:job_id;task_attempt_num

metrics.reporter.my_other_reporter.class: org.apache.flink.metrics.graphite.GraphiteReporter
metrics.reporter.my_other_reporter.host: 192.168.1.1
metrics.reporter.my_other_reporter.port: 10000
metrics.reporter.my_other_reporter.interval: 60 SECONDS

开发者可以实现自己的 reporter，将 metrics 数据导出到不同的系统。

• 实现 MetricReporter 类中的 open,close, notifyOfAddedMetric, notifyOfRemovedMetric 方法。
• 实现 Scheduled 的 report 方法，表示其需要被定期调度执行，在该方法中实现写入到其他系统的逻辑。

自定义 Metric Reporter

MetricReporter 是用来向外暴露 Metric 的监测结果的接口。由于 MetricReporter 的子类在实例化时，都是通过反射机制，所以对于其实现子类，需要有一个公共、无参的构造函数，这个接口的定义如下：

1
2
3
4
5
6

java复制代码public interface MetricReporter {
   void open(MetricConfig config);
   void close();
   void notifyOfAddedMetric(Metric metric, String metricName, MetricGroup group);
   void notifyOfRemovedMetric(Metric metric, String metricName, MetricGroup group);
}

• open —— 由于子类都是用无参构造函数，通过反射进行实例化，所以相关初始化的工作都是放在这里进行的，并且这个方法需要在实例化后，就需要调用该方法进行相关初始化的工作；
• close —— 这里就是在关闭时，进行资源回收等相关操作的；
• notifyOfAddedMetric —— 当有一个新的 Metric 注册时，会调用该方法来通知 MetricReporter；
• notifyOfRemovedMetric —— 当有一个 Metric 被移除时，通过这个方法来通知 MetricReporter；

关注 gzh “HEY DATA” 后台回复关键字 MetricReporter 可获得自定义 MetricReporter 实现例子文件。

本文由博客一文多发平台 OpenWrite 发布！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

「这是我参与11月更文挑战的第 20 天，活动详情查看：2021最后一次更文挑战」

刷算法题，从来不是为了记题，而是练习把实际的问题抽象成具体的数据结构或算法模型，然后利用对应的数据结构或算法模型来进行解题。个人觉得，带着这种思维刷题，不仅能解决面试问题，也能更多的学会在日常工作中思考，如何将实际的场景抽象成相应的算法模型，从而提高代码的质量和性能

二叉树的最大深度

题目来源：LeetCode-104.二叉树的最大深度

题目描述

给定一个二叉树，找出其最大深度

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数

说明: 叶子节点是指没有子节点的节点

示例

示例 1

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

1
2
3
4
5

markdown复制代码		3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3

解题

如果你看过我前边的一篇求二叉树的右视图的文章，这道题的思路跟那个差不多，但这个更加的简单

解法一：深度优先搜索

思路

求最大深度，我们最容易想到的其实就是层序遍历。但是你会发现用层序遍历，并不容易记录当前是哪一层。因此，我们可以考虑用深度优先搜索

深度优先搜索：随意选择一个岔路口来走，走着走着发现走不通的时候，就回退到上一个岔路口，重新选择一条路继续走，直到走完所有的情况

假设我们知道了一棵二叉树的左右子树的深度分别是l和r，那么这颗二叉树的最大深度就是max(l, r)+1

而左右子树的最大深度，可以使用相同的方法来计算，那现在递归公式就有了

1

scss复制代码max(maxDepth(root.Left), maxDepth(root.Right))

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

go复制代码func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}

	return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}

func max(x, y int) int {
	if x > y {
		return x
	}

	return y
}

解法二：广度优先搜索

思路

广度优先搜索：是一种“地毯式”层层推进的搜索策略，即先查找离起始顶点最近的，然后是次近的，依次往外搜索

广度优先搜索可以借助队列来实现，但是解本题的时候，需要做些变化

• 队列里边存的是当前层的所有结点
• 每次遍历下一层的时候，不同于广度优先搜索的每次只从队列里拿出一个节点，我们需要将队列里的所有节点都拿出来进行遍历，这样能保证每次拓展完的时候队列里存放的是当前层的所有节点，即我们是一层一层地进行遍历
• 每向下遍历一层，深度就+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
26
27
28
29
30
31
32

go复制代码//广度优先搜索实现
func maxDepth2(root *TreeNode) int {
	if root == nil {
		return 0
	}

	widthQueue := []*TreeNode{root}
	depth := 0

	for len(widthQueue) != 0 {
		count := len(widthQueue)
		for count > 0 {
			node := widthQueue[0]
			if len(widthQueue) > 1 {
				widthQueue = widthQueue[1:]
			} else {
				widthQueue = []*TreeNode{}
			}
			if node.Left != nil {
				widthQueue = append(widthQueue, node.Left)
			}
			if node.Right != nil {
				widthQueue = append(widthQueue, node.Right)
			}

			count--
		}
		depth++
	}

	return depth
}

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

「这是我参与11月更文挑战的第20天，活动详情查看：2021最后一次更文挑战」

题目

小朋友 A 在和 ta 的小伙伴们玩传信息游戏，游戏规则如下：

1. 有 n 名玩家，所有玩家编号分别为 0 ～ n-1，其中小朋友 A 的编号为 0
2. 每个玩家都有固定的若干个可传信息的其他玩家（也可能没有）。传信息的关系是单向的（比如 A 可以向 B 传信息，但 B 不能向 A 传信息）。
3. 每轮信息必须需要传递给另一个人，且信息可重复经过同一个人

给定总玩家数 n，以及按 [玩家编号,对应可传递玩家编号] 关系组成的二维数组 relation。返回信息从小 A (编号 0 ) 经过 k 轮传递到编号为 n-1 的小伙伴处的方案数；若不能到达，返回 0。

示例1：

1
2
3
4
5

rust复制代码输入：n = 5, relation = [[0,2],[2,1],[3,4],[2,3],[1,4],[2,0],[0,4]], k = 3

输出：3

解释：信息从小 A 编号 0 处开始，经 3 轮传递，到达编号 4。共有 3 种方案，分别是 0->2->0->4， 0->2->1->4， 0->2->3->4。

示例2：

1
2
3
4
5

lua复制代码输入：n = 3, relation = [[0,2],[2,1]], k = 2

输出：0

解释：信息不能从小 A 处经过 2 轮传递到编号 2

限制：

1
2
3
4

ini复制代码2 <= n <= 10
1 <= k <= 5
1 <= relation.length <= 90, 且 relation[i].length == 2
0 <= relation[i][0],relation[i][1] < n 且 relation[i][0] != relation[i][1]

解题思路

假设当前我们已经走了 i 步，所在位置为 j，那么剩余的 k - i 步，能否到达位置 n - 1，仅取决于「剩余步数 k - i」和「边权关系 relation」，而与我是如何到达位置 i 无关。

而对于方案数而言，如果已经走了 i 步，所在位置为 j，到达位置 n - 1 的方案数仅取决于「剩余步数 i - k」、「边权关系 relation」和「花费 i 步到达位置 j 的方案数」。

定义 f[i][j] 为当前已经走了 i 步，所在位置为 j 的方案数。

那么 f[k][n - 1] 为最终答案，f[0][0] = 1 为显而易见的初始化条件。

不失一般性的考虑，f[i][j] 该如何转移，f[i][j] 应该为所有能够到达位置 j 的点 p 的 f[i - 1][p] 的总和：

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13

java复制代码class Solution {
    public int numWays(int n, int[][] relation, int k) {
        int[][] dp = new int[k + 1][n];
        dp[0][0] = 1;
        for (int i = 0; i < k; i++) {
            for (int[] edge : relation) {
                int src = edge[0], dst = edge[1];
                dp[i + 1][dst] += dp[i][src];
            }
        }
        return dp[k][n - 1];
    }
}

最后

空间复杂度是: O(kn)

时间复杂度：O(km)O。其中 m 为 relation 数组的长度

**往期文章：

• 二叉树刷题总结：二叉搜索树的属性
• 二叉树总结：二叉树的属性
• 二叉树总结：二叉树的修改与构造
• StoreKit2 有这么香？嗯，我试过了，真香
• 看完这篇文章，再也不怕面试官问我如何构造二叉树啦！
• 那帮做游戏的又想让大家氪金，太坏了！
• 手把手带你撸一个网易云音乐首页 | 适配篇
• 手把手带你撸一个网易云音乐首页（三）
• 手把手带你撸一个网易云音乐首页（二）
• 手把手带你撸一个网易云音乐首页（一）
• 代码要写注释吗？写你就输了
• Codable发布这么久我就不学，摸鱼爽歪歪，哎~就是玩儿
• iOS 优雅的处理网络数据，你真的会吗？不如看看这篇
• UICollectionView 自定义布局！看这篇就够了

请你喝杯 ☕️ 点赞 + 关注哦～

1. 阅读完记得给我点个赞哦，有👍 有动力
2. 关注公众号— HelloWorld杰少，第一时间推送新姿势

最后，创作不易，如果对大家有所帮助，希望大家点赞支持，有什么问题也可以在评论区里讨论😄～**

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有