头像

温柔大鸡翅




离线:3个月前


最近来访(46)
用户头像
lzy_4
用户头像
acwinghan2018
用户头像
April_0
用户头像
_accept
用户头像
Misaka_9982
用户头像
刷题早点财务自由然后看番打游戏度过余生
用户头像
牛蛙点点
用户头像
sonnen8
用户头像
dhs4654
用户头像
liufuhang
用户头像
盛夏白瓷梅子汤
用户头像
JinxinLi
用户头像
DaSY
用户头像
zombotany
用户头像
thunderclouds
用户头像
海阔天空_51
用户头像
matinal
用户头像
AKA-Yi
用户头像
test886
用户头像
上弦月

新鲜事 原文

Offer啦~ 包比较低但是不加班 挺满意啦 要开始搞框架了~啥都不会就会做题 不知道能不能抽出来时间刷题了T T



题目描述

Alice 和 Bob 轮流玩一个游戏,Alice 先手。

一堆石子里总共有n个石子,轮到某个玩家时,他可以 移出一个石子并得到这个石子的价值。Alice 和 Bob 对石子价值有 不一样的的评判标准

给你两个长度为 n的整数数组aliceValuesbobValuesaliceValues[i]bobValues[i]分别表示 Alice 和 Bob 认为第i个石子的价值。

所有石子都被取完后,得分较高的人为胜者。如果两个玩家得分相同,那么为平局。两位玩家都会采用 最优策略进行游戏。

请你推断游戏的结果,用如下的方式表示:

如果 Alice 赢,返回1
如果 Bob 赢,返回-1
如果游戏平局,返回0

样例

示例1
输入:aliceValues = [1,3], bobValues = [2,1]
输出:1
解释:
如果 Alice 拿石子 1 (下标从 0开始),那么 Alice 可以得到 3 分。
Bob 只能选择石子 0 ,得到 2 分。
Alice 获胜。
示例2
输入:aliceValues = [1,2], bobValues = [3,1]
输出:0
解释:
Alice 拿石子 0 , Bob 拿石子 1 ,他们得分都为 1 分。
打平。
示例3
输入:aliceValues = [2,4,3], bobValues = [1,6,7]
输出:-1
解释:
不管 Alice 怎么操作,Bob 都可以得到比 Alice 更高的得分。
比方说,Alice 拿石子 1 ,Bob 拿石子 2 , Alice 拿石子 0 ,Alice 会得到 6 分而 Bob 得分为 7 分。
Bob 会获胜。

算法1

(贪心) $O(n^2)$
  1. 对每颗石子的Alice和Bob的价值求和并从大到小排序
  2. Alice和Bob按顺序取出石头, 并分别累加每个玩家的分数
  3. 判断谁的分数更高。
  4. 这里给出贪心证明:
    1. 如果有两颗石子 $[a1, b1], [a2, b2]$, 分别考虑Alice拿1号石子和2号石子的情况
    2. 如果Alice拿1,那么分数差是 $a1 - b2 =T1$
    3. 如果Alice拿2,那么分数差是 $a2 - b1 = T2$
    4. $T1 - T2 = a1 - b2 - a2 + b1 = a1 + b1 - (a2 +b2)$
    5. 所以如果$a1 + b1 > a2 + b2$ 那么 $T1 > T2$
    6. 因此在仅考虑两颗石子的情况下, Alice应该选择T更大的方案, 即按照 $a_i + b_i$从大到小的顺序选取,这个策略对Bob也是有效的
    7. 通过循环不变式,可以证明对于 n > 2的情况,此贪心策略也是有效的.

时间复杂度

  1. 预处理$a_i + b_i$需要$O(n)$的时间
  2. 排序需要$O(nlogn)$的时间
  3. 模拟选择并累加分数需要 $O(n)$的时间
  4. 故总时间复杂度为$O(nlogn)$

参考文献

C++ 代码

