• 力扣面试经典150题
• 在 VScode 中安装 LeetCode 插件即可使用 VScode 刷题，安装 Debug LeetCode 插件可以免费 debug
• 本文使用 python 语言解题，文中 “数组” 通常指 python 列表；文中 “指针” 通常指 python 列表索引

---

11. [中等] H指数

• 题目链接
• 标签：数组、计数排序、排序
  

11.1 解法1：暴力法

• 根据题目可知，h 指数不能超过论文发表总数，也不能超过最高引用此次，其最大值为 min(max(citations), len(citations))。从该最大可能取值开始反向遍历所有可能取值 i，统计引用次数 >=i 的论文数量 paper_cnt，直到找到满足 h 指数的定义（即 paper_cnt>=i）的取值为止。这是一种带剪枝的暴力搜索方法

  class Solution:
      def hIndex(self, citations: List[int]) -> int:
          # 根据定义，h 指数的理论最大值
          max_h = min(max(citations), len(citations))
  
          # 从 max_h 开始反向遍历考察所有 h 指数的可能取值 i 
          for i in range(max_h, -1, -1):
              # 统计引用次数 >= i 的论文数量
              paper_cnt = 0
              for cite in citations:
                  if cite >= i:
                      paper_cnt += 1
  
              # 满足 h 指数定义则返回
              if paper_cnt >= i:
                  return i
          return 0
  

• 时间复杂度 $O(n^2)$，空间复杂度 $O(1)$

11.2 解法2：计数排序

• 以上暴力法中，对于每一个候选的 h 指数取值都做了一次遍历计数，因此时间复杂度高。一种优化方式是，先用过一次遍历完成所有计数操作，再通过另一次和暴力法相同的反向遍历确定 h 指数的值。具体而言，第一次遍历中我们用 defaultdict 统计引用量为 h 指数各可能取值i 的论文数量，之后在反向遍历时通过求和得到引用量 >=i 的论文数量
• 这种方法通过引入 $O(n)$ 的额外存储空间，将时间复杂度从 $O(n^2)$ 降低到 $O(n)$

  class Solution:    
      def hIndex(self, citations: List[int]) -> int:
          # 根据定义，h 指数的理论最大值
          max_h = min(max(citations), len(citations))
  
          # 用 counter 统计引用量 >= 不同 cite 值的论文数量
          from collections import defaultdict
          counter = defaultdict(int)
          for cite in citations:
              cite = max_h if cite > max_h else cite
              counter[cite] += 1
  
          # 从 max_h 开始反向遍历考察所有 h 指数的可能取值 i 
          tot = 0     
          for i in range(max_h, -1, -1):
              tot += counter[i]   # 引用量不少于 i 次的论文总数
              if tot >= i:        # 满足 h 指数定义则返回
                  return i
          return 0
  

• 时间复杂度 $O(n)$，空间复杂度 $O(n)$

11.3 解法3：排序

• 先初始化 h=0，然后把引用次数 citations 排序并大到小遍历。如果当前 h 指数为 h 并且在遍历过程中找到当前值 citations[i]>h，则说明我们找到了一篇被引用了至少 h+1 次的论文，所以 h+=1。继续遍历直到 h 无法继续增大后返回即可

  class Solution:
      def hIndex(self, citations: List[int]) -> int:
          sorted_citation = sorted(citations, reverse = True)
          h = 0; i = 0; n = len(citations)
          while i < n and sorted_citation[i] > h:
              h += 1
              i += 1
          return h
  

• 时间复杂度 $O(nlogn)$，空间复杂度 $O(logn)$（这两个都是排序算法的复杂度）

12. [中等] O(1) 时间插入、删除和获取随机元素

• 题目链接
• 标签：设计、数组、哈希表、数学
  

12.1 解法1：哈希表+变长数组

