悟云

let it be

0%

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func bubbleSort(arr []int) {
var size = len(arr)
// 外层循环循环size-1次
for i := 0; i < size-1; i++ {
var swapped bool
// 内层循环从切片头部开始循环比较相邻元素大小
// 如果arr[j] > arr[j+1]交换之 确保每次循环后最大的元素会排到最后
for j := 0; j < size-1-i; j++ {
if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = true
}
}

if !swapped {
// 本次循环没有交换 此时切片已经有序
return
}
}
}

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func selectionSort(arr []int) {
var size = len(arr)
var minIndex int
// 外层循环循环size-1次
for i := 0; i < size-1; i++ {
minIndex = i
// 内层循环每次找出最小的元素
for j := i + 1; j < size; j++ {
if arr[j] < arr[minIndex] {
minIndex = j
}
}
if minIndex != i {
// 将本次找到的最小元素放入对应位置
arr[i], arr[minIndex] = arr[minIndex], arr[i]
}
}
}

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func insertionSort(arr []int) {
var size = len(arr)
// 外层循环size-1次 从切片的第二个元素开始逐一为每个元素找到合适的插入位置
for i := 1; i < size; i++ {
current := arr[i]
for preIndex := i - 1; preIndex >= 0; preIndex-- {
if arr[preIndex] > current {
// 继续往前找 并挪动位置
arr[preIndex+1] = arr[preIndex]
} else {
// 找到合适的插入位置
arr[preIndex+1] = current
break
}
}
}
}

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func shellSort(arr []int) {
var size = len(arr)
// 初始化间隙位size/2 逐步减少间隙 直至间隙为1
for gap := size / 2; gap >= 1; gap = gap / 2 {
//将切片变为间隔h个元素有序
for i := gap; i < size; i++ {
var current = arr[i]
for preIndex := i; preIndex-gap >= 0; preIndex = preIndex - gap {
if current < arr[preIndex-gap] {
arr[preIndex] = arr[preIndex-gap]
} else {
arr[preIndex] = current
break
}
}
}
}
}

快速排序

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
func quickSort(arr []int) {
_quickSort(arr, 0, len(arr)-1)
}

func _quickSort(arr []int, left, right int) {
if left < right {
// 将切片分为两个部分
// 使得[left->pivot-1]的元素都小于等于arr[pivot], [pivot+1->right]的元素都大于arr[pivot]
pivot := partition(arr, left, right)
// 对左右两个部分重复上述过程
_quickSort(arr, left, pivot-1)
_quickSort(arr, pivot+1, right)
}
}

func partition(arr []int, left, right int) int {
// 选取array[left]作为分割基准点
i, j, pivot := left, right, arr[left]
for {
// 从右往左扫描 直到某个元素小于等于pivot
for i < j && arr[j] > pivot {
j--
}

// 从左往右扫描 直到某个元素大于pivot
for i < j && arr[i] <= pivot {
i++
}

if i < j {
// 此时可以肯定 arr[j] <= pivot 同时 arr[i] > pivot, 交换a[i], a[j]
arr[i], arr[j] = arr[j], arr[i]
} else {
// 扫描完毕
break
}
}

arr[i], arr[left] = arr[left], arr[i]
return i
}

归并排序

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
func mergeSort(arr []int) []int {
var size = len(arr)
if size <= 1 {
// 只有一个值 无需排序
return arr
}

// 分成左右两组 分别继续归并排序
var mid = size / 2
var left = mergeSort(arr[:mid])
var right = mergeSort(arr[mid:])
// 合并左右两组排序结果
return merge(left, right)
}

func merge(left, right []int) (result []int) {
l, r := 0, 0
for l < len(left) && r < len(right) {
if left[l] <= right[r] {
result = append(result, left[l])
l++
} else {
result = append(result, right[r])
r++
}
}
result = append(result, left[l:]...)
result = append(result, right[r:]...)
return
}

