526互联

代码随想录算法训练营第6天 | lc454、lc383、lc15、lc18

发布时间 2023-12-09 20:15:14作者: geJoyo

（本合集全部为Go语言实现）

相关文章链接：454题解 383题解 15题解 18题解
相关视频链接：

Leetcode454

状态：秒了
实现过程中的难点：思想就是利用哈希表将部分和记录下来，最终实现将n ^ 4转换为2 * n ^ 2

个人写法

func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
  note := make(map[int]int)
  for _, i := range nums1 {
    for _, j := range nums2 {
      note[i + j]++
    }
  }
  res := 0
  for _, i := range nums3 {
    for _, j := range nums4 {
      res += note[-(i + j)]
    }
  }
  return res
}

Leetcode383

状态：秒了
实现过程中的难点：跟字母异位词差不多

个人写法

func canConstruct(ransomNote string, magazine string) bool {
  note := make([]int, 26)
  for _, c := range magazine {
    note[c - 'a']++
  }
  for _, c := range ransomNote {
    if (note[c - 'a'] == 0) {
       return false
    }
    note[c - 'a']--
  }
  return true
}

Leetcodexxx

状态：卡了挺长时间的，主要是想用个Set但是Go没有内置的实现，也没有想到其实不用去重就可以保证结果集内的元素不重复
实现过程中的难点：着重是要想明白怎么操作才能使结果集不需要去重

关键点

需要首先明确是，一定是需要先排序，再把问题化简成两数之和的处理方式

  • 为什么想到可能有重复？
    • 首先参数的数字集合中会有重复，那么在遍历的时候，就有可能出现对于单个循环来说，两次进入循环时为同一个值，此时就有会出现结果集元素的重复
  • 如何解决？
    • 首先想到的就是在进入循环时，判断是否和上一次循环的值相同，但是又有另一个疑问
  • 如果本来结果集的元素内部就有相同的值，如[2, -1, -1]，那么对于第二个-1，会不会因为进入循环时的判断而跳过这个结果？
    • 不会。对于上述的结果集元素样式，第二个-1再首次取该值时，是和前一个元素判断的，也就是循环一定是取的最左层的-1，此时第三个元素也会在循环内部取到-1，因而不会导致跳过

个人写法

主体结构可以不包括代码中的if-break判断，这些都是剪枝的判断，可以降低代码执行时间

import "sort"

func threeSum(nums []int) [][]int {
  sort.Ints(nums)
  res := make([][]int, 0)
  if nums[len(nums) - 1] < 0 {
    return res
  }
  for i := 0; i < len(nums); i++ {
    if nums[i] > 0 {
      break
    }
    if i > 0 && nums[i] == nums[i - 1] {
      continue
    }
    j, k := i + 1, len(nums) - 1
    for j < k {
      if nums[i] + nums[j] > 0 || nums[k] < 0 {
        break
      }
      if j > i + 1 && nums[j] == nums[j - 1] {
        j++
        continue
      }
      curRes := nums[i] + nums[j] + nums[k]
      if curRes > 0 {
        k--
      } else if curRes < 0 {
        j++
      } else {
        res = append(res, []int {nums[i], nums[j], nums[k]})
        j++
        k--
      }
    }
  }
  return res
}

Leetcode18

状态：卡了一下，和上一题还是有区别的，主要是在目标值是0还是其他数的区别上
实现过程中的难点：实现上本质上还是在上一题的基础上套了一层。但目标值可能不是零，如果是0️，那么可以按上一题的一些判断一样进行剪枝，但是如果不是0，那么即使前几个数比目标值小，也可能因为后续几个数的相加而变大，因为后续的数也可能是正数，反之亦然

个人写法

import "sort"

func fourSum(nums []int, target int) [][]int {
  sort.Ints(nums)
  res := make([][]int, 0)
  for i := range nums {
    if i > 0 && nums[i] == nums[i - 1] {
      continue
    }
    for j := i + 1; j < len(nums); j++ {
      cur2 := nums[i] + nums[j]
      if j > i + 1 && nums[j] == nums[j - 1] {
        continue
      }
      m, n := j + 1, len(nums) - 1
      for m < n {
        cur3 := cur2 + nums[m]
        if m > j + 1 && nums[m] == nums[m - 1] {
          m++
          continue
        }
        curRes := cur3 + nums[n]
        if curRes > target {
          n--
        } else if curRes < target {
          m++
        } else {
          res = append(res, []int {nums[i], nums[j], nums[m], nums[n]})
          m++
          n--
        }
      }
    }
  }
  return res
}

今日收获

  • 复习了几数之和系列，有一些思想如果不写一些确实比较难想到

学习时长：3小时左右