1.删除回文子序列
题目描述
给你一个字符串 s，它仅由字母 'a' 和 'b' 组成。每一次删除操作都可以从 s 中删除一个回文 子序列。
返回删除给定字符串中所有字符（字符串为空）的最小删除次数。
「子序列」定义：如果一个字符串可以通过删除原字符串某些字符而不改变原字符顺序得到，那么这个字符串就是原字符串的一个子序列。
「回文」定义：如果一个字符串向后和向前读是一致的，那么这个字符串就是一个回文。
示例 1：
输入：s = "ababa"
输出：1
解释：字符串本身就是回文序列，只需要删除一次。
示例 2：
输入：s = "abb"
输出：2
解释："abb" -> "bb" -> "".
先删除回文子序列 "a"，然后再删除 "bb"。
示例 3：
输入：s = "baabb"
输出：2
解释："baabb" -> "b" -> "".
先删除回文子序列 "baab"，然后再删除 "b"。
示例 4：
输入：s = ""
输出：0
提示：
0 <= s.length <= 1000
s 仅包含字母 'a' 和 'b'
个人思路
如果是回文串，则一次即可删除，如果不是回文串，那么把所有a或者所有b删除后，剩下的一定是回文的，即再删除一次即可。
所以，答案区间[0-2]。
AC代码
class Solution {
public int removePalindromeSub(String s) {
if (s == null || s.length() == 0) return 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) != s.charAt(s.length() - i - 1)) return 2;
}
return 1;
}
}
题目链接：https://leetcode-cn.com/problems/remove-palindromic-subsequences/
2.餐厅过滤器
题目描述
给你一个餐馆信息数组 restaurants，其中 restaurants[i] = [idi, ratingi, veganFriendlyi, pricei, distancei]。你必须使用以下三个过滤器来过滤这些餐馆信息。
其中素食者友好过滤器 veganFriendly 的值可以为 true 或者 false，如果为 true 就意味着你应该只包括 veganFriendlyi 为 true 的餐馆，为 false 则意味着可以包括任何餐馆。此外，我们还有最大价格 maxPrice 和最大距离 maxDistance 两个过滤器，它们分别考虑餐厅的价格因素和距离因素的最大值。
过滤后返回餐馆的 id，按照 rating 从高到低排序。如果 rating相同，那么按 id从高到低排序。简单起见， veganFriendlyi 和 veganFriendly为 true 时取值为 1，为 false 时，取值为 0 。
示例 1：
输入：restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 1, maxPrice = 50, maxDistance = 10
输出：[3,1,5]
解释：
这些餐馆为：
餐馆 1 [id=1, rating=4, veganFriendly=1, price=40, distance=10]
餐馆 2 [id=2, rating=8, veganFriendly=0, price=50, distance=5]
餐馆 3 [id=3, rating=8, veganFriendly=1, price=30, distance=4]
餐馆 4 [id=4, rating=10, veganFriendly=0, price=10, distance=3]
餐馆 5 [id=5, rating=1, veganFriendly=1, price=15, distance=1]
在按照 veganFriendly = 1, maxPrice = 50 和 maxDistance = 10 进行过滤后，我们得到了餐馆 3, 餐馆 1 和 餐馆 5（按评分从高到低排序）。
示例 2：
输入：restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 0, maxPrice = 50, maxDistance = 10
输出：[4,3,2,1,5]
解释：餐馆与示例 1 相同，但在 veganFriendly = 0 的过滤条件下，应该考虑所有餐馆。
示例 3：
输入：restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 0, maxPrice = 30, maxDistance = 3
输出：[4,5]
提示：
- 1 <= restaurants.length <= 10^4
- restaurants[i].length == 5
- 1 <= idi, ratingi, pricei, distancei <= 10^5
- 1 <= maxPrice, maxDistance <= 10^5
- veganFriendlyi 和 veganFriendly 的值为 0 或 1 。
- 所有 id 各不相同。
个人思路
这题不难,就是写起来有点麻烦
AC代码
class Solution {
static class Item implements Comparable<Item> {
int id;
int rating;
public Item(int id, int rating) {
this.id = id;
this.rating = rating;
}
public int compareTo(Item a) {
if (this.rating != a.rating) return a.rating - this.rating;
else return a.id - this.id;
}
}
public List<Integer> filterRestaurants(int[][] restaurants, int veganFriendly, int maxPrice, int maxDistance) {
int row = restaurants.length;
int col = restaurants[0].length;
List<Item> list = new ArrayList<Item>();
List<Integer> ans = new ArrayList<Integer>();
for (int i = 0; i < row; i++) {
if (veganFriendly == 1) {
if (restaurants[i][2] == 1 && restaurants[i][3] <= maxPrice && restaurants[i][4] <= maxDistance) {
list.add(new Item(restaurants[i][0], restaurants[i][1]));
}
} else {
if (restaurants[i][3] <= maxPrice && restaurants[i][4] <= maxDistance) {
list.add(new Item(restaurants[i][0], restaurants[i][1]));
}
}
}
Collections.sort(list);
for (int i = 0; i < list.size(); i++) {
ans.add(list.get(i).id);
}
return ans;
}
}
题目链接：https://leetcode-cn.com/problems/filter-restaurants-by-vegan-friendly-price-and-distance/
3.阈值距离内邻居最少的城市
题目描述
有 n 个城市，按从 0 到 n-1 编号。给你一个边数组 edges，其中 edges[i] = [fromi, toi, weighti] 代表 fromi 和 toi 两个城市之间的双向加权边，距离阈值是一个整数 distanceThreshold。
返回能通过某些路径到达其他城市数目最少 且路径距离 最大 为 distanceThreshold 的城市。如果有多个这样的城市，则返回编号最大的城市。
注意，连接城市 i 和 j 的路径的距离等于沿该路径的所有边的权重之和。
示例 1：
输入：n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
输出：3
解释：城市分布图如上。
每个城市阈值距离 distanceThreshold = 4 内的邻居城市分别是：
城市 0 -> [城市 1, 城市 2]
城市 1 -> [城市 0, 城市 2, 城市 3]
城市 2 -> [城市 0, 城市 1, 城市 3]
城市 3 -> [城市 1, 城市 2]
城市 0 和 3 在阈值距离 4 以内都有 2 个邻居城市，但是我们必须返回城市 3，因为它的编号最大。
示例 2：
输入：n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2
输出：0
解释：城市分布图如上。
每个城市阈值距离 distanceThreshold = 2 内的邻居城市分别是：
城市 0 -> [城市 1]
城市 1 -> [城市 0, 城市 4]
城市 2 -> [城市 3, 城市 4]
城市 3 -> [城市 2, 城市 4]
城市 4 -> [城市 1, 城市 2, 城市 3]
城市 0 在阈值距离 4 以内只有 1 个邻居城市。
提示
- 2 <= n <= 100
- 1 <= edges.length <= n * (n - 1) / 2
- edges[i].length == 3
- 0 <= fromi < toi < n
- 1 <= weighti, distanceThreshold <= 10^4
- 所有 (fromi, toi) 都是不同的。
个人思路
刚开始是想直接从一个点开始搜索,看在距离阙值之类能到的点的数量,可是不知道为什么不对,有几个测试用例死活过不去
后来才想到可以用dijkstra算法,求出到各个点的最短路径,找出能在距离阈值范围之内的点最少的那个, floyd也行,不过不会
AC代码
class Solution {
private int []vis;
private int[][] map;
private int ans, min = Integer.MAX_VALUE;
public int findTheCity(int n, int[][] edges, int distanceThreshold) {
map = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
map[i][j] = Integer.MAX_VALUE;
}
}
for (int[] edge : edges) {
int v = edge[0];
int e = edge[1];
int w = edge[2];
map[v][e] = w;
map[e][v] = w;
}
for (int i = 0; i < n; i++) {
dijkstra(i, n, distanceThreshold);
}
return ans;
}
public void dijkstra(int v0, int n, int distanceThreshold) {
boolean[] s = new boolean[n];
int []dist = new int[n];
for (int i = 0; i < n; i++) {
s[i] = false;
dist[i] = map[v0][i];
}
dist[v0] = 0;
s[v0] = true;
int v = 0;
for (int i = 1; i < n - 1; i++) {
int min = Integer.MAX_VALUE;
for (int w = 0; w < n; w++) {
if (!s[w] && dist[w] < min) {
v = w;
min = dist[w];
}
}
s[v] = true;
for (int j = 0; j < n; j++) {
if (!s[j] && (min + map[v][j] < dist[j]) && map[v][j] != Integer.MAX_VALUE) {
dist[j] = min + map[v][j];
}
}
}
int cnt = 0;
for (int i = 0; i < dist.length; i++) {
if (dist[i] != 0 && dist[i] <= distanceThreshold) {
cnt++;
}
}
if (min >= cnt) {
min = cnt;
ans = v0;
}
}
}
有几个测试用例过不去
class Solution {
static class Edge {
int v, e, w;
public Edge(int v, int e, int w) {
this.v = v;
this.e = e;
this.w = w;
}
}
private int []vis;
private List<Edge>[]adj;
private int[] at;
public int findTheCity(int n, int[][] edges, int distanceThreshold) {
vis = new int [n + 1];
adj = new ArrayList[n + 1];
at = new int [n + 1];
Arrays.fill(at, 0);
for (int i = 0; i < n; i++) {
adj[i] = new ArrayList<Edge>();
}
for (int i = 0; i < edges.length; i++) {
int v = edges[i][0];
int e = edges[i][1];
int w = edges[i][2];
adj[v].add(new Edge(v, e, w));
adj[e].add(new Edge(e, v, w));
}
for (int i = 0; i < n; i++) {
Arrays.fill(vis, 0);
dfs(distanceThreshold, i, 0, i);
}
int min = 999;
int ans = 0;
for (int i = 0; i < n; i++) {
System.out.println(at[i]);
if (at[i] <= min) {
min = at[i];
ans = i;
}
}
return ans;
}
private void dfs(int distanceThreshold, int cur, int sum, int p) {
vis[cur] = 1;
for (int i = 0; i < adj[cur].size(); i++) {
sum += adj[cur].get(i).w;
if (vis[adj[cur].get(i).e] == 0 && sum <= distanceThreshold) {
at[p] += 1;
dfs(distanceThreshold, adj[cur].get(i).e, sum, p);
}
sum -= adj[cur].get(i).w;
}
}
}
4.工作计划的最低难度
题目描述
你需要制定一份 d 天的工作计划表。工作之间存在依赖，要想执行第 i 项工作，你必须完成全部 j 项工作（ 0 <= j < i）。
你每天 至少 需要完成一项任务。工作计划的总难度是这 d 天每一天的难度之和，而一天的工作难度是当天应该完成工作的最大难度。
给你一个整数数组 jobDifficulty 和一个整数 d，分别代表工作难度和需要计划的天数。第 i 项工作的难度是 jobDifficulty[i]。
返回整个工作计划的 最小难度 。如果无法制定工作计划，则返回 -1 。
示例 1：
输入：jobDifficulty = [6,5,4,3,2,1], d = 2
输出：7
解释：第一天，您可以完成前 5 项工作，总难度 = 6.
第二天，您可以完成最后一项工作，总难度 = 1.
计划表的难度 = 6 + 1 = 7
示例 2：
输入：jobDifficulty = [9,9,9], d = 4
输出：-1
解释：就算你每天完成一项工作，仍然有一天是空闲的，你无法制定一份能够满足既定工作时间的计划表。
示例 3：
输入：jobDifficulty = [1,1,1], d = 3
输出：3
解释：工作计划为每天一项工作，总难度为 3 。
示例 4：
输入：jobDifficulty = [7,1,7,1,7,1], d = 3
输出：15
示例 5：
输入：jobDifficulty = [11,111,22,222,33,333,44,444], d = 6
输出：843
提示
- 1 <= jobDifficulty.length <= 300
- 0 <= jobDifficulty[i] <= 1000
- 1 <= d <= 10
个人思路
没有思路，没做出来
题目链接：https://leetcode-cn.com/problems/minimum-difficulty-of-a-job-schedule/
Q.E.D.
