发表于

原文链接：Go语言如何高效的进行字符串拼接（6种方式进行对比分析）

前言

哈喽，大家好，我是asong

日常业务开发中离不开字符串的拼接操作，不同语言的字符串实现方式都不同，在Go语言中就提供了6种方式进行字符串拼接，那这几种拼接方式该如何选择呢？使用那个更高效呢？本文我们就一起来分析一下。

本文使用Go语言版本：1.17.1

string类型

我们首先来了解一下Go语言中string类型的结构定义，先来看一下官方定义：

1
2
3
4
go复制代码// string is the set of all strings of 8-bit bytes, conventionally but not
// necessarily representing UTF-8-encoded text. A string may be empty, but
// not nil. Values of string type are immutable.
type string string

string是一个8位字节的集合，通常但不一定代表UTF-8编码的文本。string可以为空，但是不能为nil。string的值是不能改变的。

string类型本质也是一个结构体，定义如下：

1
2
3
4
go复制代码type stringStruct struct {
    str unsafe.Pointer
    len int
}

stringStruct和slice还是很相似的，str指针指向的是某个数组的首地址，len代表的就是数组长度。怎么和slice这么相似，底层指向的也是数组，是什么数组呢？我们看看他在实例化时调用的方法：

1
2
3
4
5
6
go复制代码//go:nosplit
func gostringnocopy(str *byte) string {
	ss := stringStruct{str: unsafe.Pointer(str), len: findnull(str)}
	s := *(*string)(unsafe.Pointer(&ss))
	return s
}

入参是一个byte类型的指针，从这我们可以看出string类型底层是一个byte类型的数组，所以我们可以画出这样一个图片：

string类型本质上就是一个byte类型的数组，在Go语言中string类型被设计为不可变的，不仅是在Go语言，其他语言中string类型也是被设计为不可变的，这样的好处就是：在并发场景下，我们可以在不加锁的控制下，多次使用同一字符串，在保证高效共享的情况下而不用担心安全问题。

string类型虽然是不能更改的，但是可以被替换，因为stringStruct中的str指针是可以改变的，只是指针指向的内容是不可以改变的，也就说每一个更改字符串，就需要重新分配一次内存，之前分配的空间会被gc回收。

关于string类型的知识点就描述这么多，方便我们后面分析字符串拼接。

字符串拼接的6种方式及原理

原生拼接方式”+”

Go语言原生支持使用+操作符直接对两个字符串进行拼接，使用例子如下：

1
2
3
go复制代码var s string
s += "asong"
s += "真帅"

这种方式使用起来最简单，基本所有语言都有提供这种方式，使用+操作符进行拼接时，会对字符串进行遍历，计算并开辟一个新的空间来存储原来的两个字符串。

字符串格式化函数fmt.Sprintf

Go语言中默认使用函数fmt.Sprintf进行字符串格式化，所以也可使用这种方式进行字符串拼接：

1
2
go复制代码str := "asong"
str = fmt.Sprintf("%s%s", str, str)

fmt.Sprintf实现原理主要是使用到了反射，具体源码分析因为篇幅的原因就不在这里详细分析了，看到反射，就会产生性能的损耗，你们懂得！！！

Strings.builder

Go语言提供了一个专门操作字符串的库strings，使用strings.Builder可以进行字符串拼接，提供了writeString方法拼接字符串，使用方式如下：

1
2
3
go复制代码var builder strings.Builder
builder.WriteString("asong")
builder.String()

strings.builder的实现原理很简单，结构如下：

1
2
3
4
go复制代码type Builder struct {
    addr *Builder // of receiver, to detect copies by value
    buf  []byte // 1
}

addr字段主要是做copycheck，buf字段是一个byte类型的切片，这个就是用来存放字符串内容的，提供的writeString()方法就是像切片buf中追加数据：

1
2
3
4
5
go复制代码func (b *Builder) WriteString(s string) (int, error) {
	b.copyCheck()
	b.buf = append(b.buf, s...)
	return len(s), nil
}

提供的String方法就是将[]]byte转换为string类型，这里为了避免内存拷贝的问题，使用了强制转换来避免内存拷贝：

1
2
3
go复制代码func (b *Builder) String() string {
	return *(*string)(unsafe.Pointer(&b.buf))
}

bytes.Buffer

因为string类型底层就是一个byte数组，所以我们就可以Go语言的bytes.Buffer进行字符串拼接。bytes.Buffer是一个一个缓冲byte类型的缓冲器，这个缓冲器里存放着都是byte。使用方式如下：

1
2
3
go复制代码buf := new(bytes.Buffer)
buf.WriteString("asong")
buf.String()

bytes.buffer底层也是一个[]byte切片，结构体如下：

1
2
3
4
5
go复制代码type Buffer struct {
	buf      []byte // contents are the bytes buf[off : len(buf)]
	off      int    // read at &buf[off], write at &buf[len(buf)]
	lastRead readOp // last read operation, so that Unread* can work correctly.
}

因为bytes.Buffer可以持续向Buffer尾部写入数据，从Buffer头部读取数据，所以off字段用来记录读取位置，再利用切片的cap特性来知道写入位置，这个不是本次的重点，重点看一下WriteString方法是如何拼接字符串的：

1
2
3
4
5
6
7
8
go复制代码func (b *Buffer) WriteString(s string) (n int, err error) {
	b.lastRead = opInvalid
	m, ok := b.tryGrowByReslice(len(s))
	if !ok {
		m = b.grow(len(s))
	}
	return copy(b.buf[m:], s), nil
}

切片在创建时并不会申请内存块，只有在往里写数据时才会申请，首次申请的大小即为写入数据的大小。如果写入的数据小于64字节，则按64字节申请。采用动态扩展slice的机制，字符串追加采用copy的方式将追加的部分拷贝到尾部，copy是内置的拷贝函数，可以减少内存分配。

但是在将[]byte转换为string类型依旧使用了标准类型，所以会发生内存分配：

1
2
3
4
5
6
7
go复制代码func (b *Buffer) String() string {
	if b == nil {
		// Special case, useful in debugging.
		return "<nil>"
	}
	return string(b.buf[b.off:])
}

strings.join

Strings.join方法可以将一个string类型的切片拼接成一个字符串，可以定义连接操作符，使用如下：

1
2
go复制代码baseSlice := []string{"asong", "真帅"}
strings.Join(baseSlice, "")

strings.join也是基于strings.builder来实现的，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
go复制代码func Join(elems []string, sep string) string {
	switch len(elems) {
	case 0:
		return ""
	case 1:
		return elems[0]
	}
	n := len(sep) * (len(elems) - 1)
	for i := 0; i < len(elems); i++ {
		n += len(elems[i])
	}

	var b Builder
	b.Grow(n)
	b.WriteString(elems[0])
	for _, s := range elems[1:] {
		b.WriteString(sep)
		b.WriteString(s)
	}
	return b.String()
}

唯一不同在于在join方法内调用了b.Grow(n)方法，这个是进行初步的容量分配，而前面计算的n的长度就是我们要拼接的slice的长度，因为我们传入切片长度固定，所以提前进行容量分配可以减少内存分配，很高效。

切片append

因为string类型底层也是byte类型数组，所以我们可以重新声明一个切片，使用append进行字符串拼接，使用方式如下：

1
2
3
4
go复制代码buf := make([]byte, 0)
base = "asong"
buf = append(buf, base...)
string(base)

如果想减少内存分配，在将[]byte转换为string类型时可以考虑使用强制转换。

Benchmark对比

上面我们总共提供了6种方法，原理我们基本知道了，那么我们就使用Go语言中的Benchmark来分析一下到底哪种字符串拼接方式更高效。我们主要分两种情况进行分析：

  • 少量字符串拼接
  • 大量字符串拼接

因为代码量有点多，下面只贴出分析结果，详细代码已经上传github：github.com/asong2020/G…

我们先定义一个基础字符串：

1
go复制代码var base  = "123456789qwertyuiopasdfghjklzxcvbnmQWERTYUIOPASFGHJKLZXCVBNM"

