1456. 定長子串中母音的最大數目
題面
給你字串 s 和整數 k 。 請返回字串 s 中長度為 k 的單個子字串中可能包含的最大母音字母數。 英文中的 母音字母 為（a, e, i, o, u）。
示例 1： 輸入：s = “abciiidef”, k = 3 輸出：3 解釋：子字串 “iii” 包含 3 個母音字母。
示例 2： 輸入：s = “aeiou”, k = 2 輸出：2 解釋：任意長度為 2 的子字串都包含 2 個母音字母。
示例 3： 輸入：s = “leetcode”, k = 3 輸出：2 解釋：“lee”、“eet” 和 “ode” 都包含 2 個母音字母。
示例 4： 輸入：s = “rhythms”, k = 4 輸出：0 解釋：字串 s 中不含任何母音字母。
示例 5： 輸入：s = “tryhard”, k = 4 輸出：1
提示： 1 <= s.length <= 10^5 s 由小寫英文字母組成 1 <= k <= s.length
思路說明
本題是一個比較簡單的滑動視窗，視窗的大小固定不變是K，要做的是判斷視窗內母音字母的個數
首先我們構建一個變數用來統計當前視窗內母音字母的數量，設定為cnt
視窗只要不斷向右滑動的，還需要一個變數儲存所有經歷過的視窗中母音字母數的最大值，也就是我們最後需要的結果，設定為ans
然後我們就是對字串進行遍歷
針對定長滑動視窗的型別，我們可以簡單總結一個規律
- 先進行條件判斷，修改對應變數值
- 判斷視窗是否需要移動，如果移動修改對應值
- 判斷視窗是否已經達到了固定長度，如果達到了，進行結果更新
一個簡單的總結，僅供參考
針對我們現在的題目
- 建立一個變數記錄當前視窗內母音字母的個數，設定為cnt
- 建立一個變數記錄所有經歷過的視窗內母音字母數最大值，設定為ans
- 然後進行遍歷
- 先判斷是不是母音字母，如果是視窗內母音字母個數cnt+1
- 然後判斷視窗是否需要滑動，如果需要，判斷最左邊元素是不是母音字母，如果是cnt-1，如果不是，不需要進行更新
- 最後，判斷當前視窗長度是不是達到要求，如果是，進行最大值的更新
- 返回最終結果ans
題解
package main
import "fmt"
func judge(ch byte) bool {
if ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' {
return true
}
return false
}
func maxVowels(s string, k int) int {
ans := 0
cnt := 0
for i := 0; i < len(s); i++ {
if judge(s[i]) {
cnt++
}
if i >= k {
if judge(s[i-k]) {
cnt -= 1
}
}
if i >= k-1 {
ans = max(ans, cnt)
}
}
return ans
}
func main() {
testCases := []struct {
s string
k int
}{
{"abciiidef", 3},
{"aeiou", 2},
{"leetcode", 3},
{"rhythms", 4},
{"tryhard", 4},
}
for _, testCase := range testCases {
fmt.Println(maxVowels(testCase.s, testCase.k))
}
}
643. 子陣列最大平均數 I
題面
給你一個由 n 個元素組成的整數陣列 nums 和一個整數 k 。 請你找出平均數最大且 長度為 k 的連續子陣列，並輸出該最大平均數。 任何誤差小於 10-5 的答案都將被視為正確答案。
示例 1：
輸入：nums = [1,12,-5,-6,50,3], k = 4
輸出：12.75
解釋：最大平均數 (12-5-6+50)/4 = 51/4 = 12.75
示例 2：
輸入：nums = [5], k = 1
輸出：5.00000
提示：
n == nums.length
1 <= k <= n <= 10^5
-10^4 <= nums[i] <= 10^4
思路說明
構建長度為k的滑動視窗，設定變數計算視窗內數字的和，當視窗滑動的時候更新變數
設定變數動態更新最大平均數，注意這個變數初始化的時候設定成 math.MinInt
題解
// 643.子数组最大平均数I
package main
import (
"fmt"
"math"
)
func findMaxAverage(nums []int, k int) float64 {
ans, cnt := math.MinInt, 0
for i, num := range nums {
cnt += num
if i >= k {
cnt -= nums[i-k]
}
if i >= k-1 {
ans = max(ans, cnt)
}
}
return float64(ans) / float64(k)
}
func main() {
testCases := []struct {
nums []int
k int
}{
{[]int{1, 12, -5, -6, 50, 3}, 4},
{[]int{5}, 1},
}
for _, testCase := range testCases {
fmt.Println(findMaxAverage(testCase.nums, testCase.k))
}
}
1343. 大小為 K 且平均值大於等於閾值的子陣列數目
題面
給你一個整數陣列 arr 和兩個整數 k 和 threshold 。
請你返回長度為 k 且平均值大於等於 threshold 的子陣列數目。
示例 1：
輸入：arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
輸出：3
解釋：子陣列 [2,5,5],[5,5,5] 和 [5,5,8] 的平均值分別為 4，5 和 6 。其他長度為 3 的子陣列的平均值都小於 4 （threshold 的值)。
示例 2：
輸入：arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5
輸出：6
解釋：前 6 個長度為 3 的子陣列平均值都大於 5 。注意平均值不是整數。
提示：
1 <= arr.length <= 10^5
1 <= arr[i] <= 10^4
1 <= k <= arr.length
0 <= threshold <= 10^4
思路說明
基本思路就是構建大小為k的視窗，計算視窗內元素的和，然後計算平均值是否大於等於某個閾值
還是按照咱們的步驟來
題解
// 1343.大小为K且平均值大于等于阈值的子数组数目
package main
import "fmt"
func numOfSubarrays(arr []int, k, threshold int) int {
ans, cnt := 0, 0
for i, num := range arr {
cnt += num
if i >= k {
cnt -= arr[i-k]
}
if i >= k-1 && cnt >= k*threshold {
ans += 1
}
}
return ans
}
func main() {
testCases := []struct {
arr []int
k int
threshold int
}{
{[]int{2, 2, 2, 2, 5, 5, 5, 8}, 3, 4},
{[]int{11, 13, 17, 23, 29, 31, 7, 5, 2, 3}, 3, 5},
}
for _, testCase := range testCases {
fmt.Println(numOfSubarrays(testCase.arr, testCase.k, testCase.threshold))
}
}
2090. 半徑為 k 的子陣列平均值
題面
給你一個下標從 0 開始的陣列 nums ，陣列中有 n 個整數，另給你一個整數 k 。
半徑為 k 的子陣列平均值 是指：nums 中一個以下標 i 為 中心 且 半徑 為 k 的子陣列中所有元素的平均值，即下標在 i - k 和 i + k 範圍（含 i - k 和 i + k）內所有元素的平均值。如果在下標 i 前或後不足 k 個元素，那麼 半徑為 k 的子陣列平均值 是 -1 。
構建並返回一個長度為 n 的陣列 avgs ，其中 avgs[i] 是以下標 i 為中心的子陣列的 半徑為 k 的子陣列平均值 。
x 個元素的 平均值 是 x 個元素相加之和除以 x ，此時使用截斷式 整數除法 ，即需要去掉結果的小數部分。
例如，四個元素 2、3、1 和 5 的平均值是 (2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75，截斷後得到 2 。
示例 1：
輸入：nums = [7,4,3,9,1,8,5,2,6], k = 3
輸出：[-1,-1,-1,5,4,4,-1,-1,-1]
解釋：
- avg[0]、avg[1] 和 avg[2] 是 -1 ，因為在這幾個下標前的元素數量都不足 k 個。
- 中心為下標 3 且半徑為 3 的子陣列的元素總和是：7 + 4 + 3 + 9 + 1 + 8 + 5 = 37 。 使用截斷式 整數除法，avg[3] = 37 / 7 = 5 。
- 中心為下標 4 的子陣列，avg[4] = (4 + 3 + 9 + 1 + 8 + 5 + 2) / 7 = 4 。
- 中心為下標 5 的子陣列，avg[5] = (3 + 9 + 1 + 8 + 5 + 2 + 6) / 7 = 4 。
- avg[6]、avg[7] 和 avg[8] 是 -1 ，因為在這幾個下標後的元素數量都不足 k 個。
示例 2：
輸入：nums = [100000], k = 0
輸出：[100000]
解釋：
- 中心為下標 0 且半徑 0 的子陣列的元素總和是：100000 。 avg[0] = 100000 / 1 = 100000 。
示例 3：
輸入：nums = [8], k = 100000
輸出：[-1]
解釋：
- avg[0] 是 -1 ，因為在下標 0 前後的元素數量均不足 k 。
提示：
n == nums.length
1 <= n <= 10^5
0 <= nums[i], k <= 10^5
思路說明
本題提出了一個概念，半徑為k的字陣列
這個時候滑動視窗的實際大小是k * 2 + 1
之後能作為圓心的點才能夠有平均值，其他的都是-1
所以，先設定答案儲存的陣列 ans 然後將全部的值初始化為-1
之後還是按照我們之前總結的思路來
題解
// 2090.半径为k的子数组平均值
package main
import "fmt"
func getAverages(nums []int, k int) []int {
ans := make([]int, len(nums))
for i := range ans {
ans[i] = -1
}
cnt := 0
for i, num := range nums {
cnt += num
if i >= 2*k {
ans[i-k] = cnt / (k*2 + 1)
cnt -= nums[i-2*k]
}
}
return ans
}
func main() {
testCases := []struct {
nums []int
k int
}{
{[]int{7, 4, 3, 9, 1, 8, 5, 2, 6}, 3},
{[]int{100000}, 0},
{[]int{8}, 100000},
}
for _, testCase := range testCases {
fmt.Println(getAverages(testCase.nums, testCase.k))
}
}
2379. 得到 K 個黑塊的最少塗色次數
題面
給你一個長度為 n 下標從 0 開始的字串 blocks ，blocks[i] 要麼是 ‘W’ 要麼是 ‘B’ ，表示第 i 塊的顏色。字元 ‘W’ 和 ‘B’ 分別表示白色和黑色。
給你一個整數 k ，表示想要 連續 黑色塊的數目。
每一次操作中，你可以選擇一個白色塊將它 塗成 黑色塊。
請你返回至少出現 一次 連續 k 個黑色塊的 最少 操作次數。
示例 1：
輸入：blocks = “WBBWWBBWBW”, k = 7
輸出：3
解釋： 一種得到 7 個連續黑色塊的方法是把第 0 ，3 和 4 個塊塗成黑色。
得到 blocks = “BBBBBBBWBW” 。
可以證明無法用少於 3 次操作得到 7 個連續的黑塊。
所以我們返回 3 。
示例 2：
輸入：blocks = “WBWBBBW”, k = 2
輸出：0
解釋：
不需要任何操作，因為已經有 2 個連續的黑塊。
所以我們返回 0 。
提示：
n == blocks.length
1 <= n <= 100
blocks[i] 要麼是 ‘W’ ，要麼是 ‘B’ 。
1 <= k <= n
思路說明
我們需要的是K個連續的黑色塊，也就是把大小為k的視窗中的白色塊全部塗黑
我們要到這個最小的塗色數，也是黑色塊最多，白色塊最少
我們找到黑色塊最多的然後用k減去這個數量即可
題解
// 2379.得到K个黑块的最少涂色次数
package main
import "fmt"
func minimumRecolors(blocks string, k int) int {
ans, cnt := 0, 0
for i, block := range blocks {
if block == 'B' {
cnt += 1
}
if i >= k {
if blocks[i-k] == 'B' {
cnt -= 1
}
}
if i >= k-1 {
ans = max(ans, cnt)
}
}
return k - ans
}
func main() {
testCases := []struct {
blocks string
k int
}{
{"WBBWWBBWBW", 7},
{"WBWBBBW", 2},
}
for _, testCase := range testCases {
fmt.Println(minimumRecolors(testCase.blocks, testCase.k))
}
}
2841. 幾乎唯一子陣列的最大和
題面
給你一個整數陣列 nums 和兩個正整數 m 和 k 。
請你返回 nums 中長度為 k 的 幾乎唯一 子陣列的 最大和 ，如果不存在幾乎唯一子陣列，請你返回 0 。
如果 nums 的一個子陣列有至少 m 個互不相同的元素，我們稱它是 幾乎唯一 子陣列。
子陣列指的是一個陣列中一段連續 非空 的元素序列。
示例 1：
輸入：nums = [2,6,7,3,1,7], m = 3, k = 4
輸出：18
解釋：總共有 3 個長度為 k = 4 的幾乎唯一子陣列。分別為 [2, 6, 7, 3] ，[6, 7, 3, 1] 和 [7, 3, 1, 7] 。這些子陣列中，和最大的是 [2, 6, 7, 3] ，和為 18 。
示例 2：
輸入：nums = [5,9,9,2,4,5,4], m = 1, k = 3
輸出：23
解釋：總共有 5 個長度為 k = 3 的幾乎唯一子陣列。分別為 [5, 9, 9] ，[9, 9, 2] ，[9, 2, 4] ，[2, 4, 5] 和 [4, 5, 4] 。這些子陣列中，和最大的是 [5, 9, 9] ，和為 23 。
示例 3：
輸入：nums = [1,2,1,2,1,2,1], m = 3, k = 3
輸出：0
解釋：輸入陣列中不存在長度為 k = 3 的子陣列含有至少 m = 3 個互不相同元素的子陣列。所以不存在幾乎唯一子陣列，最大和為 0 。
提示：
1 <= nums.length <= 2 * 10^4
1 <= m <= k <= nums.length
1 <= nums[i] <= 10^9
思路說明
從這道題開始引入一個變數，開始對視窗中元素的數量進行控制
對數量的統計和控制可以透過引入雜湊表實現，在golang中，我們可以使用map[type]type 來表示雜湊表
透過map[num]可以統計num的數量，透過len(map)可以控制元素的種類，這也是最常用的兩種方式
在本題中，我們要把len(map)控制在m以內
然後其他的邏輯都是固定的
題解
// 2841.几乎唯一子数组的最大和
package main
import "fmt"
func maxSum(nums []int, m, k int) int64 {
mp := make(map[int]int)
var ans, cnt int64
for i, num := range nums {
cnt += int64(num)
mp[num] += 1
if i >= k {
cnt -= int64(nums[i-k])
mp[nums[i-k]] -= 1
if mp[nums[i-k]] == 0 {
delete(mp, nums[i-k])
}
}
if i >= k-1 && len(mp) >= m {
ans = max(ans, cnt)
}
}
return ans
}
func main() {
testCases := []struct {
nums []int
m int
k int
}{
{[]int{2, 6, 7, 3, 1, 7}, 3, 4},
{[]int{5, 9, 9, 2, 4, 5, 4}, 1, 3},
{[]int{1, 2, 1, 2, 1, 2, 1}, 3, 3},
}
for _, testCase := range testCases {
fmt.Println(maxSum(testCase.nums, testCase.m, testCase.k))
}
}
2461. 長度為 K 子陣列中的最大和
題面
給你一個整數陣列 nums 和一個整數 k 。請你從 nums 中滿足下述條件的全部子陣列中找出最大子陣列和：
子陣列的長度是 k，且
子陣列中的所有元素 各不相同 。
返回滿足題面要求的最大子陣列和。如果不存在子陣列滿足這些條件，返回 0 。
子陣列 是陣列中一段連續非空的元素序列。
示例 1：
輸入：nums = [1,5,4,2,9,9,9], k = 3
輸出：15
解釋：nums 中長度為 3 的子陣列是：
- [1,5,4] 滿足全部條件，和為 10 。
- [5,4,2] 滿足全部條件，和為 11 。
- [4,2,9] 滿足全部條件，和為 15 。
- [2,9,9] 不滿足全部條件，因為元素 9 出現重複。
- [9,9,9] 不滿足全部條件，因為元素 9 出現重複。
因為 15 是滿足全部條件的所有子陣列中的最大子陣列和，所以返回 15 。
示例 2：
輸入：nums = [4,4,4], k = 3
輸出：0
解釋：nums 中長度為 3 的子陣列是：
- [4,4,4] 不滿足全部條件，因為元素 4 出現重複。
因為不存在滿足全部條件的子陣列，所以返回 0 。
提示：
1 <= k <= nums.length <= 10^5
1 <= nums[i] <= 10^5
思路說明
透過雜湊表大小控制所有元素各不相同的要求，透過滑動視窗控制字陣列的長度k
題解
// 2461.长度为K子数组中的最大和
package main
import "fmt"
func maximumSubarraySum(nums []int, k int) int64 {
mp := make(map[int]int)
var ans, cnt int64
for i, num := range nums {
cnt += int64(num)
mp[num] += 1
if i >= k {
cnt -= int64(nums[i-k])
mp[nums[i-k]] -= 1
if mp[nums[i-k]] == 0 {
delete(mp, nums[i-k])
}
}
if i >= k-1 && len(mp) == k {
ans = max(ans, cnt)
}
}
return ans
}
func main() {
testCases := []struct {
nums []int
k int
}{
{[]int{1, 5, 4, 2, 9, 9, 9}, 3},
{[]int{4, 4, 4}, 3},
}
for _, testCase := range testCases {
fmt.Println(maximumSubarraySum(testCase.nums, testCase.k))
}
}
1423. 可獲得的最大點數
題面
幾張卡牌 排成一行，每張卡牌都有一個對應的點數。點數由整數陣列 cardPoints 給出。
每次行動，你可以從行的開頭或者末尾拿一張卡牌，最終你必須正好拿 k 張卡牌。
你的點數就是你拿到手中的所有卡牌的點數之和。
給你一個整數陣列 cardPoints 和整數 k，請你返回可以獲得的最大點數。
示例 1：
輸入：cardPoints = [1,2,3,4,5,6,1], k = 3
輸出：12
解釋：第一次行動，不管拿哪張牌，你的點數總是 1 。但是，先拿最右邊的卡牌將會最大化你的可獲得點數。最優策略是拿右邊的三張牌，最終點數為 1 + 6 + 5 = 12 。
示例 2：
輸入：cardPoints = [2,2,2], k = 2
輸出：4
解釋：無論你拿起哪兩張卡牌，可獲得的點數總是 4 。
示例 3：
輸入：cardPoints = [9,7,7,9,7,7,9], k = 7
輸出：55
解釋：你必須拿起所有卡牌，可以獲得的點數為所有卡牌的點數之和。
示例 4：
輸入：cardPoints = [1,1000,1], k = 1
輸出：1
解釋：你無法拿到中間那張卡牌，所以可以獲得的最大點數為 1 。
示例 5：
輸入：cardPoints = [1,79,80,1,1,1,200,1], k = 3
輸出：202
提示：
1 <= cardPoints.length <= 10^5
1 <= cardPoints[i] <= 10^4
1 <= k <= cardPoints.length
思路說明
這道題同樣歸類於滑動視窗，它是首尾構成一個滑動視窗
我的做法現在陣列首部構建一個長度為k的滑動視窗
然後移動視窗開始尾部移動，直到尾部移動k
題解
// 1423.可获得的最大点数
package main
import "fmt"
func maxScore(cardPoints []int, k int) int {
left := k - 1
ans, cnt := 0, 0
for i := 0; i < k; i++ {
cnt += cardPoints[i]
}
ans = cnt
for i := len(cardPoints) - 1; i >= len(cardPoints)-k; i-- {
cnt -= cardPoints[left]
left -= 1
cnt += cardPoints[i]
ans = max(ans, cnt)
}
return ans
}
func main() {
testCases := []struct {
nums []int
k int
}{
{[]int{1, 2, 3, 4, 5, 6, 1}, 3},
{[]int{2, 2, 2}, 2},
{[]int{9, 7, 7, 9, 7, 7, 9}, 7},
{[]int{1, 1000, 1}, 1},
{[]int{1, 79, 80, 1, 1, 1, 200, 1}, 3},
}
for _, testCase := range testCases {
fmt.Println(maxSore(testCase.nums, testCase.k))
}
}
1176. 健身計劃評估
題面
你的好友是一位健身愛好者。前段日子，他給自己制定了一份健身計劃。現在想請你幫他評估一下這份計劃是否合理。
他會有一份計劃消耗的卡路里表，其中 calories[i] 給出了你的這位好友在第 i 天需要消耗的卡路里總量。
為了更好地評估這份計劃，對於卡路里表中的每一天，你都需要計算他 「這一天以及之後的連續幾天」 （共 k 天）內消耗的總卡路里 T：
如果 T < lower，那麼這份計劃相對糟糕，並失去 1 分；
如果 T > upper，那麼這份計劃相對優秀，並獲得 1 分；
否則，這份計劃普普通通，分值不做變動。
請返回統計完所有 calories.length 天后得到的總分作為評估結果。
注意：總分可能是負數。
示例 1：
輸入：calories = [1,2,3,4,5], k = 1, lower = 3, upper = 3
輸出：0
解釋：calories[0], calories[1] < lower 而 calories[3], calories[4] > upper, 總分 = 0.
示例 2：
輸入：calories = [3,2], k = 2, lower = 0, upper = 1
輸出：1
解釋：calories[0] + calories[1] > upper, 總分 = 1.
示例 3：
輸入：calories = [6,5,0,0], k = 2, lower = 1, upper = 5
輸出：0
解釋：calories[0] + calories[1] > upper, calories[2] + calories[3] < lower, 總分 = 0.
提示：
1 <= k <= calories.length <= 10^5
0 <= calories[i] <= 20000
0 <= lower <= upper
思路說明
構建滑動視窗，統計視窗中消耗的卡路里，然後判斷
基本思路還是按照之前的步驟
題解
// 1176.健身计划评估
package main
import "fmt"
func dietPlanPerformance(calories []int, k, lower, upper int) int {
ans, cnt := 0, 0
for i, calorie := range calories {
cnt += calorie
if i >= k {
cnt -= calories[i-k]
}
if i >= k-1 {
if cnt > upper {
ans += 1
}
if cnt < lower {
ans -= 1
}
}
}
return ans
}
func main() {
testCases := []struct {
calories []int
k int
lower int
upper int
}{
{[]int{1, 2, 3, 4, 5}, 1, 3, 3},
{[]int{3, 2}, 2, 0, 1},
{[]int{6, 5, 0, 0}, 2, 1, 5},
}
for _, testCase := range testCases {
fmt.Println(dietPlanPerformance(testCase.calories, testCase.k, testCase.lower, testCase.upper))
}
}
1100. 長度為 K 的無重複字元子串
題面
給你一個字串 S，找出所有長度為 K 且不含重複字元的子串，請你返回全部滿足要求的子串的 數目。
示例 1：
輸入：S = “havefunonleetcode”, K = 5
輸出：6
解釋： 這裡有 6 個滿足題意的子串，分別是：‘havef’,‘avefu’,‘vefun’,‘efuno’,‘etcod’,‘tcode’。
示例 2：
輸入：S = “home”, K = 5
輸出：0
解釋： 注意：K 可能會大於 S 的長度。在這種情況下，就無法找到任何長度為 K 的子串。
提示：
1 <= S.length <= 10^4
S 中的所有字元均為小寫英文字母
1 <= K <= 10^4
思路說明
使用雜湊表控制字串是否重複
使用滑動視窗構建長度為k的子串
題解
// 1100.长度为K的无重复字符子串
package main
import "fmt"
func numKLenSubstrNoRepeats(s string, k int) int {
mp := make(map[byte]int)
ans := 0
for i := 0; i < len(s); i++ {
mp[s[i]] += 1
if i >= k {
mp[s[i-k]] -= 1
if mp[s[i-k]] == 0 {
delete(mp, s[i-k])
}
}
if i >= k-1 && len(mp) == k {
ans += 1
}
}
return ans
}
func main() {
testCases := []struct {
s string
k int
}{
{"havefunonleetcode", 5},
{"home", 5},
}
for _, testCase := range testCases {
fmt.Println(numKLenSubstrNoRepeats(testCase.s, testCase.k))
}
}
1852. 每個子陣列的數字種類數
題面
給你一個長度為 n 的整數陣列 nums 與一個整數 k。你的任務是找到 nums 所有 長度為 k 的子陣列中 不同 元素的數量。
返回一個陣列 ans，其中 ans[i] 是對於每個索引 0 <= i < n - k，nums[i..(i + k - 1)] 中不同元素的數量。
示例 1:
輸入: nums = [1,2,3,2,2,1,3], k = 3
輸出: [3,2,2,2,3]
解釋：每個子陣列的數字種類計算方法如下：
- nums[0..2] = [1,2,3] 所以 ans[0] = 3
- nums[1..3] = [2,3,2] 所以 ans[1] = 2
- nums[2..4] = [3,2,2] 所以 ans[2] = 2
- nums[3..5] = [2,2,1] 所以 ans[3] = 2
- nums[4..6] = [2,1,3] 所以 ans[4] = 3
示例 2:
輸入: nums = [1,1,1,1,2,3,4], k = 4
輸出: [1,2,3,4]
解釋: 每個子陣列的數字種類計算方法如下：
- nums[0..3] = [1,1,1,1] 所以 ans[0] = 1
- nums[1..4] = [1,1,1,2] 所以 ans[1] = 2
- nums[2..5] = [1,1,2,3] 所以 ans[2] = 3
- nums[3..6] = [1,2,3,4] 所以 ans[3] = 4
提示:
1 <= k <= nums.length <= 10^5
1 <= nums[i] <= 10^5
思路說明
構建滑動視窗，長度固定為k
使用雜湊表記錄一下視窗內數字的種類，並實時更新
題解
// 1852.每个子数组的数字种类数
package main
import "fmt"
func distinctNumbers(nums []int, k int) []int {
mp := make(map[int]int)
ans := make([]int, len(nums)-k+1)
for i, num := range nums {
mp[num] += 1
if i >= k {
mp[nums[i-k]] -= 1
if mp[nums[i-k]] == 0 {
delete(mp, nums[i-k])
}
}
if i >= k-1 {
ans[i-k+1] = len(mp)
}
}
return ans
}
func main() {
testCases := []struct {
nums []int
k int
}{
{[]int{1, 2, 3, 2, 2, 1, 3}, 3},
{[]int{1, 1, 1, 1, 2, 3, 4}, 4},
}
for _, testCase := range testCases {
fmt.Println(distinctNumbers(testCase.nums, testCase.k))
}
}
1151. 最少交換次數來組合所有的 1
題面
給出一個二進位制陣列 data，你需要透過交換位置，將陣列中 任何位置 上的 1 組合到一起，並返回所有可能中所需 最少的交換次數。
示例 1:
輸入: data = [1,0,1,0,1]
輸出: 1
解釋:
有三種可能的方法可以把所有的 1 組合在一起：
[1,1,1,0,0]，交換 1 次；
[0,1,1,1,0]，交換 2 次；
[0,0,1,1,1]，交換 1 次。
所以最少的交換次數為 1。
示例 2:
輸入：data = [0,0,0,1,0]
輸出：0
解釋：
由於陣列中只有一個 1，所以不需要交換。
示例 3:
輸入：data = [1,0,1,0,1,0,0,1,1,0,1]
輸出：3
解釋：
交換 3 次，一種可行的只用 3 次交換的解決方案是 [0,0,0,0,0,1,1,1,1,1,1]。
示例 4:
輸入: data = [1,0,1,0,1,0,1,1,1,0,1,0,0,1,1,1,0,0,1,1,1,0,1,0,1,1,0,0,0,1,1,1,1,0,0,1]
輸出: 8
提示:
1 <= data.length <= 10^5
data[i] == 0 or 1.
思路說明
題目的要求是把所有的1都組合在一起，並返回所需要的最少交換次數
我們首先需要知道陣列中1的個數，將這個數量作為滑動視窗的大小
我們已經得到滑動視窗的大小，然後統計視窗中最大的1的數量，用視窗大小減去這個最大值，就是我們需要的最少交換次數
題解
// 1151.最少交换次数来组合所有的1
package main
import "fmt"
func minSwaps(data []int) int {
k := 0 // 滑动窗口的大小
for _, val := range data {
k += val
}
ans, cnt := 0, 0
for i, val := range data {
cnt += val
if i >= k {
cnt -= data[i-k]
}
if i >= k-1 {
ans = max(ans, cnt)
}
}
return k - ans
}
func main() {
testCases := [][]int{
[]int{1, 0, 1, 0, 1},
[]int{0, 0, 0, 1, 0},
[]int{1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1},
[]int{1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1},
}
for _, testCase := range testCases {
fmt.Println(minSwaps(testCase))
}
}
2107. 分享 K 個糖果後獨特口味的數量
題面
您將獲得一個 從0開始的 整數陣列 candies ，其中 candies[i] 表示第 i 個糖果的味道。你媽媽想讓你和你妹妹分享這些糖果，給她 k 個 連續 的糖果，但你想保留儘可能多的糖果口味。
在與妹妹分享後，返回 最多 可保留的 獨特 口味的糖果。
示例 1：
輸入: candies = [1,2,2,3,4,3], k = 3
輸出: 3
解釋: 將[1,3]（含[2,2,3]）範圍內的糖果加入[2,2,3]口味。 你可以吃各種口味的糖果[1,4,3]。 有3種獨特的口味，所以返回3。
示例 2:
輸入: candies = [2,2,2,2,3,3], k = 2
輸出: 2
解釋: 在[3,4]範圍內（含[2,3]）的糖果中加入[2,3]口味。 你可以吃各種口味的糖果[2,2,2,3]。 有兩種獨特的口味，所以返回2。 請注意，你也可以分享口味為[2,2]的糖果，吃口味為[2,2,3,3]的糖果。
示例 3:
輸入: candies = [2,4,5], k = 0
輸出: 3
解釋: 你不必給任何糖果。 你可以吃各種口味的糖果[2,4,5]。 有3種獨特的口味，所以返回3。
提示:
0 <= candies.length <= 10^5
1 <= candies[i] <= 10^5
0 <= k <= candies.length
思路說明
這個題目比較特殊，是要構建一個連續陣列，陣列長度為k，刪除這個陣列後剩餘的數字種類儘量多
這樣就使用雜湊表儲存剩餘種類和對應數量即可
還是按照三步進行即可
題解
// 2107.分享K个糖果后独特口味的数量
package main
import "fmt"
func shareCandies(candies []int, k int) int {
mp := make(map[int]int)
ans := 0
for _, candie := range candies {
mp[candie] += 1
}
for i, candie := range candies {
mp[candie] -= 1
if mp[candie] == 0 {
delete(mp, candie)
}
if i >= k {
mp[candies[i-k]] += 1
}
if i >= k-1 {
ans = max(ans, len(mp))
}
}
return ans
}
func main() {
testCases := []struct {
candies []int
k int
}{
{[]int{1, 2, 2, 3, 4, 3}, 3},
{[]int{2, 2, 2, 2, 3, 3}, 2},
{[]int{2, 4, 5}, 0},
}
for _, testCase := range testCases {
fmt.Println(shareCandies(testCase.candies, testCase.k))
}
}