1、字符串计数
Ⅰ、题目
描述
求字典序在 s1 和 s2 之间的，长度在 len1 到 len2 的字符串的个数，结果 mod 1000007。
数据范围： 1≤len(s1),len(s2)≤50 ， 1≤len1,len2≤50
注意：本题有多组输入
输入描述：
每组数据包涵s1（长度小于50），s2（长度小于50），len1（小于50），len2（大于len1，小于50）
输出描述：
输出答案。
示例1
输入：
ab ce 1 2
输出：
56
Ⅱ、题目解读
这其实可以看成26进制的减法，因为 ab 到 ce 之间有
长度为1的有 b（可以看成 b`）, c（可以看成 c`)（把a看成1，z看成26，` 的ASCLL为96，所以可以把它看成 0 ）。
长度为2的有 ac 到 az ，ba 到 bz ，ca 到 cd。2+24+26+4 =56。
可以这样通俗的理解，这题就很简单了。但是想得很简单，其实这中间还有一步：补。
因为可能s1的长度小于len2这时候就要补零了=> 补 `
而s2的长度也可能小于len2，s2就需要补 z
这样才符合题意，然后我们就按len1到len2，计算对应的字符串数
Ⅲ、代码
import java.util.*; public class Main{ public static void main(String[] args){ Scanner scan = new Scanner(System.in); while(scan.hasNext()){ String s1 =scan.next(); String s2 = scan.next(); int len1 =scan.nextInt(); int len2 = scan.nextInt(); // 先拿到s1的长度，如果小于len2，就给它补相应的位数，由于它是起始位，所以补a for(int i=s1.length();i<len2;i++){ s1 +='`'; } // 拿到s2的长度，如果小于len2，也给它补相应的位数，由于它是结束位，所以补'z'+1 for(int i=s2.length();i<len2;i++){ s2+='z'; } // 用一个数组，记录两个字符串对应位相减的值， 比如s1补位后为 aba，s2补位后为 ce('z'+1)，arr数组记录的值是 {2，3，26} int[] arr = new int[len2]; // 由于下标比长度小1，所以是取不到len2的 for(int i=0;i<len2;i++){ arr[i] = s2.charAt(i)-s1.charAt(i); } // 用一个变量记录总的数值 int sum = 0; // 从长度len1开始，依次计算每个长度下的字符串个数，这里能取到len2 for(int i= len1;i<=len2;i++){ // 每个长度下，都从arr数组中取值，让它乘以相应的26的次方，比如数组中是{2，3}，len为2时，就是2*Math.pow(26,1)+3*Math.pow(26,0)。 // len为3时，就是 2*Math.pow(26,2)+3*Math.pow(26,1) for(int j=0;j< i;j++){ // 次方既受 len的影响，也受位数的影响，所以是 i-j-1 sum+=arr[j]* Math.pow(26,i-1-j); } } System.out.println((sum-1)%1000007); } } }
当然不知道ASCll 为96的字符，也可以s1加a，s2加 "z+1"
import java.util.*; public class Main{ public static void main(String[] args){ Scanner scan = new Scanner(System.in); while(scan.hasNext()){ String s1 =scan.next(); String s2 = scan.next(); int len1 =scan.nextInt(); int len2 = scan.nextInt(); // 先拿到s1的长度，如果小于len2，就给它补相应的位数，由于它是起始位，所以补a for(int i=s1.length();i<len2;i++){ s1 +='a'; } // 拿到s2的长度，如果小于len2，也给它补相应的位数，由于它是结束位，所以补'z'+1 for(int i=s2.length();i<len2;i++){ s2+='z'+1; } // 用一个数组，记录两个字符串对应位相减的值， 比如s1补位后为 aba，s2补位后为 ce('z'+1)，arr数组记录的值是 {2，3，26} int[] arr = new int[len2]; // 由于下标比长度小1，所以是取不到len2的 for(int i=0;i<len2;i++){ arr[i] = s2.charAt(i)-s1.charAt(i); } // 用一个变量记录总的数值 int sum = 0; // 从长度len1开始，依次计算每个长度下的字符串个数，这里能取到len2 for(int i= len1;i<=len2;i++){ // 每个长度下，都从arr数组中取值，让它乘以相应的26的次方，比如数组中是{2，3}，len为2时，就是2*Math.pow(26,1)+3*Math.pow(26,0)。 // len为3时，就是 2*Math.pow(26,2)+3*Math.pow(26,1) for(int j=0;j< i;j++){ // 次方既受 len的影响，也受位数的影响，所以是 i-j-1 sum+=arr[j]* Math.pow(26,i-1-j); } } System.out.println((sum-1)%1000007); } } }
或者直接使用方法 求ASCALL为95的字符
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int a = sc.nextInt(); char c = (char) a; System.out.println(c); } }
2、发邮件
Ⅰ、题目
NowCoder每天要给很多人发邮件。有一天他发现发错了邮件，把发给A的邮件发给了B，把发给B的邮件发给了A。于是他就思考，要给n个人发邮件，在每个人仅收到1封邮件的情况下，有多少种情况是所有人都收到了错误的邮件？
即没有人收到属于自己的邮件。
输入描述:
输入包含多组数据，每组数据包含一个正整数n（2≤n≤20）。
输出描述:
对应每一组数据，输出一个正整数，表示无人收到自己邮件的种数。
示例1
输入
1. 2 2. 3
输出
1 2
Ⅱ、题目解读
错排问题。
当n个编号元素放在n个编号位置，元素编号与位置编号各不对应的方法数用D(n)表示，那么D(n-1)就表示n-1个编号元素放在n-1个编号位置，各不对应的方法数，其它类推.
第一步，把第n个元素放在一个位置，比如位置k，一共有n-1种方法；
第二步，放编号为k的元素，这时有两种情况：
⑴把它放到位置n，那么，对于剩下的n-1个元素，由于第k个元素放到了位置n，剩下n-2个元素就有D(n-2)种方法；
⑵第k个元素不把它放到位置n，这时，对于这n-1个元素，有D(n-1)种方法；
综上得到
D(n) = (n-1)* [D(n-2) + D(n-1)]
特殊地，D(1) = 0, D(2) = 1.
我们得到了递推公式，代码也就简单写出来了。
Ⅲ、代码
import java.util.Scanner; public class Main { static long dp(int n) { if (n == 1 ) return 0; if (n == 2) return 1; return (n - 1) * (dp(n - 1) + dp(n - 2)); } public static void main(String[] args) { Scanner sc=new Scanner(System.in); while (sc.hasNext()){ int n=sc.nextInt(); System.out.println(dp(n)); } } }
