阿里笔试，1，2题解法

没有参加笔试，自己写的解法，可能有漏洞，有兴趣的可以参考。

第一题：剪枝优化的回溯算法在每张牌都4张都情况下（最复杂情况），测试时间为4ms

public class getPoker {
    int min = Integer.MAX_VALUE;
    int[] poker;

    public int getCount(int[] arr) {
        poker = arr;
        backtrace(0, 0);
        return min;
    }

    public void backtrace(int n, int count) {
        if (n >= 10) {
            min = Math.min(min, count);
            return;
        }
        if (poker[n] == 0) {
            backtrace(n + 1, count);
            return;
        }
        int one = getContinue(n);
        int two = getTwoContinue(n);
        if (one > 0) {     //可以打顺子
            divide(n, 1, 5);
            backtrace(n, count + 1);
            add(n, 1, 5);
        }
        if (two > 0) {     //可以打连对
            divide(n, 2, 3);
            backtrace(n, count + 1);
            add(n, 2, 3);
        }
        if (poker[n] >= 2) {  //可以打对子
            poker[n] -= 2;
            backtrace(n, count + 1);
            poker[n] += 2;
            return;   //因为能打对子就不会打单张，此时return
        }
        {
            poker[n]--;
            backtrace(n, count + 1);
            poker[n]++;
        }
    }

    public int getContinue(int n) {     //判断顺子
        if (n + 1 > 6)
            return 0;
        int min = 5;
        for (int i = n; i < n + 5; i++) {
            min = Math.min(min, poker[i]);
        }
        return min;
    }

    public int getTwoContinue(int n) {   //判断连对
        if (n + 1 > 8)
            return 0;
        int min = 5;
        for (int i = n; i < n + 3; i++) {
            min = Math.min(min, poker[i] / 2);
        }
        return min;

    }

    public void divide(int n, int count, int time) {
        for (int i = n; i < n + time; i++) {
            poker[i] = poker[i] - count;
        }
    }

    public void add(int n, int count, int time) {
        for (int i = n; i < n + time; i++) {
            poker[i] = poker[i] + count;
        }
    }

    public static void main(String[] args) {
        int[] arr = {4,4,4,4,4,4,4,4,4,4};
        System.out.println(new getPoker().getCount(arr));
    }
}

第二题动态规划

public class getMusic {
    public static int music(String[] s){
        Arrays.sort(s);
        int count = s[0].length();
        int dp[] = new int[s.length];   //dp数组为包含当前字符串的最大长度
        dp[0] = s[0].length();
        for (int i = 1; i < s.length; i++) {
            int j = s[i].length();    
            char x = s[i].charAt(0);
            for (int k = 0; k < i; k++) {
                char y = s[k].charAt(s[k].length() - 1);
                if(x >= y){   //判断是否可以连接
                    j = Math.max(dp[k] + s[i].length(), j);  //寻找可以连接的最大长度
                }
            }
            dp[i] = j;
            count = Math.max(count,j);
        }
        return count;
    }

    public static void main(String[] args) {
        String[] s = new String[]{"xxxxxxxxxxz","zzz","azz","bcdz"};
        System.out.println(music(s));
    }
}

#阿里笔试2020##笔试题目##阿里巴巴#