面试150，数组 / 字符串

27. 移除元素

1. class Solution:
2.     def removeElement(self, nums: List[int], val: int) -> int:
3.         # 把不等于 val 的值移动到前面
4.         n = len(nums)
5.         left = 0
7.         for right in range(n):
8.             if nums[right] != val:
9.                 nums[left] = nums[right]
10.                 left += 1
11.         return left

复制代码

---

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

只保存 1 个元素

1. class Solution:
2.     def removeDuplicates(self, nums: List[int]) -> int:
3.         n = len(nums)
5.         left = 0  # 指向有效数组的最后一个元素
6.         # right 遍历数组, 每次与有效数组最后一个元素比较是否相同
7.         for right in range(n):
8.             if nums[right] != nums[left]:
9.                 left += 1
10.                 nums[left] = nums[right]
11.         return left + 1

复制代码

---

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

保存 k 个元素，次数 k = 2

1. class Solution:
2.     def removeDuplicates(self, nums: List[int]) -> int:
3.         n = len(nums)
4.         left = 0  # 指向有效数组的后一个位置
5.         k = 2  # 保留两个
6.         for right in range(n):
7.             if left < k or nums[right] != nums[left-k]:
8.                 nums[left] = nums[right]
9.                 left += 1
10.         return left

复制代码

---

274. H 指数

一样平常的情况下

1. class Solution:
2.     def hIndex(self, citations: List[int]) -> int:
3.         n = len(citations)
4.         cnt = [0] * (n + 1)  # cnt[i] 引用次数 >= i 的数目
6.         for v in citations:
7.             cite = min(v, n)  # 引用次数大于 n 的情况, 算作n
8.             cnt[cite] += 1
9.         
10.         s = 0
11.         for i in range(n, -1, -1):
12.             s += cnt[i]  # 引用次数>=i的数量
13.             if s >= i:
14.                 return i

复制代码

有序的情况下

1. class Solution:
2.     def hIndex(self, citations: List[int]) -> int:
3.         # 有h篇论文的cite次数>=h
4.         n = len(citations)
5.         citations.sort()
6.         ans = 0
8.         for i, v in enumerate(citations):
9.             d = n - i + 1  # 剩余文章数
10.             if v >= d:
11.                 return d

复制代码

---

380. O(1) 时间插入、删除和获取随机元素

list 删除尾元素的速度为 O(1)
以是删除的时候，可以将待删除的值与末端元素交换，然后删除末端元素

1. from random import choice
2. class RandomizedSet:
3.     def __init__(self):
4.         self.nums = []
5.         self.indices = {}  # { val: 在nums中的下标 }
7.     def insert(self, val: int) -> bool:
8.         if val in self.indices:
9.             return False
10.         # 如果不在, 则在末尾插入元素
11.         self.indices[val] = len(self.nums)
12.         self.nums.append(val)
13.         return True
15.     def remove(self, val: int) -> bool:
16.         if val not in self.indices:
17.             return False
18.         id = self.indices[val]  # val在nums中的下标
19.         # 1.将末尾元素与待删除元素的位置交换
20.         self.nums[id] = self.nums[-1]  # 将末尾元素的值移动到当前val位置
21.         self.indices[self.nums[id]] = id  # 更新对应的id
22.         # 删除 val
23.         self.nums.pop()
24.         del self.indices[val]
25.         return True
27.     def getRandom(self) -> int:
28.         return choice(self.nums)

复制代码

---

134. 加油站

“已经在谷底了，怎么走都是向上。”
下图为，从 0 加油站出发，到达每个站时的油量变化
可以看出，当走到 3 号加油站时，油量到达最低

以是从该点出发，之后的油量都不会比当前还低

同时，判断 sum(gas) 与 sum(cost) 的大小关系

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

1. class Solution:
2.     def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
3.         # 先计算从 0 号加油站出发的油量变化，然后从中找到油量最低时所处的加油站
4.         ans = 0
5.         min_s = 0  # 表示从 0 出发遇到的最小油量点
6.         s = 0
8.         for i, (g, c) in enumerate(zip(gas, cost)):
9.             s += g - c  # 在 i 处加油，然后出发从 i 到 i+1
10.             if s < min_s:
11.                 min_s = s  # 更新最小油量
12.                 ans = i + 1  # 注意 s 减去 c 之后，汽车在 i+1 而不是 i
14.         # 循环结束后，s 即为 gas 之和减去 cost 之和
15.         if s < 0:  # 说明不存在可行解
16.             return -1
17.         else:
18.             return ans

复制代码

---

13. 罗马数字转整数

1. class Solution:
2.     def romanToInt(self, s: str) -> int:
3.         # 小数在前表示<减去>, 小数在后表示<加上>
4.         # 从后往前遍历, 判断当前数是否比上一个数大
5.         # 如果大于上一个数, 则直接加, 反之用减
7.         d = {
8.             'I':1,
9.             'V':5,
10.             'X':10,
11.             'L':50,
12.             'C':100,
13.             'D':500,
14.             'M':1000
15.         }
17.         s = s[::-1]
18.         last_val = 0
19.         ans = 0
21.         for c in s:
22.             v = d[c]
23.             if v >= last_val:
24.                 ans += v
25.             else:
26.                 ans -= v
27.             last_val = v
28.         
29.         return ans

复制代码

---

12. 整数转罗马数字

1. class Solution:
2.     def intToRoman(self, num: int) -> str:
3.         hashmap = {
4.             1000:'M', 900:'CM',
5.             500:'D', 400:'CD',
6.             100:'C', 90:'XC',
7.             50:'L', 40:'XL',
8.             10:'X', 9:'IX',
9.             5:'V', 4:'IV', 1:'I'}
11.         ans = ''
13.         for key in hashmap:
14.             if num // key != 0:
15.                 count = num // key
16.                 ans += hashmap[key] * count
17.                 num %= key
18.         
19.         return ans

复制代码

---

[code][/code]

---

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。