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

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

image.png

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

展开讨论
共 12 个讨论

第一题

看数据范围,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

把本周赛打表的第一名举报了

if n < m: n, m = m, n
        ans = [
        [1],
        [2,1],
        [3,3,1],
        [4,2,4,1],
        [5,4,4,5,1],
        [6,3,2,3,5,1],
        [7,5,5,5,5,5,1],
        [8,4,5,2,5,4,7,1],
        [9,6,3,6,6,3,6,7,1],
        [10,5,6,4,2,4,6,5,6,1],
        [11,7,6,6,6,6,6,6,7,6,1],
        [12,6,4,3,6,2,6,3,4,5,7,1],
        [13,8,7,7,6,6,6,6,7,7,6,7,1]
        ]
        return ans[n-1][m-1]

题库里打表就罢了,竞赛打表挺过分,而且平时都是玩cpp的,偏偏这道题直接用python打表,让人怀疑。

我不清楚明令禁止的库、函数是什么,但哪怕调用一个库函数解决,也比这种打表强。

16

160题解:

P1,直接从小到大枚举x,根据单调性可以二分出y。总体nlogn

P2,就是格雷码的生成,自行google格雷码生成方法:

    next ^= next ^ (next - 1) + 1

P3,DFS,先把arr中字符串自己就包含重复字符的删掉,然后搜索即可

    fn dfs(arr: &Vec<String>, set: &mut HashSet<u8>, idx: usize, ans: &mut usize) {
        if *ans == 26 {
            return;
        }
        for i in idx..arr.len() {
            if set.len() + arr[i].len() > 26 {
                continue;
            }
            if Self::not_in_set(set, &arr[i]) {
                for c in arr[i].as_bytes() {
                    set.insert(*c);
                }
                *ans = max(*ans, set.len());
                Self::dfs(arr, set, i+1, ans);
                for c in arr[i].as_bytes() {
                    set.remove(c);
                }
            }
        }
    }

P4,动态规划。枚举给大矩形左下角填充一个长度为i的正方形,然后可以用三种方法切割剩下的部分。
0.jpeg

最主要就是第三种切法,相当于在剩下的面积中先挖一个洞。枚举这个洞的大小,然后进行切割即可。(自己想想为什么第三种切割方法挖洞要这么挖?提示:如果那个洞放在别的地方,都可以看成前两种切割方法的子问题)

use std::cmp::{max, min};

impl Solution {
    pub fn tiling_rectangle(n: i32, m: i32) -> i32 {
        let n = n as usize;
        let m = m as usize;
        if n == m {
            return 1;
        }
        let mut f = vec![vec![0; max(n,m)+1]; max(n,m)+1];
        Self::fill(n, m, &mut f)
    }
    fn fill(n:usize, m: usize, f: &mut Vec<Vec<i32>>) -> i32 {
        if n == 0 || m == 0 {
            return 0;
        }
        // 保证n比较大 方便处理
        if m > n {
            return Self::fill(m,n, f);
        }
        if m == 1 {
            return n as i32;
        }
        if f[n][m] != 0 {
            return f[n][m];
        }
        let mut ans = (m*n) as i32;
        for i in (1..=m).rev() {
            //竖着切
            ans = min(ans, Self::fill(n-i, i, f)+Self::fill(n, m-i, f)+1);

            // 横着切
            ans = min(ans, Self::fill(n-i, m, f)+Self::fill(i, m-i, f)+1);

            // 挖个洞 枚举洞的大小
            for j in 1..min(m-i, i) {
                let t = Self::fill(n-i, i+j, f) + Self::fill(i-j, m-i, f) + Self::fill(n-i+j, m-i-j, f);
                ans = min(ans, t+2);
            }
        }
        f[n][m] = ans;
        f[m][n] = ans;
        ans
    }
}
9

花了30分钟时间看懂第一题是什么意思。。。

5

先占坑,题解稍晚来:

  • 找出给定方程的正整数解
    数据范围在 [1,1000][1,1000],所以 O(n2)O(n^2) 的暴力解可以过。但其实这题和 LeetCode 74 是一模一样的,是双指针的一道非常经典的题目。大家可以参考 7474 的题解,这里就不详说了。最优复杂度为 O(n)O(n)

  • 循环码排列
    用归纳法证明:

    1. 首先,只有一位的时候,我们可以得到一个合法序列 [0,1][0,1],我们用序列 ss 表示。
    2. 现在来考虑两位的情况,我们在前面的序列中都加上 0011,可以得到 [00,01][00,01][10,11][10,11] 两个序列组,我们也称为序列 leftleft 和序列 rightright同一个序列组一定满足相邻只相差一位,因为他们的第一位补充的都是一样的。另外一个结论是, leftleft 序列的第一个串,和 rightright 序列的第一个串是只相差一位的(只有我们补充的第一位不同),同理,leftleft 序列的最后一个串,和 rightright 序列的最后一个串是只相差一位的。那么,如果我们把 rightright 序列转置和 leftleft 序列拼接,最后就能得到一个合法的序列排列
    3. 同理,对于 nn 更大的情况,也可以类似的得到结果。

    时间复杂度为 O(n2)O(n^2)

  • 串联字符串的最大长度
    由于字符串数量只有 1616 个,我们可以枚举每个字符串用或者不用,来暴力所有的结果,时间复杂度为 O(2nnm)O(2^n*n*m)mm 为字符串长度。可以用动态规划优化一下转移降低为 O(2nm)O(2^n*m) 复杂度。

  • 铺瓷砖
    这题争议比较大,各种解法也很多,先上结论:这题是一个NP问题,所以所有多项式复杂度算法都存在问题。下面给一个例子,多项式解可以验证一下,更多的例子可以参考参考网站

    image.png

    所以我们只需要关注搜索解法就可以了。有一种主流的写法是存储一个二维状态数组,记录每个格子是否被占用,然后每次取最左上的空格子,枚举放置的正方形长度来进入下一个状态。这种做法也能通过题目,但是可以稍微简化一下,我们可以只用一个一维数组记录状态,数组的每一个值是 这一行目前被占用的长度,比如 [1,2,1][1,2,1],对应着:

    [[1,0,0],
    [1,1,0],
    [1,0,0]]

    然后我们每次枚举 当前长度最短的行,然后以这点作为要放置的正方形的左上角,枚举要放置的正方形的边长。理论上的状态总数为 nnn^n,每次枚举的方法数为 nn 种。 理论时间复杂度上界为 O(nn+2)O(n^{n+2})

1

咋参加啊

5

第二题你们怎么做的

T4 要打表该怎么打,手算吗?

第四题我的暴力写了一个可能存在错误的剪枝,然后过了,但是差两分钟所以没交上去。。
但看起来正确解法还是dp,暴力做题不可取

第四题又是各种面向测试用例编程的。。。包括我

6