第 173 场周赛

Posted on | In , | |
Words count in article: 503 | Reading time ≈ 3

1332. 删除回文子序列

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int removePalindromeSub(string s) {
        if(s == "") return 0;
        for(int l=0, r=s.size()-1; l < r; l++, r--)
            if(s[l] != s[r])
                return 2;
        return 1;
    }
};

1333. 餐厅过滤器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool cmp(vector<int>& a, vector<int>& b){
    if(a[1] == b[1])
        return a[0] > b[0];
    return a[1] > b[1];
}

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        vector<vector<int>> D(n, vector<int>(n, INT_MAX));
        for (auto& e : edges) {
        	D[e[0]][e[1]] = e[2];
        	D[e[1]][e[0]] = e[2];
        }
        for (int k = 0; k < n; k++) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (i == j || D[i][k] == INT_MAX || D[k][j] == INT_MAX)
						continue;
					D[i][j] = min(D[i][k]+D[k][j], D[i][j]);
				}
			}
		}
        int ret;
        int minNum = INT_MAX;
        for (int i = 0; i < n; i++) {
        	int cnt = 0; 
        	for (int j = 0; j < n; j++) {
        		if (i != j && D[i][j] <= distanceThreshold) {
        			cnt++;
        		}
        	}
        	if (cnt <= minNum) {
        		minNum = cnt;
        		ret = i;
        	}
        }
        return ret;
    }
};

1335. 工作计划的最低难度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int minDifficulty(vector<int>& jobDifficulty, int d) {
        if(jobDifficulty.size() < d) return -1;
        int n = jobDifficulty.size(), day = d;
        vector<vector<int>> dp(n, vector<int>(d, INT_MAX));
        dp[0][0] = jobDifficulty[0];
        for(int i=1; i<n; i++){
            dp[i][0] = max(dp[i-1][0], jobDifficulty[i]);
        }
        for(int d=1; d<day; d++){
            for(int i=d; i<n; i++){
                int maxd = INT_MIN;
                for(int k=i-1; k>=d-1; k--){
                    maxd = max(maxd, jobDifficulty[k+1]);
                    dp[i][d] = min(dp[i][d], dp[k][d-1]+maxd);
                }
            }
        }
        return dp[n-1][day-1];
    }
};
Donate? comment?