【力扣刷题】29. 两数相除

jayjay

发布于 2022-11-02 16:54:22

5540

发布于 2022-11-02 16:54:22

文章被收录于专栏：jay_blogjay_blog

一、题目描述

来源:力扣（LeetCode）

实现 strStr() 函数。给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

示例 1:

输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3

示例 2:

输入: 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. 自己实现的代码

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. 别人实现的代码

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;
    }
}