算法4-中兴捧月杯热身赛1素数判断-热身赛2亲和串-热身赛3旅游路线-

题目1：素数判断

需求
给定一个数n，要求判断其是否为素数(0,1，负数都是非素数)。输入描述:测试数据有多组，每组输入一个数n。输出描述:对于每组输入,若是素数则输出yes，否则输入no。
样例1:
输入:13输出:yes

代码

// idea_algorithm
package offer2;
import java.util.Scanner;
public class Test422 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        if(method(n)){
            System.out.println("yes");
        }else{
            System.out.println("no");
        }
    }
    public static Boolean method(int n){
        if(n <= 1 ){
            return false;
        }else{
            // 注意这里遍历得从2开始。双指针实现。
            for(int i = 2,j= n-1;i<= j; i++,j--){
                if(n%i == 0|| n%j == 0){
                    return false;
                }
            }
        }
        return true;
    }
}

注意点 循环开始值是2

使用for循环遍历找n可以整除的数的时候，循环开始的点是2，因为0 不能当除数，1不是非素数与素数的区别。

题目2：亲和串

需求
人随着岁数的增长是越大越聪明还是越大越笨，这是一个值得全世界科学家思考的问题，
同样的问题Eddy也一直在思考，因为他在很小的时候就知道亲和串如何判断了，但是发现，现在长
大了却不知道怎么去判断亲和串了，于是他只好又再-次来请教聪明且乐于助人的你来解决这个问
题。亲和串的定义是这样的：给定两个字符串s1和s2,如果能通过s1循环移位,使s2包含在s1中，那
么我们就说s2是s1的亲和串。
输入描述:本题有多组测试数据，每组数据的第一行包含输入字符串s1,第 二行包含输入字符串s2,
s1与s2的长度均小于100000。
输出描述:如果s2是s1的亲和串, 则输出"yes",反之，输出"no"。每组测试的输出占-行。
样例1:
输入: AABCD
CDAA
输出: yes

代码

package offer2.Test423;

import java.util.Scanner;

public class Test423 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String strSum = in.next();
        String strSon = in.next();
        if(method(strSum,strSon) != -1){
            System.out.println("yes");
        }else{
            System.out.println("no");
        }
    }
    public static int method(String strSum,String strSon){
        String s = strSum + strSum;
        if(strSum.length() == 0 || strSum == null || strSon == null || strSum.length()-strSon.length() <0){
            return -1;
        }else{
            int index = s.indexOf(strSon);
            return index;
        }
    }
	public static int method1(String strSum,String strSon){
	        String s = strSum + strSum;
	        if(strSum.length() == 0 || strSum == null || strSon == null || strSum.length()-strSon.length() <0){
	            return -1;
	        }else{
	            Boolean b = s.contains(strSon);
	            return 1;
	        }
	    }
}

注意点 java.util.NoSuchElementException: No line found 编译出现这个问题。

分析：
经过测试发现问题可能是定义一个Scanner对象，前后两个字符串输入的内容不一样，一个是字符串“abx”，另一个是数字字符串"123"。
其中前后两个串分别是“12345” “123” 这种形式可以正确执行。
解决：

Scanner sc = new Scanner(System.in);
String s = sc.next();
// 之前使用的是nextLine()。

Scanner 类的next和nextLine方法

Scanner类的方法

方法名	说明
String next()	查找并返回此扫描仪的下一个完整令牌 不接收空格，在接收有效数据之前，所有的空格或tab键投被忽略，若有有效数据，则遇到这些键退出
int nextInt()	将输入的下一个标记扫描为int
String nextLine()	将此扫描仪推进到当前行并返回跳过的输入 可以接收空格或tab键，输入以enter键结束

代码

// idea_algorithm 
package offer2.Test423;

import java.util.Scanner;

