3无重复字符的最长子串
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
max_l = 0
l = 0
temp = ''
for i in s:
if i in temp:
temp = temp[temp.index(i) + 1:]
l = len(temp)
l = l + 1
max_l = max(l, max_l)
temp = temp + i
return max_l
7整数反转
class Solution:
def reverse(self, x: int) -> int:
if x == 0:
return 0
x = str(x)
prefix = ''
if x[0] == '-':
prefix = '-'
x = x[1:]
temp = ''
for i in range(len(x) - 1, -1, -1):
temp = temp + x[i]
temp = temp.lstrip('0')
res = int(prefix + temp)
if res >= 2147483647 or res <= -2147483648:
return 0
return res
8字符串转换整数(atoi)
class Solution:
def myAtoi(self, s: str) -> int:
s = s.lstrip()
if len(s) == 0:
return 0
temp = ''
nums = '0123456789'
if s[0] in ['+', '-']:
temp = s[0]
s = s[1:]
for i in range(len(s)):
if s[i] not in nums:
break
temp = temp + s[i]
if temp == '' or temp == '-' or temp == '+':
return 0
temp = int(temp)
if temp <= -2147483648:
temp = -2147483648
elif temp >= 2147483647:
temp = 2147483647
return temp
11盛最多水的容器
class Solution:
def maxArea(self, height: list) -> int:
if len(height) < 2:
return 0
left = 0
right = len(height) - 1
res = 0
while True:
w = right - left
h = min(height[left], height[right])
res = max(res, w * h)
if height[left] > height[right]:
right = right - 1
else:
left = left + 1
if left == right:
break
return res
14最长公共前缀
class Solution:
def longestCommonPrefix(self, strs: list[str]) -> str:
m1 = max(strs)
m2 = min(strs)
if m1 == m2:
return m2
l1 = len(m1)
l2 = len(m2)
l = l1 if l1 < l2 else l2
for i in range(l):
if m1[i] != m2[i]:
return m2[0:i]
return m2
35搜索插入位置
class Solution:
def searchInsert(self, nums: list[int], target: int) -> int:
left = 0
right = len(nums) - 1
while left < right:
if target > nums[right]:
return right + 1
elif target < nums[left]:
return left
mid = (right + left) // 2
if nums[mid] > target:
right = mid
elif nums[mid] < target:
left = mid + 1
else:
return mid
return left if nums[left] >= target else left + 1
45跳跃游戏II
class Solution:
def jump(self, nums: list[int]) -> int:
endPoint = len(nums) - 1
position = 0
step = 0
while position < endPoint:
temp = 0
step = step + 1
r = range(position + 1, nums[position] + position + 1)
for i in r:
if i >= endPoint:
return step
if nums[i] + i >= temp:
temp = nums[i] + i
position = i
return step
48旋转图像
class Solution:
def rotate(self, matrix: list[list[int]]) -> None:
l = len(matrix)
# 每次交换4个位置
# 当长度为偶数时，交换l^2/4次，等于(l/2)*(l/2)次，l//2==(l+1)//2（偶数和偶数+1的地板除结果一样）
# 当长度为奇数时，中间点不交换，交换(l^2-1)/4次，等于((l+1)/2) * ((l-1)/2)，(l+1)//2==(l+1)/2、l//2==(l-1)/2
for i in range(l // 2):
for j in range((l + 1) // 2):
temp = matrix[i][j]
matrix[i][j] = matrix[l - 1 - j][i]
matrix[l - 1 - j][i] = matrix[l - 1 - i][l - 1 - j]
matrix[l - 1 - i][l - 1 - j] = matrix[j][l - 1 - i]
matrix[j][l - 1 - i] = temp
102二叉树的层序遍历
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def levelOrder(self, root: TreeNode) -> list[list[int]]:
res = dict()
if root is None or root.val is None:
return []
res[0] = [root.val]
self._levelOrder(root, res, 1)
return [v for k, v in res.items()]
def _levelOrder(self, root: TreeNode, res, level):
if root.left is not None and root.right is not None:
if level not in res:
res[level] = [root.left.val, root.right.val]
else:
res[level].append(root.left.val)
res[level].append(root.right.val)
self._levelOrder(root.left, res, level + 1)
self._levelOrder(root.right, res, level + 1)
elif root.left is not None:
if level not in res:
res[level] = [root.left.val]
else:
res[level].append(root.left.val)
self._levelOrder(root.left, res, level + 1)
elif root.right is not None:
if level not in res:
res[level] = [root.right.val]
else:
res[level].append(root.right.val)
self._levelOrder(root.right, res, level + 1)
136只出现一次的数字
你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？
class Solution:
def singleNumber(self, nums: list[int]) -> int:
res = 0
for i in nums:
# n 异或 n == 0
res = res ^ i
return res
137只出现一次的数字II
class Solution:
def singleNumber(self, nums: list[int]) -> int:
d = dict()
c = 3
for i in nums:
if i not in d:
d[i] = 1
else:
if d[i] + 1 >= c:
d.pop(i)
else:
d[i] = d[i] + 1
return d.popitem()[0]
148排序链表
2591将钱分给最多的儿童
class Solution:
def distMoney(self, money, children):
# 钱少于人数，必有人分不到钱，返回-1
if money < children:
return -1
# 钱=8*人数，全部分到8元
elif 8 * children == money:
return children
# 钱>8*人数，n-1人分到8元，剩下一人分到8+元
elif 8 * children < money:
return children - 1
# 钱=(n-1)*8+4，n-2人分到8元，剩下2人分掉12元（不能4+8）
elif (children - 1) * 8 + 4 == money:
return children - 2
else:
# 设x人分到8元，但是要保证剩下的人都能分到钱：money-8x >= children-x
# 调整后得：x <= (money-children)/7
return (money - children) // 7
460LFU缓存
from collections import defaultdict
from typing import Optional
class Node:
__slots__ = ('prev', 'next', 'key', 'value', 'freq')
def __init__(self, key=0, val=0):
self.key = key
self.value = val
self.freq = 1
class LFUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.data_map = dict()
# 哨兵节点
def new_list() -> Node:
dummy = Node()
dummy.prev = dummy
dummy.next = dummy
return dummy
self.freq_map = defaultdict(new_list)
def get(self, key: int) -> int:
node = self._get_node(key)
return node.value if node else -1
def put(self, key: int, value: int) -> None:
node = self._get_node(key)
# 已存在
if node:
node.value = value
else:
# 超过字典长度限制
if len(self.data_map) >= self.capacity:
dummy = self.freq_map[self.min_freq]
# 找到最低频率最后加入的节点并删除它（哨兵节点的上一个，其实就是最后一个）
back_node = dummy.prev
del self.data_map[back_node.key]
self._remove(back_node)
# 清空一下，节省一点点内存
if dummy.prev == dummy:
del self.freq_map[self.min_freq]
# 把key放入字典
self.data_map[key] = node = Node(key, value)
# 设置key对应的使用频率
self._push_front(self.freq_map[1], node)
self.min_freq = 1
return None
def _get_node(self, key: int) -> Optional[Node]:
# key不存在，直接返回
if key not in self.data_map:
return None
node = self.data_map[key]
# 把节点从当前使用频率上面移除
self._remove(node)
dummy = self.freq_map[node.freq]
# 如果当前使用频率没有节点了，清空列表
if dummy.prev == dummy:
del self.freq_map[node.freq]
# 将最小频率往上移动一格
if self.min_freq == node.freq:
self.min_freq += 1
# 把节点往更高的使用频率上移动
node.freq += 1
# 放在更高频率的最前面（最晚移除）
self._push_front(self.freq_map[node.freq], node)
return node
# 删除一个节点
def _remove(self, x: Node) -> None:
x.prev.next = x.next
x.next.prev = x.prev
# 在链表头添加一个节点
def _push_front(self, dummy: Node, x: Node) -> None:
x.prev = dummy
x.next = dummy.next
x.prev.next = x
x.next.prev = x
2582递枕头
class Solution:
# 到达端点需要n-1时间
def passThePillow(self, n: int, time: int) -> int:
l_r = (time // (n - 1)) % 2
# 奇数，右往左
if l_r == 1:
return n - time % (n - 1)
else: # 偶数，左往右
return 1 + time % (n - 1)
1333餐厅过滤器
利用bisect
import bisect
class Solution:
def filterRestaurants(self, restaurants, veganFriendly: int, maxPrice: int, maxDistance: int):
res = []
for id, rating, veganFriendly1, price, distance in restaurants:
if ((
veganFriendly == 1 and veganFriendly1 == 1) or veganFriendly == 0) and price <= maxPrice and distance <= maxDistance:
# 1.题目已知id最大为10000 2.bisect.insort默认升序，转成负数
bisect.insort(res, rating * -100000 - id)
return [x % -100000 * -1 for x in res]
先过滤，再排序，然后剔除rating
class Solution:
def filterRestaurants(self, restaurants, veganFriendly: int, maxPrice: int, maxDistance: int):
res = []
for id, rating, veganFriendly1, price, distance in restaurants:
if ((
veganFriendly == 1 and veganFriendly1 == 1) or veganFriendly == 0) and price <= maxPrice and distance <= maxDistance:
res.append([id, rating])
res.sort(key=lambda x: [x[1], x[0]], reverse=True)
return [x[0] for x in res]
2251花期内花的数目
from typing import List
import bisect
# 第n天去看，花的数量= (开始时间<=n的数量) - (结束时间<n的数量)
class Solution:
def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:
starts = sorted(s for s, _ in flowers)
ends = sorted(e for _, e in flowers)
# 因为排序了，索引可以用来表示数量
# 最右边的插入位索引(开始时间<=n的数量) - 最左边的插入位索引 (结束时间<n的数量)
return [bisect.bisect_right(starts, p) - bisect.bisect_left(ends, p) for p in people]
差分数组
对于数组a，定义其差分数组（difference array）为
性质1：从左到右累加d中的元素，可以得到数组a
性质2：如下两个操作是等价的
- 区间操作：把a的子数组a[i],a[i+1],...,a[j]都加上x
- 单点操作：把d[i]增加x；如果j+1小于a的长度，把d[j+1]减少x
from typing import List
# 你有一个长为 n 的数组 a，一开始所有元素均为 0。
# 给定一些区间操作，其中 queries[i] = [left, right, x]，
# 你需要把子数组 a[left], a[left+1], ... a[right] 都加上 x。
# 返回所有操作执行完后的数组 a。
def solve(n: int, queries: List[List[int]]) -> List[int]:
diff = [0] * n # 差分数组
for left, right, x in queries:
diff[left] += x
if right + 1 < n:
diff[right + 1] -= x
for i in range(1, n):
diff[i] += diff[i - 1] # 直接在差分数组上复原数组 a
return diff
queries = [[1, 3, 2], [6, 6, 6]]
print(solve(7, queries))
605种花问题
题解1
from typing import List
class Solution:
def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
l = len(flowerbed)
c = 0
if l == 1:
c = 1 if flowerbed[0] == 0 else 0
return True if c >= n else False
# 可以在flowerbed左右各拼一个[0]来简化判断逻辑，但是会有额外的内存消耗
# 题解2的那种判断方式更好
for i in range(l):
if i == 0:
if flowerbed[i] == 0 and flowerbed[i + 1] == 0:
flowerbed[i] = 1
c += 1
elif i == l - 1:
if flowerbed[i] == 0 and flowerbed[i - 1] == 0:
flowerbed[i] = 1
c += 1
else:
if flowerbed[i] == 0 and flowerbed[i + 1] == 0 and flowerbed[i - 1] == 0:
flowerbed[i] = 1
c += 1
if c >= n:
return True
return False
题解2
from typing import List
class Solution:
def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
# n == 0的情况在头部判断，这样循环中的return True的判断可以提到if内
if n == 0:
return True
i = 0
l = len(flowerbed)
while i < l:
# i直接+2，不要赋值1，稍微省一点损耗
if (i == 0 or flowerbed[i - 1] == 0) and flowerbed[i] == 0 and (i == l - 1 or flowerbed[i + 1] == 0):
if n <= 1:
return True
n -= 1
i += 2
else:
i += 1
return False
2136全部开花的最早一天
from typing import List
class Solution:
def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:
ans = days = 0
# 根据生长天数降序，尽最大可能在生长的日子同时播种
for p, g in sorted(zip(plantTime, growTime), key=lambda z: -z[1]):
# 累加播种天数
days += p
# 更新全部开花的天数（至少要保证所有花开，所以取max）
ans = max(ans, days + g)
return ans
121买卖股票的最佳时机
只能买卖一次，遍历prices，prices[i] - min_price即可
from typing import List
class Solution:
def maxProfit(self, prices: List[int]) -> int:
res = 0
min_price = prices[0]
for i in prices:
res = max(i-min_price, res)
min_price = min(i, min_price)
return res
122买卖股票的最佳时机II
from typing import List
class Solution:
def maxProfit(self, prices: List[int]) -> int:
res = 0
for i in range(len(prices)-1):
if prices[i+1] > prices[i]:
res += prices[i+1]-prices[i]
return res
123买卖股票的最佳时机III
from typing import List
import math
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# 没有开盘前就持有了股票，是非法的，初始化为负无穷大
buy1 = buy2 = -math.inf
# 没有开盘前没有持有股票，初始化为0
sell1 = sell2 = 0
for p in prices:
# 第2次卖出和第2次买入+当前利润的最大值
sell2 = max(sell2, buy2+p)
# 第2次买入和第一次卖出-当前买入后的最大值
buy2 = max(buy2, sell1 - p)
# 第1次卖出和第1次买入+当前利润的最大值
sell1 = max(sell1, buy1+p)
# 第1次买入和第0次卖出-当前买入后的最大值
buy1 = max(buy1, -p)
return sell2
188买卖股票的最佳时机IV
from typing import List
import math
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
l = len(prices)
# 初始化dp数组，默认全为负无穷，防止数组越界，全部+1
# 因为最多k次（包含k），所以本来就是range(k+1)，所以k要再+1
# 第三维：0表示未持有股票，1表示持有股票
mp = [[[-math.inf]*2 for _ in range(k+2)] for _ in range(l+1)]
# 初始化第0天的未持股的情况全为0，j>=1
for j in range(1, k+2):
mp[0][j][0] = 0
for i, p in enumerate(prices):
for j in range(1, k+2):
mp[i+1][j][0] = max(mp[i][j][0], mp[i][j][1] + p)
mp[i+1][j][1] = max(mp[i][j][1], mp[i][j-1][0]-p)
return mp[l][k+1][0]
状态压缩，优化空间复杂度
from typing import List
import math
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
mp = [[-math.inf]*2 for _ in range(k+2)]
for j in range(1, k+2):
mp[j][0] = 0
for p in prices:
for j in range(k+1, 0, -1):
mp[j][1] = max(mp[j][1], mp[j-1][0]-p)
mp[j][0] = max(mp[j][0], mp[j][1] + p)
return mp[k+1][0]
309买卖股票的最佳时机含冷冻期
因为含冷冻期，所以当i>0买入时，需要往前再推一轮
from typing import List
import math
class Solution:
def maxProfit(self, prices: List[int]) -> int:
l = len(prices)
mp = [[-math.inf]*2 for _ in range(l+1)]
mp[0][0] = 0
for i, p in enumerate(prices):
mp[i+1][0] = max(mp[i][0], mp[i][1] + p)
if i > 0:
mp[i+1][1] = max(mp[i][1], mp[i-1][0] - p)
else:
mp[i+1][1] = max(mp[i][1], mp[i][0] - p)
return mp[l][0]
714买卖股票的最佳时机含手续费
因为含有手续费，所以还是要用动态规划，不能像122那样用贪心算法了
from typing import List
from math import inf
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
n = len(prices)
f = [[-inf]*2 for _ in range(n+1)]
f[0][0] = 0
for i, p in enumerate(prices):
f[i+1][0] = max(f[i][0], f[i][1]+p-fee)
f[i+1][1] = max(f[i][1], f[i][0]-p)
return f[n][0]
空间优化
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
f0, f1 = 0, -inf
for p in prices:
f0, f1 = max(f0, f1 + p - fee), max(f1, f0 - p)
return f0
901股票价格跨度
from math import inf
class StockSpanner:
def __init__(self):
# 初始化值，简化判断
self.spanner = [(-1, inf)]
self.current = -1
def next(self, price: int) -> int:
# 只要比当前价格低的，全部pop掉
while price >= self.spanner[-1][1]:
self.spanner.pop()
self.current += 1
self.spanner.append((self.current, price))
# 因为比当前价格低的全部pop掉了，所以只要当前-上一个即可
return self.current - self.spanner[-2][0]
2034股票价格波动
from bisect import insort, bisect_right
class StockPrice:
def __init__(self):
self.t = {}
self.p = []
self.cur = [-1, -1]
def update(self, timestamp: int, price: int) -> None:
# 维护一个有序数组，如果时间已存在，剔除掉
if timestamp in self.t:
del self.p[bisect_right(self.p, self.t[timestamp]) - 1]
# 更新时间对应的价格
self.t[timestamp] = price
insort(self.p, price)
# 更新最新价
if timestamp >= self.cur[0]:
self.cur = [timestamp, price]
return None
def current(self) -> int:
return self.cur[1]
def maximum(self) -> int:
return self.p[-1]
def minimum(self) -> int:
return self.p[0]
使用SortedList，删除元素的时候比bisect要快些
from sortedcontainers import SortedList
class StockPrice:
def __init__(self):
self.t = {}
self.p = SortedList()
self.max_time = -1
def update(self, timestamp: int, price: int) -> None:
if timestamp in self.t:
self.p.remove(self.t[timestamp])
self.t[timestamp] = price
self.p.add(price)
if timestamp > self.max_time:
self.max_time = timestamp
return None
def current(self) -> int:
return self.t[self.max_time]
def maximum(self) -> int:
return self.p[-1]
def minimum(self) -> int:
return self.p[0]
2578最小和分割
class Solution:
def splitNum(self, num: int) -> int:
a = b = ''
num = sorted(str(num))
for i, v in enumerate(num):
if i % 2 == 1:
a += v
else:
b += v
return int(a) + int(b)
更优雅的写法
class Solution:
def splitNum(self, num: int) -> int:
s = sorted(str(num))
return int(''.join(s[::2])) + int(''.join(s[1::2]))
2731移动机器人
from typing import List
class Solution:
def sumDistance(self, nums: List[int], s: str, d: int) -> int:
# 题目描述机器人无差别，所以可以无视碰撞，直接穿透过去就行了
for i, c in enumerate(s):
nums[i] += d if c == 'R' else -d
# 题目要的答案是距离的累加和，所以可以无视顺序
# 排序后更便于累加所有距离
nums.sort()
ans = s = 0
# 把nums[i]提取出来，nums[0...i-1]累加
for i, x in enumerate(nums):
ans += i * x - s
s += x
return ans % (10 ** 9 + 7)
2512奖励最顶尖的K名学生
from typing import List
class Solution:
def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str],
student_id: List[int], k: int) -> List[int]:
# 反馈列表转成字典，便于匹配评价
positive_feedback = dict(zip(positive_feedback, [1] * len(positive_feedback)))
negative_feedback = dict(zip(negative_feedback, [1] * len(negative_feedback)))
res = []
for i in range(len(student_id)):
score = 0
# 根据题目描述，直接用" "拆分
for rp in report[i].split(" "):
if rp in positive_feedback:
score += 3
if rp in negative_feedback:
score -= 1
res.append((student_id[i], score))
# 排序分数、ID
res.sort(key=lambda x: [x[1], -x[0]], reverse=True)
return [x[0] for x in res[:k]]
更优雅的实现方式
from typing import List
from collections import defaultdict
class Solution:
def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str],
student_id: List[int], k: int) -> List[int]:
# 正负合并成一个字典
score = defaultdict(int)
for w in positive_feedback: score[w] = 3
for w in negative_feedback: score[w] = -1
a = sorted((-sum(score[w] for w in r.split()), i) for r, i in zip(report, student_id))
return [i for _, i in a[:k]]
2562找出数组的串联值
from typing import List
class Solution:
def findTheArrayConcVal(self, nums: List[int]) -> int:
left = 0
right = len(nums) - 1
res = 0
while left <= right:
if left == right:
res += nums[left]
break
res += int(str(nums[left]) + str(nums[right]))
left += 1
right -= 1
return res
不进行字符串转换，通过数学计算方式累加
from typing import List
class Solution:
def findTheArrayConcVal(self, nums: List[int]) -> int:
ans = 0
i = 0
j = len(nums) - 1
while i < j:
x = nums[i]
y = nums[j]
# 通过y不断除10，来知道x需要乘以10的几次方
while y:
x *= 10
y //= 10
ans += x + nums[j]
i += 1
j -= 1
# 相等的情况移到循环外面
if i == j:
ans += nums[i]
return ans
1488避免洪水泛滥
from typing import List
from collections import defaultdict
from bisect import bisect_right
class Solution:
def avoidFlood(self, rains: List[int]) -> List[int]:
res = [-1] * len(rains)
def return_value():
return -1
temp = defaultdict(return_value)
zero = []
for i, v in enumerate(rains):
if v != 0:
# 当前湖泊有水并且可以抽水（0的索引大于当前湖泊之前下雨的索引）
if len(zero) > 0 and temp[v] > -1 and zero[-1] > temp[v]:
# 找到最小满足的0，使用它抽干湖泊
zero_index = bisect_right(zero, temp[v])
res[zero[zero_index]] = v
zero.pop(zero_index)
temp[v] = -1
# 连续2次下雨在某个湖泊，中间没有满足的0进行抽干，返回[]
if temp[v] > -1:
return []
temp[v] = i
else:
zero.append(i)
# 把剩余的0全填为1，不然提交会失败
for i in zero:
res[i] = 1
return res
更优雅的实现方式
from typing import List
from sortedcontainers import SortedList
class Solution:
def avoidFlood(self, rains: List[int]) -> List[int]:
n = len(rains)
ans = [-1] * n
sunny = SortedList()
rainy = {}
for i, v in enumerate(rains):
if v:
if v in rainy:
idx = sunny.bisect_right(rainy[v])
if idx == len(sunny):
return []
ans[sunny[idx]] = v
sunny.discard(sunny[idx])
rainy[v] = i
else:
sunny.add(i)
ans[i] = 1
return ans
136只出现一次的数字
根据约束条件，以及空间复杂度要求，本题可以用异或计算
class Solution:
def singleNumber(self, nums: List[int]) -> int:
res = nums[0]
for i in range(1, len(nums)):
res ^= nums[i]
return res
137只出现一次的数字II
from typing import List
class Solution:
def singleNumber(self, nums: List[int]) -> int:
'''
异或本质上就是先相加再%2，也可以叫模2加法（把一个bit不断地异或1，相当于在0和1之间不断转换）
nums = [6,6,3]
110
110
011 +
-----
231 %2
-----
011 -> res = 3
同理：本题就是先相加再%3，也可以叫模3加法（相当于在0,1,2之间不断转换）
nums = [6,6,6,3]
110
110
110
011 +
-----
341 %3
-----
011 -> res = 3
由于0,1,2需要2个比特位才能表示，设这2个比特分别为：a和b
a=0,b=0表示0
a=0,b=1表示1
a=1,b=1表示2
那么转换规则是：(0,0)->(0,1)->(1,0)->(0,0)...
# (0,0)、(0,1)
if a == 0:
if x == 0: # 输入0，状态不变
b = b
else: # 输入1，状态变化
b = ~b
else: # (1,0)
b = 0 # 当a等于1时，b永远等于0
引入异或运算，PS： n ^ 0 = n, n ^ 1 = ~n
if a == 0:
b = b ^ x # x等于0保持不变，x等于1取反
else:
b = 0
引入与运算，PS： n & 0 = 0, n & 1 = n
b = ~a & b ^ x # a取反后等于1，走异或逻辑;a取反后等于0和任意数与预算结果还是为0
b计算好后，基于b再计算a（此时b等于1，状态为：(0, 1)）
a = ~b & a ^ x # b取反后等于1，走异或逻辑;b取反后等于0和任意数与预算结果还是为0
'''
a = b = 0
for x in nums:
b = (b ^ x) & ~a
a = (a ^ x) & ~b
return b
260只出现一次的数字III
from typing import List
'''
nums = [1,2,1,3,2,5]
先进行一次全员异或，那么相同的都会消除，结果为：3^5=6
因为这2个数都只出现一次，即：3 != 5
所以结果值6，必定有一位为1，3和5在这个比特位上，必定有一个为1，另一个为0
110 -> 6
011 -> 3
101 -> 5
我们可以直接取最后一位1即可，6 & -6
再次遍历nums，把这个比特位上值为0的放一组，值为1的放一组，进行分组异或
那么3和5会被放到2组中，其他的相同的值要么和3一组，要么和5一组，不过最终都会被异或消除
返回每组的唯一值，即：3和5
'''
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
xor_all = nums[0]
for i in range(1, len(nums)):
xor_all ^= nums[i]
low_bit = xor_all & -xor_all
res = [0, 0]
for x in nums:
'''
if x & low_bit:
res[0] = res[0] ^ x
else:
res[1] = res[1] ^ x
'''
res[(x & low_bit) != 0] ^= x
return res
2652倍数求和
class Solution:
def sumOfMultiples(self, n: int) -> int:
def s(m:int) -> int:
# 等差数列求和公式
# SumAk = (a_1 + a_k) * k / 2
# k = n // m（有k项）, a_1 = m（首项）, a_k = mk（末项=首项*k）
return n // m * (n // m + 1) // 2 * m
# 容斥原理：公共的倍数只保留1份
return s(3) + s(5) + s(7) - s(15) - s(21) - s(35) + s(105)
2530执行K次操作后的最大分数
排序实现，较慢
from sortedcontainers import SortedList
class Solution:
def maxKelements(self, nums: List[int], k: int) -> int:
nums = SortedList(nums)
res = 0
for _ in range(k):
m = nums.pop()
res += m
nums.add(ceil(m / 3))
return res
堆实现，更优
from typing import List
from heapq import heapify, heapreplace
class Solution:
def maxKelements(self, nums: List[int], k: int) -> int:
for i in range(len(nums)):
# 小顶堆，所以转成负数
nums[i] = -nums[i]
# 原地堆化
heapify(nums)
ans = 0
for _ in range(k):
# 取出最小值，并替换
# 因为转成了负值，所以：累加->累减，向上取整->向下取整
ans -= heapreplace(nums, nums[0] // 3)
return ans
1726同积元祖
class Solution:
def tupleSameProduct(self, nums: List[int]) -> int:
d = defaultdict(int)
res = 0
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
p = nums[i] * nums[j]
d[p] += 1
if d[p] > 1:
res += (d[p] - 1) * 8
return res
2316统计无向图中无法互相到达点对数
1402做菜顺序
```
# 1155掷骰子等于目标和的方法数
[链接](https://leetcode.cn/problems/number-of-dice-rolls-with-target-sum/)
```python
2698求一个整数的惩罚数
python