阿里妈妈4.3日笔试题

1.有一叠扑克牌,每张牌介于1和10之间

有四种出牌方法:

  1. 单出1张
  2. 出2张对子
  3. 出五张顺子,如12345
  4. 出三连对子,如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[i1],比如aaa,abc是,acb不是
给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
#阿里笔试423##阿里巴巴##笔试题目#
全部评论

相关推荐

06-27 12:54
已编辑
门头沟学院 Java
累了,讲讲我的大学经历吧,目前在家待业。我是一个二本院校软件工程专业。最开始选专业是觉得计算机感兴趣,所以选择了他。本人学习计算机是从大二暑假结束开始的,也就是大三开始。当时每天学习,我个人认为Java以及是我生活的一部分了,就这样持续学习了一年半,来到了大四上学期末,大概是在12月中旬,我终于找的到了一家上海中厂的实习,但我发现实习生的工作很枯燥,公司分配的活也不多,大多时间也是自己在自学。就这样我秋招末才找到实习。时间来到了3月中旬,公司说我可以转正,但是转正工资只有7000,不过很稳定,不加班,双休,因为要回学校参加答辩了,同时当时也是心高气傲,认为可以找到更好的,所以放弃了转正机会,回学校准备论文。准备论文期间就也没有投递简历。然后时间来到了5月中旬,这时春招基本也结束了,然后我开始投递简历,期间只是约到了几家下场面试。工资也只有6-7k,到现在我不知道该怎么办了。已经没有当初学习的心劲了,好累呀,但是又不知道该干什么去。在家就是打游戏,boss简历投一投。每天日重一次。26秋招都说是针对26届的人,25怎么办。我好绝望。要不要参加考公、考研、央国企这些的。有没有大佬可以帮帮我。为什么感觉别人找工作都是顺其自然的事情,我感觉自己每一步都在艰难追赶。八股文背了又忘背了又忘,我每次都花很长时间去理解他,可是现在感觉八股、项目都忘完了。真的已经没有力气再去学习了。图片是我的简历,有没有大哥可以指正一下,或者说我应该走哪条路,有点不想在找工作了。
码客明:太累了就休息一下兄弟,人生不会完蛋的
如果实习可以转正,你会不...
点赞 评论 收藏
分享
评论
点赞
7
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务