• 大数据算法系列10:字符串检验算法

    文章目录

    一. 字符串检验算法

    字符串检验算法:
    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));
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50

    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;
	}
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39

    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]=p*ans[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();
		}
	}
 
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140

    2.8 POJ2440（DNA）

    大意:
    L位由0和1组成的基因，基因中不能包含子串101以及111，求这样的基因数（L<=10^8）

    分析:
    快速幂
    https://blog.csdn.net/weixin_45987345/article/details/116033056

    1 0 8 10^8 108，果断快速幂。
    先倒着推一下，然后再暴力打数据验证想法，最后找循环节为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);
			}
		}
	}
 
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78

    2.9 POJ3735(mat乘法优化)

    大意:
    对于n只猫，现在我们有g,e,s三种操作：

    1. g是让第a只猫得到一个花生
    2. e是让第a只猫的花生全部没有
    3. s是让第a只猫和第b只猫的花生互换

    一共有K次操作，这还不算完

    要我们重复m次这些操作后，得出的每只猫的花生个数

    分析:
    m很大，考虑矩阵变化，考虑每一个变化过程，由于有加一，将初始矩阵末尾增加一，方便进行操作，然后有如下变换
    image.png

    参考:

    1. http://www.dataguru.cn/article-5747-1.html
  • 相关阅读:
    世界前沿技术发展报告2023《世界航天技术发展报告》（五）太空探索技术
    中国雪深长时间序列数据集（1979-2020）
    坚守，一个烂俗的词，驱动人生带它走过了15年
    【javaScript面向对象-模块化-面相关对象编程——行走的方块案例】
    Linux-查询目录下包含的目录数或文件数
    element表单验证常用的几种规则
    Android 11 定制系统全局监听触摸事件接口
    区块链技术在供应链管理中的创新应用
    CP Autosar-ETH Driver配置
    AV1时域滤波相关代码
  • 原文地址：https://blog.csdn.net/u010520724/article/details/127669961