1863. 找出所有子集的异或总和再求和

方法1：暴力

长度为 n 的集合的子集个数为 $2^n$ 个，可以看成一个 n 位的二进制数，0 表示不取，1 表示取

外层循环遍历这 $2^n$ 个子集，内层循环逐位检测是否为 1

tips：pow(2,i) 等价于 2<<i

class Solution {
public:
    int subsetXORSum(vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        for (int i = 0; i < (2 << i); i++) {
            int tmp = 0;
            for (int j = 0; j < n; j++) {
                if (i & (2 << j)) {
                    tmp ^= nums[j];
                }
            }
            sum += tmp;
        }
        return sum;
    }
};

方法2：递归

长度为 n 的集合的 n 个元素可以取或不取

class Solution {
public:
    int sum = 0;
    void dfs(int val, int index, vector<int>& nums) {
        int n = nums.size();
        if (n == index) {
            sum += val;
            return;
        }
        dfs(val ^ nums[index], index + 1, nums);
        dfs(val, index + 1, nums);
    }

    int subsetXORSum(vector<int>& nums) {
        dfs(0, 0, nums);
        return sum;
    }
};

300. 最长递增子序列

动态规划

设 dp[i] 表示前 i 位序列的以 nums[i] 结尾的最长递增子序列，可以写出递推表达式： $$ dp[i]=\max(dp[i],dp[j]+1)~~if(dp[j]<dp[i]) $$ 然后遍历所有的 dp[i] 最大的就为最长的递增子序列长度。

tips：( vector 数组初始化 )

  • vector<int> dp(n,1): 大小为 n，初始值为 1 的 dp 数组
  • 等价于 int* dp = new int[n]，其中 n 必须是 const 类型，需使用 for 循环赋初值

tips：( 求数组最大值 )

  • int max = *max_element(dp.begin(),dp.end());
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        const int n = nums.size();
        //int* dp = new int[n];
        vector<int> dp(n,1);
        for(int i = 0;i<n;i++){
            //dp[i]=1;
            for(int j = 0;j<i;j++){
                if(nums[j]<nums[i]){
                    dp[i] = max(dp[i],dp[j]+1);
                }
            }
        }
        int max = 0;
        for(int i = 0;i<n;i++){
            if(dp[i]>max){
                max = dp[i];
            }
        }
        // int max = *max_element(dp.begin(),dp.end());
        return max;
    }
};

368. 最大整除子集

动态规划+回溯

动态规划参考最长递增子序列。

设 dp[i] 为以 nums[i] 结尾的前 i 位的最大整除数组，则递推方程为： $$ dp[i]=\max(dp[i],dp[j]+1)~~if(dp[i]%dp[j]==0) $$ 回溯部分使用最大整除子集的大小 maxsize = max(dp) 和最大整除子集的最大值 maxval

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        // 对数组nums进行排序
        sort(nums.begin(), nums.end());
        // 动态规划
        int n = nums.size();
        vector<int> dp(n, 1);
        int maxsize = 0;
        int maxval = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0) {
                    dp[i] = max(dp[j] + 1, dp[i]);
                }
                if (dp[i] > maxsize) {
                    maxsize = dp[i];
                    maxval = nums[i];
                }
            }
        }
        // 根据maxsize和maxval回溯找到最大整除数组
        vector<int> res;
        if (n == 1) {
            return nums;
        }
        for (int i = n - 1; i >= 0; i--) {
            if (dp[i] == maxsize && maxval % nums[i] == 0) {
                res.push_back(nums[i]);
                maxsize--;
                maxval = nums[i];
            }
            if (maxsize < 0) {
                break;
            }
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

416. 分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

动态规划

设 dp[i][j] = true 表示前 i 个数存在和为 j 的子集，递推方程为：

dp[i][j] 为真，只需要 dp[i-1][j] 为真（不取 nums[i]）或 dp[i-1][j-nums[i]] 为真（取 nums[i]）

if(nums[i]<=j) dp[i][j]=dp[i-1][j]|dp[i-1][j-nums[j]]

otherwise dp[i][j]=dp[i-1][j]

设 target = sum/2，只需遍历 dp[i][target] ，有 true 就代表可以分割成等和子集。

tips（vector 创建二维数组）：

  • vector<vector<int>> dp(n,vector<int>(target+1,0)): 创建一个大小为 dp[n][target+1]，初始值为 0 的二维数组。
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        // 01背包问题
        int n = nums.size();
        //求和
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += nums[i];
        }
        //和为奇数直接返回false
        if (sum & 1) {
            return false;
        }
        int target = sum / 2;
        //动态规划
        vector<vector<int>> dp(n, vector<int>(target + 1, 0));
        dp[0][0] = true;
        for (int i = 1; i < n; i++) {
            dp[i][0] = true;
            for (int j = 0; j <= target; j++) {
                if (j >= nums[i]) {
                    dp[i][j] = dp[i - 1][j] | dp[i - 1][j - nums[i]];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
            if (dp[i][target] == true) {
                return true;
            }
        }
        return false;
    }
};

