Golang每日一练(leetDay0050) 对链表进行插入排序

147. 对链表进行插入排序 Insertion Sort List

head

插入排序 算法的步骤:

插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。

下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。

对链表进行插入排序。

示例 1：

输入: head = [4,2,1,3]
输出: [1,2,3,4]

示例 2：

输入: head = [-1,5,3,4,0]
输出: [-1,0,3,4,5]

提示：

[1, 5000]-5000 <= Node.val <= 5000

代码： 插入排序

package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func build(list []int) *ListNode {
	head := &ListNode{Val: -1 << 31} //-5000 <= Node.val <= 5000
	for i := len(list) - 1; i >= 0; i-- {
		p := &ListNode{Val: list[i]}
		p.Next = head.Next
		head.Next = p
	}
	return head
}

func (head *ListNode) travel() {
	for p := head.Next; p != nil; p = p.Next {
		fmt.Print(p.Val)
		if p.Next != nil {
			fmt.Print("->")
		}
	}
	fmt.Println("<nil>")
}

func insertionSortList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	dummy := &ListNode{}
	dummy.Next = head
	cur := head.Next
	lastSorted := head
	for cur != nil {
		if cur.Val >= lastSorted.Val {
			lastSorted = lastSorted.Next
		} else {
			prev := dummy
			for prev.Next.Val < cur.Val {
				prev = prev.Next
			}
			lastSorted.Next = cur.Next
			cur.Next = prev.Next
			prev.Next = cur
		}
		cur = lastSorted.Next
	}
	return dummy.Next
}

func main() {
	nums := []int{4, 2, 1, 3}
	head := build(nums)
	head.travel()
	head = insertionSortList(head)
	head.travel()
	nums2 := []int{-1, 5, 3, 4, 0}
	head2 := build(nums2)
	head2.travel()
	head2 = insertionSortList(head2)
	head2.travel()
}

输出：

4->2->1->3<nil>
1->2->3->4<nil>
-1->5->3->4->0<nil>
-1->0->3->4->5<nil>

148. 排序链表 Sort List

head

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

输入：head = []
输出：[]

提示：

[0, 5 * 10^4]-10^5 <= Node.val <= 10^5

O(nlogn)

代码： 归并排序，与147题对比多了对时间和空间复杂度的要求

package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func build(list []int) *ListNode {
	head := &ListNode{Val: -1 << 31} //-5000 <= Node.val <= 5000
	for i := len(list) - 1; i >= 0; i-- {
		p := &ListNode{Val: list[i]}
		p.Next = head.Next
		head.Next = p
	}
	return head
}

func (head *ListNode) travel() {
	for p := head.Next; p != nil; p = p.Next {
		fmt.Print(p.Val)
		if p.Next != nil {
			fmt.Print("->")
		}
	}
	fmt.Println("<nil>")
}

func sortList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	slow, fast := head, head.Next
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	mid := slow.Next
	slow.Next = nil
	left := sortList(head)
	right := sortList(mid)
	return merge(left, right)
}

func merge(a, b *ListNode) *ListNode {
	dummy := &ListNode{}
	cur := dummy
	for a != nil && b != nil {
		if a.Val < b.Val {
			cur.Next = a
			a = a.Next
		} else {
			cur.Next = b
			b = b.Next
		}
		cur = cur.Next
	}
	if a != nil {
		cur.Next = a
	} else {
		cur.Next = b
	}
	return dummy.Next
}

func main() {
	nums := []int{4, 2, 1, 3}
	head := build(nums)
	head.travel()
	head = sortList(head)
	head.travel()
	nums2 := []int{-1, 5, 3, 4, 0}
	head2 := build(nums2)
	head2.travel()
	head2 = sortList(head2)
	head2.travel()
}

输出：

4->2->1->3<nil>
1->2->3->4<nil>
-1->5->3->4->0<nil>
-1->0->3->4->5<nil>

149. 直线上最多的点数 Max Points On A Line

pointspoints[i] = [xi, yi]

示例 1：

输入：points = [[1,1],[2,2],[3,3]]
输出：3

示例 2：

输入：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出：4

提示：

1 <= points.length <= 300points[i].length == 2-10^4 <= xi, yi <= 10^4points

代码1： 暴力枚举

package main

import (
	"fmt"
)

func maxPoints(points [][]int) int {
	if len(points) < 3 {
		return len(points)
	}
	ans := 0
	for i := 0; i < len(points); i++ {
		kMap := make(map[Fraction]int)
		same := 1
		for j := i + 1; j < len(points); j++ {
			dx, dy := points[i][0]-points[j][0], points[i][1]-points[j][1]
			if dx == 0 && dy == 0 {
				same++
				continue
			}
			gcd := GCD(dx, dy)
			f := Fraction{
				Numerator:   dy / gcd,
				Denominator: dx / gcd,
			}
			kMap[f]++
		}
		maxCnt := 0
		for _, cnt := range kMap {
			if cnt > maxCnt {
				maxCnt = cnt
			}
		}
		ans = max(ans, maxCnt+same)
	}
	return ans
}