class Solution {
public:
    struct Node{
        int a, b, sum;
    };
    int stoneGameVI(vector<int>& aliceValues, vector<int>& bobValues) {
        int n = aliceValues.size();
        vector<Node> alls(n);
        for(int i = 0; i < n; i++){
            alls[i] = {aliceValues[i], bobValues[i], aliceValues[i] + bobValues[i]};
        }
        sort(alls.begin(), alls.end(), [&](Node x, Node y){
            if(x.sum != y.sum)
                return x.sum > y.sum;
            return x.a > y.a;
        });

        int alice = 0, bob = 0;
        for(int i = 0; i < n; i+=2){
            alice += alls[i].a;
            if(i + 1 < n) bob += alls[i + 1].b;
        }
        if (alice > bob) return 1;
        else if (alice == bob) return 0;
        return -1;
    }
};



题目描述

给你一个 非递减有序整数数组nums

请你建立并返回一个整数数组result,它跟nums长度相同,且result[i]等于nums[i]与数组中所有其他元素差的绝对值之和。

换句话说,result[i]等于sum(|nums[i]-nums[j]|) ,其中0 <= j < nums.lengthj != i(下标从 0 开始)。

样例

示例1
输入:nums = [2,3,5]
输出:[4,3,5]
解释:假设数组下标从 0 开始,那么
result[0] = |2-2| + |2-3| + |2-5| = 0 + 1 + 3 = 4,
result[1] = |3-2| + |3-3| + |3-5| = 1 + 0 + 2 = 3,
result[2] = |5-2| + |5-3| + |5-5| = 3 + 2 + 0 = 5。
示例2
输入:nums = [1,4,6,8,10]
输出:[24,15,13,15,21]

提示

  • 2 <= nums.length <= 10^5
  • 1 <= nums[i] <= nums[i + 1] <= 10^4

算法1

(数学 前缀和) $O(n)$
  1. 这题一个很关键的点在于数组是非递减
  2. 对于nums[i]数, 它的答案应该是 $\sum_{k = 0}^{i - 1}(nums[i] - nums[k]) + \sum_{k = i +1}^{n - 1}(nums[k] - nums[i]) $
  3. 上述式子可以等价于 $nums[i] * i -(\sum_{k = 0}^{i - 1}nums[k]) + (\sum_{k = i +1}^{n - 1}nums[k]) - (n - i + 1)nums[i] $
  4. 我们预处理数组的前缀和,上述式子可以在$O(1)$的时间算出。

时间复杂度

  1. 预处理前缀和需要$O(n)$的时间
  2. 计算答案需要枚举$n$次,每次需要$O(1)$的时间算出答案ans[i]
  3. 故总时间复杂度为$O(n)$。

C++ 代码

class Solution {
public:
    vector<int> getSumAbsoluteDifferences(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans;
        vector<int> sums(n + 2);
        for(int i = 1; i <= n; i++){
            sums[i] += sums[i - 1] + nums[i - 1];
        }
        for(int i = 1; i <= n; i ++){
            int right = sums[n] - sums[i] - (n - i) * nums[i - 1];
            int left = nums[i - 1] * i - sums[i] ;
            ans.push_back(left + right);
        }
        return ans;
    }
};




题目描述

给你一个由不同字符组成的字符串 allowed 和一个字符串数组 words 。如果一个字符串的每一个字符都在 allowed 中,就称这个字符串是 一致 字符串。

请你返回 words 数组中 一致 字符串的数目。

样例

示例1
输入:allowed = "ab", words = ["ad","bd","aaab","baa","badab"]
输出:2
解释:字符串 "aaab" 和 "baa" 都是一致字符串,因为它们只包含字符 'a' 和 'b' 。
示例2
输入:allowed = "abc", words = ["a","b","c","ab","ac","bc","abc"]
输出:7
解释:所有字符串都是一致的。
示例3
输入:allowed = "cad", words = ["cc","acd","b","ba","bac","bad","ac","d"]
输出:4
解释:字符串 "cc","acd","ac" 和 "d" 是一致字符串。

提示

  • 1 <= words.length <= 10^4
  • 1 <= allowed.length <= 26
  • 1 <= words[i].length <= 10
  • allowed 中的字符 互不相同
  • words[i]allowed 只包含小写英文字母。

算法1

