一、《不同子串》

问题描述

一个字符串的非空子串是指字符串中长度至少为 1 的连续的一段字符组成的串。
例如，字符串aaab 有非空子串a,b,aa,ab,aaa,aab,aaab，一共 7个注意在计算时，只算本质不同的串的个数。
请问，字符串0100110001010001 有多少个不同的非空子串?

• 输入：0100110001010001
• 输出：100

算法分析

使用枚举获得所有子串，之后使用HashSet数据类型进行去重操作。

代码如下

package lanqiao;
import java.util.HashSet;
import java.util.Scanner;
public class DifferentSubstring {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		String line = scanner.nextLine();
		HashSet<String> hSet = new HashSet<String>();
		for(int i=0;i<line.length();i++) {
			for(int j=i;j<line.length();j++) {
				hSet.add(line.substring(i, j+1));
			}
		}
		System.out.println(hSet.size());
	}
}

二、《数列求值》

问题描述

给定数列 1,1,1,3,5,9,17,"·，从第 4 项开始，每项都是前 3 项的和。
求第 20190324 项的最后 4 位数字。

• 输入：20190324
• 输出：4659

算法分析

本题数列是基于斐波那契数列的变形，题目关键是在计算每一项数值的过程中需要对10000的进行取模（取余）运算（只取最后4位数字），防止数值过大溢出。

代码如下

package lanqiao;
import java.util.Scanner;
public class EvaluationOfSequence {
	public static void main(String[] args) {
		int a=1,b=1,c=1;
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt()-1;
		int temp;
		while(n>0) {
			//防止溢出
			temp = (a+b+c)%10000;
			a=b;
			b=c;
			c=temp;
			n--;
		}
		System.out.println(a);
	}
}

二、《数的分解》

问题描述

把 2019 分解成 3 个各不相同的正整数之和，并且要求每个正整数都不包含数字 2 和 4，一共有多少种不同的分解方法?
注意交换 3 个整数的顺序被视为同一种方法，例如 1000+1001+18 和1001+1000+18 被视为同一种。

• 输入：2019
• 输出：40785

算法分析

本题的关键在于设定a<b<c，防止解法重复，即让b从a+1开始枚举，同时c=2019-a-b需要大于b。

代码如下

package lanqiao;
import java.util.Scanner;
public class DecompositionOfNumber {
	private static boolean has2or4(int x) {
		String xString = String.valueOf(x);
		if (xString.indexOf("2")!=-1||xString.indexOf("4")!=-1) {
			return true;
		}
		return false;
	}
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int a,b,c,res=0;
		//让b从a+1开始
		for(a=1;a<2019;a++) {
			for(b=a+1;b<2019&&n-a-b>b;b++) {
				c=2019-a-b;
				if (!has2or4(a)&&!has2or4(b)&&!has2or4(c)) {
					res++;
				}
			}
		}
		System.out.println(res);
	}
}