提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

算法leetcode｜29. 两数相除（rust重拳出击）

算法
2023-04-18 16:13:17 时间

文章目录

29. 两数相除：

给定两个整数，被除数 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。

分析：

  • 面对这道算法题目，二当家的陷入了沉思。
  • 不使用乘法、除法和 mod 运算符，所以只能模拟。
  • 乘法可以用加法模拟，除法可以用减法模拟。
  • 所以只是怎么能让加减法足够快的问题。

题解：

rust

impl Solution {
    pub fn divide(mut dividend: i32, mut divisor: i32) -> i32 {
        // 考虑被除数为最小值的情况
        if dividend == i32::MIN {
            if divisor == 1 {
                return i32::MIN;
            }
            if divisor == -1 {
                return i32::MAX;
            }
        }
        // 考虑除数为最小值的情况
        if divisor == i32::MIN {
            return if dividend == i32::MIN {
                1
            } else {
                0
            }
        }
        // 考虑被除数为 0 的情况
        if dividend == 0 {
            return 0;
        }

        // 一般情况，使用类二分查找
        // 将所有的正数取相反数，这样就只需要考虑一种情况
        let mut rev = false;
        if dividend > 0 {
            dividend = -dividend;
            rev = !rev;
        }
        if divisor > 0 {
            divisor = -divisor;
            rev = !rev;
        }

        let mut n = divisor;
        let mut power = 0;
        while n >= (dividend - n) {
            n <<= 1;
            power += 1;
        }
        let mut ans = 0;
        for i in (0..(power + 1)).rev() {
            if n >= dividend {
                ans += (1 << i);
                dividend -= n;
            }
            n >>= 1;
        }

        return if rev {
            -ans
        } else {
            ans
        }
    }
}

go

func divide(dividend int, divisor int) int {
    // 考虑被除数为最小值的情况
	if dividend == math.MinInt32 {
		if divisor == 1 {
			return math.MinInt32
		}
		if divisor == -1 {
			return math.MaxInt32
		}
	}
	// 考虑除数为最小值的情况
	if divisor == math.MinInt32 {
		if dividend == math.MinInt32 {
			return 1
		} else {
			return 0
		}
	}
	// 考虑被除数为 0 的情况
	if dividend == 0 {
		return 0
	}

	// 一般情况，使用类二分查找
	// 将所有的正数取相反数，这样就只需要考虑一种情况
	rev := false
	if dividend > 0 {
		dividend = -dividend
		rev = !rev
	}
	if divisor > 0 {
		divisor = -divisor
		rev = !rev
	}

	n := divisor
	power := 0
	for n >= (dividend - n) {
		n <<= 1
		power += 1
	}
	ans := 0
	for i := power; i >= 0; i-- {
		if n >= dividend {
			ans += 1 << i
			dividend -= n
		}
		n >>= 1
	}

	if rev {
		return -ans
	} else {
		return ans
	}
}

c++

class Solution {
public:
    int divide(int dividend, int divisor) {
        // 考虑被除数为最小值的情况
        if (dividend == INT_MIN) {
            if (divisor == 1) {
                return INT_MIN;
            }
            if (divisor == -1) {
                return INT_MAX;
            }
        }
        // 考虑除数为最小值的情况
        if (divisor == INT_MIN) {
            return dividend == INT_MIN ? 1 : 0;
        }
        // 考虑被除数为 0 的情况
        if (dividend == 0) {
            return 0;
        }

        // 一般情况，使用类二分查找
        // 将所有的正数取相反数，这样就只需要考虑一种情况
        bool rev = false;
        if (dividend > 0) {
            dividend = -dividend;
            rev = !rev;
        }
        if (divisor > 0) {
            divisor = -divisor;
            rev = !rev;
        }

        int n = divisor;
        int power = 0;
        while (n >= dividend - n) {
            n += n;
            ++power;
        }
        int ans = 0;
        for (int i = power; i >= 0; --i) {
            if (n >= dividend) {
                ans += (1 << i);
                dividend -= n;
            }
            n >>= 1;
        }

        return rev ? -ans : ans;
    }
};

c

int divide(int dividend, int divisor){
    // 考虑被除数为最小值的情况
    if (dividend == INT32_MIN) {
        if (divisor == 1) {
            return INT32_MIN;
        }
        if (divisor == -1) {
            return INT32_MAX;
        }
    }
    // 考虑除数为最小值的情况
    if (divisor == INT32_MIN) {
        return dividend == INT32_MIN ? 1 : 0;
    }
    // 考虑被除数为 0 的情况
    if (dividend == 0) {
        return 0;
    }

    // 一般情况，使用类二分查找
    // 将所有的正数取相反数，这样就只需要考虑一种情况
    bool rev = false;
    if (dividend > 0) {
        dividend = -dividend;
        rev = !rev;
    }
    if (divisor > 0) {
        divisor = -divisor;
        rev = !rev;
    }

    int n = divisor;
    int power = 0;
    while (n >= dividend - n) {
        n += n;
        ++power;
    }
    int ans = 0;
    for (int i = power; i >= 0; --i) {
        if (n >= dividend) {
            ans += (1 << i);
            dividend -= n;
        }
        n >>= 1;
    }

    return rev ? -ans : ans;
}

python

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        INT_MIN, INT_MAX = -2 ** 31, 2 ** 31 - 1
        # 考虑被除数为最小值的情况
        if dividend == INT_MIN:
            if divisor == 1:
                return INT_MIN
            if divisor == -1:
                return INT_MAX
        # 考虑除数为最小值的情况
        if divisor == INT_MIN:
            if dividend == INT_MIN:
                return 1
            else:
                return 0
        # 考虑被除数为0的情况
        if dividend == 0:
            return 0
        # 一般情况，使用类二分查找
        # 将所有的正数取相反数，这样就只需要考虑一种情况
        rev = False
        if dividend > 0:
            dividend = -dividend
            rev = not rev
        if divisor > 0:
            divisor = -divisor
            rev = not rev
        n = divisor
        power = 0
        while n >= (dividend - n):
            n <<= 1
            power += 1
        ans = 0
        for i in range(power, -1, -1):
            if n >= dividend:
                ans += (1 << i)
                dividend -= n
            n >>= 1
        if rev:
            return -ans
        else:
            return ans

java

class Solution {
    public int divide(int dividend, int divisor) {
        // 考虑被除数为最小值的情况
        if (dividend == Integer.MIN_VALUE) {
            if (divisor == 1) {
                return Integer.MIN_VALUE;
            }
            if (divisor == -1) {
                return Integer.MAX_VALUE;
            }
        }
        // 考虑除数为最小值的情况
        if (divisor == Integer.MIN_VALUE) {
            return dividend == Integer.MIN_VALUE ? 1 : 0;
        }
        // 考虑被除数为 0 的情况
        if (dividend == 0) {
            return 0;
        }

        // 一般情况，使用类二分查找
        // 将所有的正数取相反数，这样就只需要考虑一种情况
        boolean rev = false;
        if (dividend > 0) {
            dividend = -dividend;
            rev = !rev;
        }
        if (divisor > 0) {
            divisor = -divisor;
            rev = !rev;
        }

        int n     = divisor;
        int power = 0;
        while (n >= dividend - n) {
            n <<= 1;
            ++power;
        }
        int ans = 0;
        for (int i = power; i >= 0; --i) {
            if (n >= dividend) {
                ans += 1 << i;
                dividend -= n;
            }
            n >>= 1;
        }

        return rev ? -ans : ans;
    }
}

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~

相关文章