OJ_动态规划

发布时间 : 1996-07-30 00:00

阅读 :

https://leetcode.cn/company/bytedance/problemset/

func lengthOfLongestSubstring(s string) int {
  if len(s) == 0 {
    return 0
  }

  m := map[int]int{}

  i := 0
  res := 1
  
  m[int(s[i])]=i

  for j := 0; j < len(s) ; j++ {
    if v, ok := m[int(s[j])]; ok {
      if j == 0 || v == -1 {
        
      } else {
        for k := i ; k < v + 1 ; k ++ {
          m[int(s[k])] = -1
        }

        i = v + 1

        // fmt.Println("v", v)
        // fmt.Println("i", i)
        // fmt.Println(m)
      }
    }
    m[int(s[j])] = j


    if j - i + 1 > res {
      res = j - i + 1
      // fmt.Println("L32", "res", res)
    }
  }


  return res
}

居然忘记了map删除元素是delete(m, s[i-1])语句。。。
左指针带动右指针！相比我这一次的右指针带动左指针，更加简单！
数组长度为128可以覆盖ASCII字符范围
rune类型可以表示任意Unicode字符，并能存储一个32位的Unicode字符编码；byte和rune可以直接转换

此作为后续滑动窗口类的模板

func lengthOfLongestSubstring(s string) int {
  right, res := -1, 0
  a := [128]int{}
  n := len(s)

  for left := 0; left < n; left++ {
    if left != 0 {
      a[s[left-1]] = 0
    }

    for right + 1 < n && a[s[right+1]] == 0 {
      a[s[right+1]] = 1
      right ++
    }

    if right - left + 1 > res {
      res = right - left + 1
    }
  }

  return res
}

200. 岛屿数量

func numIslands(grid [][]byte) int {
  res := 0

  for i := 0 ; i < len(grid) ; i++ {
    for j := 0 ; j < len(grid[0]); j++ {
      if grid[i][j] == '1' {
        res += 1
        clearLand(grid, i, j)
      }
      
    }
  }

  return res
}

func clearLand(grid [][]byte, i, j int) {
  if i < 0 || j < 0 || i >= len(grid) || j >= len(grid[0]) {
    return 
  }
  if grid[i][j] == '0' {
    return
  }

  grid[i][j] = '0'
  clearLand(grid, i-1, j)
  clearLand(grid, i, j-1)
  clearLand(grid, i, j+1)
  clearLand(grid, i+1, j)
}

2. 两数相加

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
  return addList(l1, l2, false)
}


func addList(l1 *ListNode, l2 *ListNode, needUp bool) *ListNode {
  val := 0

  if l1 != nil {
    val += l1.Val
  }

  if l2 != nil {
    val += l2.Val
  }

  if needUp {
    val += 1
  }

  var upFlag bool
  if val >= 10 {
    val = val - 10
    upFlag = true
  }

  var next *ListNode
  if l1 == nil && l2 == nil {
    fmt.Println("here", upFlag)
    if val == 0 {
      return nil
    }
    return &ListNode{
      Val: 1,
      Next: nil,
    }
  } else if l1 != nil && l2 == nil {
    next = addList(l1.Next, nil, upFlag)
  } else if l1 == nil && l2 != nil {
    next = addList(nil, l2.Next, upFlag)
  } else {
    next = addList(l1.Next, l2.Next, upFlag)
  }

  return &ListNode{
    Val: val,
    Next: next,
  }
}

func reverseList(l *ListNode) *ListNode {
  var res *ListNode

  for l.Next != nil {
    tmpNode := &ListNode{
      Val: l.Val,
      Next: res,
    }
    res = tmpNode
  }

  return res
}

2. 两数相加

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
  return addList(l1, l2, false)
}


