【数论】【分类讨论】【C++算法】1611使整数变为 0 的最少操作次数

简介: 【数论】【分类讨论】【C++算法】1611使整数变为 0 的最少操作次数

作者推荐

【动态规划】【字符串】【行程码】1531. 压缩字符串

涉及知识点

数论 数学 分类讨论

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;

};


相关文章
|
2月前
|
存储 算法 C++
高精度算法(加、减、乘、除,使用c++实现)
高精度算法(加、减、乘、除,使用c++实现)
620 0
高精度算法(加、减、乘、除,使用c++实现)
|
2月前
|
存储 缓存 分布式计算
数据结构与算法学习一:学习前的准备,数据结构的分类,数据结构与算法的关系,实际编程中遇到的问题,几个经典算法问题
这篇文章是关于数据结构与算法的学习指南,涵盖了数据结构的分类、数据结构与算法的关系、实际编程中遇到的问题以及几个经典的算法面试题。
38 0
数据结构与算法学习一:学习前的准备,数据结构的分类,数据结构与算法的关系,实际编程中遇到的问题,几个经典算法问题
|
2月前
|
移动开发 算法 前端开发
前端常用算法全解:特征梳理、复杂度比较、分类解读与示例展示
前端常用算法全解:特征梳理、复杂度比较、分类解读与示例展示
29 0
|
2月前
|
算法 数据处理 C++
c++ STL划分算法;partition()、partition_copy()、stable_partition()、partition_point()详解
这些算法是C++ STL中处理和组织数据的强大工具,能够高效地实现复杂的数据处理逻辑。理解它们的差异和应用场景,将有助于编写更加高效和清晰的C++代码。
37 0
|
2月前
|
存储 算法 决策智能
【算法】博弈论(C/C++)
【算法】博弈论(C/C++)
|
2月前
|
存储 算法 C++
【算法】哈希映射(C/C++)
【算法】哈希映射(C/C++)
|
2月前
|
机器学习/深度学习 人工智能 算法
【算法】最长公共子序列(C/C++)
【算法】最长公共子序列(C/C++)
|
2月前
|
人工智能 算法 BI
一篇带你速通差分算法(C/C++)
一篇带你速通差分算法(C/C++)
|
2月前
|
人工智能 算法 C++
一篇带你速通前缀和算法(C/C++)
一篇带你速通前缀和算法(C/C++)
|
2月前
|
存储 算法 C++
弗洛伊德(Floyd)算法(C/C++)
弗洛伊德(Floyd)算法(C/C++)