LeetCode 第 211 场周赛

模拟枚举

 1 class Solution {
 2 public:
 3     int maxLengthBetweenEqualCharacters(string s) {
 4         int n = s.size();
 5         int ans = -1;
 6         for (int i = 0; i < n; i++) {
 7             for (int j = i + 1; j < n; j++) {
 8                 if (s[i] == s[j]) {
 9                     ans = max(ans, j - i - 1);
10                 }
11             }
12         }
13         return ans;
14     }
15 };

View Code

B 执行操作后字典序最小的字符串

DFS + 剪枝

 1 class Solution {
 2 public:
 3     string ans;
 4     map<string, int> m;
 5     void dfs(string s, int a, int b) {
 6         if (m[s]) return ;
 7         m[s] = 1;
 8         ans = min(ans, s);
 9         string str = s;
10         for (int i = 1; i < str.size(); i += 2) {
11             int x = (str[i] - '0' + a) % 10;
12             str[i] = (x + '0');
13         }
14         dfs(str, a, b);
15         str = s.substr(s.size() - b, b) + s.substr(0, s.size() - b);
16         dfs(str, a, b);
17     }
18     string findLexSmallestString(string s, int a, int b) {
19         ans = s;
20         dfs(s, a, b);
21         return ans;
22     }
23 };

View Code

C 无矛盾的最佳球队

先按年龄为第一优先级从小到大排序, 再按分数为第二优先级从小到大排序, 保证能形成分数递增, 把题目转换成最长递增子序列的题目, 再走下DP就好了

 1 class Solution {
 2 public:
 3     struct node{
 4         int scores, ages;
 5     }q;
 6     static bool cmp(node x, node y) {
 7         if (x.ages == y.ages) {
 8             return x.scores < y.scores;
 9         }
10         return x.ages < y.ages;
11     }
12     int bestTeamScore(vector<int>& scores, vector<int>& ages) {
13         int n = ages.size(), ans = 0;
14         vector<node> p;
15         vector<int> dp(n, 0);
16         for (int i = 0; i < n; i++) {
17             q.ages = ages[i];
18             q.scores = scores[i];
19             p.push_back(q);
20         }
21         sort(p.begin(), p.end(), cmp);
22         for (int i = 0; i < n; i++) {
23             for (int j = 0; j < i; j++) {
24                 if (p[j].scores <= p[i].scores) dp[i] = max(dp[i], dp[j]);
25             }
26             dp[i] += p[i].scores;
27             ans = max(ans, dp[i]);
28         }
29         return ans;
30     }
31 };

View Code

D 带阈值的图连通性

思考 + 并查集

 1 class Solution {
 2 public:
 3     int fi(int x, vector<int>& fa) {
 4         return x == fa[x] ? x : fa[x] = fi(fa[x], fa);
 5     }
 6     vector<bool> areConnected(int n, int threshold, vector<vector<int>>& queries) {
 7         vector<bool> ans;
 8         vector<int> fa(n + 1, 0);
 9         for (int i = 1; i <= n; i++) fa[i] = i;
10         for (int i = threshold + 1; i <= n; i++) {
11             for (int j = 2 * i; j <= n; j += i) {
12                 int fx = fi(i, fa), fy = fi(j, fa);
13                 if (fx != fy) fa[fx] = fy;    
14             }
15         }
16         int m = queries.size();
17         for (int i = 0; i < m; i++) {
18             int fx = fi(queries[i][0], fa), fy = fi(queries[i][1], fa);
19             ans.push_back(fx == fy);
20         }
21         return ans;
22     }
23 };

View Code