algorithm-class/算法周更班/class_2022_04_3_week/Code05_ModKSubstringNumbers.java

package class_2022_04_3_week;

// 来自微众
// 4.11笔试
// 给定n位长的数字字符串和正数k，求该子符串能被k整除的子串个数
// (n<=1000，k<=100)
public class Code05_ModKSubstringNumbers {

	// 暴力方法
	// 为了验证
	public static int modWays1(String s, int k) {
		int n = s.length();
		int ans = 0;
		for (int i = 0; i < n; i++) {
			for (int j = i; j < n; j++) {
				if (Long.valueOf(s.substring(i, j + 1)) % k == 0) {
					ans++;
				}
			}
		}
		return ans;
	}

	// 正式方法
	// 时间复杂度O(N * k)
	public static int modWays2(String s, int k) {
		int[] cur = new int[k];
		// 帮忙迁移
		int[] next = new int[k];
		// 0...i 整体余几？
		int mod = 0;
		// 答案：统计有多少子串的值%k == 0
		int ans = 0;
		for (char cha : s.toCharArray()) {
			for (int i = 0; i < k; i++) {
				// i -> 10个
				// (i * 10) % k 
				next[(i * 10) % k] += cur[i];
				cur[i] = 0;
			}
			int[] tmp = cur;
			cur = next;
			next = tmp;
			mod = (mod * 10 + (cha - '0')) % k;
			ans += (mod == 0 ? 1 : 0) + cur[mod];
			cur[mod]++;
		}
		return ans;
	}

	// 为了测试
	public static String randomNumber(int n) {
		char[] ans = new char[n];
		for (int i = 0; i < n; i++) {
			ans[i] = (char) ((int) (Math.random() * 10) + '0');
		}
		return String.valueOf(ans);
	}

	// 为了测试
	public static void main(String[] args) {
		int N = 18;
		int K = 20;
		int testTime = 10000;
		System.out.println("测试开始");
		for (int i = 0; i < testTime; i++) {
			String str = randomNumber((int) (Math.random() * N) + 1);
			int k = (int) (Math.random() * K) + 1;
			int ans1 = modWays1(str, k);
			int ans2 = modWays2(str, k);
			if (ans1 != ans2) {
				System.out.println("出错了!");
				System.out.println(str);
				System.out.println(k);
				System.out.println(ans1);
				System.out.println(ans2);
				break;
			}
		}
		System.out.println("测试结束");
	}

}