leetcode 第 255 场算法比赛

零、背景

这次比赛最后一题是构造题，我没有构造出来。

看榜单全国只过了38人，全球只过了84人，你可以来看看你是否会做。

一、找出数组的最大公约数

题意：给一个数组，求最大值与最小值的最大公约数。

思路：按照题意，找出最大值和最小值，求最大公约数即可。

二、找出不同的二进制字符串

题意：给 n 个互不相同的二进制字符串数组，字符串长度都是 n。
求一个长度为 n 且没有出现在数组里的二进制字符串。

分析：长度为 n 的二进制数组有 2^n 个，题意给了 n 个，那就有 2^n-n个答案。
最简单的方法是从小到大找第一个不在数组的答案即可。

方法：数组排序，然后从 0 开始依次判断是否在二进制数组中即可。

复杂度：维护两个游标，复杂度O(n^2)

坑：题意说了给的数组的值互不相同，但是实际上存在相同值。

string findDifferentBinaryString(vector<string>& nums) {
    int n = nums.size();
    set<int> s;
    for(auto v: nums) {
        s.insert(ToNum(v));
    }

    int index = 0;
    while(1) {
        if(s.count(index) == 0) {
            return ToString(index, n);
        }
        index++;
    }
}

三、最小化目标值与所选元素的差

题意：给一个矩阵，每一行选择一个数字，可以得到一个和。
求和与目标绝对值的最小值。

思路：数据范围不大，直接枚举求出所有和即可。

四、从子集的和还原数组

题意：有一个长度为 n 的数组，现在有数组的所有子集和，求构造出一个满足子集和的数组。

分析：如果子集和没有负数，去除空集，每次都可以找到一个最小值。
找到一个最小值时，根据之前已找到的子集和，把包含当前最小值的子集全部删除，那下次的最小值还是答案。

vector<int>& FastZheng(int n){
    Del(0); // 删除空集

    vector<int> pre; // 保存的子集和
    pre.reserve(1<<n);
    pre.push_back(0);

    while(!m.empty()) {
        int one = GetMin();
        zheng--;
        for(auto v: pre) {
            Del(v + one);
            pre.push_back(v + one);
        }
        ans.push_back(one);
    }
    return ans;
}

如果子集和没有正整数，那可以使用与没有负整数一样的逻辑求出答案。

如果子集和同时存在正数和负数时，处理就比较麻烦了。

分析可以发现，最小的负数肯定是所有负数之和，最大的正数肯定是所有的正数之和。

根据上面的结论，还可以得到一个推论：最小的负数加上最大的正数，就是所有树之和。
不过这个推论好像没啥用。

看看最大正数与次大正数的关系，他们的差肯定是一个答案。
而且这个答案就是正数与负数的分界线，即最小的正数答案或最大的负数答案。

证明也很简单，使用反证法即可。

分析到这里之后，我就没思路了，不知道进一步去寻找其他答案。

看榜单，最后一题全国只过了38人，全球只过了84人，说明相当有难度了。
下午有点事，就没去研究题解了。
等后面有时间了，我再看看具体怎么构造这道题吧。

五、最后

这次比赛最后一次有点意思，你是怎么想这道题的？

加油，算法人。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code