On the shoulders of giants.

weekly-contest-173

删除回文子序列

给你一个字符串 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 是一种最小代价且合法的方案。

时间复杂度:\(O(n)\)

class Solution {
public:
    int removePalindromeSub(string s) {
        int n = s.length();
        if(n == 0) return 0;
        for(int i = 0; i < n / 2; i++) {
            if(s[i] != s[n-1-i]) return 2;
        }
        return 1;
    }
};

餐厅过滤器

给你一个餐馆信息数组 restaurants,其中  restaurants[i] = [idi, ratingi, veganFriendlyi, pricei, distancei]。你必须使用以下三个过滤器来过滤这些餐馆信息。

其中素食者友好过滤器 veganFriendly 的值可以为 true 或者 false,如果为 true 就意味着你应该只包括 veganFriendlyi 为 true 的餐馆,为 false 则意味着可以包括任何餐馆。此外,我们还有最大价格 maxPrice 和最大距离 maxDistance 两个过滤器,它们分别考虑餐厅的价格因素和距离因素的最大值。

过滤后返回餐馆的 id,按照 rating 从高到低排序。如果 rating 相同,那么按 id 从高到低排序。简单起见, veganFriendlyiveganFriendly 为 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 各不相同。
题解

模拟,直接将合法的餐厅信息加入新数组,然后排序。

时间复杂度:\(O(n\log n)\)

class Solution {
public:
    vector<int> filterRestaurants(vector<vector<int>>& restaurants, int veganFriendly, int maxPrice, int maxDistance) {
        vector<pair<int, int>> ans;
        for(auto restaurant : restaurants) {
            if(restaurant[2] < veganFriendly) continue;
            if(maxPrice < restaurant[3]) continue;
            if(maxDistance < restaurant[4]) continue;
            ans.push_back(make_pair(-restaurant[1], -restaurant[0]));
        }
        sort(ans.begin(), ans.end());
        vector<int> result;
        for(auto x : ans) {
            result.push_back(-x.second);
        }
        return result;
    }
};

阈值距离内邻居最少的城市

n 个城市,按从 0n-1 编号。给你一个边数组 edges,其中 edges[i] = [fromi, toi, weighti] 代表 fromi 和 toi两个城市之间的双向加权边,距离阈值是一个整数 distanceThreshold

返回能通过某些路径到达其他城市数目最少、且路径距离 最大 为 distanceThreshold 的城市。如果有多个这样的城市,则返回编号最大的城市。

注意,连接城市 ij 的路径的距离等于沿该路径的所有边的权重之和。

示例 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) 都是不同的。
题解

两点间的距离应该用最短距离表示,即求出任意两点间的最短路,然后记录合法个数。

时间复杂度:\(O(n^3+n^2)\)

const int N = 1E2 + 10;
class Solution {
private:
    int dis[N][N];
public:
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        int id, lim = N;
        memset(dis, 0x3f, sizeof(dis));
        for(int i = 0; i < n; i++) dis[i][i] = 0;
        for(auto 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 = 0; j < n; j++) {
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
                }
            }
        }
        for(int i = 0; i < n; i++) {
            int count = 0;
            for(int j = 0; j < n; j++) {
                if(i != j && dis[i][j] <= distanceThreshold) count++;
            }
            // cout << i << " : " << count << endl;
            if(count <= lim) lim = count, id = i;
        }
        return id;
    }
};

工作计划的最低难度

你需要制定一份 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_{d,k} \) 为工作完第 d 天已做完前 k 个任务的最小代价。

动态转移:

\(dp_{d,k}=\min \left \{ dp_{d-1,i}+cost(i+1,k) \right \}\)

其中 \(0 \leq i < k\),\(cost(x,y)\) 为任务 x 至任务 y 的最大难度。

最终答案为:\(dp_{d,n}\)

时间复杂度:\(O(dn^2)\)

class Solution {
public:
    int minDifficulty(vector<int>& jobDifficulty, int d) {
        int n  = jobDifficulty.size();
        if(n < d) return -1;
        vector<vector<int>> dp(d + 1, vector<int> (n + 1));
        for(int i = 0; i <= d; i++)
            for(int j = 0; j <= n; j++) dp[i][j] = 1E9;
        dp[0][0] = 0;
        for(int k = 1; k <= d; k++) {
            for(int i = 0; i <= n; i++) {
                int Max = -1;
                for(int j = i + 1; j <= n; j++) {
                    Max = max(Max, jobDifficulty[j - 1]);
                    dp[k][j] = min(dp[k][j], dp[k - 1][i] + Max);
                }
            }
        }
        return dp[d][n];
    }
};
Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注