无常是常

分享技术见解、学习心得和生活感悟

最新文章

链表

反转链表

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

import (
"fmt"
)

func main() {
head := &ListNode{
1, &ListNode{
2, &ListNode{
3, &ListNode{
4, &ListNode{
5, nil}},
},
},
}
for list := reverseList(head); list != nil; list = list.Next {
fmt.Println(list.Val)
}
}

type ListNode struct {
Val int
Next *ListNode
}

func reverseList(head *ListNode) *ListNode {
var cur, prev *ListNode = head, nil
for cur != nil {
cur.Next, prev, cur = prev, cur, cur.Next
}
return prev
}

交换相邻两个节点

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

import "fmt"

func main() {
head := &ListNode{
1, &ListNode{
2, &ListNode{
3, &ListNode{
4, nil},
},
},
}
for list := swapPairs(head); list != nil; list = list.Next {
fmt.Println(list.Val)
}
}

type ListNode struct {
Val int
Next *ListNode
}

func swapPairs(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
newHead := head.Next
head.Next = swapPairs(newHead.Next)
newHead.Next = head
return newHead
}

判断链表是否有环

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 main

import "fmt"

func main() {

cycle := &ListNode{
2, &ListNode{
0, &ListNode{
-4, nil}}}
cycle.Next.Next.Next = cycle
head := &ListNode{
3, cycle,
}

fmt.Println(hasCycle(head))
}

type ListNode struct {
Val int
Next *ListNode
}

func hasCycle(head *ListNode) bool {
if head == nil || head.Next == nil {
return false
}
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow, fast = slow.Next, fast.Next.Next
if slow == fast {
return true
}
}
return false
}

反转链表

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

import (
"fmt"
)

func main() {
head := &ListNode{
1, &ListNode{
2, &ListNode{
3, &ListNode{
4, &ListNode{
5, nil}},
},
},
}
for list := reverseList(head); list != nil; list = list.Next {
fmt.Println(list.Val)
}
}

type ListNode struct {
Val int
Next *ListNode
}

func reverseList(head *ListNode) *ListNode {
var cur, prev *ListNode = head, nil
for cur != nil {
cur.Next, prev, cur = prev, cur, cur.Next
}
return prev
}

交换相邻两个节点

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

import "fmt"

func main() {
head := &ListNode{
1, &ListNode{
2, &ListNode{
3, &ListNode{
4, nil},
},
},
}
for list := swapPairs(head); list != nil; list = list.Next {
fmt.Println(list.Val)
}
}

type ListNode struct {
Val int
Next *ListNode
}

func swapPairs(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
newHead := head.Next
head.Next = swapPairs(newHead.Next)
newHead.Next = head
return newHead
}

判断链表是否有环

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 main

import "fmt"

func main() {

cycle := &ListNode{
2, &ListNode{
0, &ListNode{
-4, nil}}}
cycle.Next.Next.Next = cycle
head := &ListNode{
3, cycle,
}

fmt.Println(hasCycle(head))
}

type ListNode struct {
Val int
Next *ListNode
}

func hasCycle(head *ListNode) bool {
if head == nil || head.Next == nil {
return false
}
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow, fast = slow.Next, fast.Next.Next
if slow == fast {
return true
}
}
return false
}

排序算法

排序算法

冒泡排序

双层循环,每次循环将最大的值放到数组的最后面,外层循环n次,内层循环n-i次完成排序,时间复杂度为O(n²)

1
2
3
4
5
6
7
8
9
func bubbleSort(arr []int) {
for i := 0; i < len(arr)-1; i++ {
for j := 0; j < len(arr)-i-1; j++ {
if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j]
}
}
}
}

选择排序

双层循环,每次循环找出arr[n-i]中最小的数与当前数进行交换,时间复杂度为O(n²)

1
2
3
4
5
6
7
8
9
10
11
func selectSort(arr []int) {
for i := 0; i < len(arr)-1; i++ {
var min = i
for j := i + 1; j < len(arr); j++ {
if arr[min] > arr[j] {
min = j
}
}
arr[i], arr[min] = arr[min], arr[i]
}
}

插入排序

双层循环,类似打扑克牌调整牌的顺序,每次循环对当前数字顺序进行插入调整,时间复杂度为O(n²)