(哈希表 模拟) $O(x + nm)$ , $x = allowed的长度, n = words的大小, m = words中字符串的平均长度$
  1. 预处理allowed中的所有字符。
  2. 枚举words中的所有字符串, 如果字符串中出现了allowed中没出现过的单词,则它不是一个合法的一致字符串
  3. 统计一致字符串的数量即可

时间复杂度

  1. 预处理allowed的字符需要$O(x)$的时间,其中$x = len(allowed)$
  2. 枚举words中的所有字符串需要n次,每次需要遍历整个words[i],因此枚举过程需要$O(nm)$的时间
  3. 故总时间复杂度为 $O(x + nm)$

C++ 代码

class Solution {
public:
    int countConsistentStrings(string allowed, vector<string>& words) {
        int hash[26] = {0};
        for(char ch : allowed) hash[ch - 'a'] ++;
        int n = words.size();
        int ans = 0;
        for(int i = 0; i < n; i++){
            int m = words[i].size();
            int isOk = 1;
            for(int j = 0; j < m; j++){
                if(hash[words[i][j] -'a'] == 0){
                    isOk = 0;
                    break;
                }
            }
            if(isOk) ans++;
        }
        return ans;
    }
};



题目描述

给你一棵以root为根的二叉树,请你返回 任意 二叉搜索子树的最大键值和。

二叉搜索树的定义如下:

任意节点的左子树中的键值都小于此节点的键值。
任意节点的右子树中的键值都 大于此节点的键值。
任意节点的左子树和右子树都是二叉搜索树。

样例

示例1

sample_1_1709.png

输入:root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]
输出:20
解释:键值为 3 的子树是和最大的二叉搜索树。
示例2

sample_2_1709.png

输入:root = [4,3,null,1,2]
输出:2
解释:键值为 2 的单节点子树是和最大的二叉搜索树。
示例3
输入:root = [-4,-2,-5]
输出:0
解释:所有节点键值都为负数,和最大的二叉搜索树为空。
示例4
输入:root = [2,1,3]
输出:6
示例5
输入:root = [5,4,8,3,null,6,3]
输出:7

提示

  • 每棵树最多有 40000 个节点。
  • 每个节点的键值在 [-4 * 10^4 , 4 * 10^4] 之间

算法1

(递归, 树形DP) $O(n)$
  1. 定义结构体 ST表示某个以某个节点为根的子树状态,分别为:当前子树的键值和v, 当前子树的最小节点的值minV, 最大节点的值maxV, 以及是否是一个BST的标记isBST
  2. 递归到叶子节点后返回父节点。返回过程中判断当前节点和左右子树能否形成一棵BST, 并将状态记录在哈希表中。
  3. 向上返回过程中更新答案的最大值。

时间复杂度

  1. 需要遍历所有的节点,故总时间复杂度为$O(n)$

空间复杂度

  1. 递归深度 $O(h)$
  2. 哈希表 $O(n)$
  3. 总空间复杂度为 $O(n)$
    每个节点其实只用到了左右孩子的子树信息,因此哈希表并不是必要的,令dfs函数直接返回一个ST结构体即可,可以省去哈希表的空间和查询时间将空间降为$O(h)$,这里交给读者自行实现。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    struct ST{
        int v, minV, maxV;
        bool isBST;
    };
    unordered_map<TreeNode*, ST> hash;
    int ans = 0;
    void dfs(TreeNode* root){
        if(!root) return;
        dfs(root -> left);
        dfs(root -> right); 
        if(hash[root->left].isBST == false) hash[root] = {-1, -1, -1, false};
        else if (hash[root->right].isBST == false) hash[root] = {-1, -1, -1, false};
        else{
            ST& left = hash[root -> left];
            ST& right = hash[root -> right]; 
            int val = root -> val;
            if(val > left.maxV && val < right.minV){
                int v = left.v+ right.v + val;
                hash[root] = {v, 
                            root -> left ? left.minV : root->val,
                            root-> right ? right.maxV : root->val,
                            true};
                ans = max(ans, v);
            }else hash[root] = {-1, -1, -1, false};
        }
    }

    int maxSumBST(TreeNode* root) {
        hash[nullptr] = {0, (int)1e9, (int)-1e9, true};
        dfs(root);
        return ans;
    }
};



题目描述

