Leetcode 21-30

21. 合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

• code

  /**
   * Definition for singly-linked list.
   * type ListNode struct {
   *     Val int
   *     Next *ListNode
   * }
   */
  func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
      if l1 == nil {
          return l2
      }
      if l2 == nil {
          return l1
      }
      var root = new(ListNode)
      if l1.Val < l2.Val{
          root.Val = l1.Val
          l1 = l1.Next
      }else{
          root.Val = l2.Val
          l2 = l2.Next
      }
      if l1 !=nil || l2!=nil{
          root.Next = mergeTwoLists(l1, l2)
      }
      return root
  }

22. 括号生成

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
例如，给出 n = 3，生成结果为：
[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

• code

  func generateParenthesis(n int) []string {
      var ans = []string{}
      generate(&ans, "", 0, 0, n)
      return ans
  }
  
  
  func generate(ans *[]string,cur string,l int, r int, max int) {
      if len(cur) == max*2{
          *ans = append(*ans, cur)
      }
      if l < max{
           generate(ans, cur + "(", l+1, r, max)
      }
      if r < l{
          generate(ans, cur + ")", l, r+1, max)
      }
  }

23. 合并K个排序链表

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

• code

  /**
   * Definition for singly-linked list.
   * type ListNode struct {
   *     Val int
   *     Next *ListNode
   * }
   */
  func mergeKLists(lists []*ListNode) *ListNode {
      if len(lists) == 0 {
          return nil
      }
      if len(lists) == 1{
          return lists[0]
      } 
  
  
      return mergeTwoLists(mergeKLists(lists[:len(lists)/2]), mergeKLists(lists[len(lists)/2:]))
  }

24. 两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
说明:
你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

• code

  /**
   * Definition for singly-linked list.
   * type ListNode struct {
   *     Val int
   *     Next *ListNode
   * }
   */
  func swapPairs(head *ListNode) *ListNode {
      if head == nil || head.Next == nil{
          return head
      }
      p := head
      head = head.Next
      p.Next = swapPairs(head.Next)
      head.Next = p
      return head
  }

25. k个一组翻转链表

给出一个链表，每 k 个节点一组进行翻转，并返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么将最后剩余节点保> 持原有顺序。
示例 :
给定这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5
说明 :
你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

• code

  /**
   * Definition for singly-linked list.
   * type ListNode struct {
   *     Val int
   *     Next *ListNode
   * }
   */
  func reverseKGroup(head *ListNode, k int) *ListNode {
      if k == 1{
          return head
      }
      fake := &ListNode{Next: head}
      p := fake
      for p != nil{
          p.Next = reverseKNodes(p.Next, k)
          for i:=0; p!=nil && i<k; i++{
              p = p.Next
          }
      }
      return fake.Next
  }
  
  
  func reverseKNodes(head *ListNode, k int) *ListNode {
      end := head
      for end != nil && k>0{ // end 是结束后一个
          end = end.Next
          k--
      }
      if k > 0{
          return head
      }
  
      var qNode *ListNode
      var ret = end
      var node = head
  
      for node != end {
          qNode = node.Next
          node.Next = ret
          ret = node
          node = qNode
      }
      return ret
  }

26. 删除排序数组中的重复项

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

• code

  func removeDuplicates(nums []int) int {
      if len(nums) <= 1{
          return len(nums)
      }
      newLen:=1
      base:=nums[0]
  
      for i:=1; i<len(nums); i++{
          if nums[i] != base{
              nums[newLen],newLen,base = nums[i],newLen+1,nums[i]
          }
      }
      return newLen
  }

27. 移除元素

给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

• code

  func removeElement(nums []int, val int) int {
      ind:=0
      ret:=0
      for i:=range nums{
          if nums[i] != val{
              ret++
              nums[ind] = nums[i]
              ind++
          }
      }
      return ret
  }

28. 实现strStr()

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

解: 经典 KMP 算法

• code

  func strStr(haystack string, needle string) int {
      if needle == ""{
          return 0
      }
      return kmpIndex([]byte(haystack), []byte(needle))
  }
  
  func kmpIndex(s, p []byte) int {
      i := 0
      j := 0
      next := getNext(p)
      for i < len(s) && j < len(p) {
          if j == -1 || s[i] == p[j] {
              i++
              j++
          } else {
              j = next[j]
          }
      }
      if j == len(p) {
          return i - j
      }
      return -1
  }
  
  func getNext(ms []byte) []int {
      length := len(ms)
      next := make([]int, length)
      next[0] = -1
      k := -1
      j := 0
      for j < length-1 {
          if k == -1 || ms[j] == ms[k] {
              j++
              k++
              if ms[j] != ms[k] {
                  next[j] = k
              } else {
                  next[j] = next[k]
              }
          } else {
              k = next[k]
          }
      }
      return next
  }

29. 两数相除

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
示例 1:
输入: dividend = 10, divisor = 3
输出: 3
示例 2:
输入: dividend = 7, divisor = -3
输出: -2
说明:
被除数和除数均为 32 位有符号整数。
除数不为 0。
我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。

解: 分治法

• code

  func divide(dividend int, divisor int) int {
      if dividend < 0{
          if dividend > math.MinInt32{
              if divisor == math.MinInt32{
                  return 0
              }else{
                  return divide(0-dividend, 0-divisor)
              }
          }else{
              if divisor == math.MinInt32{
                  return 1
              }else if divisor == -1{
                  return math.MaxInt32
              } else{
                  if divisor > 0{
                      return divide(divisor+dividend, divisor)-1
                  }else{
                      return divide(dividend-divisor, divisor)+1
                  }
              }
          }
      }
      ret := 0
  
      if divisor > 0{
          sum := divisor
          for sum <= dividend{
              ret++
              sum += divisor
          }
      }else{
          sum := 0-divisor
          for sum <= dividend {
              ret--
              sum -= divisor
          }
      }
  
      return ret
  }

30. 与所有单词相关联的字串

给定一个字符串 s 和一些长度相同的单词 words。在 s 中找出可以恰好串联 words 中所有单词的子串的起始位置。

子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。

示例 1:

输入:
s = “barfoothefoobarman”,
words = [“foo”,”bar”]
输出: [0,9]
解释: 从索引 0 和 9 开始的子串分别是 “barfoor” 和 “foobar” 。
输出的顺序不重要, [9,0] 也是有效答案。
示例 2:

输入:
s = “wordgoodstudentgoodword”,
words = [“word”,”student”]
输出: []

• code

  func findSubstring(s string, words []string) []int {
      if len(s) == 0|| len(words) == 0{
          return nil
      }
      m1 := make(map[string]int)
      for _,word:=range words{
          m1[word] += 1
      }
      ret := []int{}
      sl := len(words[0])
  
      for i:=0; i<sl; i++{
          cm := make(map[string]int)
          c := 0
          ind := i
          for st:=i; st<len(s)-len(words)*sl+1; {
              w := s[ind:ind+sl]
              if wc,ok := m1[w]; ok{
                  if cm[w] == wc {
                      cm[s[st:st+sl]]-=1
                      c--
                      st += sl
                  }else{
                      cm[w] ++
                      ind += sl
                      if c == len(words)-1 {
                          ret =append(ret, st)
                          cm[s[st:st+sl]]-=1
                          st += sl
                      }else{
                           c++ 
                      }
                  }
              }else{
                  c = 0
                  ind += sl
                  st = ind
                  cm = make(map[string]int)
              }
          }
      }
      return ret
  }