不使用乘法、除法和 mod 运算符，返回两数相除的整数部分，如 10/3 返回 3。题目描述
给定两个整数，被除数 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 位有符号整数，其数值范围是 [−2^31, 2^31 − 1]。本题中，如果除法结果溢出，则返回 2^31 − 1。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/divide-two-integers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。思路：二分查找
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
""""""
INT_MIN, INT_MAX = -2 ** 31, 2 ** 31 - 1
# 按照题目要求，只有一种情况会溢出
if dividend == INT_MIN and divisor == -1:
return INT_MAX
sign = (dividend > 0 and divisor > 0) or (dividend < 0 and divisor < 0)
# 核心操作
def div(a, b):
if a < b:
return 0
cnt = 1
tb = b
while (tb + tb) <= a:
cnt += cnt
tb += tb
return cnt + div(a - tb, b)
ret = div(abs(dividend), abs(divisor))
return ret if sign else -ret核心操作说明，以 60 / 8 为例：
第一轮 div(60, 8): 8 -> 32 时停止，因为 32 + 32 > 60，返回 4
第二轮 div(28, 8): 8 -> 16 时停止，因为 16 + 16 > 28，返回 2
第三轮 div(8, 8): 8 -> 8 时停止，因为 8 + 8 > 8，返回 1
第三轮 div(0, 8): 因为 0 < 8，返回 0
因此结果为 1 + 2 + 4 = 7
找出由 ATCG 构成的字符串中所有重复且长度为 10 的子串；- 基本思路：哈希表计数；
- 如果直接使用子串本身作为哈希表的 key，那么时间复杂度和空间复杂度都是
O(NL)；而如果使用位运算+滑动窗口手动构造 key，可以把复杂度降为O(N)；
题目描述
所有 DNA 都由一系列缩写为 'A'，'C'，'G' 和 'T' 的核苷酸组成，例如："ACGAATTCCG"。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。
编写一个函数来找出所有目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。
示例 1：
输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC","CCCCCAAAAA"]
示例 2：
输入：s = "AAAAAAAAAAAAA"
输出：["AAAAAAAAAA"]
提示：
0 <= s.length <= 10^5
s[i] 为 'A'、'C'、'G' 或 'T'
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/repeated-dna-sequences
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。子串作为 key
- 时间&空间复杂度：
O(NL)；
class Solution:
def findRepeatedDnaSequences(self, s: str) -> List[str]:
""""""
# from collections import defaultdict
L = 10
cnt = defaultdict(int)
ans = []
for i in range(len(s) - L + 1):
subs = s[i: i+L]
cnt[subs] += 1
if cnt[subs] == 2:
ans.append(subs)
return ans位运算+滑动窗口
- 时间&空间复杂度：
O(N)；
class Solution:
def findRepeatedDnaSequences(self, s: str) -> List[str]:
""""""
# from collections import defaultdict
L = 10
B = {'A': 0, 'T': 1, 'C': 2, 'G': 3} # 分别为 00, 01, 10, 11
if len(s) < L + 1: # assert，否则部分用例会无法通过
return []
# 先计算前 9 位的值
x = 0
for i in range(L - 1):
b = B[s[i]]
x = (x << 2) | b
ans = []
cnt = defaultdict(int)
for i in range(len(s) - L + 1):
b = B[s[i + L - 1]]
# 注意该有的括号不要少，避免运算优先级混乱
x = ((x << 2) | b) & ((1 << (L * 2)) - 1) # 滑动计算子串的 hash 值
cnt[x] += 1
if cnt[x] == 2:
ans.append(s[i: i + L])
return ans位运算说明
(x << 2) | b：# 以为均为二进制表示 设 x = 0010 1011, b = 10: 该运算相当于把 b “拼” 到 x 末尾 x : 0010 1011 x = x << 2: 1010 1100 x = x | b : 1010 1100 | 0000 0010 ----------- 1010 1110
x & ((1 << (L * 2)) - 1)# 该运算把 x 除低 10 位前的所有位置置 0 设 L = 5，x = 1110 1010 1010: y = 1 << (L * 2): 0100 0000 0000 y = y - 1 : 0011 1111 1111 x = x & y : 1110 1010 1010 & 0011 1111 1111 ---------------- 0010 1010 1010