作者推荐
涉及知识点
数论 数学 分类讨论
LeetCoce1611. 使整数变为 0 的最少操作次数
给你一个整数 n，你需要重复执行多次下述操作将其转换为 0 ：
翻转 n 的二进制表示中最右侧位（第 0 位）。
如果第 (i-1) 位为 1 且从第 (i-2) 位到第 0 位都为 0，则翻转 n 的二进制表示中的第 i 位。
返回将 n 转换为 0 的最小操作次数。
示例 1：
输入：n = 3
输出：2
解释：3 的二进制表示为 “11”
“11” -> “01” ，执行的是第 2 种操作，因为第 0 位为 1 。
“01” -> “00” ，执行的是第 1 种操作。
示例 2：
输入：n = 6
输出：4
解释：6 的二进制表示为 “110”.
“110” -> “010” ，执行的是第 2 种操作，因为第 1 位为 1 ，第 0 到 0 位为 0 。
“010” -> “011” ，执行的是第 1 种操作。
“011” -> “001” ，执行的是第 2 种操作，因为第 0 位为 1 。
“001” -> “000” ，执行的是第 1 种操作。
提示：
0 <= n <= 109
数论
两种方式其实是一种：
如果是最低位，可以翻转。
如果有一位比它低，后边必须是1。
如果有两位比它低，后边必须是10。
如果有三位比它低，后边必须是100。
…
消除高位时，比它低的位必须是指定值。先低位后高位没有好处。所以先处理最高位。
分以下情况：
一，0,1。直接n。
二，n只有一个二进制位是1。这1后面的0转成1…0…。在将这个1消掉。
三，只有2个1，且挨着一起，消掉高位的1。
四，2个1，不挨着。低位1的前一位变成1，自身变成0。
五，2个以上1，除1的最高位和次高位，其它全为0。
翻转是可逆的，所以a到b和b到a的操作次数完全一样。
代码
核心代码
class Solution { public: int minimumOneBitOperations(int n) { return Rec(n); } int Rec(int n) { if (n <= 1) { return n; } if (m_data.count(n)) { return m_data[n]; } int iLowBit = n & (-n); int iOther = n - iLowBit; if (0 == iOther) {//只有一位是1: 0变成n/2后 ，将iLowBit消掉，变成n/2,变成0。 n1 变成n2和n2变成需要的步骤完全一样，逆运算，成立。 return m_data[n] = Rec(n / 2) + 1 + Rec(n / 2); } if (iLowBit * 2== iOther) {//只有两个1，且挨着一起，方式二消除 return m_data[n] = 1 + Rec(n - 2*iLowBit); } while (iOther & (iOther - 1)) { iLowBit = iOther & (-iOther); iOther -= iLowBit; } const int iNew = iOther + iLowBit; if (iNew == n) { return m_data[n] = 1 + Rec(iOther + iLowBit * 2) + Rec(iLowBit); } return m_data[n] = Rec(n - iNew) + Rec(iNew); } unordered_map<int, int> m_data; };
## 测试用例
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> balls; { Solution sln; vector<int> nums = {3,6,2,4,5,7}; vector<int> ans = {2,4,3,7,6,5}; vector<int> ret; for (const auto& n : nums ) { ret.emplace_back(sln.minimumOneBitOperations(n)); } Assert(ret, ans); } }
2023年2月
class Solution {
public:
int minimumOneBitOperations(int n) {
if (n < 2)
{
return n;
}
if (m_n.count(n))
{
return m_n[n];
}
int iMaxBitValue = GetMaxBitValue(n);
const int iDest = iMaxBitValue >> 1;
const int iSrc = n - iMaxBitValue;
return m_n[n] = Change2(iSrc, iDest) + 1 + minimumOneBitOperations(iDest);
}
int Change2(int iSrc, int iDest)
{
if (iSrc == iDest)
{
return 0;
}
if (1 == iDest)
{
return 1;
}
if (m_change2[iSrc].count(iDest))
{
return m_change2[iSrc][iDest];
}
if (iSrc & iDest)
{
return minimumOneBitOperations(iSrc - iDest);
}
const int iRet = 1 + Change2(iSrc, iDest >> 1) + minimumOneBitOperations(iDest >> 1);
return m_change2[iSrc][iDest] =iRet;
}
inline int GetMaxBitValue(int n )
{
int iMaxBitValue = n;
while (iMaxBitValue&(iMaxBitValue - 1))
{
iMaxBitValue = iMaxBitValue&(iMaxBitValue - 1);
}
return iMaxBitValue;
}
std::unordered_map<int, int> m_n;
std::unordered_map<int, std::unordered_map<int, int>> m_change2;
};
