1456. Maximum Number of Vowels in a Substring of Given Length
Problem
Given a string s and an integer k. Return the maximum number of vowel letters in any single substring of s with length k. The vowel letters in English are (a, e, i, o, u).
Example 1: Input: s = “abciiidef”, k = 3 Output: 3 Explanation: The substring “iii” contains 3 vowel letters.
Example 2: Input: s = “aeiou”, k = 2 Output: 2 Explanation: Any substring of length 2 contains 2 vowel letters.
Example 3: Input: s = “leetcode”, k = 3 Output: 2 Explanation: “lee”, “eet” and “ode” all contain 2 vowel letters.
Example 4: Input: s = “rhythms”, k = 4 Output: 0 Explanation: The string s does not contain any vowel letters.
Example 5: Input: s = “tryhard”, k = 4 Output: 1
Constraints: 1 <= s.length <= 10^5 s consists of lowercase English letters 1 <= k <= s.length
Approach
This is a fairly simple sliding-window problem. The window size is fixed at K, and what we need to do is determine the number of vowel letters in the window.
First, we build a variable to count the number of vowel letters in the current window, set to cnt.
As the window keeps sliding to the right, we also need a variable to store the maximum number of vowel letters among all the windows we have seen, which is the result we ultimately need; set it to ans.
Then we iterate over the string.
For the fixed-length sliding window type, we can simply summarize a pattern:
- First perform the condition check and modify the corresponding variable values
- Check whether the window needs to move; if it does, modify the corresponding values
- Check whether the window has already reached the fixed length; if it has, update the result
A simple summary, for reference only.
For our current problem:
- Create a variable to record the number of vowel letters in the current window, set to cnt
- Create a variable to record the maximum number of vowel letters among all windows seen, set to ans
- Then iterate
- First determine whether the character is a vowel letter; if it is, add 1 to the number of vowel letters in the window, cnt+1
- Then determine whether the window needs to slide; if it does, determine whether the leftmost element is a vowel letter: if it is, cnt-1; if not, no update is needed
- Finally, determine whether the current window length meets the requirement; if it does, update the maximum value
- Return the final result ans
Solution
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. Maximum Average Subarray I
Problem
Given an integer array nums consisting of n elements, and an integer k. Find a contiguous subarray whose length is equal to k that has the maximum average value, and output that maximum average. Any answer with an error less than 10-5 will be considered correct.
Example 1:
Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation: The maximum average is (12-5-6+50)/4 = 51/4 = 12.75
Example 2:
Input: nums = [5], k = 1
Output: 5.00000
Constraints:
n == nums.length
1 <= k <= n <= 10^5
-10^4 <= nums[i] <= 10^4
Approach
Build a sliding window of length k and set up a variable to compute the sum of the numbers in the window, updating the variable as the window slides.
Set up a variable to update the maximum average dynamically; note that this variable should be initialized to math.MinInt.
Solution
// 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. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold
Problem
Given an integer array arr and two integers k and threshold.
Return the number of subarrays of length k whose average is greater than or equal to threshold.
Example 1:
Input: arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
Output: 3
Explanation: The subarrays [2,5,5],[5,5,5] and [5,5,8] have averages of 4, 5 and 6 respectively. The averages of all other subarrays of length 3 are less than 4 (the value of threshold).
Example 2:
Input: arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5
Output: 6
Explanation: The first 6 subarrays of length 3 all have averages greater than 5. Note that the averages are not integers.
Constraints:
1 <= arr.length <= 10^5
1 <= arr[i] <= 10^4
1 <= k <= arr.length
0 <= threshold <= 10^4
Approach
The basic idea is to build a window of size k, compute the sum of the elements in the window, and then check whether the average is greater than or equal to the threshold.
Again, we follow our steps.
Solution
// 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 Radius Subarray Averages
Problem
You are given a 0-indexed array nums of n integers, and an integer k.
The k-radius average of a subarray means the average of all elements in a subarray of nums that is centered at index i with radius k; that is, the average of all elements whose indices lie in the range i - k to i + k (inclusive of i - k and i + k). If there are fewer than k elements before or after index i, then the k-radius average is -1.
Build and return an array avgs of length n, where avgs[i] is the k-radius average of the subarray centered at index i.
The average of x elements is the sum of the x elements divided by x, using truncated integer division, that is, the fractional part of the result needs to be removed.
For example, the average of the four elements 2, 3, 1 and 5 is (2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75, which truncates to 2.
Example 1:
Input: nums = [7,4,3,9,1,8,5,2,6], k = 3
Output: [-1,-1,-1,5,4,4,-1,-1,-1]
Explanation:
- avg[0], avg[1] and avg[2] are -1, because the number of elements before these indices is less than k.
- The sum of the elements of the subarray centered at index 3 with radius 3 is: 7 + 4 + 3 + 9 + 1 + 8 + 5 = 37. Using truncated integer division, avg[3] = 37 / 7 = 5.
- For the subarray centered at index 4, avg[4] = (4 + 3 + 9 + 1 + 8 + 5 + 2) / 7 = 4.
- For the subarray centered at index 5, avg[5] = (3 + 9 + 1 + 8 + 5 + 2 + 6) / 7 = 4.
- avg[6], avg[7] and avg[8] are -1, because the number of elements after these indices is less than k.
Example 2:
Input: nums = [100000], k = 0
Output: [100000]
Explanation:
- The sum of the elements of the subarray centered at index 0 with radius 0 is: 100000. avg[0] = 100000 / 1 = 100000.
Example 3:
Input: nums = [8], k = 100000
Output: [-1]
Explanation:
- avg[0] is -1, because the number of elements before and after index 0 is less than k.
Constraints:
n == nums.length
1 <= n <= 10^5
0 <= nums[i], k <= 10^5
Approach
This problem introduces a concept: a subarray with radius k.
At this point the actual size of the sliding window is k * 2 + 1.
After that, only the points that can serve as the center have an average; all the others are -1.
So first set up an array ans to store the answers, and then initialize all the values to -1.
After that, we still follow the approach we summarized earlier.
Solution
// 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. Minimum Recolors to Get K Consecutive Black Blocks
Problem
You are given a 0-indexed string blocks of length n, where blocks[i] is either ‘W’ or ‘B’, indicating the color of the i-th block. The characters ‘W’ and ‘B’ represent white and black respectively.
You are given an integer k, which is the desired number of consecutive black blocks.
In each operation, you can choose a white block and recolor it into a black block.
Return the minimum number of operations needed for at least one occurrence of k consecutive black blocks.
Example 1:
Input: blocks = “WBBWWBBWBW”, k = 7
Output: 3
Explanation: One way to get 7 consecutive black blocks is to recolor the 0th, 3rd and 4th blocks black.
Getting blocks = “BBBBBBBWBW”.
It can be proven that it is impossible to get 7 consecutive black blocks in fewer than 3 operations.
So we return 3.
Example 2:
Input: blocks = “WBWBBBW”, k = 2
Output: 0
Explanation:
No operation is needed, because there are already 2 consecutive black blocks.
So we return 0.
Constraints:
n == blocks.length
1 <= n <= 100
blocks[i] is either ‘W’ or ‘B’.
1 <= k <= n
Approach
What we need is K consecutive black blocks, that is, painting all the white blocks in a window of size k black.
To get this minimum number of recolors, we also want the most black blocks and the fewest white blocks.
We find the window with the most black blocks and then subtract this number from k.
Solution
// 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. Maximum Sum of Almost Unique Subarray
Problem
You are given an integer array nums and two positive integers m and k.
Return the maximum sum out of all almost unique subarrays of nums of length k. If no almost unique subarray exists, return 0.
A subarray of nums is called almost unique if it contains at least m distinct elements.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [2,6,7,3,1,7], m = 3, k = 4
Output: 18
Explanation: There are a total of 3 almost unique subarrays of length k = 4. They are [2, 6, 7, 3], [6, 7, 3, 1] and [7, 3, 1, 7]. Among these subarrays, the one with the maximum sum is [2, 6, 7, 3], with a sum of 18.
Example 2:
Input: nums = [5,9,9,2,4,5,4], m = 1, k = 3
Output: 23
Explanation: There are a total of 5 almost unique subarrays of length k = 3. They are [5, 9, 9], [9, 9, 2], [9, 2, 4], [2, 4, 5] and [4, 5, 4]. Among these subarrays, the one with the maximum sum is [5, 9, 9], with a sum of 23.
Example 3:
Input: nums = [1,2,1,2,1,2,1], m = 3, k = 3
Output: 0
Explanation: In the input array there is no subarray of length k = 3 that contains at least m = 3 distinct elements. Therefore no almost unique subarray exists, and the maximum sum is 0.
Constraints:
1 <= nums.length <= 2 * 10^4
1 <= m <= k <= nums.length
1 <= nums[i] <= 10^9
Approach
Starting with this problem, we introduce a variable and begin to control the counts of elements in the window.
The counting and control of quantities can be achieved by introducing a hash table; in Go, we can use map[type]type to represent a hash table.
map[num] can count the occurrences of num, and len(map) can control the number of distinct elements; these are also the two most common ways.
In this problem, we need to keep len(map) within m.
The rest of the logic is fixed.
Solution
// 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. Maximum Sum of Distinct Subarrays With Length K
Problem
You are given an integer array nums and an integer k. Find the maximum subarray sum of all the subarrays of nums that meet the following conditions:
The length of the subarray is k, and
All the elements of the subarray are distinct.
Return the maximum subarray sum of all the subarrays that meet the requirements of the problem. If no subarray meets these conditions, return 0.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [1,5,4,2,9,9,9], k = 3
Output: 15
Explanation: The subarrays of nums with length 3 are:
- [1,5,4], which meets all the conditions, with a sum of 10.
- [5,4,2], which meets all the conditions, with a sum of 11.
- [4,2,9], which meets all the conditions, with a sum of 15.
- [2,9,9], which does not meet all the conditions, because the element 9 is repeated.
- [9,9,9], which does not meet all the conditions, because the element 9 is repeated.
Since 15 is the maximum subarray sum among all subarrays that meet all the conditions, we return 15.
Example 2:
Input: nums = [4,4,4], k = 3
Output: 0
Explanation: The subarrays of nums with length 3 are:
- [4,4,4], which does not meet all the conditions, because the element 4 is repeated.
Since no subarray meets all the conditions, we return 0.
Constraints:
1 <= k <= nums.length <= 10^5
1 <= nums[i] <= 10^5
Approach
Use the size of the hash table to enforce the requirement that all elements are distinct, and use the sliding window to control the subarray length k.
Solution
// 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. Maximum Points You Can Obtain from Cards
Problem
Several cards are arranged in a row, and each card has a corresponding number of points. The points are given by the integer array cardPoints.
In each move, you can take one card from the beginning or the end of the row, and you must eventually take exactly k cards.
Your points are the sum of the points of all the cards you have taken.
Given an integer array cardPoints and an integer k, return the maximum points you can obtain.
Example 1:
Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: In the first move, no matter which card you take, your points are always 1. However, taking the rightmost card first will maximize the points you can obtain. The optimal strategy is to take the three cards on the right, for a final score of 1 + 6 + 5 = 12.
Example 2:
Input: cardPoints = [2,2,2], k = 2
Output: 4
Explanation: No matter which two cards you take, the points you can obtain are always 4.
Example 3:
Input: cardPoints = [9,7,7,9,7,7,9], k = 7
Output: 55
Explanation: You must take all the cards; the points you can obtain are the sum of the points of all cards.
Example 4:
Input: cardPoints = [1,1000,1], k = 1
Output: 1
Explanation: You cannot take the middle card, so the maximum points you can obtain is 1.
Example 5:
Input: cardPoints = [1,79,80,1,1,1,200,1], k = 3
Output: 202
Constraints:
1 <= cardPoints.length <= 10^5
1 <= cardPoints[i] <= 10^4
1 <= k <= cardPoints.length
Approach
This problem is likewise classified as a sliding window; it forms a sliding window from the beginning and the end.
In my approach, I first build a sliding window of length k at the beginning of the array.
Then I slide the window toward the tail until the tail has moved k positions.
Solution
// 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. Diet Plan Performance
Problem
Your friend is a fitness enthusiast. Some time ago, he made a fitness plan for himself, and now he wants you to help him evaluate whether this plan is reasonable.
He has a table of planned calorie expenditure, where calories[i] gives the total number of calories your friend needs to consume on day i.
To better evaluate this plan, for each day in the calorie table you need to compute the total calories T he consumes over “this day and the following consecutive days” (k days in total):
If T < lower, then this plan is relatively poor, and 1 point is lost;
If T > upper, then this plan is relatively good, and 1 point is gained;
Otherwise, this plan is just so-so, and the score does not change.
Return the total score obtained after counting all calories.length days as the evaluation result.
Note: the total score may be negative.
Example 1:
Input: calories = [1,2,3,4,5], k = 1, lower = 3, upper = 3
Output: 0
Explanation: calories[0], calories[1] < lower and calories[3], calories[4] > upper, total score = 0.
Example 2:
Input: calories = [3,2], k = 2, lower = 0, upper = 1
Output: 1
Explanation: calories[0] + calories[1] > upper, total score = 1.
Example 3:
Input: calories = [6,5,0,0], k = 2, lower = 1, upper = 5
Output: 0
Explanation: calories[0] + calories[1] > upper, calories[2] + calories[3] < lower, total score = 0.
Constraints:
1 <= k <= calories.length <= 10^5
0 <= calories[i] <= 20000
0 <= lower <= upper
Approach
Build a sliding window, count the calories consumed in the window, and then make the judgment.
The basic approach still follows the previous steps.
Solution
// 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. Find K-Length Substrings With No Repeated Characters
Problem
Given a string S, find all substrings of length K that do not contain repeated characters, and return the number of all substrings that meet the requirement.
Example 1:
Input: S = “havefunonleetcode”, K = 5
Output: 6
Explanation: There are 6 substrings that meet the requirement, namely: ‘havef’,‘avefu’,‘vefun’,‘efuno’,‘etcod’,‘tcode’.
Example 2:
Input: S = “home”, K = 5
Output: 0
Explanation: Note: K may be greater than the length of S. In this case, no substring of length K can be found.
Constraints:
1 <= S.length <= 10^4
All characters in S are lowercase English letters
1 <= K <= 10^4
Approach
Use a hash table to check whether characters are repeated.
Use a sliding window to build substrings of length k.
Solution
// 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. Distinct Numbers in Each Subarray
Problem
You are given an integer array nums of length n and an integer k. Your task is to find the number of distinct elements in all subarrays of nums of length k.
Return an array ans, where for each index 0 <= i < n - k, ans[i] is the number of distinct elements in nums[i..(i + k - 1)].
Example 1:
Input: nums = [1,2,3,2,2,1,3], k = 3
Output: [3,2,2,2,3]
Explanation: The number of distinct numbers in each subarray is calculated as follows:
- nums[0..2] = [1,2,3] so ans[0] = 3
- nums[1..3] = [2,3,2] so ans[1] = 2
- nums[2..4] = [3,2,2] so ans[2] = 2
- nums[3..5] = [2,2,1] so ans[3] = 2
- nums[4..6] = [2,1,3] so ans[4] = 3
Example 2:
Input: nums = [1,1,1,1,2,3,4], k = 4
Output: [1,2,3,4]
Explanation: The number of distinct numbers in each subarray is calculated as follows:
- nums[0..3] = [1,1,1,1] so ans[0] = 1
- nums[1..4] = [1,1,1,2] so ans[1] = 2
- nums[2..5] = [1,1,2,3] so ans[2] = 3
- nums[3..6] = [1,2,3,4] so ans[3] = 4
Constraints:
1 <= k <= nums.length <= 10^5
1 <= nums[i] <= 10^5
Approach
Build a sliding window whose length is fixed at k.
Use a hash table to record the kinds of numbers in the window and update it in real time.
Solution
// 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. Minimum Swaps to Group All 1’s Together
Problem
Given a binary array data, you need to group all the 1’s at any position in the array together by swapping positions, and return the minimum number of swaps required among all possibilities.
Example 1:
Input: data = [1,0,1,0,1]
Output: 1
Explanation:
There are three possible ways to group all the 1’s together:
[1,1,1,0,0], 1 swap;
[0,1,1,1,0], 2 swaps;
[0,0,1,1,1], 1 swap.
So the minimum number of swaps is 1.
Example 2:
Input: data = [0,0,0,1,0]
Output: 0
Explanation:
Since there is only one 1 in the array, no swap is needed.
Example 3:
Input: data = [1,0,1,0,1,0,0,1,1,0,1]
Output: 3
Explanation:
With 3 swaps, one feasible solution that uses only 3 swaps is [0,0,0,0,0,1,1,1,1,1,1].
Example 4:
Input: 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]
Output: 8
Constraints:
1 <= data.length <= 10^5
data[i] == 0 or 1.
Approach
The requirement of the problem is to group all the 1’s together and return the minimum number of swaps required.
We first need to know the number of 1’s in the array, and use this number as the size of the sliding window.
Now that we have the size of the sliding window, we count the maximum number of 1’s in a window; the window size minus this maximum is the minimum number of swaps we need.
Solution
// 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. Number of Unique Flavors After Sharing K Candies
Problem
You are given a 0-indexed integer array candies, where candies[i] represents the flavor of the i-th candy. Your mom wants you to share these candies with your little sister, giving her k consecutive candies, but you want to keep as many candy flavors as possible.
After sharing with your sister, return the maximum number of unique flavors of candy you can keep.
Example 1:
Input: candies = [1,2,2,3,4,3], k = 3
Output: 3
Explanation: Give the candies in the range [1,3] (inclusive) with flavors [2,2,3]. You can eat candies with flavors [1,4,3]. There are 3 unique flavors, so return 3.
Example 2:
Input: candies = [2,2,2,2,3,3], k = 2
Output: 2
Explanation: Give the candies in the range [3,4] (inclusive) with flavors [2,3]. You can eat candies with flavors [2,2,2,3]. There are 2 unique flavors, so return 2. Please note that you can also share the candies with flavors [2,2] and eat the candies with flavors [2,2,3,3].
Example 3:
Input: candies = [2,4,5], k = 0
Output: 3
Explanation: You do not have to give any candies. You can eat candies with flavors [2,4,5]. There are 3 unique flavors, so return 3.
Constraints:
0 <= candies.length <= 10^5
1 <= candies[i] <= 10^5
0 <= k <= candies.length
Approach
This problem is a bit special: it asks us to build a contiguous subarray of length k, and after deleting this subarray, the number of remaining distinct numbers should be as large as possible.
In that case, we just use a hash table to store the remaining kinds and their corresponding counts.
Again, just follow the three steps.
Solution
// 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))
}
}