public class StringnextLineDemo {
    public static void main(String[] args) {
        method1();
    }
    public static void method(){
        Scanner input = new Scanner(System.in);
        String s1 = input.next();
        String s2 = input.next();
        System.out.println(s1);
        System.out.println(s2);
        System.out.println(s1 + s2);

        // 键盘输入ABC(空格）DEF(空格）(空格）
        // 输出结果是：
        // ABC
        // DEF
        // ABCDEF
        // 分析：没有接收空格，要是接收了空格，那么最后的输出应该会有空格，ABC 和 DEF 之间的空格被当做 两个字符串之间的划分，表示输入的是两个字符串
    }

    public static void method1(){
        Scanner input = new Scanner(System.in);
        String s1 = input.next();
        String s2 = input.next();
        String s3 = input.nextLine();

        System.out.println(s1);
        System.out.println(s2);
        System.out.println(s3);
        System.out.println(s1 + s2);
        System.out.println(s1 + s2 + s3);

        // 键盘输入A(空格)B(空格)C(空格)D(空格)
        // 输出结果是：
        //A
        //B
        //(空格)C(空格)D(空格)
        //AB
        //AB(空格)C(空格)D(空格)
        // nextLine()方法可以接收空格或tab键。
    }
}

不是亲和串的特殊情况

首先两个字符串，一个是FatherStr，另一个是SonStr。
FatherStr 不能为空

FatherStr.length() == 0

FatherStr的长度 不能比 SonStr的长度 短，

FatherStr.length() - SonStr.length() < 0 

FatherStr 和 SonStr 都不能为null

FatherStr == null SonStr == null

子串属于父串使用的String类中的方法

方法名	说明
Boolean contains（CharSequence s	当且仅当此字符串包含指定的char值序列时才返回true contains方法的参数可以是String类型
int indexOf（String str）	返回指定子字符串第一次出现的字符串内的索引

题目3：旅游线路

题目描述:
2010年，世博会在中国上海举办，吸引了数以千万计的中外游客前来参观。暑假期间小Z也来到了上海世博园，她对世博园的拥挤早有所闻，对有的展馆甚至要排上好几个小时的队才能进入也做好了充分准备,但为了使得自己的世博之旅更加顺利舒畅，小Z决定在游玩之前先制定一份详细的旅行路线。
小Z搜集到了世博园的地图,她发现从整体上看世博园是-块非常狭长的区域，每一个展馆占用了其中一个几乎相同大小的方块。因此可以将整个园区看成一个n x m的矩阵(n≤3)，其中每个格子为一个主题展馆。由于不同展馆受到的关注度会有一些差别， 因此排队时间的长短也不尽相同。
小Z根据统计信息给每一个展馆(x, y)标记了Tx,y = 0或1，
如果Tx,y= 1,表示这个展馆非常热门，需要排很长时间的队;
如果Tx,y= 0,表示这个展馆相对比较普通，几乎不需要排队即可进入参观。
小Z希望能够制定一份合理的路线，使得能交替参观热门馆和普通馆，既不会因为总是参观热门馆而长时间在排队，也不会因为总是参观普通馆而使得游览过于平淡。同时，小Z办事很讲究效率,她希望在游遍所有展馆的同时，又不会走冤枉路浪费体力。因此她希望旅行路线满足以几个限制:
在参观完位于(x, y)的展馆后，下一个参观的是一个相邻的且未被参观过的展馆(x’, y’)，即|x-x’|+|y-
y’|=1;
路线的起点位于整个矩阵的边界上，即x= 1或x= n或y= 1或y= m;
她制定了一个长度为n*m的01列L，她希望第i个参观的展馆(x,y)满足Tx,y=Li。小Z想知道有多少条不同的旅行路线能
够满足她的要求。由于最终的结果可能很大，小Z只想知道可行的旅行路线总数 mod 11192869的值。
题目要求整理：

题目输入：
输入描述：第一行包含两个正整数n, m。第2行至第n+ 1行,每行有m个01整数，其中第i+ 1行第j个数表示 Tij。
第n+ 2行有n*m个01整数，其中第i个数表示Li的值。
输出描述：仅包含一个整数，表示可行的旅行路线总数 mod 11192869的值。
案例：
输入：
2 2
1 0
0 1
1 0 1 0
输出 4
xhj理解