【数论】【分类讨论】【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;

};


相关文章
|
21天前
|
机器学习/深度学习 算法 数据可视化
利用SVM(支持向量机)分类算法对鸢尾花数据集进行分类
本文介绍了如何使用支持向量机(SVM)算法对鸢尾花数据集进行分类。作者通过Python的sklearn库加载数据,并利用pandas、matplotlib等工具进行数据分析和可视化。
138 70
|
1月前
|
负载均衡 算法 安全
探秘:基于 C++ 的局域网电脑控制软件自适应指令分发算法
在现代企业信息化架构中,局域网电脑控制软件如同“指挥官”,通过自适应指令分发算法动态调整指令发送节奏与数据量,确保不同性能的终端设备高效运行。基于C++语言,利用套接字实现稳定连接和线程同步管理,结合实时状态反馈,优化指令分发策略,提升整体管控效率,保障网络稳定,助力数字化办公。
52 19
|
1月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
51 2
|
1月前
|
存储 算法 安全
基于哈希表的文件共享平台 C++ 算法实现与分析
在数字化时代,文件共享平台不可或缺。本文探讨哈希表在文件共享中的应用,包括原理、优势及C++实现。哈希表通过键值对快速访问文件元数据(如文件名、大小、位置等),查找时间复杂度为O(1),显著提升查找速度和用户体验。代码示例展示了文件上传和搜索功能,实际应用中需解决哈希冲突、动态扩容和线程安全等问题,以优化性能。
|
2月前
|
存储 算法 安全
基于红黑树的局域网上网行为控制C++ 算法解析
在当今网络环境中,局域网上网行为控制对企业和学校至关重要。本文探讨了一种基于红黑树数据结构的高效算法,用于管理用户的上网行为,如IP地址、上网时长、访问网站类别和流量使用情况。通过红黑树的自平衡特性,确保了高效的查找、插入和删除操作。文中提供了C++代码示例,展示了如何实现该算法,并强调其在网络管理中的应用价值。
|
2月前
|
算法 安全 C++
用 C++ 算法控制员工上网的软件,关键逻辑是啥?来深度解读下
在企业信息化管理中,控制员工上网的软件成为保障网络秩序与提升办公效率的关键工具。该软件基于C++语言,融合红黑树、令牌桶和滑动窗口等算法,实现网址精准过滤、流量均衡分配及异常连接监测。通过高效的数据结构与算法设计,确保企业网络资源优化配置与安全防护升级,同时尊重员工权益,助力企业数字化发展。
65 4
|
4月前
|
移动开发 算法 前端开发
前端常用算法全解:特征梳理、复杂度比较、分类解读与示例展示
前端常用算法全解:特征梳理、复杂度比较、分类解读与示例展示
58 0
|
4月前
|
算法 数据处理 C++
c++ STL划分算法;partition()、partition_copy()、stable_partition()、partition_point()详解
这些算法是C++ STL中处理和组织数据的强大工具,能够高效地实现复杂的数据处理逻辑。理解它们的差异和应用场景,将有助于编写更加高效和清晰的C++代码。
90 0
|
4月前
|
存储 算法 C++
高精度算法(加、减、乘、除,使用c++实现)
高精度算法(加、减、乘、除,使用c++实现)
1151 0
高精度算法(加、减、乘、除,使用c++实现)
|
4月前
|
存储 缓存 分布式计算
数据结构与算法学习一:学习前的准备,数据结构的分类,数据结构与算法的关系,实际编程中遇到的问题,几个经典算法问题
这篇文章是关于数据结构与算法的学习指南,涵盖了数据结构的分类、数据结构与算法的关系、实际编程中遇到的问题以及几个经典的算法面试题。
57 0
数据结构与算法学习一:学习前的准备,数据结构的分类,数据结构与算法的关系,实际编程中遇到的问题,几个经典算法问题