Golang每日一练(leetDay0028) 删除排序链表中的重复元素I\II、柱状图中最大的矩形-阿里云开发者社区

Golang每日一练(leetDay0028) 删除排序链表中的重复元素I\II、柱状图中最大的矩形

2024-01-30 80

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： Golang每日一练(leetDay0028) 删除排序链表中的重复元素I\II、柱状图中最大的矩形

82. 删除排序链表中的重复元素 II Remove-duplicates-from-sorted-list-II

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

示例 1：

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

输出：[1,2,5]

示例 2：

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

输出：[2,3]

提示：

链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序排列

代码1：双指针

package main
import (
  "fmt"
)
type ListNode struct {
  Val  int
  Next *ListNode
}
func removeDuplicates(head *ListNode) *ListNode {
  if head == nil || head.Next == nil {
    return head
  }
  dummy := &ListNode{Val: 0, Next: head}
  pre := dummy
  cur := head
  for cur != nil {
    if cur.Next != nil && cur.Val == cur.Next.Val {
      // 相同节点一直跳过
      for cur.Next != nil && cur.Val == cur.Next.Val {
        cur = cur.Next
      }
      pre.Next = cur.Next
    } else {
      pre = pre.Next
    }
    cur = cur.Next
  }
  return dummy.Next
}
func build(list []int) *ListNode {
  head := &ListNode{Val: 0}
  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 main() {
  head := build([]int{1, 2, 3, 3, 4, 4, 5})
  removeDuplicates(head).travel()
  head = build([]int{1, 1, 1, 2, 3})
  removeDuplicates(head).travel()
}

输出：

1->2->5

2->3

代码2：递归法

package main
import (
  "fmt"
)
type ListNode struct {
  Val  int
  Next *ListNode
}
func removeDuplicates(head *ListNode) *ListNode {
  if head == nil || head.Next == nil {
    return head
  }
  if head.Val == head.Next.Val {
    for head.Next != nil && head.Val == head.Next.Val {
      head = head.Next
    }
    return removeDuplicates(head.Next)
  } else {
    head.Next = removeDuplicates(head.Next)
    return head
  }
}
func build(list []int) *ListNode {
  head := &ListNode{Val: 0}
  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 main() {
  head := build([]int{1, 2, 3, 3, 4, 4, 5})
  removeDuplicates(head).travel()
  head = build([]int{1, 1, 1, 2, 3})
  removeDuplicates(head).travel()
}

83. 删除排序链表中的重复元素 Remove-duplicates-from-sorted-list

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

示例 1：

输入：head = [1,1,2]

输出：[1,2]

示例 2：

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

输出：[1,2,3]

提示：

链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序排列

代码1：双指针

package main
import (
  "fmt"
)
type ListNode struct {
  Val  int
  Next *ListNode
}
func deleteDuplicates(head *ListNode) *ListNode {
  if head == nil || head.Next == nil {
    return head
  }
  pre := head
  cur := head.Next
  for cur != nil {
    if pre.Val == cur.Val {
      pre.Next = cur.Next
    } else {
      pre = cur
    }
    cur = cur.Next
  }
  return head
}
func build(list []int) *ListNode {
  head := &ListNode{Val: 0}
  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 main() {
  head := build([]int{1, 1, 2})
  deleteDuplicates(head).travel()
  head = build([]int{1, 1, 2, 3, 3})
  deleteDuplicates(head).travel()
}

双指针另一种写法：

func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    cur := head
    for cur.Next != nil {
        if cur.Val == cur.Next.Val {
            cur.Next = cur.Next.Next
        } else {
            cur = cur.Next
        }
    }
    return head
} 
输出：
1->2
1->2->3

代码2：递归法

递归处理子链表，如果子链表的头节点和下一个节点的值相等，则将头节点的 next 指针指向下一个节点的下一个节点，这样就可以删除重复节点。

package main
import (
  "fmt"
)
type ListNode struct {
  Val  int
  Next *ListNode
}
func deleteDuplicates(head *ListNode) *ListNode {
  if head == nil || head.Next == nil {
    return head
  }
  head.Next = deleteDuplicates(head.Next)
  if head.Val == head.Next.Val {
    return head.Next
  }
  return head
}
func build(list []int) *ListNode {
  head := &ListNode{Val: 0}
  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 main() {
  head := build([]int{1, 1, 2})
  deleteDuplicates(head).travel()
  head = build([]int{1, 1, 2, 3, 3})
  deleteDuplicates(head).travel()
}

84. 柱状图中最大的矩形 Largest-rectangle-in-histogram

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

输入：heights = [2,1,5,6,2,3]

输出：10

解释：最大的矩形为图中红色区域，面积为 10

示例 2：

输入： heights = [2,4]

输出： 4

提示：

1 <= heights.length <=10^5
0 <= heights[i] <= 10^4

代码1： 暴力枚举

package main
import "fmt"
func largestRectangleArea(heights []int) int {
  n := len(heights)
  maxArea := 0
  for i := 0; i < n; i++ {
    left, right := i, i
    for left >= 0 && heights[left] >= heights[i] {
      left--
    }
    for right < n && heights[right] >= heights[i] {
      right++
    }
    area := heights[i] * (right - left - 1)
    if area > maxArea {
      maxArea = area
    }
  }
  return maxArea
}
func main() {
  heights := []int{2, 1, 5, 6, 2, 3}
  fmt.Println(largestRectangleArea(heights))
  heights = []int{2, 4}
  fmt.Println(largestRectangleArea(heights))
}

输出：

代码2： 单调栈

package main
import "fmt"
func largestRectangleArea(heights []int) int {
  n := len(heights)
  stack := make([]int, 0)
  maxArea := 0
  for i := 0; i <= n; i++ {
    var curHeight int
    if i == n {
      curHeight = 0
    } else {
      curHeight = heights[i]
    }
    for len(stack) > 0 && curHeight < heights[stack[len(stack)-1]] {
      h := heights[stack[len(stack)-1]]
      stack = stack[:len(stack)-1]
      var w int
      if len(stack) == 0 {
        w = i
      } else {
        w = i - stack[len(stack)-1] - 1
      }
      area := h * w
      if area > maxArea {
        maxArea = area
      }
    }
    stack = append(stack, i)
  }
  return maxArea
}
func main() {
  heights := []int{2, 1, 5, 6, 2, 3}
  fmt.Println(largestRectangleArea(heights))
  heights = []int{2, 4}
  fmt.Println(largestRectangleArea(heights))
}

代码3： 分治法

package main
import "fmt"
func largestRectangleArea(heights []int) int {
  return helper(heights, 0, len(heights)-1)
}
func helper(heights []int, left, right int) int {
  if left > right {
    return 0
  }
  minIndex := left
  for i := left; i <= right; i++ {
    if heights[i] < heights[minIndex] {
      minIndex = i
    }
  }
  area1 := heights[minIndex] * (right - left + 1)
  area2 := helper(heights, left, minIndex-1)
  area3 := helper(heights, minIndex+1, right)
  return max(area1, max(area2, area3))
}
func max(a, b int) int {
  if a > b {
    return a
  }
  return b
}
func main() {
  heights := []int{2, 1, 5, 6, 2, 3}
  fmt.Println(largestRectangleArea(heights))
  heights = []int{2, 4}
  fmt.Println(largestRectangleArea(heights))
}