算法第四版第一章节

累加器

API

image-20200711224750298
image-20200711224750298

实现

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
package ds

import kotlin.math.sqrt

/**
* 累加器 防抖动版本
* */
class Accumulator constructor(
private var total: Double = 0.0
) {
private var times: Int = 0
private var mean: Double = 0.0
private var s: Double = 0.0

fun <T : Number> addDataValue(value: T) {
times += 1
val dv = value.toDouble()
total += dv

s += 1.0 * (times - 1) / times * (dv - mean) * (dv - mean)
mean += (dv - mean) / times
}

fun mean(): Double = mean

fun variance(): Double = if (times <= 1) Double.NaN else s / (times - 1)

fun stddev(): Double = sqrt(variance())

fun total(): Double = total

override fun toString(): String {
return "Mean ($times times, ${String.format("%.2f", total)} values): " +
"${String.format("%7.5f", mean())}"
}
}

可视化累加器

API

image-20200711224928831
image-20200711224928831

实现

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
package ds

import edu.princeton.cs.algs4.StdDraw
import kotlin.math.sqrt

class VisualAccumulator constructor(
private val xMax: Int = 100,
private val yMax: Double = 100.0
) {
private var times: Int = 0
private var total: Double = 0.0
private var mean: Double = 0.0
private var s: Double = 0.0

init {
StdDraw.setXscale(0.0, xMax.toDouble())
StdDraw.setYscale(0.0, yMax)
StdDraw.setPenRadius(.01)
}

fun <T : Number> addDataValue(value: T) {
times += 1
val dv = value.toDouble()
total += dv

mean += (dv - mean) / times
s += 1.0 * (times - 1) / times * (dv - mean) * (dv - mean)

StdDraw.setPenColor(StdDraw.DARK_GRAY)
StdDraw.point(times.toDouble(), value.toDouble())
StdDraw.setPenColor(StdDraw.RED)
StdDraw.point(times.toDouble(), mean())
StdDraw.setPenColor(StdDraw.BLUE)
StdDraw.point(times.toDouble(), stddev())
}

fun mean(): Double = mean

fun variance(): Double = if (times <= 1) 0.0 else s / (times - 1)

fun stddev(): Double = sqrt(variance())

fun total(): Double = total

override fun toString(): String {
return "Mean ($times times, ${String.format("%.2f", total)} values): " +
"${String.format("%7.5f", mean())}"
}
}

可视化结果

image-20200711225013771
image-20200711225013771

有理数

API

image-20200711225149973
image-20200711225149973

实现

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
package ds

import utils.qgcd
import kotlin.reflect.typeOf

class Rational constructor(
private var numerator: Long,
private var denominator: Long = 1L
) : Comparable<Rational> {
init {
if (denominator == 0L) {
throw IllegalAccessError("分母不能为0!")
}

simplify()
}

fun numerator(): Long {
return numerator
}

fun denominator(): Long {
return denominator
}

private fun simplify() {
val g = qgcd(numerator, denominator)
numerator /= g
denominator /= g
if (denominator < 0) {
denominator = -denominator
numerator = -numerator
}
}

public operator fun plus(other: Rational): Rational {
if (this.numerator == 0L) return other
if (other.numerator == 0L) return this
val g = qgcd(this.denominator, other.denominator)
return Rational(
this.numerator * (other.denominator / g) + other.numerator * (this.denominator / g),
this.denominator * (other.denominator / g)
)
}

public operator fun minus(other: Rational): Rational {
if (this.numerator == 0L) return other
if (other.numerator == 0L) return this

val g = qgcd(this.denominator, other.denominator)
return Rational(
this.numerator * (other.denominator / g) - other.numerator * (this.denominator / g),
this.denominator * (other.denominator / g)
)
}

public operator fun times(other: Rational): Rational {
return Rational(
this.numerator * other.numerator,
this.denominator * other.denominator
)
}

public operator fun div(other: Rational): Rational {
return Rational(
this.numerator * other.denominator,
this.denominator * other.numerator
)
}

override fun equals(other: Any?): Boolean {
if (other == null) return false
if (this::class != other::class) return false
return this.compareTo(other as Rational) == 0
}

override fun toString(): String {
if (denominator == 1L) {
return "$numerator"
}
return "$numerator/$denominator"
}

override fun compareTo(other: Rational): Int {
// 除法判断大小于
val num = this.numerator * other.denominator
val den = this.denominator * other.numerator
if (num > den)
// 说明分子大 当前数大
return 1
if (num < den)
return -1
return 0
}
}