• 要求实现插入、删除和获取随机元素操作的平均时间复杂度为 $O(1)$
  1. 变长数组：可以在 $O(1)$ 的时间内完成获取随机元素操作。但是由于需要 $O(n)$ 时间判断元素是否存在，因此无法满足插入和删除的时间复杂度要求
  2. 哈希表：哈希表的核心思想，是通过函数函数把元素映射到存储位置索引，这样就能在 $O(1)$ 的时间内判断元素是否存在，或找到元素存储位置进行插入或删除。但哈希表无法在 $O(1)$ 时间内获取当前全体元素，因此无法满足随机取元素的时间复杂度要求
• 通过结合变长数组和哈希表，可以实现题目要求

  class RandomizedSet:
      def __init__(self):
          from collections import defaultdict
          import random
          self.item = []  # 在此存储元素
          self.idx = {}   # 哈希表，将元素映射到其在 self.item 中的索引位置
  
      def insert(self, val: int) -> bool:
          if val in self.idx:
              return False
          self.item.append(val)
          self.idx[val] = len(self.item) - 1
          return True
  
      def remove(self, val: int) -> bool:
          if not val in self.idx:
              return False
          idx_val = self.idx[val]         
          item_last = self.item[-1]       
          self.item[idx_val] = item_last  # self.item 中，用 item_last 替换目标元素
          self.idx[item_last] = idx_val   # self.idx 哈希表中，更新 item_last 对应的索引位置
          self.item.pop()                 # 弹出已经移动到 idx_val 处的 item_last
          del self.idx[val]               # 删除目标元素在哈希表中的索引
          return True
  
      def getRandom(self) -> int:
          return random.choice(self.item)
         
  # Your RandomizedSet object will be instantiated and called as such:
  # obj = RandomizedSet()
  # param_1 = obj.insert(val)
  # param_2 = obj.remove(val)
  # param_3 = obj.getRandom()
  # @lc code=end
  

13. [中等] 除自身以外的数组的乘积

• 题目链接
• 标签：数组、前缀和
  

13.1 解法1：左右乘积列表

• 用双指针同时从左右开始遍历列表，将左侧所有数字的乘积（前缀积）和右侧所有数字的乘积（后缀积）存储到两个辅助列表中。最后将两个辅助列表对应位置相乘得到结果

  class Solution:
      def productExceptSelf(self, nums: List[int]) -> List[int]:
          # pre_prods 存储每个索引位置所有前驱元素乘积
          # post_prods 存储每个索引位置所有后继元素乘积
          pre_prod, post_prod = 1, 1
          pre_prods, post_prods = [], []
          left, right = 0, -1
          for i in range(len(nums)):
              pre_prods.append(pre_prod)
              post_prods.append(post_prod)
              pre_prod *= nums[left]
              post_prod *= nums[right]
              left += 1
              right -= 1
          post_prods.reverse() 
          
          # 输出中每个索引位置，取 pre_prods 和 post_prods 对应位置元素相乘即可
          res = []
          for i in range(len(nums)):
              res.append(pre_prods[i] * post_prods[i])
          
          return res
  

• 时间复杂度 $O(n)$，空间复杂度 $O(n)$

13.2 解法2：左右乘积列表

• 以上方法需要构造存储前缀积和后缀积的两个辅助列表。为了减少空间复杂度，可以先构造前缀积列表，然后在计算后续元素乘积时直接将其乘到前缀积列表中并作为输出。这样可以把空间复杂度降低到 $O(1)$（不考虑输出数组）

  class Solution:
      def productExceptSelf(self, nums: List[int]) -> List[int]:
          # pre_prods 存储每个索引位置所有前驱元素乘积
          pre_prod = 1
          res = []
          for num in nums:
              res.append(pre_prod)
              pre_prod *= num
          
          # 再把后续元素乘积直接乘到 res 的对应位置上，实现 O(1) 的空间复杂度
          post_prod = 1
          for i in range(len(nums)-1, -1, -1):
              res[i] *= post_prod
              post_prod *= nums[i]
          
          return res
  

• 时间复杂度 $O(n)$，空间复杂度 $O(1)$

14. [中等] 加油站

• 题目链接
• 标签：贪心、数组
  

