Golang每日一练(leetDay0055) 最长子串、相交链表

简介: Golang每日一练(leetDay0055) 最长子串、相交链表

159.至多包含两个不同字符的最长子串  Longest-substring-with-at-most-two-distinct-characters


给定一个字符串 s ,找出至多包含两个不同字符的最长子串 t 。


示例 1:

输入:"eceba"

输出:3

解释:t 是 "ece",长度为3。


示例 2:

输入:"ccaabbb"

输出:5

解释:t 是 "aabbb",长度为5。


代码1:滑动窗口

package main
import "fmt"
func lengthOfLongestSubstringTwoDistinct(s string) int {
  n := len(s)
  if n <= 2 {
    return n
  }
  left, right := 0, 0
  charsCount := make(map[byte]int)
  maxLen := 0
  for right < n {
    charsCount[s[right]]++
    for len(charsCount) > 2 {
      charsCount[s[left]]--
      if charsCount[s[left]] == 0 {
        delete(charsCount, s[left])
      }
      left++
    }
    maxLen = max(maxLen, right-left+1)
    right++
  }
  return maxLen
}
func max(x, y int) int {
  if x > y {
    return x
  }
  return y
}
func main() {
  str := "eceba"
  fmt.Println(lengthOfLongestSubstringTwoDistinct(str))
  str = "ccaabbb"
  fmt.Println(lengthOfLongestSubstringTwoDistinct(str))
}


代码2:双指针

package main
import "fmt"
func lengthOfLongestSubstringTwoDistinct(s string) int {
  n := len(s)
  if n <= 2 {
    return n
  }
  left, right := 0, 0
  charsCount := make(map[byte]int)
  maxLen := 0
  num := 0
  for right < n {
    charsCount[s[right]]++
    if charsCount[s[right]] == 1 {
      num++
    }
    right++
    for num > 2 {
      charsCount[s[left]]--
      if charsCount[s[left]] == 0 {
        num--
      }
      left++
    }
    maxLen = max(maxLen, right-left)
  }
  return maxLen
}
func max(x, y int) int {
  if x > y {
    return x
  }
  return y
}
func main() {
  str := "eceba"
  fmt.Println(lengthOfLongestSubstringTwoDistinct(str))
  str = "ccaabbb"
  fmt.Println(lengthOfLongestSubstringTwoDistinct(str))
}


输出:

3

5


160. 相交链表 Intersection-of-two-linked-lists


给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。


图示两个链表在节点 c1 开始相交:

260e3c31ccfd1daaa1176143d0778007.png

题目数据 保证 整个链式结构中不存在环。

注意,函数返回结果后,链表必须 保持其原始结构 。


自定义评测:


评测系统 的输入如下(你设计的程序 不适用 此输入):


   intersectVal - 相交的起始节点的值。如果不存在相交节点,这一值为 0

   listA - 第一个链表

   listB - 第二个链表

   skipA - 在 listA 中(从头节点开始)跳到交叉节点的节点数

   skipB - 在 listB 中(从头节点开始)跳到交叉节点的节点数


评测系统将根据这些输入创建链式数据结构,并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点,那么你的解决方案将被 视作正确答案 。


示例 1:

4f1c24ca6111b454bec89afaa77d15eb.png

输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3

输出:Intersected at '8'


解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。

从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,6,1,8,4,5]。

在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。


示例 2:

f73a5d044e3ee38231bf689dc543d7f7.png

输入:intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1

输出:Intersected at '2'


解释:相交节点的值为 2 (注意,如果两个链表相交则不能为 0)。

从各自的表头开始算起,链表 A 为 [1,9,1,2,4],链表 B 为 [3,2,4]。

在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。


示例 3:

输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2

输出:null

解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。

由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。

这两个链表不相交,因此返回 null 。


提示:

   listA 中节点数目为 m

   listB 中节点数目为 n

   1 <= m, n <= 3 * 10^4

   1 <= Node.val <= 10^5

   0 <= skipA <= m

   0 <= skipB <= n

   如果 listA 和 listB 没有交点,intersectVal 为 0

   如果 listA 和 listB 有交点,intersectVal == listA[skipA] == listB[skipB]

进阶:你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案?


代码:

package main
import "fmt"
type ListNode struct {
  Val  int
  Next *ListNode
}
var (
  skipA        = 0
  skipB        = 0
  intersectVal = 0
)
func build(list []int) *ListNode {
  head := &ListNode{Val: -1 << 31}
  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() {
  if head != nil {
    for p := head.Next; p != nil; p = p.Next {
      fmt.Print(p.Val)
      if p.Next != nil {
        fmt.Print("->")
      }
    }
  }
  fmt.Println("<nil>")
}
func getIntersectionNode(headA, headB *ListNode) *ListNode {
  pointA, pointB := headA, headB
  for skipA > 0 {
    pointA = pointA.Next
    skipA--
  }
  for skipB > 0 {
    pointB = pointB.Next
    skipB--
  }
  if isSameList(pointA, pointB) {
    return pointA
  }
  return nil
}
func isSameList(l1, l2 *ListNode) bool {
  for l1 != nil && l2 != nil {
    if l1.Val != l2.Val {
      return false
    }
    l1 = l1.Next
    l2 = l2.Next
  }
  return l1 == nil && l2 == nil
}
func main() {
  nums1 := []int{4, 1, 8, 4, 5}
  nums2 := []int{5, 6, 1, 8, 4, 5}
  headA := build(nums1)
  headB := build(nums2)
  headA.travel()
  headB.travel()
  skipA, skipB = 2, 3
  intersectVal = 8
  IntersectionNode := getIntersectionNode(headA, headB)
  IntersectionNode.travel()
}


输出:

4->1->8->4->5<nil>

5->6->1->8->4->5<nil>

8->4->5<nil>

目录
打赏
0
0
0
0
74
分享
相关文章
|
10月前
|
【力扣刷题】两数求和、移动零、相交链表、反转链表
【力扣刷题】两数求和、移动零、相交链表、反转链表
64 2
【力扣刷题】两数求和、移动零、相交链表、反转链表
|
5月前
|
❤️算法笔记❤️-(每日一刷-160、相交链表)
❤️算法笔记❤️-(每日一刷-160、相交链表)
36 1
|
5月前
【数据结构】环形、相交、回文、分割、合并、反转链表
【数据结构】环形、相交、回文、分割、合并、反转链表
44 0
|
8月前
【数据结构OJ题】相交链表
力扣题目——相交链表
50 1
【数据结构OJ题】相交链表
|
7月前
|
【Leetcode刷题Python】106.相交链表
采用双指针法来找出两个链表的相交起始节点,并详细解释了算法的时间和空间复杂度。
50 1
深入解析力扣160题:相交链表的解决方法(哈希表法与双指针法详细图解)
深入解析力扣160题:相交链表的解决方法(哈希表法与双指针法详细图解)
【数据结构与算法 经典例题】相交链表求交点
【数据结构与算法 经典例题】相交链表求交点
|
9月前
|
Go
Go语言每日一练链表篇(一)
Go语言每日一练链表篇(一)