Leetcode-数组系列3 | 顾澜的技术小站

返回总目录

204. 计数质数

解题思路

根据质数定义可知，除了1和它本身意外不再有其他因数的自然数。对于每一个x，我们可以枚举[2, x-1]中的每个数y，判断y是否是x的因数。如果y是x的因数，那么y永远在[2, √x]范围内

示例代码

func countPrimes(n int) int {
   var count int
   for i := 2; i < n; i++ {
      if isPrime(i) {
         count++
      }
   }
   return count
}

func isPrime(x int) bool {
   for i := 2; i*i <= x; i++ {
      if x%i == 0 {
         return false
      }
   }
   return true
}

解题思路

厄拉多塞筛法的定义不再详细解释，大致的意思是：如果x是质数，那么2x，3x，4x….一定不是质数。定义一个数组isPrime表示是否为质数，如果isPrime[i]是质数，就将i的倍数全部标记为非质数。

示例代码

func countPrimes(n int) int {
   var count int
   isPrime := make([]bool, n)
   for i := 0; i < n; i++ {
      isPrime[i] = true
   }
   for i := 2; i < n; i++ {
      if isPrime[i] {
         count++
         for j := i * 2; j < n; j += i {
            isPrime[j] = false
         }
      }
   }
   return count
}

解题思路

思路来自于埃氏筛，我们将已知的质数存放与一个数组中，遍历数组取出质数x，我们不再标记x的倍数，而是标记质数集合每一项与当前i乘积，切当i为质数倍数时结束当前标记，避免了重复标记

示例代码

func countPrimes(n int) int {
   primes := []int{}
   isPrime := make([]bool, n)
   for i := 0; i < n; i++ {
      isPrime[i] = true
   }
   for i := 2; i < n; i++ {
      if isPrime[i] {
         primes = append(primes, i)
      }
      for _, prime := range primes {
         if i*prime >= n {
            break
         }
         isPrime[i*prime] = false
         if i%prime == 0 {
            break
         }
      }
   }
   return len(primes)
}

303. 区域和检索 - 数组不可变

解题思路

将原数组存放在NumArray中，在SumRange中求i到j的和即可

示例代码

type NumArray struct {
   sums []int
}

func Constructor(nums []int) NumArray {
   sums := make([]int, len(nums))
   for i, v := range nums {
      sums[i] = v
   }
   return NumArray{sums: sums}
}

func (this *NumArray) SumRange(left int, right int) int {
   var count int
   for i := left; i <= right; i++ {
      count += this.sums[i]
   }
   return count
}

解题思路

假设数组nums的长度为n，创建长度为n+1的数组sums，对于0 ≤ i < n都有sums[i+1] = sums[i] + nums[i]，sums[i]表示了nums从下标0到i-1的前缀和，因为前缀和数组sums的长度为n+1的缘故，不需要对i = 0进行额外处理，所以：sumRange(i,j)=sums[j+1]−sums[i]

示例代码

type NumArray struct {
   sums []int
}

func Constructor(nums []int) NumArray {
   sums := make([]int, len(nums)+1)
   for i, num := range nums {
      sums[i+1] = sums[i] + num // sum[i+1]存储nums[i]的前缀和
   }
   return NumArray{sums: sums}
}

func (this *NumArray) SumRange(left int, right int) int {
   return this.sums[right+1] - this.sums[left]
}

349. 两个数组的交集

解题思路

创建key为int，value为bool的map，遍历nums1，将数值的元素为key值为true存入map，循环nums2，判断map中是否存在，存在则表示此数在两数组中同事存在，为了避免重复添加，将值改为flase，判断是改为map中存在切值为true。

处于节省空间考虑，建立map数组时应尽量使用较小的数组

实例代码

func intersection(nums1 []int, nums2 []int) []int {
   if len(nums1) > len(nums2){ // 遍历较小的数组生成map
      intersection(nums2, nums1)
   }
   var intersection []int
   mapList := make(map[int]bool)
   for _, v := range nums1 {
      mapList[v] = true
   }

   for _, v := range nums2 {
      if _, ok := mapList[v]; ok && mapList[v] {
         intersection = append(intersection, v)
         mapList[v] = false
      }
   }
   return intersection
}

解题思路

先对两个数组排序，然后双指针循环两个数组，判断指针指向的数是否相等，若相等，则指针后移，交集中不存在则添加值交集数组中，指针所在数不相等则判断两数的大小，较小的数指针后移

示例代码

func intersection(nums1 []int, nums2 []int) []int {
   var intersection []int
   sort.Ints(nums1)
   sort.Ints(nums2)
   for i,j := 0,0; i<len(nums1) && j <len(nums2); {
      if nums1[i] == nums2[j] {
         if intersection == nil || intersection[len(intersection)-1] != nums1[i] {
            intersection = append(intersection, nums1[i])
         }
         i++
         j++
      }else if nums1[i] > nums2[j]{
         j++
      } else {
         i++
      }
   }
   return intersection
}

