LeetCode Weekly Contest 173 解题报告
No.1 Remove Palindromic Subsequences
解题思路
题目描述有两个关键点:
1.每次删除的是回文子序列, 而不是子串
2.只包含 'a' 和 'b' 这两种字符
那么我们一定可以在 2 次之内删除完毕: 一次删除所有的 'a', 一次删除所有的 'b'. 而如果原串本身是一个回文串, 那么只需要 1 次就可以删除.
代码展示
class Solution {
public int removePalindromeSub(String s) {
// 只包含 a 和 b
if (s == null || s.equals("")) {
return 0;
}
char[] str = s.toCharArray();
for (int i = 0, j = str.length - 1; i < j; i++, j--) {
if (str[i] != str[j]) {
return 2; // 原串不是回文串, 那么需要删除 2 次
}
}
return 1; // 原串是回文串, 删除 1 次
}
}
● 大厂码工日常大揭秘 ●
求职分享公益讲座
大厂码工求职分享讲座：
大公司招聘内幕
刷100题如何做到弯道超车成功上岸
如何做好刷题准备
快快扫描二维码参与免费讲座~
No.2 Filter Restaurants by Vegan-Friendly, Price and Distance
解题思路
将根据三个指标过滤之后剩下的餐厅按照 (rating, id) 从大到小排序即可.
注意当 rating 相等时, 按照 id 从大到小排序.
代码展示
// 用于储存按照三个指标过滤之后的餐厅 (只需要 id 和 rating)
class Pair {
public int id;
public int rating;
public Pair(int id, int rating) {
this.id = id;
this.rating = rating;
}
}
class Solution {
private boolean check(int[] restaurant, int veganFriendly, int maxPrice, int maxDistance) {
// 检查一个餐厅是否满足条件, 满足则返回 true, 应该被过滤掉则返回 false
return restaurant[3] <= maxPrice &&
restaurant[4] <= maxDistance &&
(veganFriendly == 0 || restaurant[2] == 1);
}
public List<Integer> filterRestaurants(int[][] restaurants, int veganFriendly, int maxPrice, int maxDistance) {
// 过滤餐厅
List<Pair> filtered = new ArrayList<>();
for (int[] restaurant : restaurants) {
if (check(restaurant, veganFriendly, maxPrice, maxDistance)) {
filtered.add(new Pair(restaurant[0], restaurant[1]));
}
}
// 排序
filtered.sort(new Comparator<Pair>() {
@Override
public int compare(Pair o1, Pair o2) { // 按照 (rating, id) 降序排列
return o1.rating == o2.rating ? o2.id - o1.id : o2.rating - o1.rating;
}
});
// 提取答案
List<Integer> res = new ArrayList<>();
for (Pair p : filtered) {
res.add(p.id);
}
return res;
}
}
-
No.3 Find theCity With theSmallest Number of Neighbors at a Threshold Distance
解题思路
这道题目需要求出任意两个城市之间的最短路径, 所以使用 floyd 算法.
时间复杂度:o(n^3), 而 n <= 100, 可以通过.
空间复杂度:o(n^2).
代码展示
class Solution { public int findTheCity(int n, int[][] edges, int distanceThreshold) { final int INF = 0x3f3f3f3f; // 不使用 Integer.MAX_VALUE, 避免加法溢出 int[][] dis = new int[n][n]; // dis[i][j] 表示 i 和 j 之间的最短路长度 // 初始化为无穷大 for (int i = 0; i < n; i++) { Arrays.fill(dis[i], INF); } // 使用直接相连的边计算一部分 dis for (int[] edge : edges) { dis[edge[0]][edge[1]] = Math.min(edge[2], dis[edge[0]][edge[1]]); dis[edge[1]][edge[0]] = Math.min(edge[2], dis[edge[1]][edge[0]]); } // floyd 算法三层循环, 求出所有的 dis for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { dis[i][j] = Math.min(dis[i][j], dis[i][k] + dis[k][j]); } } } // 根据 dis 统计每个城市可以在 distanceThreshold 内到达的城市数量, 得到答案 int city = -1, counter = INF; for (int i = 0; i < n; i++) { int cnt = 0; for (int j = 0; j < n; j++) { cnt += dis[i][j] <= distanceThreshold && i != j ? 1 : 0; } if (cnt <= counter) { city = i; counter = cnt; } } return city; } }No.4 Minium Difficulty of a Job Schedule
解题思路
动态规划问题.
定义状态: f[i][j] 表示前 i 天完成前 j 项任务的最小难度和
状态转移方程: f[i][j] = min{ f[i-1][k] + maxDifficulty(k + 1, j) }, 其中第 i 天完成的任务就是第 k + 1 项到第 j 项, 枚举 k.
初始状态: f[0][0] = 0, 其他均为 INF
最终答案: f[d][n] 即 d 天完成全部 n 项任务的最小难度和
非法情况: 即无法完成任务的情况. 在 n < d 时无法做到每天至少完成一项任务, 此时应该返回 -1
时间复杂度: o(n^3) = 状态数量 o(n^2) *times 状态转移时间\ o(n)
空间复杂度: o(n^2)
优化: 动态规划可以使用滚动数组将空间优化到 o(n), 并且 maxd 数组可以使用 ST 表优化到 $o(nlogn)$ 的时空复杂度. 但是由于动态规划仍然要花费 o(n^3) 的时间, 所以使用 ST 表并不能显著优化整体运行时间.
代码展示
class Solution { public int minDifficulty(int[] jobDifficulty, int d) { if (jobDifficulty == null || jobDifficulty.length < d) { return -1; } final int INF = 0x3f3f3f3f; int n = jobDifficulty.length; int[][] f = new int[d + 1][n + 1]; int[][] maxd = new int[n][n]; // 初始化 f for (int i = 0; i <= d; i++) { Arrays.fill(f[i], INF); } f[0][0] = 0; // 预处理 maxd 数组 for (int i = 0; i < n; i++) { maxd[i][i] = jobDifficulty[i]; } for (int i = 1; i < n; i++) { for (int j = 0; j + i < n; j++) { maxd[j][j + i] = Math.max(maxd[j][j + i - 1], jobDifficulty[j + i]); } } // 动态规划递推 for (int i = 1; i <= d; i++) { for (int j = i; j <= n; j++) { for (int k = i - 1; k < j; k++) { f[i][j] = Math.min(f[i][j], f[i - 1][k] + maxd[k][j - 1]); // f: 1-indexed maxd: 0-indexed } } } return f[d][n]; } }今天一定要努力刷题
绝对不会浪费时间
想要了解最新的最新的周赛题解信息，可以入群与大佬们交流~
-
-
创作新主题