少量字符串拼接的测试我们就采用拼接一次的方式验证，base拼接base，因此得出benckmark结果：

1
2
3
4
5
6
7
8
9
10
11
12
go复制代码goos: darwin
goarch: amd64
pkg: asong.cloud/Golang_Dream/code_demo/string_join/once
cpu: Intel(R) Core(TM) i9-9880H CPU @ 2.30GHz
BenchmarkSumString-16           21338802                49.19 ns/op          128 B/op          1 allocs/op
BenchmarkSprintfString-16        7887808               140.5 ns/op           160 B/op          3 allocs/op
BenchmarkBuilderString-16       27084855                41.39 ns/op          128 B/op          1 allocs/op
BenchmarkBytesBuffString-16      9546277               126.0 ns/op           384 B/op          3 allocs/op
BenchmarkJoinstring-16          24617538                48.21 ns/op          128 B/op          1 allocs/op
BenchmarkByteSliceString-16     10347416               112.7 ns/op           320 B/op          3 allocs/op
PASS
ok      asong.cloud/Golang_Dream/code_demo/string_join/once     8.412s

大量字符串拼接的测试我们先构建一个长度为200的字符串切片：

1
2
3
4
go复制代码var baseSlice []string
for i := 0; i < 200; i++ {
		baseSlice = append(baseSlice, base)
}

然后遍历这个切片不断的进行拼接，因为可以得出benchmark:

1
2
3
4
5
6
7
8
9
10
11
12
go复制代码goos: darwin
goarch: amd64
pkg: asong.cloud/Golang_Dream/code_demo/string_join/muliti
cpu: Intel(R) Core(TM) i9-9880H CPU @ 2.30GHz
BenchmarkSumString-16                       7396            163612 ns/op         1277713 B/op        199 allocs/op
BenchmarkSprintfString-16                   5946            202230 ns/op         1288552 B/op        600 allocs/op
BenchmarkBuilderString-16                 262525              4638 ns/op           40960 B/op          1 allocs/op
BenchmarkBytesBufferString-16             183492              6568 ns/op           44736 B/op          9 allocs/op
BenchmarkJoinstring-16                    398923              3035 ns/op           12288 B/op          1 allocs/op
BenchmarkByteSliceString-16               144554              8205 ns/op           60736 B/op         15 allocs/op
PASS
ok      asong.cloud/Golang_Dream/code_demo/string_join/muliti   10.699s

结论

通过两次benchmark对比，我们可以看到当进行少量字符串拼接时，直接使用+操作符进行拼接字符串，效率还是挺高的，但是当要拼接的字符串数量上来时，+操作符的性能就比较低了；函数fmt.Sprintf还是不适合进行字符串拼接，无论拼接字符串数量多少，性能损耗都很大，还是老老实实做他的字符串格式化就好了；strings.Builder无论是少量字符串的拼接还是大量的字符串拼接，性能一直都能稳定，这也是为什么Go语言官方推荐使用strings.builder进行字符串拼接的原因，在使用strings.builder时最好使用Grow方法进行初步的容量分配，观察strings.join方法的benchmark就可以发现，因为使用了grow方法，提前分配好内存，在字符串拼接的过程中，不需要进行字符串的拷贝，也不需要分配新的内存，这样使用strings.builder性能最好，且内存消耗最小。bytes.Buffer方法性能是低于strings.builder的，bytes.Buffer 转化为字符串时重新申请了一块空间，存放生成的字符串变量，不像strings.buidler这样直接将底层的 []byte 转换成了字符串类型返回，这就占用了更多的空间。

同步最后分析的结论：

无论什么情况下使用strings.builder进行字符串拼接都是最高效的，不过要主要使用方法，记得调用grow进行容量分配，才会高效。strings.join的性能约等于strings.builder，在已经字符串slice的时候可以使用，未知时不建议使用，构造切片也是有性能损耗的；如果进行少量的字符串拼接时，直接使用+操作符是最方便也是性能最高的，可以放弃strings.builder的使用。

综合对比性能排序：

strings.join ≈ strings.builder > bytes.buffer > []byte转换string > “+” > fmt.sprintf

总结

本文我们针对6种字符串的拼接方式进行介绍，并通过benckmark对比了效率，无论什么时候使用strings.builder都不会错，但是在少量字符串拼接时，直接+也就是更优的方式，具体业务场景具体分析，不要一概而论。

文中代码已上传github：github.com/asong2020/G…

好啦，本文到这里就结束了，我是asong，我们下期见。

欢迎关注公众号：Golang梦工厂

本文转载自: 掘金

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

发表于

这是我参与11月更文挑战的第20天，活动详情查看：2021最后一次更文挑战」 @TOC
在这里插入图片描述

@TOC

一、前言

一看到标题，有的同学可能要奇怪了，诶。怎么是方法，我之前学的C语言，不是叫函数吗，到Java怎么成方法了。
其实这两个是一样的，如果硬要抠字眼的话，方法是不能脱离类存在的，而函数可以。

二、方法的基本概念

2.1 什么是方法

方法可以理解成C语言的函数，是一个代码片段，用来执行或完成一个任务。

2.2创建一个方法

在Java当中，创建方法的格式为：

1
2
3
java复制代码   方法返回类型  +   方法名（参数类型）{
          方法体
   }

举一个例子：我需要创建一个能让两数相加的方法！

1
2
3
java复制代码  int  add(int a,int b){
  return a+b;
  }

在这里，int是方法返回类型，add是方法名称，int a,int b是方法参数的类型和参数名称。 return a+b。是方法体。如果方法返回类型不是void空的话，在方法结尾，就需要返回方法返回类型。说起来有点绕，意思就是最前面写的是int，那么方法结尾就要返回一个int类型的数据。

三、方法的重载

3.1重载

一句话来说就是，同一个方法名字，提供不同版本的实现，这就是重载。

重载的规则：

  • 方法名相同
  • 方法参数不同(参数个数或参数类型均可)
  • 方法的返回值类型不影响重载
  • 当两个方法的名字相同, 参数也相同, 但是返回值不同的时候, 不构成重载.

方法重载的错误示范：

1
2
3
java复制代码public static int addInt(int x, int y) {
 return x + y;
 }
1
2
3
java复制代码public static double addDouble(int x, int y) {
 return x + y;
 }

这里的addInt方法错就错在了返回值类型,不应该是int了，而应该是double。

四、方法的递归

函数自己调用自己这样的行为就叫做方法的递归。
举个例子：

求N的阶乘

1
2
3
4
5
6
java复制代码public static int factor(int n) {
    if (n == 1) {
        return 1;
   }
    return n * factor(n - 1); 
}

像return n * factor(n - 1);这样的代码。factor方法在方法体里又调用了自己的行为就叫方法的递归。

本文转载自: 掘金

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

发表于

​

基于Springboot机票预订系统

本项目基于Springboot框架构建，使用SpringMvc和Mybatis框架进行相应的开发，数据库采用mysql,前端页面采用html实现，基于Jquery+AJAX异步请求处理，主要实现前端用户预定机票，订单查询等功能，后台管理用户实现航班管理，机票管理功能。本项目适合做期未作业使用。

部分功能展示如下：

一，前端用户登陆

  1. 登陆页面：前端用户登陆

)​

2.机票查询功能

)​

3.预订机票

)​

4.订单查询列表

)​

  1. 5.订单详情查询

)​

二，后端用户登陆

  1. 后台管理用户登陆：
  2. )​

2.航班管理：可以对航班进行增删改查操作

)​

  1. 机票管理

)​

以上是网上机票预定系统的功能展示，项目结构清晰，简洁，如有功能需要添加，可以在此基础上进行添加，建议做课程设计或期未作业使用。wx: baozai_7788

\

​

本文转载自: 掘金

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

发表于

简介

Rust 和 C/C++ 具有同样的性能，但是很多常见的 bug 在编译时就可以被消灭了。

Rust 是一种通用的编程语言，善于以下场景：

  • 高性能场景
  • 内存安全场景
  • 利用多处理器场景

C/C++ 虽然性能非常好，类型系统和内存不太安全。

