阿里妈妈4.3日笔试题
1.有一叠扑克牌，每张牌介于1和10之间
有四种出牌方法：
- 单出1张
- 出2张对子
- 出五张顺子，如12345
- 出三连对子，如112233
给10个数，表示1-10每种牌有几张，问最少要多少次能出完
回溯与搜索：
import java.util.*;
public class AliBaba4_3_1 {
private static int min_count=Integer.MAX_VALUE;
//1-10数字的牌数
private static int[] poker=new int[10];
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int cnt=0;
while(cnt<10){
poker[cnt]=scanner.nextInt();
cnt++;
}
//from:从哪个数字牌开始，count：已经出了多少次牌
backtrace(0,0);
System.out.println(min_count);
}
//从from顺序出牌,count表示已经出了多少次牌，深搜
public static void backtrace(int from,int count){
//牌全出完了
if(from>=10){
min_count=Math.min(min_count,count);
return;
}
//当前数字牌数为0，从下一数字牌开始
if(poker[from]==0){
backtrace(from+1,count);
return;
}
//搜索出牌方案
//能出3连对
if(canContinuesTwo(from,3)){
takeIt(from,from+2,2);
backtrace(from,count+1);
returnBack(from,from+2,2);
}
//能出顺子
if(canContinuesOne(from,5)){
takeIt(from,from+4,1);
//继续搜索
backtrace(from,count+1);
//回溯
returnBack(from,from+4,1);
}
//能出连对
if(poker[from]>=2){
takeIt(from,from,2);
//继续搜索
backtrace(from,count+1);
//回溯
returnBack(from,from,2);
}
//出单张
takeIt(from,from,1);
//继续搜索
backtrace(from,count+1);
//回溯
returnBack(from,from,1);
}
public static boolean canContinuesOne(int from,int count){
if(from+count>=10)return false;
for(int i=from;i<from+count;i++){
if(poker[i]<1)return false;
}
return true;
}
public static boolean canContinuesTwo(int from,int count){
if(from+count>=10)return false;
for(int i=from;i<from+count;i++){
if(poker[i]<2)return false;
}
return true;
}
public static void takeIt(int from,int end,int count){
for(int i=from;i<=end;i++){
poker[i]-=count;
}
}
public static void returnBack(int from,int end,int count){
for(int i=from;i<=end;i++){
poker[i]+=count;
}
}
}
2.首先定义上升字符串s，s[i]≥s[i−1],比如aaa，abc是，acb不是
给n个上升字符串，选择任意个拼起来，问能拼出来的最长上升字符串长度
给n个上升字符串，选择任意个拼起来，问能拼出来的最长上升字符串长度
动态规划：
import java.util.*;
public class AliBaba4_3_2 {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int N=Integer.valueOf(scanner.nextLine());
System.out.println(N);
//按照尾字母从小到大排序；如果相同则按照首字母从小到大排序
List<String>input=new ArrayList<>();
while(input.size()<N){
input.add(scanner.nextLine());
System.out.println(input.size());
}
input.sort(new Comparator<String>() {
@Override public int compare(String o1, String o2) {
if(o1.charAt(o1.length()-1)==o2.charAt(o2.length()-1))
return o1.charAt(0)-o2.charAt(0);
return o1.charAt(o1.length()-1)-o2.charAt(o2.length()-1);
}
});
//dp[i]表示以i+'a'字符结尾的最大连接长度
int dp[]=new int[26];
int max_len=0;
for(int i=0;i<N;i++){
String s=input.get(i);
char right=s.charAt(s.length()-1);
char left=s.charAt(0);
int max_temp=0;
for(int j=0;j<=left-'a';j++){
//找出以某个字符（小于等于字符left）结尾的最大连接长度
max_temp=Math.max(max_temp,dp[j]);
}
dp[right-'a']=max_temp+s.length();
max_len=Math.max(max_len,dp[right-'a']);
}
System.out.println(max_len);
}
} 输入：bcde aa aaa aab aaab bcf acdf 输出13 
