日常算法刷题

👨‍💻 关于作者：会编程的土豆

“不是因为看见希望才坚持，而是坚持了才看见希望。”

你好，我是会编程的土豆，一名热爱后端技术的Java学习者。

📚正在更新中的专栏：

• 《数据结构与算法》😊😊😊

• 《leetcode hot 100》🥰🥰🥰🤩🤩🤩

• 《数据库mysql》

💕作者简介：后端学习者

1.

#include<iostream> #include<vector> #include<algorithm> using namespace std; int main() { string s; cin >> s; int n = s.size(); vector<vector<int>>dp(n + 1, vector<int>(n + 1)); string t = s; reverse(s.begin(), s.end()); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (s[i - 1] == t[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]); } } } cout << n - dp[n][n] << endl; return 0; }

经典 LCS（最长公共子序列），所谓公共子序列，就是可以不连续的，两个字符串中相同的部分，比如Ab3bd和db3bA，公共子序列就是b3b；

那么这个题为什么要使用公共子序列呢，诶，很有意思，这个题要求回文字串，回文子串就是正反一样的那种，他问要几个字母才能构成，非常有意思，咱们把原来的字符串反过来，然后求这个字符串和原来的字符串的公共子序列，这个公共子序列就是回文一样的，咱们用总字符串大小减去这个大小就是答案；

2.

#include<iostream> #include<vector> #include<algorithm> using namespace std; int main() { vector<int>arr; int x; while (cin >> x) { arr.push_back(x); } reverse(arr.begin(), arr.end()); vector<int>tail; for (int i = 0; i < arr.size(); i++) { int x = arr[i]; auto it = upper_bound(tail.begin(), tail.end(), x); if (it == tail.end()) { tail.push_back(x); } else { *it = x; } } cout << tail.size() << endl; reverse(arr.begin(), arr.end()); vector<int>g; for (int i = 0; i < arr.size(); i++) { int x = arr[i]; auto it = lower_bound(g.begin(), g.end(), x); if (it == g.end()) { g.push_back(x); } else *it = x; } cout << g.size() << endl; return 0; }

这个需要注意的是用while作为输入，那么结束的时候就需要Ctrl+Z一下；

两个小问，第一问要求求出最长的那个导弹长度，题目要求递减，咱们倒过来就是求递增，因为算法只会求递增哈；

第二问求有几个递减序列，咱们把原始数组递增的个数求出来，就是有几个递减的；

3.

#include<iostream> #include<vector> #include<algorithm> using namespace std; typedef struct node { int u, v, w; }node; vector<int>parent; vector<node>arr; vector<bool>enemy; int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); } return parent[x]; } bool f(node a, node b) { return a.w > b.w; } int main() { int N, K; cin >> N >> K; enemy.resize(N + 1, false); parent.resize(N + 1); for (int i = 1; i <= N; i++) parent[i] = i; for (int i = 1; i <= K; i++) { int mmm; cin >> mmm; enemy[mmm] = true; } long long ssum = 0; for (int i = 1; i <= N - 1; i++) { int u, v, w; cin >> u >> v >> w; ssum += w; arr.push_back({ u,v,w }); } sort(arr.begin(), arr.end(), f); long long sum = 0; for (int i = 0; i < arr.size(); i++) { int u = arr[i].u; int v = arr[i].v; int w = arr[i].w; int rootu = find(u); int rootv = find(v); if (!(enemy[rootu] && enemy[rootv])) { if (rootu != rootv) { parent[rootu] = rootv; sum += w; enemy[rootv] = enemy[rootu] || enemy[rootv]; } } } cout << ssum - sum << endl; return 0; }