一、题目描述
来源:力扣（LeetCode）
实现 strStr() 函数。 给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
示例 1:
代码语言：javascript复制输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3示例 2:
代码语言：javascript复制输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2提示：
- 被除数和除数均为 32 位有符号整数。
- 除数不为 0。
- 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。
二、思路分析
1. 自己的思路
由于不能用除法、乘法和%运算，也就是说可以用减法，除法就是求出被除数由多少个除数加起来的结果集，那我们反过来用减法，每次被除数减去除数，记录减的次数，直到被除数小于除数，减了多少次就是商
由于忽略了被除数是2^31,除数是1或者-1的情况，AC后速度超级慢，已经算超时了，故这种方式不行
2. 别人的思路
为避免运算过程中出现超过32位限制，将入参全部转为负数运算，运算结果再根据入参符号判断正负（超限则返回Integer.MAX_VALUE）
题目要求不能使用除法，循环减则效率太低，那么可以采用位移实现除法操作（不了解位移请自行百度），因为位移只能实现除以2^0，2^1...2^n的操作，而divisor值可能落于2^(n-1)与2^n之间，所以需要循环（实现dividend除以2^(n-1)与2^n之间某个数的操作）来使dividend位移结果不断逼近divisor，直至得出最终结果，以下给出具体运算说明
将dividend右移n位，n符合dividend>>n的绝对值小于divisor绝对值，dividend>>(n-1)的绝对值大于divisor绝对值，则dividend除以divisor大于2^(n-1)，小于2^n（自己代入数值进行验证，此处不予证明）。那么divisor乘以2^(n-1)小于dividend，乘以2^n大于dividend，divisor乘以2^(n-1)为当前循环最接近dividend的值。将dividend与divisor乘以2^(n-1)的差（相当于除法中的余数）重新赋值给dividend，重复计算dividend与divisor的最接近结果，直至最终dividend绝对值小于divisor绝对值，累加多次循环得出最终结果
三、代码实现
1. 自己实现的代码
代码语言：javascript复制class Solution {
public int strStr(String haystack, String needle) {
if("".equals(needle)){
return 0;
}
int idx = -1;
int nlen = needle.length();
int hlen = haystack.length();
for (int i = 0; i < hlen; i ) {
if (i nlen > haystack.length()) {
break;
}
String substring = haystack.substring(i, i nlen);
if(substring.equals(needle)){
idx = i;
break;
}
}
return idx;
}
}2. 别人实现的代码
代码语言：javascript复制class Solution {
public int divide(int dividend, int divisor) {
boolean symbol = true;
if (dividend > 0) {
dividend = -dividend;
symbol = false;
}
if (divisor > 0) {
divisor = -divisor;
symbol = !symbol;
}
int result = 0;
while (dividend <= divisor) {
int n = 1;
while (true) {
int compare = dividend >> n;
if (compare >= divisor) {
result -= (int) Math.pow(2, n - 1);
dividend = dividend - (divisor << (n - 1));
break;
}
n ;
}
}
return symbol ? (result == Integer.MIN_VALUE ? Integer.MAX_VALUE : -result) : result;
}
}四、运行结果
1. 时间过长的AC结果
2. 别人的AC结果
总结
这道题限制了简单的解题方式，实在想不到的好的办法，看到别人用二分，倍增乘法，还有用位移的，感叹计算机的神奇和自己的不足
