蚂蚁金服两道编程题

说明：当时考试时长60分钟，没有做出来这两道题；是事后自己写出来的，不知道是否可以全部AC。

最少出牌次数

来源：阿里巴巴-蚂蚁金服
思路就是，共有1 2 3 4 5 6 7 8 9 10 这十种牌，输入的是每种牌的个数，每种牌个数在0-4之间，可以出的牌型有：

• 单排
• 对子
• 顺子 12345 34567 等
• 连对 112233 445566等。
  输出最少出牌次数。

思路：首先，每次出什么牌可以自己做出选择，也就是每次都可以从4种牌型中出牌（前提是存在该牌型），因此可以使用深度优先搜索的方法，主要内容如下：

"""
2020-03-20：考试的最后时间想到思路
2020-03-21：今天解决了这个问题。
"""
def output_a(nums, a=1):
    """返回出单牌或者对子之后所有可能的结果"""
    seqs = []
    for i in range(len(nums)):
        if nums[i] >= a:
            temp_nums = nums[:]
            temp_nums[i] -= a
            seqs.append(temp_nums)
    return seqs


def sequence_index(nums, a, b):
    """输出所有可以出的顺子或者连对的下标"""
    n = len(nums)
    seqs_index = []

    i = 0
    j = i + b
    while j <= n:
        if min(nums[i:j]) >= a:
            # 此时说明区间i到j中存在顺子
            seqs_index.append(list(range(i, j)))
        i += 1
        j = i+b
    return seqs_index


def output_sequence(nums, a=1, b=5):  # 默认情况下是输出顺子
    """返回出顺子之后的所有可能的结果"""
    seqs_index = sequence_index(nums, a, b)
    seqs = []   # 保存所有可能的出牌之后的序列
    for seq_index in seqs_index:
        temp_nums = nums[:]
        for index in seq_index:
            temp_nums[index] -= a
        seqs.append(temp_nums)
    return seqs


nums = [1, 1, 1, 2, 2, 2, 2, 2, 1, 1]
# 只有一张牌的情况
if sum(nums) == 1:
    print(1)

# print(len(output_a(nums, a=1)))


counts = []


def DFS(nums, count=0):
    # 深度优先搜索来遍历4种情况。
    global counts
    if sum(nums) == 0:
        counts.append(count)

    for i in ['aabbcc', 'abcde', 'aa','a']:
        # 为了减少出牌的次数，应该首先出顺子或者连对，这样可以最大化的减少出牌的次数。
        # 如果不使用这种方法，程序可能会迭代比较深，耗时很久才可能得到答案
        seqs = output_sequence(nums, a=1, b=5)
        if seqs:
            for seq in seqs:
                count += 1
                DFS(seq, count)
                count -= 1
            continue
        seqs = output_sequence(nums, a=2, b=3)
        if seqs:
            for seq in seqs:
                count += 1
                DFS(seq, count)
                count -= 1
            continue

        if i == 'a':
            # 考虑所有出单牌之后，剩余牌的结果，然后遍历所有的牌型，深度搜索。
            seqs = output_a(nums)
        if i == 'aa':
            seqs = output_a(nums, a=2)
        if i == 'abcde':
            seqs = output_sequence(nums, a=1, b=5)
        if i == 'aabbcc':
            seqs = output_sequence(nums, a=2, b=3)
        if seqs:
            for seq in seqs:
                count += 1
                DFS(seq, count)
                count -= 1
DFS(nums, 0)
print(min(counts))

关键：首先，明确这是一个深度优先搜索可以解决的问题，每次出牌有4种选择；接着，为了减少递归的次数，应该明确知道，每次出牌前先判断是否存在连对或者顺子，这样可以很大程度减少出牌次数；最后回溯的时候应该注意count值减少1.

合并最长连续子序列

来源：阿里巴巴-蚂蚁金服
已知有n个非递减序列，比如aaa, bcd, zzz, bcfg, 将这n个序列合并在一起构建一个最长的非递减序列，比如aaa, bcfg, zzz这3个可以构成 aaabcfgzzz长度为10的序列。

# """
# 思路：也可以使用深度递归的方法，遍历所有的可能，然后寻找出最合适的结果。
# """
def longest_sequence(st_list):
    flag = [False for i in range(len(st_list))]
    lengths = []
    sts = []
    min_all = None
    max_all = None

    def DFS(st):
        nonlocal min_all
        nonlocal max_all

        if set(st) not in sts:   # 转化为set来避免重复
            # 这里需要注意，添加的st应该是st内容的拷贝，后续st的变化不再影响这里面的值。
            # 如果写成st而不是st[:]，那么后面st发生变化的时候，sts内容也会发生变化
            sts.append(set(st[:]))   
            lengths.append(len(''.join(st[:])))

        for i in range(len(st_list)):
            if flag[i] == False:
                # 获取当前序列的最小、最大值
                min_alpha = st_list[i][0]
                max_alpha = st_list[i][-1]

                # 如果全局还没有最小和最大值，就使用第一个元素的最小和最大值来初始化。
                if not min_all and not max_all:
                    min_all = min_alpha
                    max_all = max_alpha
                    st.append(st_list[i])
                    flag[i] = True
                    DFS(st)
                    flag[i] = False
                    st.pop()
                    min_all = None
                    max_all = None
                    continue

                if min_alpha >= max_all:
                    max_all = max_alpha
                    st.append(st_list[i])
                    flag[i] = True
                    DFS(st)
                    flag[i] = False
                    st.pop()
                    if st:
                        max_all = max(''.join(st))

                elif max_alpha <= min_all:
                    min_all = min_alpha
                    st.append(st_list[i])
                    flag[i] = True
                    DFS(st)
                    flag[i] = False
                    st.pop()

    DFS([])
    return lengths, sts


st_list = ['aaa','bcd','zzz','bcfg']
lengths, sts = longest_sequence(st_list)
print(max(lengths))
print(sts)

需要注意两点：

1. 每次增加或者修改元素进行下一步递归的时候，当回溯的时候也要对应的修改状态、st以及min_all和max_all.
2. 添加到sts中的元素应该是st[:]，也就是st的内容拷贝，否则，在之后的代码中如果st发生了变化，那么sts也对应的会产生改变，从而造成错误。