给定一个数字字符串 S,比如 S = "123456579",我们可以将它分成斐波那契式的序列 [123, 456, 579]

形式上,斐波那契式序列是一个非负整数列表 F,且满足:

0 <= F[i] <= 2^31 - 1,(也就是说,每个整数都符合 32 位有符号整数类型);
F.length >= 3
对于所有的0 <= i < F.length - 2,都有 F[i] + F[i+1] = F[i+2] 成立。
另外,请注意,将字符串拆分成小块时,每个块的数字一定不要以零开头,除非这个块是数字 0 本身。

返回从 S 拆分出来的任意一组斐波那契式的序列块,如果不能拆分则返回 []

样例

示例1
输入:"123456579"
输出:[123,456,579]
示例2
输入: "11235813"
输出: [1,1,2,3,5,8,13]
示例3
输入: "112358130"
输出: []
解释: 这项任务无法完成。
示例4
输入: "1101111"
输出: [110, 1, 111]
解释: 输出 [11,0,11,11] 也同样被接受。
提示:
  • 1 <= S.length <= 200
  • 字符串 S 中只含有数字。

算法1

(递归搜索) $O(k^2n)$ 其中$k$是一个系数,值在 $min(31, log_{10}n)$
  1. 定义递归函数,如果可以找到答案返回true
  2. 定义答案数组ans。 当ans的数字数量小于2时,我们先尝试找序列的前两个数。
  3. ans的数字数量大于等于2时,尝试枚举后面的数cur。当字符串凑成的数等于ans中的最后两个数的和sum的时候,继续递归,否则如果小于sum则继续补位,如果大于和则返回false
  4. 如果可以搜完整个字符串且ans中数量个数超过2时,说明有解,返回true
  5. 任意一次搜索分支返回true即可全部返回终止搜索。

时间复杂度

  1. 每层递归需要$O(n)$的时间遍历字符串
  2. 仅前两个数字需要用$k = min(31, log_{10}n)$的时间枚举(数字范围不超过INT_MAX)
  3. 故总时间复杂度为$O(k^2n)$

C++ 代码

class Solution {
public:
    vector<int> ans;
    int n;
    vector<int> splitIntoFibonacci(string S) {
        n = S.size();
        if(S.size() < 3) return ans;
        dfs(S, 0);
        return ans; 
    }

    bool dfs(string& S, int idx){
        if(idx == S.size()){
            return ans.size() > 2;
        }
        long long cur = 0;
        for(int i = idx; i < n; i++){
            if(i > idx && cur == 0) return false;;
            cur = cur * 10 + S[i] - '0';
            if(cur > INT_MAX) return false;
            if(ans.size() < 2){
                ans.push_back(cur);
                if (dfs(S, i + 1)) return true;
                ans.pop_back();
            }else {
                int sz = ans.size();
                int sum = ans[sz - 1] + 0LL + ans[sz - 2];
                if(sum > cur) continue;
                else if (sum == cur){
                    ans.push_back(cur);
                    if(dfs(S, i + 1)) return true;
                    ans.pop_back();
                }else{
                    return false;
                }
            }
        }
        return false;
    }
};



题目描述

我们给出了 N 种不同类型的贴纸。每个贴纸上都有一个小写的英文单词。

你希望从自己的贴纸集合中裁剪单个字母并重新排列它们,从而拼写出给定的目标字符串 target

如果你愿意的话,你可以不止一次地使用每一张贴纸,而且每一张贴纸的数量都是无限的。

拼出目标target 所需的最小贴纸数量是多少?如果任务不可能,则返回 -1

样例

示例1
输入:["with", "example", "science"], "thehat"
输出:3
解释:我们可以使用 2 个 "with" 贴纸,和 1 个 "example" 贴纸。
把贴纸上的字母剪下来并重新排列后,就可以形成目标 “thehat“ 了。
此外,这是形成目标字符串所需的最小贴纸数量。
示例2
输入:["notice", "possible"], "basicbasic"
输出:-1
解释:我们不能通过剪切给定贴纸的字母来形成目标“basicbasic”。

