ToB企服应用市场:ToB评测及商务社交产业平台

标题: 面试150，数组 / 字符串 [打印本页]
作者: 大号在练葵花宝典    时间: 5 天前
标题: 面试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) 的大小关系

  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企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4