阿烫的后花园

烫烫烫烫烫烫

并查集是一种树形的数据结构,顾名思义,它用于处理一些不交集的 合并 及 查询 问题。 它支持两种操作:查询、合并。查询用于查找元素在哪个子集中,合并用于将两个子集合并成一个。

disjoint-set

这是一个什么样的结构体?一个 int[] fa 即可。每个结点都只有一个父节点, fa[3] == 1,表示的是 3 号结点的父节点为 1,特别的,祖父结点的父节点为本身。

初始化

首先是初始化,每个结点的父节点设置为自己。

1
2
3
4
5
6
7
public void init(int n) {
fa = new int[n];
// 每个结点为一个子集
for(int i = 0; i < n; i++) {
fa[i] = i;
}
}

查询

查询操作是查找一个结点的祖宗结点的过程,简单递归即可。

1
2
3
4
5
6
public void find(int node) {
if(fa[node] == node) {
return node;
}
return find(fa[node]);
}
路径压缩

我们在查询之后,得到了某个结点的祖宗结点。如果不做优化,下次查询该结点可能还需要很多步,纯属浪费,我们可以直接将该结点,提到祖宗结点的下一层,下次查询非常快。

路径压缩

啰嗦写法,但易懂。

1
2
3
4
5
6
7
8
9
public void find(int node) {
if(fa[node] == node) {
return node;
}
int p = find(fa[node]);
// 将该结点的父节点直接设置为祖宗结点
fa[node] = p;
rerturn p;
}

简单写法。

1
2
3
4
5
6
public void find(int node) {
if(fa[node] != node) {
fa[node] = find(fa[node]);
}
rerturn fa[node];
}

合并

1
2
3
4
5
6
public void union(int x, int y) {
x = find[x];
y = find[y];
// 将 x 的祖先变成 y 的儿子
fa[x] = y;
}

应用

哪些问题可以使用并查集来解决?

  1. 查找元素属于哪个集合
  2. 判断两个元素是否在同一个集合
  3. 计算集合的个数,森林中子森林的个数。

心得

并查集一般都是使用 int [] 来存储数据,但一些情况下题目提供的是字符串或者其它对象,我们需要将这些元素映射到数组 int [],同时使用一个 Map 来存储原字符串和 int [] 中下标的对应关系,即存下标。可以看例题 399 题,「除法求值」。

另外还有一些题目,不再是简单的并查集,并查集中除了 fa[] 数组,还需要维护一些其他数据,这就r是带权并查集,还是可以看「除法求值」这一题。

目的

对于 Java 开发者来说,我认为最好了解下 Kotlin,它确实提升了开发效率,有非常多的优点。这篇文章将介绍 Kotlin 的现状和一些优秀特性,并和 Java 做对比。希望大家能对这个语言感兴趣,平常有一些小玩意的话,也可以用 Kotlin 尝试一下。

什么是 Kotlin?

Kotlin 是一种开源静态类型编程语言,面向 JVM、Android、JavaScript 和 Native。它由 JetBrains 开发。该项目始于 2010 年,第一个官方 1.0 版本于 2016 年 2 月发布。

它能做什么?

  1. Android 开发,2017 年谷歌宣布 Kotlin 为开发 Android 的首选语言。
  2. 服务端开发,与 JVM 100% 兼容,可以使用现有的框架。Spring 也在加快对 Kotlin 的支持,https://start.spring.io/ 上 Language 可选 Kotlin,且部分源代码已使用 Kotlin 改写,博客中还有非常多相关文章。
  3. Web开发,在针对 JavaScript 时,Kotlin 会转译为 ES5.1 并生成与包括 AMD 和 CommonJS 在内的模块系统兼容的代码。
  4. 原生开发,Kotlin/Native 是 Kotlin 项目的一部分,它将 Kotlin 编译为无需 VM 即可运行的特定于平台的代码。(目前处于测试阶段)

发展

  1. JetBrains 于 2011 年推出 Kotlin
  2. 2016 年发布第一个稳定版本 Kotlin 1.0
  3. 2017 年 Google 宣布 Kotlin 正式成为Android 的开发首选语言

2021 开发者生态系统现状

兼容性

Kotlin 与 Java 100% 兼容,可以使用所有的现有框架,例如 Spring、Vert.x。两种语言也可互操作,可以轻松地从 Java 调用 Kotlin 代码或者从 Kotlin 调用 Java 代码。IDE 中还内置了一个自动化的 Java 到 Kotlin 的转换器,可简化现有代码的迁移。但生产中,还是不太建议这样操作,一是转换的代码可读性可能不符合你的期望,二是如果类特备复杂,则影响范围较大有一定风险。可根据类的复杂度,自行抉择是否转换。

