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

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

image.png

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

展开讨论

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
展开全部 12 讨论