sort()和最短编辑距离

算法

力扣302周赛t3

c++自定义排序规则~

class Solution {
public:
    vector<int> smallestTrimmedNumbers(vector<string>& nums, vector<vector<int>>& qs) {
        int n = nums.size(), m = qs.size();
        vector<pair<string, int>> str(n);
        for(int i = 0; i < n; i ++)     str[i] = {nums[i], i};
        vector<int> ans;
        for(int i = 0; i < m; i ++) {
            int k = qs[i][0], trim = qs[i][1];
            sort(str.begin(), str.end(), [&](pair<string, int>& a, pair<string, int>& b) {
                for(int i = a.first.size() - trim; i < a.first.size(); i ++) 
                    if(a.first[i] < b.first[i])
                        return true;
                    else if(a.first[i] > b.first[i])
                        return false;
                return a.second < b.second;
            });
            ans.push_back(str[k - 1].second);
        }
        return ans;
    }
};

最长上升子序列II

贪心，找到整个序列中递增序列中最长的那个，用个中间数组存下递增序列，每次二分找到每个数该放的位置

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 100010;

int a[N];
int q[N];
int n;

int main() {
    cin >> n;
    for(int i = 0; i < n; i ++)
        cin >> a[i];
        
    int len = 0;
    q[0] = -2e9;
    for(int i = 0; i < n; i ++) {
        int l = 0, r = len;
        while(l < r) {
            int mid = l + r + 1 >> 1;
            if(q[mid] < a[i])   l = mid;
            else    r = mid - 1;
        }
        q[r + 1] = a[i];
        len = max(len, r + 1);
    }
    cout << len << endl;
    
    return 0;
}

最长公共子序列

f[i][j]表示的是a字符串前i个字母和b字符串前j个字母中公共子序列的最大值。

根据a[i]和b[j]的选择情况来划分集合。①不选i,j；②不选i，选j；③选i，不选j；④选i,j。

#include<iostream>

using namespace std;

const int N = 1010;

int n, m;
char a[N], b[N];
int f[N][N];

int main() {
    cin >> n >> m;
    scanf("%s%s", a + 1, b + 1);
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++) {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if(a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
        }
    cout << f[n][m] << endl;
    return 0;
}

最短编辑距离

集合划分从题目中所给的三个操作来分析；①替换，如果a[i] != b[j], f[i - 1][j - 1] + 1，否则f[i - 1][j -1]；②增加，f[i][j - 1] + 1；③删除，f[i - 1][j] + 1。

需要初始化！！

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010;

char a[N], b[N];
int n, m;
int f[N][N]; //fij表示第a中i个字母变化到b中第j个字母所需要的最少操作次数。

int main() {
    scanf("%d%s", &n, a + 1);
    scanf("%d%s", &m, b + 1);
    
    for(int i = 0; i <= n; i ++)    f[i][0] = i;
    for(int i = 0; i <= m; i ++)    f[0][i] = i;
    
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++) {
            f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;
            f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] == b[j] ? 0 : 1));
        }
    
    cout << f[n][m] << endl;
    return 0;
}

动态规划总结

• 初始化
  • 非入口初始化为无穷（如果要求最大值，初始化为负无穷，求最小值初始化为正无穷），入口按状态表示初始化。不需要对要计算的状态初始化。
• 状态转移
  • 从前一个状态想象，如背包问题思考第i个物品选与不选；最长上升子序列考虑第i-1个数是多少；最长公共子序列考虑a中第i个字母和b中第j个字母选与不选的情况；最短编辑距离考虑的是三种操作。总之，就是考虑它可以从哪些状态转移过来，或者说可以进行哪些操作到达这一步。

编辑距离

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 20, M = 1010;

int n, m;
char str[M][N];

int fun(char a[], char b[]) {
    int l1 = strlen(a + 1), l2 = strlen(b + 1);
    int f[N][N];
    
    for(int i = 0; i <= l1; i ++)   f[i][0] = i;
    for(int i = 0; i <= l2; i ++)   f[0][i] = i;
    
    for(int i = 1; i <= l1; i ++)
        for(int j = 1; j <= l2; j ++) {
            f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;
            f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] != b[j]));
        }
    return f[l1][l2];
}

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) {
        scanf("%s", str[i] + 1);
    }
    
    while(m --) {
        char s[N];
        int x;
        scanf("%s%d", s + 1, &x);
        int res = 0;
        for(int i = 1; i <= n; i ++) {
            if(fun(str[i], s) <= x)  res ++;
        }
        cout << res << endl;
    }
    return 0;
}