Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0.
If there are multiple solutions, return any subset is fine.
給出一個(gè)不重復(fù)的正整數(shù)集合，找出滿足 Si % Sj = 0 或者 Sj % Si = 0 的最長(zhǎng)可整除子序列。如果有多個(gè)解，只需返回任意一個(gè)即可
nums: [1,2,3]
Result: [1,2] (of course, [1,3] will also be ok)
nums: [1,2,4,8]
Result: [1,2,4,8]
動(dòng)態(tài)規(guī)劃解。這道題和LIS非常相似，LIS的要求是遞增，而最長(zhǎng)可正整除序列的要求則是可整除。所以只要我們先將列表排序，這樣只需判斷 Si % Sj = 0 （i > j），再接下來(lái)就和LIS完全一樣了（和我上一篇差不多就不寫了）。不過(guò)這里需要輸出一種結(jié)果。所以我們還需要額外保存每個(gè)元素的上一個(gè)元素索引。
class Solution(object): def largestDivisibleSubset(self, nums): """ :type nums: List[int] :rtype: List[int] """ if len(nums) == 0: return [] # 先排序保證只需要相除一次 nums.sort() dp = [1] * len(nums) dp_index = [-1] * len(nums) # 保存元素的上一個(gè)元素的索引，用于得到序列 max_len = 1 # 維護(hù)一個(gè)最長(zhǎng)子序列的長(zhǎng)度 for index_n, n in enumerate(nums): for i in range(index_n): if n % nums[i] == 0 and dp[i] + 1 > dp[index_n]: dp[index_n] = dp[i] + 1 dp_index[index_n] = i # 每次更新dp時(shí)同時(shí)保存其上一個(gè)元素的索引 max_len = max(dp[i] + 1, max_len) result = [] # 定位到第一個(gè)最長(zhǎng)子序列的結(jié)尾 index = dp.index(max_len) # 根據(jù)dp_index反向保存最長(zhǎng)子序列 while index != -1: result.append(nums[index]) index = dp_index[index] # 得到上一個(gè)元素的索引 result.reverse() # 倒序 return result新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