提示

  • stickers 长度范围是[1, 50]
  • stickers 由小写英文单词组成(不带撇号)。
  • target 的长度在[1, 15]范围内,由小写字母组成。
  • 在所有的测试案例中,所有的单词都是从 1000 个最常见的美国英语单词中随机选取的,目标是两个随机单词的串联。
  • 时间限制可能比平时更具挑战性。预计 50 个贴纸的测试案例平均可在35ms内解决。

算法1

(记忆化搜索, 字符串哈希) $O(M + n * N * 2^n)$ , 其中 n = stickers.size(), N = target.size(), M = stickers中单词总长度
  1. 定义哈希表hash<ULL, int>表示从stickers中凑出target及其子串,需要的最少单词数量. key是这个字符串的哈希值. 当然读者定义成 hash<string, int> 也是完全可以过这道题的。
  2. 定义数组哈希表mp[50][26]并预处理处stickers中每个单词中的字符数量.
  3. 如此, 题目就简化成了一个获取 hash[target]的记忆化搜索问题,搜索过程中找到target能被stickers中单词消掉生成的所有子序列s. 这里可以用到一个剪枝技巧,就是我们总是尝试消掉s的第一个字符。因为我们不消掉第一个字符也会在后续的搜索过程中搜到一样的方案,而每次至少只消第一个字符一定不会错过最优答案。
  4. 尝试所有“每次可以消掉至少s一个字符”的拼接方式,直到s == ""时结束。
  5. 题解中用到了字符串哈希,降低了一次字符串在哈希表中查找时要遍历两次字符串的操作。

时间复杂度

  1. 预处理mp数组需要$O(M)$的时间, $M = stickers中单词总长度$
  2. 递归的过程中, 每一层递归要枚举所有stickers中的单词, 共n
    1. 每一次枚举单词需要生成一个平均长度为N的子序列s,
    2. 每一层在哈希表中查找字符串是否枚举过需要$O(N)$的时间生成哈希值,并需要$O(1)$的时间查找,
    3. s的数量可以看做target二进制压缩后的子集数量, 共有 $2^n$个
    4. 12可以合并成 $O(2N) = O(N)$
  3. 故总时间复杂度为$O(M + n * N * 2^n)$

C++ 代码

int mp[50][26];
#define INF 0x3f3f3f3f
typedef unsigned long long ULL;
class Solution {
public:
    const int MOD1 = 13331;
    const int MOD2 = 131;
    ULL getHash(string & s){
        int n = s.size();
        ULL p1 = 0, p2 = 0;
        for(int i = 0; i < n; i++){
            p1 = p1 * MOD1 + s[i];
            p2 = p2 * MOD2 + s[i];
        }
        return p1 * p2;
    }

    unordered_map<ULL, int> hash;
    int n;
    int minStickers(vector<string>& stickers, string target) {
        memset(mp, 0, sizeof mp);
        n = stickers.size();
        for(int i = 0; i < n; i++){
            int m = stickers[i].size();
            for(int j = 0; j < m; j++){
                mp[i][stickers[i][j] - 'a']++;
            }
        }
        int ans = dfs(stickers, target);
        return ans == INF ? - 1 : ans;

    }

    int dfs(vector<string>& stickers, string& target){
        if(target == "") return 0;
        ULL hashCode = getHash(target);
        if(hash.count(hashCode)) return hash[hashCode];
        int m = target.size();
        int ans = INF;
        int firstCh = target[0] - 'a';
        int tmap[26] = {0};
        for(char ch : target) tmap[ch - 'a'] ++;
        for(int i = 0; i < n; i++){
            if(!mp[i][firstCh]) continue;
            string ne = "";
            for(int j = 0; j < 26; j ++){
                if(tmap[j] > 0){
                    for(int k = 0; k < tmap[j] - mp[i][j]; k++){
                        ne += (char)('a'+j);
                    }
                }
            }
            ans = min(ans, dfs(stickers, ne) + 1);
        }
        hash[hashCode] = ans;
        return hash[hashCode];
    }
};

算法2 等醒了补。先睡了

(状态压缩动态规划) $O(M + n * N * 2^n)$
  1. 将算法1的记忆化搜索改写成状态压缩动态规划是很自然的。
  2. 定义dp[i]表示凑成了target中$2_i$个字符的最小答案.

