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

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

image.png

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

展开讨论

用栈操作构建数组

思路

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