悟云

let it be

0%

Posted on

冒泡排序

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
}

Posted on

题目描述

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)]
}

Posted on

题目描述

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
}

Posted on

题目描述

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)
    }
}

Posted on

题目描述

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)
	}
}