1. 两数相除
给定两个整数，被除数 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。
出处：
https://edu.csdn.net/practice/25023633
代码：
import math class Solution(object): def divide(self, dividend, divisor): if divisor == 0: return MAX_INT if dividend == 0: return 0 isPositive = (dividend < 0) == (divisor < 0) m = abs(dividend) n = abs(divisor) res = math.log(m) - math.log(n) res = int(math.exp(res)) if isPositive: return min(res, 2147483647) return max(0 - res, -2147483648) if __name__ == '__main__': s = Solution() print(s.divide(10, 3)) print(s.divide(7, -3))
输出：
3
-2
2. 分割回文串
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a"
输出：[["a"]]
提示：
1 <= s.length <= 16
s 仅由小写英文字母组成
出处：
https://edu.csdn.net/practice/25023634
代码：
import math class Solution(object): def partition(self, s): """ :type s: str :rtype: List[List[str]] """ if len(s) == 0: return [] else: res = [] self.dividedAndsel(s, [], res) return res def dividedAndsel(self, s, tmp, res): if len(s) == 0: res.append(tmp) for i in range(1, len(s) + 1): if s[:i] == s[:i][::-1]: self.dividedAndsel(s[i:], tmp + [s[:i]], res) if __name__ == '__main__': s = Solution() print(s.partition("aab")) print(s.partition("a"))
输出：
[['a', 'a', 'b'], ['aa', 'b']]
[['a']]
3. x 的平方根
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
出处：
https://edu.csdn.net/practice/25023635
代码：
class Solution: def mySqrt(self, x): if x < 0: return 0 if x < 4: return 1 res = 2 * self.mySqrt(x / 4) if 0 <= (res + 1) * (res + 1) <= x: return res + 1 return res # %% s = Solution() print(s.mySqrt(4)) print(s.mySqrt(8))
输出：
2
2
二分法：
class Solution: def mySqrt(self, x): left, right = 0, x res = -1 while left <= right: mid = (left + right)//2 tmp = mid * mid if tmp <= x: res = mid left = mid + 1 else: right = mid - 1 return res