type Fraction struct {
	Numerator   int
	Denominator int
}

func GCD(a, b int) int {
	if b == 0 {
		return a
	}
	return GCD(b, a%b)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	points := [][]int{{1, 1}, {2, 2}, {3, 3}}
	fmt.Println(maxPoints(points))
	points = [][]int{{1, 1}, {3, 2}, {5, 3}, {4, 1}, {2, 3}, {1, 4}}
	fmt.Println(maxPoints(points))
}

代码2： 哈希表

package main

import (
	"fmt"
)

func maxPoints(points [][]int) int {
	if len(points) < 2 {
		return len(points)
	}
	ans := 1
	for i, p := range points {
		if ans >= len(points)-i {
			break
		}
		cnt := map[fraction]int{}
		for _, q := range points[i+1:] {
			k := newFraction(p, q)
			cnt[*k]++
		}
		for _, c := range cnt {
			ans = max(ans, c+1)
		}
	}
	return ans
}

type fraction struct {
	dx, dy int
}

func newFraction(p, q []int) *fraction {
	dx, dy := p[1]-q[1], p[0]-q[0]
	if dx == 0 {
		dy = 1
	} else if dy == 0 {
		dx = 1
	} else if dy < 0 {
		dx, dy = -dx, -dy
	}
	g := gcd(abs(dx), abs(dy))
	return &fraction{dx / g, dy / g}
}

func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	points := [][]int{{1, 1}, {2, 2}, {3, 3}}
	fmt.Println(maxPoints(points))
	points = [][]int{{1, 1}, {3, 2}, {5, 3}, {4, 1}, {2, 3}, {1, 4}}
	fmt.Println(maxPoints(points))
}

输出：

3
4

150. 逆波兰表达式求值 Evaluate Reverse Polish Notation

根据逆波兰表示法，求表达式的值。

+-*/

注意两个整数之间的除法只保留整数部分。

可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：

输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

提示：

1 <= tokens.length <= 10^4tokens[i]"+""-""*""/"[-200, 200]

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

( 1 + 2 ) * ( 3 + 4 )( ( 1 2 + ) ( 3 4 + ) * )

逆波兰表达式主要有以下两个优点：

1 2 + 3 4 + *

代码1： 栈 stack

package main

import (
	"fmt"
	"strconv"
)

func evalRPN(tokens []string) int {
	stack := make([]int, 0)
	for _, t := range tokens {
		if t == "+" {
			a, b := stack[len(stack)-2], stack[len(stack)-1]
			stack = stack[:len(stack)-2]
			stack = append(stack, a+b)
		} else if t == "-" {
			a, b := stack[len(stack)-2], stack[len(stack)-1]
			stack = stack[:len(stack)-2]
			stack = append(stack, a-b)
		} else if t == "*" {
			a, b := stack[len(stack)-2], stack[len(stack)-1]
			stack = stack[:len(stack)-2]
			stack = append(stack, a*b)
		} else if t == "/" {
			a, b := stack[len(stack)-2], stack[len(stack)-1]
			stack = stack[:len(stack)-2]
			stack = append(stack, a/b)
		} else {
			num, _ := strconv.Atoi(t)
			stack = append(stack, num)
		}
	}
	return stack[0]
}

func main() {
	tokens := []string{"2", "1", "+", "3", "*"}
	fmt.Println(evalRPN(tokens))
	tokens = []string{"4", "13", "5", "/", "+"}
	fmt.Println(evalRPN(tokens))
	tokens = []string{"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"}
	fmt.Println(evalRPN(tokens))
}

代码2： DFS 递归

package main

import (
	"fmt"
	"strconv"
)

func evalRPN(tokens []string) int {
	var dfs func() int
	dfs = func() int {
		if len(tokens) == 0 {
			return 0
		}
		op := tokens[len(tokens)-1]
		tokens = tokens[:len(tokens)-1]
		if op == "+" {
			return dfs() + dfs()
		} else if op == "-" {
			a, b := dfs(), dfs()
			return b - a
		} else if op == "*" {
			return dfs() * dfs()
		} else if op == "/" {
			a, b := dfs(), dfs()
			return b / a
		} else {
			num, _ := strconv.Atoi(op)
			return num
		}
	}
	return dfs()
}

func main() {
	tokens := []string{"2", "1", "+", "3", "*"}
	fmt.Println(evalRPN(tokens))
	tokens = []string{"4", "13", "5", "/", "+"}
	fmt.Println(evalRPN(tokens))
	tokens = []string{"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"}
	fmt.Println(evalRPN(tokens))
}

输出：

9
6
22

✨ 持续，努力奋斗做强刷题搬运工！

👍 点赞，你的认可是我坚持的动力！

🌟 收藏，你的青睐是我努力的方向！

✎ 评论，你的意见是我进步的财富！