LeetCode 1073. 负二进制数相加:简单算法 + 原理解析

news/2024/10/30 2:54:24/

【LetMeFly】1073.负二进制数相加

力扣题目链接:https://leetcode.cn/problems/adding-two-negabinary-numbers/

给出基数为 -2 的两个数 arr1 和 arr2,返回两数相加的结果。

数字以 数组形式 给出:数组由若干 0 和 1 组成,按最高有效位到最低有效位的顺序排列。例如,arr = [1,1,0,1] 表示数字 (-2)^3 + (-2)^2 + (-2)^0 = -3数组形式 中的数字 arr 也同样不含前导零:即 arr == [0] 或 arr[0] == 1

返回相同表示形式的 arr1arr2 相加的结果。两数的表示形式为:不含前导零、由若干 0 和 1 组成的数组。

 

示例 1:

输入:arr1 = [1,1,1,1,1], arr2 = [1,0,1]
输出:[1,0,0,0,0]
解释:arr1 表示 11,arr2 表示 5,输出表示 16 。

示例 2:

输入:arr1 = [0], arr2 = [0]
输出:[0]

示例 3:

输入:arr1 = [0], arr2 = [1]
输出:[1]

 

提示:

  • 1 <= arr1.length, arr2.length <= 1000
  • arr1[i] 和 arr2[i] 都是 0 或 1
  • arr1 和 arr2 都没有前导0

方法一:模拟

使用一个变量 c c c来存放加法的进位。我们从最低位开始遍历两个数组,记两个数组的当前元素分别为 a a a b b b。令 x = a + b + c x = a + b + c x=a+b+c

  • x ≥ 2 x\geq 2 x2,则 x − = 2 , c = − 1 x -= 2, c = -1 x=2,c=1,即逢 2 2 2 − 1 -1 1(后面会解释)
  • x = − 1 x = -1 x=1,则 x = 1 , c = 1 x = 1, c = 1 x=1,c=1
  • 否则, c = 0 c=0 c=0(不产生进位)

x x x的最终值加入到答案数组中,继续处理下一位。

最终将答案数组翻转并去除前导零即可。

原因解释:

首先假设上述方法正确,因两个 0 0 0 1 1 1相加的结果在 0 0 0 2 2 2之间,进位 c c c的范围在 − 1 -1 1 1 1 1之间,所以 x = a + b + c x=a+b+c x=a+b+c的范围在 − 1 -1 1 3 3 3之间。

  • x = 2 x=2 x=2 x = 3 x=3 x=3,因为负2进制每一位的范围是 0 0 0 1 1 1,所以 x x x需要进位。记进位后的数为 x f i n a l x_{final} xfinal,则有 x = 2 + x f i n a l x=2+x_{final} x=2+xfinal

    x × ( − 2 ) i = ( 2 + x f i n a l ) × ( − 2 ) i = 2 × ( − 2 ) i + x f i n a l × ( − 2 ) i = ( − 1 ) × ( − 2 ) × ( − 2 ) i + x f i n a l × ( − 2 ) i = ( − 1 ) × ( − 2 ) i + 1 + x f i n a l × ( − 2 ) i \begin{align*} x\times(-2)^{i}& =(2+x_{final})\times(-2)^{i}\\ &=2\times(-2)^i+x_{final}\times(-2)^i \\ &=(-1)\times(-2)\times(-2)^i+x_{final}\times(-2)^i \\ &=(-1)\times(-2)^{i+1}+x_{final}\times(-2)^i \end{align*} x×(2)i=(2+xfinal)×(2)i=2×(2)i+xfinal×(2)i=(1)×(2)×(2)i+xfinal×(2)i=(1)×(2)i+1+xfinal×(2)i
    因此,进位为 − 1 -1 1,本位为 x f i n a l = x − 2 x_{final}=x - 2 xfinal=x2(在 0 0 0 1 1 1的范围内)

  • x = − 1 x=-1 x=1,同理, x × ( − 2 ) i = ( − 1 ) × ( − 2 ) i = ( ( 1 ) + ( − 2 ) ) × ( − 2 ) i = ( − 2 ) i + 1 + ( − 2 ) i x\times(-2)^i=(-1)\times(-2)^i=((1) + (-2))\times(-2)^i=(-2)^{i+1}+(-2)^i x×(2)i=(1)×(2)i=((1)+(2))×(2)i=(2)i+1+(2)i,所以进位为 1 1 1,本位为 1 1 1
  • x = 0 x=0 x=0 x = 1 x=1 x=1,则不必考虑进位( c = 0 c=0 c=0

完毕。

  • 时间复杂度 O ( N 2 ) \mathcal O(N^2) O(N2)
  • 空间复杂度 O ( N log ⁡ N ) \mathcal O(N\log N) O(NlogN)

AC代码

C++

class Solution {
public:vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) {vector<int> ans;for (int i = arr1.size() - 1, j = arr2.size() - 1, c = 0; i >= 0 || j >= 0 || c; i--, j--) {int a = i >= 0 ? arr1[i] : 0;int b = j >= 0 ? arr2[j] : 0;int x = a + b + c;if (x >= 2) {x -= 2;c = -1;}else if (x == -1) {x = 1;c = 1;}else {c = 0;}ans.push_back(x);}while (ans.size() > 1 && !ans.back()) {ans.pop_back();}reverse(ans.begin(), ans.end());return ans;}
};

