LeetCode 第182场周赛

暂时只有前三题题解，第四题还在研究中。。。

第一题：找出数组中的幸运数

　　在整数数组中，如果一个整数的出现频次和它的数值大小相等，我们就称这个整数为「幸运数」。
　　
　　给你一个整数数组 arr，请你从中找出并返回一个幸运数。
　　
　　如果数组中存在多个幸运数，只需返回最大的那个。
　　如果数组中不含幸运数，则返回 -1 。
　　
　　
　　示例 1：
　　输入：arr = [2,2,3,4]
　　输出：2
　　解释：数组中唯一的幸运数是 2 ，因为数值 2 的出现频次也是 2 。
　　
　　示例 2：
　　输入：arr = [1,2,2,3,3,3]
　　输出：3
　　解释：1、2 以及 3 都是幸运数，只需要返回其中最大的 3 。
　　
　　示例 3：
　　输入：arr = [2,2,2,3,3]
　　输出：-1
　　解释：数组中不存在幸运数。
　　
　　示例 4：
　　输入：arr = [5]
　　输出：-1
　　
　　示例 5：
　　输入：arr = [7,7,7,7,7,7,7]
　　输出：7

思路：
　　统计次数所有元素的出现次数后遍历。

代码：

class Solution:
    def findLucky(self, arr: List[int]) -> int:
        import collections
        c = collections.Counter(arr)
        ans = -1
        for k in c:
            if c[k] == k:
                ans = max(ans, k)  

        return ans

class Solution:

def findLucky(self, arr: List[int]) -> int:

import collections

c = collections.Counter(arr)

ans = -1

for k in c:

if c[k] == k:

ans = max(ans, k)

return ans

第二题：统计作战单位数

　　 n 名士兵站成一排。每个士兵都有一个独一无二的评分 rating 。
　　
　　每 3 个士兵可以组成一个作战单位，分组规则如下：
　　
　　从队伍中选出下标分别为 i、j、k 的 3 名士兵，他们的评分分别为 rating[i]、rating[j]、rating[k]
　　作战单位需满足： rating[i] < rating[j] < rating[k] 或者 rating[i] > rating[j] > rating[k] ，其中 0 <= i < j < k < n
　　请你返回按上述条件可以组建的作战单位数量。每个士兵都可以是多个作战单位的一部分。
　　
　　
　　示例 1：
　　输入：rating = [2,5,3,4,1]
　　输出：3
　　解释：我们可以组建三个作战单位 (2,3,4)、(5,4,1)、(5,3,1) 。
　　
　　示例 2：
　　输入：rating = [2,1,3]
　　输出：0
　　解释：根据题目条件，我们无法组建作战单位。
　　
　　示例 3：
　　输入：rating = [1,2,3,4]
　　输出：4

思路：
　　动态规划。
　　dp[i][0]表示rating[i]之前比rating[i]小的数有几个。
　　dp[i][1]表示rating[i]之前有几个升序的作战单位。
　　降序的把整个rating倒过来算一次即可。

代码：

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n = len(rating)
        def helper(rating):
            dp = [[0 for _ in range(2)] for _ in range(n)]  # dp[i][0] 表示2个的 de[i][1]表示3个的
            for i in range(1, n):
                for j in range(i):
                    if rating[i] > rating[j]:
                        dp[i][0] += 1  # 两个的

            for i in range(1, n):
                for j in range(i):
                    if rating[i] > rating[j]:
                        dp[i][1] += dp[j][0]  # 三个的

            # print(dp)
            return sum([dp[i][1] for i in range(1, n)])

        return helper(rating) + helper(rating[::-1])

class Solution:

def numTeams(self, rating: List[int]) -> int:

n = len(rating)

def helper(rating):

dp = [[0 for _ in range(2)] for _ in range(n)] # dp[i][0] 表示2个的 de[i][1]表示3个的

for i in range(1, n):

for j in range(i):

if rating[i] > rating[j]:

dp[i][0] += 1 # 两个的

for i in range(1, n):

for j in range(i):

if rating[i] > rating[j]:

dp[i][1] += dp[j][0] # 三个的

# print(dp)

return sum([dp[i][1] for i in range(1, n)])

return helper(rating) + helper(rating[::-1])

第三题：设计地铁系统

