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

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

image.png

3 分 - 分割字符串的最大得分
4 分 - 可获得的最大点数
5 分 - 对角线遍历 II
6 分 - 带限制的子序列和

展开讨论
共 16 个讨论

昨天团体赛被虐,今天的周赛似乎是安慰人的,难度超低。

4

操蛋,手速慢一点就会GG了。。
发下讨论的第2,3,4道题

第2道题:
这道题我的想法是从前往后sum1,从后往前sum2做一次前缀数组,然后遍历k的程度
答案就是ans=max(sum1[k−1−i]+sum2[n−i+1],sum1[k−1],sum2[n−k+1]),i=1,2,...,k−1,n=cardPoints.length−1ans=max(sum1[k-1-i]+sum2[n-i+1],sum1[k - 1],sum2[n - k + 1]), i=1,2,...,k-1, n=cardPoints.length-1

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class test7
{
    public int maxScore(int[] cardPoints, int k)
    {
        if(cardPoints == null || cardPoints.length == 0 || k <= 0) return 0;


        int n = cardPoints.length - 1;
        int[] sum1 = new int[cardPoints.length];
        int[] sum2 = new int[cardPoints.length];

        for (int i = 0; i < sum1.length; i++)
        {
            if(i == 0) sum1[i] = cardPoints[i];
            else sum1[i] = cardPoints[i] + sum1[i-1];

            if(i == 0) sum2[n - i] = cardPoints[n - i];
            else sum2[n - i] = cardPoints[n - i] + sum2[n - i  + 1];
        }

        if(k >= cardPoints.length) return sum1[n];

        int ans = Math.max(sum1[k - 1],sum2[n - k + 1]);
        for(int i = 1; i <= k - 1; i++)
        {
            ans = Math.max(ans,sum1[k - 1 - i] + sum2[n - i + 1]);
        }

        return ans;
    }

    public static void main(String[] args) {
        test7 of = new test7();

        int[] cardPoints = {11,49,100,20,86,29,72};
        int k = 4;
        System.out.println(of.maxScore(cardPoints,k));
    }

}

第3道题:
排序吧,有规律,假设某个位置上的值的坐标为(i,j),对角线上的i+j一定是唯一的,然后排个序就好了

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class test6
{

    class Point implements Comparable<Point>
    {
        int x,y;
        int value;

        @Override
        public int compareTo(Point o)
        {
            int sum1 = x + y;
            int sum2 = o.x + o.y;

            if(sum1 < sum2) return -1;
            else if (sum1 == sum2)
            {
                if (x > o.x) return -1;
            }
            return 1;
        }

        public Point(int x, int y, int value)
        {
            this.x = x;
            this.y = y;
            this.value = value;
        }
    }

    public int[] findDiagonalOrder(List<List<Integer>> nums)
    {
        if(nums == null || nums.size() == 0) return new int[]{};

        int sum = 0;
        for(int i = 0; i < nums.size();i++) sum += nums.get(i).size();

        int top = 0;
        Point[] tmp = new Point[sum];
        int[] ans = new int[sum];

        for (int i = 0; i < nums.size(); i++)
        {
            List<Integer> t = nums.get(i);
            for (int j = 0; j < t.size(); j++)
            {
                tmp[top++] = new Point(i,j,t.get(j));
            }
        }

        Arrays.sort(tmp);

        for (int i = 0; i < tmp.length; i++)
        {
            ans[i] = tmp[i].value;
        }
        return ans;
    }

    public static void main(String[] args)
    {
        int[][] test = {{1,2,3,4,5},{6,7},{8},{9,10,11},{12,13,14,15,16}};

        List<List<Integer>> input = new ArrayList<>();
        for (int i = 0; i < test.length; i++)
        {
            List<Integer> tmp = new ArrayList<>();
            for (int j = 0; j < test[i].length; j++)
            {
                tmp.add(test[i][j]);
            }
            input.add(tmp);
        }
        test6 of = new test6();
        int[] ans = of.findDiagonalOrder(input);
        for (int i = 0; i < ans.length; i++)
        {
            System.out.print(ans[i]+ "  ");
        }
        System.out.println();
    }
}

