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

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

代码:

第二题:统计作战单位数

   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倒过来算一次即可。

代码:

第三题:设计地铁系统

  请你实现一个类 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]
代码: