面试150，数组 / 字符串

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