庞果网合法字符串

题目详情:
用n个不同的字符（编号1 - n），组成一个字符串，有如下2点要求：
1、对于编号为i 的字符，如果2 * i > n，则该字符可以作为最后一个字符，但如果该字符不是作为最后一个字符的话，则该字符后面可以接任意字符；
2、对于编号为i的字符，如果2 * i <= n，则该字符不可以作为最后一个字符，且该字符后面所紧接着的下一个字符的编号一定要 >= 2 * i。
问有多少长度为M且符合条件的字符串。
例如：N = 2，M = 3。则abb, bab, bbb是符合条件的字符串，剩下的均为不符合条件的字符串。

输入：n,m (2<=n,m<=1000000000)；
输出：满足条件的字符串的个数，由于数据很大，输出该数Mod 10^9 + 7的结果。

函数头部
int validstring(int n,int m) {

}

代码如下：

import java.math.BigDecimal;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static int validstring(int n,int m) {
        if (n > 2 || m > 1000000000){
            System.err.println("‘n’或者‘m’超出范围了！");
            return 0;
        }
        long count = countValid(n, m);
        return BigDecimal.valueOf(count % (Math.pow(10, 9) + 7)).intValue();
    }
    
    //n个字符m位的全排列组合
    private static long countValid(int n, int m) {
        String v = "";
        long s = 0;
        char[] charArray = buildCharArray(n);
        // 队列用来保存被访问节点的分支节点(邻接点）
        Queue<String> que = new LinkedList<String>();
        que.offer(v);// 起点入队列
        while (!que.isEmpty()) {
            v = que.poll();// 弹出当前顶点
            // 将当前节点的分支节(邻接）点加入到队列中
            for (int i = 0; i < n; i++) {
                String u = v + charArray[i];
                if (u.length() == m) {//m位，则校验是不是符合题目的要求
                    if (checkStr(u, charArray, 0)){
                        System.out.println(u);
                        ++s;
                    }
                } else{
                    que.add(u); // 邻接点入队
                }
            }
        }
        return s;
    }
    
    //校验字符串是否符合规则
    private static boolean checkStr(String str, char[] charArray, int j){
        boolean returnFlag = false;
        int n = charArray.length;
        int m = str.length();
        char c = str.charAt(j);
        Integer i = getCharArrayIndex(charArray, c);
        //如果2 * i > n，则该字符可以作为最后一个字符，但如果该字符不是作为最后一个字符的话，则该字符后面可以接任意字符；
        if (2 * (i + 1) > n){
            if (j == m - 1){
                returnFlag = true;
            }else{
                returnFlag = checkStr(str, charArray, j + 1);
            }
        }else{//如果2 * i <= n，则该字符不可以作为最后一个字符，且该字符后面所紧接着的下一个字符的编号一定要 >= 2 * i。
            if (j == m - 1){
                returnFlag = false;
            }else{
                char d = str.charAt(j + 1);
                int ii = getCharArrayIndex(charArray, d);
                if (ii + 1 < 2 * (i + 1)){
                    returnFlag = false;
                }else{
                    returnFlag = checkStr(str, charArray, j + 1);
                }
            }
        }
        return returnFlag;
    }
    
    private static Integer getCharArrayIndex(char[] charArray, char c){
        Integer returnIndex = null;
        for (int i = 0; i < charArray.length; i++){
            char d = charArray[i];
            if (d == c){
                returnIndex = i;
            }
        }
        return returnIndex;
    }
    
    //产生1-n的随机字符
    private static char[] buildCharArray(int n){
        StringBuffer returnValue = new StringBuffer();
        for (int i = 0; i < n; i++){
            char c = 'a';
            c = (char)(c + i);
            returnValue.append(c);
        }
        return returnValue.toString().toCharArray();
    }

    //start 提示：自动阅卷起始唯一标识，请勿删除或增加。 
    public static void main(String args[]) 
    { 
           System.out.println(validstring(2, 10) + " 次");
    } 
    //end //提示：自动阅卷结束唯一标识，请勿删除或增加。
}

补充：软件开发 , Java ,

庞果网 合法字符串

庞果网合法字符串