个人算法练习库-go语言版--1

wslzwps00321 · · 1545 次点击 · · 开始浏览

```package main

import (
"fmt"
"util/stack"
)

type tree struct {
data int
l    *tree
r    *tree
}

type list struct {
data int
next *list
}

//阶乘
func fact(n uint32) uint32 {
if n == 0 {
return 1
}
return n * fact(n-1)
}

//二分查找
func BSearch(a []int, element, low, height int) int {
if low > height {
return -1
}

mid := (low + height) / 2

if a[mid] == element {
return 0
} else if a[mid] > element {
return BSearch(a, element, low, mid-1)
} else {
return BSearch(a, element, mid+1, height)
}
}

//斐波那契数列--递归
func f(n int) int {
if n < 3 {
return 1
}
return f(n-1) + f(n-2)
}

//斐波那契数列--非递归
func f1(n int) int {

var s, s1, s2 int = 1, 1, 1

for i := 3; i <= n; i++ {
s = s1 + s2
s2 = s1
s1 = s
}
return s
}

//冒泡
func bubblesort(a []int, n int) {
//n个数据需要n-1趟
for i := 1; i < n; i++ {
//每趟需要比较 元素个数-1 次
for j := 0; j < n-i; j++ {
if a[j] > a[j+1] {
temp := a[j]
a[j] = a[j+1]
a[j+1] = temp
}
}
}
}

//反转链表
}
return ph
}

}
for node2 != nil {
node2.next = node1
node1.next = nil

node1 = node2
node2 = node3
node3 = node3.next
}

return node2

}

//将二叉搜索树转换成双向链表
func treeToDoubleList(head, tail *tree, root *tree) {
if root == nil {
tail = nil
return
}

if ltail != nil {
ltail.r = root
root.l = ltail
} else {
}

} else {
tail = root
}

}

//比较两个树是否相等
func compareTree(t1, t2 *tree) int {
if t1 == nil && t2 == nil {
return 1
}
if t1 == nil || t2 == nil {
return -1
}
if t1.data != t2.data {
return -1
}

if compareTree(t1.l, t2.l) == 1 && compareTree(t1.r, t2.r) == 1 {
return 1
} else {
return -1
}

}

//在二元树中找出和为某一值的所有路径
func getValuePath(root *tree, n int, sum int) {
if root == nil {
return
}

s.Push(root.data)

sum += root.data

if sum == n {
fmt.Println(s)
s.Pop()
return
}
getValuePath(root.l, n, sum)
getValuePath(root.r, n, sum)

s.Pop()

}

//获取最大子数组
func getMaxSubArray(a []int, n int) {
if n < 0 || a == nil {
return
}
var sum, begin, end, max int = 0, 0, 0, -1 << 31

for i := 0; i < n; i++ {
sum += a[i]
if sum < 0 {
sum = 0
begin = i + 1
}
if sum > max {
max = sum
end = i
}
}
fmt.Println(begin, end, max)
}

//判断整数序列是不是二元查找树的后序遍历结果
func checkPostOrder(a []int, l, h int, b *bool) {
if l >= h {
return
}
parent := a[h]
//fmt.Println(parent, l, h)
i := l
for ; i < h-1; i++ {
if a[i] > parent {
break
}
}

for j := i + 1; j < h; j++ {
if a[j] <= parent {
*b = false
break
}
}

if *b {
checkPostOrder(a, l, i-1, b)
checkPostOrder(a, i, h-1, b)
}
}

//^-反转句子里面单词的顺序
func swap(b []byte, begin, end int) {
if begin > end {
return
}
for begin <= end {
tmp := b[begin]
b[begin] = b[end]
b[end] = tmp

begin++
end--

}
}
func reverseStr(str *string) {

begin := 0

b := []byte(*str)

for i := 0; i < len(*str); i++ {
if b[i] == 32 {
swap(b, begin, i-1)
begin = i + 1
}
}
swap(b, begin, len(*str)-1)

//反转整个字符串
swap(b, 0, len(*str)-1)

fmt.Println(string(b))

}

//\$-反转句子里面单词的顺序

func main() {
/*
//var b uint32 = 6
//fmt.Println(b, "!=", fact(b))
//a := []int{1, 2, 4, 6, 7, 8, 9, 10, 11, 12}
//c := BSearch(a, 4, 0, 9)
//fmt.Println(c)
//t := []int{3, 2, 1, 5, 7, 6, 9, 0}
//bubblesort(t, 8)
//fmt.Println(t)
//t := []int{1, -2, 3, 10, -4, 7, 2, -5}

//getMaxSubArray(t1, len(t1))

t1 := tree{4, nil, nil}
t2 := tree{7, nil, nil}
t3 := tree{5, &t1, &t2}
t4 := tree{12, nil, nil}
root := tree{10, &t3, &t4}

getValuePath(&root, 22, 0)

t := []int{5, 7, 6, 9, 11, 20, 1, 8}
//t := []int{7, 4, 6, 5}
b := true
checkPostOrder(t, 0, 7, &b)
fmt.Println(b)
*/
str := "i am a student."
reverseStr(&str)

}
```

