大同网络公司,网络优化是什么专业,如何查看网站名称,创意设计绘画作品【问题描述】[中等]
给定两个整数#xff0c;被除数 dividend 和除数 divisor。将两数相除#xff0c;要求不使用乘法、除法和 mod 运算符。返回被除数 dividend 除以除数 divisor 得到的商。整数除法的结果应当截去#xff08;truncate#xff09;其小数部分#xff0c;…【问题描述】[中等]
给定两个整数被除数 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
【解答思路】 1. 暴力超时
时间复杂度O(N) 空间复杂度O(1)
public int divide(int dividend, int divisor) {if(dividendInteger.MIN_VALUEdivisor-1)return Integer.MAX_VALUE;boolean k(dividend0divisor0)||(dividend0divisor0);int result0;dividend-Math.abs(dividend);divisor-Math.abs(divisor);while(dividenddivisor) {dividend-divisor;result1;}return k?result:-result;}
2. 二分法优化 时间复杂度O(logN) 空间复杂度O(1)
public int divide(int dividend, int divisor) {if(dividendInteger.MIN_VALUEdivisor-1)return Integer.MAX_VALUE;boolean k(dividend0divisor0)||(dividend0divisor0);int result0;dividend-Math.abs(dividend);divisor-Math.abs(divisor);while(dividenddivisor) {int tempdivisor;int c1;while(dividend-temptemp) {temptemp1;cc1;}dividend-temp;resultc;}return k?result:-result;}
【总结】
1.正数统一转化为负数 边界思考量相对较小
2.可用二分法对暴力法进行优化
3.符号问题 脑子要清醒
转载https://leetcode-cn.com/problems/divide-two-integers/solution/yong-fu-shu-yun-suan-jian-hua-bian-jie-chu-li-by-g/
