a = 21 (10101) b = 11 (01011) c = ~a = -22 (01010) d = a | b = 31 (11111) e = a ^ b = 30 (11110) f = a & b = 1 (00001) 1 << 4 = 16 (10000) 16 << 2 = 4 (00100)
位运算的经典操作
简单的集合部分
1 2 3 4 5 6 7
A |=1 << C # 在集合 A 中加入 C A &= ~(1 << C) # 在集合 A 中删除 C A = 1 << C; # 相当于 A = 2 ** C a & (-a) # lowbit 操作:获得某数的最后一位为 1 的数字 A = 0# 将 A 置空 All = (1 << 15) - 1; # 将 All 置满 (A & B) == B # B 是否为 A 的子集
classSolution: defminNumberOfSemesters(self, n: int, dependencies, k: int) -> int: # 遍历 + 剪枝 global res depend = [0for _ inrange(n)] root = [[] for _ inrange(n)] ways = {} res = 16
for a, b in dependencies: root[a-1].append(b-1) depend[b-1] += 1
defbacktrack(choice,step,k,n):
global res ifmax(choice) == -1: res = min(res,step) return0 step += 1 tempnum = 0 is0 = [] for i inrange(len(choice)): if choice[i] == 0: tempnum += 1 is0.append(i)
help = sum(2 ** i for i in is0) ifhelpin ways and ways[help] <= step: #pass return0 else: ways[help] = step
if tempnum <= k: for i in is0:
choice[i] -= 1 for j in root[i]: choice[j] -= 1 backtrack(choice,step,k,n) else: for temp2 in combinations(is0,k): temp3 = copy.deepcopy(choice) for i in temp2: temp3[i] -= 1 for j in root[i]: temp3[j] -= 1 backtrack(temp3,step,k,n)