力扣面试经典150 —— 11-15题

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

文章目录

11. [中等] H指数
12. [中等] O(1) 时间插入、删除和获取随机元素
- 12.1 解法1：哈希表+变长数组
13. [中等] 除自身以外的数组的乘积
- 13.1 解法1：左右乘积列表
- 13.2 解法2：左右乘积列表
14. [中等] 加油站
- 14.1 解法1：一次遍历
15. [困难] 分发糖果
- 15.1 解法1：两次遍历

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(n^2) O(n2)，空间复杂度 O ( 1 ) O(1) O(1)

11.2 解法2：计数排序

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

这种方法通过引入 O ( n ) O(n) O(n) 的额外存储空间，将时间复杂度从 O ( n 2 ) O(n^2) O(n2) 降低到 O ( n ) O(n) 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) O(n)，空间复杂度 O ( n ) 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 ( n l o g n ) O(nlogn) O(nlogn)，空间复杂度 O ( l o g n ) O(logn) O(logn)（这两个都是排序算法的复杂度）

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

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

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

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

13.2 解法2：左右乘积列表

以上方法需要构造存储前缀积和后缀积的两个辅助列表。为了减少空间复杂度，可以先构造前缀积列表，然后在计算后续元素乘积时直接将其乘到前缀积列表中并作为输出。这样可以把空间复杂度降低到 O ( 1 ) O(1) 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(n) O(n)，空间复杂度 O ( 1 ) O(1) 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(n) O(n)，空间复杂度 O ( 1 ) O(1) 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 i i 个小孩分配 max(L[i], R[i]) 颗糖果即可。为了分析这种操作的正确性，假设 L [ i ] > R [ i ] L[i] > R[i] L[i]>R[i]，则 max ⁡ ( L [ i ] , R [ i ] ) = L [ i ] \max(L[i], R[i]) = L[i] max(L[i],R[i])=L[i]，此时左规则一定满足，考虑右规则
1. 若 ratings[i]>ratings[i+1]，此时分配数量 L [ i ] > R [ i ] > R [ i + 1 ] L[i]>R[i]>R[i+1] L[i]>R[i]>R[i+1] 一定满足右规则
2. 若 ratings[i-1]>ratings[i]，这意味着 i i i 处于一个递减序列内，此时 L [ i ] = 1 L[i]=1 L[i]=1，不可能有 L [ i ] > R [ i ] L[i] > R[i] L[i]>R[i]，故增加给第 i i i 个小孩的糖果数量不会导致在 i − 1 i-1 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) O(n)，空间复杂度 O ( n ) O(n) O(n)

云端FFF