Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit2c392ae

Browse files
committed
Add leetcode daily problem
1 parent4f2de0f commit2c392ae

File tree

2 files changed

+249
-0
lines changed

2 files changed

+249
-0
lines changed
Lines changed: 92 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,92 @@
1+
#LeetCode[371. 两整数之和](https://leetcode-cn.com/problems/sum-of-two-integers/)
2+
3+
##题解
4+
5+
题目要求不能使用 $+、-$​，自然想到使用其他的二元运算符，我们可以根据二进制位，选择位运算符计算得到两数之和。
6+
7+
###两个二进制位相加有以下四种情况
8+
9+
```
10+
1 + 1 = 0 (进位)
11+
1 + 0 = 1
12+
0 + 1 = 1
13+
0 + 0 = 0
14+
```
15+
16+
直接使用异或 ​^ 运算符的话，需要额外处理 两个二进制位都为1 的情况。
17+
18+
我们可以使用 bit位为进位符，来判断这种情况。
19+
20+
下面考虑 bit进位符，如何和两个二进制位相加相结合。
21+
22+
**假设现在统计到二进制的第 i 位。**
23+
24+
```
25+
bit = 0 的情况
26+
27+
二进制位相加 运算后结果
28+
29+
1 + 1 = 0 (进位) --> 答案加 0 bit=1
30+
1 + 0 = 1 --> 答案加 2^i bit=0
31+
0 + 1 = 1 --> 答案加 2^i bit=0
32+
0 + 0 = 0 --> 答案加 2^i bit=0
33+
```
34+
35+
```
36+
bit = 1 的情况
37+
38+
二进制位相加 运算后结果
39+
40+
1 + 1 = 0 (进位) --> 答案加 2^i bit=1
41+
1 + 0 = 1 --> 答案加 0 bit=1
42+
0 + 1 = 1 --> 答案加 0 bit=1
43+
0 + 0 = 0 --> 答案加 2^i bit=0
44+
```
45+
46+
、
47+
48+
数据范围是 $-1000<=x<=1000$，如果没有负数，根据二进制位，我们只需要统计10个二进制位，因为 $2^{10}=1024>100$​。
49+
50+
有负数的情况，我们需要统计到最高位，判断是否为负数，因此要统计32位。
51+
52+
时间复杂度: $O(C)$ C为常数32。
53+
54+
空间复杂度: O(1)。
55+
56+
57+
##代码
58+
59+
```c++
60+
classSolution {
61+
public:
62+
int getSum(int a, int b) {
63+
int ans = 0, bit = 0;
64+
for (int i = 0; i < 32; i++) {
65+
int x = (a >> i) & 1, y = (b >> i) & 1;
66+
if (x == 1 && y == 1) {
67+
ans |= (bit << i);
68+
bit = 1;
69+
} else if (x | y) {
70+
ans |= (1 ^ bit) << i;
71+
} else {
72+
ans |= (bit << i);
73+
bit = 0;
74+
}
75+
}
76+
return ans;
77+
}
78+
};
79+
```
80+
81+
## 最后
82+
83+
大家好，我是编程熊，字节跳动、旷视科技前员工，ACM亚洲区域赛金牌，欢迎 [关注我](https://leetcode-cn.com/u/bianchengxiong/) 和加入 [LeetCode组队刷题群](https://mp.weixin.qq.com/s/TsTcCDboXwnTnUeIW3Zg9Q)。
84+
85+
分享几篇算法超级易懂的文章，希望对你有所帮助
86+
87+
1、[ACM金牌选手讲解LeetCode算法《线性表》](https://mp.weixin.qq.com/s/qwaYOFIksFVqZtA_nisl6g)
88+
2、[ACM金牌选手讲解LeetCode算法《栈和队列的高级应用》](https://mp.weixin.qq.com/s/I3DQOUmABmWav4nrAiI3Fg)
89+
3、[ACM金牌选手讲解LeetCode算法《哈希表》](https://mp.weixin.qq.com/s/af4gvYURUoCTfsyzsI9Www)
90+
4、[ACM金牌选手讲解LeetCode算法《二叉树》](https://mp.weixin.qq.com/s/8AcRNQS0Nno2_fU6kMtZeQ)
91+
92+
如果题解和文章对你有所帮助，欢迎**点赞**支持。
Lines changed: 157 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,157 @@
1+
#LeetCode[371. 两整数之和](https://leetcode-cn.com/problems/sum-of-two-integers/)
2+
3+
##题解
4+
5+
6+
7+
题目要求不能使用 $+、-$，自然想到使用其他的二元运算符，我们可以根据二进制位，选择位运算符计算得到两数之和。
8+
9+
**二进制相加，思想类似于十进制加法，但从「逢十进一」变为 「逢二进一」。**
10+
11+
**两个二进制位相加有以下四种情况。**
12+
13+
```
14+
15+
1 + 1 = 0 (进位)
16+
17+
1 + 0 = 1
18+
19+
0 + 1 = 1
20+
21+
0 + 0 = 0
22+
23+
```
24+
25+
26+
27+
直接使用异或 ^ 运算符的话，需要额外处理进位的情况， 即两个二进制位都为1。
28+
29+
我们可以使用 bit位为进位符，来判断这种情况。
30+
31+
下面考虑bit进位符，两个二进制位如何相加。
32+
33+
34+
35+
**假设现在统计到二进制的第 i 位。**
36+
37+
```
38+
39+
bit = 0 的情况
40+
41+
42+
43+
二进制位相加 运算后结果
44+
45+
46+
47+
1 + 1 = 0 (进位) --> 答案加 0 bit=1
48+
49+
1 + 0 = 1 --> 答案加 2^i bit=0
50+
51+
0 + 1 = 1 --> 答案加 2^i bit=0
52+
53+
0 + 0 = 0 --> 答案加 2^i bit=0
54+
55+
```
56+
57+
58+
59+
```
60+
61+
bit = 1 的情况
62+
63+
64+
65+
二进制位相加 运算后结果
66+
67+
68+
69+
1 + 1 = 0 (进位) --> 答案加 2^i bit=1
70+
71+
1 + 0 = 1 --> 答案加 0 bit=1
72+
73+
0 + 1 = 1 --> 答案加 0 bit=1
74+
75+
0 + 0 = 0 --> 答案加 2^i bit=0
76+
77+
```
78+
79+
数据范围是 $-1000<=x<=1000$，如果没有负数，根据二进制位，我们只需要统计10个二进制位，因为 $2^{10}=1024>100$。
80+
81+
有负数的情况，我们需要统计到最高位，判断是否为负数，因此要统计32位。
82+
83+
时间复杂度: $O(C)$ C为常数32。
84+
85+
空间复杂度: $O(1)$。
86+
87+
##代码
88+
89+
90+
91+
```c++
92+
93+
classSolution {
94+
95+
public:
96+
97+
int getSum(int a, int b) {
98+
99+
int ans = 0, bit = 0;
100+
101+
for (int i = 0; i < 32; i++) {
102+
103+
int x = (a >> i) & 1, y = (b >> i) & 1;
104+
105+
if (x & y) {
106+
107+
ans |= (bit << i);
108+
109+
bit = 1;
110+
111+
} else if (x | y) {
112+
113+
ans |= (1 ^ bit) << i;
114+
115+
} else {
116+
117+
ans |= (bit << i);
118+
119+
bit = 0;
120+
121+
}
122+
123+
}
124+
125+
return ans;
126+
127+
}
128+
129+
};
130+
131+
```
132+
133+
134+
##最后
135+
136+
137+
138+
大家好，我是编程熊，字节跳动、旷视科技前员工，ACM亚洲区域赛金牌，欢迎[关注我](https://leetcode-cn.com/u/bianchengxiong/) 和加入[LeetCode组队刷题群](https://mp.weixin.qq.com/s/TsTcCDboXwnTnUeIW3Zg9Q)。
139+
140+
141+
142+
**分享几篇算法超级易懂的文章，希望对你有所帮助**
143+
144+
1、[ACM金牌选手讲解LeetCode算法《线性表》](https://mp.weixin.qq.com/s/qwaYOFIksFVqZtA_nisl6g)
145+
146+
2、[ACM金牌选手讲解LeetCode算法《栈和队列的高级应用》](https://mp.weixin.qq.com/s/I3DQOUmABmWav4nrAiI3Fg)
147+
148+
3、[ACM金牌选手讲解LeetCode算法《哈希表》](https://mp.weixin.qq.com/s/af4gvYURUoCTfsyzsI9Www)
149+
150+
4、[ACM金牌选手讲解LeetCode算法《二叉树》](https://mp.weixin.qq.com/s/8AcRNQS0Nno2_fU6kMtZeQ)
151+
152+
5、[编程熊讲解LeetCode算法《堆》](https://mp.weixin.qq.com/s/ggd42G_QJ6I43F-vXSbpdA)
153+
154+
155+
156+
如果题解和文章对你有所帮助，欢迎**点赞**支持。
157+

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp