20200320阿里笔试题

题目来源以及题解：
https://www.nowcoder.com/discuss/387100?type=0&order=0&pos=52&page=1
https://www.nowcoder.com/discuss/387726?type=post&order=time&pos=&page=1
https://www.nowcoder.com/discuss/387802?type=1

第二题：

作者：牛客585071975号
链接：https://www.nowcoder.com/discuss/387802?type=1
来源：牛客网
小明在学旋律，每段旋律都可以用字符串来表示，并且旋律的每个字符的ASCALL码递增的比如以下4段旋律 ：aaa bcd bcdef zzz 现在就是要求，小明能够吧这些旋律拼接起来组成最长的旋律。比如上述例子输出 11 最长的旋律为 aaabcdefzzz `

思路（一堆废话预警）（看了大佬们的题解才看懂）：

先用一个列表保存输入的旋律musicList（比如['aaa', 'bcd', 'bcdef', 'zzzz']）
然后利用动态规划，dp[i]表示当有第i段旋律时，拼接起来组成最长的旋律长度
比如dp[2]表示有'aaa', 'bcd', 'bcdef'这三段旋律时，拼接起来组成最长的旋律长度为8（aaabcdef）

问题来了， 如何求dp[i]

1. 首先要把musicList按照ASCII码递增排序 musicList.sort()
2. dp[0] 就是列表中第一段旋律的长度（此时只有一段旋律）
3. 当i>.0， 判断musicList[i]这段旋律能否与它前面的旋律拼接起来
   比如i=2，要判断bcdef能否拼接在aaa后面、能否拼接在bcd后面。（让bcdef去与bcdef前面的旋律aaa、bcd都试探一下）
   • 如果能拼接在aaa后面，拼接后的长度为dp[0] + len(musicList[i])
   • 如果能拼接在bcd后面，拼接后的长度为dp[1] + len(musicList[i])
   • 判断是否能拼接：musicList[i]的首个字符ASCII码要≥ 待拼接旋律最后一个字符ASCII码

题解：https://www.nowcoder.com/discuss/387726?type=post&order=time&pos=&page=1

或者是从前往后想，上面的第三步：

3. 当i>.0， 判断musicList[i]这段旋律能否与它后面的旋律拼接起来
   对于 一段旋律i， 遍历它后面的旋律j=i+1,….，看后面的旋律能否加在这段旋律后面
   比如 bcd , 判断bcdef能否加在bcd后面、判断zzzz能否加在bcd后面
   即：dp[j] = 已拼接好bcd的旋律的最长长度+ musicList[j]的长度

大佬题解地址：https://www.nowcoder.com/discuss/387100?type=0&order=0&pos=52&page=1

image.png

照着大佬的题解，补充了读取输入，下面是完整的程序：

关键函数是大佬写的我只是照着写了一遍，大佬本来的代码在上面

import sys
class Solution:
    def getMusic(self,musicList):
        if not musicList: return 0
        musicList.sort() #把旋律们按照升序排序
        dp = [0 for _ in range (len(musicList))]
        dp[0] = len(musicList[0])
        for i in range(len(musicList)):
            for j in range(i+1,len(musicList)):
                if musicList[j][0] >= musicList[i][-1]:
                    dp[j] = dp[i] + len(musicList[j])
        return dp[-1]

if __name__ == "__main__":
    solution = Solution()
    try:
        musicList = []
        while True:
            m = sys.stdin.readline().strip()
            if m == '':
                break
            m = list(m.split())
            musicList.extend(m) #存成一个一维list
        print(musicList)
    except:
        pass
    res = solution.getMusic(musicList)
    print(res)

image.png

第一题：

题目来源 https://www.nowcoder.com/discuss/387802?type=1
有一叠扑克牌，每张牌介于1和10之间
有四种出牌方法：
单出1张
出2张对子
出五张顺子，如12345
出三连对子，如112233
给10个数，表示1-10每种牌有几张，问最少要多少次能出完

明天接着看今天看不动了