(有一句俗话,Java 最好的第三方库是 Kotlin。

优势

Kotlin 更简洁,根据官方的数据,**代码行数约减少了 40%**。

其次,空安全,程序不再容易 NPE 的影响。

其他高级特性,如智能转换、高阶函数、扩展函数等等,提供了编写富有表现力的代码的能力。

难学吗?

Kotlin 的灵感来自 Java、C#、JavaScript、Scala 和 Groovy 等语言,在下面的特性介绍中可以看到很多其他语言的影子。它的基础语法非常易于学习,可以在几天内轻松上手、阅读和编写 Kotlin。 但如果想要学习更多高级功能可能需要更长的时间,但总体而言,它不是一门复杂的语言。

由于 Kotlin 也基于 JVM,可以反编译字节码,再将其转为 Java,这是学习 Kotlin 一种较好的方式,能快速理解。

特性

空安全

在平常的开发和自测过程中,遇见最多的异常可能就是 NPE 了。Kotlin 吸取了 C# 的做法,从源头上抓起,区分了可空引用和不可空引用。空引用:十亿美元的错误

例如,常规的 String 类型的变量就不能容纳 null,在变量类型后面加上一个问号,才表明这个变量可以为 null。如果尝试将一个可空类型的变量直接赋值给一个不可空类型变量,或者访问一个可空类型变量的属性,在编译编译阶段,都会报错。

在语法层面强制 null,这点从实际工程角度来说是非常有利的。

1
2
3
4
5
6
// Kotlin
var output: String
output = null // Compilation error

val name: String? = null // Nullable type
println(name.length()) // Compilation error

如果一个变量 b 可能是空,那该如何访问它的属性?

判断 null

这和 Java 几乎差不多。先判断是否为 null,不为 null 再操作

1
2
// Kotlin
val l = if (b != null) b.length else -1
安全的调用 ?.

或者可以使用安全调用操作符 ?. :

1
2
3
4
5
// Kotlin
val a = "Kotlin"
val b: String? = null
println(b?.length)
println(a?.length) // 无需安全调用

如果 b 非空,就返回 b.length, 否则返回 null, b?.length 表达式的类型是 Int?

在这个例子中,安全调用看起来很普通,但在链式调用中能简化非常多代码。例如,在业务中经常会获取某个嵌套很深的属性,在 Java 中,就是要做逐层判断,或者使用 Java8 新增的 Optional 类:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Java 逐层判断
if(a != null) {
if (a.b != null) {
if (a.b.c != null) {
// 在此处访问 d 属性
ans = a.b.c.d;
}
}
}

// Java 使用 Optional,但还是有不适感
Optional.ofNullable(a)
.map(it -> it.b)
.map(it -> it.c)
.map(it -> it.d)
.get()

// Kotlin 安全操作符 一行即可
val d = a?.b?.c?.d
Elvis 操作符 ?:

当我们有一个可空的引用 b 时,我们可以说“如果 b 非空,我使用它;否则使用某个非空的值”:

1
2
3
4
5
6
7
8
9
// Java
if(b != null) {
return b.length;
} else {
return -1;
}

// Kotlin
return b?.length ?: -1

如果左侧的 b?.length 不为空,那就返回,否则就返回右侧的表达式。仅当左侧为空时,才会对右侧进行运算。

由于 throw 和 return 在 Kotlin 中都是表达式,所以非常方便用于检测一些入参或者快速返回:

1
2
3
4
5
6
// Kotlin
fun foo(node: Node): String? {
val parent = node.getParent() ?: return null
val name = node.getName() ?: throw IllegalArgumentException("name expected")
// ……
}
!! 操作符

这是不优雅的操作,这是非空断言运算符,可以将任何值转换非空类型,如果为空,则会抛出异常,所以使用该运算符可能会得到一个 NPE

1
val l = b!!.length

协程

和 Java 相比,协程是 Kotlin 一个新颖的概念,不过协程不是 Kotlin 提出的概念。在网上搜索协程,我们会看到:

  • Kotlin 官方文档上说「本质上,协程是轻量级的线程」。
  • 很多博客提到「不需要从用户态切换到内核态」、「是协作式的」等等。

协程早在 1958 年就被 Melvin Conway 提出并用用于构建汇编程序,协程是一种编程思想,并不局限于特定的语言。

从 Java 开发者的角度去理解 Coroutines 和 Threads 的关系:

  • 我们所有的代码都是跑在线程中,而线程是跑在进程中的。
  • 协程没有直接和操作系统关联,操作系统并不知道协程的存在。但它不是空中阁楼,它也可以跑在线程中,可以是单线程,也可以是多线程。
  • 单线程中的协程总的执行时间并不会比不用协程少。

而 Kotlin 的协程,它本质上只是线程池的包装,封装成一套好用的 API,Java仅仅是没有解决写得优雅这个问题。

由于 Android 的 UI 主线程不能阻塞,所以所有 IO 等耗时操作都要放在 work 线程中,并使用异步回调的方式来更新UI,导致会有大量的回调地狱。因此协程在 Android 上有非常明显的优势,能用同步的方式写出异步+回调的非人类代码。

而对于服务端来说,虽然也可以再一些阻塞态问题上使用协程,但目前都是同步编程,协程的效益并没有那么明显,如果使用的是异步编程框架,则有质的飞越。

参数默认值

函数参数可以有默认值,当省略相应的参数时使用默认值。否则就需要通过重载方法来实现参数默认值,如果有4个可选参数,则要写 2^4 = 16 个重载方法,而带有这个语法的语言(js、c++、python)会有明显优势。

1
2
3
4
5
6
7
8
// Kotlin
fun bar(a:Int, b: String = "hello", c: Int = 0) {}

// Java 重载
void bar(int a, String b) { bar(a, b, 0);}
void bar(int a) { bar(a, "hello", 0);}
void bar(int a, int c) { bar(a, "hello", c);}
void bar(int a, String b, int c) {}

命名参数

在工程中,如果一个方法的参数过多,将参数依次对应起来是件比较麻烦的事情,尤其是当所有参数类型都一致的时候,更需要小心。如果对错了,编译能通过,但会出现逻辑错误,此类 bug 可能要排查很久。

而 Kotlin 在函数调用中可以使用命名参数,还可以自由更改它们的列出顺序,如果要使用它们的默认值,可以完全忽略此参数。

1
2
3
4
5
6
7
8
// Java  入参过多,且类型都相似
void bar(int a, int b, int c, int d, int e) {}

// Kotlin
// 方法定义
fun bar(a: Int, b: Int, c: Int, d: Int, e: Int) {}
// 方法调用
bar(c = 3, d = 4, e = 5, a = 1, b = 2)

扩展函数

对于 Java 而言,如果想扩展一个类的新功能需要继承原来的类,或者使用装饰者这样的设计模式。但有的类来自第三方库,无法修改,或者被 final 修饰,这些情况下,Java 将无能为力,只能使用静态方法,将此类的对象传入进去。而 Kotlin 的扩展方法则无任何限制,新增的函数就像原始类本来就有的函数一样,可以用普通的方法调用。(如果查看字节码,会发现其实现就是静态方法,第一个入参为扩展类的对象)

Kotlin 鼓励开发者尽量精简类的定义,一个类只定义框架,工具函数可以通过外部扩展一点点地添加,尽量不改动原有的类,这也是扩展方法的意义,让代码更加简单和整洁。

Java 里的许多工具类,比如 Collections、Arrays、Objects 等等,它们提供了一系列静态方法来充当工具函数,通过参数传入被操作的对象,既不直观又冗长无比,Kotlin 将这些常用的方法都改成了扩展方法,我们可以非常方便的使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 自义定一些扩展方法
// 为所有类新增一个 toJson 方法,用于转成 json
fun Any.toJson(): String {
return gson.toJson(this);
}

// 还可以为可空类型做扩展,将一些常用的空判断放在扩展方法中
fun Any?.toString(): String {
if(this == null) {
return "null"
}
return toString();
}

// Kotlin 定义好的一些常用扩展方法
fun String.toInt(): Int = java.lang.Integer.parseInt(this)
fun String.toLong(): Long = java.lang.Long.parseLong(this)
String.toBigDecimal(): java.math.BigDecimal = java.math.BigDecimal(this)
// 还有其他 todouble, tofloat ...

// 集合判空 etc...
public inline fun <T> Collection<T>?.isNullOrEmpty(): Boolean {
return this == null || this.isEmpty()
}

扩展是静态解析的,扩展并不能真正的修改他们所扩展的类,通过定义一个扩展方法或熟悉,并没有在类中插入一个新成员,仅仅是通过该类的变量用点表达式去调用这个新函数。

如果一个类定义有一个成员函数和一个扩展函数,且两个函数有完全一样的方法签名,那么只会调用成员函数。

扩展属性

与函数类似,Kotlin 支持扩展属性,当一个类的某些属性可以由该类的其他属性推导出来时,可以使用扩展属性。它只是看着像操作属性,实际上还是方法的访问。

1
2
3
4
5
6
7
8
9
10
11
12
13
open class Student(
val stuNo: Int,
var name: String,
val englishScore: Int,
val chineseScore: Int,
val mathScore: Int
)

// 判断是否通过了考试
var Student.pass: Boolean
get() = englishScore >= 60 && chineseScore >= 60 && mathScore >= 60
// 这里的 set 方法单纯演示
set(value) {name = value.toString()}

泛型

Kotlin 泛型与 Java 泛型相似,大都只是名字概念上的变化。这里只讲讲 Kotlin 增强的部分。

由于类型擦除, Java 和 Kotlin 的泛型类型实参都会在编译阶段被擦除,无法知道实际类型,这个问题,在 Java 中的解决方案通常是额外传递一个 Class 类型的参数。但 Kotlin 中存在一个额外手段,即内联函数,此时可以说是【真泛型】。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Java
public <T> void test(Integer arg) {
boolean b = arg instanceof T; // 编译错误
T t = new T(); // 编译错误
T[] array = new T[100]; // 编译错误
T[] array2 = (T[]) new Object[100]; // 警告
}


// Kotlio
// inline 内联, reified 具象化的
inline fun <reified T> test(arg: Int) {
val clazz: Class<T> = T::class.java // 获取泛型的实际类型
val b = arg is T // 判断参数是否是 T 类型
val newInstance = clazz.newInstance() // 创建一个 T 对象
}
应用场景

inline 和 reified 比较有用的一个场景是用在反序列的时候。由于泛型运行时类型擦除的问题,目前用反序列化泛型类时步骤是比较繁琐的,工具类中都需要传入一个 Class 参数,利用 inline 和 reified 我们就可以简化掉这个参数。

1
2
3
4
5
6
val gson = Gson()

// 只需一个参数,无需传入类型信息
inline fun <reified T> toBean(json: String): T {
return gson.fromJson(json, T::class.java)
}

还有一些冷门用法,用于实现不同的返回类型函数重载。无论是 Kotlin 还是 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
// 需要实现一个 英尺转厘米 的方法,返回值可以是不精确的 int 类型,也可以是 double


// 这种方法无法通过编译
fun inchToCm(inch: Double): Int {
val cm: Double = inch * 2.54
return cm.toInt()
}
fun inchToCm(inch: Double): Double {
val cm: Double = inch * 2.54
return cm
}


// 使用 reified,实现不同的返回类型函数重载
inline fun <reified T> inchToCm(inch: Double): T {
val cm: Double = inch * 2.54
return when(T::class) {
Double::class -> cm as T
Int::class -> cm.toInt() as T
else -> throw IllegalStateException("Type not supported")
}
}

fun main() {
val cm1: Int = inchToCm(12.0)
val cm2: Double = inchToCm(12.0)
}

实际工程中,一个可能的情景是:有一个方法,需要被多个方法调用,但每个调用方需要的返回值可能是不同的 BO 对象,因此可以对该方法的返回值进行重载,进行类型转换。

原理

如果要是真泛型,则必须是内联函数。内联函数会将代码平铺到所有的调用点,有多少个调用点,就会将泛型方法编译多少次。 Kotlin 通过调用点知道了传入的类型,平铺后,泛型方法就可以知道泛型的类型了。

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
// 源代码
inline fun <reified T> inlineTest() {
println(T::class.java.name)
}

fun <T> test() {
println("aaa")
}

fun main() {
inlineTest<Int>()
test<Int>()
}

// 将其反编译为 Java 代码后再观察
// main 方法并没有直接调用 inlineTest 方法
public final class KTestKt {
// $FF: synthetic method
public static final void inlineTest() {
int $i$f$inlineTest = 0;
Intrinsics.reifiedOperationMarker(4, "T");
String var1 = Object.class.getName();
System.out.println(var1);
}

public static final void test() {
String var0 = "aaa";
System.out.println(var0);
}

public static final void main() {
int $i$f$inlineTest = false;
String var1 = Integer.class.getName(); // 非调用方法,直接平铺代码并传入调入点的 Integer 类型
System.out.println(var1);
test(); // 非内联方法,调用
}

// $FF: synthetic method
public static void main(String[] var0) {
main();
}
}

高阶函数与 Lambda 表达式

在 Java 里,如果你有一个 a 方法,需要调用另外一个 b 方法,直接调用即可。而如果想在 a 调用时动态设置 b 方法的参数,就要把参数传给 a,再从 a 的内部把参数传给 b:

1
2
3
4
5
6
// Java
int a(int param) {
return b(param);
}
a(1); // 内部调用 b(1)
a(2); // 内部调用 b(2)

如果想动态设置的不是方法参数,而是方法本身呢?比如我在 a 的内部有一处对别的方法的调用,这个方法可能是 b,可能是 c,不一定是谁,我只知道,我在这里有一个调用,它的参数类型是 int ,返回值类型也是 int ,而具体在 a 执行的时候内部调用哪个方法,我希望可以动态设置:

1
2
3
4
5
6
// Java
int a(??? method) {
return method(1);
}
a(method1);
a(method2);

想把方法作为参数传到另一个方法里,这个……可以做到吗?不行,Java 里是不允许把方法作为参数传递的,但有一个历史悠久的变通方案:接口。可以通过接口的方式把方法包装起来:

1
2
3
4
5
6
7
8
9
10
11
12
// Java
public interface Wrapper {
int method(int param);
}

int a(Wrapper wrapper) {
return wrapper.method(1);
}

// 在调用外部方法时,传递接口的对象来作为参数:
a(wrapper1);
a(wrapper2);

而在 Kotlin 里,函数的参数也可以是函数类型的,这是一种 Java 中不存在的类型,这种类型的对象可以当函数来用,还可以作为函数的参数、返回值,以及赋值给变量。这种「参数或者返回值为函数类型的函数」,在 Kotlin 中就被称为「高阶函数」——Higher-Order Functions。所谓的「高阶」,总给人神秘感,其实概念源自于数学中的高阶函数,没有其他特殊功能,唬人的概念罢了。

如下代码,funParam 就是一个函数类型的参数,它接受一个 int 类型的参数,返回类型是 String:

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
// Kotlin 
fun a(funParam: (Int) -> String): String {
// somet code ...
return funParam(1)
}

// 定义一个方法,以 lambda 的形式
val bar: (Int) -> String = { param -> param.toString() }
// 传进去
a(bar)

// 或者直接传进去
a({param -> param.toString()})

// 如果 Lambda 是函数的最后一个参数,你可以把 Lambda 写在括号的外面:
a() { param -> param.toString() }
// 而如果 Lambda 是函数唯一的参数,你还可以直接把括号去了:
a { param -> param.toString() }
// 另外,如果这个 Lambda 是单参数的,它的这个参数也省略掉不写,且有默认名字 it
a { it.toString() }



// 对于一个声明好的函数,不管是你要把它作为参数传递给函数,还是要把它赋值给变量,都得在函数名的左边加上双冒号才行
fun b(param: Int): String {
return param.toString()
}
a(::b)

Kotlin 里「函数可以作为参数」这件事的本质,是函数在 Kotlin 里可以作为对象存在——因为只有对象才能被作为参数传递。赋值也是一样道理,只有对象才能被赋值给变量。但函数本身的性质又决定了它没办法被当做一个对象,函数就是函数,没有类型,也不是对象。那怎么办?Kotlin 的选择是,那就创建一个和函数具有相同功能的对象。怎么创建?使用双冒号,这个是底层的逻辑。Kotlin 的 Lambda 本质也是一个函数类型的对象。

Java 的 Lambda

上面我们提到 Java 可以通过接口来传递方法,即:

1
2
3
4
5
6
7
8
// Java
Wrapper wrapper1 = new Wrapper() {
@Override
public int method(int param) {
return param * 2;
}
};
a(wrapper1);

但看看代码,实在是太长了。于是,Java 从 8 开始引入了对 Lambda 的支持,对于单抽象方法的接口——简称 SAM 接口,Single Abstract Method 接口——对于这类接口,Java 8 允许你用 Lambda 表达式来创建匿名类对象,但它本质上还是在创建一个匿名类对象,它没有属性自己的类型,必须要使用一个接口来接收 Lambda。它只是一种简化写法而已,本质上没有功能上的突破。

1
2
3
// Java Lambda
Wrapper wrapper2 = param -> param * 2;
a(wrapper2);

var、val

在声明一个变量时,我们习惯了敲打两次变量类型,第一次用于声明变量类型,第二次用于构造函数。Kotlin 可以使用 var 让编译器自己去推断类型,Java 10 也支持了这个语法。Kotlin 中还支持 val,表示该变量一旦初始化不可改变,即 final。

1
2
3
4
var codefx = new URL("http://codefx.org");
var connection = codefx.openConnection();
var reader = new BufferedReader(
new InputStreamReader(connection.getInputStream()));

这样可以少敲几个字,但更重要的是,它避免了信息冗余,而且对齐了变量名,更容易阅读。当然,这也需要付出一点代价:有些变量,比如例子当中的 connection,就无法立即知道它是什么类型的。虽说 IDE 可以辅助显示出这些变量的类型,但还是需要光标放上去或者跳转到方法定义查看返回值类型,并且在其他场景下可能就完全不行了,比如在代码评审的时候。

在 new 对象的时候使用 var 推导类型,而在接某个方法的返回值时,使用完整的类型而不是 var,可能是一个比较好的办法,便于阅读。

字符串模板

Java 中,如果要拼接复杂字符串,一般用 StringBuilder 或者 String.format 方法,但如果参数过多,也非常麻烦,参数还可能对岔了。

Kotlin 支持字符串模板,它是一段代码,会计算并将结果返回到字符串中。这块古老的糖从 shell 开始就有了,但 Java 却迟迟缺席。

1
2
3
4
5
// Java
String message = String.format("您好%s,晚上好!您目前余额:%.2f元,积分:%d", "张三", 10.155, 10);

// Kotlin
val message = "您好${user.name},晚上好!您目前余额:${cashAmount + presentAmount}元,积分:$point"

解构

Kotlin 支持将一个对象解构为多个变量,如:

1
val (name, age) = person

这种语法叫做解构声明,解构声明一次创建多个变量,之后可以独立的使用这些变量。这种语法可以用来从一个函数返回多个值。不关心的变量,可以使用下划线 _ 代替。

多返回值

很多场景需要从一个函数中返回两件事,例如,一个状态和一个结果对象。在 Java 中,一般封装成一个对象,或手写 Pair 类,但出参并不好理解,一般都叫 first、second 之类。 但解构时需要正确命名数据,否则也不太好理解。

1
2
3
4
5
6
7
8
// Kotlin
fun getInfo() : Pair<Int, Any> {
// 不能创建任意元组,可以使用内置的数据类型,如 Pair 和 Triple,也可自定义
return Pair(200, Any())
}

// 调用
val (status, data) = getInfo()
解构声明和映射
1
2
3
4
5
6
7
8
9
// for 遍历时,解构声明 Map 中的 Entry 对象
for ((key, value) in map) {
// do something with the key and the value
}

// lambdas 中的解构
map.mapValues { entry -> "${entry.value}!" }
// 未使用的 key 可以用 _ 代替
map.mapValues { (_, value) -> "$value!" }

嵌套函数(本地函数)

在一个复杂方法中,常常会有一些相似逻辑,常规思路就是抽成一个私有方法,有时候作用域还是太大。Kotlin 支持在函数中定义作用域更小局部函数,这点类似于 JavaScript。

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
fun login(user: String, password: String, illegalStr: String) {
// 验证 user 是否为空
if (user.isEmpty()) {
throw IllegalArgumentException(illegalStr)
}
// 验证 password 是否为空
if (password.isEmpty()) {
throw IllegalArgumentException(illegalStr)
}
}


fun login(user: String, password: String, illegalStr: String) {
// 嵌套函数中可以访问在它外部的所有变量或常量,因此不再需要传参 illegalStr
fun validate(value: String) {
if (value.isEmpty()) {
throw IllegalArgumentException(illegalStr)
}
}
validate(user, illegalStr)
validate(password, illegalStr)
}

// 其实还有更简单的方法,使用内置的 require 方法和 lambda 表达式
fun login(user: String, password: String, illegalStr: String) {
require(user.isNotEmpty()) { illegalStr }
require(password.isNotEmpty()) { illegalStr }
}

数据类

从此告别繁琐的 Java 数据类,会自动生成 toString、hashcode、equals、getter、setter、copy 等方法,再也不需要 lombok 了。

1
data class User(val name: String, val age: Int)

但数据类的坑或者用起来不舒服的地方也较多:

  1. 它只有全参构造函数,而一些序列化框架依赖于无参构造函数,此时会出现问题。而且 new 一个数据类的时候就要把所有入参一口气设置好。
  2. Json 字符串可能出现一些字段缺失或者 null,如果数据类的定义字段都不可空,那么序列化报错,怎么办?
    1. 所有字段都加上 ?,可空,那以后所有这个字段的使用都要加上 ?. 也是非常麻烦的,或者再加一个数据类转换一下。
    2. 约束好上游,做好定义,哪些不能为空等。

单例对象

这应该是来自于Scala,连关键字都一模一样。

1
2
object Document {
}

别名

支持为包、类型指定别名。在工程中如果有两个类名一样,包不一样,则容易出错,一些代码必须要写完整的包路径,代码冗长难读。例如 @Service 注解,项目中可能有两个包,一个是org.springframework.stereotype.Service; ,一个是 com.dianping.pigeon.remoting.provider.config.annotation.Service; 每次都需要查看一下 import 的是哪个包,易误导人。

1
2
3
4
5
6
// 包别名,Python、Groovy 都这个语法
import org.springframework.stereotype.Service as SpringService
import com.dianping.pigeon.remoting.provider.config.annotation.Service as PigeonService

// 类型别名,可以一些复杂的类型设置一个别名。 和 Scala 相似,Scala 关键字为 type。
typealias Table = Map<Int, Map<String, Int>>

运算符重载

这个是 C# 和 Scala 的把戏。

1
2
3
data class Point(val x: Int, val y: Int)
operator fun Point.plus(val point: Point) = Point(x + point.x, y + point.y)
Point(1, 2) + Point(3, 4) // Point(x=4, y=6)

没有受检查异常

Kotlin 并没有受检查异常。因为在大型的项目中,它对代码质量的提升极其有限,但是却大大降低了效率。这个灵感大概来源于 C#,可以参考 Why doesn’t C# have checked exceptions?

集合字面量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Java 不愿用糖来吸引小朋友,想快速创建一个带有初始值的集合都比较麻烦
// 1. 最啰嗦的办法,无法使用单个表达式来完成
List<String> colors = new ArrayLis<>();
list.add("red");
list.add("blue");

// 2. 但这样创建出来的 ArrayList 非彼 java.util.ArrayList ,只是个内部类,没有实现 add remove 等方法
List<String> colors = Arrays.asList("red", "blue");

// 3. 使用 Stream
List<String> colors = Stream.of("red", "blue").collect(Collectors.toList());

// 4. 用第三方的轮子 Guava
List<String> colors = ImmutableList.of("red", "blue");

// Kotlin 集合字面量 http://openjdk.java.net/jeps/269
val list = listOf("red", "blue")
val set = setOf("red", "blue")
val map = mapOf("red" to "1", "blue" to "2")

when

Kotlin 提供了非常强大的 when 操作符,是增强版 switch。

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
//Kotlin
when (x) {
1 -> print("x == 1")
2,3 -> print("x == 2 || x ==3")
parseInt(s) -> print("s encodes x") // 可以使用任意表达式作为分支条件,Java 仅仅支持常量
else -> { // 每个 when 表达式都必须要有这个块
print("x is neither 1 nor 2")
}
}


// 支持任意类型的值(调用 equals 方法进行判断), Java 只支持一些基本类型 char, byte, short, int, Character, Byte, Short, Integer, String, or an enum
// 由于智能转换,在类型判断后,也无需再次转换
fun hasPrefix(x: Any) = when(x) {
is String -> x.startsWith("prefix")
else -> false
}


// 还可以无参,用来取代 if-else if链,一直判断直到匹配到一个分支
when {
x.isOdd() -> print("x is odd")
y.isEven() -> print("y is even")
else -> print("x+y is odd.")
}

其他

  • 参考 RxJava 创造出的 Flow

  • 大量简单的流式集合操作 map(), forEach() 等,可以用于替换 Java 的 Stream,Java 3 行,此只需要 1 行。

最后也发现了一个有趣的网站,大家也可以自己再看下。 https://www.kotlinvsjava.com

文章参考:

几个月没更新博客了,为什么呢,大概两件事吧,一个是找工作,入职了美团,二是在做一个App,花费的时间也有点长。

首先,上主页,看看长啥样吧——阿烫的网格账本

为什么要做这个App

做网格计划,需要知道资金账户情况。一般可以使用Excel,但确有一些麻烦的地方,一是上班时候并不方便操作,二是格式并不太好定义,每次操作略麻烦,甚至是记错。
或者也可以单独开通一个证券账户来做网格,但一个人最多只能有三个证券账户的限制的。

于是便有了这个App,便于操作,方便查看数据。

还有一部分原因是闲得慌,找点事情做。

功能设计

  • 新建/编辑网格
  • 网格快速买入卖出
  • 检查更新
  • 实时获取基金净值
  • 登录,同步数据
  • 数据导出Excel
  • 开放配色、自定义布局
  • 对所有数据进行对称加密,秘钥数据只存储本地

开发过程

关于UI

UI 是我的第一大关卡,不怕写代码,就怕搞这种设计,因为我看的太少了,没经验。在墨刀上画了好几种,还有五颜六色的,各种配色各种布局实在是直男,巨丑无比,没得救了。

最后还是换成简单点的吧,配色全部白色,亏损绿色,盈利红色。布局都基本参考【且慢】和【有知有行】,你能在这两个App上看见一些影子。

关于开发

首先还是技术选型,对 flutter 比较感兴趣,因为是跨平台的,后端的话就还是 Kotlin + Vertx。
基本上 flutter 就是边学编写,组件边看边用,工程结构应该很糟糕。

这种创作型的工作,着实让我感到困难,这是第二道关卡。一是没什么好的点子,二是自己画图能力着实很差。为什么最后定成一只鱼呢?因为 网格交易 -> 网 -> 渔网 -> 鱼,多吃鱼肉吧!绘画是找人画的,自己画不来。

有了 logo 原图,要裁剪成 Android 和 IOS 平台所需的大小,有很多第三方工具,如 图标工厂

关于名称

憋了很久没憋出来,后来想到了【阿烫的网格账本】,安装后发现太长了,手机上显示不完,直接省略号了。那就短点吧 【网格账本】,挺好的。

关于上架

大四在百度应用商城上架【我想学】时,比较简单,没有要求一些烦人的文件。

而现在的商城上架App好像基本都要企业资质,软件著作权之类,着实麻烦。

而苹果上架首先要有开发者账号,门票 $99/年,就硬抢呗…

因此要暂缓一下上架了,看看后期有无上架需求。

关于首页

由于App上架都需要官网首页,又不可能真的自己来写吧,于是网上逛了一圈,发现了一个网站可以制作模板 launchaco.com,而自定义域名需要充会员,,,直接wget拉下来放到自己服务器上结束。只能防小白,防不到稍微懂一点的人…

关于基金价格

基金价格和名称一开始都是使用的阿里云市场上的第三方付费服务,一是价格贵,二发现部分基金无法获取到实时价格,所以切换数据源为天天基金。

复盘

  1. 一开始功能差不多都确定好了,一直到开发结束,也几乎没大的变更,这是一个好的地方。我在大四开发【我想学】App的时候,功能在一开始没完全确定,不停地改,数据模型也经常发生变更,改起来着实是个大工程。。。
  2. 但这次 UI 一开始没设计好,做了两版。第一版的 UI,都是基于弹窗,新增编辑网格品种都是使用弹窗,新增编辑交易也都是基于弹窗,还有删除等等也都是弹窗。一开始的为什么想这样做呢,因为觉得这样交互最简单,不用跳到跳去,用户使用更方便,开发也可能更方便。实际上,当我开发完成后,才发现并不是那回事,首先,修改交易有六个输入框,都放在弹窗中过于拥挤,过于丑陋,甚至可能会叠两层弹窗,且弹窗的开发并没有想象中的那么简单,还比页面稍微复杂一些。于是大部分的弹窗又全部改成了新页面,浪费了很多时间精力。
  3. 缺乏 flutter 工程经验。由于是初次学习使用,并不清楚一个真正的 flutter 应用的代码结构,层级是什么样的,也不清楚 dart 的编程规范是什么样的,还是使用的 Java 规范,代码复用度似乎也不够,实际代码可能有点糟糕。
  4. 以前使用 Vertx,并没有开发过接口之类的,这次使用了 Vertx 的服务代理,,也遇到了一些问题,对 Vertx 的理解应该更深了。
  5. 对App的上架流程并不了解
  6. 如果是个人开发者,可能更适合做工具型APP,更有市场,小而美。

难乎?甚难。有何难哉?亦不难。

动态规划套路

所有的背包问题都是动态规划。动态规划,一定要明确 「状态」「选择」 ,明确了之后,所有的动态规划都可以套在下面公式中:

1
2
3
4
for 状态1 in 状态1的所有取值:
for 状态2 in 状态2的所有取值:
for ...
dp[状态1][状态2][...] = 择优(选择1, 选择2, ...)

0-1背包问题

问题描述

给你一个可装载重量为 W 的背包,和 N 个物品。每个物品有重量和价值两个属性,第 i 个物品的重量为 wt[i],价值为 val[i],现在让你用这个背包装物品,最多能装的价值是多少?

首先找到状态,有两个,一个是可选的物品,一个是背包的容量,那么我们可以定义状态转移方程:

dp[i][w]: 对于前 i 个物品,当前背包的容量为 w,这种情况下可以装的最大价值是 dp[i][w]

根据此定义,我们想求的最终答案是 dp[N][W],base case 就是 dp[0][..,] = dp[…][0] = 0,因为没有物品或背包的时候,最大价值就是0。

细化上面的框架:

1
2
3
4
5
6
7
8
9
10
11
12
int dp[N + 1][W + 1];
dp[0][...] = 0;
dp[...][0] = 0;

for i in [1...N]:
for w in [1...W]:
dp[i][w] = max(
把物品 i 装进背包,
不把物品 i 装进背包,
);

return dp[N][W];

之后就是选择,如何选择呢,如何在代码中体现这两种选择呢?

还是需要重申一下对 dp 的定义,**dp[i][w]: 对于前 i 个物品,当前背包的容量为 w,这种情况下可以装的最大价值是 dp[i][w]。**。

  1. 如果没有把第 i 个物品装入背包,那么 dp[i][w] 应该等于 dp[i-1][w], 不装嘛,就是继承之前的结果。
  2. 如果把第 i 个物品装入背包了,那么 dp[i][w] 应该等于 dp[i-1][w - wt[i - 1]] + val[i - 1],(因为 i 是从 1 开始的)。如何理解dp[i-1][w - wt[i - 1]]呢,因为我们需要把第 i 个物品放入背包,需要占用 wt[i - 1] 的重量,所以我们要寻找剩余重量限制下w - wt[i-1] 能装的最大价值。

基于以上两种情况,我们就可以翻译出代码了,再加上处理一些边界情况:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int knapsack(int W, int N, int[] wt, int[] val) {
int[][] dp = new int[val.length + 1][wt.length + 1];
for (int i = 1; i <= N; i++) {
for (int w = 1; w <= W; w++) {
if (wt[i - 1] > w) {
// 当前背包背不下
dp[i][w] = dp[i - 1][w];
} else {
// 背包可以背下,选择不背或背的最优质的
dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][wt[i - 1]] + val[i - 1]);
}
}
}
return dp[N][W];
}