Python

# from typing import Listclass Solution:def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:i, j, c = len(arr1) - 1, len(arr2) - 1, 0ans = []while i >= 0 or j >= 0 or c:a = arr1[i] if i >= 0 else 0b = arr2[j] if j >= 0 else 0x = a + b + cif x >= 2:x -= 2c = -1elif x == -1:x = 1c = 1else:c = 0ans.append(x)i, j = i - 1, j - 1while len(ans) > 1 and not ans[-1]:ans.pop()ans.reverse()return ans

同步发文于CSDN,原创不易,转载请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/130741318


http://www.ppmy.cn/news/70219.html

相关文章

以SpringMVC入门案例分析服务器初始化过程、单次请求流程

文章目录 1&#xff0c;SpringMVC概述2&#xff0c;SpringMVC入门案例2.1 需求分析2.2 案例制作步骤1:创建Maven项目步骤2:补全目录结构步骤3:导入jar包步骤4:创建配置类步骤5:创建Controller类步骤6:使用配置类替换web.xml步骤7:配置Tomcat环境步骤8:启动运行项目步骤9:浏览器…

【Spring Cloud Alibaba】Nacos的安装与介绍以及Nacos集群的安装

欢迎来到 Nacos 的世界&#xff01; Nacos /nɑ:kəʊs/ 是 Dynamic Naming and Configuration Service的首字母简称&#xff0c;一个更易于构建云原生应用的动态服务发现、配置管理和服务管理平台。 Nacos 致力于帮助您发现、配置和管理微服务。Nacos 提供了一组简单易用的特性…

Vue3通透教程【十二】TS类型声明优势

文章目录 &#x1f31f; 写在前面&#x1f31f; 上篇文章解惑&#x1f31f; JS函数中的隐患&#x1f31f; 函数中的类型&#x1f31f; 写在最后 &#x1f31f; 写在前面 专栏介绍&#xff1a; 凉哥作为 Vue 的忠实 粉丝输出过大量的 Vue 文章&#xff0c;应粉丝要求开始更新 V…

屏幕录像怎么录?分享3个简单实用的方法!

案例&#xff1a;怎么录制电脑屏幕&#xff1f; 【对于我这种不太熟悉电脑的人来说&#xff0c;想要录制电脑屏幕十分困难。听说录制电脑屏幕&#xff0c;需要用到录屏工具。有没有小伙伴有好的录屏软件介绍&#xff0c;顺便附带一下教程&#xff01;求&#xff01;】 屏幕录…

QML APP开发套路(三):前/后端值传递(自定义值类型)

&#xff08;1&#xff09;前/后端交互内容 QML APP前后端交互的内容按目标&#xff08;拍脑袋&#xff09;可以分为2个部分&#xff1a; 方向内容后端&#xff08;C&#xff09; → 前端&#xff08;QML&#xff09;前端展示所需的数据&#xff0c;形式&#xff1a;简单类型…

eBPF动手实践系列二:构建基于纯C语言的eBPF项目

千里之行&#xff0c;始于足下 了解和掌握纯c语言的eBPF编译和使用&#xff0c;有助于我们加深对于eBPF技术原理的进一步掌握&#xff0c;也有助于开发符合自己业务需求的高性能的ebpf程序。上一篇文章《eBPF动手实践系列一&#xff1a;解构内核源码eBPF样例编译过程》中&…

Python语法装饰器

参考&#xff1a; 【【python】装饰器超详细教学&#xff0c;用尽毕生所学给你解释清楚&#xff0c;以后再也不迷茫了&#xff01;-哔哩哔哩】 https://b23.tv/Y6Ss8cN【Python小技巧&#xff1a;装饰器(Decorator)-哔哩哔哩】 https://b23.tv/hacMmem x.1 Python中的Abstract…

142. 环形链表 II Python

文章目录 一、题目描述示例 1示例 2示例 3 二、代码三、解题思路 一、题目描述 给定一个链表的头节点 head &#xff0c;返回链表开始入环的第一个节点。 如果链表无环&#xff0c;则返回 null。 如果链表中有某个节点&#xff0c;可以通过连续跟踪 next 指针再次到达&#x…