python 02 List

Python 1-14 列表

第一课

1437. 是否所有 1 都至少相隔 k 个元素

class Solution:def kLengthApart(self, nums: List[int], k: int) -> bool:cnt = k # 处理第一个 1for i, x in enumerate(nums):if x == 1:if cnt < k: return Falsecnt = 0 # 遇到 1 从新记数else: cnt += 1return True# left = -(k + 1) # 处理第一个 1# for i, x in enumerate(nums):#     if x == 1:#         if i - left <= k: return False#         left = i # 记录 1 的位置# return True

★997. 找到小镇的法官

有向图中节点的入度和出度的概念。在有向图中，一个节点的入度是指向该节点的边的数量；而一个节点的出度是从该节点出发的边的数量。

class Solution:def findJudge(self, n: int, trust: List[List[int]]) -> int:        if n == 1: return 1d = [0] * (n + 1) # 列表的元素全是 0，共 n + 1 元素。for a, b in trust:d[b] += 1 # 如果被信任加一d[a] -= 1 # 信任别人减一for i, x in enumerate(d):if x == n - 1: return i# if n - 1 in arr: return arr.index(n - 1)return -1

26. 删除有序数组中的重复项

class Solution:def removeDuplicates(self, nums: List[int]) -> int:left = 1n = len(nums)for i in range(1, n):if nums[i] != nums[i - 1]:nums[left] = nums[i]left += 1return left

第二课

★1436. 旅行终点站

知识点： 列表 list，append。

class Solution:def destCity(self, paths: List[List[str]]) -> str:start, end = [], []for s, e in paths:start.append(s)end.append(e)for x in end:if x not in start:return x

1299. 将每个元素替换为右侧最大元素

知识点： 逆序遍历

class Solution:def replaceElements(self, arr: List[int]) -> List[int]:n, m = len(arr), -1 # m 记录最大值for i in range(n - 1, -1, -1): # 逆序遍历m, arr[i] = max(arr[i], m), m # 原地修改，可定义列表。return arr

1394. 找出数组中的幸运数

class Solution:def findLucky(self, arr: List[int]) -> int:q = [0] * 501 # 统计个数# q[0] = -1 # 去掉 0for x in arr:  # 统计每个数的个数q[x] += 1# res = -1 # 先假设没有# for i, x in enumerate(q[1:], 1):            #     if i == x: res = i# return res for x in range(len(q) - 1, 0, -1): # 逆序遍历if x == q[x]: return xreturn -1

python 内置函数 enumerate()

将一个 可遍历 iterable 数据对象（如 list、tuple 或 str）组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中。
函数返回一个 enumerate 对象，是一个 可迭代对象。具体元素值可通过遍历取出。

语法：

enumerate(sequence, [start=0])

参数：
sequence – 一个序列、迭代器或其他支持迭代对象。是一个可迭代对象。
start – 下标起始位置。是一个可选参数，表示索引从几开始计数。

返回 enumerate(枚举) 对象。

a = [1,2,3,4]
# 从第二个元素开始，下标从 1 开始
for i, x in enumerate(a[1:], 1):print(i, x)
# 1 2
# 2 3
# 3 4

**知识点：**推导式，生成器，next。
教程：Python 推导式

class Solution:def destCity(self, paths: List[List[str]]) -> str:citiesA = {path[0] for path in paths}return next(path[1] for path in paths if path[1] not in citiesA)

第三课

1700. 无法吃午餐的学生数量

class Solution:def countStudents(self, students: List[int], sandwiches: List[int]) -> int:# n = 0# while n < len(students):#     if students[0] == sandwiches[0]:#         students.pop(0)#         sandwiches.pop(0)#         n = 0#     else:#         students = students[1:] + [students[0]]#         n += 1# return ncnt = [0, 0]  # 统计喜欢圆形和方形三明治学生数量for i in students: cnt[i] += 1for i in sandwiches:    # 依次取出栈顶三明治,直到没有学生喜欢 i。if cnt[i] == 0: breakcnt[i] -= 1return sum(cnt)

▲1089. 复写零