完全背包问题

问题描述

这个问题和01背包问题比较相似,唯一的区别就是每种物品都有无数件。从每种物品的角度考虑,与之有关的策略不再是「取」或「不取」两种状态,而是取0件、取1件、…取N件。

这题的状态转移方程和之前的一样:

有两个状态,一个是可选的物品,一个是背包的容量,那么我们可以定义状态转移方程:

dp[i][w]: 对于前 i 个物品,当前背包的容量为 w,这种情况下可以装的最大价值是 dp[i][w]

1
2
3
4
5
6
7
8
9
10
11
12
int dp[N + 1][W + 1];
dp[0][...] = 0;
dp[...][0] = 0;

for i in [1...N]:
for w in [1...W]:
dp[i][w] = max(
把物品 i 装进背包,
不把物品 i 装进背包,
);

return dp[N][W];

那么就是如何用代码描述这两种选择了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int knapsack(int W, int N, int[] wt, int[] val) {
int[][] dp = new int[val.length + 1][wt.length + 1];
for (int i = 1; i <= N; i++) {
for (int w = 1; w <= W; w++) {
if (wt[i - 1] > w) {
// 当前背包背不下
dp[i][w] = dp[i - 1][w];
} else {
// 背包可以背下,选择不背或背的最优质的
dp[i][w] = Math.max(dp[i - 1][w], dp[i][wt[i - 1]] + val[i - 1]);
}
}
}
return dp[N][W];
}

