数组

209. 长度最小的子数组

题目

image.png

思路

双指针，一开始都指向下标为0，开始移动右指针，移动的过程中计算求和，当求和大于target的时候就左指针右移一位。求和减去左指针的值。当右指针遍历完一遍，具体看下面代码

代码

  1. func minSubArrayLen(target int, nums []int) int {
  2.     i := 0            //左指针，j为右指针
  3.     l := len(nums)  // 数组长度
  4.     sum := 0        // 子数组之和
  5.     result := l + 1 // 初始化返回长度为l+1，目的是为了判断“不存在符合条件的子数组，返回0”的情况
  6.     for j := 0; j < l; j++ {
  7.         sum += nums[j]
  8.         for sum >= target { //这里注意是for 不是if
  9.             subLength := j - i + 1 //这是临时窗口长度
  10.             if subLength < result {
  11.                 result = subLength
  12.             }
  13.             sum -= nums[i]//这两句的意思是，只要sum>target
  14.             i++              //左指针就一直往右移动
  15.         }
  16.     }
  17.     if result == l+1 { //这里是如果全部都不符合条件
  18.         return 0
  19.     } else {
  20.         return result
  21.     }
  22. }

27. 移除元素

  1. func removeElement(nums []int, val int) int {
  2.     res := 0
  3.     for _,v :=range nums{
  4.         if v != val{
  5.             nums[res] = v
  6.             res++
  7.         }
  8.     }
  9.     return res
  10. }

977. 有序数组的平方

  1. func sortedSquares(nums []int) []int {
  2.     res := make([]int,len(nums))
  3.     length := len(nums)-1
  4.     l,r := 0,len(nums)-1
  5.     for l <= r{
  6.         if nums[l]*nums[l] <= nums[r]*nums[r]{
  7.             res[length] = nums[r]*nums[r]
  8.             r--
  9.             length--
  10.         }else{
  11.             res[length] = nums[l]*nums[l]
  12.             l++
  13.             length--
  14.         }
  15.     }
  16.     return res
  17. }

59. 螺旋矩阵 II

image.png

  1. func generateMatrix(n int) [][]int {
  2.     top, bottom := 0, n-1
  3.     left, right := 0, n-1
  4.     num := 1
  5.     tar := n * n
  6.     matrix := make([][]int, n)
  7.     for i := 0; i < n; i++ {
  8.         matrix[i] = make([]int, n)
  9.     }
  10.     for num <= tar {
  11.         for i := left; i <= right; i++ {
  12.             matrix[top][i] = num
  13.             num++
  14.         }
  15.         top++
  16.         for i := top; i <= bottom; i++ {
  17.             matrix[i][right] = num
  18.             num++
  19.         }
  20.         right--
  21.         for i := right; i >= left; i-- {
  22.             matrix[bottom][i] = num
  23.             num++
  24.         }
  25.         bottom--
  26.         for i := bottom; i >= top; i-- {
  27.             matrix[i][left] = num
  28.             num++
  29.         }
  30.         left++
  31.     }
  32.     return matrix
  33. }

链表

203. 移除链表元素

image.png
这里就涉及如下链表操作的两种方式：

  • 直接使用原来的链表来进行删除操作。
  • 设置一个虚拟头结点在进行删除操作。

移除头结点和移除其他节点的操作是不一样的，因为链表的其他节点都是通过前一个节点来移除当前节点，而头结点没有前一个节点。
所以头结点如何移除呢，其实只要将头结点向后移动一位就可以，这样就从链表中移除了一个头结点。
可以设置一个虚拟头结点，这样原链表的所有节点就都可以按照统一的方式进行移除了。
image.png

  1. //前面没想到的地方是设置虚拟节点以后不会怎么设置返回值，如果头节点被删掉，返回谁
  2. func removeElements(head *ListNode, val int) *ListNode {
  3.     dummyHead := &ListNode{}//这时候初始化为0，如果是var定义的话就初始化为nil
  4.     dummyHead.Next = head
  5.     cur := dummyHead
  6.     for cur != nil && cur.Next != nil {
  7.         if cur.Next.Val == val {
  8.             cur.Next = cur.Next.Next
  9.         } else {
  10.             cur = cur.Next
  11.         }
  12.     }
  13.     return dummyHead.Next
  14. }