Java/C# 拥有很好的 GC，能保证内存安全，也有很多优秀特性，但是性能相对较低。

Rust 擅长的领域：

  • 高性能 Web Service
  • Webassembly
  • 命令行工具
  • 网络编程
  • 嵌入式编程
  • 系统编程

安装及开发环境配置（Mac）

访问官网（中文官网），点击 ”Install（安装）“，然后执行官网上给出的命令：

1
sh复制代码curl https://sh.rustup.rs -sSf | sh

不过国内的网络可能导致命令不可用，先配置国内源。

1
2
sh复制代码export RUSTUP_DIST_SERVER=https://mirrors.sjtug.sjtu.edu.cn/rust-static
export RUSTUP_UPDATE_ROOT=https://mirrors.sjtug.sjtu.edu.cn/rust-static/rustup

不过官方也提供了离线安装的方案。

在 Install Rust 界面点击“ Other Installation Methods（其他安装方式）”，然后选择 “x86_64-apple-darwin” 进行下载。下载好后直接“傻瓜式”安装即可。

验证安装：

1
sh复制代码rustc --version

安装好之后，使用 VSCode 进行开发，然后给 VSCode 安装一个插件 “Rust-analyzer”。

Hello World

创建文件 main.rs，写入代码：

1
2
3
rust复制代码fn main() {
    println!("Hello World");
}

编译（编译之前一定要安装 XCode）：

1
sh复制代码rustc main.rs

运行：

1
sh复制代码./main

Cargo

对于小项目 rustc 足够了，但是对于大项目我们就需要 Cargo 了。他是一个 Rust 的构建系统和包管理工具，他可以构建代码、下载依赖库、构建代码。

一般在安装 Rust 的时间就会把 Cargo 自动安装上了，可以输入一些命令来判断是否已安装：

1
sh复制代码cargo --version

使用 Cargo 创建项目

1
sh复制代码cargo new hello_cargo

执行之后会创建一个 hello_cargo 目录，其中有 src 目录、Cargo.toml、.gitignore 等文件。

TOML（Tom’s Obvious, Minimal Language）格式，是 Cargo 的配置格式。

在 Rust 里面，代码的包称作 crate，官网地址。

构建 Cargo 项目

使用以下命令构建项目：

1
sh复制代码cargo build

构建好之后会生成可执行文件：target/debug/hello_cargo，输入以下命令运行：

1
sh复制代码./target/debug/hello_cargo

第一次运行构建会在顶层目录生成 cargo.lock 文件，负责精确追踪项目依赖和精确版本，一般不需要手动修改。

为发布构建时需要加 --release 参数：

1
sh复制代码cargo build --release

编译时会进行优化，代码运行会更快，但是编译时间也更长。构建好之后会生成可执行文件在：target/release/ 目录下。

运行 Cargo 项目

使用以下命令可以编译+执行项目：

1
sh复制代码cargo run

如果之前编译过，且源码没改变的情况下，就会直接运行。

检查代码

使用以下命令可以在无编译的情况下检查代码，通过检查的代码是肯定能编译过的，但是不会产生可执行文件，速度比构建要快很多：

1
sh复制代码cargo check

升级依赖包

下面这条命令会升级我们的依赖包，忽略 Cargo.lock 的配置，并从 Cargo.toml 的依赖里面去找指定的版本：

1
sh复制代码cargo update

猜数游戏

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
rust复制代码use rand::Rng;
use std::cmp::Ordering;
use std::io; // prelude; trait

fn main() {
    println!("猜数游戏!");
    let secret_number = rand::thread_rng().gen_range(1..101); // i32 u32 i64
    // println!("神秘数字是： {}", secret_number);
    
    loop {
        println!("猜测一个数");

        let mut guess = String::new();

        io::stdin().read_line(&mut guess).expect("无法读取行");

        // shadow
        let guess: u32 = match guess.trim().parse() {
            Ok(num) => num,
            Err(_) => continue,
        };
        println!("你猜测的数是：{}", guess);

        match guess.cmp(&secret_number) {
            Ordering::Less => println!("Too small!"),
            Ordering::Greater => println!("Too big!"),
            Ordering::Equal => {
                println!("You win!");
                break;
            }
        }
    }
}

变量与可变性

let

声明变量，默认情况下声明出来的变量是不可变的（Immutable）。

如果想让变量可变需要在定义的时候在变量前面加上 mut 关键字。

1
2
3
4
5
6
7
8
9
10
11
rust复制代码fn main() {
    println!("Hello World");
    
    let x = 5;
    // 这样声明之后下面代码将不会报错
    // let mut x = 5;
    println!("The value of x is {}", x);
    
    // 下面代码将报错
    // x = 6;
}

const

常量（constant），常量在绑定值以后是不可变的，但是它与不可变的变量有很多区别：

  • 不可使用 mut，常量永远都是不可变的
  • 声明常量使用 const 关键字，它的类型必须被标注
  • 常量可以在任何作用域内进行声明，包括全局作用域
  • 常量只可以绑定常量表达式，无法绑定到函数的调用结果或只能在运行时才能计算出的值

在程序运行期间，常量在其声明的作用域内一直有效。

命名规范：全大写，每个单词之间用下划线分开，例如：MAX_POINTS，const MAX_POINTS: u32 = 100_000;

1
2
3
4
5
rust复制代码const MAX_POINTS: u32 = 100_000;

fn main() {
    println!("Max points is {}", MAX_POINTS);
}

Shadowing（隐藏）

可以使用相同的名字声明新的变量，新的变量就会 shadow 之前声明的同名变量。

1
2
3
4
5
6
rust复制代码fn main() {
    let x = 5;
    // 下面这个 x 会把上面这个 x 隐藏
    let x = x + 1;
    println!("The value of x is {}", x);
}

Shadowing 的时候类型也是可变的，mut 无法做到这一点：

1
2
3
4
5
rust复制代码fn main() {
    let spaces = "    ";
    let spaces = spaces.len();
    println!("{}", spaces); // 4
}

数据类型

标量

整数类型

无符号的以 u 开头，有符号的以 i 开头。

例如：u32：无符号整型，范围 0 ~ 2的32次方减1，占 32 位空间。

Length Signed Unsigned
8-bit i8 u8
16-bit i16 u16
32-bit i32 u32
64-bit i64 u64
128-bit i128 u128
arch isize usize

isize 和 usize 的位数由计算机的架构所决定，如果是 64 位计算机就是 64 位，如果是 32 位计算机就是 32 位，一般用得不多。

整数字面量：

Number literals Example
Decimal 98_222
Hex 0xff
Octal 0o77
Binary 0b111_0000
Byte(u8 only) b’A’

除了 byte 类型外，所有的数值字面量多允许使用类型后缀，例如：57u8。

整数的默认类型是 i32。

整数溢出：

例如：u8 范围是 0 ~ 255，如果把一个 u8 变量设置为 256，那么在调试模式下编译，可能就会被检查出来，程序会在运行时发生 panic，如果在发布模式（–release）下编译，就不会检查出可能导致的 panic 错误，发生溢出之后 Rust 会执行“环绕”操作：256 变成 0， 257 变成 1，依次类推。

浮点类型

Rust 有两种基础的浮点类型：f32（单精度）、f64（双精度）。浮点类型使用了的是 IEEE - 754 标准，默认是 f64 类型。

1
2
3
4
rust复制代码fn main() {
    let x = 2.0;
    let y: f32 = 3.0;
}

布尔类型

占用一个字节的大小，只有 false 和 true。

1
2
3
4
rust复制代码fn main() {
    let x = 2.0;
    let y: f32 = 3.0;
}

字符类型

char 类型被用来描述最基础的单个字符。字符类型的字面值使用单引号，占用 4 个字节大小，是 Unicode 标量值。

1
2
3
4
5
rust复制代码fn main() {
    let x = 'x';
    let y: char = 'y';
    let z = '😂'; // win + . 输入表情
}

复合类型

Tuple 元祖

可以将多个类型的值放在一个类型里面。

