Python 小白的 Leetcode Daily Challenge 刷题计划 - 20240209（除夕）

本文主要是介绍Python 小白的 Leetcode Daily Challenge 刷题计划 - 20240209（除夕），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

368. Largest Divisible Subset

难度：Medium

• 动态规划 + 方案还原

Yesterday's Daily Challenge can be reduced to the problem of shortest path in an unweighted graph while today's daily challenge can be reduced to the problem of longest path in an unweighted graph.
Happy Chinese New Year!

class Solution:def largestDivisibleSubset(self, nums: list[int]) -> list[int]:n = len(nums)nums.sort()f, pre = [1]*n, [-1]*nt = 0for i in range(n):for j in range(i):if nums[i] % nums[j] == 0:if f[j]+1 > f[i]:f[i] = f[j]+1pre[i] = jif f[i] > f[t]:t = ians = []while t != -1:ans.append(nums[t])t = pre[t]return ansdef test():samples = [[1,2,3],[1,2,4,8]]sol = Solution()for nums in samples:print(sol.largestDivisibleSubset(nums))if __name__ == '__main__':test()

这篇关于Python 小白的 Leetcode Daily Challenge 刷题计划 - 20240209（除夕）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---