【位运算 试填法】【推荐】3022. 给定操作次数内使剩余元素的或值最小

算法可以发掘本质，如：

一，若干师傅和徒弟互有好感，有好感的师徒可以结对学习。师傅和徒弟都只能参加一个对子。如何让对子最多。

二，有无限多1X2和2X1的骨牌，某个棋盘若干格子坏了，如何在没有坏的格子放足够多骨牌。

三，某个单色图，1表示前前景，0表示后景色。每次操作可以将一个1，变成0。如何在最少得操作情况下，使得没有两个1相邻（四连通）。

四，若干路人，有些人是熟人，如何选出最多的人参加实验。为了避免熟人影响实验的效果，参加的人不能是熟人。

一二是二分图的最大匹配，三是二分图的最小点覆盖，四是二分图最大独立集。 而这三者是等效问题。

本文涉及知识点

位运算 试填法

LeetCode 3022. 给定操作次数内使剩余元素的或值最小

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

一次操作中，你可以选择 nums 中满足 0 <= i < nums.length - 1 的一个下标 i ，并将 nums[i] 和 nums[i + 1] 替换为数字 nums[i] & nums[i + 1] ，其中 & 表示按位 AND 操作。

请你返回 至多 k 次操作以内，使 nums 中所有剩余元素按位 OR 结果的 最小值 。

示例 1：

输入：nums = [3,5,3,2,7], k = 2

输出：3

解释：执行以下操作：

1. 将 nums[0] 和 nums[1] 替换为 (nums[0] & nums[1]) ，得到 nums 为 [1,3,2,7] 。
2. 将 nums[2] 和 nums[3] 替换为 (nums[2] & nums[3]) ，得到 nums 为 [1,3,2] 。
   最终数组的按位或值为 3 。
   3 是 k 次操作以内，可以得到的剩余元素的最小按位或值。
   示例 2：
   输入：nums = [7,3,15,14,2,8], k = 4
   输出：2
   解释：执行以下操作：
3. 将 nums[0] 和 nums[1] 替换为 (nums[0] & nums[1]) ，得到 nums 为 [3,15,14,2,8] 。
4. 将 nums[0] 和 nums[1] 替换为 (nums[0] & nums[1]) ，得到 nums 为 [3,14,2,8] 。
5. 将 nums[0] 和 nums[1] 替换为 (nums[0] & nums[1]) ，得到 nums 为 [2,2,8] 。
6. 将 nums[1] 和 nums[2] 替换为 (nums[1] & nums[2]) ，得到 nums 为 [2,0] 。
   最终数组的按位或值为 2 。
   2 是 k 次操作以内，可以得到的剩余元素的最小按位或值。
   示例 3：
   输入：nums = [10,7,10,3,9,14,9,4], k = 1
   输出：15
   解释：不执行任何操作，nums 的按位或值为 15 。
   15 是 k 次操作以内，可以得到的剩余元素的最小按位或值。
   提示：
   1 <= nums.length <= 10⁵
   0 <= nums[i] < 2³⁰
   0 <= k < nums.length

试填法

假定我们能消除 iRemove，其中iRemvoe&iHas == iHas。

最终结果 iHas - iRemove。

iCanMove = ~iHas。

如果iCanMove的最高位i能消除，则 ：

iCanMove -= (1 << i )

iRemove += (1 << i )

否则：

iCanMove -= (1 << i )

假定新的最高位i1，则iTest = iRemove + (1 <<i1)

如果iTest能消除：

iCanMove -= (1 << i )

iRemove = iTest

否则：

iCanMove -= (1 << i )

直到 iCanMove为0。可以不修改iCanMove，直接枚举iCanMove。也可以不需要iCanMove，直接i=29 to 0 ，然后判断(1 << i ) & iHas 是否为真。

计算消除iTest需要的次数

第一种情况：从i1到i2消除。

第二种情况：无法消除

第三种情况：消除[i1,i2]及左侧或右侧的元素。

第一种情况可以继续细分：如果[i1,i3]可以消除，则i3-i1次消掉，[i3+!,i2]下次再消。

代码

核心代码

class Solution {
public:
  int minOrAfterOperations(vector<int>& nums, int k) {
    for (const auto& n : nums) {
      m_iHas |= n;
    }
    int iRemove = 0;
    for (int i = 29; i >= 0; i--) {
      if (m_iHas & (1 << i)) {
        if (Need(nums, iRemove + (1 << i)) <= k) {
          iRemove += (1 << i);
        }
      }
    }
    return m_iHas - iRemove;
  }
  int Need(const vector<int>& nums, int iTest) {
    int iAnd = iTest;
    int iCnt = 0;
    int iNeed = 0;
    for (int i = 0; i < nums.size(); i++)
    {
      if (nums[i] & iTest) {
        iCnt++;
        iAnd &= nums[i];
        if (0 == iAnd) {
          iNeed += iCnt - 1;
          iCnt = 0;
          iAnd = iTest;
        }
      }
      else
      {
        iNeed += iCnt - 1 + (0 != iAnd);
        iCnt = 0;
        iAnd = iTest;
      }
    }
    if ((nums.size() == iCnt) && (iAnd)) {
      return 1'000'000'000;
    }
    iNeed += iCnt - 1 + (0 != iAnd);
    return iNeed;
  }
  int m_iHas = 0;
};

测试用例

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;
  int k;
  {
    Solution sln;
    nums = { 3, 5, 3, 2, 7 }, k = 2;
    auto res = sln.minOrAfterOperations(nums, k);
    Assert(3, res);
  }
  {
    Solution sln;
    nums = { 7,3,15,14,2,8 }, k = 4;
    auto res = sln.minOrAfterOperations(nums, k);
    Assert(2, res);
  }
  {
    Solution sln;
    nums = { 10,7,10,3,9,14,9,4 }, k = 1;
    auto res = sln.minOrAfterOperations(nums, k);
    Assert(15, res);
  }
  {
    Solution sln;
    nums = { 37,6,46,32,23 }, k = 3;
    auto res = sln.minOrAfterOperations(nums, k);
    Assert(4, res);
  }
}

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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++**实现。