招商银行4/8第二题

首先测试样例的确给的挺坑的，第一位前面不能加符号，每两位数字间可以加符号或者不加，很多人0%的应该就是这问题
Java写的，回溯法，用一个数组来存每一位前面加符号的状态，再记下当前到第几位了。

把所有加符号状态都遍历出来（其实就是暴力），到最后一位的时候，也就是得到一种完整情况后，就去计算当前这一加符号状态得到的结果。

public class Problem2 {

    static int ans;
    static String str;
    static int tar;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while(T-->0) {
            str = sc.next();
            tar = sc.nextInt();
            ans = 0;
            recur(new int[str.length()], 1);
//            System.out.println("ans:" + ans);
            System.out.println(ans);
        }

    }

    private static void recur(int[] op, int pos) {
        if(pos == str.length()) {
            if(tar == checkOp(op)) {
                ans++;
            }
            return;
        }

        for(int i = 1; i <= 3; i++) {
            op[pos] = i;
            recur(op, pos+1);
            op[pos] = 0;
        }
        return;
    }

    /*
    1不操作
    2加好
    3减号
     */
    private static int checkOp(int[] op) {
//        if(op[0] != 1)
//            return tar-1;

        StringBuilder sb = new StringBuilder();
        sb.append(str.charAt(0));
        for (int i = 1; i < op.length; i++) {
            if(op[i] == 1) {
                sb.append(str.charAt(i));
            } else if( op[i] == 2) {
                sb.append('+').append(str.charAt(i));
            } else if( op[i] == 3) {
                sb.append('-').append(str.charAt(i));
            }
        }
        String s = sb.toString();

        int sum = 0;
        int *** = 1;
        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i)=='+') {
                *** = 1;
            } else if(s.charAt(i) == '-') {
                *** = -1;
            } else{
                int cur = 0;
                int x = i;
                while(x < s.length() && s.charAt(x) != '+' && s.charAt(x) != '-') {
                    cur = cur*10 + (s.charAt(x) - '0' );
                    x++;
                }
                sum += cur****;
                i = x-1;
            }
        }
//        System.out.println(s + "=" + sum);
        return sum;
    }


}

菜鸡第一次AC两题，发个帖嘚瑟一下/cy

#招商银行##笔试题目#