这两者代码区别非常微小。因为完全背包物品有无限个,所以是 dp[i][wt[i - 1]] + val[i - 1] 而不是 dp[i - 1][wt[i - 1]] + val[i - 1],可以再继续拿。

背包变体

1049. 最后一块石头的重量 II

今天偶然发现了一个概念,在线算法和离线算法,以前没有听说过。

简单而言,在线算法可以处理数据流,而离线算法不可以,离线算法必须要在算法开始前就准备好所有数据。

举个例子,插入排序就是个在线算法,哪怕给定的列表已经排完序,我也可以在最后面再添加一个数据,继续重新排序。

插入排序

另外一个在线算法的例子,就是水塘抽样算法,之前有写过这个有趣的算法:蓄水池抽样算法


而离线算法,就要求在算法的一开始就准备好所有数据,如选择排序。
选择排序

https://zh.wikipedia.org/zh-cn/在线算法

2023年3月25日

  1. 梦见我爸想要做平衡车,类似于小米的那种,别人问我为什么要做这个,我说我爸是电工,也还是木工,很厉害的。我和我爸说,这个东西还需要软件的,我之前写过代码,所以想到了 pid 算法,觉得还是蛮简单的,然后我就又想到我需要配一台台式机了,因为我只有公司Mac,写那些东西不是很方便(印象中),还要烧录程序。然后我又想到了我需要去买一些硬件了,比如 stm32f103,等等,可能要花很多钱(想到之前算过,要花几百块吧)。然后我爸也会快做出了原型,用木头做的,我说需要一个扭矩非常大的电机才行,巴拉巴拉巴拉后面忘记了。
  2. 我背着书包,去某个店,然后书包忘记拿了,再回头的时候,书包不见了!非常焦急,因为公司电脑在里面,我就和他们说东西很贵,要3w,然后问我们走了之后谁还来过,店里人说没有人来过了,我就说那

