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'

代码

viv丑陋版

我笑死了,这题我的反应居然这么快,大概是无知者无畏。
因为题目中说只有a、b两个字母,所以删除次数的上界是2。
如果是空串,返回0。否则如果是回文串,返回1。
剩下不是回文串的情况,出现几种字母返回几。

class Solution {
public:
    int removePalindromeSub(string s) {
        int len = s.size();
        if(len == 0) return 0;
        if(len == 1) return 1;
        bool flag = true;
        for(int i=0; i<len/2; i++) {
            if(s[i] != s[len-1-i]) flag = false;
        }
        if(flag) return 1;
        else { // flag = false;
            for(int i=1; i<len; i++) {
                if(s[i] != s[i-1]) flag = true;
            }
            if(flag) return 2;
            return 1;
        }
    }
};

zz美丽版

看完zz的发现我还是猪。我服了。
如果是回文串,就包含了只有一个字母的情况呀。

class Solution {
public:
    int removePalindromeSub(string s) {
        int len = s.size();
        if(len == 0) return 0;
        
        bool flag = true;
        for(int i=0; i<len/2; i++) {
            if(s[i] != s[len-1-i]) {
                flag = false; 
                break;
            } 
        }

        if(flag) return 1;
        return 2;
    }
};

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 。
  • 所有 idi 各不相同。

代码

viv丑陋版

水题,首先过滤,然后写个cmp函数排序。
然而比赛的时候有锅,没说rating相同怎么排,我很生气。

bool cmp(vector<int> &a, vector<int> &b) {
    if(a[1] != b[1]) return a[1] > b[1];
    else return a[0] > b[0];
}
class Solution {
public:
    vector<int> filterRestaurants(vector<vector<int>>& restaurants, int veganFriendly, int maxPrice, int maxDistance) {
        int len = restaurants.size();
        vector<vector<int>> ans;
        for(int i=0; i<len; i++) {
            vector<int> cur = restaurants[i];
            if(veganFriendly == 1 && cur[2] == 0) continue;
            if(maxPrice < cur[3]) continue;
            if(maxDistance < cur[4]) continue;
            ans.push_back(cur);
        }
        sort(ans.begin(), ans.end(), cmp);
        int siz = ans.size();
        vector<int> ret;
        for(int i=0; i<siz; i++) ret.push_back(ans[i][0]);
        return ret;
    }
};

zz美丽版

瞄了一眼代码,几乎一模一样,开心。
希望我也能记住这个auto的用法。

inline bool cmp(vector<int> &a, vector<int> &b) {
    if(a[1] != b[1]) return a[1] > b[1];
    else return a[0] > b[0];
}
class Solution {
public:
    vector<int> filterRestaurants(vector<vector<int>>& restaurants, int veganFriendly, int maxPrice, int maxDistance) {
        int len = restaurants.size();
        vector<vector<int>> ans;
        for(int i=0; i<len; i++) {
            vector<int> cur = restaurants[i];
            if(veganFriendly == 1 && cur[2] == 0) continue;
            if(maxPrice < cur[3]) continue;
            if(maxDistance < cur[4]) continue;
            ans.push_back(cur);
        }
        sort(ans.begin(), ans.end(), cmp);
        int siz = ans.size();
        vector<int> ret;
        for(auto r: ans) ret.push_back(r[0]);
        return ret;
    }
};

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 <= $from_i$ < $to_i$ < n
  • 1 <= $weight_i$, distanceThreshold <= 10^4
  • 所有 ($from_i$, $to_i$) 都是不同的。

代码

viv丑陋版

先用Floyd算出每个结点到其余结点的距离,再用阈值过滤,然后按要求返回。
我是猪,Floyd是比赛的时候百度的。

class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        int dist[105][105]; memset(dist, 0x3f, sizeof(dist));
        
        int len = edges.size();
        for(int i=0; i<len; i++) {
            vector<int> cur = edges[i];
            dist[cur[0]][cur[1]] = dist[cur[1]][cur[0]] = cur[2];
        }
        
        for(int k=0; k<n; k++) {
            for(int i=0; i<n; i++) {
                for(int j=0; j<n; j++) {
                    if(dist[i][j] > dist[i][k] + dist[k][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
        
        int mn = 0x3f3f3f3f, ans = -1;
        int cnt[105]; memset(cnt, 0, sizeof(cnt));
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if(i == j) continue;
                if(dist[i][j] <= distanceThreshold) cnt[i]++;
            }
            if(mn >= cnt[i]) {
                mn = cnt[i];
                ans = i;
            }
        }
        return ans;
    }
};

zz美丽版

zz是用spfa写的,让我来复习一下spfa和边表。
挖坑最短路 & 链式前向星。明明学过又忘了TAT。

class Solution {
public:

    vector<pair<int, int>> edge[150];
    queue<int> que;
    int dist[150], vis[150];
    int spfa(int s, int threshold, int n) {
        while(!que.empty()) que.pop();
        memset(vis, 0, sizeof(vis));
        memset(dist, 0x3f, sizeof(dist));
        
        dist[s] = 0; vis[s] = 1; que.push(s);
        while(!que.empty()) {
            int x = que.front(); que.pop();
            for(auto e: edge[x]) {
                int t = e.first, w = e.second;
                if(dist[t] > dist[x] + w) {
                    dist[t] = dist[x] + w;
                    if(vis[t] == 0) {
                        vis[t] = 1;
                        que.push(t);
                    }
                }
            }
            vis[x] = 0;
        }
        
        int ret = 0;
        for(int i=0; i<n; i++) {
            if(dist[i] <= threshold) ret++;
        }
        return ret;
    }
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        for(int i=0; i<n; i++) edge[i].clear();
        for(auto e: edges) {
            edge[e[0]].push_back(make_pair(e[1], e[2]));
            edge[e[1]].push_back(make_pair(e[0], e[2]));
        }

        int ans = -1, mn = n + 1;
        for(int i=0; i<n; i++) {
            int ret = spfa(i, distanceThreshold, n);
            if(ret <= mn) {
                ans = i;
                mn = ret;
            }
        }
        return ans;
    }
};

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

代码

viv丑陋版

不说了。我觉得我需要挖坑简单DP。

zz丑陋版

dp[i][j]表示前i天已经完成了前j个任务。
对于每一个dp[i][j],都需要讨论前i-1天的状态。
假设前i-1天完成的任务数为pre,前i天完成的任务数为cur。
则$1<=cur<=n, 0<=pre<cur$。
倒序遍历pre,可以直接更新mx。
初始条件dp[0][0] = 0。

class Solution {
public:
    int minDifficulty(vector<int>& jobDifficulty, int d) {
        int len = jobDifficulty.size();
        int dp[15][305]; memset(dp, -1, sizeof(dp));
        dp[0][0] = 0;

        for(int i=1; i<=d; i++) {
            for(int cur=1; cur<=len; cur++) {
                int mx = jobDifficulty[cur - 1];
                for(int pre=cur-1; pre>=0; pre--) {
                    if(dp[i-1][pre] != -1) {
                        if(dp[i][cur]==-1 || dp[i][cur]>dp[i-1][pre]+mx)
                            dp[i][cur] = dp[i-1][pre] + mx;
                    }                      
                    if(pre > 0) mx = max(mx, jobDifficulty[pre - 1]);
                }
                printf("%d %d %d\n", i, cur, dp[i][cur]);
            }
        }
        return dp[d][len];
    }
};
最后修改:2020 年 03 月 18 日 11 : 26 AM
如果觉得我的文章对你有用,请随意赞赏