class Solution:def duplicateZeros(self, arr: List[int]) -> None:"""Do not return anything, modify arr in-place instead."""## 方法一：insert pop# i = 0# while i < len(arr):#     if not arr[i]:#         arr.pop()#         arr.insert(i, 0)#         i += 1#     i += 1## 方法二：添加标记       n = len(arr)i = j = 0while j < n:if arr[i] == 0: j += 1i += 1j += 1i -= 1    # i 回到最后一次合法的位置j -= 1    # j 同理，但 j 仍可能等于 n（例如输入 [0]）while i >= 0:if j < n: arr[j] = arr[i]if arr[i] == 0:j -= 1arr[j] = arr[i]i -= 1j -= 1

904. 水果成篮

算法：双指针

class Solution:def totalFruit(self, fruits: List[int]) -> int:arr = [0] * len(fruits) # 0 <= 种类 < len(fruits) <= 100000left = 0 # 左边界k = 0 # 记录区间包含的种类for i, x in enumerate(fruits):if arr[x] == 0: k += 1 # 遇到一种arr[x] += 1 # 计数if k > 2:  # 种类 > 2 左边同步收缩 否则右边单边扩张y = fruits[left] arr[y] -= 1 if arr[y] == 0: k -= 1 left += 1return len(fruits) - left # n - 1 - left + 1

第四课

390. 消除游戏

class Solution:def lastRemaining(self, n: int) -> int:# 方法一：模拟 转成 list 会超时arr = range(1, n + 1) # 可迭代对象，用一个生成一个while len(arr) > 1:arr = arr[1::2][::-1]return arr[0]# 方法二flag, a, step = True, 1, 1while n > 1:           if flag or n & 1: a += step           flag = not flagn >>= 1step <<= 1        return a# 方法三：递归return 1 if n == 1 else 2 * (n // 2 + 1 - self.lastRemaining(n // 2))

1652. 拆炸弹

class Solution:def decrypt(self, code: List[int], k: int) -> List[int]:n = len(code)ans = [0] * nif k == 0: return ansres = []code += codeif k > 0:l, r = 1, kelse:l, r = n + k, n - 1w = sum(code[l:r+1])for i in range(n):res.append(w)w -= code[l]w += code[r + 1]l, r = l + 1, r + 1return res

2516. 每种字符至少取 K 个

第五课

88. 合并两个有序数组

1768. 交替合并字符串

class Solution:def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:i, j = m - 1, n - 1for k in range(m+n-1,-1,-1):if j == -1: break # 如果 nums2 移完了结束if i == -1 or nums1[i] < nums2[j]:  # 如果 nums1 移完了，接着移 num2nums1[k] = nums2[j]j -= 1else:nums1[k] = nums1[i]i -= 1

2022. 将一维数组转变成二维数组

class Solution:def construct2DArray(self, original: List[int], m: int, n: int) -> List[List[int]]:return [original[i:i + n] for i in range(0,  len(original), n)] if len(original) == m * n else []

915. 分割数组

class Solution:def partitionDisjoint(self, nums: List[int]) -> int:n = len(nums)# 三次遍历# left, right = [0] * n, [0] * n# left[0], right[-1] = nums[0], nums[-1]# for i in range(n - 2, -1, -1):#     right[i] = min(right[i + 1], nums[i])# for i in range(1, n):#     left[i] = max(left[i - 1], nums[i])# for i in range(n):#     if left[i] <= right[i+1]:#         return i + 1# 二次遍历# right = [0] * n# max_, right[-1] = 0, nums[-1]# for i in range(n - 2, -1, -1):#     right[i] = min(right[i + 1], nums[i])# for i in range(n - 1):#     max_ = max(max_, nums[i])#     if max_ <= right[i + 1]:#         return i + 1# 一次遍历pos, max_, left = 1, nums[0], nums[0]for i, x in enumerate(nums):max_ = max(max_, x)if x < left:left = max_pos = i + 1return pos 

练习

807. 保持城市天际线

class Solution:def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:row = list(map(max, grid))col = list(map(max, zip(*grid)))return sum(min(row[i], col[j]) - h for i, r in enumerate(grid) for j, h in enumerate(r))

1716. 计算力扣银行的钱

等差数列的通项公式为：an = a1 + (n - 1) d
前n项和公式为：Sn = na1 + n (n - 1) d / 2 或 Sn = n (a1 + an) / 2

class Solution:def totalMoney(self, n: int) -> int:# w, d = divmod(n, 7)         # res = w * 28 + w * (w - 1) * 7 // 2 # 整周计算# res += d * (w + 1) + d * (d - 1) * 1 // 2 week, day, res = 0, 1, 0        for i in range(n):res += week + dayday += 1if day == 8:day = 1week += 1return res

