本文涉及知识点

C++贪心

位运算、状态压缩、枚举子集汇总

LeetCode2571. 将整数减少到零需要的最少操作数

给你一个正整数 n ，你可以执行下述操作 任意 次：
n 加上或减去 2 的某个 幂返回使 n 等于 0 需要执行的 最少 操作数。
如果 x == 2i 且其中 i >= 0 ，则数字 x 是 2 的幂。
示例 1：
输入：n = 39
输出：3
解释：我们可以执行下述操作：

• n 加上 20 = 1 ，得到 n = 40 。
• n 减去 23 = 8 ，得到 n = 32 。
• n 减去 25 = 32 ，得到 n = 0 。
  可以证明使 n 等于 0 需要执行的最少操作数是 3 。
  示例 2：
  输入：n = 54
  输出：3
  解释：我们可以执行下述操作：
• n 加上 21 = 2 ，得到 n = 56 。
• n 加上 23 = 8 ，得到 n = 64 。
• n 减去 26 = 64 ，得到 n = 0 。
  使 n 等于 0 需要执行的最少操作数是 3 。
  1 <= n <= 10⁵

错误想法：贪心：反证法+数学归纳法

性质一：$\forall$i,2ⁱ 只会有以下三种情况：
一，没加也没减。
二，加一次。
三，减一次。
下面分情况证明：
一，加一次减一次，劣于不加不减。
二，加两次，劣于加2^j+1。
三，减两次，劣于减2^j+1。
性质二：最低位1的必定是情况二或情况三,令为i1位。情况一，无论如何操作，最终和的绝对值一定大于等于2ⁱ¹。情况二或三，直接消除或转为高位问题，都可能解决。若干个2^j加减,j>i1，其和一定是2ⁱ¹⁺¹的整数倍，不仿令其为x倍。则2ⁱ¹+2xⁱ¹=0，不存在整数解。等式两边同时除以2ⁱ¹，变成1+2x=0。x=0.5，非整数解。
性质三：如果j1+1位也是1，则+2ⁱ¹一起消除不劣于减2ⁱ¹。连续m个1，令最低位为j1，则可以2次消除：+2^j1-2^j1+m。
性质三：如果j1+1位不是1，则减2ⁱ¹不劣于+2ⁱ¹。减一定1次。加除非前面的连续1有2个或更多且只隔一个0，否则需要两次。
不断处理最低位直到n为0。如果i1和i1+1都为1 ，则+，否则-。
时间复杂度：O(logn)

数学方法

3 * n ^ n中1的数量，证明方法过于复杂。不建议学习。孤立的知识点是记不住的。

代码

核心代码

class Solution {
		public:
			int minOperations(int n) {
				int ans = 1;
				while (n & (n - 1)) {
					int low = n & (-n);
					if ((low << 1) & n) {
						n += low;
					}
					else {
						n -= low;
					}
					ans++;
				}
				return ans;
			}
		};

单元测试

int n;
		TEST_METHOD(TestMethod11)
		{
			n = 39;
			auto res = Solution().minOperations(n);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod12)
		{
			n = 54;
			auto res = Solution().minOperations(n);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod13)
		{
			n = 27;
			auto res = Solution().minOperations(n);
			AssertEx(3, res);
		}