【阿里巴巴校园招聘】【技术类】在线笔试3.20场

题目一

题意

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

有四种出牌方法：

1. 单出1张
2. 出2张对子
3. 出五张顺子，如12345
4. 出三连对子，如112233

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

思路

爆搜
dfs 1-10，每次枚举能否按照四种情况出牌，如果当前牌出完了，dfs下一个，否则继续dfs当前值
复杂度大概在4104^{10}410

题目二

题意

首先定义上升字符串，s[i]≥s[i−1]s[i] \ge s[i-1]s[i]≥s[i−1],比如aaa，abc是，acb不是
给n个上升字符串，选择任意个拼起来，问能拼出来的最长上升字符串长度

思路

排序+dp

首先按照字符串最后一个字母，由小到大排序，如果最后一个相同，按第一个由小到大

然后定义dp数组，dp[i]表示以字母'a'+i结尾的最长上升字符串长度
枚举输入的字符串，假设当前是s，l=s[0]-'a',r=*s.rbegin()-'a'
那么dp[r]=max⁡(dp[r],max⁡i=0l(dp[i])+s.size())dp[r] = \max(dp[r],\max\limits_{i=0}^l(dp[i])+s.size())dp[r]=max(dp[r],i=0maxl(dp[i])+s.size())
复杂度大概26n26n26n