【滑动窗口】【差分数组】C++算法:K 连续位的最小翻转次数

简介: 【滑动窗口】【差分数组】C++算法:K 连续位的最小翻转次数

差分数组

LeetCode995: K 连续位的最小翻转次数

给定一个二进制数组 nums 和一个整数 k 。

k位翻转 就是从 nums 中选择一个长度为 k 的 子数组 ,同时把子数组中的每一个 0 都改成 1 ,把子数组中的每一个 1 都改成 0 。

返回数组中不存在 0 所需的最小 k位翻转 次数。如果不可能,则返回 -1 。

子数组 是数组的 连续 部分。

示例 1:

输入:nums = [0,1,0], K = 1

输出:2

解释:先翻转 A[0],然后翻转 A[2]。

示例 2:

输入:nums = [1,1,0], K = 2

输出:-1

解释:无论我们怎样翻转大小为 2 的子数组,我们都不能使数组变为 [1,1,1]。

示例 3:

输入:nums = [0,0,0,1,0,1,1,0], K = 3

输出:3

解释:

翻转 A[0],A[1],A[2]: A变成 [1,1,1,1,0,1,1,0]

翻转 A[4],A[5],A[6]: A变成 [1,1,1,1,1,0,0,0]

翻转 A[5],A[6],A[7]: A变成 [1,1,1,1,1,1,1,1]

参数范围

1 <= nums.length <= 105

1 <= k <= nums.length

滑动窗口+差分数组

时间复杂度 O(n)。

如果nums中不存在0,则直接返回0。

令nums[i1]等于0,如果有多个符合的i1,取最小值。设某次翻转[i,i+k),则i的最小值一定为i1。且一定只翻转一次。

翻转奇数次和翻转一次的效果完全一样,所以不需要翻转1以外的奇数次。

翻转偶数次,和没翻转效果一样。所以没必要翻转偶数次。

i < i1 翻转一次后nums[i]变成0,不符合题意
i>i1 nums[i1]为0,不符合题意

翻转i1后,类似原理处理nums[i1+1…],直到处理完毕。

差分数组

翻转[i,i+len)不需要修改nums[i,i+k)的值,那样的时间复杂度是O(k)。修改vDiff[i]++,vDiff[i+len]-- 就可以了。

i的翻转次数就是vDiff[0,i]之和。差分数组单个修改的时间复杂为O(1)。

只能翻转k次,不能翻转k-1次

即i+len <= n 。最后的k-1个元素无法翻转。

代码

核心代码

class Solution {
public:
  int minKBitFlips(vector<int>& nums, int k) {
    m_c = nums.size();
    vector<int> vDiff(m_c+1);
    int iRet = 0;
    int iDiff = 0;
    int i = 0;
    for (; i+k-1 < m_c; i++)
    {
      iDiff += vDiff[i];
      int n = (nums[i] + iDiff) % 2;
      if (0 == n)
      {
        iRet++;
        iDiff++;
        vDiff[i + k]--;
      }
    }
    for (; i  < m_c; i++)
    {
      iDiff += vDiff[i];
      int n = (nums[i] + iDiff) % 2;
      if (0 == n)
      {
        return -1;
      }
    }
    return iRet;
  }
  int m_c;
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{
  vector<int> nums = { 1, 2, 1, 2, 3 };
  int k = 2;
  {
    Solution sln;
    nums = { 0,1,0 }, k = 1;
    auto res = sln.minKBitFlips(nums, k);
    Assert(2, res);
  }
  {
    Solution sln;
    nums = { 1,1,0 }, k = 2;
    auto res = sln.minKBitFlips(nums, k);
    Assert(-1, res);
  }
  {
    Solution sln;
    nums = { 0,0,0,1,0,1,1,0 }, k = 3;
    auto res = sln.minKBitFlips(nums, k);
    Assert(3, res);
  }
}

2023年3月版

class Solution {
public:
int minKBitFlips(vector& nums, int k) {
m_c = nums.size();
//差分数组
vector v(m_c);
int iVTotal = 0;
int iRet = 0;
for (int i = 0; i < m_c; i++)
{
iVTotal += v[i];
const int iCur = (nums[i] + iVTotal)%2 ;
if (0 == iCur)
{
if (i + k > m_c)
{
return -1;
}
v[i]++;
if (i + k != m_c)
{
v[i + k]–;
}
iVTotal++;
iRet++;
}
}
return iRet;
}
int m_c;
};

2023年7月版

class Solution {
public:
int minKBitFlips(vector& nums, int k) {
m_c = nums.size();
vector vDiff(m_c + 1);
int iRotaNum = 0;
int iRota = 0;
for (int i = 0; i < m_c; i++)
{
iRota += vDiff[i];
const int iCur = (0 == iRota % 2) ? nums[i] : (1 - nums[i]);
if (1 == iCur )
{
continue;
}
const int iEnd = i + k;
if (iEnd > m_c)
{
return -1;
}
iRotaNum++;
iRota++;
vDiff[i]++;
vDiff[iEnd]++;
}
return iRotaNum;
}
int m_c;
};


扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统:win7 开发环境: VS2019 C++17

或者 操作系统:win10 开发环境: VS2022 C++17

如无特殊说明,本算法C++ 实现。

相关文章
|
13天前
|
机器学习/深度学习 安全 算法
【图论】【割点】【C++算法】928. 尽量减少恶意软件的传播 II
【图论】【割点】【C++算法】928. 尽量减少恶意软件的传播 II
|
28天前
|
存储 算法 Serverless
【C/C++ 数据结构】深入探索数据结构中算法复杂度:从C++和数学的视角
【C/C++ 数据结构】深入探索数据结构中算法复杂度:从C++和数学的视角
46 0
|
28天前
|
存储 算法 数据管理
【C/C++ 基础算法】 C/C++ 位图算法的使用
【C/C++ 基础算法】 C/C++ 位图算法的使用
35 0
|
29天前
|
存储 算法 编译器
【C++ 字符数组的模板特化】面向字符串的C++模板特化:理解与实践
【C++ 字符数组的模板特化】面向字符串的C++模板特化:理解与实践
47 1
|
28天前
|
缓存 算法 C语言
【C++ 标准查找算法 】C++标准库查找算法深入解析(In-depth Analysis of C++ Standard Library Search Algorithms)
【C++ 标准查找算法 】C++标准库查找算法深入解析(In-depth Analysis of C++ Standard Library Search Algorithms)
46 0
|
11天前
|
算法
算法系列--两个数组的dp问题(2)(下)
算法系列--两个数组的dp问题(2)(下)
17 0
|
11天前
|
存储 算法
算法系列--动态规划--⼦数组、⼦串系列(数组中连续的⼀段)(1)(下)
算法系列--动态规划--⼦数组、⼦串系列(数组中连续的⼀段)(1)
15 0
|
11天前
|
算法
算法系列--动态规划--⼦数组、⼦串系列(数组中连续的⼀段)(1)(上)
算法系列--动态规划--⼦数组、⼦串系列(数组中连续的⼀段)(1)
21 0
|
11天前
|
算法 计算机视觉
算法系列--两个数组的dp问题(1)(下)
算法系列--两个数组的dp问题(1)
18 0
|
11天前
|
算法
算法系列--两个数组的dp问题(1)(上)
算法系列--两个数组的dp问题(1)
14 0

热门文章

最新文章