日期类

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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
package ds

class Date : Comparable<Date> {
private val year: Int
private val month: Int
private val day: Int

constructor(
y: Int = 0,
m: Int = 0,
d: Int = 0
) {
if (!isDateValid(d, m, y))
throw IllegalArgumentException("输入日期错误!")
year = y
month = m
day = d
}

constructor(
parseString: String
) {
parseString.split("/").run {
if (size < 3) {
throw IllegalArgumentException("输入日期错误!")
}
year = get(0).toInt()
month = get(1).toInt()
day = get(2).toInt()
if (!isDateValid(day, month, year))
throw IllegalArgumentException("输入日期错误!")
}

}

companion object {
val monthDayList = listOf(0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)
}

private fun isDateValid(d: Int, m: Int, y: Int): Boolean {
if (m > 12 || m < 1) {
return false
}
if (d > monthDayList[m] || d < 1) {
return false
}
if (m == 2 && d == 29 && !isLeapYear(y)) {
return false
}
return true
}

// is y a leap year?
fun isLeapYear(y: Int): Boolean {
if (y % 400 == 0) return true
if (y % 100 == 0) return false
return y % 4 == 0
}

fun year() = year
fun month() = month
fun day() = day

override fun compareTo(other: Date): Int {
if (this.year < other.year)
return -1
if (this.year > other.year)
return 1
if (this.month < other.month)
return -1
if (this.month > other.month)
return 1
if (this.day < other.day)
return -1
if (this.day > other.day)
return 1
return 0
}

override fun toString(): String {
return "$year/$month/$day"
}

override fun hashCode(): Int {
return day + 31 * month + 31 * 12 * year
}
}

账单

实现

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
package ds

class Transaction : Comparable<Transaction> {
private val who: String
private val time: Date
private val amount: Double

constructor(
w: String,
t: Date,
a: Double
) {
if (!isAmountValid(a))
throw IllegalArgumentException("输入金额格式错误!")
who = w
time = t
amount = a
}

constructor(
parseString: String
) {
parseString.split(" ").run {
if (size < 3) {
throw IllegalArgumentException("输入格式错误!")
}
who = get(0)
time = Date(get(1))
amount = get(2).toDouble()
if (!isAmountValid(amount))
throw IllegalArgumentException("输入金额错误!")
}

}

fun who() = who
fun time() = time
fun amount() = amount

private fun isAmountValid(amount: Double): Boolean {
if (
Double.NaN == amount ||
Double.NEGATIVE_INFINITY == amount ||
Double.POSITIVE_INFINITY == amount
) {
return false
}
return true
}


override fun compareTo(other: Transaction): Int {
return compareValues(this.amount, other.amount)
}

override fun toString(): String {
return String.format("%-10s %10s %8.2f", who, time, amount)
}
}

GCD

普通GCD

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* 普通gcd模板
* */
fun <T : Number> gcd(a: T, b: T): Long {
if (a == 0) return b.toLong()
if (b == 0) return a.toLong()
var ta = abs(a.toLong())
var tb = abs(b.toLong())
while (tb != 0L) {
ta = tb.also {
tb = ta % tb
}
}
return ta
}

快速GCD

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* 快速gcd模板
* */
private fun qgcd_(a: Long, b: Long): Long {
if (a == 0L) return b
if (b == 0L) return a

if ((a and 1) == 0L && (b and 1) == 0L)
return qgcd_(a shr 1, b shr 1) shl 1
else if ((b and 1) == 0L)
return qgcd_(a, b shr 1)
else if ((a and 1) == 0L)
return qgcd_(a shr 1, b)
else
return qgcd_(abs(a - b), min(a, b))
}

fun <T : Number> qgcd(a: T, b: T): Long {
if (a == 0) return b.toLong()
if (b == 0) return a.toLong()
var ta = a.toLong()
var tb = b.toLong()
return qgcd_(abs(ta), abs(tb))
}

