2022-02-13 swipe questions and punch in every day

AcWing - Fundamentals of algorithm

897. Longest common subsequence - AcWing question bank

Given two strings A and B with lengths of N and M respectively, find the longest string length of both A subsequence and B subsequence.

Input format

The first line contains two integers N and M.

The second line contains A string of length N, representing string A.

The third line contains a string of length M, representing string B.

Strings are composed of lowercase letters.

Output format

Output an integer representing the maximum length.

Data range

1≤N,M≤1000

Input sample:

4 5
acbd
abedc

Output example:

3

This problem uses the knowledge points of dynamic programming, but it is two-dimensional dynamic programming. (plum blossom three degrees)

First look at this figure. We take the size of one string as the number of rows and the size of another string as the number of columns to make this two-dimensional array. Then, for each comparison, if the currently traversed text1 character is not equal to the character on text2, we will take a maximum value from the top or front and assign it to the grid. If it is equal, we will assign the value + 1 at the top to the current grid, Finally, return to the grid in the bottom right corner.

#include<iostream>
using namespace std;

const int N=1010;
int f[N][N];

int main()
{
    int n,m;
    cin>>n>>m;
    string str1,str2;
    cin>>str1>>str2;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(str1[i-1]==str2[j-1])f[i][j]=f[i-1][j-1]+1;
            else f[i][j]=max(f[i-1][j],f[i][j-1]);
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}

902. Shortest editing distance - AcWing question bank

Given the two strings A and B, now we need to change A into B through several operations. The available operations are:

1. Delete – deletes A character from string A.
2. Insert – inserts A character somewhere in string A.
3. Replace – replaces one character in string A with another.

Now please find out how many operations it takes to change A into B at least.

Input format

The first line contains the integer n, which represents the length of string A.

The second line contains A string A of length n.

The third line contains the integer m, which represents the length of string B.

The fourth line contains a string B of length m.

All strings contain only uppercase letters.

Output format

Output an integer indicating the minimum number of operations.

Data range

1≤n,m≤1000

Input sample:

10 
AGTCTGACGC
11 
AGTAAGTAGGC

Output example:

4

I don't quite understand the reason. It feels like the longest common subsequence...

#include<iostream>
using namespace std;

const int N=1010;
string str1,str2;
int f[N][N];

int main()
{
    int n,m;
    cin>>n>>str1>>m>>str2;
    for(int i=0;i<=n;i++)f[i][0]=i;
    for(int j=0;j<=m;j++)f[0][j]=j;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);
            if(str1[i-1]!=str2[j-1])f[i][j]=min(f[i][j],f[i-1][j-1]+1);
            else f[i][j]=min(f[i][j],f[i-1][j-1]);
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}

Blue Bridge Cup - algorithm improvement

Algorithm to improve common elements

Problem description

Given two ascending integer arrays a and b with n elements, find their common elements

Input format

The first line contains two integers n,
The next two lines, each with n positive integers, represent the elements in arrays a and B respectively.

Output format

Output 1 line, including all common elements, in ascending order

sample input

5
0 1 2 3 4
1 3 5 7 9

sample output

1 3

Prepare two arrays to store values, and then traverse the arrays on both sides at the same time. If the number is the same, output that number. If the number of the first array is large, the second array will traverse one bit forward, otherwise the first array will traverse one bit forward.

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<string.h>
#include<string>
#include<math.h>



int main()
{
    int n;
    cin >> n;
    vector<int>v1(n), v2(n),v3;
    for (int i = 0; i < n; i++)cin >> v1[i];
    for (int i = 0; i < n; i++)cin >> v2[i];
    int l = 0, r = 0;
    while (l < n && r < n)
    {
        if (v1[l] == v2[r])
        {
            cout << v1[l] << " ";
            l++, r++;
        }
        else if (v1[l] > v2[r])
            r++;
        else l++;
    }


    return 0;
}