206. 反转链表

image.png
首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。
然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。
为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。
接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。
最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。 此时我们return pre指针就可以了，pre指针就指向了新的头结点

  1. //这个是正确的，建议用这个
  2. func reverseList(head *ListNode) *ListNode {
  3.     var pre *ListNode
  4.     cur := head
  5.     for cur != nil {
  6.         next := cur.Next
  7.         cur.Next = pre
  8.         pre = cur
  9.         cur = next
  10.     }
  11.     return pre
  12. }
  13. //下面这个输出单个元素是错误的，错误的地方是没有提取保存cur的下一个值，就cur.Next = pre
  14. //这样，cur的下一个值就永远找不到了，所以在cur.Next = pre之前要保存一下下一个的节点
  15. func reverseList(head *ListNode) *ListNode {
  16.     var pre *ListNode
  17.     cur := head
  18.     for cur != nil{
  19.         cur.Next = pre
  20.         head = head.Next
  22.         pre = cur
  23.         cur = head
  24.     }
  25.     return pre
  26. }
  27. //下面这个是正确的
  28. func reverseList(head *ListNode) *ListNode {
  29.     var pre *ListNode
  30.     cur := head
  31.     for cur != nil{
  32.         head = head.Next
  33.         cur.Next = pre
  35.         pre = cur
  36.         cur = head
  37.     }
  38.     return pre
  39. }

这里空着设计链表和两两交换链表中的节点

19. 删除链表的倒数第 N 个结点

image.png

  1. //这里我错误的地方是没有设置虚拟头节点
  2. func removeNthFromEnd(head *ListNode, n int) *ListNode {
  3.     dummyHead := &ListNode{}
  4.     dummyHead.Next = head
  5.     cur := head
  6.     prev := dummyHead
  7.     i := 1
  8.     for cur != nil {
  9.         cur = cur.Next
  10.         if i > n {
  11.             prev = prev.Next
  12.         }
  13.         i++
  14.     }
  15.     prev.Next = prev.Next.Next
  16.     return dummyHead.Next
  17. }

面试题 02.07. 链表相交

image.png
使用哈希表

  1. func getIntersectionNode(headA, headB *ListNode) *ListNode {
  2.     m := make(map[*ListNode]int)
  3.     for headA != nil{
  4.         m[headA]++
  5.         headA = headA.Next
  6.     }
  7.     for headB != nil{
  8.         _,ok := m[headB]
  9.         if ok{
  10.             return headB
  11.         }
  12.         headB = headB.Next
  13.     }
  14.     return nil
  15. }

142. 环形链表 II

image.png

  1. func detectCycle(head *ListNode) *ListNode {
  2.     slow, fast := head, head
  3.     for fast != nil && fast.Next != nil {
  4.         slow = slow.Next
  5.         fast = fast.Next.Next
  6.         if slow == fast {
  7.             for slow != head {
  8.                 slow = slow.Next
  9.                 head = head.Next
  10.             }
  11.             return head
  12.         }
  13.     }
  14.     return nil
  15. }

哈希表

349. 两个数组的交集

image.png

  1. //我的写法
  2. func isAnagram(s string, t string) bool {
  3.     if len(s)!=len(t){
  4.         return false
  5.     }
  6.     m := make(map[byte]int)
  7.     for _,v := range s{
  8.         m[byte(v)]++
  9.     }
  10.     for _,k := range t{
  11.         _,ok := m[byte(k)]
  12.         if ok {
  13.             if m[byte(k)] == 0{
  14.                 return false
  15.             }else{
  16.                 m[byte(k)]--
  17.             }
  18.         }else{
  19.             return false
  20.         }
  21.     }
  22.     return true
  23. }
  24. //比较好的答案
  25. func isAnagram(s, t string) bool {
  26.     var c1, c2 [26]int
  27.     for _, ch := range s {
  28.         c1[ch-'a']++
  29.     }
  30.     for _, ch := range t {
  31.         c2[ch-'a']++
  32.     }
  33.     return c1 == c2
  34. }

