编程开发 购物 网址 游戏 小说 歌词 地图 快照 股票 美女 新闻 笑话 | 汉字 软件 日历 阅读 下载 图书馆 开发 租车 短信 China
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
移动开发 架构设计 编程语言 互联网 开发经验 Web前端 开发总结
开发杂谈 系统运维 研发管理 数据库 云 计 算 Java开发
VC(MFC) Delphi VB C++(C语言) C++ Builder 其它开发语言 云计算 Java开发 .Net开发 IOS开发 Android开发 PHP语言 JavaScript
ASP语言 HTML(CSS) HTML5 Apache MSSQL数据库 Oracle数据库 PowerBuilder Informatica 其它数据库 硬件及嵌入式开发 Linux开发资料
  编程开发知识库 -> 云计算 -> 368. Largest Divisible Subset -> 正文阅读
 

[云计算]368. Largest Divisible Subset[第1页]

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.
Example 1:

nums: [1,2,3]

Result: [1,2] (of course, [1,3] will also be ok)

Example 2:

nums: [1,2,4,8]

Result: [1,2,4,8]

一般来说,DP是不能用来求解具体方案的,但是这个题目中只是要求返回任意的一个,因此也是可以使用DP来做的。
java

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        List<Integer> arr = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return arr;
        }
        Arrays.sort(nums);
        int[] f = new int[nums.length];
        int[] rec = new int[nums.length];
        for (int i = 0; i < f.length; i++) {
            f[i] = 1;
            rec[i] = -1;
        }
        for (int i = 1; i < f.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0) {
                    if (f[i] > f[j] + 1) {
                        continue;
                    } else {
                        f[i] = f[j] + 1;
                        rec[i] = j;
                    }
                }
            }
        }
        int sum = 0;
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if (sum < f[i]) {
                sum = f[i];
                index = i;
            } else {
                continue;
            }
        }
        arr.add(nums[index]);
        while (rec[index] != -1) {
            arr.add(0, nums[rec[index]]);
            index = rec[index];
        }
        return arr;
    }
}

阅读全文
版权声明:本文为博主原创文章,未经博主允许不得转载。
本文已收录于以下专栏:

发表评论
HTML/XML objective-c Delphi Ruby PHP C# C++ JavaScript Visual Basic Python Java CSS SQL 其它
相关文章推荐
[leetcode] 368. Largest Divisible Subset
题目链接: https://leetcode.com/problems/largest-divisible-subset/ Given a set of distinct positiv...
TonyYang1995 2016-07-30 11:53 177 LeetCode #368: Largest Divisible Subset
Problem Statement(Source) Given a set of distinct positive integers, find the largest subset such th...
junchen1992 2016-09-18 22:49 94 368. Largest Divisible Subset -Medium
Question Given a set of distinct positive integers, find the largest subset such that every pair (...
Euadvancer 2017-02-05 21:26 87 Leetcode 368. Largest Divisible Subset
368. Largest Divisible Subset Total Accepted: 939 Total Submissions: 2935 Difficulty: Medium ...
fantasiasango 2016-06-29 03:16 924 Leetcode 368. Largest Divisible Subset[medium]
题目: Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj...
qq379548839 2016-10-14 22:22 67 leetcode_middle_79_368. Largest Divisible Subset
题意: 给一列数,找出其中最长的一个子序列。使序列中所有的数字两两可整除。 分析: 随便举个例子分析dp[ i ] 1  2  3  9  16  32 比如截止9这时候最长的是139,但是到最...
pusude 2017-03-08 15:16 69 Leetcode 368. Largest Divisible Subset
-题目Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) ...
sdcs2016_dyq 2016-10-31 21:55 76 [leetcode] 368. Largest Divisible Subset
Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of...
TstsUgeg 2016-07-04 16:02 204 Leetcode 368. Largest Divisible Subset思路及详解
题目链接:368. Largest Divisible SubsetGiven a set of distinct positive integers, find the largest subset...
xindoo 2016-11-05 17:58 244 LeetCode No.368. Largest Divisible Subset
LeetCode No.368. Largest Divisible Subset
woshihuangjianwei 2016-11-14 17:25 170
sinat_32547403 +关注
原创 414 粉丝 21 喜欢 0 码云  
他的最新文章 更多文章
120. Triangle 692. Top K Frequent Words TreeMap使用简介 658. Find K Closest Elements
在线课程

【免费】搜狗机器翻译技术分享
讲师:

深度学习在推荐领域的应用和实践
讲师:吴岸城
热门文章 OFDM系统的关键技术及分析
4013
python的三种取整方式
2903
python round函数用法
2722
Matplotlib -多组线用不同的线性、颜色、节点绘制
2688
Pandas 时间序列数据绘制X轴主要刻度和次要刻度
2595
0
  云计算 最新文章
NLP06-Gensim源码简析[字典]
pandas中使用三元表达式
Docker基础笔记
大数据工程师必备技能图谱
ServiceComb中的数据最终一致性方案
63. Unique Paths II
手把手教你建github技术博客by hexo
hadoop datanode结点不启动导致dfs控制台显
spark on yarn架构简介
mapreduce程序本地模式调试
上一篇文章      下一篇文章      查看所有文章
加:2017-10-30 04:04:25  更:2017-10-30 04:04:27 
VC(MFC) Delphi VB C++(C语言) C++ Builder 其它开发语言 云计算 Java开发 .Net开发 IOS开发 Android开发 PHP语言 JavaScript
ASP语言 HTML(CSS) HTML5 Apache MSSQL数据库 Oracle数据库 PowerBuilder Informatica 其它数据库 硬件及嵌入式开发 Linux开发资料
360图书馆 软件开发资料 文字转语音 购物精选 软件下载 美食菜谱 新闻资讯 电影视频 小游戏 Chinese Culture 股票 租车
生肖星座 三丰软件 视频 开发 短信 中国文化 网文精选 搜图网 美图 阅读网 多播 租车 短信 看图 日历 万年历 2018年7日历
2018-7-19 4:06:02
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  编程开发知识库