招商银行信用卡中心笔试编程题

1.判断字符串是否由其子串构成

代码：

    /**
     * 招行笔试第一题：字符串是否由其子串构成，若是输出子串，否输出false
     * @param str 字符串
     */
    public static void test11(String str){
            int n = str.length();
            int m;
            int flag=0;
            for(int i=n/2; i>=1; i--){     //i为原字符串的可重复子串的子串的长度；对每种可能长度的子串进行遍历，i为子串长度。
                if( n%i == 0 ){         //n%i == 0：长度为i的子串可以切分str，否则，str的长度不能整除i，表示str就不可能由若干子串重复组成
                    m = n/i;            //m: str中长度为i的子串的个数
                    for(int j=0; j <i; j++){      //比较m个长度为i的子串是否相等，j遍历子串的每个字符
                        flag=0;                 //标记所有子串所有元素是否相等
                        for(int k=1;k<m;k++) {          //k遍历所有子串
                            if(str.charAt(j) != str.charAt(j+k*i)){        //比较子串的第j个位置的字符是否相等
                                flag = 1;                                  //如果不等，则退出比较，当前子串长度i的划分不满足要求，结束，更新i，进行下一次的搜索
                                break;
                            }
                        }
                        if(flag == 1) {
                            break;
                        }
                    }
                    if(flag == 0){
                        for(int j=0; j <i; j++){
                            System.out.print(str.charAt(j));
                        }
                        System.out.println();//true
                        return;
                    }
                }
            }
            System.out.println(false);//如果子串长度i的所有划分都不满足要求，则返回flase，表示该字符串不能由某个子串的若干倍组成 
    }
}

2.给定整数n，将n分解成i1+i2+...in=n，求i1*i2*...*in最大值

代码：

    /**
     * 招行笔试第二题：给定整数n，将n分解成i1+i2+...in=n，求i1*i2*...*in最大值
     * 策略：首先尽量分为3，其次分为4或者2
     */
    public static void test2(){
        Scanner scanner=new Scanner(System.in);
        while(scanner.hasNext()){
            int n=scanner.nextInt();
            int res=1;
            while(n-3>=2){
                n-=3;
                res*=3;
            }
            res*=n;
            System.out.println(res);
        }
    }

3.n组左右括号组成的合法组合（卡特尔数）

代码：

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
    /**
     * 招行笔试第三题：卡特尔数
     */
    public static void test3(){
        Scanner scanner=new Scanner(System.in);
        while (scanner.hasNext()){
            int n=scanner.nextInt();
            test33(n,n,"");
            for (int i=strList.size()-1;i>=0;i--){
                System.out.print(i>0?strList.get(i)+",":strList.get(i)+"\n");
            }
            strList.clear();
        }
    }
 
    public static void test33(int l,int r,String s){
        if (l==0&&r==0){
            strList.add(s);
            return;
        }
        if (l<r){
            test33(l,r-1,s+")");
        }
        if (l>0){
            test33(l-1,r,s+"(");
        }
    }