349. 两个数组的交集

image.png

  1. //我的做法
  2. func intersection(nums1 []int, nums2 []int) []int {
  3.     m := make(map[int]int)
  4.     res := []int{}
  5.     for _,v := range nums1{
  6.         m[v]++
  7.     }
  8.     for _,k := range nums2{
  9.         _,ok := m[k]
  10.         if ok && m[k] != 0{
  11.             res = append(res,k)
  12.             m[k] = 0//这一步的意思就是，我往res中以及添加了k元素，后面再遇到就不再添加了
  13.         }
  14.     }
  15.     return res
  16. }
  17. //答案
  18. func intersection(nums1 []int, nums2 []int) []int {
  19.     res := []int{}
  20.     m := map[int]int{}
  21.     for _,v := range nums1{
  22.         m[v]++
  23.     }
  24.     for _,k := range nums2{
  25.         _,ok := m[k]
  26.         if ok != false{
  27.             res = append(res,k)
  28.             delete(m,k)
  29.         }
  30.     }
  31.     return res
  32. }

202. 快乐数

image.png
这道题目使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止。判断sum是否重复出现就可以使用哈希表。

  1. func isHappy(n int) bool {
  2.     m := make(map[int]bool)
  3.     for n != 1 && !m[n] {
  4.         n, m[n] = getSum(n), true
  5.     }
  6.     return n == 1
  7. }
  9. func getSum(n int) int {
  10.     sum := 0
  11.     for n > 0 {
  12.         sum += (n % 10) * (n % 10)
  13.         n = n / 10
  14.     }
  15.     return sum
  16. }

454. 四数相加 II

image.png

  1. func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
  2.     m := make(map[int]int)
  3.     count := 0
  4.     for _, v1 := range nums1 {
  5.         for _, v2 := range nums2 {
  6.             m[v1+v2]++
  7.         }
  8.     }
  9.     for _, v3 := range nums3 {
  10.         for _, v4 := range nums4 {
  11.             count += m[-v3-v4]
  12.         }
  13.     }
  14.     return count
  15. }

383. 赎金信

image.png

  1. //我的代码，没有标准答案好
  2. func canConstruct(ransomNote string, magazine string) bool {
  3.     m := make(map[byte]int)
  4.     for i,_ := range magazine{
  5.         m[magazine[i]]++
  6.     }
  7.     for i,_ := range ransomNote{
  8.         _,ok := m[ransomNote[i]]
  9.         if ok{
  10.             m[ransomNote[i]]--
  11.             if m[ransomNote[i]] == 0{
  12.                 delete(m,ransomNote[i])
  13.             }
  14.         }else{
  15.             return false
  16.         }
  17.     }
  18.     return true
  19. }
  20. //答案
  21. func canConstruct(ransomNote string, magazine string) bool {
  22.     record := make([]int, 26)
  23.     for _, v := range magazine {
  24.         record[v-'a']++
  25.     }
  26.     for _, v := range ransomNote {
  27.         record[v-'a']--
  28.         if record[v-'a'] < 0 {
  29.             return false
  30.         }
  31.     }
  32.     return true
  33. }

15. 三数之和

image.png

  1. func threeSum(nums []int)[][]int{
  2.     sort.Ints(nums)
  3.     res:=[][]int{}
  4.     for i:=0;i<len(nums)-2;i++{
  5.         n1:=nums[i]
  6.         if n1>0{
  7.             break
  8.         }
  9.         if i>0&&n1==nums[i-1]{
  10.             continue
  11.         }
  12.         l,r:=i+1,len(nums)-1
  13.         for l<r{
  14.             n2,n3:=nums[l],nums[r]
  15.             if n1+n2+n3==0{
  16.                 res=append(res,[]int{n1,n2,n3})
  17.                 for l<r&&nums[l]==n2{
  18.                     l++
  19.                 }
  20.                 for l<r&&nums[r]==n3{
  21.                     r--
  22.                 }
  23.             }else if n1+n2+n3<0{
  24.                 l++
  25.             }else {
  26.                 r--
  27.             }
  28.         }
  29.     }
  30.     return res
  31. }