　　请你实现一个类 UndergroundSystem ，它支持以下 3 种方法：
　　
　　1. checkIn(int id, string stationName, int t)
　　
　　编号为 id 的乘客在 t 时刻进入地铁站 stationName 。
　　一个乘客在同一时间只能在一个地铁站进入或者离开。
　　2. checkOut(int id, string stationName, int t)
　　
　　编号为 id 的乘客在 t 时刻离开地铁站 stationName 。
　　3. getAverageTime(string startStation, string endStation)
　　
　　返回从地铁站 startStation 到地铁站 endStation 的平均花费时间。
　　平均时间计算的行程包括当前为止所有从 startStation 直接到达 endStation 的行程。
　　调用 getAverageTime 时，询问的路线至少包含一趟行程。
　　你可以假设所有对 checkIn 和 checkOut 的调用都是符合逻辑的。也就是说，如果一个顾客在 t1 时刻到达某个地铁站，那么他离开的时间 t2 一定满足 t2 > t1 。所有的事件都按时间顺序给出。
　　
　　
　　示例：
　　输入：
　　[“UndergroundSystem”,”checkIn”,”checkIn”,”checkIn”,”checkOut”,”checkOut”,”checkOut”,”getAverageTime”,”getAverageTime”,”checkIn”,”getAverageTime”,”checkOut”,”getAverageTime”]
　　[[],[45,”Leyton”,3],[32,”Paradise”,8],[27,”Leyton”,10],[45,”Waterloo”,15],[27,”Waterloo”,20],[32,”Cambridge”,22],[“Paradise”,”Cambridge”],[“Leyton”,”Waterloo”],[10,”Leyton”,24],[“Leyton”,”Waterloo”],[10,”Waterloo”,38],[“Leyton”,”Waterloo”]]
　　
　　输出：
　　[null,null,null,null,null,null,null,14.0,11.0,null,11.0,null,12.0]
　　
　　解释：
　　UndergroundSystem undergroundSystem = new UndergroundSystem();
　　undergroundSystem.checkIn(45, “Leyton”, 3);
　　undergroundSystem.checkIn(32, “Paradise”, 8);
　　undergroundSystem.checkIn(27, “Leyton”, 10);
　　undergroundSystem.checkOut(45, “Waterloo”, 15);
　　undergroundSystem.checkOut(27, “Waterloo”, 20);
　　undergroundSystem.checkOut(32, “Cambridge”, 22);
　　undergroundSystem.getAverageTime(“Paradise”, “Cambridge”); // 返回 14.0。从 “Paradise”（时刻 8）到 “Cambridge”(时刻 22)的行程只有一趟
　　undergroundSystem.getAverageTime(“Leyton”, “Waterloo”); // 返回 11.0。总共有 2 躺从 “Leyton” 到 “Waterloo” 的行程，编号为 id=45 的乘客出发于 time=3 到达于 time=15，编号为 id=27 的乘客于 time=10 出发于 time=20 到达。所以平均时间为 ( (15-3) + (20-10) ) / 2 = 11.0
　　undergroundSystem.checkIn(10, “Leyton”, 24);
　　undergroundSystem.getAverageTime(“Leyton”, “Waterloo”); // 返回 11.0
　　undergroundSystem.checkOut(10, “Waterloo”, 38);
　　undergroundSystem.getAverageTime(“Leyton”, “Waterloo”); // 返回 12.0

思路：
　　用字典，selfon_way记录还没下车的，如on_way[45] = ("Leyton", 3)，self.ave记录两两车站之间的所有行程，如self.ave[("Leyton", "Waterloo")] = [12, 10]。
代码：

from collections import defaultdict

class UndergroundSystem:

    def __init__(self):
        self.on_way = {}  # 在路上  on_way[45] = (from, t)
        self.ave = defaultdict(list)  # [('leyton', 'waterloo')] = []


    def checkIn(self, id: int, stationName: str, t: int) -> None:
        self.on_way[id] = (stationName, t)


    def checkOut(self, id: int, stationName: str, t: int) -> None:
        from_station, checkin_time = self.on_way.pop(id)  # 出站时将入站记录删除
        self.ave[(from_station, stationName)].append(t-checkin_time)


    def getAverageTime(self, startStation: str, endStation: str) -> float:
        ave = self.ave[(startStation, endStation)]
        return sum(ave) / len(ave)

from collections import defaultdict

class UndergroundSystem:

def __init__(self):

self.on_way = {} # 在路上 on_way[45] = (from, t)

self.ave = defaultdict(list) # [('leyton', 'waterloo')] = []

def checkIn(self, id: int, stationName: str, t: int) -> None:

self.on_way[id] = (stationName, t)

def checkOut(self, id: int, stationName: str, t: int) -> None:

from_station, checkin_time = self.on_way.pop(id) # 出站时将入站记录删除

self.ave[(from_station, stationName)].append(t-checkin_time)

def getAverageTime(self, startStation: str, endStation: str) -> float:

ave = self.ave[(startStation, endStation)]

return sum(ave) / len(ave)