func addList(l1 *ListNode, l2 *ListNode, needUp bool) *ListNode {
  val := 0

  if l1 != nil {
    val += l1.Val
  }

  if l2 != nil {
    val += l2.Val
  }

  if needUp {
    val += 1
  }

  var upFlag bool
  if val >= 10 {
    val = val - 10
    upFlag = true
  }

  var next *ListNode
  if l1 == nil && l2 == nil {
    fmt.Println("here", upFlag)
    if val == 0 {
      return nil
    }
    return &ListNode{
      Val: 1,
      Next: nil,
    }
  } else if l1 != nil && l2 == nil {
    next = addList(l1.Next, nil, upFlag)
  } else if l1 == nil && l2 != nil {
    next = addList(nil, l2.Next, upFlag)
  } else {
    next = addList(l1.Next, l2.Next, upFlag)
  }

  return &ListNode{
    Val: val,
    Next: next,
  }
}

func reverseList(l *ListNode) *ListNode {
  var res *ListNode

  for l.Next != nil {
    tmpNode := &ListNode{
      Val: l.Val,
      Next: res,
    }
    res = tmpNode
  }

  return res
}

审题不仔细，多写了一个reverse。
归并只需要补零就好了，不需要使用递归。

146. LRU 缓存

type LRUCache struct {
  capacity int
  m map[int]ValStruc
  head *ListNode_
  tail *ListNode_
  length int
}

type ValStruc struct {
  val int
  loc *ListNode_
}

type ListNode_ struct {
  key int
  pre *ListNode_
  next *ListNode_
}

func (l *ListNode_) Show() {
  fmt.Print("head[")
  for l != nil {
    fmt.Print(l.key, " ")
    l = l.next
  }
  fmt.Print("]\n")
}


func (l *ListNode_) ShowReverse() {
  fmt.Print("tail[")
  for l != nil {
    fmt.Print(l.key, " ")
    l = l.pre
  }
  fmt.Print("]\n")
}


func (this *LRUCache) Show() {
  return
    this.head.Show()
    this.tail.ShowReverse()
    if this.tail != nil {
      fmt.Print("tail: ", this.tail.key, "\n")
    }
    if this.head != nil {
      fmt.Print("head: ", this.head.key, "\n")
    }
}

func Constructor(capacity int) LRUCache {
  return LRUCache{
    capacity: capacity,
    length: 0,
    m: map[int]ValStruc{},
    head: nil,
    tail: nil,
  }
}

func (this *LRUCache) Get(key int) int {
  fmt.Println("user get", key)
  valStruc, ok := this.m[key]
  if !ok {
    
    this.Show()
    return -1
  }

  this.moveToTail(key)

    this.Show()
  return valStruc.val
}


func (this *LRUCache) Put(key int, value int)  {
  fmt.Println("user put", key, value)
  v, ok := this.m[key]
  if ok && v.val != -1 {
    // this.moveToTail(key)
    temp := v.loc
    this.m[key] = ValStruc{
      val: value,
      loc: temp,
    }

    this.moveToTail(key)

    this.Show()
    return
  }

  // fmt.Println("length", this.length)
  if this.length >= this.capacity {
    this.removeOldestOne()
  } else {
    this.length ++
    // fmt.Println("length", this.length)
  }

  if this.tail == nil {
    this.tail = &ListNode_{
      key: key,
      next: nil,
      pre: nil,
    }
    this.head = this.tail
  } else {
    this.tail.next = &ListNode_{
      key: key,
      next: nil,
      pre: this.tail,
    }
    this.tail = this.tail.next
  }

  this.m[key] = ValStruc{
    val: value,
    loc: this.tail,
  }
  // fmt.Println(this.m)
    this.Show()
}

func (this *LRUCache) moveToTail(key int) {
  // fmt.Println("try move", key, "to tail")
  if this.tail.key == key {
    return
  }
  // fmt.Println("move", key, "to tail")

  // if this.m[key].loc == nil {
  //   fmt.Println("[panic]", "key: ", key, "value", this.m[key].val)
  // }
  
  // fmt.Println("move to tail", key, this.m[key].loc)

  // fmt.Println("now head", this.head.key, this.head)

  if this.head.key == key {
    // fmt.Println("ok")
    this.head = this.head.next
  }



  if this.m[key].loc.pre != nil {
    this.m[key].loc.pre.next = this.m[key].loc.next
  }
  if this.m[key].loc.next != nil {
    this.m[key].loc.next.pre = this.m[key].loc.pre
  }


  oldTail := this.tail

  this.tail.next = this.m[key].loc
  this.tail = this.m[key].loc
  this.tail.next = nil
  this.tail.pre = oldTail

  // fmt.Println("now head", this.head.key)
}