1
2
3
4
5
6
7
8
9
rust复制代码fn main() {
    let tup: (i32, f64, u8) = (500, 2.0, 1);
    
    let (x, y, z) = tup;
    
    println!("{}, {}, {}", tup.0, tup.1, tup.2);
    
    println!("{}, {}, {}", x, y, z);
}

数组

可以将多个值放在一个类型里面，但是值的类型必须相同，数组的长度在声明时就固定了。

1
2
3
4
5
6
7
rust复制代码fn main() {
    let arr = [1, 2, 3, 4, 5];
    let a: [i32, 5] = [1, 2, 3, 4, 5];
    let b = [3; 5]; // 等价于 [3, 3, 3, 3, 3]
    
    println!("{}", arr[0]);
}

如果你想让你的数据存放在栈（stack）内存里面，而不是堆（heap）内存里面，或者想保证有固定数量的元素，这时使用数组更有好处。

函数

声明函数使用 fn 关键字，针对函数和变量名，Rust 使用 snake case 命名规范，即所有字母都是小写的，单词之间使用下划线分开。

1
2
3
4
5
6
7
8
9
rust复制代码fn main() {
    println!("hello world");
    another_function();
}

// another_function 的定义不必在调用之前，这一点不同于 C/C++，更接近 JS
fn another_function() {
    println!("Another function");
}

函数参数

1
2
3
4
5
6
7
8
rust复制代码fn main() {
    another_function(5, 6); // argument
}

// another_function 的定义不必在调用之前，这一点不同于 C/C++，更接近 JS
fn another_function(x: i32, y: i32) { // parameter
    println!("{}", x, y);
}

语句和表达式的区别：

1
2
3
4
5
6
7
8
9
10
rust复制代码fn main() {
	let x = 5;
	let y = {
        let x = 1;
        x + 1 // 此处不加分号，代表表达式，y = x + 1
        x + 1; // 此处加分号就是一个语句，返回的 ()，会报错
    }
    
    println!("{}", y);
}

函数返回值：

如果要提前返回，就用 return，如果不提前返回则返回最后一个表达式。

1
2
3
4
5
6
7
8
9
10
11
12
13
rust复制代码fn five -> i32 {
    5
}

fn plus_five(x: i32) -> i32 {
    x + 5 // 不能加分号
}
fn main() {
	let x = five();
	let y = plus_five(6);
    
    println!("{}, {}", x, y);
}

注释

1
2
3
rust复制代码// 单行注释
/* 多行注释
多行注释 */

控制流

if 表达式

1
2
3
4
5
6
7
8
rust复制代码fn main() {
	let x = 3;
	if number < 5 {
        println!("true");
    } else {
         println!("false");
    }
}
1
2
3
4
5
6
7
8
9
10
11
rust复制代码// 一般来说 else if 最好只出现一次，多次出现最好用 match
fn main() {
	let x = 6;
	if number % 4 == 0 {
        println!("a");
    } else if number % 3 == 0 {
         println!("b");
    } else {
        println!("c");
    }
}
1
2
3
4
5
6
7
8
9
rust复制代码fn main() {
	let condition = true;
    
    let number = if condition { 5 } else { 6 };
    
    let number = if condition { 5 } else { "6" }; // 会报错，类型不兼容
    
    println!("{}", number);
}

循环

loop

反复执行一段代码，直到你喊停（break）为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
rust复制代码fn main() {
	let mut counter = 0;
    
    let result = loop {
        counter += 1;
        
        if counter == 10 {
            break counter * 2;
        }
    }
    
    println!("{}", result);
}

while

1
2
3
4
5
6
7
8
9
rust复制代码fn main() {
	let mut number = 3;
    
    while number != 0 {
        println!("{}", number);
        
        number = number - 1;
    }
}

for

1
2
3
4
5
6
rust复制代码fn main() {
    let a = [10, 20, 30, 40, 50];
    for element in a.iter() { // 迭代器
        println!("{}", element);
    }
}

for 循环比 while 和 loop 更安全和快捷。

Range

1
2
3
4
5
rust复制代码fn main() {
    for number in (1..4).rev() { // (1..4) 就是一个 Range，代表 1, 2, 3（注意：不含 4），rev 是反转这个 Range
        println!("{}", element);
    }
}

所有权

Rust 的核心特性就是所有权。所有程序在运行时都必须管理它们使用计算机内存的方式。

有些语言是自己的 GC，在程序运行时，它们会不断地寻找不再使用的内存，比如 Java，其它语言中，程序员必须显式地分配和释放内存，比如 C++。

而 Rust 采用了一种新的方式：内存是通过一个所有权系统来管理的，其中包含一组编译器在编译时检查的规则。当程序运行，所有权特性不会减慢程序的运行速度。

Stack vs Heap

栈内存和堆内存，在像 Rust 这样的系统级编程语言里，一个值是在 stack 上还是在 heap 上对语言的行为和你为什么要做某些决定是有更大的影响的。

存储数据

Stack 是后进先出，所有存储在 stack 上的数据必须拥有已知的固定的大小，编译时大小未知的数据或运行时大小可能发生变化的数据必须存放在 heap 上。

Heap 内存组织性差一些，当你把数据放入 heap 时，你会请求一定数量的空间，当操作系统在 heap 里找到一块足够大的空间，把它标记为在用，并返回一个指针，也就是这个空间的地址，这个过程叫做在 heap 上进行分配，有时仅仅称为“分配”。

把值压到 stack 上不叫分配，因为指针是已知固定大小的，可以把指针存放在 stack 上。但如果想要实际数据，你必须使用指针来定位。

把数据压到 stack 上要比在 heap 上分配快得多，因为操作系统不需要寻找用来存储新数据的空间，那个位置永远都在 stack 的顶端。

在 heap 上分配空间需要做更多工作，操作系统首先要找到一个足够大的空间来存储数据，然后要做好记录方便下次分配。

访问数据

访问 heap 中的数据要比访问 stack 中的数据慢，因为需要通过指针才能找到 heap 中的数据。对于现代的处理器来说，由于缓存的缘故，如果指令在内存中跳转的次数越少，那么速度就越快。

如果数据存放的距离比较近，那么处理器的处理速度就会更快一些（stack 上）；

如果数据存放的距离比较远，那么处理器的处理速度就会更慢一些（heap 上）；在 heap 上分配大量的空间也是需要时间的。

函数调用

当你的代码调用函数时，值被传入到函数（也包括指向 heap 的指针）。函数本地的变量被压到 stack 上。当函数结束后，这些值会从 stack 上弹出。

所有权存在的原因

所有权解决的问题：

  • 跟踪代码的哪些部分正在使用 heap 的哪些数据
  • 最小化 heap 上的重复数据量
  • 清理 heap 上未使用的数据以避免空间不足

一旦你懂了所有权，那么就不需要经常去想 stack 或 heap 了。

但是知道管理 heap 数据是所有权存在的原因，这有助于解释它为什么会这样工作。

所有权规则

  • 有个值都有一个变量，这个变量是该值的所有者
  • 每个值同时只能有一个所有者
  • 当所有者超出作用域（scope）时，该值将被删除
1
2
3
4
5
6
7
8
9
rust复制代码fn main() {
    // 与标量的 char 不同，String 是分配到 heap 上的数据类型
    let mut s = String::from("hello");
    
    s.push_str(", world");
    
    println!("{}", s);
}
// 超出作用域之后，Rust 会自动调用 drop 函数，s 就会被内存回收
1
2
3
4
5
6
7
rust复制代码fn main() {
    let mut s1 = String::from("hello");
    
    let s2 = s1;
    
    println!("{}", s1); // 会报错，因为在 Rust 中，赋值之后 s1 会失效（借用了已经移动的值 s1），只能使用 s2
}

上述 s1 赋值给 s2 的操作，不同于传统的浅拷贝（shallow copy）和深拷贝（deep copy），所以我们用一个新术语表达：移动（Move）。

1
2
3
4
5
6
7
rust复制代码fn main() {
    let mut s1 = String::from("hello");
    
    let s2 = s1.clone;
    
    println!("{}, {}", s1, s2);
}

