AcWing 2816. 【算法基础课】判断子序列    原题链接    简单

作者： 作者的头像   Conan15 ,  2022-06-21 20:53:26 ,  所有人可见 ,  阅读 1501

14


1

$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$
笔记：
到此双指针部分就结束啦！真开心
这题就是和归并排序一样的模式：指向两个序列的双指针算法。（其实是单指针吧。。。）
因为序列是有序的，所以我们只要从头往后扫描b数组，只要有一个a中的元素匹配不上，就是“失配”。
否则是匹配的。

代码：

#include <bits/stdc++.h>
using namespace std;
int n, m, a[100010], b[100010];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int j = 1; j <= m; j++) scanf("%d", &b[j]);
    int j = 1;
    for (int i = 1; i <= n; i++) {
        while (b[j] != a[i] && j <= m) j++;
        if (j > m) {puts("No"); return 0;}
        j++;
    } puts("Yes");
    return 0;
}

8 评论

用户头像
@Chase   2022-07-21 12:53      1    踩      回复 
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N],b[N];
int n,m;

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ )
    {
        scanf("%d", &a[i]);
    }
    for (int j = 0; j < m; j ++ )
    {
        scanf("%d", &b[j]);
    }
    bool flag = true;
    for (int i = 0,j = 0; i < n; i ++,j ++) // 相等时，i和j同步+1即可
    {
        while(j < m && b[j] != a[i]) j ++; // 不相等的时候：j后移找到第一个相等的
        if(j == m) { // 如果未找到
            cout << "No" << endl;
            flag = false;
            break;
        }
    }
    if (flag)
        cout << "Yes" << endl;
    return 0;
}
用户头像
学不会动态规划不改名   2023-01-09 22:59         踩      回复

和我想法一样

用户头像
tlsn   2023-01-10 19:09         踩      回复

一样 XD

用户头像
bloom_wmh   24天前         踩      回复

本以为我的想法不对，结果与大佬的想法一样(＾－＾)V，赶快去调试一下

用户头像
奋战中   2023-03-22 19:46         踩      回复

哪里错了啊

#include [HTML_REMOVED]
using namespace std;
int n, m, a[100010], b[100010];
int main() {
scanf(“%d%d”, &n, &m);
for (int i = 1; i <= n; i) scanf(“%d”, &a[i]);
for (int j = 1; j <= m; j) scanf(“%d”, &b[j]);

int j = 0;
int i = 0;
for(; i<n; i++){
    while(a[i]!=b[j] && j<m){
        j++;
    }
    if(j==m){
        printf("No");
        return 0;
    }
    j++;
}
printf("Yes");

}

用户头像
Conan15   2023-03-22 20:11         踩      回复

是不是下标问题，看一下

用户头像
释然r   2023-09-17 20:45         踩      回复

你这个 while 循环结束后应该先进行j++

用户头像
雨後   2022-10-27 21:22         踩      回复

妙啊