讨论/题目交流/🏆 第 160 场力扣周赛/
🏆 第 160 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 找出给定方程的正整数解
5 分 - 循环码排列
5 分 - 串联字符串的最大长度
7 分 - 铺瓷砖

展开讨论

第一题

看数据范围,xxyy 都是 10001000 以内,就算是遍历遍所有的 (x,y)(x,y),也就 10610^6 个数对,
当然假定了 CustomFunction.f 这个函数是 O(1)O(1) 复杂度,如果这个函数复杂度高一点,就得用二分了。

class Solution {
public:
    vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {
        vector<vector<int>> ret;
        for (int x = 1;x <= 1000;x++) {
            for (int y = 1;y <= 1000;y++) {
                if (customfunction.f(x, y) == z) {
                    ret.push_back({x, y});
                }
            }
        }
        return ret;
    }
}

第二题

如果 startstart00 开始,我们将怎么构造循环码?

假设 AA 为长度为 2(n1)2^{(n-1)} 的循环码,那么 AA 里面所有的数肯定都比 2(n1)2^{(n-1)} 小,那么:
AA 的所有数加上 2(n1)2^{(n-1)},形成数组 BB,这数组 BB 长度为 2(n1)2^{(n-1)},而且相邻数组也满足相邻相差 11 个 bit 的条件。

我们可以将 BB 倒过来,放在 AA 后面,AA 数组的最后一个数正好跟 BB 数组倒过来后的第一个数相差 11 个 bit,而 AA 数组的第一个数正好跟 BB 数组倒过来后的最后一个数相差 11 个 bit。

也就是 A+[B]A+[~B] 为长度为 2n2^n 的循环码。

题目给定循环码的开头,其实有很多种方法构造,比如说:

  1. 按照刚才所说,构造一个 startstart00 的循环码,然后再把指定开头的那个数循环挪到开头。
  2. AA 数组加上 2(n1)2^{(n-1)} 改成异或上 2(n1)2^{(n-1)},由于根据构造方法,AA 数组的第 n1n-1 位肯定要么全为 00,要么全为 11,循环码的条件依旧成立。
class Solution {
public:
    vector<int> circularPermutation(int n, int start) {
        vector<int> ret;
        ret.push_back(start);
        for (int i = 0;i < n;i++) {
            int m = ret.size();
            for (int j = 0;j < m;j++) {
                ret.push_back(ret[m - j - 1] ^ (1 << i));
            }
        }
        return ret;
    }
};

第三题

arr 的长度才 1616... 枚举所有的子集合也就 2162^16 种情况。
针对每种情况:

  1. 判断是否满足每一个字符都只出现过一次
  2. 计算字符总长度,以便求出满足条件的最大长度
class Solution {
public:
    //将字符串s压成数位,每一位代表一个字母出现与否
    int change(string s) {
        int ret = 0;
        for (int i = 0;i < s.size();i++) {
            if (ret & (1 << (s[i] - 'a'))) {
                return -1;
            } else {
                ret += 1 << (s[i] - 'a');
            }
        }
        return ret;
    }
    //判断某一种情况,是否满足每个字符值出现一次,如果满足,则返回长度
    //bit每一位表示data[i]是否参与计算
    int judge(int bit, vector<int>& data) {
        int x = 0;
        for (int i = 0;i < data.size();i++) {
            if (bit & (1 << i)) {
                if (x & data[i]) {
                    return -1;
                } else {
                    x += data[i];
                }
            }
        }
        int count = 0;
        for (int i = 0;i < 26;i++) {
            if (x & (1 << i)) {
                count++;
            }
        }
        return count;
    }
    int maxLength(vector<string>& arr) {
        vector<int> data;
        for (int i = 0;i < arr.size();i++) {
            string s = arr[i];
            int x = change(s);
            if (x != -1) {
                data.push_back(x);
            }
        }
        int ret = 0;
        for (int i = 1;i < (1 << data.size());i++) {
            int x = judge(i, data);
            if (x != -1) {
                ret = max(ret, x);
            }
        }
        return ret;
    }
};

第四题

第四题最无语,暴力搜索过了。没啥知识点的,就是递归,回溯。据说有 dp 方式,不知道咋做的。
还有用 oeis 大法的。。。很欢乐。

看下递归代码,我稍微写一下注释,当回溯题练习也不错。

class Solution {
public:
    //ret表示当前最小瓷砖数,如果搜索的过程中,瓷砖数比这个数还大,就不用接着搜索了,这是这份代码中唯一的剪枝
    int ret;

    //data表示当前瓷砖铺的情况,总共有n*m个bit,这里把每一行的bit压缩成一个int了,节省空间
    //x表示当前位置的横坐标
    //y表示当前位置的纵坐标
    //now表示当前的瓷砖数
    //n和m就是题目的n和m,因为后面判断需要用到,这里把这俩货也传进来了
    
    //对于dfs来说,状态变量其实只有data,其他变量都是辅助
    void dfs(vector<int>& data, int x, int y, int now, int n, int m) {
        //当行坐标到了n,说明搜索已经结束了,可以保存结果
        if (x == n) {
            ret = min(ret, now);
            return;
        }
        //当纵坐标到了m,说明来到了一行的末尾,直接换下一行的行首继续搜
        if (y == m) {
            dfs(data, x + 1, 0, now, n, m);
            return;
        }
        //如果当前瓷砖数比搜索过的最小瓷砖数还大,直接跳出,这是唯一的剪枝
        if (now >= ret) {
            return;
        }
        //如果坐标(x,y)已经被贴了瓷砖,搜索下一个
        if (data[x] & (1 << y)) {
            dfs(data, x, y + 1, now, n, m);
            return;
        }
        //k表示坐标(x,y)最大可放的瓷砖,如果放下去超过n*m的范围,就不能放了
        int k = 0;
        for (int i = 1;x + i - 1 < n && y + i - 1 < m;i++) {
            k = i;
        }
        //为啥要从最大可放的瓷砖开始搜呢,因为瓷砖越大,最后的瓷砖数会极有可能越少,这样跟剪枝代码结合起来,可以多剪一点
        while (k >= 1) {
            //flag表示是否可以放k\*k的操作,这里应该可以跟上面的循环合并。如果k\*k中正好某个位置已经被贴瓷砖了,就不能放了
            bool flag = true;
            for (int i = 0;i < k;i++) {
                for (int j = 0;j < k;j++) {
                    if (data[x + i] & (1 << (y + j))) {
                        flag = false;
                    }
                }
            }
            //flag为true表示可以放,既然可以放,就放呗
            if (flag) {
                //贴瓷砖的过程
                for (int i = 0;i < k;i++) {
                    for (int j = 0;j < k;j++) {
                        data[x + i] += (1 << (y + j));
                    }
                }
                //继续搜下一个位置
                dfs(data, x, y + 1, now + 1, n, m);
                //回溯的本质,如果搜索完,必须还原现场
                for (int i = 0;i < k;i++) {
                    for (int j = 0;j < k;j++) {
                        data[x + i] -= (1 << (y + j));
                    }
                }
            }
            k--;
        }
    }
    int tilingRectangle(int n, int m) {
        vector<int> data(n, 0);
        ret = n * m;
        dfs(data, 0, 0, 0, n, m);
        return ret;
    }
};
20
展开全部 12 讨论