2778. 特殊元素平方和

image-20230716144210359

根据题意计算即可

1
2
3
4
5
6
7
8
9
func sumOfSquares(nums []int) int {
    var res int
    for i, num := range nums {
        if len(nums)%(i+1) == 0 {
            res += num * num
        }
    }
    return res
}

2779. 数组的最大美丽值

image-20230716144610489

差分数组：

因为是选子序列，且子序列所有的元素都相等，所以元素顺序对答案没有影响，可以先对数组进行排序。

对于 nums[i]nums[i] 可替换为 nums[i]−knums[i]-k 到 nums[i]+knums[i]+k 内的任一整数，所以实际上是在求 nn 个 数组段 的重合范围，可以用差分数组来实现

以 nums=[4,6,1,2]，k=2nums = [4,6,1,2]， k = 2 为例：

  • nums[0]nums[0] 的取值范围为 [2,6][2,6]
  • nums[1]nums[1] 的取值范围为 [4,8][4,8]
  • nums[2]nums[2] 的取值范围为 [−1,3][-1,3]
  • nums[3]nums[3] 的取值范围为 [4,6][4,6]

转换为差分数组，就变成了在 [2,6],[4,8],[0,3],[4,6][2,6],[4,8],[0,3],[4,6] 范围内的数分别 +1+1（因为 nums[i]≥1nums[i] \geq 1，所以小于0的部分在差分数组中可以省略）

最后求出差分数组中最大的值即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func maximumBeauty(nums []int, k int) int {
    n := len(nums)
    
    sort.Ints(nums)
    d := make([]int, nums[n-1]+k+2)
    for _, num := range nums {
        d[max(0, num-k)] += 1
        d[num+k+1] -= 1
    }
    
    res := 0
    for i := max(0, nums[0]-k); i < len(d); i++ {
        res = max(res, res+d[i])
    }
    
    return res
}

滑动窗口：

差分数组在最极端的情况下会申请长度为 $10^5 \times 2 $ 的数组，会造成空间浪费。

按照上述思路，将数组排序后，因为替换的都是一个连续范围内的数，所以选出来的子序列必然是一段连续子数组。

原问题就变成了：「找出最长连续子数组，数组头结点与尾节点之差不超过 2k2k」，只要子数组满足这个要求，其中的元素就可以变成同一个数。

使用双指针解决，枚举 nums[right]nums[right] 作为子数组的最后一个数，如果 nums[right]−nums[left]>2knums[right] - nums[left] > 2k，就移动左端点。

right−left+1right - left + 1 就是子数组的长度，取所有长度最大值即是答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
func maximumBeauty2(nums []int, k int) int {
    sort.Ints(nums)
    left := 0
    res := 1 // 子数组最小长度为1
    for right := 1; right < len(nums); right++ {
        for nums[right]-nums[left] > k*2 {
            left++
        }
        res = max(res, right-left+1)
    }
    return res
}
func max(a, b int) int { if b > a { return b }; return a }

2780. 合法分割的最小下标

image-20230716151845224

image-20230716151855032

解题思路：

根据题意，切割出来的两个子数组中，支配元素相同，这里我们设支配元素为 xx，从 ii 处分割

对于第一个数组有：

freq(x)1×2>i+1freq(x)_1 \times 2 > i + 1

对于第二个数组有：

freq(x)2×n−i−1freq(x)_2 \times n-i-1

由于这两个数组合并之后是原数组，所以：

freq(x)×2=freq(x)1×2+freq(x)2×2>(i+1)+(n−i−1)=nfreq(x) \times 2 = freq(x)_1 \times 2 + freq(x)_2 \times 2 > (i+1) + (n-i-1) = n

首先求出支配元素 xx 极其出现的次数 totaltotal，然后枚举 ii ，一边枚举一边统计 freq1(x)freq_1(x)，那么 freq2(x)=total−freq1(x)freq_2(x) = total - freq_1(x)。只要满足 freq1(x)×2>i+1freq_1(x) \times 2 > i + 1 且 freq2(x)>n−i−1freq_2(x) > n - i - 1，就返回 ii，没有这样的 ii， 就返回 −1-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func minimumIndex(nums []int) int {
    freq := map[int]int{}
    x := nums[0]
    for _, num := range nums {
        freq[num]++
        if freq[num] > freq[x] {
            x = num
        }
    }
    
    total := freq[x]
    freq1 := 0
    for i, num := range nums {
        if num == x {
            freq1++
        }
        if freq1*2 > i+1 && (total-freq1)*2 > len(nums)-i-1 {
            return i
        }
    }
    return -1
}

2781. 最长合法子字符串的长度

image-20230716154251416

解题思路：

采用双指针的方式，初始化子串左端点 left=0left = 0，枚举右端点 rightright。当子串中出现不合法字段时，我们将左端点向右移动，两个指针都只能往右移动。

当 rightright 右移到一个新字母时，枚举一该字母为右端点的 forbidden[i]forbidden[i] 的最短长度（出现不合法时，leftleft 就需要右移，最短可以保证 leftleft 移动的效率），如果发现子串 word[i]word[i] 到 word[right]word[right] 在 forbiddenforbidden 中，那么更新 left=i+1left = i+1 并结束枚举，从而避免合法子串包含 forbiddenforbidden 中的字符串。枚举结束后，更新答案为合法子串长度 right−left+1right -left + 1 的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func longestValidSubstring(word string, forbidden []string) int {
    m := make(map[string]bool, len(forbidden))
    for _, s := range forbidden {
        m[s] = true
    }
    
    left := 0
    res := 0
    for right := range word {
        for i := right; i >= left && i > right-10; i-- { // forbidden中子串长度小于10
            if m[word[i:right+1]] {
                left = i + 1
                break
            }
        }
        res = max(res, right-left+1)
    }
    return res
}