算法-数组、链表

两数之和

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


func twoSum(nums []int, target int) []int {
    if nums == nil || len(nums) <= 1 {
        return nil
    }
    // a = target -b
    cache := make(map[int]int)
    for index, value := range nums {
        if otherIndex, ok := cache[target-value]; ok {
            return []int{index, otherIndex}
        }
        cache[value] = index
    }
    return nil
}

盛最多水的容器

 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


// 双指针
func maxArea(height []int) int {
	area, left, right := 0, 0, len(height)-1
	for left < right {
		newArea := getArea(left, right, height)
		area = getMax(newArea, area)
		if height[left] > height[right] {
			right--
		} else {
			left++
		}
	}
	return area
}

func getArea(left, right int, height []int) int {
	// 高选低的
	if height[left] > height[right] {
		return (right - left) * height[right]
	}
	return (right - left) * height[left]
}

func getMax(newArea, oldArea int) int {
	if newArea > oldArea {
		return newArea
	}
	return oldArea
}

移动零

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


func moveZeroes(nums []int)  {
	saveIndex := 0
	for index := 0; index < len(nums); index++ {
		if nums[index] != 0 {
			nums[saveIndex] = nums[index]
			if index != saveIndex {
				nums[index] = 0
			}
			// 放到下面++
			saveIndex++
		}
	}
}

爬楼梯

 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


// 递归
func climbStairs(n int) int {
	if n <= 2 {
		return n
	}
	cache := make(map[int]int)
	cache[1] = 1
	cache[2] = 2
	return climbStair(n, cache)
}

func climbStair(n int, cache map[int]int) int {
	if n <= 2 {
		return n
	}
	if setups, ok := cache[n]; ok {
		return setups
	}
	setups := climbStair(n-1, cache) + climbStair(n-2, cache)
	cache[n] = setups
	return setups
}

// ---- 动态规划
func climbStairs(n int) int {
	if n <= 2 {
		return n
	}
	events := make([]int, n+1)
	events[1] = 1
	events[2] = 2
	for index := 3; index <= n; index++ {
		events[index] = events[index-1] + events[index-2]
	}
	return events[n]
}

三数之和

 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


// 两数之和解法
func threeSum(nums []int) [][]int {
	var res [][]int
	if len(nums) < 3 {
		return res
	}
	sort.Ints(nums)
	cache := make(map[string]struct{})
	for index := 0; index < len(nums); index++ {
		twoRes := myTwoSum(nums[index+1:], -nums[index])
		for _, values := range twoRes {
			if _, ok := cache[fmt.Sprintf("%d,%d,%d", nums[index], values[0], values[1])]; !ok {
				cache[fmt.Sprintf("%d,%d,%d", nums[index], values[0], values[1])] = struct{}{}
				res = append(res, []int{nums[index], values[0], values[1]})
			}
		}
	}
	return res
}

func myTwoSum(nums []int, target int) [][]int {
	var res [][]int
	cache := make(map[int]struct{})
	for index := 0; index < len(nums); index++ {
		if _, ok := cache[target-nums[index]]; ok {
			res = append(res, []int{nums[index], target - nums[index]})
		} else {
			cache[nums[index]] = struct{}{}
		}
	}
	return res
}

// 夹逼法解法
func threeSum(nums []int) [][]int {
	var res [][]int
	if len(nums) < 3 {
		return res
	}
	sort.Ints(nums)
	cache := make(map[string]struct{})
	for index := 0; index < len(nums)-2; index++ {
		left, right := index+1, len(nums)-1
		for left < right {
			sum := nums[index] + nums[left] + nums[right]
			if sum == 0 {
				if _, ok := cache[fmt.Sprintf("%d,%d,%d", nums[index], nums[left], nums[right])]; !ok {
					cache[fmt.Sprintf("%d,%d,%d", nums[index], nums[left], nums[right])] = struct{}{}
					res = append(res, []int{nums[index], nums[left], nums[right]})
				}
				right--
				left++
			} else if sum > 0 {
				right--
			} else {
				left++
			}
		}
	}
	return res
}

反转链表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


func reverseList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	// pre = nil
	// 3->4->5
	// nil<-3<-4<-5
	var pre *ListNode
	for head != nil {
		next := head.Next
		// 当前节点的next变为前置节点
		head.Next = pre
		// 当前节点变为pre
		pre = head
		// 尝试进行下一次循环,覆盖head
		head = next
	}
	return pre
}

两两交换链表中的节点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


func swapPairs(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	curr, pre := head, head.Next
	// 一对节点反转即 pre.next = curr,head 变为pre,所以return pre
	// 那么curr的next就编程pre.next继续做反转的动作了
	curr.Next = swapPairs(pre.Next)
	pre.Next = curr

	return pre
}

环形链表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


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

环形链表II

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


func detectCycle(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return nil
	}
	slow, fast := head, head
	for slow != nil && fast != nil && fast.Next != nil {
		slow, fast = slow.Next, fast.Next.Next
		if slow == fast {
			break
		}
	}
	// 判断有环没
	if fast == nil || fast.Next == nil {
		return nil
	}

	slow = head
	// 相遇的时就是结果
	for slow != fast {
		slow = slow.Next
		fast = fast.Next
	}
	return slow
}

K个一组翻转链表

 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


func reverseKGroup(head *ListNode, k int) *ListNode {
	// 找到k个节点，然后反转，head就是当前链表的最后一个节点，那么head的next就是一个k个节点的开头
	if k <= 1 {
		return head
	}
	// 便利k-1次，因为head已经+1了, 记得判断curr不能等于nil
	curr := head
	for i := 0; i < k-1 && curr != nil; i++ {
		// 找到最后一个
		curr = curr.Next
	}
	// 不够k，直接返回head
	if curr == nil {
		return head
	}
	// 下个k链表
	next := curr.Next
	// 截断当前链表
	curr.Next = nil
	// 进行反转
	localReverse(head)
	// 继续反转下个k，然后head的Next就是下个链表
	head.Next = reverseKGroup(next, k)
	return curr
}

func localReverse(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	var pre *ListNode
	for head != nil {
		next := head.Next
		head.Next = pre
		pre = head
		head = next
	}
	return pre
}

删除链表倒数第n个结点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


func removeNthFromEnd(head *ListNode, n int) *ListNode {
	newList := &ListNode{Val: 0, Next: head}
	curr, fast := newList, head
	for setup := 0; setup < n; setup++ {
		fast = fast.Next
	}
	for fast != nil {
		fast = fast.Next
		curr = curr.Next
	}
	curr.Next = curr.Next.Next
	return newList.Next
}

求链表的中间结点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


func middleNode(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	slow, fast := head, head

	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	return slow
}

Contents