时间复杂度

C++ 代码




活动打卡代码 AcWing 2171. EK求最大流

#include <iostream>
#include <algorithm>
#include <cstring>

#define INF 0x3f3f3f3f
using namespace std;

const int N = 1010, M = 20010;
int h[N], e[M], ne[M], f[M], idx;

void add(int a, int b, int c){
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx++;
}

int n, m, S, T;

int D[N], st[N], pre[N], q[N];


bool bfs(){
    memset(st, 0, sizeof st);
    D[S] = INF;
    int hh = 0, tt = -1;
    q[++tt] = S;
    st[S] = 1;
    while(hh <= tt){
        int t = q[hh++];
        for(int i = h[t]; ~i; i = ne[i]){
            int j = e[i];
            if(st[j] || f[i] == 0) continue;
            D[j] = min(f[i], D[t]);
            st[j] = true;
            pre[j] = i;
            if(j == T) return true;
            q[++tt] = j;
        }
    }

    return false;

}

int EK(){
    int ans = 0;
    while(bfs()){
        ans += D[T];
        for (int i = T; i != S; i = e[pre[i] ^ 1])
            f[pre[i]] -= D[T], f[pre[i] ^ 1] += D[T];

    }
    return ans;
}


int main(){
    memset(h, -1, sizeof h);
    cin >> n >> m >> S >> T;
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    cout << EK() << endl;

    return 0;
}



题目描述

给你一个整数数组nums 和一个整数k。你需要将这个数组划分到k个相同大小的子集中,使得同一个子集里面没有两个相同的元素。

一个子集的 不兼容性 是该子集里面最大值和最小值的差。

请你返回将数组分成 k个子集后,各子集 不兼容性最小值,如果无法分成分成 k个子集,返回-1

子集的定义是数组中一些数字的集合,对数字顺序没有要求。

样例

示例1
输入:nums = [1,2,1,4], k = 2
输出:4
解释:最优的分配是 [1,2] 和 [1,4] 。
不兼容性和为 (2-1) + (4-1) = 4 。
注意到 [1,1] 和 [2,4] 可以得到更小的和,但是第一个集合有 2 个相同的元素,所以不可行。
示例2
输入:nums = [6,3,8,1,3,1,2,2], k = 4
输出:6
解释:最优的子集分配为 [1,2],[2,3],[6,8] 和 [1,3] 。
不兼容性和为 (2-1) + (3-2) + (8-6) + (3-1) = 6 。
示例3
输入:nums = [5,3,3,6,3,3], k = 3
输出:-1
解释:没办法将这些数字分配到 3 个子集且满足每个子集里没有相同数字。

提示

  • 1 <= k <= nums.length <= 16
  • nums.length 能被 k 整除
  • 1 <= nums[i] <= nums.length

算法1

(状态压缩 + 剪枝 动态规划) $O(n2^n)$
  1. 定义所有合法的单个最小集合st以及总集合的划分方式f,状态数量分别为tt2f[i]表示用了用了二进制状态下i的位为1的数.
  2. 利用二进制枚举子集,统计出stf
    1. 每一个集合的元素个数应该为cnt = n / k
    2. 合法的单个集合 __builtin_popcount(i) == cnt
    3. 合法的整体总集合 __builtin_popcount(i) %cnt == 0
    4. 合法的单个集合中,不可以有相同数字。
  3. 因此对于单个集合的合法性我封装成了一个函数check,在计算合法的同时返回集合的不兼容性,如果返回-1表示集合不合法
  4. 初始化f[i]INF, 但对于 i==st[k]的状态(最小单个集合),初始化成st[k]的不兼容性
  5. 枚举所有f的状态state, 再枚举所有可行的单个集合ss, ss属于st, 如果ssstate的一个子集, 那么尝试更新f[state]的值。
  6. 由于state的状态是从小到大的,那么当ss >= state时就可以停止枚举子集. 判断一个二进制状态是否是另一个数的二进制状态可以通过 state | ss == state来判断,因为当statess有一位不同时,等式将不成立
  7. 最终答案即为 f[(1 << n) - 1]