堆排序

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
func heapSort(arr []int) {
var size = len(arr)
// 构建大顶堆
for i := size/2 - 1; i >= 0; i-- {
// 从第一个非叶子节点从下至上, 从左到右调整结构
adjustHeap(arr, i, size)
}

// 下沉堆定元素+重新调整堆结构
for i := size - 1; i > 0; i-- {
arr[0], arr[i] = arr[i], arr[0]
adjustHeap(arr, 0, i)
}
}

func adjustHeap(arr []int, i, size int) {
var tmp = arr[i]
for k := i*2 + 1; k < size; k = k*2 + 1 {
//从i结点的左子结点开始,也就是2i+1处开始
if k+1 < size && arr[k] < arr[k+1] {
//如果左子结点小于右子结点,k指向右子结点
k++
}

if arr[k] > tmp {
//如果子节点大于父节点,将子节点值赋给父节点(不用进行交换)
arr[i] = arr[k]
i = k
} else {
break
}
}
//将temp值放到最终的位置
arr[i] = tmp
}

非比较类型排序

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
118
119
120
121
122
123
124
125
126
// 计数排序
func countingSort(arr []int) {
var maxValue = maxValue(arr)
// 分配一个能容纳0-maxValue整数的切片
var bucket = make([]int, maxValue+1)
// 将每个元素直接存到对应位置
for _, value := range arr {
bucket[value] += 1
}

sortedIndex := 0
// 存放元素位置的顺序就是元素排序后的顺序
for i := range bucket {
for {
if bucket[i] > 0 {
arr[sortedIndex] = i
bucket[i]--
sortedIndex++
} else {
break
}
}
}
}

// 桶排序 计数排序的升级版 利用函数映射
func bucketSort(arr []int) {
//桶数
var size = len(arr)
var maxValue = maxValue(arr)
//二维切片
buckets := make([][]int, size)
//分配入桶
index := 0
for i := 0; i < size; i++ {
index = arr[i] * (size - 1) / maxValue //函数映射
buckets[index] = append(buckets[index], arr[i])
}

// 按顺序遍历桶取出数据
tmpPos := 0
for i := 0; i < size; i++ {
bucketLen := len(buckets[i])
if bucketLen > 0 {
// 桶内排序
// 此处实现插入排序方式,其实可以用任意其他排序方式
insertionSort(buckets[i])
copy(arr[tmpPos:], buckets[i])
tmpPos += bucketLen
}
}
}

// 获取数组最大元素
func maxValue(arr []int) (max int) {
if len(arr) == 0 {
return 0
}

max = arr[0]
for _, value := range arr {
if value > max {
max = value
}
}

return
}

// 基数排序
// 将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零
// 然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。
// 基数排序的方式可以采用LSD(Least significant digital)或MSD(Most significant digital)
// LSD的排序方式由键值的最右边开始,而MSD则相反,由键值的最左边开始。
// 下面是实现的LSD版本
func radixSort(arr []int) {
var (
size = len(arr)
tmp = make([]int, size, size)
radix = 1
maxDigit = maxDigit(arr)
)

var i, j, k int
for i = 0; i < maxDigit; i++ { //进行maxDigit次排序
// count index 0->9对应每个位上的数字
// count value 对应每个位上数字出现次数
var count = make([]int, 10)
for j = 0; j < size; j++ {
k = (arr[j] / radix) % 10
count[k]++
}

for j = 1; j < 10; j++ {
count[j] = count[j-1] + count[j]
}
// 逆序
for j = size - 1; j >= 0; j-- {
k = (arr[j] / radix) % 10
tmp[count[k]-1] = arr[j]
count[k]--
}

for j = 0; j < size; j++ {
arr[j] = tmp[j]
}

// 十进制位数增加
radix = radix * 10
}
}

//求数组元素的十进制位数
func maxDigit(arr []int) (ret int) {
if len(arr) == 0 {
return 0
}
var radix = 1
for _, value := range arr {
for value >= radix {
radix = radix * 10
ret++
}
}
return
}

题目描述

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
定义一个二维数组N*M(其中2<=N<=10;2<=M<=10),如5 × 5数组下所示:


int maze[5][5] = {


0, 1, 0, 0, 0,


0, 1, 0, 1, 0,


0, 0, 0, 0, 0,


0, 1, 1, 1, 0,


0, 0, 0, 1, 0,


};


它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。入口点为[0,0],既第一空格是可以走的路。

Input

一个N × M的二维数组,表示一个迷宫。数据保证有唯一解,不考虑有多解的情况,即迷宫只有一条通道。

Output

左上角到右下角的最短路径,格式如样例所示。

Sample Input

0 1 0 0 0

0 1 0 1 0

0 0 0 0 0

0 1 1 1 0

0 0 0 1 0

Sample Output

(0, 0)

(1, 0)

(2, 0)

(2, 1)

(2, 2)

(2, 3)

(2, 4)

(3, 4)

(4, 4)

输入描述

1
输入两个整数,分别表示二位数组的行数,列数。再输入相应的数组,其中的1表示墙壁,0表示可以走的路。数据保证有唯一解,不考虑有多解的情况,即迷宫只有一条通道。

输出描述

1
左上角到右下角的最短路径,格式如样例所示。

示例

输入

1
2
3
4
5
6
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

输出

1
2
3
4
5
6
7
8
9
(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)

code

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
package main
import "fmt"

func main() {
for {
var m, n int
_, err := fmt.Scan(&m)
if err != nil {
return
}
fmt.Scan(&n)
matrix := make([][]int, m)
for i := range matrix {
matrix[i] = make([]int, n)
}

for i := 0; i < m; i++ {
for j := 0; j <n; j++ {
fmt.Scan(&matrix[i][j])
}
}

bestPath = nil
path = nil

findPath(matrix, 0, 0, m, n)
for _, p := range bestPath {
fmt.Printf("(%d,%d)\n", p.row, p.col)
}

}
}

type Position struct {
row int
col int
}


var (
path []*Position
bestPath []*Position
)

func findPath(matrix [][]int, i, j, m, n int) {
if len(bestPath) == m + n - 2 {
return
}
matrix[i][j] = 1
path = append(path, &Position{i, j})
if i == m -1 && j == n -1 {
if len(bestPath) == 0 || len(bestPath) > len(path) {
bestPath = path
}
}

if i > 0 && matrix[i-1][j] == 0 {
findPath(matrix, i-1, j, m, n)
}

if i < m -1 && matrix[i+1][j] == 0 {
findPath(matrix, i+1, j, m, n)
}

if j > 0 && matrix[i][j-1] == 0 {
findPath(matrix, i, j-1, m, n)
}

if j < n -1 && matrix[i][j+1] == 0 {
findPath(matrix, i, j+1, m, n)
}

matrix[i][j] = 0


path = path[0:len(path)]
}

题目描述

1
分子为1的分数称为埃及分数。现输入一个真分数(分子比分母小的分数,叫做真分数),请将该分数分解为埃及分数。如:8/11 = 1/2+1/5+1/55+1/110。

输入描述

1
输入一个真分数,String型

输出描述

1
输出分解后的string

示例

输入

1
8/11

输出

1
1/2+1/5+1/55+1/110

思路

代码

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
package main
import "fmt"

func main() {
for {
var a, b int
_, err := fmt.Scanf("%d/%d", &a, &b)
if err != nil {
return
}

var x = gcd(a, b)
a /= x
b /= x

var try bool
var result []int
for {
if b % a == 0 && try {
result = append(result, b / a)
break
}

var p = b/a + 1
result = append(result, p)
a = a * p - b
b *= p
try = true
}


for i, v := range result {
fmt.Printf("1/%d", v)
if i < len(result) - 1 {
fmt.Print("+")
} else {
fmt.Print("\n")
}
}

}

}

func gcd(a, b int) int {
if a == 1 || b == 1 {
return 1
}

var min int
if a >= b {
min = b
} else {
min = a
}

var result = 1
for i := 2; i <= min; i++ {
if a % i == 0 && b % i == 0 {
a /= i
b /= i
min /= i
result *= i
}
}

return result
}

题目描述

1
计算两个字符串的最大公共字串的长度,字符不区分大小写

