算法ak

第一题

小X和小Y正在进行加密算法有关的研究。

小X提出了一种简单的加密算法:对于一个只包含小写英文字母的字符串，将’a’替换成1,’b'替换成2.… ’ z’替换成26，比如一个字符串’abcyz’,加密后变成:1232526’。但是小Y觉得对于一个加密后的数字串可能对应很多原串:比如’1232526’可能表示’abcyz’,也可能表示’abcbebf',也可能表示’Icyz’但固执的小X并不想听取小Y的想法。为了说服小X，小Y希望能计算出某个加密后的数字串可能对应的原串个数，由于答案可能很大，请输出答案对1000000007(10^9+7)取模后的结果。

package com.面试中的算法.三六零;

import java.util.Scanner;

/**
 * @author xing'chen
 * @version 1.0
 * @description: TODO
 * @date 2024/9/28 17:38
 */
public class MAIN {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String str= sc.next();
        System.out.println(numdecoding(str));
    }

    private static int numdecoding(String str) {
        int  mod=1000000007;
        int n=str.length();
        int[] dp=new int[n+1];
        dp[0]=1;
        dp[1]=str.charAt(0)=='0'?0:1;
        for (int i=2; i<=n; i++){
            int one = Integer.parseInt(str.substring(i-1,i));//取一位
            int two = Integer.parseInt(str.substring(i-2,i));//取一位
            if (one>=1&&one<=9){
                dp[i]=(dp[i]+dp[i-1])%mod;
            }
            if (two>=10&&two<=26){
                dp[i]=(dp[i]+dp[i-2])%mod;
            }
        }
        return dp[n];
    }
}

第二题

某公司有n名员工，第i名员工具有的能力可以用一个正整数a,描述，称为员工的能力值,现在，公司有一个项目需要交给恰好[n/2]名员工负责。为了保证项目能顺利进行，要求负责该项目的所有员工能力值之和大于等于x。

公司希望你可以帮忙求出，有多少种不同的派遣员工来负责这个项目的方案。上文中，[x]表示大于等于x的最小整数，例如[4]=4，[4.2]=5。认为两个方案不同，当且仅当存在一名员工在一种方案中负责该项目，而在另一种方案中不负责。

package com.面试中的算法.三六零;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author xing'chen
 * @version 1.0
 * @description: TODO
 * @date 2024/9/28 17:50
 */
public class Main2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        for (int i = 0; i < T; i++) {
            int n = scanner.nextInt();
            int x=  scanner.nextInt();
            int[] ab=new int[n];
            for (int j = 0; j < n; j++) {
                ab[j]=scanner.nextInt();
            }
            System.out.println(get(n,x,ab));
        }
    }

    private static int get(int n, int x, int[] ab) {
        int acquire=(n+1)/2;
        List<List<Integer>> ans=new ArrayList<List<Integer>>();
        generateCombinate(ab,ans,new ArrayList<Integer>(),0,acquire);
        int valid=0;
        for (List<Integer> combination : ans) {
            int sum=0;
            for (Integer integer : combination) {
                sum+=integer;
            }
            if(sum>=x){
                valid++;
            }
        }
        return valid;
    }
    private static void generateCombinate(int[] ab, List<List<Integer>> ans, ArrayList<Integer> combination, int index, int acquire) {
        if(combination.size()==acquire){
            ans.add(new ArrayList<>(combination));
            return;
        }
        for (int i = index; i <ab.length; i++) {
            combination.add(ab[i]);
            generateCombinate(ab,ans,combination,i+1,acquire);
            combination.remove(ans.size()-1);
        }
    }

}