时间复杂度

  1. 为了方便统计,一些非常小的复杂度,例如check函数, 对nums排序不做赘述
  2. 枚举所有单个最小集合和总集合需要枚举状态 1 << n次,复杂度为$O(2^n)$
  3. 每一个状态的check需要的时间为$(O(n))$ (n <= 16, 固定计算16次)
  4. 合法的最小子集数量是一个组合数,值为$T1 = C_{n}^{n/k} * C_{n - n / k}^{n/k}… $
  5. 合法的大集合数量也是一个组合数,值为$T2 = C_{n}^{n/k} + C_{n}^{n/k * 2} + C_{n}^{n/k * 3} + … $
  6. 总时间复杂度为 $T1 * T2 + n2^n$.
  7. 公式化简太麻烦了。。但是由于子集数量有限,一般考虑$O(T1 * T2) <= 2^n$,故总时间复杂度为$O(n2^n)$

C++ 代码

pair<int, int> st[1 << 16]; // first 表示状态, second表示不兼容性
int alls[1 << 16];
int f[1 << 16];
#define INF 0x3f3f3f3f
class Solution {
public:
    int check(vector<int> & nums, int x){
        int p[16] = {}, idx = 0;
        for(int i = 0; i < 16; i++){
            if(x >> i & 1) p[idx++] = i;
        }
        for(int i = 0; i < idx - 1; i++){
            if(nums[p[i]] == nums[p[i + 1]]) return -1;
        }
        return nums[p[idx - 1]] - nums[p[0]];
    }

    int minimumIncompatibility(vector<int>& nums, int k) {
        memset(f, 0x3f, sizeof f);
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int cnt = n / k, t = 0, t2 = 0;
        for(int i = 1; i < 1 << n; i++){
            int cnt1 = __builtin_popcount(i);
            if(cnt1 % cnt == 0) alls[t2++] = i;
            if(cnt1 == cnt){
                int diff = check(nums, i);
                if(diff != -1) {
                    st[t++] = {i, diff};
                    f[i] = diff;
                }
            }
        }
        for(int i = 0; i < t2; i++){
            int state = alls[i];
            for(int j = 0; j < t && st[j].first < state; j++){
                int ss = st[j].first;
                if((state | ss) == state){
                    f[state] = min(f[state], f[state - ss] + st[j].second);
                }

            }
        }
        int ans = f[(1 << n) - 1];
        return ans == INF ? -1 : ans;
    }
};




题目描述

给你一个整数 n ,请你将 1n 的二进制表示连接起来,并返回连接结果对应的 十进制 数字对 10^9 + 7 取余的结果。

样例

示例1
输入:n = 1
输出:1
解释:二进制的 "1" 对应着十进制的 1 。
示例2
输入:n = 3
输出:27
解释:二进制下,1,2 和 3 分别对应 "1" ,"10" 和 "11" 。
将它们依次连接,我们得到 "11011" ,对应着十进制的 27 。
示例2
输入:n = 12
输出:505379714
解释:连接结果为 "1101110010111011110001001101010111100" 。
对应的十进制数字为 118505380540 。
对 10^9 + 7 取余后,结果为 505379714 。

提示

1 <= n <= 10^5


算法1

(位运算) $O(nlog(n))$
  1. f(n)表示连接1-n的答案
  2. f(n + 1)则等于 $f(n)$ 连接 $(n + 1)$的二进制表示后模1e9+7
  3. 连接可以表示为 $(f(n) << len(n_2)) + (n + 1)_2$
  4. 因此枚举1-n,递推求解答案即可。

时间复杂度

  1. 枚举所有数字需要$O(n)$的时间
  2. 每次需要$O(log(n))$的时间计算出$len(x_2)$ (其实最多32次计算)
  3. 故总时间复杂度为$O(nlog(n))$

C++ 代码

class Solution {
public:
    int concatenatedBinary(int n) {
        const int mod = 1e9 + 7;
        long long ans = 0;
        for(int i = 1; i <= n; i++){
            int len = 0;
            int t = i;
            while(t) {
                len++;
                t >>= 1;
            }
            ans = (ans << len) + i;
            ans %= mod;
        }
        return ans;
    }
};