剑指Offer|LCR 002. 二进制求和

news/2024/12/19 19:48:04/

LCR 002. 二进制求和

给定两个 01 字符串 ab ,请计算它们的和,并以二进制字符串的形式输出。

输入为 非空 字符串且只包含数字 10

示例 1:

输入: a = "11", b = "10"
输出: "101"

提示:

  • 每个字符串仅由字符 '0''1' 组成。
  • 1 <= a.length, b.length <= 10^4
  • 字符串如果不是 "0" ,就都不含前导零。

使用js语言编写代码

法1:转为十进制计算,再转为二进制

分析:

可以将二进制字符转换成int型,然后把两个整数相加,再换成二进制字符。例如: ( 11 ) 2 + ( 10 ) 2 = ( 3 ) 10 + ( 2 ) 10 = ( 5 ) 10 = ( 101 ) 2 (11)_2+(10)_2=(3)_{10}+(2)_{10}=(5)_{10}=(101)_2 (11)2+(10)2=(3)10+(2)10=(5)10=(101)2(下标2表示二进制,10表示十进制)这个解法容易导致溢出。这题没有限制二进制字符串长度。当二进制字符串比较长时,它表示的整数可能超出int型整数或long型整数的范围,此时不能直接将其转换。

function addBinary(a, b) {// 将二进制字符串转换为十进制数let numA = parseInt(a, 2);let numB = parseInt(b, 2);// 计算二者的和let sum = numA + numB;// 将和转换为二进制字符串并返回return sum.toString(2);
};

leetcode上通过不了,计算示例 1还可以。

法2:直接加,逢二进一

分析:

按照十进制加法的思想,十进制是逢十进一,二进制是逢二进一

二进制加法类似,从字符串的右端出发,向左做加法,逢二进一

a = "11", b = "10"为例:

定义各自数组的索引,从右端出发计算,所以初始化为i = a.length - 1,j同理。此时获取到数字1数字0,即digitA=1,digitB=0,sum = 1,加入结果result = '1'

i和j等于0时,digitA=1,digitB=1,sum= 1+1+0 = 2,carry = 1,sum大于等于自减2,sum为0,加入结果result = '01'

当前carry=1,再在结果中加个进位result = '101'

  • 时间复杂度:O(max(m, n))
  • 空间复杂度:O(max(m, n))

其中,m 是字符串 a 的长度,n 是字符串 b 的长度。

var addBinary = function(a, b) {let result = '';let i = a.length - 1; // a的索引,从右往左遍历let j = b.length - 1; // b的索引let carry = 0; // 进位// 两个索引的值只要有一个是合法的(>=0,表明还有数要算),就要进行计算while (i >= 0 || j >= 0) {// 三目运算符// 下标ij合法,就取最右边的数字digitA、digitB// 因为a.charAt(i--)本身是字符串,通过 -'0' 操作 变为整数,i--,索引左移let digitA = i >= 0 ? a.charAt(i--) - '0' : 0;let digitB = j >= 0 ? b.charAt(j--) - '0' : 0;let sum = digitA + digitB + carry; // 计算当前位的和carry = sum >= 2 ? 1 : 0; // 逢二进一,sum>=2,carry进位就为1sum = sum >= 2 ? sum - 2 : sum; // sum>=2的话,需要自减2。也就是二进制中1+1=10,十进制1+1=2,这里的2-2=0,从而获取二进制结果10右端的0,如果sun就是1,就不用管,直接用1result = sum + result;  // 将当前位的计算结果加入结果}if (carry === 1) {result = '1' + result;  // carry进位存在的话,需要加到最左端}return result;
};

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

相关文章

Pikachu-XXE靶场(注入攻击)

1.攻击测试 <?xml version"1.0"?> <!DOCTYPE foo [ <!ENTITY xxe "a" > ]> <foo>&xxe;</foo> 2.查看文件 <?xml version"1.0"?> <!DOCTYPE foo [ <!ENTITY xxe SYSTEM "file:///E:/ph…

Django ORM查询优化策略

Django的ORM确实简化了数据库操作&#xff0c;但若使用不当&#xff0c;可能会引发性能问题。对于处理庞大数据集和高并发应用而言&#xff0c;优化数据库查询至关重要。以下是一些常见的查询优化策略&#xff1a; 避免N1查询问题&#xff1a;通过合理的查询设计&#xff0c;减…

docker 容器相互访问

目前采用 network 方式 1. 创建自定义网络 docker network create network-group 如下 2. 相互访问的容器更改&#xff08;目前演示redis 以及netcore api 访问redis &#xff09; //redis 原有容器删除 跟之前区别就是加入 --network network-group docker run \ -p 6379:…

浏览器对JSON格式数据的支持【超详解】

一、JSON 数据的解析 内置 JSON 解析器&#xff1a;现代浏览器都内置了 JSON 解析器&#xff0c;通过JSON.parse()方法可以将 JSON 格式的字符串转换为 JavaScript 对象或数组&#xff0c;以便在脚本中进行操作。例如&#xff1a; let jsonStr {"name":"John…

马斯克Neuralink:未来的人机交互先锋,将会挑战传统通讯方式

Neuralink&#xff0c;由埃隆马斯克于2016年创立&#xff0c;专注于研发脑机接口技术。该技术通过植入大脑的芯片&#xff0c;实现人类与机器的“无缝连接”。2024年&#xff0c;Neuralink取得了突破性进展&#xff0c;成功在人体中植入了脑芯片。首位植入者Noland Arbaugh通过…

Docker的镜像

目录 1. 镜像是什么&#xff1f;&#xff1f;2. 镜像命令详解2.1 镜像命令清单2.2 docker rmi命令2.3 docker save命令2.4 docker load命令2.5 docker history命令2.6 docker import命令2.7 docker image prune命令2.8 docker build命令 3. 镜像的操作4. 离线迁移镜像5. 镜像存…

基于Spring Boot的校园部门资料管理系统

一、系统背景与目的 随着信息技术的飞速发展&#xff0c;校园信息化建设成为必然趋势。学校各部门在日常工作中积累了大量的资料&#xff0c;包括教学资料、学生档案、科研成果、行政文件等。传统的纸质资料管理方式存在效率低、易丢失、难以检索等问题&#xff0c;无法满足现…

有哪些 Web 应用程序类型

Web 应用程序类型多种多样&#xff0c;可以根据其架构、交互方式、数据处理模式等多个维度进行分类。以下是几种常见的 Web 应用程序类型&#xff1a; 1. 静态网站 (Static Websites) 描述&#xff1a;这类网站主要由 HTML 文件组成&#xff0c;内容固定且不经常变化。它们通…