力扣加加 - 努力做西湖区最好的算法题解
lucifer 的博客
Github
公众号
搜索文档…
introduction
第一章 - 算法专题
第二章 - 91 天学算法
第三章 - 精选题解
第四章 - 高频考题(简单)
面试题 17.12. BiNode
0001. 两数之和
0020. 有效的括号
0021. 合并两个有序链表
0026. 删除排序数组中的重复项
0053. 最大子序和
0160. 相交链表
0066. 加一
0088. 合并两个有序数组
0101. 对称二叉树
0104. 二叉树的最大深度
0108. 将有序数组转换为二叉搜索树
0121. 买卖股票的最佳时机
0122. 买卖股票的最佳时机 II
0125. 验证回文串
0136. 只出现一次的数字
0155. 最小栈
0167. 两数之和 II 输入有序数组
0169. 多数元素
0172. 阶乘后的零
0190. 颠倒二进制位
0191. 位 1 的个数
0198. 打家劫舍
0203. 移除链表元素
0206. 反转链表
0219. 存在重复元素 II
0226. 翻转二叉树
0232. 用栈实现队列
0263. 丑数
0283. 移动零
0342. 4 的幂
0349. 两个数组的交集
0371. 两整数之和
401. 二进制手表
0437. 路径总和 III
0455. 分发饼干
0504. 七进制数
0575. 分糖果
0665. 非递减数列
0661. 图片平滑器
821. 字符的最短距离
0874. 模拟行走机器人
1128. 等价多米诺骨牌对的数量
1260. 二维网格迁移
1332. 删除回文子序列
第五章 - 高频考题(中等)
第六章 - 高频考题(困难)
后序
由
GitBook
提供支持
0371. 两整数之和
题目地址(371. 两整数之和)
https://leetcode-cn.com/problems/sum-of-two-integers/
题目描述
1
不使用运算符 + 和 - ,计算两整数 a 、b 之和。
2
3
示例 1:
4
5
输入: a = 1, b = 2
6
输出: 3
7
示例 2:
8
9
输入: a = -2, b = 3
10
输出: 1
Copied!
前置知识
位运算
公司
阿里
腾讯
百度
字节
思路
不能使用加减法来求加法。 我们只能朝着位元算的角度来思考了。
由于
异或
是
相同则位0,不同则位1
,因此我们可以把异或看成是一种不进位的加减法。
371.sum-of-two-integers-1
由于
与
是
全部位1则位1,否则位0
,因此我们可以求与之后左移一位来表示进位。
371.sum-of-two-integers-2
然后我们对上述两个元算结果递归求解即可。 递归的结束条件就是其中一个为 0,我们直接返回另一个。
关键点解析
位运算
异或是一种不进位的加减法
求与之后左移一位来可以表示进位
代码
代码支持:JS,C++,Java,Python Javascript Code:
1
/*
2
* @lc app=leetcode id=371 lang=javascript
3
*
4
* [371] Sum of Two Integers
5
*/
6
/**
7
* @param {number} a
8
* @param {number} b
9
* @return {number}
10
*/
11
var
getSum
=
function
(
a
,
b
)
{
12
if
(
a
===
0
)
return
b
;
13
14
if
(
b
===
0
)
return
a
;
15
16
return
getSum
(
a
^
b
,
(
a
&
b
)
<<
1
);
17
};
Copied!
C++ Code:
1
class
Solution
{
2
public
:
3
int
getSum
(
int
a
,
int
b
)
{
4
if
(
a
==
0
)
return
b
;
5
if
(
b
==
0
)
return
a
;
6
7
while
(
b
!=
0
)
8
{
9
// 防止 AddressSanitizer 对有符号左移的溢出保护处理
10
auto
carry
=
((
unsigned
int
)
(
a
&
b
))
<<
1
;
11
// 计算无进位的结果
12
a
=
a
^
b
;
13
//将存在进位的位置置1
14
b
=
carry
;
15
}
16
return
a
;
17
}
18
};
Copied!
Java Code:
1
class
Solution
{
2
public
int
getSum
(
int
a
,
int
b
)
{
3
if
(
a
==
0
)
return
b
;
4
if
(
b
==
0
)
return
a
;
5
6
while
(
b
!=
0
)
7
{
8
int
carry
=
a
&
b
;
9
// 计算无进位的结果
10
a
=
a
^
b
;
11
//将存在进位的位置置1
12
b
=
carry
<<
1
;
13
}
14
return
a
;
15
}
16
}
Copied!
Python Code:
1
# python整数类型为Unifying Long Integers, 即无限长整数类型.
2
# 模拟 32bit 有符号整型加法
3
class
Solution
:
4
def
getSum
(
self
,
a
:
int
,
b
:
int
)
->
int
:
5
a
&=
0xFFFFFFFF
6
b
&=
0xFFFFFFFF
7
while
b
:
8
carry
=
a
&
b
9
a
^=
b
10
b
=
((
carry
)
<<
1
)
&
0xFFFFFFFF
11
# print((a, b))
12
return
a
if
a
<
0x80000000
else
~
(
a
^
0xFFFFFFFF
)
Copied!
复杂度分析
时间复杂度:$O(1)$
空间复杂度:$O(1)$
由于题目数据规模不会变化,因此其实复杂度分析是没有意义的。
更多题解可以访问我的 LeetCode 题解仓库:
https://github.com/azl397985856/leetcode
。 目前已经 37K star 啦。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。
以前
0349. 两个数组的交集
下一个
401. 二进制手表
最近更新
1yr ago
复制链接
内容
题目地址(371. 两整数之和)
题目描述
前置知识
公司
思路
关键点解析
代码