350. 两个数的交集 II

解题思路

基于349的map思路，将map的值由bool换成int，循环第一个数组时，记录出现的值的次数，循环第二个数组时判断是否存在且剩余个数大于1则添加为交集

实例代码

func intersect(nums1 []int, nums2 []int) []int {
   if len(nums1) > len(nums2) { // 遍历较小的数组生成map
      intersect(nums2, nums1)
   }
   var intersection []int
   mapList := make(map[int]int)
   for _, v := range nums1 {
      mapList[v] ++
   }

   for _, v := range nums2 {
      if _, ok := mapList[v]; ok && mapList[v] > 0 {
         intersection = append(intersection, v)
         mapList[v] --
      }
   }
   return intersection
}

解题思路

因为不需要去重，所以对于两个排好序的数组，直接遍历即可，遇到相同的就添加，不相同时较小的后移

示例代码

func intersect(nums1 []int, nums2 []int) []int {
   var intersection []int
   sort.Ints(nums1)
   sort.Ints(nums2)
   for i, j := 0, 0; i < len(nums1) && j < len(nums2); {
      if nums1[i] == nums2[j] {
         intersection = append(intersection, nums1[i])
         i++
         j++
      } else if nums1[i] > nums2[j] {
         j++
      } else {
         i++
      }
   }
   return intersection
}

453. 最小操作次数使数组元素相同

解题思路

先看示例

[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]  3
[1,3,5] => [2,4,5] => [3,5,5] => [4,5,6] => [5,7,5] => [6,7,6] => [7,7,7]  6
[1,2,5] => [2,3,5] => [3,4,5] => [4,5,5] => [5,6,5] => [6,6,6] 5
[1,2,3,4] => [2,3,4,4] => [3,4,5,4] => [4,5,6,4] => [5,6,6,5] => [6,6,7,6] => [7,7,7,7]  6

根据以上示例可知，假设数组是有序，每一位加上与最小位相差的数既得到最终的次数以[1,2,5]为例，第一位和第二位加4后可得[5,6,5]，排序可得[5,5,6]，重复上述步骤加1，得到[6,6,6]，共操作5次

示例代码

func minMoves(nums []int) int {
   sort.Ints(nums)
   var count int
   for i := len(nums) - 1; i > 0; i-- {
      count += nums[i] - nums[0]
   }
   return count
}

解题思路

基于排序的思路我们不难发现最终操作次数为数组中所有数组与最小值差的和，也即是数组的和减去N个最小值

示例代码

func minMoves(nums []int) int {
   count, min := 0, math.MaxInt32
   for _, num := range nums {
      count += num
      if min > num {
         min = num
      }
   }
   return count - len(nums)*min
}

解题思路

假设数组时有序的，数组长度为3，那么要是三个数相等，可以分两步做

先使前两个数相等，则需要移动次数为nums[1]-nums[0]记为moves。注意：此时第三个数以静发生了变化，增大了moves，新arr[2]=原arr[2]+moves
此时前两个数已经相等，相等的数可以看做一个数，此时则需要让后两个数相等，让num[1]等于新num[2]，则需要移动新nums[2] - nums[1] = 原nums[2] + moves - nums[1]记为diff2，最终结果为moves = moves + newmoves

当数组长度大于3时，依照上面方式递推即可

示例代码

func minMoves(nums []int) int {
   sort.Ints(nums)
   var moves int
   for i := 1; i < len(nums); i++ {
      diff := moves + nums[i]- nums[i-1]
      nums[i] += moves // 这里比较难理解,此时相加的实际上是完成上一次操作中的改变nums[2]
      moves += diff
   }
   return moves
}

455. 分发饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子i，都有一个胃口值g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干j，都有一个尺寸s[j] 。如果s[j] >= g[i]，我们可以将这个饼干j分配给孩子i，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

示例 1：

输入: g = [1,2,3], s = [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。

示例 2：

输入: g = [1,2], s = [1,2,3]
输出: 2
解释:
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.

提示：

1 <= g.length <= 3 * 104
0 <= s.length <= 3 * 104
1 <= g[i], s[j] <= 231 - 1

解题思路

直接将两个两个数组排序，然后双指针的方式向后移，当满足g[i] <= s[j]的时候，将饼干j分配给孩子i，i和j同时后移为下一个孩子分配饼干；不满足时j后移知道满足

示例代码

func findContentChildren(g []int, s []int) int {
   sort.Ints(g)
   sort.Ints(s)
   var count int
   for    i,j := 0,0; i<len(g) && j < len(s); {
      if g[i] <= s[j] { // 满足即分配
         count ++
         i++
         j++
      }else{ // 寻找符合孩子胃口的饼干
         j ++
      }
   }
   return count
}