Algorithm
本周选择的算法题是：Divide Two Integers。
规则
Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.
Return the quotient after dividing dividend by divisor.
The integer division should truncate toward zero, which means losing its fractional part. For example, truncate(8.345) = 8 and truncate(-2.7335) = -2.
Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For this problem, assume that your function returns 231 − 1 when the division result overflows.
Example 1:
Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = truncate(3.33333..) = 3.
Example 2:
Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = truncate(-2.33333..) = -2.
Example 3:
Input: dividend = 0, divisor = 1
Output: 0
Example 4:
Input: dividend = 1, divisor = 1
Output: 1
Constraints:
-231 <= dividend, divisor <= 231 - 1divisor != 0
Solution
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
if dividend == -2147483648 and divisor == -1: return 2147483647
ans, abs_dividend, abs_divisor = 0, abs(dividend), abs(divisor)
while abs_dividend >= abs_divisor:
temp, remainder = abs_divisor, 1
while temp << 1 <= abs_dividend:
temp <<= 1
remainder <<= 1
abs_dividend -= temp
ans += remainder
return ans if (dividend > 0) == (divisor > 0) else -ans
Review
将包形容成商店非常的形象，不仅介绍了用 __init__ 管理包的优点是什么，还有常见的三种组织方式：
- 以包作为所有功能的统一入口，对用户来说不用关心子模块，但容易有子模块间的冲突问题
- 仍然以包作为所有功能的统一入口，但选择性的暴露子模块中的功能，相比第一种，包管理者有更高的维护成本
- 将子模块暴露给用户，减少了冲突的概率，但用户需要关心自己所需的功能在哪个子模块中
这三种方式在流行的 Python 包中都有所应用，比如 numpy、matplotlib、pandas。
Tip
重温代码就近原则。