Day19 两数相除

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

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

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

https://leetcode-cn.com/problems/divide-two-integers/

示例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 位有符号整数，其数值范围是 [−2^31, 2^31 − 1]。本题中，如果除法结果溢出，则返回 2^31 − 1。

Java解法

思路：

• Emmm 知识盲区，没有思路，看下大佬们的解法

• 没有啥官方解，参考了下大佬们的解法，主要两个步骤

• 转换为减法，不断减值逼近结果，优化查找提高效率

• 处理边界符号问题，符号问题有特殊处理及转long型处理的方式，这边尝试下特殊处理

• 运算正常，但是超时

  public static int divide(int dividend, int divisor) {
      if (divisor==0) {
          return 0;
      }
      //dividend =  divisor * result
      int result = 0;
      if (dividend > 0 && divisor > 0) {
          while (dividend -divisor >= 0) {
              result++;
              dividend = dividend - divisor;
          }
      } else if (dividend > 0 && divisor < 0) {
          while (dividend + divisor>=0) {
              result++;
              dividend = dividend + divisor;
          }
          result = -result;
      }else if (dividend < 0 && divisor < 0) {
          //边界溢出发生在 -2^31 / -1 的时候
          if (dividend== Integer.MIN_VALUE&&divisor==-1) {
              return Integer.MAX_VALUE;
          }
          while (dividend - divisor<=0) {
              result++;
              dividend = dividend - divisor;
          }
      }else if (dividend < 0 && divisor > 0) {
          while (dividend + divisor<=0) {
              result++;
              dividend = dividend + divisor;
          }
          result = -result;
      }
      return result;
  }
  

  • 后续优化太难处理，决定将int转为lon型，修复边界问题，方便对算法统一

package sj.shimmer.algorithm.ten_2;

import sj.shimmer.algorithm.Utils;

/**
 * Created by SJ on 2021/2/12.
 */

class D19 {
    public static void main(String[] args) {
        Utils.logTime();
        System.out.println(divide(-2147483648, -3));
        Utils.logTime();
//        System.out.println(divide(-1,-1));
//        System.out.println(divide(10,3));
//        System.out.println(divide(7,-3));
    }

    public static int divide(int dividend, int divisor) {
        if (divisor == 0) {
            return 0;
        }
        if (divisor == 1) {
            return dividend;
        }
        if (divisor == -1) {
            //边界溢出发生在 -2^31 / -1 的时候
            if (dividend == Integer.MIN_VALUE) {
                return Integer.MAX_VALUE;
            }
            return -dividend;
        }
        long dd = dividend;
        long dr = divisor;

        if (dividend > 0 && divisor > 0) {
            return get(dd, dr);
        } else if (dividend < 0 && divisor < 0) {
            return get(-dd, -dr);
        } else if (dividend > 0 && divisor < 0) {
            return -get(dd, -dr);
        } else if (dividend < 0 && divisor > 0) {
            return -get(-dd, dr);
        }
        return 0;
    }

    private static int get(long dd, long dr) {
        if (dd<dr) {
            return 0;
        }
        int result = 1;
        long temp = dr;
        while (dd > dr+dr) {
            dr+=dr;
            result+=result;
        }

        return result+get(dd-dr,temp);
    }
}

参考解

https://leetcode-cn.com/problems/divide-two-integers/solution/

1. 倍增解决优化查找
2. long型解决边界溢出