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

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

image.png

3 分 - 方阵中战斗力最弱的 K 行
4 分 - 数组大小减半
5 分 - 分裂二叉树的最大乘积
6 分 - 跳跃游戏 V

第一题:

没啥意思,阅读理解题

class Solution {
public:
    int sum(vector<int>& v) {
        int ret = 0;
        for (int data: v) {
            ret += data;
        }
        return ret;
    }
    vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
        vector<pair<int, int>> data;
        for (int i = 0;i < mat.size();i++) {
            data.push_back(make_pair(sum(mat[i]), i));
        }
        sort(data.begin(), data.end());
        vector<int> ret;
        for (int i = 0;i < k;i++) {
            ret.push_back(data[i].second);
        }
        return ret;
    }
};

第二题:

这一题是贪心,某个数越多,删掉它就越可能达到数组大小减半的要求

  1. 统计每个数的数量
  2. 按照每个数的数量从大到小排序
  3. 按数量从大到小一个一个减,直到达到数组大小减半
class Solution {
public:
    int minSetSize(vector<int>& arr) {
        map<int, int> counter;
        for (int& data: arr) {
            counter[data]++;
        }
        
        vector<int> data;
        for (auto it = counter.begin();it != counter.end();it++) {
            data.push_back(it->second);
        }
        sort(data.begin(), data.end(), greater<int>());
        
        int ret = 0;
        int sum = arr.size();
        int i = 0;
        while (i < data.size() && sum * 2 > arr.size()) {
            sum -= data[i];
            i++;
            ret++;
        }
        return ret;
    }
};

第三题:

二叉树的边总共就 n - 1 个,在 dfs 遍历时,不管是前中后序,从 root 都会遍历到 root -> left 和 root -> right ,这个关系,其实就是边的关系。

每条边连接着一对父子节点,断开这条边,相当于以子节点为根的子树从父节点断开,因此我们得到以下这个算法:

  1. dfs 统计所有节点的和
  2. 再一次 dfs ,计算每一个子树的和,假设某个子树的节点和为 aa ,那么断开子树的根节点到父节点后,分裂二叉树的乘积为 a(suma)a * (sum - a)
  3. 统计所有的乘积,取最大

注意两个问题:

  1. 需要用 64 位整数来保存中间结果,最后再取模,不能用取模的结果来比较大小
  2. leetcode 的 c++ 不知道加了什么编译参数,如果单个函数自我递归,不会出现栈溢出异常,但其他情况就不一定了
class Solution {
public:
    long long ret = 0;
    long long _sum = 0;
    int sum(TreeNode* root) {
        int ret = 0;
        if (!root) {
            return 0;
        }
        return root->val + sum(root->left) + sum(root->right);
    }
    int dfs(TreeNode* root) {
        if (!root) {
            return 0;
        }
        int s = root->val;
        if (root->left) {
            int left = dfs(root->left);
            ret = max(ret, left * (_sum - left));
            s += left;
        }
        if (root->right) {
            int right = dfs(root->right);
            ret = max(ret, right * (_sum - right));
            s += right;
        }
        return s;
    }
    int maxProduct(TreeNode* root) {
        _sum = sum(root);
        ret = 0;
        dfs(root);
        return ret % 1000000007;
    }
};

第四题:

第四题出得不错,dp 有个重要的条件,就是 dp 阶段先后的问题。01 背包中,由于物品是相对独立的,哪个物品先进哪个物品后进,没什么区别。在最长上升序列中,变更的序列是以流的形式存在的。在这个题中,由于数值高的可以跳到数值低的,数值低的不可以跳到数值高的,因此这个题的递推顺序是从数值低的点递推到数值高的点

class Solution {
public:
    int maxJumps(vector<int>& arr, int d) {
        vector<pair<int, int>> data;
        for (int i = 0;i < arr.size();i++) {
            data.push_back(make_pair(arr[i], i));
        }
        sort(data.begin(), data.end());
        
        vector<int> dp(arr.size(), 1);
        int ret = 0;
        for (int i = 0;i < data.size();i++) {
            int now = data[i].second;
            
            int j = now - 1;
            while (j >= 0 && arr[j] < arr[now] && now - j <= d) {
                dp[now] = max(dp[now], dp[j] + 1);
                j--;
            }
            j = now + 1;
            while (j < arr.size() && arr[j] < arr[now] && j - now <= d) {
                dp[now] = max(dp[now], dp[j] + 1);
                j++;
            }
            ret = max(ret, dp[now]);
        }
        return ret;
    }
};
5
展开全部 18 讨论