输入描述

1
输入两个字符串

输出描述

1
输出一个整数

示例

输入

1
2
asdfas
werasdfaswer

输出

1
6
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
package main
import "fmt"
import "strings"

func main() {
for {
var m, n string
if _, err := fmt.Scan(&m); err != nil {
return
}

if _, err := fmt.Scan(&n); err != nil {
return
}


m = strings.ToLower(m)
n = strings.ToLower(n)

var max int
var dp [][]int = make([][]int, len(m)+1)
for i := range dp {
dp[i] = make([]int, len(n)+1)
}

for i := 1; i <= len(m); i++ {
for j := 1; j <= len(n); j++ {
if m[i-1] == n[j-1] {
dp[i][j] = dp[i-1][j-1] + 1
}

if dp[i][j] > max {
max = dp[i][j]
}
}

}

fmt.Println(max)
}
}
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
package main
import "fmt"
import "strings"

func main() {
for {
var m, n string
if _, err := fmt.Scan(&m); err != nil {
return
}

if _, err := fmt.Scan(&n); err != nil {
return
}



var longStr, shortStr string
if len(m) >= len(n) {
longStr = strings.ToLower(m)
shortStr = strings.ToLower(n)
} else {
shortStr = strings.ToLower(m)
longStr = strings.ToLower(n)
}

var maxLen int
for i := 0; i < len(shortStr); i++ {
for j := 1; j <= len(shortStr) - i; j++ {
if strings.Contains(longStr, shortStr[i:i+j]) {
if maxLen < j {
maxLen = j
}
}
}

}

fmt.Println(maxLen)
}
}

题目描述

1
给定一个正整数N代表火车数量,0<N<10,接下来输入火车入站的序列,一共N辆火车,每辆火车以数字1-9编号,火车站只有一个方向进出,同时停靠在火车站的列车中,只有后进站的出站了,先进站的才能出站。要求以字典序排序输出火车出站的序列号。

输入描述

1
有多组测试用例,每一组第一行输入一个正整数N(0<N<10),第二行包括N个正整数,范围为1到9。

输出描述

1
输出以字典序从小到大排序的火车出站序列号,每个编号以空格隔开,每个输出序列换行,具体见sample。

示例

输入

1
2
3
1 2 3

输出

1
2
3
4
5
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1

code

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

import (
"fmt"
"sort"
"strings"
)

type stack []string

func (s *stack) push(v string) {
*s = append(*s, v)
}

func (s *stack) pop() string {
l := len(*s)
result := (*s)[l-1]
*s = (*s)[0 : l-1]
return result
}

func (s *stack) unshift() string {
result := (*s)[0]
*s = (*s)[1:]
return result
}

func (s *stack) empty() bool {
return len(*s) == 0
}

func main() {
for {
var N uint8
_, err := fmt.Scan(&N)
if err != nil {
break
}

var trainList = make([]string, 0, N)
for i := uint8(0); i < N; i++ {
var train string
fmt.Scan(&train)
trainList = append(trainList, train)
}

pre := stack(trainList)
in := stack{}
out := stack{}
handle(pre, in, out)
}

sort.Strings(results)
for _, result := range results {
fmt.Println(result)
}
}

var (
results []string
)

func handle(pre, in, out stack) {
if pre.empty() && in.empty() {
results = append(results, strings.Join(out, " "))
return
}

if !pre.empty() {
prec := make([]string, len(pre))
inc := make([]string, len(in))
outc := make([]string, len(out))

copy(prec, pre)
copy(inc, in)
copy(outc, out)

pres := stack(prec)
ins := stack(inc)
outs := stack(outc)

ins.push(pres.unshift())
handle(pres, ins, outs)
}

if !in.empty() {
prec := make([]string, len(pre))
inc := make([]string, len(in))
outc := make([]string, len(out))

copy(prec, pre)
copy(inc, in)
copy(outc, out)

pres := stack(prec)
ins := stack(inc)
outs := stack(outc)

outs.push(ins.pop())
handle(pres, ins, outs)
}
}