0 回复

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、``单行代码``
• 支持 @ 本站用户；支持表情（输入 : 提示），见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传
```package main

import (
"fmt"
"util/stack"
)

type tree struct {
data int
l    *tree
r    *tree
}

type list struct {
data int
next *list
}

//阶乘
func fact(n uint32) uint32 {
if n == 0 {
return 1
}
return n * fact(n-1)
}

//二分查找
func BSearch(a []int, element, low, height int) int {
if low > height {
return -1
}

mid := (low + height) / 2

if a[mid] == element {
return 0
} else if a[mid] > element {
return BSearch(a, element, low, mid-1)
} else {
return BSearch(a, element, mid+1, height)
}
}

//斐波那契数列--递归
func f(n int) int {
if n < 3 {
return 1
}
return f(n-1) + f(n-2)
}

//斐波那契数列--非递归
func f1(n int) int {

var s, s1, s2 int = 1, 1, 1

for i := 3; i <= n; i++ {
s = s1 + s2
s2 = s1
s1 = s
}
return s
}

//冒泡
func bubblesort(a []int, n int) {
//n个数据需要n-1趟
for i := 1; i < n; i++ {
//每趟需要比较 元素个数-1 次
for j := 0; j < n-i; j++ {
if a[j] > a[j+1] {
temp := a[j]
a[j] = a[j+1]
a[j+1] = temp
}
}
}
}

//反转链表
}
return ph
}

}
for node2 != nil {
node2.next = node1
node1.next = nil

node1 = node2
node2 = node3
node3 = node3.next
}

return node2

}

//将二叉搜索树转换成双向链表
func treeToDoubleList(head, tail *tree, root *tree) {
if root == nil {
tail = nil
return
}

if ltail != nil {
ltail.r = root
root.l = ltail
} else {
}

} else {
tail = root
}

}

//比较两个树是否相等
func compareTree(t1, t2 *tree) int {
if t1 == nil && t2 == nil {
return 1
}
if t1 == nil || t2 == nil {
return -1
}
if t1.data != t2.data {
return -1
}

if compareTree(t1.l, t2.l) == 1 && compareTree(t1.r, t2.r) == 1 {
return 1
} else {
return -1
}

}

//在二元树中找出和为某一值的所有路径
func getValuePath(root *tree, n int, sum int) {
if root == nil {
return
}

s.Push(root.data)

sum += root.data

if sum == n {
fmt.Println(s)
s.Pop()
return
}
getValuePath(root.l, n, sum)
getValuePath(root.r, n, sum)

s.Pop()

}

//获取最大子数组
func getMaxSubArray(a []int, n int) {
if n < 0 || a == nil {
return
}
var sum, begin, end, max int = 0, 0, 0, -1 << 31

for i := 0; i < n; i++ {
sum += a[i]
if sum < 0 {
sum = 0
begin = i + 1
}
if sum > max {
max = sum
end = i
}
}
fmt.Println(begin, end, max)
}

//判断整数序列是不是二元查找树的后序遍历结果
func checkPostOrder(a []int, l, h int, b *bool) {
if l >= h {
return
}
parent := a[h]
//fmt.Println(parent, l, h)
i := l
for ; i < h-1; i++ {
if a[i] > parent {
break
}
}

for j := i + 1; j < h; j++ {
if a[j] <= parent {
*b = false
break
}
}

if *b {
checkPostOrder(a, l, i-1, b)
checkPostOrder(a, i, h-1, b)
}
}

//^-反转句子里面单词的顺序
func swap(b []byte, begin, end int) {
if begin > end {
return
}
for begin <= end {
tmp := b[begin]
b[begin] = b[end]
b[end] = tmp

begin++
end--

}
}
func reverseStr(str *string) {

begin := 0

b := []byte(*str)

for i := 0; i < len(*str); i++ {
if b[i] == 32 {
swap(b, begin, i-1)
begin = i + 1
}
}
swap(b, begin, len(*str)-1)

//反转整个字符串
swap(b, 0, len(*str)-1)

fmt.Println(string(b))

}

//\$-反转句子里面单词的顺序

func main() {
/*
//var b uint32 = 6
//fmt.Println(b, "!=", fact(b))
//a := []int{1, 2, 4, 6, 7, 8, 9, 10, 11, 12}
//c := BSearch(a, 4, 0, 9)
//fmt.Println(c)
//t := []int{3, 2, 1, 5, 7, 6, 9, 0}
//bubblesort(t, 8)
//fmt.Println(t)
//t := []int{1, -2, 3, 10, -4, 7, 2, -5}

//getMaxSubArray(t1, len(t1))

t1 := tree{4, nil, nil}
t2 := tree{7, nil, nil}
t3 := tree{5, &t1, &t2}
t4 := tree{12, nil, nil}
root := tree{10, &t3, &t4}

getValuePath(&root, 22, 0)

t := []int{5, 7, 6, 9, 11, 20, 1, 8}
//t := []int{7, 4, 6, 5}
b := true
checkPostOrder(t, 0, 7, &b)
fmt.Println(b)
*/
str := "i am a student."
reverseStr(&str)

}
```