2020-10-13携程招聘算法题

先bb几句

好久没写博客，今年感情学业一团糟，去年及其热爱的NLP现在也不得不暂时放弃。 哎 世事难料，九到十月忙着校招，华为一面挂，B站网易携程58同城直接没给机会（笔试稀碎）， 其他大厂没投，现在还剩最后同程艺龙(苏州)一家22号面试。 10月初自己好好考虑了一下，主要因为我走了不少弯路，没有系统的去学习计算机基础课程，将最好的大二大三的时光用在了过于上层的AI，机器学习领域，导致秋招季算法岗没有资格投递，基础开发岗自己又基础不牢，导致笔试成绩可以说是稀碎，面试也是稀碎。 迄今为止 人生大写的失败 哈哈

题目：

现在很流行打卡，每到一个景点都会进行打卡发朋友圈，有这样一个任务； 每个城市有1-9个景点需要打卡，每次发朋友圈最多只能发9个打卡景点， 一个景点打一次卡，并且一个城市的打卡景点必须在一次发表中展现，所有景点必须全部打卡。 一次发表可以包括多个城市的景点。 给出一些城市的景点数，计算至少需要发多少次朋友圈。 =========================================================================================================== [1,1,2,3,4,5,6,9] 共计8个城市，每个城市对应需要打卡的景点数 最少需要发4次朋友圈。

思路

看到的第一秒觉得绝壁是回溯（毕竟是求数组排列组合这一块的），但是因为严蔚敏版/leetcode的经典回溯看多了，一时间做不出来 看：

但是难在 终止条件？但是某一次打卡数量不确定，打多少个城市也不确定 不确定的因素太多 所以 要用贪心的思想 1 打卡数量不确定：直接从最大打卡数量遍历到0（从最大开始必定能保证最终的打卡数是最小的） 2 多少城市不确定：不设置此限制条件即无所谓

def Card_Solve(landspaces, card_nums): ''' :param landspaces: 景点数组 :param card_nums: 每天最多打卡数 :return: ''' visited = [0 for _ in range(len(landspaces))] result = [] length = len(visited) solve(landspaces, length, card_nums, visited, result) return result def solve(landspaces, length, card_nums, visited, result): ''' :param landspaces: :param length: 输入数组的长度 :param card_nums: 此轮最多打卡数量 :param visited: 字面意思 :param result: 结果 :return: ''' if card_nums == 0: #还需打卡数已经为0，结束 return if sum(visited) == length-1: #还剩一个城市，直接放入result for i in range(length): if visited[i] == 0: result.append([landspaces[i]]) break return sumx = [] footprint = [] flag = 0 for i in range(length-1, -1, -1): if visited[i] == 0 and (sum(sumx)+landspaces[i] <= card_nums): sumx.append(landspaces[i]) footprint.append(i) if sum(sumx) == card_nums: result.append(sumx) flag = 1 break if flag == 1: # 若此次card_nums成功 则根据footprint更新visited for i in footprint: visited[i] = 1 solve(landspaces, length, card_nums, visited, result) # 重要如果此次成功，那么以相同card_nums再继续遍历 else: solve(landspaces, length, card_nums - 1, visited, result) if __name__ == '__main__': lands = [[1, 1, 2, 3, 4, 5, 6, 9], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [2, 2, 2, 2, 2, 2, 2, 7]] for i in lands: result = Card_Solve(i, 9) print("最少打卡数：{},\t 详细描述：{}".format(len(result), result))