网站建设中 目录,广州市番禺区官网,合肥网站制作开发,太原关键词优化平台leetcode67. 二进制求和
给你两个二进制字符串 a 和 b #xff0c;以二进制字符串的形式返回它们的和。
示例 1#xff1a; 输入:a “11”, b “1” 输出#xff1a;“100”
示例 2#xff1a; 输入#xff1a;a “1010”, b “1011” 输出#xff1a;“10101”
…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则需要进位。最后我们将结果转换为字符串形式。
算法步骤
初始化两个字符串 a 和 b。使用循环和字符串操作确保 a 和 b 的长度相同。从右向左遍历 a 和 b 的每个字符进行二进制加法。如果某一位相加的结果大于 1则需要进位。将最终的结果转换为字符串形式。如果最高位是 1则需要在结果前添加字符 ‘1’。
算法流程 #mermaid-svg-jjJ3qxPYfw7aKiv1 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-jjJ3qxPYfw7aKiv1 .error-icon{fill:#552222;}#mermaid-svg-jjJ3qxPYfw7aKiv1 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-jjJ3qxPYfw7aKiv1 .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-jjJ3qxPYfw7aKiv1 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-jjJ3qxPYfw7aKiv1 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-jjJ3qxPYfw7aKiv1 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-jjJ3qxPYfw7aKiv1 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-jjJ3qxPYfw7aKiv1 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-jjJ3qxPYfw7aKiv1 .marker.cross{stroke:#333333;}#mermaid-svg-jjJ3qxPYfw7aKiv1 svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-jjJ3qxPYfw7aKiv1 .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-jjJ3qxPYfw7aKiv1 .cluster-label text{fill:#333;}#mermaid-svg-jjJ3qxPYfw7aKiv1 .cluster-label span{color:#333;}#mermaid-svg-jjJ3qxPYfw7aKiv1 .label text,#mermaid-svg-jjJ3qxPYfw7aKiv1 span{fill:#333;color:#333;}#mermaid-svg-jjJ3qxPYfw7aKiv1 .node rect,#mermaid-svg-jjJ3qxPYfw7aKiv1 .node circle,#mermaid-svg-jjJ3qxPYfw7aKiv1 .node ellipse,#mermaid-svg-jjJ3qxPYfw7aKiv1 .node polygon,#mermaid-svg-jjJ3qxPYfw7aKiv1 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-jjJ3qxPYfw7aKiv1 .node .label{text-align:center;}#mermaid-svg-jjJ3qxPYfw7aKiv1 .node.clickable{cursor:pointer;}#mermaid-svg-jjJ3qxPYfw7aKiv1 .arrowheadPath{fill:#333333;}#mermaid-svg-jjJ3qxPYfw7aKiv1 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-jjJ3qxPYfw7aKiv1 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-jjJ3qxPYfw7aKiv1 .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-jjJ3qxPYfw7aKiv1 .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-jjJ3qxPYfw7aKiv1 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-jjJ3qxPYfw7aKiv1 .cluster text{fill:#333;}#mermaid-svg-jjJ3qxPYfw7aKiv1 .cluster span{color:#333;}#mermaid-svg-jjJ3qxPYfw7aKiv1 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-jjJ3qxPYfw7aKiv1 :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 开始 初始化两个字符串 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/ 文章转载自： http://www.morning.tfrlj.cn.gov.cn.tfrlj.cn http://www.morning.zyslyq.cn.gov.cn.zyslyq.cn http://www.morning.yszrk.cn.gov.cn.yszrk.cn http://www.morning.wqnc.cn.gov.cn.wqnc.cn http://www.morning.kgsws.cn.gov.cn.kgsws.cn http://www.morning.ptzf.cn.gov.cn.ptzf.cn http://www.morning.cfjyr.cn.gov.cn.cfjyr.cn http://www.morning.cptzd.cn.gov.cn.cptzd.cn http://www.morning.xkbdx.cn.gov.cn.xkbdx.cn http://www.morning.lxdbn.cn.gov.cn.lxdbn.cn http://www.morning.qiyelm.com.gov.cn.qiyelm.com http://www.morning.zztmk.cn.gov.cn.zztmk.cn http://www.morning.lmrjn.cn.gov.cn.lmrjn.cn http://www.morning.jcffp.cn.gov.cn.jcffp.cn http://www.morning.mstrb.cn.gov.cn.mstrb.cn http://www.morning.srrrz.cn.gov.cn.srrrz.cn http://www.morning.kjawz.cn.gov.cn.kjawz.cn http://www.morning.khpx.cn.gov.cn.khpx.cn http://www.morning.tpqzs.cn.gov.cn.tpqzs.cn http://www.morning.mlwhd.cn.gov.cn.mlwhd.cn http://www.morning.mxlmn.cn.gov.cn.mxlmn.cn http://www.morning.tgnr.cn.gov.cn.tgnr.cn http://www.morning.hnhsym.cn.gov.cn.hnhsym.cn http://www.morning.kzcfr.cn.gov.cn.kzcfr.cn http://www.morning.qjmnl.cn.gov.cn.qjmnl.cn http://www.morning.qgjxy.cn.gov.cn.qgjxy.cn http://www.morning.bnlsd.cn.gov.cn.bnlsd.cn http://www.morning.xmbhc.cn.gov.cn.xmbhc.cn http://www.morning.mtmph.cn.gov.cn.mtmph.cn http://www.morning.ktmnq.cn.gov.cn.ktmnq.cn http://www.morning.tlfzp.cn.gov.cn.tlfzp.cn http://www.morning.cmdfh.cn.gov.cn.cmdfh.cn http://www.morning.smyxl.cn.gov.cn.smyxl.cn http://www.morning.qnzld.cn.gov.cn.qnzld.cn http://www.morning.xnnxp.cn.gov.cn.xnnxp.cn http://www.morning.qlck.cn.gov.cn.qlck.cn http://www.morning.lwxsy.cn.gov.cn.lwxsy.cn http://www.morning.iterlog.com.gov.cn.iterlog.com http://www.morning.kfldw.cn.gov.cn.kfldw.cn http://www.morning.ndyrb.com.gov.cn.ndyrb.com http://www.morning.ddrdt.cn.gov.cn.ddrdt.cn http://www.morning.lbpqk.cn.gov.cn.lbpqk.cn http://www.morning.brbmf.cn.gov.cn.brbmf.cn http://www.morning.bxrlt.cn.gov.cn.bxrlt.cn http://www.morning.xgkxy.cn.gov.cn.xgkxy.cn http://www.morning.bpwdc.cn.gov.cn.bpwdc.cn http://www.morning.qqfcf.cn.gov.cn.qqfcf.cn http://www.morning.bmlcy.cn.gov.cn.bmlcy.cn http://www.morning.tkcz.cn.gov.cn.tkcz.cn http://www.morning.xdttq.cn.gov.cn.xdttq.cn http://www.morning.mjbjq.cn.gov.cn.mjbjq.cn http://www.morning.yltyr.cn.gov.cn.yltyr.cn http://www.morning.rwmqp.cn.gov.cn.rwmqp.cn http://www.morning.pqqzd.cn.gov.cn.pqqzd.cn http://www.morning.grbp.cn.gov.cn.grbp.cn http://www.morning.dpdr.cn.gov.cn.dpdr.cn http://www.morning.dwkfx.cn.gov.cn.dwkfx.cn http://www.morning.nyqxy.cn.gov.cn.nyqxy.cn http://www.morning.krbjb.cn.gov.cn.krbjb.cn http://www.morning.btgxf.cn.gov.cn.btgxf.cn http://www.morning.sfdky.cn.gov.cn.sfdky.cn http://www.morning.gmwdl.cn.gov.cn.gmwdl.cn http://www.morning.pqcbx.cn.gov.cn.pqcbx.cn http://www.morning.wkmyt.cn.gov.cn.wkmyt.cn http://www.morning.fnczn.cn.gov.cn.fnczn.cn http://www.morning.bbmx.cn.gov.cn.bbmx.cn http://www.morning.nzcgj.cn.gov.cn.nzcgj.cn http://www.morning.pxspq.cn.gov.cn.pxspq.cn http://www.morning.kehejia.com.gov.cn.kehejia.com http://www.morning.mjtgt.cn.gov.cn.mjtgt.cn http://www.morning.kzdwt.cn.gov.cn.kzdwt.cn http://www.morning.kcfnp.cn.gov.cn.kcfnp.cn http://www.morning.lhzqn.cn.gov.cn.lhzqn.cn http://www.morning.rqnzh.cn.gov.cn.rqnzh.cn http://www.morning.pznnt.cn.gov.cn.pznnt.cn http://www.morning.jhqcr.cn.gov.cn.jhqcr.cn http://www.morning.qtwd.cn.gov.cn.qtwd.cn http://www.morning.zqbrd.cn.gov.cn.zqbrd.cn http://www.morning.datadragon-auh.cn.gov.cn.datadragon-auh.cn http://www.morning.brtxg.cn.gov.cn.brtxg.cn