2022年9月9日

英语

梦回英语高考,考前不知道做了什么,被老师训了一顿。然后还有二十多分钟快考试了,老师让我们去考场,别人都距离非常近,但是我在另外一栋楼。遇到了其他在这个楼的,我们跑了很久很久,一直跑,才找到考场。还有几分钟就考试了,我又很尿急,又举手申请上厕所。然后是一个女考官在看厕所,我进去后看到一个有很多水的大池子,就往里面撒了,然后觉得不对劲,又去了小便池,不停地撒啊撒啊撒,很久很久。后来考官进来了看我怎么回事,一边看一边通话说我这没作弊风险。然后就回考场了,以为考试应该已经过了半小时了,很焦虑,却发现听力都没开始,一看试卷,没听力,是让你读口语的。。。
END

2022年2月17日

无题

梦见自己晚上出去上网,在下载东西,很慢。然后等着等着就睡着了,醒来已经是十二点了,翘了半天的课,和老爸说,也没骂我,很奇怪。

割bp

在医院,医生帮我检查dd,然后说bp太长(实际上一点都不长),要割,我说割过了,他说没割好,还要再割,害怕的很,我不想再经历这个了。结果医生二话不说,直接拿起✂️几秒钟结束….然后就疼了好久,很真实的感受。

2022年2月14日
Spring
TlhCNVFUVTNkVWsyVEN0Wk5YQnBkalpMTm5BMVRESm5OVFY1VERWWmFYYzFUSEZITmt3cldqVk1hWEUxTm1WWk5XRXJSMHhwTkhWTVoyOUxOVzlEVHpWTWJVazJXVTg1TlhKTGFEVnZUM28xV1dsM05YQnBkalZ4ZVdvMVlrTlFOa3BEVFRjM2VVMDFjVXR0TlZscGR6VmFTMDAxWVRaNk5XOURWalZaZVRZMVRHbEJOV0ZsVVdKWGVtcG5TVXhzY0dKUWEzVkpkbTVzVEdacmRVbHlkblpKZW05Mk5XcHZjamRVYkhCaU0yNXZZWHBzYkZseWFtZEpUR3BuU1V4cVowbE1iSEJaWm0xblMzSnViVzlVYlcxTEwyOTJOV3B0YVZwUWJtcHZkbTluU1ZoMmRrbDZhM1ZKUkc5MmNtNXVhbkZ1YTNWSlJHOTJjbXhyWWlzck9HcFBZVWxyWldWUGNXVlhLMndyWlVKeEsybEpiblVyT0dwUFZ5dHBUMmxRYms4ck9HcFBhUzl0VDJVM2FpdFhOSFZQWVUxbmRXRmpkWFVyT0dwUFlYUjFLMWNyYkN0VE5XNHJWMnR0ZFNzNGFrOVROR2RQWldKMFQyRlBhV1ZYU1doMVQwRm5aejA5

