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

这是 9 月的第二场周赛,欢迎小伙伴们在这里交流分享你的参赛心得以及体验。

image.png

展开讨论
共 17 个讨论

分享一下第四题的做法~

题意:给定一个数组 arr1arr1,操作可以将 arr1arr1 中数字变换为 arr2arr2 中数字,问将 arr1arr1 变为一个严格升序的数组的最小操作次数。

首先,一个很明显的贪心是,如果我们要确定对 arr1[i],i>1arr1[i], i>1 进行操作,那么我们一定选择一个最小的 karr2k \in arr2 且满足 k>arr1[i1]k > arr1[i-1]。因为,我们将 arr1[i]arr1[i] 变得越小,之后留给后面的数字的余地就越多。
所以,对于 arr1arr1 中的一个数字,只有两个选择:不变 / 变成 arr2arr2 中最小的大于它的数字。

这样,就可以动态规划了,定义 DP[i][j]DP[i][j] 表示将 arr1arr1 中的第 ii 个数字变为 arr2arr2 中的第 jj 个数字后(可以设定一个特殊的 jj 表示 arr1[i]arr1[i] 不变),满足 arr1[1i]arr1[1\cdots i] 严格升序递增的最小操作次数。
转移方程就是对于所有的 dp[i][j]dp[i][j],枚举第 arr1[i+1]arr1[i+1] 是否变化,然后进行转移就可以了。(转移详情见代码)

int pool[2050];
int dp[2050][2050];
class Solution {
public:
    int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
        int n=arr1.size(), m=arr2.size();
        
        for (int i=0; i<m; i++) pool[i]=arr2[i];
        sort(pool, pool+m);
        m=unique(pool, pool+m)-pool;
        
        memset(dp, -1, sizeof(dp));
        dp[0][m]=0; for (int i=0; i<m; i++) dp[0][i]=1;
        for (int i=0; i<n-1; i++){
            for (int j=0; j<=m; j++){
                if (dp[i][j]==-1) continue;
                int now_v=(j==m?arr1[i]:pool[j]);
                // Don't
                if (arr1[i+1]>now_v){
                    if (dp[i+1][m]==-1 || dp[i+1][m]>dp[i][j]) dp[i+1][m]=dp[i][j];
                }
                // Modify
                int nxt_p=upper_bound(pool, pool+m, now_v)-pool;
                if (nxt_p<m){
                    // printf("Change(%d) %d->%d\n", i, arr1[i], pool[nxt_p]);
                    if (dp[i+1][nxt_p]==-1 || dp[i+1][nxt_p]>dp[i][j]+1) dp[i+1][nxt_p]=dp[i][j]+1;
                }
            }
        }
        
        int ans=-1;
        for (int i=0; i<=m; i++){
            if (dp[n-1][i]==-1) continue;
            if (ans==-1 || ans>dp[n-1][i]) ans=dp[n-1][i];
        }
        
        return ans;
    }
};
15

当我开始用O(n^2)暴力法做第三题时,我就该想到会超时的。

9

分享一下第三题的思路。O(N)时间,O(1)空间

class Solution {
public:
    int maximumSum(vector<int>& arr) {
        unsigned n = arr.size();
        int dp_i_0 = -1e4, dp_i_1 = -1e4;
        int ans = INT_MIN;
        for (int i = 0; i < n; ++i) {
            dp_i_1 = max(dp_i_1 + arr[i], dp_i_0);
            dp_i_0 = max(dp_i_0 + arr[i], arr[i]);            
            ans = max(ans, max(dp_i_0, dp_i_1));
        }
        return ans;
    }
};
5

Java 题解比较少,分享一下来自一个大佬的第三题的动态规划

public int maximumSum(int[] arr) {
    int ans = arr[0];
    int len = arr.length;
    int[][] dp = new int[len][2];
    // 初始化状态
    // "尚未删除",最大子数组和为本身
    dp[0][0] = arr[0];
    // "已经删除",只能删除自身,最大子数组和为 0
    dp[0][1] = 0;
    for (int i = 1; i < len; i++) {
        // 如果前一个子数组和大于 0,则加上
        dp[i][0] = Math.max(arr[i], arr[i] + dp[i - 1][0]);
        // 删除的字符的两种情况:
        // 1. 当前数字被删除,为了满足至少一个元素,必须加上前面一个子数组 "尚未删除" 的最大值
        // 2. 当前数字不被删除,则由前面子数组删除,前面子数组 "已经删除" 的最大值加上当前数字
        dp[i][1] = Math.max(dp[i - 1][1] + arr[i], dp[i - 1][0]);
        // 两种状态都可能产生最大值
        ans = Math.max(ans, dp[i][0]);
        ans = Math.max(ans, dp[i][1]);
    }
    return ans;
}

