LeetCode 368. Largest Divisible Subset分析代码

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:

image.png Example 2:

image.png

分析

这里需要发现一个规律,就是如果result中已经有【1,2】,那么对于要新加进来的数,只要它能整除掉result中最大的数就可以,因为如果先把result按大小排序,那么显然result中最大的数可以整除其他比他小的数,那么新加来的数都可以整除最大的数,自然也可以其他数。所以我们先将数组排序。然后用一个数组记录添加的元素,也就是类似记录路径,这种方法记录路径的方法很常用,类似于并查集中的应用。具体看代码

代码

public class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        int n = nums.length;
        int[] count = new int[n];
        int[] pre = new int[n];
        Arrays.sort(nums);
        int max = 0, index = -1;
        for (int i = 0; i < n; i++) {
            count[i] = 1;
            pre[i] = -1;
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] % nums[j] == 0) {
                    if (1 + count[j] > count[i]) {
                        count[i] = count[j] + 1;
                        pre[i] = j;
                    }
                }
            }
            if (count[i] > max) {
                max = count[i];
                index = i;
            }
        }
        List<Integer> res = new ArrayList<>();
        while (index != -1) {
            res.add(nums[index]);
            index = pre[index];
        }
        return res;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏aCloudDeveloper

算法导论第六章堆排序(一)

现在来看, 堆的含义大概有两种,一种是数据结构,一种是在一些语言中所定义的“垃圾回收机制”,如Java,在书本上的开篇强调了这两者,并强调若非特殊说明,皆把堆看...

267100
来自专栏架构说

Leetcode 200 Number of Islands 岛的个数

1. 遍历每一个结点,如果某结点是陆地且未访问过,岛数目加1,修改未访问标志位,然后把该点放入队列中,以备扩展岛屿使用,进入2 2. 队列不为空时,取出点,然...

34430
来自专栏Lambda

Java 常见内存溢出异常与代码实现

Java 堆 OutOfMemoryError Java 堆是用来存储对象实例的, 因此如果我们不断地创建对象, 并且保证 GC Root 和创建的对象之间...

22180
来自专栏Android机动车

数据结构学习笔记——队列

线性表有顺序存储和链式存储,栈是线性表,所以有这两种存储方式。同样,队列作为一种特殊的线性表,也同样存在这两种存储方式。

6210
来自专栏WindCoder

Java漫谈-容器

除并发应用,Queue在Java SE5中仅有两个实现 LinkedList和PriorityQueue,差异在于排序行为,而不是性能。

9510
来自专栏C语言及其他语言

【每日一题】问题 1157: 【亲和数】

古希腊数学家毕达哥拉斯在自然数研究中发现,220的所有真约数(即不是自身的约数)之和为: 1+2+4+5+10+11+20+22+44+55+110=284...

8520
来自专栏ACM算法日常

Bessie的好牌(队列)- POJ 3629

Bessie is playing a card game with her N-1 (2 ≤ N ≤ 100) cow friends using a dec...

15630
来自专栏拭心的安卓进阶之路

Java 集合源码解析(2):ListIterator

今天心情和股票一样红,还是学学 ListIterator 吧! ListIterator ? 根据官方文档介绍, ListIterator 有以下功能: 允许...

23890
来自专栏小灰灰

Java容器篇小结之List自问自答

I. List篇 0. 什么是List 看到这个有点懵逼,一时还真不知道怎么解释,能让完全没有接触过的人都能听懂 列表,什么是列表呢? 好比你到了一个村里,看...

23280
来自专栏青玉伏案

算法与数据结构(一) 线性表的顺序存储与链式存储(Swift版)

温故而知新,在接下来的几篇博客中,将会系统的对数据结构的相关内容进行回顾并总结。数据结构乃编程的基础呢,还是要不时拿出来翻一翻回顾一下。当然数据结构相关博客中我...

22970

扫码关注云+社区

领取腾讯云代金券