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

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

image.png

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

展开讨论

方阵中战斗力最弱的 K 行

思路

  1. 循环时,按照列优先,这样能第一时间发现先变成 0 的行
  2. 将变成 0 的行加入结果,使用 vi 记录

答题

vector<int> kWeakestRows(vector<vector<int>>& mat, int k)
{
    vector<int> ans;
    vector<int> vi(mat.size(), 0);
    int minSum = INT_MAX;
    for (int j = 0; j < mat[0].size(); j++)
    {
        if (ans.size() == k) break;
        for (int i = 0; i < mat.size(); i++)
        {
            if (ans.size() == k) break;
            if (vi[i] == 1) continue;
            if (mat[i][j] != 0) continue;
            ans.push_back(i);
            vi[i] = 1;
        }
    }
    int ii = 0;
    while (ans.size() != k)
    {
        while (vi[ii] == 1) ii++;
        ans.push_back(ii);
        vi[ii] = 1;
    }
    return ans;
}

数组大小减半

思路

  1. 使用 map 计算出每个数字出现的次数
  2. 将次数保存在 vector 中,排序
  3. 将次数从大到小取出,如果和超过了一半,返回取出的个数

答题

int minSetSize(vector<int>& arr) 
{
	map<int, int> cnt;
	for (auto &n : arr)
	{
		cnt[n]++;
	}

	vector<int> v;
	for (auto &m : cnt)
	{
		v.push_back(m.second);
	}
	sort(v.rbegin(), v.rend());

	int sum = arr.size() / 2;
	for (int i = 0; i < v.size(); i++)
	{
		sum -= v[i];
		if (sum <= 0) return i + 1;
	}
	return -1;
}

分裂二叉树的最大乘积

思路

  1. 使用 dfs 将原树转化为前缀和树
  2. 使用 dfs 找到与总和一半最接近的值
    21. 想要 k * (k - x) 最大, x 需要接近 k 的一半
  3. 相乘取模,注意使用 long long

答题

int part_sum(TreeNode* root)
{
	if (root == nullptr) return 0;
	root->val += part_sum(root->left) + part_sum(root->right);
	return root->val;
}

void getDiff(TreeNode* root, int full, int& diff)
{
	if (root == nullptr) return;
	int a = full - root->val * 2;
	diff = (abs(a) < abs(diff)) ? a : diff;
	getDiff(root->left, full, diff);
	getDiff(root->right, full, diff);
}

int maxProduct(TreeNode* root) 
{
	if (root == nullptr) return 0;
	root->val += part_sum(root->left) + part_sum(root->right);

	int full = root->val;
	int diff = INT_MAX;
	getDiff(root, full, diff);
	int half = (full + diff) / 2;

	int ans = ((long long)(full - half) * (long long)half) % (long long)(1e9 + 7);
	return ans;
}

跳跃游戏 V

思路

  1. 分析题目
    11. 只能往左右两个方向跳
    12. 只能往低了跳,并且跳过去的部分不能比起跳点
    13. 可以从任意点起跳,不能跳到外边
    14. 求最多能跳的次数
  2. 递归
    21. 从一个点开始跳,往左或往右
    22. 如果高度比 起跳点 高,就结束
    23. 如果可以跳,就挨着跳
    231. 起跳点可跳跃次数 是所有能跳到的点的最大 可跳跃次数 加一
    232. 递归进入这个点,计算他的 可跳跃次数
    24. 如果左右两边都没有可以继续跳的点,那么这个点的 可跳跃次数 为 0 (递归出口)
    25. 使用 vector<int>& steps 记忆化已经确定的 可跳跃次数
    26. 使用 ans 保存最大的结果

答题

void maxJumps(vector<int>& arr, int d, int cur, vector<int>& steps, int& ans)
{
	if (steps[cur] != -1) return;

	int l = max(0, cur - d);	// 确定左右边界
	int r = min((int)arr.size() - 1, cur + d);

	int step = 0;
	for (int dirction = -1; dirction <= 1; dirction += 2)	// 方向,往左往右
	{
		for (int i = cur + dirction; i <= r && i >= l; i += dirction)
		{
			if (arr[cur] <= arr[i]) break;	// 高度超过就结束

			maxJumps(arr, d, i, steps, ans);	// 递归
			step = max(step, steps[i]);
		}
	}

	steps[cur] = step + 1;
	ans = max(ans, steps[cur]);
}

int maxJumps(vector<int>& arr, int d) 
{
	vector<int> steps(arr.size(), -1);
	int ans = 0;
	for (int i = 0; i < arr.size(); i++)
	{
		maxJumps(arr, d, i, steps, ans);
	}
	return ans;
}

致谢

当看到 跳跃游戏 的时候,我就想这题一定要做出来呀,嘿嘿

赶在 11:57 提交,能够完赛还是开心!

9
展开全部 18 讨论