判断子序列
给定一个长度为 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); } }