作者:hlxing
链接:https://leetcode-cn.com/circle/article/lwbQfe/
3

分享一篇个人创作的周赛题解,「第 153 场周赛」题解,欢迎阅读~

2

一直以为平年二月是30天,闰年是31天,我一年有367天,郁闷了好久,真是 *** 了

3

今天做出来两个题
分享一下
第一题

class Solution:
    def distanceBetweenBusStops(self, distance: List[int], start: int, destination: int) -> int:
        if len(distance)==1:
            return distance[0]
        if start > destination:
        	start,destination = destination,start
        a = sum(distance[start:destination])
        del distance[start:destination]
        b = sum(distance)
        return min(a,b)

第二题


import java.time.LocalDate;
class Solution {
    public String dayOfTheWeek(int day, int month, int year) {
        String ans[] = {"", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday","Sunday"};
        LocalDate ld = LocalDate.of(year,month,day);
        int a = ld.getDayOfWeek().getValue();
        System.out.println(a);
        return ans[a];
    }
}

没了

1

第三题O(n)解法,不用辅助数组,直接用两个辅助的数,分两种情况,一种是连续的子序列不删除,这个简单,O(n)搞定,另一种情况是连续子序列中删除一个,这种情况下,对于以J结尾的某个子序列来说,当新增第J+1个元素时只有两种情况,要么j+1直接添加到现有结果,要么j+1就是要删除的,对于j+1要删除的情况,只需要在找到前面最大的连续子序列即可。

class Solution {
public:
	int maximumSum(vector<int>& arr) {
		int arrLength = arr.size();

		if (1 == arrLength) {
			return arr[0];
		}
		int result = arr[0];

		int sum, presum, preSumMin, prepreSumMin, preMinMinux, prepreMinMinux;
		presum = arr[0];
		prepreSumMin = 0;
		prepreMinMinux = arr[0];
		int maxContinue = arr[0];
		for (int i = 1; i < arrLength; ++i) {
			sum = presum + arr[i];
			preSumMin = min(prepreSumMin, presum);
			maxContinue = max(maxContinue, sum - preSumMin);

			preMinMinux = min(arr[i] + prepreSumMin, prepreMinMinux);

			if (1 == i) {
				result = max(result, max(sum, maxContinue));
			}
			else {
				result = max(result, max(sum - preMinMinux, maxContinue));
			}

			presum = sum;
			prepreSumMin = preSumMin;
			prepreMinMinux = preMinMinux;
		}

		return result;
	}
};

一紧张把第三题看错了。。
当成求幂集再求最大了
太惨了,写完调试的时候才发现

第三题O(n)做法
分别记录不删除数字和可删除数字的两种Sum

    public int maximumSum(int[] arr) {
        if (arr.length == 0)return 0;
        if (arr.length == 1)return arr[0];

        int sum = 0;
        int res = 0;
        int maxNum = arr[0];

        boolean used = false;
        int useNum = 0;
        int sumRegular = 0;

        for (int i = 0; i < arr.length; i++) {
            maxNum = Math.max(maxNum,arr[i]);

            int cur = arr[i];

            if (cur>=0){
                sum += cur;
                res = Math.max(res,sum);
            }else {
                if (sum+cur>0){
                    sum+=cur;
                    if (!used){
                        sum-=cur;
                        used = true;
                        useNum = cur;
                    }
                    else if (cur<useNum){
                        sum+=useNum;
                        sum-=cur;
                        used = true;
                        useNum = cur;
                    }
                }else {
                    if (sum+useNum>0){
                        used = true;
                        sum = sum+useNum;
                        useNum = cur;
                    }else {
                        used = false;
                        sum = 0;
                    }
                }
                if (sumRegular > sum){
                    sum = sumRegular;
                    used = true;
                    useNum = cur;
                }
            }

            if (sumRegular+cur>0)sumRegular+= cur;
            else sumRegular = 0;
//            System.out.println(cur+"  "+sum+" "+used+" "+useNum+" "+sumRegular);
        }
        if (maxNum<=0)return maxNum;
        return res;
    }
1