leetcode 153周赛

浅浅的花香味﹌ 2023-08-17 15:44 104阅读 0赞

> 链接：[https://leetcode-cn.com/contest/weekly-contest-153/][https_leetcode-cn.com_contest_weekly-contest-153]  
> 环形公交路线上有 n 个站，按次序从 0 到 n - 1 进行编号。我们已知每一对相邻公交站之间的距离，distance\[i\] 表示编号为 i 的车站和编号为 (i + 1) % n 的车站之间的距离。  
> 环线上的公交车都可以按顺时针和逆时针的方向行驶。  
> 返回乘客从出发点 start 到目的地 destination 之间的最短距离。

思路:看代码

class Solution {
    public:
        int distanceBetweenBusStops(vector<int>& distance, int start, int destination) {
            int n=distance.size();
            int len=0;
            for(int i=0;i<n;++i)len+=distance[i];
            int dist=0;
            for(int i=start;i<destination;++i)dist+=distance[i];
            for(int i=destination;i<start;++i)dist+=distance[i];
            return min(dist,len-dist);
        }
    };

> 给你一个日期，请你设计一个算法来判断它是对应一周中的哪一天。  
> 输入为三个整数：day、month 和 year，分别表示日、月、年。  
> 您返回的结果必须是这几个值中的一个 \{"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"\}。

思路：看代码（1971年1月1日，星期五

class Solution {
    public:
        string dayOfTheWeek(int day, int month, int year) {
            int mon[]={31,28,31,30,31,30,31,31,30,31,30,31};
            string d[]={"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
            int len=4;
            for(int i=1971;i<year;++i){
                len=(len+365)%7;
                if(is_year(i))
                    len=(len+1)%7;
            }
            for(int i=1;i<month;++i){
                if(is_year(year)&&i==2)len=(len+1)%7;
                len=(len+mon[i-1])%7;
            }
            len=(len+day)%7;
            return d[len];
        }
        bool is_year(int year){
            if(((year%4==0)&&(year%100!=0))||(year%400==0))
                return true;
            return false;
        }
    };

> 给你一个整数数组，返回它的某个 非空 子数组（连续元素）在执行一次可选的删除操作后，所能得到的最大元素总和。  
> 换句话说，你可以从原数组中选出一个子数组，并可以决定要不要从中删除一个元素（只能删一次哦），（删除后）子数组中至少应当有一个元素，然后该子数组（剩下）的元素总和是所有子数组之中最大的。  
> 注意，删除一个元素后，子数组 不能为空。

思路一：  
1.这里left\[i\]表示的是以自身为右端点的一个连续区间段的最大值,right\[i\]相同  
2.在求left\[i\]时可以顺带求不删除一个区间段的一个值的答案来更新答案。  
3.最后求删除arr\[i\]时的情况

class Solution {
    public:
        int maximumSum(vector<int>& arr) {
            if(arr.size()==1)return arr[0];//特殊情况
            int n=arr.size();
            vector<int> left(n+1);
            vector<int> right(n+1);
            left[0]=arr[0];
            int ans=arr[0];
            for(int i=1;i<n;++i){
                left[i]=max(left[i-1]+arr[i],arr[i]);//不删除
                ans=max(ans,left[i]);
            }
            right[n-1]=arr[n-1];
            for(int i=n-2;i>=0;i--){
                right[i]=max(right[i+1]+arr[i],arr[i]);
            }
            
            for(int i=0;i<n;++i){//删除arr[i]
                int l=0,r=0;
                if(i-1>=0){
                    l=left[i-1];
                    
                }
                if(i+1<n){
                    r=right[i+1];
        
                }
                ans=max(ans,l+r);
                
            }
            return ans;
        }
    };

思路二：  
1.g\[i\]表示以i结尾且删除了一个元素的序列和  
2.f\[i\]表示以i结尾且一个也不删除的序列和  
3.状态转移：f\[i\]第i位可以和前面加在一起，也可以另起一个新的序列  
g\[i\]第i位可以删除自己和前面f\[i-1\]，不删的话就是g\[i\]+当前数  
4.答案更新：在ans和f\[i\],g\[i\]中取最大值

class Solution {
    public:
        int maximumSum(vector<int>& arr) {
            int n=arr.size();
            if(n==1)return arr[0];
            vector<int> f(n),g(n);
            f[0]=arr[0];
            g[0]=0;
            int ans=arr[0];
            for(int i=1;i<n;++i){
                f[i]=max(f[i-1]+arr[i],arr[i]);
                g[i]=max(f[i-1],g[i-1]+arr[i]);
                ans=max(ans,max(f[i],g[i]));
            }
            return ans;
        }
    };

> 给你两个整数数组 arr1 和 arr2，返回使 arr1 严格递增所需要的最小「操作」数（可能为 0）。  
> 每一步「操作」中，你可以分别从 arr1 和 arr2 中各选出一个索引，分别为 i 和 j，0 <= i < arr1.length 和 0 <= j < arr2.length，然后进行赋值运算 arr1\[i\] = arr2\[j\]。  
> 如果无法让 arr1 严格递增，请返回 -1。

思路：  
1.f\[i\]\[j\]表示前i位经历j次操作达到的最小值  
2.状态转移：f\[i\]\[j\]对第i位不进行操作，那么f\[i-1\]\[j\]<arr1\[i\]就可以转移  
若对第i位操作，f\[i-1\]\[j-1\]若是成功操作过(!=INT\_MAX)，那麽就可以在arr2里面找数进行赋值操作  
3.答案在f\[n-1\]\[j\]里面寻找，看最小j是否操作过

class Solution {
    public:
        int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
            int n=arr1.size();
            int m=arr2.size();
            sort(arr2.begin(),arr2.end());
            vector<vector<int>> f(n+1,vector<int>(n+1,INT_MAX));//f[i][j]表示前i位经历j次赋值的最小值,j<=i+1
            f[0][1]=arr2[0];
            f[0][0]=arr1[0];
            for(int i=1;i<n;++i){
                for(int j=0;j<=i+1;++j){
                    if(f[i-1][j]<arr1[i]){
                        f[i][j]=min(f[i][j],arr1[i]);
                    }
                    if(j-1>=0){
                        int t=f[i-1][j-1];
                        if(t<INT_MAX){
                            auto it = upper_bound(arr2.begin(),arr2.end(),t);
                            if(it!=arr2.end()){
                                f[i][j]=min(f[i][j],*it);
                            }
                        }
                    }
                }
            }
            for(int j=0;j<=n;++j){
                if(f[n-1][j]!=INT_MAX)
                    return j;
            }
            return -1;
        }
    };

转载于:https://www.cnblogs.com/clear-love/p/11485706.html

[https_leetcode-cn.com_contest_weekly-contest-153]: https://leetcode-cn.com/contest/weekly-contest-153/