成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

leetcode368. Largest Divisible Subset

Honwhy / 3531人閱讀

摘要：題目要求假設(shè)有一組值唯一的正整數(shù)數(shù)組，找到元素最多的一個(gè)子數(shù)組，這個(gè)子數(shù)組中的任選兩個(gè)元素都可以構(gòu)成或。只要這個(gè)數(shù)字是前面數(shù)字的倍數(shù)，則構(gòu)成的數(shù)組的長(zhǎng)度則是之前數(shù)字構(gòu)成最長(zhǎng)子數(shù)組加一。

題目要求 
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:

Input: [1,2,3]
Output: [1,2] (of course, [1,3] will also be ok)
Example 2:

Input: [1,2,4,8]
Output: [1,2,4,8]

假設(shè)有一組值唯一的正整數(shù)數(shù)組，找到元素最多的一個(gè)子數(shù)組，這個(gè)子數(shù)組中的任選兩個(gè)元素都可以構(gòu)成Si % Sj = 0 或 Sj % Si = 0。

思路和代碼

這題最核心的思路在于，假如知道前面k個(gè)數(shù)字所能夠組成的滿足題意的最長(zhǎng)子數(shù)組，我們就可以知道第k+1個(gè)數(shù)字所能構(gòu)成的最長(zhǎng)子數(shù)組。只要這個(gè)數(shù)字是前面數(shù)字的倍數(shù)，則構(gòu)成的數(shù)組的長(zhǎng)度則是之前數(shù)字構(gòu)成最長(zhǎng)子數(shù)組加一。

這里我們使用了兩個(gè)臨時(shí)數(shù)組count和pre，分別用來(lái)記錄到第k個(gè)位置上的數(shù)字為止能夠構(gòu)成的最長(zhǎng)子數(shù)組，以及該子數(shù)組的前一個(gè)可以被整除的值下標(biāo)為多少。

    public List largestDivisibleSubset(int[] nums) {
        int[] count = new int[nums.length];
        int[] pre = new int[nums.length];
        Arrays.sort(nums);
        int maxIndex = -1;
        int max = 0;
        for(int i = 0 ; i=0 ; j--) {
                if(nums[i] % nums[j] == 0 && count[j] >= count[i]){
                    count[i] = count[j] + 1;
                    pre[i] = j;
                }
            }
            if(count[i] > max) {
                max = count[i];
                maxIndex = i;
            }
        }
        
        List result = new ArrayList();
        while(maxIndex != -1){
            result.add(nums[maxIndex]);
            maxIndex = pre[maxIndex];
        }
        return result;
    }


想要了解更多開(kāi)發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/72612.html

相關(guān)文章

  • Leetcode[368] Largest Divisible Subset

    摘要：讓數(shù)組從小到大排序。因?yàn)槿绻粋€(gè)數(shù)能被加到這個(gè)中的話，說(shuō)明這個(gè)數(shù)能被這個(gè)中的最大的數(shù)整除。同樣可以用一個(gè)數(shù)組來(lái)記錄之前搜索過(guò)的。，表示的是我們搜索的路徑是從到。初始化這個(gè)位置是頭結(jié)點(diǎn)。說(shuō)明是，并沒(méi)有是當(dāng)前最大的里的最大值。 LeetCode[368] Largest Divisible Subset Given a set of distinct positive integers,...

    springDevBird 評(píng)論0 收藏0

  • 368. Largest Divisible Subset

    368. Largest Divisible Subset 題目鏈接：https://leetcode.com/problems... dp記錄最大的長(zhǎng)度，加parent指針存路徑。dp方程是：dp[i] = max(dp[j]) + 1, if nums[i]%nums[j] == 0 public class Solution { public List largestDivisibl...

    mmy123456 評(píng)論0 收藏0

  • 368. Largest Divisible Subset

    摘要：題目解答參考的里的解法，核心思想從小到大，每一位數(shù)都能被比他大的數(shù)整除。對(duì)于從后往前看，找出每一個(gè)可以被它整除的數(shù)的數(shù)組，并更新它作為從這里開(kāi)始，往后最大的，記錄下最大數(shù)組開(kāi)始的地方，并把下一個(gè)數(shù)記在里找出最長(zhǎng)的這個(gè)數(shù)組中的每一個(gè)數(shù) 題目：Given a set of distinct positive integers, find the largest subset such th...

    source 評(píng)論0 收藏0

  • LeetCode[333] Largest BST Subtree

    摘要：復(fù)雜度思路考慮對(duì)于每一個(gè)節(jié)點(diǎn)來(lái)說(shuō)，能組成的的。那么并且所以我們需要兩個(gè)返回值，一個(gè)是這個(gè)是不是，另一個(gè)是當(dāng)前的能組成的最大的值。代碼這個(gè)能構(gòu)成一個(gè)這個(gè)不能構(gòu)成一個(gè) LeetCode[333] Largest BST Subtree Given a binary tree, find the largest subtree which is a Binary SearchTree (B...

    WrBug 評(píng)論0 收藏0

  • [Leetcode] Subset 子集

    摘要：深度優(yōu)先搜索復(fù)雜度時(shí)間空間遞歸棧空間思路這道題可以轉(zhuǎn)化為一個(gè)類似二叉樹的深度優(yōu)先搜索。另外需要先排序以滿足題目要求。新的集合要一個(gè)新的，防止修改引用。 Subset I Given a set of distinct integers, nums, return all possible subsets. Note: Elements in a subset must be in n...

    hzc 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<