1995. 统计特殊四元组

class Solution:def countQuadruplets(self, nums: List[int]) -> int:        res = 0n = len(nums)for i in range(n-3):for j in range(i+1,n-2):for k in range(j+1,n-1):for l in range(k+1,n):if nums[i]+nums[j]+nums[k] == nums[l]:res += 1return res

372. 超级次方

模运算对于乘法与加法满足交换律与结合律

(a ∗ b) % c = (a % c) ∗ (b % c) % c

pow(x, y[, z])
如果z在存在，则再对结果进行取模，其结果等效于 pow(x, y) % z
pow(a, 123) = pow(a, 3) * pow(pow(a, 12), 10) # 123 = 12 * 10 + 3

class Solution:def superPow(self, a: int, b: List[int]) -> int:return pow(a, b.pop()) * pow(self.superPow(a, b), 10) % 1337  if b else 1

279. 完全平方数

方法一：数学

四平方定理： 任何一个正整数都可以表示成不超过四个整数的平方之和。
推论： if and only if n is not of the form n = 4^a ( 8 b + 7 ) for integers a and b.
当且仅当 $n\ne 4^k\times (8m+7)$ 时，n 可以被表示为至多三个正整数的平方和。

class Solution:def numSquares(self, n: int) -> int:        sqr = int(sqrt(n))if n == sqr * sqr: return 1# 4 * x**2 = (2*x) ** 2        while n % 4 == 0:n >>= 2if n & 7 == 7: return 4 # n & 7 等价于 n % 8i = 0while i*i < n:j = int(sqrt(n - i*i))if i*i + j*j == n:  return 2i += 1return 3

方法二：动态规划

f[i] 表示最少需要多少个数的平方来表示整数 i。
这些数必然落在区间 $[1,\sqrt{n}]$。枚举这些数，假设当前枚举到 j，那么还需要取若干数的平方，构成 $i-j^2$ 。此时子问题和原问题一样，规模更小，符合了动态规划的要求。
状态转移方程：

$f[i]=1+{\min }_{j=1}^{\lfloor \sqrt{i}\rfloor }f[i-j^2]$

边界条件 $f[0]=0$

因为计算 $f[i]$ 时所需要用到的状态仅有 $f[i-j^2]$，必然小于 i，因此只需要从小到大地枚举 i 来计算 $f[i]$ 即可。

class Solution:def numSquares(self, n):if n == int(sqrt(n)) ** 2: return 1dp = [inf for i in range(n + 1)] # 4dp[0] = 0for i in range(n + 1):j = 1while i + j*j <= n:dp[i + j*j] = min(dp[i + j*j], dp[i] + 1)j += 1return dp[n]

2239. 找到最接近 0 的数字

class Solution:def findClosestNumber(self, nums: List[int]) -> int:ans = inffor x in nums:if abs(x) == abs(ans): ans = max(x, ans)elif abs(x) < abs(ans):  ans = x                return ans

2432… 处理用时最长的那个任务的员工

class Solution:def hardestWorker(self, n: int, logs: List[List[int]]) -> int:ans = pre = most = 0for i, t in logs: dif = t - prepre = tif most < dif or most == dif and ans > i:ans = imost = difreturn ans

1610. 可见点的最大数目

在视角 angle 范围内内最多的点数。
location 为极点，刚好位于 location 的点单独进行统计，计算其它所有点的极角，然后排序。
在极坐标系中，平面上任何一点到极点的连线和极轴的夹角叫做极角。
极坐标和直角坐标的互化：
函数「atan2」的返回值范围为 [−π,π]，它的覆盖范围为 2π。将 angle 转换成弧度。
由于存在 $d_{p_i}+\text{angle}>\pi$ 的情况，可以在原数组中将每个元素 $d_{p_i}+2\pi$ 添加到原数组的后面，这样即可防止反转的问题。

class Solution:def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:same, polar = 0, []for p in points:if p == location: same += 1else:polar.append(atan2(location[1] - p[1], location[0] - p[0]))polar.sort()polar += [p + 2 * pi for p in polar]arc = angle * pi / 180# 二分查找# return max((bisect_right(polar, p + arc) - i for i, p in enumerate(polar)), default=0) + same# 滑动窗口n, maxCount, right = len(polar), 0, 0for i in range(n//2):while right < n and polar[right] <= polar[i] + arc:right += 1maxCount = max(maxCount, right - i)return maxCount + same