大数据算法系列10:字符串检验算法
2022-11-02 本文已影响0人
只是甲
一. 字符串检验算法
字符串检验算法:
image.png
奇偶校验:
磁盘阵列的Raid5就是使用了奇偶校验。
海明码:
image.png
二. 练习
2.1 面试题(输出字符串的排列组合)
题目:
image.png
分析:
采用递归加动态规划的思路，加上恢复现场的原理，同时解决。
代码:
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
class Main {
public static Set<String> getPermutation(String str) {
//创建 set 集合以避免重复排列
Set<String> permutations = new HashSet<String>();
//检查字符串是否为空
if (str == null) {
return null;
} else if (str.length() == 0) {
//递归的终止条件
permutations.add("");
return permutations;
}
//得到第一个字符
char first = str.charAt(0);
//获取剩余的子字符串
String sub = str.substring(1);
//递归调用getPersertion()
Set<String> words = getPermutation(sub);
//遍历 words
for (String strNew : words) {
for (int i = 0;i<=strNew.length();i++){
//将排列插入到set集合中
permutations.add(strNew.substring(0, i) + first + strNew.substring(i));
}
}
return permutations;
}
public static void main(String[] args) {
//创建scanner类的对象
Scanner input = new Scanner(System.in);
// 接受用户的输入
System.out.print("输入字符串: ");
String data = input.nextLine();
System.out.println(data + " 的排列组合有: \n" + getPermutation(data));
}
}
2.2 POJ2262(求奇质素之和)
题目:
image.png
代码:
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(true) {
int t=sc.nextInt();
if(t==0)break;//t等于0退出
for (int i = 3; i <=t/2; i+=2) {//从3开始，因为必须是奇素数，就不考虑2了
if(isPrime(i)&&isPrime(t-i)) {
System.out.println(t+" = "+i+" + "+(t-i));
break;
}
}
}
}
private static boolean isPrime(int i) {
if(i==2||i==3) {//等于2,3直接返回是素数
return true;
}
//3之后的素数，一定，在6的两边
if(i%6!=1 && i%6!=5) {//不在6的左右两边，一定不是素数
return false;
}
//在6的左右两边的数，也有可能不是素数
int sqrt=(int)Math.sqrt(i);
for (int j = 5; j <=sqrt ; j+=6) {
if(i%j==0 || i%(j+2)==0) {
return false;
}
}
return true;
}
}
2.3 开门游戏
题目:
image.png
分析:
用0表示关门，用1表示开门，把数据放到一个数组里面。
然后写个if判断，每次改变装填，最后给数组求和，就能知道有多少开门的。
2.4 Uva106(费马大定律)
题目:
image.png
分析:
拆解开了，根据公式进行循环判断即可。
2.5 POJ3744(踩地雷)
大意:
输入n，代表一位童子兵要穿过一条路，路上有些地方放着n个地雷（1<=n<=10）。再输入p，代表这位童子兵非常好玩，走路一蹦一跳的。每次他在 i 位置有 p 的概率走一步到 i+1 ，或者 (1-p) 的概率跳一步到 i+2。输入n个数，代表n个地雷的位置（1<=n<=100000000），童子兵初始在1位置，求他安全通过这条道路的概率。
分析:
如果k 号位有雷，那么安全通过这个雷只可能是在 k-1 号位选择走两步到 k+1 号位。因此，可以得到如下结论：在第 i 个雷的被处理掉的概率就是从 a[i-1]+1 号位到 a[i] 号位的概率。于是，可以用 1 减去就可以求出安全通过第 i个雷的概率，最后乘起来即可，比较悲剧的是数据很大，所以需要用到矩阵快速幂……
类似斐波那契数列，有ans[i]=pans[i-1]+(1-p)ans[i-2]
2.6 POJ3233(矩阵计算)
题目:
image.png
分析:
image.png
2.7 POJ1226(哈希)
大意:
多组数据，每组n个字符串，寻找最长的X，使得对n个字符串中的任意一个，X或者X反转过来的字符串是其子串。(输出X的长度即可)
分析:
这道好像KMP或者后缀数组都能做，但我还是习惯用哈希。此题可以先二分这个长度（显然如果某个长度满足那么小于这个长度的串也是能找到的），不妨记这个长度为len。然后呢，以第一个字符串为标准，正一遍反一遍扫过去得到该字符串中，以i为下标开始的长度为len的子串的哈希值（不妨记为h1[i]），以及其翻转过来串对应的哈希值（不妨记为h2[i]）。同时，后面几个字符串中长度为len的子串的哈希值也可处理出来，放到容器里。接下来，就是看是否存在这样的i，使得剩余n-1个字符串对应的n-1个容器里要么含有h1[i],要么含有h2[i]。如果是则len可以，所求长度肯定大于等于len；否则，所求长度小于len。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.HashSet;
import java.util.StringTokenizer;
class Reader {
static BufferedReader reader;
static StringTokenizer tokenizer;
static void init(InputStream input) {
reader = new BufferedReader(new InputStreamReader(input));
tokenizer = new StringTokenizer("");
}
static String next() throws IOException {
while (!tokenizer.hasMoreTokens()) {
tokenizer = new StringTokenizer(reader.readLine());
}
return tokenizer.nextToken();
}
static int nextInt() throws IOException {
return Integer.parseInt(next());
}
}
public class Main {
/**
* @param args
*/
static int t, n, cnt, len1;
static char ch[][];
static int hash1[], hashin[];
static HashSet<Integer> hashSet[];
static String str;
static long mul = 100000007;
static long monum = Integer.MAX_VALUE;
static long mulnum;
private static boolean isOk(int num) {
hashSet = new HashSet[n + 1];
for (int i = 1; i <= n; i++)
hashSet[i] = new HashSet<Integer>();
mulnum = 1;
for (int i = 1; i <= num; i++)
mulnum = (mulnum * mul) % monum;
long v;
for (int i = 2; i <= n; i++) {
if (ch[i].length < num)
return false;
v = 0;
for (int j = 0; j < num; j++)
v = (v * mul + (long) ch[i][j]) % monum;
hashSet[i].add((int) v);
for (int j = num; j < ch[i].length; j++) {
v = (v * mul + (long) ch[i][j]) % monum;
v = ((v - mulnum * (long) ch[i][j - num]) % monum + monum)
% monum;
hashSet[i].add((int) v);
}
}
hash1 = new int[len1 + 1];
hashin = new int[len1 + 1];
v = 0;
for (int i = 0; i < num; i++) {
v = (v * mul + (long) ch[1][i]) % monum;
}
hash1[1] = (int) v;
for (int i = num; i < len1; i++) {
v = (v * mul + (long) ch[1][i]) % monum;
v = ((v - mulnum * (long) ch[1][i - num]) % monum + monum) % monum;
hash1[i - num + 2] = (int) v;
}
v = 0;
for (int i = len1 - 1; i >= len1 - num; i--) {
v = (v * mul + (long) ch[1][i]) % monum;
}
hashin[len1 - num + 1] = (int) v;
for (int i = len1 - num - 1; i >= 0; i--) {
v = (v * mul + (long) ch[1][i]) % monum;
v = ((v - mulnum * (long) ch[1][i + num]) % monum + monum) % monum;
hashin[i + 1] = (int) v;
}
boolean flag;
for (int i = 1; i <= len1; i++) {
flag = true;
for (int j = 2; j <= n; j++)
if ((!hashSet[j].contains(hash1[i]))
&& (!hashSet[j].contains(hashin[i]))) {
flag = false;
break;
}
if (flag)
return true;
}
return false;
}
private static void deal() {
len1 = ch[1].length;
int l = 0;
int r = ch[1].length;
if (n == 1) {
System.out.println(r);
return;
}
int mid;
while (r - l > 1) {
mid = (l + r) / 2;
if (isOk(mid))
l = mid;
else
r = mid;
}
if (isOk(r))
System.out.println(r);
else
System.out.println((r - 1));
}
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
Reader.init(System.in);
t = Reader.nextInt();
ch = new char[101][];
for (int casenum = 1; casenum <= t; casenum++) {
n = Reader.nextInt();
for (int i = 1; i <= n; i++) {
str = Reader.next();
ch[i] = str.toCharArray();
}
deal();
}
}
}
2.8 POJ2440（DNA）
大意:
L位由0和1组成的基因，基因中不能包含子串101以及111，求这样的基因数（L<=10^8）
分析:
快速幂
https://blog.csdn.net/weixin_45987345/article/details/116033056
，果断快速幂。
先倒着推一下，然后再暴力打数据验证想法，最后找循环节为200就可以
a[n]表示长度为n的情况数，第n位只有0或1两种情况
当第n位为0时,前一位为0或1都可以，即a[n-1]
当第n位为1，n-1位为0时，则n-2位只能为0，n-3位任意取，即a[n-3]，
当第n位为1，n-1位为1时，则n-2位只能为0，n-3位只能为0，n-4位任意取，即a[n-4]
a[n]=a[n-1]+a[n-3]+a[n-4]
代码:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
public class Main {
/**
* @param args
*/
static int n, sum;
static int mat1[][], nowmat[][];
static BufferedReader reader;
static String str;
private static int[][] mulmat(int a[][], int b[][]) {
int c[][] = new int[9][9];
int val;
for (int i = 1; i <= 8; i++)
for (int j = 1; j <= 8; j++) {
val = 0;
for (int k = 1; k <= 8; k++)
val = (val + a[i][k] * b[k][j]) % 2005;
c[i][j] = val;
}
return c;
}
private static int[][] mul(int n) {
if (n == 1)
return mat1;
else {
int mat[][] = mul(n / 2);
mat = mulmat(mat, mat);
if (n % 2 == 1)
mat = mulmat(mat, mat1);
return mat;
}
}
private static void init() {
mat1 = new int[9][9];
mat1[1][1] = 1;
mat1[1][5] = 1;
mat1[2][1] = 1;
mat1[2][5] = 1;
mat1[3][2] = 1;
mat1[4][2] = 1;
mat1[5][3] = 1;
mat1[5][7] = 1;
mat1[7][4] = 1;
}
public static void main(String[] args) throws NumberFormatException,
IOException {
// TODO Auto-generated method stub
reader = new BufferedReader(new InputStreamReader(System.in));
while ((str = reader.readLine()) != null) {
n = Integer.parseInt(str);
if (n == 1)
System.out.println(2);
else if (n == 2)
System.out.println(4);
else if (n == 3)
System.out.println(6);
else {
init();
nowmat = mul(n - 3);
sum = 0;
for (int i = 1; i <= 8; i++)
for (int j = 1; j <= 8; j++)
sum = (sum + nowmat[i][j]) % 2005;
System.out.println(sum);
}
}
}
}
2.9 POJ3735(mat乘法优化)
大意:
对于n只猫，现在我们有g,e,s三种操作：
- g是让第a只猫得到一个花生
- e是让第a只猫的花生全部没有
- s是让第a只猫和第b只猫的花生互换
一共有K次操作，这还不算完
要我们重复m次这些操作后，得出的每只猫的花生个数
分析:
m很大，考虑矩阵变化，考虑每一个变化过程，由于有加一，将初始矩阵末尾增加一，方便进行操作，然后有如下变换
image.png
