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
给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。
示例 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 <= 300
points[i].length == 2
-10^4 <= xi, yi <= 10^4
points 中的所有点 互不相同
代码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^4
tokens[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
