一、《不同子串》

问题描述

一个字符串的非空子串是指字符串中长度至少为 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);}
}