阿里笔试，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));
}
}
本地你俩不是乱杀