1、字符串计数

字符串计数_牛客题霸_牛客网 (nowcoder.com)

Ⅰ、题目 

描述

求字典序在 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'+1for(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开始，依次计算每个长度下的字符串个数，这里能取到len2for(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-1sum+=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'+1for(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开始，依次计算每个长度下的字符串个数，这里能取到len2for(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-1sum+=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.com)

Ⅰ、题目

链接：发邮件__牛客网
来源：牛客网
 

NowCoder每天要给很多人发邮件。有一天他发现发错了邮件，把发给A的邮件发给了B，把发给B的邮件发给了A。于是他就思考，要给n个人发邮件，在每个人仅收到1封邮件的情况下，有多少种情况是所有人都收到了错误的邮件？
即没有人收到属于自己的邮件。

 

输入描述:

输入包含多组数据，每组数据包含一个正整数n（2≤n≤20）。

输出描述:

对应每一组数据，输出一个正整数，表示无人收到自己邮件的种数。

示例1

输入

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