背包

API

image-20200711225738407
image-20200711225738407

实现

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
package ds

import kotlin.NoSuchElementException


class Bag<T> : Iterable<T> {
private var first: Node<T>? = null
private var n: Int = 0

fun isEmpty(): Boolean = first == null

fun size(): Int = n

fun add(item: T) {
val oi = first
first = Node(
item,
oi
)
n++
}

override fun iterator(): Iterator<T> {
return LinkedIterator<T>(first)
}

private data class Node<T>(
val item: T,
var next: Node<T>? = null
)

private class LinkedIterator<T>(
private var current: Node<T>?
) : Iterator<T> {

override fun hasNext(): Boolean {
return current != null
}

fun remove() {
throw UnsupportedOperationException()
}

override fun next(): T {
if (!hasNext()) {
throw NoSuchElementException()
}
val item = current?.item
current = current?.next
return item!!
}
}
}

API

image-20200711225952602
image-20200711225952602

实现

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
package ds

class Stack<T> : Iterable<T> {
private var first: Node<T>? = null
private var n: Int = 0

fun isEmpty(): Boolean = first == null

fun size(): Int = n

fun push(item: T) {
val oi = first
first = Node(
item,
oi
)
n++
}

fun pop(): T? {
if (isEmpty()) {
throw NoSuchElementException("Stack underflow")
}
return first?.item.also {
first = first?.next
n--
}
}

fun peek(): T? {
if (isEmpty()) {
throw NoSuchElementException("Stack underflow")
}
return first?.item
}

override fun toString(): String {
return StringBuilder().also {
this.forEach { item -> it.append("$item ") }
}.toString()
}

override fun iterator(): Iterator<T> {
return LinkedIterator(first)
}

private data class Node<T>(
val item: T,
var next: Node<T>? = null
)

private class LinkedIterator<T>(
private var current: Node<T>?
) : Iterator<T> {

override fun hasNext(): Boolean {
return current != null
}

fun remove() {
throw UnsupportedOperationException()
}

override fun next(): T {
if (!hasNext()) {
throw NoSuchElementException()
}
val item = current?.item
current = current?.next
return item!!
}
}
}

队列

API

image-20200711230035937
image-20200711230035937

实现

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
package ds

class Queue<T> : Iterable<T> {
private var first: Node<T>? = null
private var last: Node<T>? = null
private var n: Int = 0

fun isEmpty(): Boolean = first == null

fun size(): Int = n

fun enqueue(item: T) {
val ol = last
last = Node(
item,
null
)
if (isEmpty()) {
first = last
} else {
ol?.next = last
}
n++
}

fun dequeue(): T? {
if (isEmpty()) {
throw NoSuchElementException("Stack underflow")
}
return first?.item.also {
first = first?.next
n--
if (isEmpty()) {
last = null
}
}
}

fun peek(): T? {
if (isEmpty()) {
throw NoSuchElementException("Stack underflow")
}
return first?.item
}

override fun toString(): String {
return StringBuilder().also {
this.forEach { item -> it.append("$item ") }
}.toString()
}

override fun iterator(): Iterator<T> {
return LinkedIterator(first)
}

private data class Node<T>(
val item: T,
var next: Node<T>? = null
)

private class LinkedIterator<T>(
private var current: Node<T>?
) : Iterator<T> {

override fun hasNext(): Boolean {
return current != null
}

fun remove() {
throw UnsupportedOperationException()
}

override fun next(): T {
if (!hasNext()) {
throw NoSuchElementException()
}
val item = current?.item
current = current?.next
return item!!
}
}
}

括号匹配

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* 括号是否匹配
* */
fun isBanlanced(expr: String): Boolean {
val s = Stack<Char>()

expr.forEach { c: Char ->
when (c) {
'(', '{', '[' -> s.push(c)
')' -> if (s.isEmpty() || s.pop() != '(') return false
']' -> if (s.isEmpty() || s.pop() != '[') return false
'}' -> if (s.isEmpty() || s.pop() != '{') return false
}
}

return true
}

Github

Github