func (this *LRUCache) removeOldestOne() {
  if this.length == 0 {
    return
  }

  // fmt.Println("remove", this.head.key)

  // fmt.Println("this.head.key", this.head.key)
  // this.m[this.head.key] = ValStruc{
  //   val: -1,
  //   loc: nil,
  // }

  delete(this.m, this.head.key)

  if this.tail == this.head {
    this.tail = nil
    this.head = nil
  } else {
    this.head = this.head.next
  }

  if this.head != nil {
    this.head.pre = nil
  }


  // fmt.Println("remove, now head is", this.head.key)
  // fmt.Println(this.m)

}

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */

最长回文子串

func longestPalindrome(s string) string {
  var res string

  for i, c := range(s) {
    fmt.Println(c)

    tmp := getPalindrome(s, i)
    if len(tmp) > len(res) {
      res = tmp
    }
  }
  return res
}

func getPalindrome(s string, i int) string {
  a := getPalindromeA(s, i)
  b := getPalindromeB(s, i)

  if len(a) > len(b) {
    return a
  }
  return b
}

func getPalindromeA(s string, i int) string {
  l, r := i-1, i+1
  n := len(s)
  res := string(s[i])

  for l >= 0 && r < n  {
    if s[l] == s[r] {
      res = s[l: r+1]
      l--
      r++
    } else {
      break
    }
  }

  // fmt.Println(l)
  // fmt.Println(r)
  return res
}

func getPalindromeB(s string, i int) string {
  l, r := i, i+1
  n := len(s)
  res := ""

  for l >= 0 && r < n {
    if s[l] == s[r] {
      res = s[l:r+1]
      l--
      r++
    } else {
      break
    }
  }

  return res
}

15. 三数之和

// var mp map[int]int

var mp1 map[int]map[int]int

func threeSum(nums []int) [][]int {
  // mp = map[int]int{}

  mp1 = map[int]map[int]int{}

  sort.Ints(nums)
  res := [][]int{}
  // mp := map[int]bool{}

  for i, _ := range(nums) {
    // if _, ok := mp[v]; ok {
    //   continue
    // }

    res = append(res, find(nums, i)...)
    // mp[v] = true
    // fmt.Println(mp)
  }
  return res
}

func find(nums []int, i int) [][]int {
  l, r, n := i-1, i+1, len(nums)
  res := [][]int{}

  for l >= 0 && r < n {
    sum := nums[l] + nums[i] + nums[r]
    if sum == 0 {
      // v, ok := mp[nums[i]]
      // if !ok || v != nums[r] {
      //   res = append(res, []int{nums[l], nums[i], nums[r]})
      //   mp[nums[i]]= nums[r]
      //   fmt.Println(mp)
      // }
      if _, ok := mp1[nums[l]]; ok {
        // fmt.Println(mp1)
        if _, okk := mp1[nums[l]][nums[i]]; okk {
          // fmt.Println(nums[l], nums[i], nums[r])

          l--
          r++
          continue
        }
      }

      res = append(res, []int{nums[l], nums[i], nums[r]})
      if _, ok := mp1[nums[l]]; !ok {
        mp1[nums[l]] = map[int]int{}
      }
      mp1[nums[l]][nums[i]] = nums[r]

      l--
      r++
    } else if sum > 0 {
      l--
    } else {
      r++
    }
  }
  return res
}

切片排序 sort.Ints(nums)
2023/11/19，今天结束，明天开始记得开闹钟做题

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 nz_nuaa@163.com