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

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

image.png

3 分 - 用栈操作构建数组
4 分 - 形成两个异或相等数组的三元组数目
5 分 - 收集树上所有苹果的最少时间
7 分 - 切披萨的方案数

展开讨论
共 12 个讨论

用栈操作构建数组

用两个指针来维护一些信息:

  1. a 指针指向目标数组的元素
  2. b 指针指向 {1,2,3 ... n} 列表的当前元素

显然可以得到以下操作:

  1. 当 b 所指元素小于 a 所指元素,需要丢弃,对应一个 Push + Pop;并且 b 移向下一位
  2. 当 b 所指元素等于 a 所指元素,需要保留,对应一个 Push;b 和 a 都移向下一位
  3. 按题意给出的保证可推导出,b 所指元素不会大于 a 所指的元素

形成两个异或相等数组的三元组数目

关于异或有两个常用的性质:

  1. 任何数和自己异或都得到 0
  2. 任何数和 0 异或都得到自身

由以上两条性质不难解决一个问题 —— 对于一个数组,想求下标范围 [i, j] 之间的所有元素的异或值,可以转化为两个前缀的异或:

  1. pre[j]: 表示 [0, j] 的异或值
  2. pre[i-1]: 表示 [0, i-1] 的异或值
  3. pre[j] ^ pre[i-1] 等价于把 pre[i-1] 抵消掉了,只剩下 [i, j] 的异或值

回到本题:

  1. 先预处理出前缀元素的异或值,记 pre[i] 表示 [0, i] 元素的异或值,O(n)
  2. 对于查询 [i, k] 可以 O(1) 回答:pre[k] ^ pre[i-1]
  3. 对于 [i, k] 的异或值为 0,必定存在下标 j,使得 [i, j-1] 的异或值等于 [j, k] 的异或值(性质1); 枚举下标 j 进行判断

收集树上所有苹果的最少时间

基于一个基本的贪心策略:一个子树有苹果才需要深入下去。因此我们要记录每个节点及其子树下是否有苹果

  1. 记 cnt[i] 表示节点 i 及其子树的苹果数,cnt[i] > 0 表示有苹果
  2. 对于节点 u,它的儿子节点 v,满足 cnt[v] > 0 才需要走进去
  3. 记得返回时,步数也要加 1;特别的,从节点 0 不需要返回,不要加步数

切披萨的方案数

问题的突破在于切饼的方式:每次横切完会把上部分给顾客,竖切完会把左部分给顾客,这意味着上或左部分是不会再参与切割的。

问题进一步转化为,其实总是在考虑某个 (r,c,n,m) 矩阵应该怎么切,其中 r,c 表示矩阵左上角坐标,n,m 表示原始矩阵右下角。

用 DP 来解决这类计数问题:

  1. dp[r][c][k] 表示 (r,c,n,m) 矩阵切成 k 份的方案数;总的状态个数为 505010 = 25000
  2. 枚举横切,假设在 r1 行切,那么转向 dp[r1][y][k-1]
  3. 枚举竖切,假设在 c1 列切,那么转向 dp[r][c1][k-1]
  4. 枚举的代价为 50 + 50 = 100
  5. 总的时间复杂度 O(n * n * k * (n+n))

还需要解决一个问题,判断切割是否合法,也就是判断一个矩阵内是否有苹果:

  1. 把整个矩阵看成 0 1 矩阵,有苹果是 1;一个矩阵有苹果说明矩阵元素和大于 0
  2. 求一个矩阵 (r,c,r1,c1) 的和,等价于 (0,0,r1,c1) - (0,0,r1,c-1) - (0,0,r1-1,c1) + (0,0,r1-1,c1-1);因此先预处理出所有 (0,0,r,c) 矩阵的和
7

这次的成绩又是前二!(指做出来前两个题)

4

第一次AK,纪念下😂
1.

class Solution {
    public List<String> buildArray(int[] target, int n) {
        List<String> ans = new ArrayList<>();
        if(target.length == 0)
            return ans;
        int last = 0;
        for(int curr:target) {
            for(int j=1;j<curr - last;j++) {
                ans.add("Push");
                ans.add("Pop");
            }
            ans.add("Push");
            last = curr;
        }
        return ans;
    }
}
class Solution {
    public int countTriplets(int[] arr) {
        int[][] dp = new int[arr.length][arr.length];
        for (int i = 0; i < arr.length; i++) {
            int prev = arr[i];
            dp[i][i] = prev;
            for (int j = i + 1; j < arr.length; j++) {
                dp[i][j] = prev ^ arr[j];
                prev = dp[i][j];
            }
        }
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                for (int k = j; k < arr.length; k++) {
                    if (dp[i][j - 1] == dp[j][k])
                        count++;
                }
            }
        }
        return count;
    }
}
class Solution {
    private List<Boolean> hasApple;
    private Map<Integer, List<Integer>> g;

    public int minTime(int n, int[][] edges, List<Boolean> hasApple) {
        g = new HashMap<>();
        this.hasApple = hasApple;
        for (int[] e : edges) {
            List<Integer> ch = g.get(e[0]);
            if (ch == null)
                g.put(e[0], ch = new ArrayList<>());
            ch.add(e[1]);
        }
        return Math.max(0, dfs(0))*2;
    }

