5319. 删除回文子序列 顯示英文描述
給你一個字元串 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’
思路
腦筋急轉彎題。
由于字元串隻含有兩種字元，而且題目要求删除的是子序列而不是子串（『子序列』可以是不連續的），是以隻需要進行2個判斷：
- 字元串是否為空。如果字元串為空，則隻需删除0次；
- 字元串是否本身是回文串。如果字元串本身是回文串，則隻需删除一次；
對于剩下的字元串，第一次删除所有的’a’，第二次删除所有的’b’，需要删除的次數為2
代碼
class Solution {
private boolean checkHuiwen(String s) {
int n = s.length(), i = 0;
if (n == 1) {
return true;
}
for (i = 0; i < n/2; ++i) {
if (s.charAt(i) != s.charAt(n - 1 - i)) {
return false;
}
}
return true;
}
public int removePalindromeSub(String s) {
if (s.isEmpty()) {
return 0;
}
if (checkHuiwen(s)) {
return 1;
} else {
return 2;
}
}
}
5320. 餐廳過濾器 顯示英文描述
給你一個餐館資訊數組 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 。
所有 idi 各不相同。
思路
對于Java來說，這道題更像是文法題而不是算法題。
代碼
class Solution {
private class Restaurant implements Comparable<Restaurant> {
public int id, rating;
public Restaurant(int id, int rating) {
this.id = id;
this.rating = rating;
}
@Override
public int compareTo(Restaurant other) {
if (rating == other.rating) {
return other.id - id;
} else {
return other.rating - rating;
}
}
}
public List<Integer> filterRestaurants(int[][] restaurants, int veganFriendly, int maxPrice, int maxDistance) {
ArrayList<Restaurant> rests = new ArrayList<>();
for (int[] rest: restaurants) {
if (!(veganFriendly == 1 && rest[2] == 0) && rest[3] <= maxPrice && rest[4] <= maxDistance) {
rests.add(new Restaurant(rest[0], rest[1]));
}
}
Collections.sort(rests);
ArrayList<Integer> ids = new ArrayList<>();
for (Restaurant rest: rests) {
ids.add(rest.id);
}
return ids;
}
}
5321. 門檻值距離内鄰居最少的城市 顯示英文描述
有 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) 都是不同的。
思路
弗洛伊德算法求n to n最短路. 可惜比賽的時候弗洛伊德算法也錯了，有點遺憾
代碼
class Solution {
public int findTheCity(int n, int[][] edges, int distanceThreshold) {
int[][] dis = new int[n][n];
for (int[] edge: edges) {
dis[edge[0]][edge[1]] = edge[2];
dis[edge[1]][edge[0]] = edge[2];
}
for (int k=0; k<n; ++k) {
for (int i=0; i<n; ++i) {
for (int j=i+1; j<n; ++j) {
if (i != j && i != k && j != k && dis[i][k] != 0 && dis[k][j] != 0 && ((dis[i][j] == 0) || (dis[i][k] + dis[k][j] < dis[i][j]))) {
int tmp = dis[i][k] + dis[k][j];
dis[i][j] = tmp;
dis[j][i] = tmp;
}
}
}
}
int cnt = 0, cntMin = Integer.MAX_VALUE, idMin = -1;
for (int i=0; i<n; ++i) {
cnt = 0;
for (int j=0; j<n; ++j) {
if (dis[i][j] != 0 && dis[i][j] <= distanceThreshold) {
++cnt;
}
}
if (cnt <= cntMin) {
cntMin = cnt;
idMin = i;
}
}
return idMin;
}
}
5322. 工作計劃的最低難度 顯示英文描述
你需要制定一份 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
思路
二維動态規劃。
dp[i][j]
表示用
j
天完成前
i
項工作的最小難度值。注意邊界情況
dp[0][j]
和
dp[i][0]
的處理
代碼
class Solution {
private static final int INF = 0x3f3f3f3f;
public int minDifficulty(int[] jobDifficulty, int d) {
int n = jobDifficulty.length, i = 0, j = 0, k = 0;
if (n < d) {
return -1;
}
int[][] dp = new int[n+1][d+1], subMax = new int[n][n];
for (i=0; i<n; ++i) {
subMax[i][i] = jobDifficulty[i];
}
for (i=0; i<n-1; ++i) {
for (j=i+1; j<n; ++j) {
subMax[i][j] = Math.max(subMax[i][j-1], jobDifficulty[j]);
}
}
for (j=1; j<=d; ++j) {
dp[0][j] = INF;
}
for (i=1; i<=n; ++i) {
dp[i][0] = INF;
}
for (i=1; i<=n; ++i) {
for (j=1; j<=d; ++j) {
dp[i][j] = INF;
for (k=0; k<i; ++k) {
dp[i][j] = Math.min(dp[i][j], dp[k][j-1] + subMax[k][i-1]);
}
}
}
return dp[n][d];
}
}