这样操作 s1 和 s2 都可以使用了。

引用和借用

& 符号就表示引用（References），允许你引用某些值而不取得其所有权。

1
2
3
4
5
6
7
8
9
rust复制代码fn main() {
    let s1 = String::from("hello");
    let len = calculate_length(&s1);
    println!("{}, {}", s1, len);
}
// 这个函数使用了引用的方式去使用 s1，这种方式，没有转移 s1 的所有权，不会对 s1 的所有权产生影响
fn calculate_length(s: &String) -> usize {
    s.len()
}

我们把引用作为函数参数这个行为叫做借用。

借用的东西，如果被引用变量是可变的，那么借用的变量才能可变，否则不可变。

1
2
3
4
5
6
7
8
9
rust复制代码fn main() {
    let mut s1 = String::from("hello");
    let len = calculate_length(&mut s1);
    println!("{}, {}", s1, len);
}

fn calculate_length(s: &mut String) -> usize {
    s.len()
}

另外，对于某一块数据，只有一个可变的引用（不可变引用可以有很多个）。这样做在编译的时候可以防止数据竞争（两个或多个指针同时访问同一个数据；至少有一个指针用于写入数据；没有使用任何机制来同步对数据的访问）。

1
2
3
4
5
6
rust复制代码fn main() {
    let mut s = String::from("hello");
    let s1 = &mut s;
    let s2 = &mut s; // 会报错
    println!("{}, {}", s1, s2);
}
1
2
3
4
5
6
7
rust复制代码// 这样就不会报错了
fn main() {
    let mut s = String::from("hello");
    { let s1 = &mut s; }
    let s2 = &mut s;
    println!("{}, {}", s1, s2);
}

不可以同时拥有一个可变引用和一个不可变引用。

1
2
3
4
5
6
7
rust复制代码fn main() {
    let mut s = String::from("hello");
    let r1 = &s;
    let r2 = &s;
    let s1 = &mut s; // 会报错
    println!("{}, {}", r1, r2, s1);
}

悬空引用（悬垂引用 Dangling References）：一个指针引用了内存中的某个地址，而这块儿内存可能已经释放并分配给其它人使用了，俗称“野指针”。

1
2
3
4
5
6
7
8
rust复制代码fn main() {
    let r = dangle();
}

fn dangle() -> &String {
    let s = String::from("hello"); // s 在函数执行完之后就会被释放，但是此函数返回了 s 的引用
    &s
}

Rust 在编译的时候就会报错，防止悬空指针 bug 出现。

切片

Rust 的另一种不持有所有权的数据类型：切片（slice）。

下面这段代码返回一个字符串中的空格的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
rust复制代码fn main() {
	let mut s = String::from("hello world");
    let wordIndex = first_word(&s);
    
    // s.clear(); // 如果加上这句 wordIndex 的有效性是不能保障的，后续再使用，可能会出 bug，但是编译时不会报错
    println!("{}", wordIndex);
}

fn first_word(s: &String) -> usize {
    let bytes = s.as_bytes();
    
    for (i, &item) in bytes.iter().enumerate() {
        if item == b' ' {
            return i;
        }
    }
    s.len()
}

不过这段代码有个致命的问题，也就是 wordIndex 的有效性是不能保障的，容易出 bug。

但是，字符串切片就可以解决这个问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
rust复制代码fn main() {
	let mut s = String::from("hello world");
    let hello = &s[0..5]; // 切片
    let world = &s[6..11];
    
    /* 语法糖
    let hello = &s[..5]; // 从零开始可以不写 0
    let world = &s[6..]; // 以末尾结束可以不写末尾 index
    let whole = &s[..]; // 整个字符串，头尾数字都可以不写
    */
    
    println!("{}", wordIndex);
}

改造上面的函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
rust复制代码fn main() {
	let mut s = String::from("hello world");
    let wordIndex = first_word(&s);
    
    s.clear(); // 此时会报错
    println!("{}", wordIndex);
}

fn first_word(s: &String) -> &str {
    let bytes = s.as_bytes();
    
    for (i, &item) in bytes.iter().enumerate() {
        if item == b' ' {
            return &s[..i];
        }
    }
    &s[..]
}

字符串字面值就是一个切片，其类型为 &str。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
rust复制代码fn main() {
	let s = String::from("hello world");
    let wordIndex = first_word(&s[..]);
    
    let my_str = "hello world";
    let wordIndex2 = first_word(my_str);
}

fn first_word(s: &str) -> &str { // 这样用更好，会使我们的函数更加通用
    let bytes = s.as_bytes();
    
    for (i, &item) in bytes.iter().enumerate() {
        if item == b' ' {
            return &s[..i];
        }
    }
    &s[..]
}

其它类型的切片：

1
2
3
4
rust复制代码fn main() {
    let a = [1, 2, 3, 4, 5];
    let slice = &a[1..3];
}

本文转载自: 掘金

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

发表于

读完本文，你不仅学会了算法套路，还可以顺便去 LeetCode 上拿下如下题目：

  1. 以图判树（中等）
  2. 最低成本联通所有城市（中等）
  3. 连接所有点的最小费用（中等）

———–

图论中知名度比较高的算法应该就是 Dijkstra 最短路径算法，环检测和拓扑排序，二分图判定算法 以及今天要讲的最小生成树（Minimum Spanning Tree）算法了。

最小生成树算法主要有 Prim 算法（普里姆算法）和 Kruskal 算法（克鲁斯卡尔算法）两种，这两种算法虽然都运用了贪心思想，但从实现上来说差异还是蛮大的，本文先来讲 Kruskal 算法，Prim 算法另起一篇文章写。

Kruskal 算法其实很容易理解和记忆，其关键是要熟悉并查集算法，如果不熟悉，建议先看下前文 Union-Find 并查集算法。

接下来，我们从最小生成树的定义说起。

什么是最小生成树

先说「树」和「图」的根本区别：树不会包含环，图可以包含环。

如果一幅图没有环，完全可以拉伸成一棵树的模样。说的专业一点，树就是「无环连通图」。

那么什么是图的「生成树」呢，其实按字面意思也好理解，就是在图中找一棵包含图中的所有节点的树。专业点说，生成树是含有图中所有顶点的「无环连通子图」。

容易想到，一幅图可以有很多不同的生成树，比如下面这幅图，红色的边就组成了两棵不同的生成树：

对于加权图，每条边都有权重，所以每棵生成树都有一个权重和。比如上图，右侧生成树的权重和显然比左侧生成树的权重和要小。

那么最小生成树很好理解了，所有可能的生成树中，权重和最小的那棵生成树就叫「最小生成树」。

PS：一般来说，我们都是在无向加权图中计算最小生成树的，所以使用最小生成树算法的现实场景中，图的边权重一般代表成本、距离这样的标量。

在讲 Kruskal 算法之前，需要回顾一下 Union-Find 并查集算法。

Union-Find 并查集算法

刚才说了，图的生成树是含有其所有顶点的「无环连通子图」，最小生成树是权重和最小的生成树。

那么说到连通性，相信老读者应该可以想到 Union-Find 并查集算法，用来高效处理图中联通分量的问题。

前文 Union-Find 并查集算法详解 详细介绍了 Union-Find 算法的实现原理，主要运用 size 数组和路径压缩技巧提高连通分量的判断效率。

