最大整除子集 -- LeetCode -- 4.23

368.最大整除子集

 

  给你一个由 无重复 正整数组成的集合 nums ,请你找出并返回其中最大的整除子集 answer ,子集中每一元素对 (answer[i], answer[j]) 都应当满足:
  answer[i] % answer[j] == 0 ,或     answer[j] % answer[i] == 0;
  如果存在多个有效解子集,返回其中任何一个均可。

示例 1:

  输入:nums = [1,2,3]
  输出:[1,2]
  解释:[1,3] 也会被视为正确答案。
示例 2:

  输入:nums = [1,2,4,8]
  输出:[1,2,4,8]

提示:

  1 <= nums.length <= 1000
  1 <= nums[i] <= 2 * 109
  nums 中的所有整数 互不相同

先找出那个集合,找的方法和找最长上升子序列方法一样,DP问题而且状态转移方程 也与其一样;找到最大max = dp[i] 的值,这也是最后returnsize的值,也是最后答案res数组的长度;

最后解决如何把集合放进res数组,可以是倒着往前搜,找到符合条件的放进数组里;

nums 2 3 5 25 30 50
dp 1 1 1 2 2 3

具体符合条件的就是先找到max,放入数组,然后max - 1,再一次次找 = max的,而且要找到的的数和前一个是整除关系;就比如说  50  是数组最后一个数,而 30 就不能是倒数第二个数!

int cmp(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}
int* largestDivisibleSubset(int* nums, int numsSize, int* returnSize){
    qsort(nums, numsSize, sizeof(nums[0]), cmp); //排序
    int i, j, dp[1005], max = -999999;
    int t, x;//x 记录nums[i]的数值;用于判断是否整除for(i = 0; i < numsSize; i++){
        dp[i] = 1;
        for(j = i - 1; j >= 0; j--){
            if(nums[i] % nums[j] == 0){
                 dp[i] = fmax(dp[i], dp[j] + 1);
            }
        }
        if(max < dp[i]){
            max = dp[i];
            x = nums[i];
        }
    }
    int *res = malloc(sizeof(int) * max);
    t = max;
    if(max == 1){//小优化;
        res[0] = nums[0];
        *returnSize = max;
        return res;
    }
    for(i = numsSize - 1; i >= 0; i--){
        if(dp[i] == t && x % nums[i] == 0){
            res[--t] = nums[i];
            x = nums[i];
        }
    }
    *returnSize = max;
    return res;
}

 



 

上一篇:UVA11547 Automatic Answer 题解


下一篇:jQuery Mobile笔记