1
2
3
4
5
6
7
8
9
10
11
func insertionSort(arr []int) {
for i := range arr {
preIndex := i - 1
current := arr[i]
for preIndex >= 0 && arr[preIndex] > current {
arr[preIndex+1] = arr[preIndex]
preIndex -= 1
}
arr[preIndex+1] = current
}
}

归并排序

分治的思想,时间复杂度O(N*logN)

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
func mergeSort(arr []int) []int {
if len(arr) < 2 {
return arr
}
i := len(arr) / 2
left := mergeSort(arr[:i])
right := mergeSort(arr[i:])
result := merge(left, right)
return result
}

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

堆排序

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

func sink(array []int, parentIndex int, length int) {
//保存父节点,用于最后的赋值
temp := array[parentIndex]
//左子节点
childIndex := 2*parentIndex + 1
//是否有左子节点
for childIndex < length {
//判断是否有右子节点,并且右子节点大于左子节点的值
if childIndex+1 < length && array[childIndex+1] > array[childIndex] {
childIndex++
}
//如果父节点大于任何一个子节点的值直接跳出
if temp >= array[childIndex] {
break
}
array[parentIndex] = array[childIndex]
parentIndex = childIndex
childIndex = 2*childIndex + 1
}
array[parentIndex] = temp
}

func heapSort(array []int) {
//构建大顶堆
for i := (len(array) - 2) / 2; i >= 0; i-- {
sink(array, i, len(array))
}
//将堆顶元素和最后一个元素交换,数组长度i--(相当于循环删除根顶部元素,然后sink 调整最大堆)
for i := len(array) - 1; i > 0; i-- {
array[i], array[0] = array[0], array[i]
sink(array, 0, i)
}
}

排序算法

冒泡排序

双层循环,每次循环将最大的值放到数组的最后面,外层循环n次,内层循环n-i次完成排序,时间复杂度为O(n²)

1
2
3
4
5
6
7
8
9
func bubbleSort(arr []int) {
for i := 0; i < len(arr)-1; i++ {
for j := 0; j < len(arr)-i-1; j++ {
if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j]
}
}
}
}

选择排序

双层循环,每次循环找出arr[n-i]中最小的数与当前数进行交换,时间复杂度为O(n²)

1
2
3
4
5
6
7
8
9
10
11
func selectSort(arr []int) {
for i := 0; i < len(arr)-1; i++ {
var min = i
for j := i + 1; j < len(arr); j++ {
if arr[min] > arr[j] {
min = j
}
}
arr[i], arr[min] = arr[min], arr[i]
}
}

插入排序

双层循环,类似打扑克牌调整牌的顺序,每次循环对当前数字顺序进行插入调整,时间复杂度为O(n²)

1
2
3
4
5
6
7
8
9
10
11
func insertionSort(arr []int) {
for i := range arr {
preIndex := i - 1
current := arr[i]
for preIndex >= 0 && arr[preIndex] > current {
arr[preIndex+1] = arr[preIndex]
preIndex -= 1
}
arr[preIndex+1] = current
}
}

归并排序

分治的思想,时间复杂度O(N*logN)

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
func mergeSort(arr []int) []int {
if len(arr) < 2 {
return arr
}
i := len(arr) / 2
left := mergeSort(arr[:i])
right := mergeSort(arr[i:])
result := merge(left, right)
return result
}

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

堆排序

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

func sink(array []int, parentIndex int, length int) {
//保存父节点,用于最后的赋值
temp := array[parentIndex]
//左子节点
childIndex := 2*parentIndex + 1
//是否有左子节点
for childIndex < length {
//判断是否有右子节点,并且右子节点大于左子节点的值
if childIndex+1 < length && array[childIndex+1] > array[childIndex] {
childIndex++
}
//如果父节点大于任何一个子节点的值直接跳出
if temp >= array[childIndex] {
break
}
array[parentIndex] = array[childIndex]
parentIndex = childIndex
childIndex = 2*childIndex + 1
}
array[parentIndex] = temp
}

func heapSort(array []int) {
//构建大顶堆
for i := (len(array) - 2) / 2; i >= 0; i-- {
sink(array, i, len(array))
}
//将堆顶元素和最后一个元素交换,数组长度i--(相当于循环删除根顶部元素,然后sink 调整最大堆)
for i := len(array) - 1; i > 0; i-- {
array[i], array[0] = array[0], array[i]
sink(array, 0, i)
}
}