如果不了解 Union-Find 算法的读者可以去看前文，为了节约篇幅，本文直接给出 Union-Find 算法的实现：

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
java复制代码class UF {
    // 连通分量个数
    private int count;
    // 存储一棵树
    private int[] parent;
    // 记录树的「重量」
    private int[] size;

    // n 为图中节点的个数
    public UF(int n) {
        this.count = n;
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }
    
    // 将节点 p 和节点 q 连通
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ)
            return;
        
        // 小树接到大树下面，较平衡
        if (size[rootP] > size[rootQ]) {
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ];
        } else {
            parent[rootP] = rootQ;
            size[rootQ] += size[rootP];
        }
        // 两个连通分量合并成一个连通分量
        count--;
    }

    // 判断节点 p 和节点 q 是否连通
    public boolean connected(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }

    // 返回节点 x 的连通分量根节点
    private int find(int x) {
        while (parent[x] != x) {
            // 进行路径压缩
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    // 返回图中的连通分量个数
    public int count() {
        return count;
    }
}

前文 Union-Find 并查集算法运用 介绍过 Union-Find 算法的一些算法场景，而它在 Kruskal 算法中的主要作用是保证最小生成树的合法性。

因为在构造最小生成树的过程中，你首先得保证生成的那玩意是棵树（不包含环）对吧，那么 Union-Find 算法就是帮你干这个事儿的。

怎么做到的呢？先来看看力扣第 261 题「以图判树」，我描述下题目：

给你输入编号从 0 到 n - 1 的 n 个结点，和一个无向边列表 edges（每条边用节点二元组表示），请你判断输入的这些边组成的结构是否是一棵树。

函数签名如下：

1
java复制代码boolean validTree(int n, int[][] edges);

比如输入如下：

1
2
shell复制代码n = 5
edges = [[0,1], [0,2], [0,3], [1,4]]

这些边构成的是一棵树，算法应该返回 true：

但如果输入：

1
2
shell复制代码n = 5
edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]

形成的就不是树结构了，因为包含环：

对于这道题，我们可以思考一下，什么情况下加入一条边会使得树变成图（出现环）？

显然，像下面这样添加边会出现环：

而这样添加边则不会出现环：

总结一下规律就是：

对于添加的这条边，如果该边的两个节点本来就在同一连通分量里，那么添加这条边会产生环；反之，如果该边的两个节点不在同一连通分量里，则添加这条边不会产生环。

而判断两个节点是否连通（是否在同一个连通分量中）就是 Union-Find 算法的拿手绝活，所以这道题的解法代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
java复制代码// 判断输入的若干条边是否能构造出一棵树结构
boolean validTree(int n, int[][] edges) {
    // 初始化 0...n-1 共 n 个节点
    UF uf = new UF(n);
    // 遍历所有边，将组成边的两个节点进行连接
    for (int[] edge : edges) {
        int u = edge[0];
        int v = edge[1];
        // 若两个节点已经在同一连通分量中，会产生环
        if (uf.connected(u, v)) {
            return false;
        }
        // 这条边不会产生环，可以是树的一部分
        uf.union(u, v);
    }
    // 要保证最后只形成了一棵树，即只有一个连通分量
    return uf.count() == 1;
}

class UF {
    // 见上文代码实现
}

如果你能够看懂这道题的解法思路，那么掌握 Kruskal 算法就很简单了。

Kruskal 算法

所谓最小生成树，就是图中若干边的集合（我们后文称这个集合为 mst，最小生成树的英文缩写），你要保证这些边：

1、包含图中的所有节点。

2、形成的结构是树结构（即不存在环）。

3、权重和最小。

有之前题目的铺垫，前两条其实可以很容易地利用 Union-Find 算法做到，关键在于第 3 点，如何保证得到的这棵生成树是权重和最小的。

这里就用到了贪心思路：

将所有边按照权重从小到大排序，从权重最小的边开始遍历，如果这条边和 mst 中的其它边不会形成环，则这条边是最小生成树的一部分，将它加入 mst 集合；否则，这条边不是最小生成树的一部分，不要把它加入 mst 集合。

这样，最后 mst 集合中的边就形成了最小生成树，下面我们看两道例题来运用一下 Kruskal 算法。

第一题是力扣第 1135 题「最低成本联通所有城市」，这是一道标准的最小生成树问题：

每座城市相当于图中的节点，连通城市的成本相当于边的权重，连通所有城市的最小成本即是最小生成树的权重之和。

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
java复制代码int minimumCost(int n, int[][] connections) {
    // 城市编号为 1...n，所以初始化大小为 n + 1
    UF uf = new UF(n + 1);
    // 对所有边按照权重从小到大排序
    Arrays.sort(connections, (a, b) -> (a[2] - b[2]));
    // 记录最小生成树的权重之和
    int mst = 0;
    for (int[] edge : connections) {
        int u = edge[0];
        int v = edge[1];
        int weight = edge[2];
        // 若这条边会产生环，则不能加入 mst
        if (uf.connected(u, v)) {
            continue;
        }
        // 若这条边不会产生环，则属于最小生成树
        mst += weight;
        uf.union(u, v);
    }
    // 保证所有节点都被连通
    // 按理说 uf.count() == 1 说明所有节点被连通
    // 但因为节点 0 没有被使用，所以 0 会额外占用一个连通分量
    return uf.count() == 2 ? mst : -1;
}

class UF {
    // 见上文代码实现
}

这道题就解决了，整体思路和上一道题非常类似，你可以认为树的判定算法加上按权重排序的逻辑就变成了 Kruskal 算法。

再来看看力扣第 1584 题「连接所有点的最小费用」：

比如题目给的例子：

1
css复制代码points = [[0,0],[2,2],[3,10],[5,2],[7,0]]

算法应该返回 20，按如下方式连通各点：

很显然这也是一个标准的最小生成树问题：每个点就是无向加权图中的节点，边的权重就是曼哈顿距离，连接所有点的最小费用就是最小生成树的权重和。

所以解法思路就是先生成所有的边以及权重，然后对这些边执行 Kruskal 算法即可：

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
java复制代码int minCostConnectPoints(int[][] points) {
    int n = points.length;
    // 生成所有边及权重
    List<int[]> edges = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int xi = points[i][0], yi = points[i][1];
            int xj = points[j][0], yj = points[j][1];
            // 用坐标点在 points 中的索引表示坐标点
            edges.add(new int[] {
                i, j, Math.abs(xi - xj) + Math.abs(yi - yj)
            });
        }
    }
    // 将边按照权重从小到大排序
    Collections.sort(edges, (a, b) -> {
        return a[2] - b[2];
    });
    // 执行 Kruskal 算法
    int mst = 0;
    UF uf = new UF(n);
    for (int[] edge : edges) {
        int u = edge[0];
        int v = edge[1];
        int weight = edge[2];
        // 若这条边会产生环，则不能加入 mst
        if (uf.connected(u, v)) {
            continue;
        }
        // 若这条边不会产生环，则属于最小生成树
        mst += weight;
        uf.union(u, v);
    }
    return mst;
}

这道题做了一个小的变通：每个坐标点是一个二元组，那么按理说应该用五元组表示一条带权重的边，但这样的话不便执行 Union-Find 算法；所以我们用 points 数组中的索引代表每个坐标点，这样就可以直接复用之前的 Kruskal 算法逻辑了。

通过以上三道算法题，相信你已经掌握了 Kruskal 算法，主要的难点是利用 Union-Find 并查集算法向最小生成树中添加边，配合排序的贪心思路，从而得到一棵权重之和最小的生成树。

最后说下 Kruskal 算法的复杂度分析：

假设一幅图的节点个数为 V，边的条数为 E，首先需要 O(E) 的空间装所有边，而且 Union-Find 算法也需要 O(V) 的空间，所以 Kruskal 算法总的空间复杂度就是 O(V + E)。

时间复杂度主要耗费在排序，需要 O(ElogE) 的时间，Union-Find 算法所有操作的复杂度都是 O(1)，套一个 for 循环也不过是 O(E)，所以总的时间复杂度为 O(ElogE)。

本文就到这里，关于这种贪心思路的简单证明以及 Prim 最小生成树算法，我们留到后续的文章再聊。

＿＿＿＿＿＿＿＿＿＿＿＿＿

查看更多优质算法文章 点击我的头像，手把手带你刷力扣，致力于把算法讲清楚！我的 算法教程 已经获得 90k star，欢迎点赞！

本文转载自: 掘金

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

发表于

题目介绍

力扣44题：leetcode-cn.com/problems/wi…

image.png

image.png

分析

我们来看这样一个表

image.png
其中，横轴为string s，纵轴为pattern p，这个表第(m,n)个格子的意义是:【p从0位置到m位置】这一整段，是否能与【s从0位置到n位置】这一整段匹配
 