3396. 使数组元素互不相同所需的最少操作次数

哈希表 unordered_set

特点：

  • 基于哈希表实现，元素无序存储。
  • 插入、删除、查找操作平均时间复杂度为 O(1)（最坏情况 O(n)）。
  • 元素唯一（不允许重复）。

常用操作：

操作 代码 说明
插入元素 S.insert(value); 插入值，返回 pair<iterator, bool>（成功与否）
高效插入 S.emplace(args); 直接构造元素，避免拷贝
删除元素 S.erase(value); 按值删除，返回删除的元素数量（0或1）
清空集合 S.clear(); 移除所有元素
检查存在性 S.count(value); 返回 1（存在）或 0（不存在）
元素数量 S.size(); 返回当前元素个数
是否为空 S.empty(); 返回布尔值

本题思路为从后往前将元素放入哈希表，当检测到有重复元素时，即可得到需要移除的次数。

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        int n = nums.size();
        unordered_set<int> S;
        S.insert(nums[n - 1]);
        for (int i = n - 2; i >= 0; i--) {
            if (S.count(nums[i])) {
                return i / 3 + 1;
            }
            S.insert(nums[i]);
        }
        return 0;
    }
};

3375. 使数组的值全部为 K 的最少操作次数

哈希表的简单应用。

class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        int n = nums.size();
        unordered_set<int> S;
        for (int i = 0; i < n; i++) {
            if (nums[i] < k) {
                return -1;
            }
            if (nums[i] > k) {
                S.insert(nums[i]);
            }
        }
        return S.size();
    }
};

1922. 统计好数字的数目

我们称一个数字字符串是 好数字 当它满足（下标从 0 开始）偶数 下标处的数字为 偶数 且 奇数 下标处的数字为 质数 （2，3，5 或 7）。

  • 考点：模下快速幂
double QuickPow(double x, long long n) {
    double res = 1;
    if (n < 0) {
        n = -n;
        x = 1 / x;
    }
    while (n) {
        if (n & 1) {
            res = res * x;
        }
        x = x * x;
        n = n >> 1;
    }
    return res;
}

本题是快速幂的简单应用：

class Solution {
public:
    const long long mod = 1e9 + 7; // 10^9+1
    long long qpow(unsigned long long x, long long n) {
        long long res = 1;
        while (n) {
            if (n & 1) {
                res = res * x % mod;
            }
            x = x * x % mod;
            n >>= 1;
        }
        return res;
    }
    long long countGoodNumbers(unsigned long long n) {
        // 偶数 0 2 4 6 8 ，5个
        // 质数 4个
        long long even = n / 2;
        long long odd = (n + 1) / 2;

        return (qpow(4, even) * qpow(5, odd) % mod);
    }
};