    private int dfs(int root) {
        List<Integer> ch = g.getOrDefault(root, Collections.emptyList());
        if (ch.isEmpty()) {
            return hasApple.get(root) ? 0 : -1;
        }
        int ans = 0;
        for (int next : ch) {
            int nextPath = dfs(next);
            if (nextPath >= 0)
                ans += nextPath + 1;
        }
        return ans == 0 ? (hasApple.get(root) ? 0 : -1) : ans;
    }
}
class Solution {
    boolean[][] grid;
    Integer[][][] memo;
    private int kMod = (int) (1e9 + 7);

    public int ways(String[] pizza, int k) {
        int m = pizza.length;
        int n = pizza[0].length();
        grid = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pizza[i].charAt(j) == 'A')
                    grid[i][j] = true;
            }
        }
        memo = new Integer[m][n][k + 1];
        return dp(0, 0, k);
    }

    private boolean hasAppleCurr(int left, int right, int top, int bottom) {
        for (int i = left; i < right; i++)
            for (int j = top; j < bottom; j++)
                if (grid[j][i])
                    return true;
        return false;
    }

    private int dp(int left, int top, int k) {
        if (left >= grid[0].length || top >= grid.length)
            return 0;
        if (memo[top][left][k] != null)
            return memo[top][left][k];
        if (k == 1) {
            return hasAppleCurr(left, grid[0].length, top, grid.length) ? 1 : 0;
        }
        long ans = 0;
        // 横切
        for (int i = top + 1; i < grid.length; i++) {
            if (hasAppleCurr(left, grid[0].length, top, i))
                ans = (ans + dp(left, i, k - 1)) % kMod;
        }
        for (int i = left + 1; i < grid[0].length; i++) {
            if (hasAppleCurr(left, i, top, grid.length))
                ans = (ans + dp(i, top, k - 1)) % kMod;
        }
        return memo[top][left][k] = (int) ans;
    }
}
2

第一题:“题目数据保证答案是唯一的”
真的吗?

2

题目出的不错,难度很适中,考察的也挺全面,就是最后一题因为忘了取模白白弄了一个WA。

1

用栈操作构建数组

思路

  1. 读懂题意
  2. 意思就是说,从 1 - n 依次 Push 进来数字
  3. 如果目标数组里没有这个数,就把它 Pop 出去

答题

    vector<string> buildArray(vector<int>& target, int n) {
        vector<string> ans;
        int i = 1;
        for (auto& t : target) {
            while (i < t) {
                i++;
                ans.push_back("Push");
                ans.push_back("Pop");
            }
            i++;
            ans.push_back("Push");
        }
        return ans;
    }

形成两个异或相等数组的三元组数目

思路

  1. 吃了异或不熟的亏,题解区有更好的解法

答题

    int countTriplets(vector<int>& arr) {
        int ans = 0;
        for (int i = 1; i < arr.size(); i++) {
            arr[i] = arr[i - 1] ^ arr[i];
        }
        for (int i = 0; i < arr.size(); i++) {
            for (int j = i + 1; j < arr.size(); j++) {
                for (int k = j; k < arr.size(); k++) {
                    int a = (i == 0) ? arr[j - 1] : arr[j - 1] ^ arr[i - 1];
                    int b = arr[k] ^ arr[j - 1];
                    ans += (a == b);
                }
            }
        }
        return ans;
    }

收集树上所有苹果的最少时间

思路

  1. 首先处理下输入数据,转成树形结构
  2. 只有当这个节点或者其子节点有苹果的时候,才需要走到这个节点来
  3. 递归,返回值为是否有苹果
  4. 对于有苹果的节点,如果不是根节点,就加上个 2 ,即来回的路程

答题

class Solution {
public:
    int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {
        vector<vector<int>> ft(n, vector<int>());
        for (int i = 0; i < edges.size(); i++) {
            ft[edges[i][0]].push_back(edges[i][1]);
        }

        int ans = 0;
        minTime(0, ft, hasApple, ans);
        return ans;
    }

    bool minTime(int from, vector<vector<int>>& ft, vector<bool>& hasApple, int& ans) {
        bool ha = hasApple[from];
        for (auto& to : ft[from]) {
            if (minTime(to, ft, hasApple, ans)) {
                ha = true;
            }
        }
        ans += (ha && from != 0) ? 2 : 0;
        return ha;
    }
};

切披萨的方案数

思路

  1. 没来的及做,一会儿来补

致谢

感谢您的观看,希望对您有帮助,欢迎热烈的交流!

如果感觉还不错就点个赞吧~

这是 我的leetcode ,帮助我收集整理题目,可以方便的 visual studio 调试,欢迎关注,star

1

复制样例的时候因为提交快捷键喜提两发 WA
佛辣

总觉得很快就能找出bug,然后看着截止时间的到来还是改不对……T_T!

这次第三题怎么大家都会做?为何我觉得很难呀。。。

比赛完才看到这周周赛还可以简历内推?这什么操作,参加周赛不多,还没见到过这样的周赛