也就是说，如果表格的下面这一个位置储存的是T(True)：
说明，”adcb”和”a*b”这一段是可以匹配的，你不用管前面发生了什么，你只要知道，这两段是匹配的，这就是动态规划为什么很棒棒

image.png

好，我们回到最初的起点。那么我们如何在这个表格上愉快地行走呢？

我在(START,START)这个位置放了一个T，这就是我们开始行走的位置，只有在T时才能继续往下走

image.png
那么从T可以往哪个方向走？

这道题是一个字符串匹配题，那字符串匹配肯定是不能回头的，你不可能在”abcde”里面倒着走，比如从e走到d

这个“不能倒着走”的规定，反映到我们的表格当中，就是只能往右下角走，大家可以细品一下为什么
(往右走、往下走也是有可能的，待会儿我们再说；反正左、上、左上角是不可能的，因为不能倒着走！)

往右下角走，我来举个例子，比如从刚才的初始位置出发，往右下角走一格，来到(a,a)这个位置，发现新引入的这两个字母正好匹配，于是我们在这里记录一个“T”。

image.png

就是这么简单，如果p和s里只有字母，没有”*”和”?”这两个东西，每次你只要从原来T的某个格子往右下角走一格，如果新引入的两个字母正好匹配，你就可以在新的格子里记录一个T。
再敲一次黑板：只能从T的格子走，如果某个格子里没有东西(即False)，你是不可以从那里出发的。
 
下面我们来介绍”*”和”?”

我为什么在标题里称这个表格为一个棋盘，是因为我觉得这像是一个下棋游戏，我们知道，中国象棋里每个棋子的功能都不同，像小兵每次只能直走一格，但车却可以直走任意格，还有的棋子则能跳着走

我们这里，普通字母如a、b就像是小兵角色，遇到他们只能右下走一格,走完这一步后判断新引入两个字母是否匹配才能记录T；

而”*“和”?”则是有特殊技能的角色！

角色：”*”
特技：铲平道路
描述：如果这一行是”*”，可以从上一行的任意T出发，向下、右铲平这一行的任意道路

示例：

image.png

所到之处，皆为平地

“*“可以从原来T向正下方走的原因：星号可以匹配空串

“*“可以铲平所有右边道路的原因：星号可以匹配任意长度字符串
大家可以品一品这两个原因。
 
在讲解另一个狠角色”?”之前，我们再往下走两步，巩固一下之前的知识。接下来我们在pattern里遇到了一个b，它是一个普通字母，所以只能从上一行某个T往右下角走到达，而且字母匹配才能记录T，于是我们发现可以走这两步：

image.png

角色：”?”
特技：狸猫换太子
描述：如果这一行是”?”，从上一行某个T也只能向右下角走，但不必匹配字母就能记录T

示例：

image.png
只要有T就可以直接往右下角走一格，不用在意字母。这里太子“e”被狸猫”?”抵消了

wow，一下子来到了最后一格，小兵走一格就可以liao

image.png

要判定是否成功匹配，只要看一个格子！！如果最最右下角的格子是T，那就是匹配成功了，不用在意之前到底发生了什么，所以我们成功了，

举个例子，像这种情况(我把s的最后一个字母b换成了e)就是不成功了：

image.png

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
java复制代码class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] f = new boolean[m + 1][n + 1];
        
        f[0][0] = true;
        for(int i = 1; i <= n; i++){
            f[0][i] = f[0][i - 1] && p.charAt(i - 1) == '*';
        }
        
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                //直接往右下角移动
                if(s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?'){
                    f[i][j] = f[i - 1][j - 1];
                }
                if(p.charAt(j - 1) == '*'){
                    f[i][j] = f[i][j - 1] || f[i - 1][j];
                }
            }
        }
        return f[m][n];
    }
}

本文转载自: 掘金

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

发表于

SpringMVC以及原理

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

重新复习后端的知识。

一、了解SpringMVC

MVC(Model View Controller)是一种软件设计的框架模式， MVC也就是模型(Model)、视图(View)、控制器(Controller)的简写，是将业务逻辑、数据、显示分离的方法来组织代码，主要作用是降低了视图与业务逻辑间的双向偶合，从而实现前后端代码的分离。

三个核心部分：

Model（模型）：数据模型，提供要展示的数据，因此包含数据和行为，可以认为是领域模型或JavaBean组件（包含数据和行为），不过现在一般都分离开来：Value Object（数据Dao） 和 服务层（行为Service）。也就是模型提供了模型数据查询和模型数据的状态更新等功能，包括数据和业务。

View（视图）：负责进行模型的展示，一般就是我们见到的用户界面，客户想看到的东西。在web开发中就是jsp页面。

Controller（控制器）：接收用户请求，委托给模型进行处理（状态改变），处理完毕后把返回的模型数据返回给视图，由视图负责展示。也就是说控制器做了个调度员的工作。

二、SpringMVC的优点

  • SpringMVC 具有强大的灵活性、非侵入性和可配置型。
  • SpringMVC 分工明确，包括控制器、验证器、命令对象、模型对象、处理程序映射视图解析器，等等，每一个功能实现由一个专门的对象负责完成。
  • 强大而直接的配置方式：将框架类和应用程序类都能作为JavaBean配置，支持跨多个context的引用。
  • 可重用的业务代码：可以使用现有的业务对象作为命令或表单对象，而不需要去扩展某个特定框架的基类。
  • 简单而强大的JSP标签库(Spring Tag Library)：支持包括诸如数据绑定和主题(theme)之类的许多功能。他提供在标记方面的最大灵活性。
  • 可定制的handler mapping和view resolution：Spring提供从最简单的URL映射，到复杂的、专用的定制策略。与某些web MVC框架强制开发人员使用单一特定技术相比，Spring显得更加灵活。

三、SpringMVC 的原理

我们来分析一下这个过程

一次完整的请求在SpringMVC的原理如下图所示：

springmvc.png

1、用户向服务器发送请求，请求被Spring 前端控制器Servelt DispatcherServlet捕获
例如：http://localhost:8080/SpringMVC/hello

如上url拆分成三部分：

http://localhost:8080服务器域名

SpringMVC部署在服务器上的web站点

hello表示控制器

通过分析，如上url表示为：请求位于服务器localhost:8080上的SpringMVC站点的hello控制器。

2、DispatcherServlet对请求URL进行解析，得到请求资源标识符（URI）。然后根据该URI，调用HandlerMapping获得该Handler配置的所有相关的对象（包括Handler对象以及Handler对象对应的拦截器），最后以HandlerExecutionChain对象的形式返回

3、DispatcherServlet 根据获得的Handler，选择一个合适的HandlerAdapter。

4、提取Request中的模型数据，填充Handler入参，开始执行Handler（Controller)。 在填充Handler的入参过程中，根据你的配置，Spring将帮你做一些额外的工作，如 HttpMessageConveter： 将请求消息（如Json、xml等数据）转换成一个对象，将对象转换为指定的响应信息

5、Handler执行完成后，向DispatcherServlet 返回一个ModelAndView对象

6、根据返回的ModelAndView，选择一个适合的ViewResolver（必须是已经注册到Spring容器中的ViewResolver)返回给DispatcherServlet

7、ViewResolver 结合Model和View，来渲染视图

8、将渲染结果返回给客户端

这就是执行一次的完整的请求执行的步骤了，我们只要做视图和控制器的编写，其余都是spring帮我们做了。

今日分享的学习笔记。加油！

本文转载自: 掘金

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

发表于

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

  1. 必备环境与推荐软件

1.1 必备环境

  • mysql
  • redis
  • golang

1.2 推荐软件

  • goland
  • navicat
  • runapi

  1. 项目初始化

  • 创建项目

在这里插入图片描述

  • 创建文件夹

在这里插入图片描述

  • 项目结构
