判断子序列
序列 判断
2023-09-14 09:14:24 时间
判断子序列
给定一个长度为 n 的整数序列 a1,a2,…,an 以及一个长度为 m 的整数序列 b1,b2,…,bm。
请你判断 a 序列是否为 b 序列的子序列。
子序列指序列的一部分项按原有次序排列而得的序列,例如序列 {a1,a3,a5} 是序列 {a1,a2,a3,a4,a5} 的一个子序列。
输入格式
第一行包含两个整数 n,m。
第二行包含 n 个整数,表示 a1,a2,…,an。
第三行包含 m 个整数,表示 b1,b2,…,bm。
输出格式
如果 a 序列是 b 序列的子序列,输出一行 Yes。
否则,输出 No。
数据范围
1≤n≤m≤105,
−109≤ai,bi≤109
输入样例:
3 5
1 3 5
1 2 3 4 5
输出样例:
Yes
思路分析:
设计两个数字a,b
- 利用for循环遍历两个数组
- 思路就是看一下这个遍历b数组的时候 这个a数组是否会走完
- 如果这个a数组走完了 那么就代表的是
- 这个长度更小的a数组是b数组的子序列
C++
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m;
int a[N], b[N];
bool flag;
int main()
{
cin >> n >> m;
for (int i = 0; i < n; ++ i) cin >> a[i];
for (int j = 0; j < m; ++ j) cin >> b[j];
// 利用for循环遍历两个数组
// 思路就是看一下这个遍历b数组的时候 这个a数组是否会走完
// 如果这个a数组走完了 那么就代表的是
// 这个长度更小的a数组是b数组的子序列
for (int i = 0, j = 0; i < m && j < n; ++ i)
{
// 首先判断的是 两个数组的元素是否相等 如果想的的话
// 这个a数组就往后走一格
if (b[i] == a[j]) j ++;
// 当走完的时候 设置flag=true
if (j == n) flag = true;
}
if (flag) cout << "Yes";
else cout << "No";
return 0;
}
Java
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int [] a = new int [n + 10];
int [] b = new int [m + 10];
for (int i = 0; i < n; ++ i) a[i] = in.nextInt();
for (int j = 0; j < m; ++ j) b[j] = in.nextInt();
boolean flag = false;
int j = 0;
for (int i = 0; i < m; ++ i)
{
if (a[j] == b[i]) j ++;
if (j == n)
{
flag = true;
break;
}
}
if (flag) System.out.println("Yes");
else System.out.println("No");
}
}
每天一道算法题
最长连续不重复子序列
给定一个长度为 n 的整数序列,请找出最长的不包含重复的数的连续区间,输出它的长度。
输入格式
第一行包含整数 n。
第二行包含 n 个整数(均在 0∼105 范围内),表示整数序列。
输出格式
共一行,包含一个整数,表示最长的不包含重复的数的连续区间的长度。
数据范围
1≤n≤105
输入样例:
5
1 2 2 3 5
输出样例:
3
提交代码
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N], s[N];
int n, res;
int main()
{
cin >> n;
for (int i = 0; i < n; ++ i) cin >> a[i];
for (int i = 0, j = 0; i < n; ++ i)
{
s[a[i]] ++; // 记录下a[i]出现的次数
while(s[a[i]] > 1) // 一点碰见两个重复的元素后
{
s[a[j]] --; // 这里要主要的一点是这个算法是没有回溯的
// 不要被for循环里面的条件误导以为会回溯、
// 现在遇到两个相同的元素了
// !!! 现在是这个算法最厉害的地方
// 这个j代表的是 j可以到达最左的地方 所以在j左边的
// 元素的个数就需要都-- 这点很妙
// 每次求的是 j到i之间的符合条件的最大值
j ++; // 然后j++
}
res = max(res, i - j + 1); // 这个res的含义是 在i这个位置、
// 可以达到的符合题目条件的最大长度
}
cout << res;
return 0;
}
import java.io.*;
import java.util.*;
public class Main
{
public static void main(String[] args) throws IOException{
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int [] a = new int [n + 10];
int [] s = new int [n + 10];
int res = 0;
for (int i = 0; i < n; ++ i) a[i] = in.nextInt();
for (int i = 0, j = 0; i < n; ++ i)
{
s[a[i]] ++;
while(s[a[i]] > 1)
{
s[a[j]] --;
j ++;
}
res = Math.max(res, i - j + 1);
}
System.out.println(res);
}
}
相关文章
- 02-线性结构1 两个有序链表序列的合并
- Python:过滤序列的filter()函数
- 使用 Temporal Fusion Transformer 进行时间序列预测
- 线性平稳时间序列
- sql查询序列是否存在_oracle if判断是否为空
- ICML 2022 | 用于时间序列预测的指数平滑 Transformer
- postgresql修改自增序列操作
- 使用Oracle字段序列实现序列号(oracle字段序列)
- 最长回文子序列算法详解编程语言
- Mysql如何利用自增序列实现自动编号(mysql自增序列)
- Oracle添加表序列:一步一步指南(oracle添加表序列)
- MySQL中使用序列实现自增的方法(mysql序列自增)
- 优化网络传输Redis压缩传输序列(压缩传输序列redis)
- php数组函数序列之array_key_exists()-查找数组键名是否存在
- php数组函数序列之asort()-对数组的元素值进行升序排序,保持索引关系
- 判断整数序列是否为二元查找树的后序遍历结果的解决方法