Сложность: medium
Дан бинарный массив nums, верните максимальное количество последовательных единиц в массиве, если можно перевернуть не более одного нуля.
Пример:
Input: nums = [1,0,1,1,0]
Output: 4
Explanation:
- If we flip the first zero, nums becomes [1,1,1,1,0] and we have 4 consecutive ones.
- If we flip the second zero, nums becomes [1,0,1,1,1] and we have 3 consecutive ones.
The max number of consecutive ones is 4.
👨💻 Алгоритм:
1⃣Для каждого возможного начала последовательности в массиве nums начните считать количество нулей.
2⃣Для каждой последовательности проверяйте, сколько нулей содержится в ней. Если количество нулей не превышает одного, обновите максимальную длину последовательности единиц.
3⃣Продолжайте проверять все возможные последовательности в массиве, и верните максимальную длину последовательности единиц, удовлетворяющую условию.
😎 Решение:
class Solution {
func findMaxConsecutiveOnes(_ nums: [Int]) -> Int {
var longestSequence = 0
for left in 0..<nums.count {
var numZeroes = 0
for right in left..<nums.count {
if nums[right] == 0 {
numZeroes += 1
}
if numZeroes <= 1 {
longestSequence = max(longestSequence, right - left + 1)
}
}
}
return longestSequence
}
}Ставь 👍 и забирай 📚 Базу знаний