1
2
3
4
5
6
7
8
9
10
11
12
复制代码mall/
├── api
├── cache
├── conf
├── middleware
├── model
├── pkg
│  ├── e
│  ├── util
├── routes
├── serializer
└── service
1
2
3
4
5
6
7
8
9
10
diff复制代码- api : 用于定义接口函数
- cache : 放置redis缓存
- conf : 用于存储配置文件
- middleware : 应用中间件
- model : 应用数据库模型
- pkg/e : 封装错误码
- pkg/util : 工具函数
- routes : 路由逻辑处理
- serializer : 将数据序列化为 json 的函数
- service : 接口函数的实现
  • go mod 管理包依赖

在这里插入图片描述

  • 换源

在这里插入图片描述

  1. 配置文件初始化

在conf文件夹下创建config.ini和conf.go
在这里插入图片描述

3.1 config.ini

先进行mysql的配置

1
2
3
4
5
6
7
8
9
10
11
12
ini复制代码#debug开发模式,release生产模式
[service]
AppMode = debug
HttpPort = :3000

[mysql]
Db = mysql
DbHost = 127.0.0.1
DbPort = 3306
DbUser = root
DbPassWord = root
DbName = mail_db

3.2 conf.go

  • 配置文件
1
2
3
4
5
6
7
8
9
10
11
go复制代码var (
	AppMode  			string
	HttpPort 			string

	Db         			string
	DbHost     			string
	DbPort     			string
	DbUser     			string
	DbPassWord 			string
	DbName     			string
)
  • 读取配置文件
1
2
3
4
5
6
7
8
9
10
11
12
go复制代码func Init() {
	//从本地读取环境变量
	file, err := ini.Load("./conf/config.ini")
	if err != nil {
		fmt.Println("配置文件读取错误，请检查文件路径:", err)
	}
	LoadServer(file)
	LoadMysqlData(file)
	//MySQL
	path := strings.Join([]string{DbUser, ":", DbPassWord, "@tcp(", DbHost, ":", DbPort, ")/", DbName, "?charset=utf8&parseTime=true"}, "")
	model.Database(path)
}
  • 加载配置
1
2
3
4
5
6
7
8
9
10
11
12
13
go复制代码func LoadServer(file *ini.File) {
	AppMode = file.Section("service").Key("AppMode").String()
	HttpPort = file.Section("service").Key("HttpPort").String()
}

func LoadMysqlData(file *ini.File) {
	Db = file.Section("mysql").Key("Db").String()
	DbHost = file.Section("mysql").Key("DbHost").String()
	DbPort = file.Section("mysql").Key("DbPort").String()
	DbUser = file.Section("mysql").Key("DbUser").String()
	DbPassWord = file.Section("mysql").Key("DbPassWord").String()
	DbName = file.Section("mysql").Key("DbName").String()
}

3.3 main函数

在main函数中进行初始化配置
在这里插入图片描述

还有一些配置没有写进去的。redis、七牛云的配置啥的。

我们后面用到的时候才补上去吧。

本文转载自: 掘金

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

发表于

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

前言

Kubernetes ，简称 K8s ，这个 8 是指名字中间的 8 个字符“ubernete”。是一个开源的，用于管理云平台中多个主机上的容器化的应用，K8s 的目标是让部署容器化的应用 简单 并且 高效（powerful）, K8s 提供了应用部署，规划，更新，维护的一种机制。

概述

K8S是谷歌在2014年开源的容器化集群管理系统。我们可以使用K8S进行容器化应用部署， 并且K8S利于应用的扩展，使项目部署更加简洁高效。

特性

1. 自动部署

基于容器对应用自动部署
2. 自我修复
当容器失败时，会对容器进行重启，多节点情况下会自动切换节点

当所有节点都有问题时，会对容器进行重新部署和调度
3. 水平扩展
通过简单的命令扩展和剪裁应用服务
4. 服务发现
支持服务发现和负载均衡
5. 滚动更新
可以根据应用的变化，对应用容器运行的应用，进行一次性或者批量式更新
6. 版本回退
对部署的应用，即时的进行版本回退操作
7. 密钥和配置管理
在不重新构建镜像的情况下，部署和更新密钥和应用配置，类似热部署
8. 存储编排
支持系统存储挂载及应用，存储系统支持本地、网络存储、公共云存储服务
9. 批处理
提供一次性任务，定时任务，满足批量数据处理和分析的场景。

集群架构组件

Master组件(主控节点)

1. API server

集群统一入口，以restful方式，交给etcd存储

2. scheduler

节点调度，选择node节点应用部署

3. controller-manager

集群中后台统一控制，处理集群中常规后台任务，一个资源对应一个控制器

4. etcd

存储系统，用于保存集群相关的数据

node组件(工作节点)

1. kubelet

master排到node节点代表，管理本机容器的各种操作

2. kube-porxy

提供网络代理，负载均衡等操作

核心概念

1. Pod

  • 最小部署单元
  • 一组容器的集合
  • 共享网络
  • 生命周期是短暂的，重启会生成新的Pod

2. Controller （创建pod）

  • 确保预期的pod副本数量
  • 无状态应用部署 (拿来即用)
  • 有状态应用部署 (使用依赖某些条件)
  • 确保所有node运行同一个pod
  • 一次性任务和定时任务

3. Service

定义一组pod的访问规则

本文转载自: 掘金

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

发表于

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

分类 最好时间复杂度 平均时间复杂度 最坏时间复杂度 空间复杂度 稳定情况
直接插入排序 O(n) O(n^2) O(n^2) O(1) 稳定
希尔排序 不稳定
选择排序 O(n^2) O(n^2) O(n^2) O(1） 不稳定
堆排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1） 不稳定
冒泡排序 O(n) O(n^2) O(n^2) O(1） 稳定
快速排序 O(nlog2n) O(nlog2n) O(n^2) O(log2n) 稳定
归并排序 O(nlog2n) O(nlog2n) O(nlog2n) O(n) 稳定

上面主要对比的是排序算法的算法性能分析对比。

其中关于一个算法是否稳定是如何判断的：

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的（来自百度百科）简单来说：假设两个待排序的元素位置a和b 且a在b的前面 位置上对应的关键字是相等的 在排序后他们的相对位置不变则为稳定的

  • 直接插入排序 最好的情况就是直接在其后面插入，最坏的情况就是逆序 每次插入都要循环n遍 （这耶可以看出 待排序列越有序 效率就越高 ）
  • 选择排序
    要选数据再把选好的数据放在后面 所以无论序列是否有序时间复杂度都是n^2
  • 希尔排序 （缩小增量排序）
    他是不稳定的 因为根据希尔排序的过程我们可以看到 每次他是以一个增量来选择一个分组 在这个分组中进行排序 则相对位置就有可能改变
  • 冒泡排序
    当数据有序是 其不用进行交换 只需要遍历一遍序列即可，但若数据无序 则需要的时间复杂度就是n^2
    因为冒泡排序主要是对小于或则大于的数据才会进行交换 所以是稳定的算法
  • 快速排序
    他的性能好坏主要是对于取这个基准数据要选的好 所以他最好也要nlog2n
  • 堆排序
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
css复制代码//建堆
void BuildMaxHeap(ElementType A[], int len) { 
      for (int i = len / 2; i > 0; i--) { 
      HeadAdjust(A, i, len);
      }
}

//调整为大顶堆
void HeadAdjust(ElementType A[], int k, int len) {
  A[0] = A[k];
  for (int i = 2 * k; i <= len; i *= 2) {
    if (i < len && A[i] < A[i + 1]) {i++;}
    if (A[i] <= A[0]) break;
    else {
      A[k] = A[i];
      k=i;
    }
  }
  A[k] = A[0];
}

//堆排序 不断调整位置
void HeapSort(ElementType A[], int len) {
  BuildMaxHeap(A, len);
  for (int i = len; i > 1; i--){
    swap(A[i], A[1]); //交换位置
    HeadAdjust(A, 1, i - 1);
  }
  
}

从上面的代码进行分析 我们建堆 从最后一个非叶子结点向根结点遍历（倒着录）判断其左右子树是否需要调整 调整完后又向上进行比对 调整直到比对到根结点 以此类推 所以根据这个代码可知其时间复杂度为nlog2n

本文转载自: 掘金

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

0%