第4道题:
经典dp,设dp[i]的意思为,当前位置i下的最大值,那么可以想到递推公式为dp[i]=max(max(dp[i−t])+nums[i],num[i]),t=1,...,kdp[i]=max(max(dp[i-t]) + nums[i],num[i]),t=1,...,k
可是这里的max(dp[i-t])得怎么找呢?用单调队列搞一下就好了。

import java.util.Deque;
import java.util.LinkedList;

public class test8
{
    class Point
    {
        int x;
        int value;

        public Point(int x, int value) {
            this.x = x;
            this.value = value;
        }
    }

    public int constrainedSubsetSum(int[] nums, int k)
    {
        if(nums == null || nums.length == 0 || k < 0) return 0;
        int ans = Integer.MIN_VALUE;

        Deque<Point> dq = new LinkedList<>();

        for (int i = 0; i < nums.length; i++)
        {
            if(dq.size() == 0)
            {
                ans = Math.max(ans,nums[i]);
                dq.addLast(new Point(i,nums[i]));
            }
            else
            {
                // 把前面最大值全删除了
                while ( dq.size() > 0 && (i - dq.peekFirst().x) > k)
                {
                    dq.pollFirst();
                }

                int test = nums[i];
                if(dq.size() > 0)
                {
                    test = Math.max(test,dq.peek().value + nums[i]);
                }
                ans = Math.max(test,ans);

                // 把后面最大值也给删除了
                while (dq.size() > 0 && ( (i - dq.peekLast().x) > k || dq.peekLast().value <= test))
                {
                    dq.pollLast();
                }
                dq.addLast(new Point(i,test));
            }
        }

        return ans;
    }


    public static void main(String[] args)
    {
        test8 of = new test8();
        int[] nums = {10,-2,-10,-5,20};
        int k = 2;
        System.out.println(of.constrainedSubsetSum(nums,k));
    }
}
1

第三题给我的伤害比另外三个加起来都大

1

要上班啊,没法参加

1

简单记录一下本次周赛的历程
第一题没多想,O(N^2)超级暴力枚举
第二题先记录每个位置的连续和,然后枚举
第三题是个排序,以i+j为主关键字,j为次关键字,排序后按次序输出对应值即可
第四题我的想法是DP+滑动窗口求最大值,当然看了大佬的解说我发现是单调队列,比赛的时候自己搓了极其丑陋的数据结构来求k滑动窗口的最大值

题目里坑真多,罚时好几次😭😭

为什么前200的积分还没有发呢

做第四题的时候,发现测试用例[-1,-2,-3]和k=1答案是-1,然而运行时答案变成了36,发现是全局变量数组的初始化出了问题,不全为零导致了错误,请问是什么情况?

int que[100005];
int dp[100005];
int head=1,tail=0;
class Solution {
public:
    int constrainedSubsetSum(vector<int>& nums, int k) {
        int n=nums.size();
        int r=-2e9;
        for(int i=0;i<10;i++){
            cout<<que[i]<<endl; // 显示未初始化全局数组的前十位
        }
        //memset(que,0,100005);
        //memset(dp,0,100005);
        for(int i=0;i<n;i++){
            while(head<=tail && que[head]<i-k) head++;
            int w=(head>tail)?0:dp[que[head]];
            w=max(w,0);
            w+=nums[i];
            dp[i]=w;
            while(head<=tail && dp[que[tail]]<dp[i]) tail--;
            que[++tail]=i;
            r=max(r,dp[i]);
        }
        
        return r;
    }
};

报错:
image.png

捞的不谈,喜获两个超时

第三题不是说最多10^5个数吗,那为什么还会超时?