首页 > 其他分享 >6352.美丽子集的数目-337

6352.美丽子集的数目-337

时间:2023-03-19 16:00:14浏览次数:44  
标签:6352 nums int 337 dfs 子集 数组 path

美丽子集的数目

给你一个由正整数组成的数组 nums 和一个 正 整数 k 。

如果 nums 的子集中,任意两个整数的绝对差均不等于 k ,则认为该子数组是一个 美丽 子集。

返回数组 nums 中 非空 且 美丽 的子集数目。

nums 的子集定义为:可以经由 nums 删除某些元素(也可能不删除)得到的一个数组。只有在删除元素时选择的索引不同的情况下,两个子集才会被视作是不同的子集。

示例 1:

输入:nums = [2,4,6], k = 2
输出:4
解释:数组 nums 中的美丽子集有:[2], [4], [6], [2, 6] 。
可以证明数组 [2,4,6] 中只存在 4 个美丽子集。
示例 2:

输入:nums = [1], k = 1
输出:1
解释:数组 nums 中的美丽数组有:[1] 。
可以证明数组 [1] 中只存在 1 个美丽子集。

提示:

1 <= nums.length <= 20
1 <= nums[i], k <= 1000

解题思路1:dfs

由于数据量并不是十分大,可以使用dfs遍历所有的子集并判断是否符合题目给定的条件,在判断是否符合条件时我使用的是遍历的方法,进一步的优化可以使用哈希表或者是数组在O(1)的时间内判断是否存在nums[i] + k或者是nums[i] - k;至于dfs的写法,主要还是要画或者是imagine一棵递归树出来这样就可以对着递归树较好地写dfs了,时间复杂度为\(O(2^n)\).

code

class Solution {
public:
    //通过组合找到所有子集
    //判断子集是否美丽
    //提前终止dfs
    int ans = 0;
    void dfs(vector<int> & nums,vector<int> & path,int depth,int & k)
    {
        if(depth == nums.size()) return;
        
        for(int i = depth;i < nums.size();i ++)
        {
            bool flag = true;
            for(int j = 0;j < path.size();j ++)
            {
                if(nums[i] - path[j] == k) flag = false;
            }
            if(flag)
            {
                path.push_back(nums[i]);
                ans ++;
                dfs(nums,path,i + 1,k);
                path.pop_back();
            }
        }
        
    }
    int beautifulSubsets(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end());
        vector<int> path;
        dfs(nums,path,0,k);
        return ans;
    }
};

标签:6352,nums,int,337,dfs,子集,数组,path
From: https://www.cnblogs.com/huangxk23/p/17233406.html

相关文章

  • 子集卷积
    一想到我FWT的笔记还没写就来写这个东西,我就忍不住笑了子集卷积是一种定义在集合幂级数上的运算,虽然作者对集合幂级数一窍不通,但我们可以先从位运算的角度来理解一下子......
  • 算法随想Day41【动态规划】| LC198-打家劫舍、LC213-打家劫舍Ⅱ、LC337-打家劫舍Ⅲ
    LC198.打家劫舍自己写的版本,用pair<不取本次的最大收获,取本次的最大收获>进行记录introb(vector<int>&nums){intsize=nums.size();vector<pair<int,i......
  • 算法随想Day37【动态规划】| LC416-分割等和子集
    动态规划五部曲确定dp[i]的含义dp递推公式dp数组如何初始化确认dp数组遍历顺序打印dp数组,主要用于调试LC416.分割等和子集这道题是“背包问题”的应用,但其实不好......
  • 一种子集枚举方式的正确性说明
    一种常见的枚举子集的方法是for(intS=SET;S;S=(S-1)&SET)其中,变量\(\rm{S}\)是所枚举的子集考虑\(\rm{S}\)的二进制展开\[\mathrm{S}=(b_1b_2b_3\cdo......
  • 回溯算法解决排列—组合—子集问题
    回溯算法解决排列—组合—子集问题无论是排列、组合还是子集问题,就是让你从序列nums中以给定规则取若干元素,主要有以下几种变体:元素无重不可复选,即nums中的元素都......
  • 【LOJ 3378】点格棋(DP)(推论)
    点格棋题目链接:LOJ3378题目大意有一个(n+1)*(m+1)的格点组成的网格,然后两个人轮流操作,选两个相邻(距离为1)且没有连边的点对连一个竖直或者水平的线段。然后如果一个......
  • 力扣---78. 子集
     给你一个整数数组 nums,数组中的元素互不相同。返回该数组所有可能的子集(幂集)。解集不能包含重复的子集。你可以按任意顺序返回解集。 示例1:输入:nums=......
  • 【LeetCode回溯算法#07】子集问题I+II,巩固解题模板并详解回溯算法中的去重问题
    子集力扣题目链接给你一个整数数组nums,数组中的元素互不相同。返回该数组所有可能的子集(幂集)。解集不能包含重复的子集。你可以按任意顺序返回解集。示例1:输......
  • P3378 【模板】堆
    P3378【模板】堆【模板】堆题目描述给定一个数列,初始为空,请支持下面三种操作:给定一个整数x,请将x加入到数列中。输出数列中最小的数。删除数列中最小的数(如果有......
  • 78.子集
    子集给你一个整数数组 nums,数组中的元素互不相同。返回该数组所有可能的子集(幂集)。解集不能包含重复的子集。你可以按任意顺序返回解集。示例1:输入:nums=[1......