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

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

image.png

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

展开讨论
共 18 个讨论

方阵中战斗力最弱的 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

第一题:

没啥意思,阅读理解题

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

大佬还是人吗,爷半个多小时做完都快100名了,这些题目很简单???
最后一题思路,先把高度(带index)排序,然后从低往高遍历,更新以每个最高点为起始点的最长距离即可,O(N2)可以过

4

今天的题挺简单
第一题第二题都是排序
第三题求每个子树的和和总和,然后在里面找最接近总和一半的那个
第四题,DP,存好每个下标能跳多远,找最大的那个

3

5328. 方阵中战斗力最弱的 K 行

记录每一行0的个数和对应是第几行,排个序取前k个对应的行数

class Solution:
    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
        res = []
        for i, v in enumerate(mat):
            num = 0
            for j in v:
                if j==1:
                    num+=1
            res.append((num, i))
        res.sort()
        return [i[1] for i in res][:k]

5329. 数组大小减半

算一下每个数字出现的次数,再把次数按降序排序,从最大开始累加,当累积超过总数一半时,所对应的累加次数就是结果

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        le = len(arr)
        ct = dict(collections.Counter(arr))
        it = list(ct.values())
        it.sort(reverse=True)
        res = 0
        sm = 0
        for i in it:
            sm+=i
            res+=1
            if sm>=le/2: break
        return res

5330. 分裂二叉树的最大乘积

一开始看错题了,上了个厕所回来恍然大悟,赶时间怎么想就怎么写了,过程可以更简洁一下

dfs

开两个数组, 一个记录每个非根节点对应子树的和,一个记录所有节点

计算所有节点和 Si

遍历每个非根节点对应子树的和 Sj,计算 Sj*(Si-Sj), 记录最大值即可

class Solution:
    def maxProduct(self, root: TreeNode) -> int:
        mod = 1000000007
        lis = []
        l2 = []
        ans = 0

        def dfs(node):
            nonlocal lis, ans, sm
            if not node:
                return 0
            
            lis.append(node.val)
            res = node.val
            res+=dfs(node.left)
            res+=dfs(node.right)
            
            if node!=root:
                l2.append(res)
            
            return res
        
        dfs(root)
        sm = sum(lis)
        for i in l2:
            ans = max(ans, (sm-i)*i)
        
        return ans%mod

5331. 跳跃游戏 V

最小堆+DP

因为只能从大的柱子往小的跳,所以要先知道小的柱子最多可以访问几个下标

DP[i]表示第i个柱子最多可以访问几个下标

把所有柱子大小和下标压入最小堆

遍历柱子i可以跳到的柱子j,DP[i] = min(DP[j]+1, DP[i])

遍历的时候遇到比自己大的柱子直接跳出

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        from heapq import heappush, heappop
        lis = []
        
        for i, v in enumerate(arr):
            heappush(lis, (v, i))
        
        le = len(arr)
        dp = [-1]*le
        
        
        while lis:
            # print(i)
            v, i = heappop(lis)
            dis = 0
            dp[i] = 1
            for j in range(i+1, min(i+d+1, le)):
              
                if arr[j]>=arr[i]: break
                if dp[j]!=-1:
                    dp[i] = max(dp[j]+1, dp[i])
            for j in range(i-1, max(i-d, 0)-1, -1):
                if arr[j]>=arr[i]: break
                dp[i] = max(dp[j]+1, dp[i])
                
                
        # print(dp)
        return max(dp)

3

C++过不了大数据,是不是要自己写模啊啊啊 哭了

1

第一题:计数,排序
第二题:计数排序,个数贪心从多到少取.
第三题:先求出总和,深搜回溯在每个子树节点的时候,判断self.res = max((总和-left)*left, (总和-right)*right, self.res)
第四题:DP,从低高度开始, 高跳到低的时候,如果已经做过,就加上低的.(代码晚上来写,要去做饭了......)
和大佬的差距太大了,我才写2题,20分钟...他们就都做完了.....

1

最后一题垃圾的我只能想出来构造图,然后Floyd求最短路径,O(N^3)的算法并过不了

1
  1. 方阵中战斗力最弱的 K 行
    方法:简单排序+统计,复杂度o(nlogn)o(nlogn)
    题解:就是维护一个二元组<军人个数,行号>,然后按题意排序一下就行了。
import java.util.Arrays;
import java.util.Comparator;

public class test4 {

    class Point
    {
        public int ju;
        public int row;

        public Point(int ju, int row) {
            this.ju = ju;
            this.row = row;
        }
    }

    class myCom implements Comparator<Point>
    {
        @Override
        public int compare(Point o1, Point o2) {

            if(o1.ju < o2.ju)
            {
                return -1;
            }
            else if(o1.ju == o2.ju)
            {
                if(o1.row < o2.row) return -1;
                return 1;
            }
            return 1;
        }
    }

    public int[] kWeakestRows(int[][] mat, int k) {


        Point[] point= new Point[mat.length];

        for(int i = 0;i < mat.length;i++)
        {
            int sum = 0;
            for(int j = 0;j < mat[i].length;j++)
            {
                if(mat[i][j] == 1) sum++;
            }
            point[i] = new Point(sum,i);
        }

        Arrays.sort(point,new myCom());

        int [] ans = new int[k];

        for(int i = 0;i < k;i++)
        {
            ans[i] = point[i].row;
//            System.out.println(ans[i]);
        }

        return ans;
    }

