闻缺陷则喜何志丹

闻缺陷则喜何志丹

算法可以发掘本质,如:
一,若干师傅和徒弟互有好感,有好感的师徒可以结对学习。师傅和徒弟都只能参加一个对子。如何让对子最多。
二,有无限多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

试填法

i H a s ∣ = i : 0 n − 1 n u m s [ i ] iHas \Large|=_{i:0}^{n-1}nums[i] iHas=i:0n1nums[i]
假定我们能消除 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需要的次数

将nums分成若干区间[i1,i2] ∀ \forall i ∈ \in [i1,i2] ,nums[i]& iTest 为真。
∀ \forall i n o t ∈ not\in not [i1,i2] nums[i]& iTest 为假。
cur = iTest cur A n d = i : i 1 i 2 n u m s [ i ] \Large And=_{i:i1}^{i2}nums[i] And=i:i1i2nums[i]
{ i 2 − i 1 次 c u r = = 0 无法消除 e l s e i f ( 0 = = i 1 ) 且 ( i 2 = = n u m s . s i z e ( ) − 1 ) i 2 + i 1 次 e l s e \begin{cases} i2-i1次 && cur==0 \\ 无法消除 && else \quad if (0==i1)且(i2==nums.size()-1) \\ i2+i1次 && else \\ \end{cases} i2i1无法消除i2+i1cur==0elseif(0==i1)(i2==nums.size()1)else
第一种情况:从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);
	}
}

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

扩展阅读

视频课程

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

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

04-23 20:22