2021年 8月15日
英语高考
梦见高三复读了,想要努力读书,每天认真做题,但还是没有坚持。高考的时候,前面坐了个英语学霸,我偷偷抄她的考卷,抄了阅读理解的,好像还有一部分选择。但突然就考试结束了,要收卷子了,我答题卡还没有涂,作文还没写,一看分数,65分的作文,还有其他很多分的非选择题都没写,,,绝望,然后就断了。

2021年 8月8日
逃亡
战争,好像是有侵略者,我被迫为侵略者表演节目,后来,侵略者败退,有人要找我们表演节目的清算,于是我们准备逃亡了。正准备逃亡的时候,他们来了,直接交火了。我们有类似防爆盾一样的东西,能抵挡住。后来他们使用了一个新型的炸弹,爆炸的时候没法抵挡,所有人都直接变成了白骨,非常厉害。(突然意识到太bug了,连设置炸弹的人也被炸的只剩白骨了,于是将炸弹范围修改的小一点再重新爆炸),我队友直接就没了,变成骨头了。我用盾牌挡着,温度太高,融化了和我的脸粘在了一起一点点。 于是我就开始跑,跳窗,沿着河一直跑一边扣面具,终于扣掉了,但一直甩不掉追的两个人。后来跳进了河里,在水下面游泳,这才甩掉。后来他们又在关键水位派人监守,我又一直不敢露头,,,后来就忘记了。

2021年 7月20日
高三
梦见了高三的历史老头子,在准备高考,他说,虽然历史不算高考分,但你们如果没考好,也不行不能高考。然后叽叽歪歪说到了自己带领学校致富,带领镇子致富,让我们推选他当校长。然后我还想,这个老头子的气势还的确适合当校长,很会忽悠人。然后又说自己怎么带领大家致富的呢,卖沙子。然后场景就转到外面,到处都是沙子,漫天的沙子,河里也都是沙子,然后还有挖土机不停地往地上倒沙子,然后沙子就漫出来了,漫到了教室里,此时的教室已经变成了盗墓笔记里的那种墓的样子,从上往下各种沟壑、坑,然后沙子就往下漏下来,大家一起叫喊,沙子不停地漏在我们的脸上,还好戴了口罩…没了。

2021年 7月10日
梦见了弯弯,到她家玩,潘晓燕也都在,还有狗狗,蛮大的一个房子,想和她说我在望京。

2021年 7月9日
多贝
又回到了多贝,这次带着源代码回来了。。。还是熟悉的文档转换系统,和朋哥说在新公司做的文档转换系统。解压,打开源代码,说转换思路,各种方案,有多好之类的,,,绝了。。。

2021年 7月7日
梦见up主四脚鸡更新视频了,是baka爱的?结果视频内容有少儿不宜的,直呼这是怎么过审的!
还梦到一个大纸箱子,要用它做饭,把它裁成了一块一块的矩形,裁了一半,说吃不下了,够了。

2021年 7月6日
浇水
梦见回家了,场景很像朱雯琪那个地方,有很大一个院子。种了非常非常多的花草,还有菜。我就和我妈就一个个浇水。然后有的地特别贫瘠特别破烂,全靠化肥搁那顶着,很多白色的,大概就是这样。还有一个破房子,里面有很多多肉。

2021年 6月29日

  1. 莫名其妙梦见好像是写代码,一个 for 循环,依次执行任务。然后有人问我,能不能别用 for 循环,我想一起执行。想了一会,脑子里突然崩出个东西,栅栏 —— CyclicBarrier。(梦里当然是记不得这个类的,醒来后查了查)
  2. 印象中是在一个游戏世界,遇到了一个特别牛逼,土豪玩家,是这个世界的老大姐,名字就一个数字 1 。然后我还透了人家?不过就一下,,,还是个chu,捅破一层膜的感觉很真实。然后就开始进行游戏了,不停地捡地上的奇形怪状的武器、飞镖,然后往别人身上扔,一直扔不中,很气,之后就记不得了。

2021年 6月28日
抽烟
梦见大家都开始抽烟了,我也抽,我妈也抽,而且烟入肺的感觉真的很真实,抽的还很花,直接把整个烟含在嘴里抽。。。

2021年 6月27日
是个春梦,对象是某大学同学,但是比较讨厌的那种,这是怎么回事???

2021年 6月8日
很混乱,还记得以下场景:

  • 陪周彤一起找工作,反正就是呆着了同一个办公室,是个国企,开价8k,周彤想要1w,说计算机行业的都至少1w打底,然后指着我说他也是程序员,在美团,问我:“是吧?” ,我说:“是的,1w是至少的”。于是就成交了。(为什么会梦到她?)
  • 裴乐、我妈还有俩人是谁记不得了,在一起打牌。
  • 和狗子一起玩耍,狗子很调皮,于是拿链子拴住,但是是前腿栓后腿那种,让它别跑那么快……
  • 和裴乐一起看什么演唱会,座位不远处上方有一块布,飘啊飘,颜色还蛮漂亮,于是乐乐就拿着相机拍,然后挡着了一些人,那些人就一直说,但乐乐还是一直拍,说等一等,一会就好了,那群人就一直骂……实际上好久也没拍好,好像拍了很多东西。
  • 好像也还是在演唱会,反正人很多,大家问袁隆平如何看待 明星伙食费一天650元不够吃,袁隆平说了很多话,现场很多人都流泪了,当然也包括我,虽然在梦中,但能感觉到我的身体反应。

2021年 6月1日
多贝
又回到了多贝,此时Java组已经多了好多人了,原来空旷的两行桌子,现在已经坐满了挤不下了,好像也都是实习生。我坐在朋哥右边的位置,我右边还有俩人,一个男的,一个女的,总共有2个妹子,都不太好看印象中。
之后就有一个 bug,我一直和有为争论是谁的锅,争论了好久,明明我才刚来公司哈哈哈哈。

2021年 5月30日
起的很晚,做了好多梦,朦朦胧胧还记得俩

  1. 在老家,自己养海洋宝宝玩,然后当皮球玩,特别Q弹,一直害怕拍坏,但一直没事。后来还泡了两个巨无霸,有半个我那么大,离谱。小孩子很多,很喜欢玩,然后我想把海洋宝宝种子给他们,跟他们说放在水里可以变的很大,却没人要。
  2. 和jy复合了,好像在逃亡之类的,一起躲在某个地方。

2021年 5月28日
出差
梦见在新公司,住四人宿舍,还不停地出差,高铁票都在晚上十二点,太苦逼了。还有人说记得把被子床铺什么的收起来,要不然其他人会过来睡,长住,,,,太尼玛坑了。感觉场景像学校,但是人有一个是新同事小平,很混乱。

2021年 5月20日
课堂
变成了一个好学生,成绩特别厉害,在一次数学作业中,正面做的很认真,但反面很敷衍,四五道大题目,全部都只写了一行。老师上课讲题目,走到我旁边时候刚好讲到反面,发现我非常敷衍,几乎没做,于是不停地责骂我,问我咋回事吧啦吧啦,就醒了。

2021年 5月19日
婚礼
梦见自己变成了一个女的,嫁入豪门,还为男主怀孕了。但男主他妈一直不同意。但由于怀孕,被迫终究还是结婚,婚礼过程中,男主慢慢晕倒,我也开始肚子疼(现实中的确有点肚子疼),该不会流产了吧……当我醒来后,果然发现孩子没了。我越想越不对劲,是不是老太婆搞的鬼,去查监控,果然是被下了药…oh……,男主后来和我亲热所以也吸收了一点药,所以也倒了……

没了小孩没人在意了,最后是老太婆的胜利。

几个基础公式

条件概率

指事件 A 在事件 B 已经发生的条件下发生的概率,公式为:
$$P(A|B) = \frac{P(AB)}{P(B)}$$

全概率

作用在于将复杂事件的概率求解转化为在不同情况下发生的简单事件的概率求和
$$
P(A) = \sum_{i=1}^N P(A | B_i) * P(B_i) \\
\sum_{i=1}^N P(B_i) = 1
$$

联合概率

上式中 P(AB) 称为联合概率,表示 A 和 B 两个事件共同发生的概率,如果两个事件是相互独立的,那么有 $ P(AB) = P(A) · P(B) $,还有 $ P(A|B) = P(A) $

P(A,B) 或者 P(A∩B) 也都是联合概率的表达方式。

贝叶斯定律

