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
🌟 每日一练刷题专栏 🌟
✨持续,努力奋斗做强刷题搬运工!
👍 点赞,你的认可是我坚持的动力!
🌟 收藏,你的青睐是我努力的方向!
✎ 评论,你的意见是我进步的财富!
☸ 主页:https://hannyang.blog.csdn.net/