leetcode67. 二进制求和,简单模拟

2024-08-21 01:36

本文主要是介绍leetcode67. 二进制求和,简单模拟,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

leetcode67. 二进制求和

给你两个二进制字符串 a 和 b ,以二进制字符串的形式返回它们的和。

示例 1:
输入:a = “11”, b = “1”
输出:“100”

示例 2:
输入:a = “1010”, b = “1011”
输出:“10101”

提示:
1 <= a.length, b.length <= 104
a 和 b 仅由字符 ‘0’ 或 ‘1’ 组成
字符串如果不是 “0” ,就不含前导零
在这里插入图片描述

题目描述

给定两个二进制字符串,返回它们相加的结果。

算法分析

这个问题可以通过直接模拟二进制加法来解决。我们首先确保两个字符串的长度相同,然后从右向左逐位相加。如果某一位相加的结果大于 1,则需要进位。最后,我们将结果转换为字符串形式。

算法步骤

  1. 初始化两个字符串 ab
  2. 使用循环和字符串操作,确保 ab 的长度相同。
  3. 从右向左遍历 ab 的每个字符,进行二进制加法。
  4. 如果某一位相加的结果大于 1,则需要进位。
  5. 将最终的结果转换为字符串形式。
  6. 如果最高位是 1,则需要在结果前添加字符 ‘1’。

算法流程

开始
初始化两个字符串 a 和 b
确保 a 和 b 的长度相同
从右向左进行二进制加法
处理进位
将结果转换为字符串
处理最高位的进位
结束

具体代码

class Solution {
public:string addBinary(string a, string b) {int al = a.size();int bl = b.size();while(al < bl) //让两个字符串等长,若不等长,在短的字符串前补零,否则之后的操作会超出索引{a = '0' + a;++ al;}while(al > bl){b = '0' + b;++ bl;}for(int j = a.size() - 1; j > 0; -- j) //从后到前遍历所有的位数,同位相加{a[j] = a[j] - '0' + b[j];if(a[j] >=  '2') //若大于等于字符‘2’,需要进一{a[j] = (a[j] - '0') % 2 + '0';a[j-1] = a[j-1] + 1;}}a[0] = a[0] - '0' + b[0]; //将ab的第0位相加if(a[0] >= '2') //若大于等于2,需要进一{a[0] = (a[0] - '0') % 2 + '0';a = '1' + a;}return a;}
};

算法分析

复杂度分析

  • 时间复杂度:O(max(a.size(), b.size()),其中 a.size()b.size() 分别是两个字符串的长度。
  • 空间复杂度:O(1),我们不需要额外的空间来存储数据。

易错点

  • 在确保两个字符串长度相同时,确保正确地添加零。
  • 在进行二进制加法时,确保正确地处理进位。
  • 在将结果转换为字符串时,确保正确地处理最高位的进位。

注意事项

  • 确保在处理字符串时不要超出字符串的边界。
  • 在进行字符转换时,确保不会覆盖任何字符。

相似题目

题目链接
二进制加法https://leetcode.com/problems/add-binary/
反转字符串https://leetcode.com/problems/reverse-string/
字符串转换整数https://leetcode.com/problems/string-to-integer-atoi/
整数转换字符串https://leetcode.com/problems/integer-to-roman/

这篇关于leetcode67. 二进制求和,简单模拟的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1091750

相关文章

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

hdu2289(简单二分)

虽说是简单二分,但是我还是wa死了  题意:已知圆台的体积,求高度 首先要知道圆台体积怎么求:设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路: 1. 用一个 hash[ ] 数组存放输入的数字,令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ,检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999,第二行数从 10到99。 4. 剪枝。 代码: /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h

usaco 1.2 Transformations(模拟)

我的做法就是一个一个情况枚举出来 注意计算公式: ( 变换后的矩阵记为C) 顺时针旋转90°:C[i] [j]=A[n-j-1] [i] (旋转180°和270° 可以多转几个九十度来推) 对称:C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<

uva 10387 Billiard(简单几何)

题意是一个球从矩形的中点出发,告诉你小球与矩形两条边的碰撞次数与小球回到原点的时间,求小球出发时的角度和小球的速度。 简单的几何问题,小球每与竖边碰撞一次,向右扩展一个相同的矩形;每与横边碰撞一次,向上扩展一个相同的矩形。 可以发现,扩展矩形的路径和在当前矩形中的每一段路径相同,当小球回到出发点时,一条直线的路径刚好经过最后一个扩展矩形的中心点。 最后扩展的路径和横边竖边恰好组成一个直

poj 1113 凸包+简单几何计算

题意: 给N个平面上的点,现在要在离点外L米处建城墙,使得城墙把所有点都包含进去且城墙的长度最短。 解析: 韬哥出的某次训练赛上A出的第一道计算几何,算是大水题吧。 用convexhull算法把凸包求出来,然后加加减减就A了。 计算见下图: 好久没玩画图了啊好开心。 代码: #include <iostream>#include <cstdio>#inclu

uva 10130 简单背包

题意: 背包和 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <queue>#include <map>

hdu4431麻将模拟

给13张牌。问增加哪些牌可以胡牌。 胡牌有以下几种情况: 1、一个对子 + 4组 3个相同的牌或者顺子。 2、7个不同的对子。 3、13幺 贪心的思想: 对于某张牌>=3个,先减去3个相同,再组合顺子。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOExcepti

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点