公式:

$$P(H | D) = \frac{P(D | H) · P(H)}{P(D)}$$

来理解一下出现的几个定义:

  • P(H),H 的先验概率,即预先设定的假设成立的概率。
  • P(D | H),H 的似然概率 $l(H | D)$,是在假设成立的前提下观测到结果的概率。
  • P(H | D),H 的后验概率,即在观测到结果的前提下假设成立的概率。

举个 🌰

由于定义从不说人话,大部分人第一次看见这个都一脸懵逼,下面结合一个 🌰 来理解:

国人玩游戏的概率为 P(✔️) = 0.6,不玩游戏的概率为 P(✗) = 0.4,这个概率是统计得到的,或者是自身根据经验给出的一个概率值,我们称这个为先验概率
另外,玩游戏的人中男性的概率为 P(M | ✔️) = 0.8,女性的概率为 P(F | ✔️) = 0.2。

我们可以写出对应的条件概率分布:
P(M | ✔️) = 0.8, P(M | ✗) = 0.2
P(F | ✔️) = 0.2, P(F | ✗) = 0.8

严格来讲,P(M | ✔️) = 0.8 并不能推导出 P(M | ✗) = 0.2,但我们先做出这个假设。

现在想知道一个男性玩游戏的概率是多少? 即 P(✔️ | M) 的值,这就是后验概率
根据贝叶斯公式和全概率公式可得

\begin{split}
P(✔️ | M) &= \frac{P(M | ✔️) · P(✔️)}{P(M)} \\
&\quad= \frac{P(M | ✔️) · P(✔️)}{P(M | ✔️) · P(✔️) + P(M | ✗) · P(✗)} \\
&\quad= \frac{0.8 * 0.6}{0.8 * 0.6 + 0.2 * 0.4} \\
&\quad= 0.857 \\
\end{split}

再理解

结合 🌰 理解一下,可以有个大概印象:

先验概率

先验概率是以全事件为背景下,✔️ 事件发生的概率,即 P(✔️ | Ω)

全事件一般是统计获得的,所以称为先验概率,没有实验前的概率。
Ω:样本空间,概率论和统计力学中所有可能的事件或系统状态的集合

后验概率

后验概率是以新事件 M 为背景下,✔️ 事件发生的概率,即 P(✔️ | M),计算的是在给定 M 后,✔️ 发生的概率。实际上就是条件概率。

新事件一般是试验,如试验B,此时的事件背景从全事件变成了B,该事件B可能对A的概率有影响,那么需要对A现在的概率进行一个修正,从P(A|Ω)变成 P(A|B),所以称 P(A|B)为后验概率,也就是试验(事件B发生)后的概率。

似然概率

在这个例子中,P(✔️ | M) 是后验概率, P( M | ✔️) 是似然概率。
P(✔️ | M) 是给定参数男性,他玩游戏的可能性,关注的是事件 ✔️ 的发生概率。
如何理解似然呢?P( M | ✔️),是玩游戏的人是男性的概率。

P(✔️ | M) 是一个有两个变量的函数, 将 M 看作为常量,则会得到一个概率函数;将 ✔️ 看作常量,会得到一个似然函数(关于 M 的函数)。
P(✔️ | M) 是 M 参数下 ✔️ 出现的概率,同时也是 ✔️ 出现时 M 参数的靠谱程度,也就是 M 的似然。

**极大似然估计 (ML估计)**,就是在已知观测的数据的前提下,找到使得似然概率最大的参数值。

再谈似然函数

公式

设已知样本集为 $D={x_1, x_2, ··· , x_n}$,
参数 θ 的似然函数为 $l(θ) = P(D | θ) = P(x_1, x_2, ··· , x_n | θ) = \prod_{i=i}^nP(x_i | θ)$

如果说 $θ_0$ 是能使似然函数 $l(θ)$ 取得最大值的 $θ$ 值,则应该 $θ_0$ 是最可能的参数值,那么 $θ_0$ 就是 $θ$ 的极大似然估计量。

image.png

max 和 argmax 的区别 ?设 y = f(x) 是一般的函数式
y = max f(x)代表:y 是 f(x) 函数所有值中最大的。
y = argmax f(x)代表:y 是 f(x) 函数中,会产生最大值的那个参数 x。arg 即 argument,此处意为“自变量”。

举个 🌰

拿抛硬币这个例子来说,一枚均匀硬币的正面概率是 $p = 0.5$,正面朝上记作 $H$ ,反面朝上记作 $T$,现在要预测抛三次,结果是 $HHT$ 的概率。

$$
data = (x_1, x_2, x_3) = (H, H, T)\\
P(HHT ; p=0.5) = \prod_{i=i}^3P(x_i ; p=0.5) = 0.5 * 0.5 * 0.5 = 0.125
$$

如果说正面朝上的概率 $p = 0.4$ ,那么 $P(HHT ; p=0.4) = 0.4 * 0.4 * 0.6 = 0.096$

似然概率正好与这个过程相反,我们关注的量不再是事件的发生概率,而是已知发生了某些事件,我们希望知道参数应该是多少。

现在我们已经抛了三次硬币,并且知道了结果是两次正面,一次反面,这时候,我们希望知道这枚硬币抛出去正面朝上概率为 0.5 的概率是多少?正面朝上概率为 0.8 的概率是多少?

如果我们希望知道正面朝上概率为 0.5 的概率,这个东西就叫似然概率,可以说是对某一个参数猜想 $p = 0.5$ 的概率。这样表示成条件概率就是:
$$
l(p=0.5 | HHT) = P(HHT ; p=0.5) = 0.125\\
l(p=0.4 | HHT) = P(HHT ; p=0.5) = 0.096
$$
我们可以写出似然函数 $l(p | HHT) = P(HHT ; p) = p · p · (1-p) = -p^3+p^2$ ,做出函数图像如下,大约在 $p = 0.67$ 左右能够取得最大值,因此如果出现 $HHT$ ,正面朝上的概率 p 最可能是 0.67,这是最合理的数,但未必符合真实情况,因为数据量不足的缘故。

image.png

参考文章:
https://zh.wikipedia.org/wiki/后验概率
https://www.zhihu.com/question/54082000/answer/1640044106
似然和似然函数详解 https://zhuanlan.zhihu.com/p/42598338

给定一个集合,我们有很多办法能够对这个集合快速排序,但如果给一个已经排序过的集合,如何公平随机地打乱它呢?

问题特点

此类问题最大的特点就是要公平公平还是TMD公平!。何为公平,洗牌的结果是所有元素排成一列,如果一副牌有 n 个元素,最终排列的结果就有 n! 个,公平的洗牌算法要保证能等概率地给出这 n! 个结果中的任意一个。

应用场景

  1. 可以用来洗牌哈;
  2. 随机不重复地播放列表中的歌曲;
  3. 扫雷,雷的初始化;
  4. client 将 所有 servers 的 ip 随机打乱,做负载均衡。

其他解决方案

在介绍洗牌算法前,先介绍一些其他简单而又暴力的解决方式,一起来品一品:
一:穷举 n! 个结果,随机选择一个,算法是绝对公平了,但是时间复杂度达到了 O(N!),直接螺旋升天。
image.png

二:用 random() % n 的方式,不停地随机选取一个数,放入另外一个数组中,直至原数组中的每个数都被选中过。这样的问题是可能会随机到重复的数,你可能需要维护一个 Set 来确保每个数只被选取一次,且越到后来,随机到重复数字的概率越高,算法性能也非常差。

洗牌算法

无比简单,只要一句话就能概括:从最后一个元素开始,随机地和前面所有元素中的某一个进行交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void randomizedArray(Object[] array) {
int p = array.length;
while (p > 0) {
int index = (int) Math.floor(Math.random() * p--);
swap(array, index, p);
}
}

public static void swap(Object[] values, int i, int j) {
Object tmp = values[i];
values[i] = values[j];
values[j] = tmp;
}

KnuthShuffle.java

在别人的指点下,了解到了这个算法,研究后发现是一个特别巧妙的随机算法。

问题特点

  1. 需要在一组数据流中选出 m 个数据;
  2. 数据流的规模 N 可能很大,甚至未知,无法一次性全部加载在内存中;
  3. 要保证每个数据被选中的概率是一致的。

需要注意的是第二点,规模可能是未知的,或者说很难得到规模。如果我们能提前确定 N 的大小,那么可以简单的使用 rand()%N 的方式得到一个确切的随机位置,且每个数据被选中的概率都是 $\frac{1}{N}$ ,无需使用此算法。

应用场景

有一些特定的场景可能会使用该算法,场景比较类似,都是大数据量且规模未知,要公平公平还是TMD公平!

  1. 一个很大的文本,无法得知有多少行,需要随机抽取其中若干行,每一行概率都要相等。
  2. 规模未知的用户参与抽奖,奖品若干,保证每个用户中奖的概率是一致的。

