class Solution:def removeElement(self, nums: List[int], val: int) -> int:# 把不等于 val 的值移動到前面n = len(nums)left = 0for right in range(n):if nums[right] != val:nums[left] = nums[right]left += 1return left

只保留 1 個元素

class Solution:def removeDuplicates(self, nums: List[int]) -> int:n = len(nums) left = 0  # 指向有效數組的最后一個元素# right 遍歷數組, 每次與有效數組最后一個元素比較是否相同for right in range(n):if nums[right] != nums[left]:left += 1nums[left] = nums[right]return left + 1

保留 k 個元素，次數 k = 2

class Solution:def removeDuplicates(self, nums: List[int]) -> int:n = len(nums)left = 0  # 指向有效數組的后一個位置k = 2  # 保留兩個for right in range(n):if left < k or nums[right] != nums[left-k]:nums[left] = nums[right]left += 1return left

一般的情況下

class Solution:def hIndex(self, citations: List[int]) -> int:n = len(citations)cnt = [0] * (n + 1)  # cnt[i] 引用次數 >= i 的數目for v in citations:cite = min(v, n)  # 引用次數大于 n 的情況, 算作ncnt[cite] += 1s = 0for i in range(n, -1, -1):s += cnt[i]  # 引用次數>=i的數量if s >= i:return i

有序的情況下

class Solution:def hIndex(self, citations: List[int]) -> int:# 有h篇論文的cite次數>=hn = len(citations)citations.sort()ans = 0for i, v in enumerate(citations):d = n - i + 1  # 剩余文章數if v >= d:return d

list 刪除尾元素的速度為 O(1)
所以刪除的時候，可以將待刪除的值與末尾元素交換，然后刪除末尾元素

from random import choice
class RandomizedSet:def __init__(self):self.nums = []self.indices = {}  # { val: 在nums中的下標 }def insert(self, val: int) -> bool:if val in self.indices:return False# 如果不在, 則在末尾插入元素self.indices[val] = len(self.nums)self.nums.append(val)return Truedef remove(self, val: int) -> bool:if val not in self.indices:return Falseid = self.indices[val]  # val在nums中的下標# 1.將末尾元素與待刪除元素的位置交換self.nums[id] = self.nums[-1]  # 將末尾元素的值移動到當前val位置self.indices[self.nums[id]] = id  # 更新對應的id# 刪除 valself.nums.pop()del self.indices[val]return Truedef getRandom(self) -> int:return choice(self.nums)

“已經在谷底了，怎么走都是向上。”

下圖為，從 0 加油站出發，到達每個站時的油量變化
可以看出，當走到 3 號加油站時，油量達到最低

所以從該點出發，之后的油量都不會比當前還低

同時，判斷 sum(gas) 與 sum(cost) 的大小關系

• 如果 sum(gas) >= sum(cost) ，則一定有解
• 反之沒有，返回 -1

class Solution:def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:# 先計算從 0 號加油站出發的油量變化，然后從中找到油量最低時所處的加油站ans = 0min_s = 0  # 表示從 0 出發遇到的最小油量點s = 0for i, (g, c) in enumerate(zip(gas, cost)):s += g - c  # 在 i 處加油，然后出發從 i 到 i+1if s < min_s:min_s = s  # 更新最小油量ans = i + 1  # 注意 s 減去 c 之后，汽車在 i+1 而不是 i# 循環結束后，s 即為 gas 之和減去 cost 之和if s < 0:  # 說明不存在可行解return -1else:return ans

class Solution:def romanToInt(self, s: str) -> int:# 小數在前表示<減去>, 小數在后表示<加上># 從后往前遍歷, 判斷當前數是否比上一個數大# 如果大于上一個數, 則直接加, 反之用減d = {'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}s = s[::-1]last_val = 0ans = 0for c in s:v = d[c]if v >= last_val:ans += velse:ans -= vlast_val = vreturn ans

class Solution:def intToRoman(self, num: int) -> str:hashmap = {1000:'M', 900:'CM', 500:'D', 400:'CD',100:'C', 90:'XC',50:'L', 40:'XL', 10:'X', 9:'IX', 5:'V', 4:'IV', 1:'I'}ans = ''for key in hashmap:if num // key != 0:count = num // keyans += hashmap[key] * countnum %= keyreturn ans