力扣1073. 负二进制数相加 C++

article/2024/7/13 10:45:12

思路

正常如果看二进制不太好看出来规律,得拆开看
如 [1,1,1,1,1]+[1,0,1]列竖式也看不出来啥
列成这样

(-2)^4+(-2)^3+(-2)^2+(-2)^1+(-2)^0(-2)^2+       (-2)^0

可以看出来两个(-2)2和(-2)0 两个可以变成2^3和2,就可以和前面一位的1抵消,同时这一位也变成0
就变成 (-2)^4,就可以得到结果[1,0,0,0,0]
当然如果相同的位为奇数位(当最后一位为偶数位),也同理。

现在就剩两种情况,但是奇偶规律相同,所以就剩一种情况:
如[1,1,0,1,1]+[1,0,1,0]

(-2)^4+(-2)^3+0*(-2)^2+(-2)^1+(-2)^0(-2)^3+0*(-2)^2+(-2)^1+0*(-2)^0

按照之前的情况规律来,应该位进位的前一位减1,但是前一位为0所以减不了,这个时候就想到了学减法的时候的借位
就向0之前借一位,但这个时候不能在借位那位减1,因为符号是相反的,所以应该加1,
这个时候写出来是这样

(-2)^4+(-2)^3+(-2)^3+2*(-2)^2+(-2)^1+(-2)^0(-2)^3+       0*(-2)^2+(-2)^1+0*(-2)^0(-2)^4+2*(-2)^3+2*(-2)^2+(-2)^1+(-2)^0(-2)^3+0*(-2)^2+(-2)^1+0*(-2)^0

再使用最开始的规律就可以得出结果。
但是呢,又有人问了,那最高位再借位呢。就将两个数组补齐,再在最高位前面加两个0就可以了,使用栈存一下就能得到结果了

写的不好仅供参考

代码

class Solution {
public:vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) {int temp=0;int s1=arr1.size(),s2=arr2.size();int size=abs(s1-s2);vector<int>& p=s1<s2?arr1:arr2;push(p,size);push(arr1,2);push(arr2,2);stack<int> s;//偶位相加进1奇位减1 若奇位为0 ... 奇位同理auto it1=arr1.rbegin(),it2=arr2.rbegin();while(it1!=arr1.rend()||it2!=arr2.rend()){int t=*it1+*it2+temp;int jin=0;if(t<0){t+=2;jin=1;}else jin=-1*t/2;s.push(t%2);temp=jin;it1++;it2++;}trim(s);if(s.empty()) return {0};vector<int> res;while(!s.empty()){res.push_back(s.top());s.pop();}return res;}void push(vector<int>& p,int size){while(size--){p.insert(p.begin(),0);}}void trim(stack<int>& s){while(!s.empty()&&s.top()==0){s.pop();}}
};

http://www.ngui.cc/article/show-845527.html

相关文章

记一次nginx崩溃事件

一、事件描述 2023年春节复工第一天&#xff0c;项目组同事反馈说业务系统中图像处理代理Nginx服务于1月23日发生崩溃&#xff0c;完成了重启操作&#xff0c;检查nginx的日志有如下报错&#xff1a; 2023/01/23 11:07:07 [crit] 3237#3237: *2253009 pwritev() "/var/c…

mysql:如何在windows环境下配置并随意切换两种mysql版本

系列文章目录 文章目录系列文章目录前言一、去官网下载zip安装包二、配置创建my.ini文件2.环境变量3、使用管理员身份打开dos命令窗口4、安装mysql8的服务和初始化data5、启动6 错误解决&#xff1a;修改mysql8服务的注册表最后前言 之前安装过5.7的版本 后来由于需要 就安装了…

【Ambari】ambari中添加新服务

背景 栈的定义可以在源代码树中找到/ambari-server/src/main/resources/stacks。当你安装Ambari Server服务之后&#xff0c;栈的定义可以被发现/var/lib/ambari-server/resources/stacks。 结构 一个栈的结构定义如下 |_ stacks|_ <stack_name>|_ <stack_version…

云原生 | Kubernetes - kubectl 备忘单

目录 Kubectl 自动补全 BASH ZSH 关于 --all-namespaces 的一点说明 Kubectl 上下文和配置 Kubectl apply 创建对象 查看和查找资源 更新资源 部分更新资源 编辑资源 对资源进行伸缩 删除资源 与运行中的 Pod 进行交互 从容器中复制文件和目录 与 Deployments …

学习记录675@项目管理之风险管理案例

之前觉得风险管理章节废话太多就没有单独一篇文章记录&#xff0c;但是这个案例还是考到了风险管理的知识&#xff0c;所以借着这个案例梳理下一些重要的知识。 案例 某市石油销售公司计划实施全市的加油卡联网收费系统项目。该石油销售公司选择了系统集成商Simple 公司作为项…

实现文件拷贝,例如将1.c中的内容拷贝到2.c中;

实现文件拷贝&#xff0c;例如将1.c中的内容拷贝到2.c中&#xff1b;通过命令行传参的方式&#xff0c;传入文件名;计算一个文件的大小. 封装成函数通过命令行传参的方式&#xff0c;传入文件名; 统计一个文件有几行。封装成函数代码&#xff1a;#include <stdio.h> //封…

齐晖医药冲刺上市:毛利率持续下滑,刘祥宜和朱建民夫妇为实控人

近日&#xff0c;江苏齐晖医药科技股份有限公司&#xff08;下称“齐晖医药”&#xff09;递交预披露招股书&#xff0c;准备在上海证券交易所主板上市。本次冲刺上市&#xff0c;齐晖医药计划募资6.97亿元&#xff0c;将用于动保原料药生产基地项目、研发中心建设项目&#xf…

星环科技数据治理与数据价值评估实践分享

数据价值评估背景 自2015年8月国务院《促进大数据发展行动纲要》提出“数据已成为国家基础性战略资源”以来&#xff0c;我国出台了诸多政策和法案&#xff0c;推进数据的发展和数据要素的资产化。 2019年10月&#xff0c;第十九届四中全会关于《推进国家治理体系和治理能力现…

解决OpenEuler系统 Minimal BASH-like line editing is supported

2023年开工解决的第一个问题~呃&#xff0c;起因是这样的&#xff0c;由于业务需要&#xff0c;修改内核参数后重新打包内核&#xff0c;然后安装内核rpm包后&#xff0c;强制关机&#xff0c;结果就出现如上界面。网上搜索后绝大部分是因为安装了双系统后找不到grub系统引导文…

【数据结构】8.2 插入排序

文章目录前言1. 直接插入排序直接插入排序算法直接插入排序性能分析2. 折半插入排序3. 希尔排序希尔排序算法希尔排序算法分析排序方法比较前言 类似于俺们打牌时的插入&#xff0c;每抓来一张牌的时候&#xff0c;就将它放在合适的位置上&#xff0c;插入一张牌之后手里的牌仍…