14.1 解法1：一次遍历

• 最直接的思想是依次把每一个加油站作为起点进行考察，直到找到能够绕行一周的加油站为止，但是这种暴力解法时间复杂度高。可以通过减小被检查的加油站数目来降低时间复杂度。
• 注意到这样一个事实：如果从 x 加油站出发最多只能到达 z 加油站，那么从 x 和 z 之间的 y 加油站出发一定无法到达超过 z 的位置。这是因为从 x 出发到达 y 时可能车里还有剩余燃油，直接从 y 出发不可能走得更远
• 我们可以从第 0 个加油站开始判断能否环绕一周；如果不能，就从第一个无法到达的加油站开始继续检查。

  class Solution:
      def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
          def _available_cnt(idx):
              # 计算从 idx 开始可以连续到达的加油站数量
              cnt, gas_left = 0, 0
              for i in range(n):
                  gas_left += delta[(idx + i) % n] 
                  if gas_left < 0:
                      return cnt
                  cnt += 1
              return cnt
  
          # 从各个加油站出发到下一个加油站导致的油量变化
          delta = [g - c for g, c in zip(gas, cost)]  
  
          # 检查从各个加油站出发能否环绕一周；不能则从第一个无法到达的加油站开始继续检查
          n, idx = len(gas), 0
          while idx < n:
              cnt = _available_cnt(idx)
              # 找到可能访问所有加油站的起点则返回
              if cnt == n:
                  return idx
              idx += cnt + 1
          return -1
  

• 时间复杂度 $O(n)$，空间复杂度 $O(1)$

15. [困难] 分发糖果

• 题目链接
• 标签：贪心、数组
  

15.1 解法1：两次遍历

• “相邻的孩子中，评分高的孩子必须获得更多的糖果” 这一句话可以拆分成两个规则
  1. 左规则：ratings[i-1]<ratings[i] 时，i 号的糖果比 i-1 号多
  2. 右规则：ratings[i]>ratings[i+1] 时，i 号的糖果比 i+1 号多
• 单独处理其中任意一个规则是简单的，以左规则为例，初始化分配糖果数为1，从左到右遍历，若分数递增则分配糖果数+1，反之重置为1。右规则同理。
  1. 对于仅满足左规则的分配数组 L，其在每一个分数递增段都从1开始递增，其余部分全是1
  2. 对于仅满足右规则的分配数组 R，其在每一个分数递减段都递减到1，其余部分全是1
• 经过两次遍历得到 L 和 R 后，直接给第 $i$ 个小孩分配 max(L[i], R[i]) 颗糖果即可。为了分析这种操作的正确性，假设 $L[i]>R[i]$，则 $\max (L[i],R[i])=L[i]$，此时左规则一定满足，考虑右规则
  1. 若 ratings[i]>ratings[i+1]，此时分配数量 $L[i]>R[i]>R[i+1]$ 一定满足右规则
  2. 若 ratings[i-1]>ratings[i]，这意味着 $i$ 处于一个递减序列内，此时 $L[i]=1$，不可能有 $L[i]>R[i]$，故增加给第 $i$ 个小孩的糖果数量不会导致在 $i-1$ 处违反右规则
• 综上，给出如下的求解代码

  class Solution:
      def candy(self, ratings: List[int]) -> int:
          n = len(ratings)
  
          # 仅考虑左规则对应的最少糖果分配
          left = [1, ]
          for i in range(n-1):
              left.append(left[i] + 1 if ratings[i+1] > ratings[i] else 1)
              
          # 仅考虑右规则对应的最少糖果分配
          ratings.reverse()
          right = [1, ]
          for i in range(n-1):
              right.append(right[i] + 1 if ratings[i+1] > ratings[i] else 1)
          right.reverse()
  
          # max 操作确定每个索引处同时满足左右规则的糖果数，求和
          return sum([max(l, r) for l, r in zip(left, right)])
  

• 时间复杂度 $O(n)$，空间复杂度 $O(n)$