LeetCode Weekly Contest 182解题报告
No.1 找出数组中的幸运数 ★解题思路
注意到数据范围: 数组中的元素在 [1, 500] 区间内, 所以我们可以直接使用一个数组来统计每个数字出现的次数. 然后从大到小检查每个数字的出现次数是否等于它本身即可。
代码展示
class Solution {
public int findLucky(int[] arr) {
int[] cnt = new int[501];
for (int num : arr) {
cnt[num]++;
}
for (int i = 500; i > 0; i--) {
if (cnt[i] == i) {
return i;
}
}
return -1;
}
}
No.2 统计作战单位数 ★解题思路
这个题目就是在问一共有多少个三元组 (i, j, k) 满足:
1. i < j < k 2. rating[i] < rating[j] < rating[k] 或者 rating[i] > rating[j] > rating[k]
我们可以依次统计每个元素作为这样的三元组的中间元素时的情况数, 这样就可以做到不重不漏.
以元素 rating[i] 为中间元素的合法三元组数量就是: i 左侧比 rating[i] 小的元素数量 * i 右侧比 rating[i] 大的元素数量 + i 左侧比 rating[i] 大的元素数量
代码展示
class Solution {
public int numTeams(int[] rating) {
int n = rating.length;
int res = 0;
for (int i = 1; i < n - 1; i++) {
// lt_l 表示 i 左侧比 rating[i] 小的元素的数量
// lt_r 表示 i 右侧比 rating[i] 小的元素的数量
// gt_l 表示 i 左侧比 rating[i] 大的元素的数量
// gt_r 表示 i 右侧比 rating[i] 大的元素的数量
int lt_l = 0, lt_r = 0, gt_l = 0, gt_r = 0;
for (int j = 0; j < i; j++) {
lt_l += rating[j] < rating[i] ? 1 : 0;
gt_l += rating[j] < rating[i] ? 0 : 1;
}
for (int j = i + 1; j < n; j++) {
lt_r += rating[j] < rating[i] ? 1 : 0;
gt_r += rating[j] < rating[i] ? 0 : 1;
}
// 以 i 为中间元素的三元组数量
res += lt_l * gt_r + lt_r * gt_l;
}
return res;
}
}
由于该题目数据范围较小, 所以可以直接使用循环来统计. 时间复杂度 o(n^2)
存在更优的做法, 比如离散化之后使用树状数组或线段树来查找 lt_l, lt_r 等, 但是实现比较复杂. 时间复杂度 o(nlogn)
No.3 设计地铁系统 ★解题思路
我们需要存储两种数据:
1. 已经上车但是还没下车的乘客信息, 包括 id, 上车时间, 上车车站, 并且我们需要能够从 id 查询到这些信息. 2. 已经建立起的车站之间的路径耗时.
实现一
我们可以使用三个类储存这些信息 (由于要使用 HashMap, 所以一定要正确重写 hashCode() 和 equals() 方法) 代码展示
class Aboard {
public int id;
public int time;
public String station;
public Aboard(int id, int time, String station) {
this.id = id;
this.time = time;
this.station = station;
}
@Override
public int hashCode() {
return Integer.hashCode(id) ^ Integer.hashCode(time) ^ station.hashCode();
}
@Override
public boolean equals(Object obj) {
if (obj instanceof Aboard) {
Aboard o = (Aboard) obj;
return id == o.id && time == o.time && station.equals(o.station);
}
return false;
}
}
class Edge {
public String start, end;
public Edge(String start, String end) {
this.start = start;
this.end = end;
}
@Override
public int hashCode() {
return start.hashCode() ^ end.hashCode();
}
@Override
public boolean equals(Object obj) {
if (obj instanceof Edge) {
Edge o = (Edge) obj;
return start.equals(o.start) && end.equals(o.end);
}
return false;
}
}
class EdgeAvg {
public int num, sum;
public EdgeAvg() {
num = 0;
sum = 0;
}
@Override
public int hashCode() {
return num ^ sum;
}
@Override
public boolean equals(Object obj) {
if (obj instanceof EdgeAvg) {
EdgeAvg o = (EdgeAvg) obj;
return num == o.num && sum == o.sum;
}
return false;
}
}
然后, 我们只需要使用 HashMap 建立 id -> Aboard 和 Edge -> EdgeAvg的映射即可. 在乘客上下车时更新这些信息.
class UndergroundSystem {
private Map<Integer, Aboard> checkedIn;
private Map<Edge, EdgeAvg> edges;
public UndergroundSystem() {
checkedIn = new HashMap<>();
edges = new HashMap<>();
}
public void checkIn(int id, String stationName, int t) {
checkedIn.put(id, new Aboard(id, t, stationName));
}
public void checkOut(int id, String stationName, int t) {
Aboard in = checkedIn.get(id);
checkedIn.remove(id);
Edge edge = new Edge(in.station, stationName);
if (!edges.containsKey(edge)) {
edges.put(edge, new EdgeAvg());
}
EdgeAvg avg = edges.get(edge);
avg.num++;
avg.sum += t - in.time;
}
public double getAverageTime(String startStation, String endStation) {
Edge edge = new Edge(startStation, endStation);
EdgeAvg avg = edges.get(edge);
return (double)avg.sum / avg.num;
}
}
实现二 我们也可以完全不使用自定义的类来实现映射, 而是多使用几个 HashMap. 这样整体代码更精简, 不过数据封装性不如实现一. 代码展示
class UndergroundSystem {
Map<Integer,Integer> aboardTime; // id -> 上车时间
Map<Integer,String> aboardStation; // id -> 上车车站
Map<String,Integer> timeSum; // 路径 -> 时间总和; 由于站名只有字母和数字, 所以路径的表示格式为: 起点-终点
Map<String,Integer> count; // 路径 -> 路径数量
public UndergroundSystem() {
aboardTime = new HashMap<>();
aboardStation = new HashMap<>();
timeSum = new HashMap<>();
count = new HashMap<>();
}
public void checkIn(int id, String stationName, int t) {
aboardTime.put(id, t);
aboardStation.put(id, stationName);
}
public void checkOut(int id, String stationName, int t) {
int startTime = aboardTime.get(id);
String edge = aboardStation.get(id) + "-" + stationName;
aboardTime.remove(id);
aboardStation.remove(id);
timeSum.put(edge, timeSum.getOrDefault(edge, 0) + t - startTime);
count.put(edge, count.getOrDefault(edge, 0) + 1);
}
public double getAverageTime(String startStation, String endStation) {
String edge = startStation + "-" + endStation;
return (double)timeSum.get(edge) / count.get(edge);
}
}
No.4 找到所有好字符串 ★解题思路 看到这个题目基本想法就是动态规划. 不过为了简化状态的表示, 我们使用容斥原理: 字典序在 s1 和 s2 之间的不包含 evil 字符串的数量 = 字典序不超过 s2 的不包含 evil 字符串的数量 - 字典序不超过 s1 的不包含 evil 字符串的数量 + 字典序等于 s1 的不包含 evil 字符串的数量. 现在问题变成了: 求字典序不超过 s 的且不包含 evil 字符串的数量. 具体思路见代码注释. 代码展示
class Solution {
final long MOD = 1000000007;
public int findGoodStrings(int n, String s1, String s2, String evil) {
long r = findGoodStrings(s2, evil);
long l = findGoodStrings(s1, evil);
return (int)((r - l + MOD + (s1.contains(evil) ? 0 : 1)) % MOD);
}
// 返回字典序不超过 s 且不包含 t 的字符串的数量
private long findGoodStrings(String s0, String evil) {
char[] s = s0.toCharArray();
char[] t = evil.toCharArray();
// dp[i][j][k] 表示长度为 i 的字符串
// 并且这样的字符串的后缀和 t 的前缀相同的长度为 j 时, 字符串的数量
// 而 k = 0 表示字典序严格小于 s 的相同前缀, k = 1 表示相等
int n = s.length;
int m = t.length;
long[][][] dp = new long[n + 1][m][2];
dp[0][0][1] = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 考虑 dp[i][j][0] 和 dp[i][j][1] 可以贡献到哪个状态里 dp[ni][nj][nk]
// ni 必定为 i + 1 而 nk 与 k 有关; 比较麻烦的是 nj 的确定
// 枚举决策: 添加了哪个字符
for (char c = 'a'; c <= 'z'; c++) {
int nj;
// 确定 nj, 这需要查看 t 的长度为 j 的前缀加上字符 c 之后变成了多长的前缀
// 这里可以使用 KMP 的 next 数组优化, 不过数据范围较小, 直接暴力求解也可以
if (c == t[j]) {
nj = j + 1;
} else {
String str = evil.substring(0, j) + c;
int len = str.length();
for (nj = j; nj > 0; nj--) {
if (evil.substring(0, nj).equals(str.substring(len - nj, len))) {
break;
}
}
}
if (nj == m) { // 完全包含 evil, 跳过
continue;
}
// dp[i][j][0] 加上字符 c 必然转移到 dp[i + 1][nj][0]
dp[i + 1][nj][0] = (dp[i + 1][nj][0] + dp[i][j][0]) % MOD;
// dp[i][j][1] 需要判断
if (c == s[i]) { // 转移到 dp[i + 1][nj][1]
dp[i + 1][nj][1] = (dp[i + 1][nj][1] + dp[i][j][1]) % MOD;
} else if (c < s[i]) { // 转移到 dp[i + 1][nj][0]
dp[i + 1][nj][0] = (dp[i + 1][nj][0] + dp[i][j][1]) % MOD;
}
}
}
}
long ans = 0;
for (int j = 0; j < m; j++) {
ans = (ans + dp[n][j][0] + dp[n][j][1]) % MOD;
}
return ans;
}
}
创作新主题