Golang每日一练(leetDay0007)

2023-05-26 101

版权

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

简介： Golang每日一练(leetDay0007)

19. 删除链表的倒数第 N 个结点 Remove-nth-node-from-end-of-list

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

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

输出：[1,2,3,5]

示例 2：

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

输出：[]

示例 3：

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

输出：[1]

提示：

链表中结点的数目为 sz

1 <= sz <= 30

0 <= Node.val <= 100

1 <= n <= sz

进阶：你能尝试使用一趟扫描实现吗？

代码：

package main
import (
  "fmt"
)
type ListNode struct {
  data int
  next *ListNode
}
func (head *ListNode) build(list []int) {
  for i := len(list) - 1; i >= 0; i-- {
    p := &ListNode{data: list[i]}
    p.next = head.next
    head.next = p
  }
}
func (head *ListNode) travel() {
  for p := head.next; p != nil; p = p.next {
    fmt.Print(p.data)
    if p.next != nil {
      fmt.Print("->")
    }
  }
  fmt.Println("<nil>")
}
func removeNthFromEnd(head *ListNode, n int) *ListNode {
  var fast, slow *ListNode
  fast = head
  slow = head
  for i := 0; i < n; i++ {
    fast = fast.next
  }
  if fast == nil {
    head = head.next
    return head
  }
  for fast.next != nil {
    fast = fast.next
    slow = slow.next
  }
  slow.next = slow.next.next
  return head
}
func main() {
  nums := []int{1, 2, 3, 4, 5}
  head := &ListNode{}
  head.build(nums)
  head.travel()
  head = removeNthFromEnd(head, 2)
  head.travel()
  head = &ListNode{}
  head.build([]int{1})
  head.travel()
  head = removeNthFromEnd(head, 1)
  head.travel()
  head = &ListNode{}
  head.build([]int{1, 2})
  head.travel()
  head = removeNthFromEnd(head, 1)
  head.travel()
}

输出：

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

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

1<nil>

<nil>

1->2<nil>

1<nil>

其他解法：

package main
import (
  "fmt"
)
type ListNode struct {
  data int
  next *ListNode
}
func (head *ListNode) build(list []int) {
  for i := len(list) - 1; i >= 0; i-- {
    p := &ListNode{data: list[i]}
    p.next = head.next
    head.next = p
  }
}
func (head *ListNode) travel() {
  for p := head.next; p != nil; p = p.next {
    fmt.Print(p.data)
    if p.next != nil {
      fmt.Print("->")
    }
  }
  fmt.Println("<nil>")
}
func removeNthFromEnd(head *ListNode, n int) *ListNode {
  if head == nil {
    return nil
  }
  len := countBackwards(head, n)
  if n >= len {
    return head.next
  }
  return head
}
func countBackwards(p *ListNode, n int) int {
  if p.next == nil {
    return 1
  }
  res := countBackwards(p.next, n) + 1
  if res == n+1 {
    if n == 1 {
      p.next = nil
    } else {
      p.next = p.next.next
    }
  }
  return res
}
func main() {
  nums := []int{1, 2, 3, 4, 5}
  head := &ListNode{}
  head.build(nums)
  head.travel()
  head = removeNthFromEnd(head, 2)
  head.travel()
  head = &ListNode{}
  head.build([]int{1})
  head.travel()
  head = removeNthFromEnd(head, 1)
  head.travel()
  head = &ListNode{}
  head.build([]int{1, 2})
  head.travel()
  head = removeNthFromEnd(head, 1)
  head.travel()
}

20. 有效的括号 Valid Parentheses

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1：

输入：s = "()"

输出：true

示例 2：

输入：s = "()[]{}"

输出：true

示例 3：

输入：s = "(]"

输出：false

示例 4：

输入：s = "([)]"

输出：false

示例 5：

输入：s = "{[]}"

输出：true

提示：

1 <= s.length <= 10^4

s 仅由括号 '()[]{}' 组成

代码：

package main
import (
  "fmt"
)
func isValid(s string) bool {
  stack := make([]byte, 0)
  for _, ch := range s {
    switch ch {
    case '(':
      fallthrough
    case '[':
      fallthrough
    case '{':
      stack = append(stack, byte(ch))
    case ')':
      if len(stack) > 0 && stack[len(stack)-1] == '(' {
        stack = stack[:len(stack)-1]
      } else {
        return false
      }
    case ']':
      if len(stack) > 0 && stack[len(stack)-1] == '[' {
        stack = stack[:len(stack)-1]
      } else {
        return false
      }
    case '}':
      if len(stack) > 0 && stack[len(stack)-1] == '{' {
        stack = stack[:len(stack)-1]
      } else {
        return false
      }
    }
  }
  return len(stack) == 0
}
func main() {
  fmt.Println(isValid("()"))
  fmt.Println(isValid("()[]{}"))
  fmt.Println(isValid("(]"))
  fmt.Println(isValid("([)]"))
  fmt.Println(isValid("{()}"))
}

输出：

true

false

true

21. 合并两个有序链表 Mmerge-two-sorted-lists

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]

输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []

输出：[]

示例 3：

输入：l1 = [], l2 = [0]

输出：[0]

提示：

两个链表的节点数目范围是 [0, 50]

-100 <= Node.val <= 100

l1 和 l2 均按非递减顺序排列

代码：

package main
import (
  "fmt"
)
type ListNode struct {
  data int
  next *ListNode
}
func (head *ListNode) build(list []int) {
  for i := len(list) - 1; i >= 0; i-- {
    p := &ListNode{data: list[i]}
    p.next = head.next
    head.next = p
  }
}
func (head *ListNode) travel() {
  for p := head.next; p != nil; p = p.next {
    fmt.Print(p.data)
    if p.next != nil {
      fmt.Print("->")
    }
  }
  fmt.Println("<nil>")
}
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
  res := &ListNode{}
  p := res
  for l1 != nil && l2 != nil {
    if l1.data < l2.data {
      p.next = l1
      l1 = l1.next
    } else {
      p.next = l2
      l2 = l2.next
    }
    p = p.next
  }
  if l1 != nil {
    p.next = l1
  } else {
    p.next = l2
  }
  return res.next
}
func main() {
  nums1 := []int{1, 2, 4}
  nums2 := []int{1, 3, 4}
  l1 := &ListNode{}
  l2 := &ListNode{}
  l1.build(nums1)
  l2.build(nums2)
  l1.travel()
  l2.travel()
  result := mergeTwoLists(l1, l2).next
  result.travel()
}

输出：

1->2->4<nil>

1->3->4<nil>

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

递归法：

package main
import (
  "fmt"
)
type ListNode struct {
  data int
  next *ListNode
}
func (head *ListNode) build(list []int) {
  for i := len(list) - 1; i >= 0; i-- {
    p := &ListNode{data: list[i]}
    p.next = head.next
    head.next = p
  }
}
func (head *ListNode) travel() {
  for p := head.next; p != nil; p = p.next {
    fmt.Print(p.data)
    if p.next != nil {
      fmt.Print("->")
    }
  }
  fmt.Println("<nil>")
}
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
  if l1 == nil {
    return l2
  }
  if l2 == nil {
    return l1
  }
  if l1.data < l2.data {
    l1.next = mergeTwoLists(l1.next, l2)
    return l1
  }
  l2.next = mergeTwoLists(l1, l2.next)
  return l2
}
func main() {
  n1 := []int{1, 2, 4}
  n2 := []int{1, 3, 4}
  l1 := &ListNode{}
  l2 := &ListNode{}
  l1.build(n1)
  l2.build(n2)
  l1.travel()
  l2.travel()
  result := mergeTwoLists(l1, l2).next
  result.travel()
}