目录
题目
注意：
示例 1:
示例 2:
提示：
题目解析
题目思路
代码思路
数据处理
注意
减法函数
第一次使用的函数
问题
第二次改良后的代码
处理i的值并且返回
总代码
力扣的代码
注意
题目
给你两个整数，被除数 dividend 和除数 divisor。将两数相除，要求 不使用 乘法、除法和取余运算。
整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345 将被截断为 8 ，-2.7335 将被截断至 -2 。
返回被除数 dividend 除以除数 divisor 得到的 商 。
注意：
假设我们的环境只能存储 32 位 有符号整数，其数值范围是 [−231, 231 − 1] 。本题中，如果商 严格大于 231 − 1 ，则返回 231 − 1 ；如果商 严格小于 -231 ，则返回 -231 。
示例 1:
输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = 3.33333… ，向零截断后得到 3 。
示例 2:
输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = -2.33333… ，向零截断后得到 -2 。
提示：
-231 <= dividend, divisor <= 231 - 1divisor != 01
2
3
4
5
6
7
| if (dividend == 0)return 0;
if (divisor == 1)return dividend;
if (divisor == -1)
{
if (dividend > INT_MIN) return -dividend;
return INT_MAX;
}
|
题目解析
这是一个让你不用除法来实现除法的题目
很奇怪，代码中不能直接或者间接的用除法，乘法，以及求余
题目思路
由于还可以用减法以及加法
这时候可以想到小学的知识
除法的本质就是看在被除数中有几个除数
我们可以用减法来依次减去就可以了
代码思路
越界的情况
首先我们要判断给出的值越界的情况
1
2
3
4
5
6
7
| if (dividend == 0)return 0;
if (divisor == 1)return dividend;
if (divisor == -1)
{
if (dividend > INT_MIN) return -dividend;
return INT_MAX;
}
|
数据处理
之后我们判断除数与被除数之间的的符号关系并且记录下来
并且为了方便结算全部取绝对值
1
2
3
4
5
6
7
8
| long long i = 0;
long long sum_1 = (long long)dividend * divisor;
if (dividend < 0)
dividend = -dividend;
if (divisor < 0)
divisor = -divisor;
|
注意
这里的long long的数据类型是为了防止给出的数据相乘后越界，并且把其中"i"变量的值记录下来用于返回
减法函数
第一次使用的函数
原来是用这个函数的
1
2
3
4
5
| while (dividend >= divisor)
{
dividend=dividend-divisor;
i++
}
|
问题
运行时间可能会慢因为除数是21亿并且除数是2的话要运行10亿次
第二次改良后的代码
1
2
3
4
5
6
7
8
9
10
11
12
| while (dividend >= divisor)
{
long long j = 1;
long long sum_3 = divisor;
while (dividend> sum_3 + sum_3)
{
sum_3 = sum_3 + sum_3;
j = j + j;
}
dividend = dividend - sum_3;
i = i + j;
}
|
这个实现方法就是
如果是144除以2第一步执行的是144-64第二步为80-64第三步为16-16
这样运行步骤会大大降低
处理i的值并且返回
1
2
3
| if (sum_1 < 0)
i = -i;
return i;
|
总代码
可以直接运行的代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include <iostream>
using namespace std;
int divide(long long dividend, long long divisor)
{
if (dividend == 0)return 0;
if (divisor == 1)return dividend;
if (divisor == -1)
{
if (dividend > INT_MIN) return -dividend;
return INT_MAX;
}
long long i = 0;
long long sum_1 = (long long)dividend * divisor;
if (dividend < 0)
dividend = -dividend;
if (divisor < 0)
divisor = -divisor;
while (dividend >= divisor)
{
long long j = 1;
long long sum_3 = divisor;
while (dividend> sum_3 + sum_3)
{
sum_3 = sum_3 + sum_3;
j = j + j;
}
dividend = dividend - sum_3;
i = i + j;
}
if (sum_1 < 0)
i = -i;
return i;
}
int main()
{
int a = divide(-2147483648, -3);
cout << a << endl;
return 0;
}
|
力扣的代码
力扣提交的代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| class Solution {
public:
int divide(long long dividend, long long divisor)
{
if (dividend == 0)return 0;
if (divisor == 1)return dividend;
if (divisor == -1)
{
if (dividend > INT_MIN) return -dividend;
return INT_MAX;
}
long long i = 0;
long long sum_1 = (long long)dividend * divisor;
if (dividend < 0)
dividend = -dividend;
if (divisor < 0)
divisor = -divisor;
while (dividend >= divisor)
{
long long j = 1;
long long sum_3 = divisor;
while (dividend> sum_3 + sum_3)
{
sum_3 = sum_3 + sum_3;
j = j + j;
}
dividend = dividend - sum_3;
i = i + j;
}
if (sum_1 < 0)
i = -i;
return i;
}
};
|
注意
代码不难，注意越界的数据越界的问题