    public static void main(String[] args) {


        int[][]mat ={{1,1,0,0,0},
                {1,1,1,1,0},
                {1,0,0,0,0},
                {1,1,0,0,0},
                {1,1,1,1,1}};

        int k = 3;

        test4 of = new test4();
        System.out.println(of.kWeakestRows(mat,k));

    }
}
  1. 数组大小减半
    方法:简单统计+排序(贪心),复杂度O(nlogn)O(nlogn)
    题解:我没想多复杂,就是统计一下每个数的个数,然后排个序,从最大的个数开始减,直到满足length<arr.length/2length<arr.length/2
import java.util.*;

public class test5
{
    class MyCom implements Comparator<Integer>
    {

        @Override
        public int compare(Integer o1, Integer o2) {

            if(o1 > o2) return -1;
            else if(o1 < o2) return 1;
            return 0;
        }
    }

    public int minSetSize(int[] arr) {

        int ans = 0;
        int length = arr.length;
        Map<Integer,Integer> maps = new HashMap<>();

        for(int i = 0;i < arr.length;i++)
        {
            maps.put(arr[i],maps.getOrDefault(arr[i],0)+1);
        }

        int i = 0;
        Integer[] key = new Integer[maps.size()];
        Collection<Integer> as = maps.values();

        Iterator<Integer> it = as.iterator();
        while (it.hasNext())
        {
            key[i] = it.next();
            i++;
        }

        Arrays.sort(key,new MyCom());
        for(i = 0;i < key.length;i++)
        {
            length -= key[i];
            ans++;
            if(length<=(arr.length/2)) break;
        }

        return ans;
    }

    public static void main(String[] args) {

        test5 of = new test5();
        int[] arr = new int[]{1,2,3,4,5,6,7,8,9,10};
        System.out.println(of.minSetSize(arr));
    }
}
  1. 分裂二叉树的最大乘积
    方法:遍历,复杂度O(n)O(n)
    题解:首先计算整棵树的sumsum,然后从开始剪边,其实就是遍历一个节点的左右子树,同时得到子树的sonSum,这样就相当于剪边,然后计算sonSum*(sum-sonSum),找到最大值,要记得用long来存,否则会爆数。
public class test6
{
    private long max = 0;
    private final long mod = (int) (1e9+7);
    private long sum = 0;

    public static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
    }

    int getsum(TreeNode root)
    {
        if(root == null) return 0;

        int left = getsum(root.left);
        int right = getsum(root.right);

        return left  + right + root.val;
    }


    long find(TreeNode root)
    {
        long tmp;
        if(root == null) return 0;

        long left = find(root.left);
        tmp = left * (sum - left);
        max = Math.max(tmp,max);

        long right = find(root.right);
        tmp = right * (sum - right);
        max = Math.max(tmp,max);

        return left + right + root.val;
    }

    public int maxProduct(TreeNode root) {

        sum = getsum(root);
        find(root);

        return (int)(max % mod);
    }


    public static void main(String[] args) {

        test6 of = new test6();
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);

        node1.right = node2;
        node2.left = node3;
        node2.right = node4;
        node4.left = node5;
        node4.right = node6;

        System.out.println(of.maxProduct(node1));

    }
}
  1. 跳跃游戏 V
    方法:dp,复杂度O(n2)O(n^2)
    题解:这道题我用滚动的数组来做,其实可以从题意上看出全局的点不管怎么跳,一定会达到一个收敛条件,就是所在的位置都不能再跳了,就代表收敛,所以dp[last][j]代表的是上一次跳动后,到达j点时最大次数dp[now][i]代表的是这次跳动后,到达i点时最大的次数,假设dp[last][j]=0的时候,这个点的在上一次没有跳过来,其实没必要再要这个点了;当dp[last][j]>0,说明这个点上一步有其他点跳过来了,那么尝试这次跳i=(j-d<=j<=j+d),如果能跳,状态转移就为dp[now][i]=dp[last][j]+1dp[now][i]=dp[last][j]+1
public class test7
{

    public void  clear(int[] arr,int val)
    {
        for(int i = 0;i < arr.length;i++) arr[i] = val;
    }

    public int maxJumps(int[] arr, int d) {

        int max = 1;
        int[][] dp = new int[2][arr.length];

        clear(dp[0],1);
        clear(dp[1],0);
        int now = 1;
        int last = now ^ 1;
        boolean flag = true;

        while (flag)
        {
            flag = false;

            for(int i = 0;i < dp[last].length;i++)
            {
                if(dp[last][i] == 0) continue;

                for(int j = i - 1,index = 0;j >= 0 && index < d;j--,index++)
                {
                    if(arr[i] <= arr[j]) break;

                    if(dp[last][i] + 1 > dp[now][j])
                    {
                        flag = true;
                        dp[now][j] = dp[last][i] + 1;
                        max = Math.max(dp[now][j],max);
                    }
                }

                for(int j = i + 1,index = 0;j < dp[last].length && index < d;j++,index++)
                {
                    if(arr[i] <= arr[j]) break;
                    if(dp[last][i] + 1 > dp[now][j])
                    {
                        flag = true;
                        dp[now][j] = dp[last][i] + 1;
                        max = Math.max(dp[now][j],max);
                    }
                }
            }
            now = now ^ 1;
            last = now ^ 1;
            clear(dp[now],0);
        }

        return max;
    }

    public static void main(String[] args) {
        test7 of = new test7();
        int[] arr = new int[]{6,4,14,6,8,13,9,7,10,6,12};
        int d = 2;
        System.out.println(of.maxJumps(arr,d));
    }
}
1

没羞没臊的扔一个自己的题解:LeetCodeWeeklyContest-174