算法流程

设定数据的规模为 N,需要采样的数量为 m,即蓄水池的容量。

  1. 将 N 个数据的前 m 个直接放入蓄水池;
  2. 从第 i 个数据开始( i 从1开始), i > m,在 [0, i) 范围内随机选择整数 d, 如果 d 在[0, m) 范围内,则用第 i 个数据替换原蓄水池中下标为 d 的数据;
  3. 不停地重复步骤2,直至没有数据。

巧妙之处在于:当处理完所有数据时,蓄水池中的每个数据都是以 $\frac{m}{N}$ 的概率获得的。

代码实现

实现的核心代码约10行:ReservoirSampling.java
单元测试,运行后观察在重复若干次后,每个数据被选中的概率:ReservoirSamplingTest.java

大部分人看到这里就差不多结束了,下面会文字说下证明过程,感兴趣的可以再看看。


等概率证明过程

依旧设定数据的规模为 N,需要采样的数量为 m,数据编号 i 从1开始。

每个数据被选中的概率的计算公式如下:
\begin{equation}
\begin{split}
第 i 个接收到的数据最后能留在蓄水池中的概率&=第 i 个数据进入过蓄水池 \\
&\quad* 之后所有数据都没把 i 替换掉的概率
\end{split}
\end{equation}

我们需要讨论两种情况,一种是 i 在 [1, m] 这个范围内的情况,一种是 i 在 (m, N] 的范围内。

  1. 当 i <= m 时, 数据直接放入蓄水池,第 i 个数据进入过蓄水池的概率 = 1

  2. 当 i > m 时,在 [0, i) 内随机选取一个数 d,如果 d < m,则用第 i 个数据,替换蓄水池中下标为 d 的数据,所以**第 i 个数据进入过蓄水池的概率 = $\frac{m}{i}$**。

  3. 当 i <=m 时,算法从接收到第 m+1 个数据时开始有可能出现替换操作,根据第2点得出的规律,第 m+1 个数据会进入水池并替换掉池其它数据的概率为 $\frac{m}{m+1}$ ,刚好替换第 i 个数据的概率为 $\frac{1}{m+1}$,那么第 i 个数据不被第 m+1 个数据替换的概率为 1 - $\frac{1}{m+1}$ = $\frac{m}{m+1}$。

    同理,第 m+2 个数据会进入水池并替换掉池其它数据的概率为 $\frac{m}{m+2}$,刚好替换第 i 个数据的概率是 $\frac{1}{m+2}$,第 i 个数据不被第 m+2 个数据替换的概率为 1 - $\frac{1}{m+2}$ = $\frac{m+1}{m+2}$,……, 第 N 个数据不替换第 i 个数据的概率为 $\frac{N-1}{N}$。

    所以有以下结果:

\begin{split}
第 i 个数据不被后面所有数据替换的概率&=不被第m+1个数据替换的概率 \\
&\quad* 不被第m+2个数据替换的概率 \\
&\quad* 不被第m+3个数据替换的概率 \\
&\quad* … \\
&\quad* 不被第N个数据替换的概率 \\
&= \frac{m}{m+1} * \frac{m+1}{m+2} * \frac{m+2}{m+3} * … * \frac{N-1}{N} \\
&= \frac{m}{N}
\end{split}
4. 当 i > m 时,算法从接收到第 i+1 个数据时开始有可能替换第 i 个数据,根据第3点得到的结果, 第 i 个数据不被之后所有数据替换的概率为 $\frac{i}{N}$。

总结:
根据以上四条规律,以及开始所说的公式 (1),可以得出结果:

  • 结合第1点、第3点,当 i <= m 时,第 i 个数据被选中的概率为 $ 1 * \frac{m}{N} = \frac{m}{N}$;
  • 结合第2点、第4点,当 i > m 时,第 i 个数据被选中的概率为 $ \frac{m}{i} * \frac{i}{N} = \frac{m}{N}$。

==> 因此,对于任意 i ,都有 $\frac{m}{N}$ 的概率。

作为 Web 开发者,我们应当知道自己开发的系统有哪些风险漏洞可能会被攻击,这篇文章将讲述在 Web 中经常使用的攻击手段,以及相应的防御策略。

信息探测

第一步,我们需要踩点,搜集目标资料,找到哪些网站可能存在漏洞。

子域名收集

为什么要枚举子域名?

  • 子域名枚举可以再测试范围内发现更多的域,这将增大漏洞发现的机会。
  • 有些隐藏的、被忽略的子域上运行的应用程序可能帮助我们发现重大漏洞。

如何枚举?

  1. 利用搜索引擎,如 site:baidu.com ,但这样并不靠谱,可能前几页都是一个子域名。
  2. DNS信息收集,借助一些网站,如这是百度的子域收集结果:https://www.virustotal.com/gui/domain/baidu.com/relations
  3. 一些其他开源工具,如 https://github.com/shmilylty/OneForAll

更多工具详情,可参考 https://zhuanlan.zhihu.com/p/31334686

借助搜索搜索敏感信息

可以根据 Google 提供的语法进行信息查询。常用语法可以参考https://en.wikipedia.org/wiki/Google_hacking
如搜索存在敏感信息的网站:
image.png

使用Nmap

探测主机信息

Nmap是一个开源的网络连接端扫描软件,用于扫描计算机开放的网络连接端,确定哪些服务运行在哪些连接端,推断计算机运行的操作系统。

  1. 扫描指定 IP 所开放的端口(这里指定了端口范围是1-65535)
    nmap -sS -p 1-65535 -v 192.168.1.100
  2. 全面的系统检测,默认扫描主机1000个高危端口
    nmap -v -A www.xxser.com
  3. 扫描指定端口
    nmap -p 80,22,3306 www.xxser.com
  4. 穿透防火墙进行扫描(被禁用ping)
    nmap -Pn -A www.xxser.com

更多指令参数查看 -help

使用Nmap脚本

nmap还提供了强大的脚本功能,是最好的功能之一,可以利用脚本快速探测服务器

  1. 扫描Web敏感目录
    nmap -p 80 --script=http-enum.nse www.xxser.com
  2. 暴力破解mysql密码,只能欺负欺负弱密码
    ➜ nmap -p 3306 --script=mysql-brute 127.0.0.1
    更多脚本请查看https://nmap.org/nsedoc/

常见漏洞

SQL注入漏洞

原理

在用户登录时,可能会这样写SQL:select * from user where username = '${name}' and password = '${passwd}'; 。在一般情况下没有问题,但用户如果输入了这样一个“ ' or 1=1;--”特殊的用户名会如何?最终执行的sql将会变成 select * from user where username = '' or 1=1;--' and password = '';

这条SQL会将所有的用户都查询出来,后面的password判断彻底失效,因为已经被注释掉了,如果在 加个 limit 1,几乎可以登录任意一个用户的账号了,后果非常严重。

解决办法

检查数据类型和格式

如果sql语句是类似 where id = ${id},那么在执行前就应该确保 id 是数字类型。如果使用的 Java 这样的强类型语言,没抛异常就说明是没问题的了。

特殊字符串转义

除了检查类型,还应该检查入参中,是否包含一些特殊的字符,如系统的用户名如果不允许用 ‘-‘,就应该排除掉。对于这些特殊字符,如单引号、双引号、反斜杠、中横线,都应该根据业务考虑禁止,如果不可,那么只能对特殊字符串进行转义。

预编译语句

上面说的可能是比较low的方法,最佳方案是使用预编译语句来预防SQL注入。

使用预编译后注入的参数将不会再进行SQL编译。也就是说其后注入进来的参数系统将不会认为它会是一条SQL语句,而默认其是一个参数,参数中的or或者and 等就不是SQL语法保留字了。

数据库提供了预编译技术,Mybatis中打印SQL的话,会看见这种带问号的,如select * from users where name = ? ,? 就是填充符。

在Mysql中进行实验:

  1. 准备数据

    1
    2
    3
    4
    5
    6
    CREATE TABLE `user` (
    `username` varchar(20) DEFAULT NULL,
    `password` varchar(20) DEFAULT NULL
    ) ENGINE=InnoDB DEFAULT CHARSET=utf8;

    insert into user values("a","a1");
  2. 对sql进行预编译

    1
    prepare sqltpl from 'select * from user where username = ? and password = ?';
  3. 设置参数

    1
    set @para1='a',@para2='a1';
  4. 使用该参数来执行预编译语句

    1
    execute sqltpl using @para1, @para2;

    image.png


写着写着突然发现这个网站… PeiQi WiKi-POC文库🐑,这篇文章基本太监了。

0%