阿里巴巴2020春招暑期实习笔试题

今天药忘吃喽~ 2023-07-17 15:47 23阅读 0赞

> 周五参加阿里暑期实习的笔试，一共两道编程题，一小时时间，在这里总结记录一下此次笔试题！

### 第一题 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTk5NDU1_size_16_color_FFFFFF_t_70_pic_center]

##### **题目描述**： #####

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

有四种出牌方法：

*  单出一张
 *  出两张相同的牌(对子)
 *  出五张顺子(如12345)
 *  出三连对子(如112233)

给10个数，表示1-10每种牌有几张，问最少要多少次能出完？

##### **题目解析：** #####

> 该题目需要去考虑到多种状态，起初考虑使用DP求解，但是没有找到动态转移方程，所以采用暴力回溯法求解：
> 
> 1、每次根据当前牌的情况优先执行连对 -> 顺子 -> 对子 -> 单子；  
> 2、执行完当前情况，回溯到执行前的状态，若满足下一优先级的执行方式，则继续执行，以此类推，递归查询到最少次数；

代码如下：

public class Main { 
        /** * 测试用例： * 1 1 1 2 2 2 2 2 1 1 * * 输出结果：3 * */
        public static void main(String[] args) { 
            Scanner scanner = new Scanner(System.in);
            //num记录牌的总数
            int num = 0;
            //ans记录最终出牌次数
            int ans = 0;
            int temp;
            int[] cards = new int[10];
            for(int i=0; i<10; i++){ 
                temp = scanner.nextInt();
                cards[i] = temp;
                num += temp;
            }
            //如果只有一张牌则直接返回
            if(num == 1){ 
                System.out.println(1);
                return;
            }
    
            //使用暴力回溯发求解
            ans = getNum(cards, 0);
    
            System.out.println(ans);
        }
        private static  int getNum(int[] cards, int k){ 
            int ans = Integer.MAX_VALUE;
            if(k >= cards.length)
                return 0;
            //若牌数为0则继续下一张
            else if (cards[k] == 0){ 
                return getNum(cards,k+1);
            }
    
            //优先出连对
            if(k <= cards.length-3 && cards[k] >= 2 && cards[k+1] >= 2 && cards[k+3] >= 2){ 
                cards[k] -= 2;
                cards[k+1] -= 2;
                cards[k+2] -= 2;
                ans = Math.min(1+getNum(cards, k), ans);
                cards[k] += 2;
                cards[k+1] += 2;
                cards[k+2] += 2;
            }
    
            //出顺子
            if(k <= cards.length - 5 && cards[k] >= 1 && cards[k+1] >=1 && cards[k+2] >= 1 && cards[k+3] >= 1 && cards[k+4] >=1){ 
                cards[k] -= 1;
                cards[k+1] -= 1;
                cards[k+2] -= 1;
                cards[k+3] -= 1;
                cards[k+4] -= 1;
                ans = Math.min(1+getNum(cards, k), ans);
                cards[k] += 1;
                cards[k+1] += 1;
                cards[k+2] += 1;
                cards[k+3] += 1;
                cards[k+4] += 1;
            }
    
            //出对子
            if(cards[k] >= 2){ 
                cards[k] -= 2;
                ans = Math.min(1+getNum(cards, k), ans);
                cards[k] += 2;
            }
    
            //出单子
            if(cards[k] >= 1){ 
                cards[k] -= 1;
                ans = Math.min(1+getNum(cards, k), ans);
                cards[k] += 1;
            }
            return ans;
        }
    }
    
    
    //

### 第二题 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTk5NDU1_size_16_color_FFFFFF_t_70_pic_center 1]

#### 题目解析： ####

> 使用dp来进行求解，关键在于状态转移的存储，这里定义一个一维数组，存储当前位置的最长字符串长度。  
> 初始化：dp\[i\] = string.length;  
> 状态方程：dp\[i\] = max((dp\[j\] + temp.length), dp\[i\]) , i代表当前位置

代码如下：

public class Test2 { 
        /** * 测试用例： * 4 * aaa * bcd * zzz * bcdef * * 答案输出： * 11 * */
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            if(n == 1){ 
                System.out.println(sc.nextLine());
                return;
            }
            //list存储输入的字符串
            ArrayList<String> list = new ArrayList<>();
            for(int i=0; i<n; i++){ 
                list.add(sc.next());
            }
    
            Collections.sort(list);
    
            int ans = longestlength(list);
            System.out.println(ans);
    
        }
    
        /** * 获取最长字符串长度 * 使用ＤＰ进行求解，dp[i] = string.length; * @param list 所有输入的字符串 * @return 返回int类型的长度 */
        private static int longestlength(ArrayList<String> list){ 
            int[] dp = new int[list.size()];
            String temp,str ;
            for(int i=list.size()-1; i>=0; i--){ 
                temp = list.get(i);
                for(int j=i; j<list.size(); j++){ 
                    str = list.get(j);
                    if(i == j){ 
                        dp[i] = temp.length();
                    }
                    /** * 注意这里的条件判断，当ｉ　＝＝　j时 * 测试用例：4 * aaa * bcd * zzz * bcdef * * ｄｐ初始化过程中，第一步执行zzz, 此时若没有 i!=j 的判断，则会进入该if条件句，导致dp[3] = 6，结果错误！！！ * */
                    if(temp.charAt(temp.length() - 1) <= str.charAt(0) && i != j){ 
                        dp[i] = Math.max(temp.length() + dp[j], dp[i]);
                    }
                }
            }
            return dp[0];
        }
    }

> 欢迎读者一起交流，代码实现如有错误和优化之处还望指出，期待有其他解决思路的读者可以分享一下，感谢！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTk5NDU1_size_16_color_FFFFFF_t_70_pic_center]: /images/20230528/eb951c14f9104a9fb5fbddd9e69040c2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTk5NDU1_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20230528/44c4aef42b1e425ca18e4c2ebcbeb75d.png