讨论/技术交流/🏆 第 227 场力扣周赛/
🏆 第 227 场力扣周赛

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

image.png

3 分 - 检查数组是否经排序和轮转得到
4 分 - 移除石子的最大得分
5 分 - 构造字典序最大的合并字符串
6 分 - 最接近目标值的子序列和

4
共 92 个回复

第一次参赛,就做了第一题,哈哈哈

23

简要题解:
1.排序后对每个可能的xx判断即可,复杂度O(n2)O(n^2).也可以找到最小值后判断是否递增,复杂度O(n)O(n).
2.经典问题,可以扩展到多堆.最大一堆如果比其他堆之和大,那么答案就是其他堆之和.否则答案是所有和除以22(下取整).复杂度O(1)O(1).
3.经典问题,每次贪心选取后缀更大的字符串.复杂度O(n2)O(n^2).如果通过后缀数组等方法判断后缀大小关系,复杂度O(n)O(n).
4.经典NP-Hard问题.使用折半搜索复杂度可以做到O(2n2)O(2^\frac n2).

19

大过年的一个人搁那儿玩儿石子,是社恐的我没错了

9

移除石子这道题目

设三堆石子数量分别为a,b,c
首先不妨设a>b>c.

  1. 如果a>b+c,那么答案显然是b+c,即每次都从第一堆中拿一个石子,再从第二堆或第三堆中拿一个石子
  2. 如果a<=b+c,那么答案是(a+b+c)//2, 证明如下:
    证明:
  3. 我们每一步都从石子数量最多的堆和数量第二多的堆中各选取一个石子,由于之前的假设为a>b>c,那么经过b-c+1次步骤后,三堆石子数量分别为 a-b+c-1,c-1,c
  4. 接下来从第一堆和第三堆中选取,直到地三堆中数量小于第二堆,按照这样的方法不断在第二堆和第三堆中切换,又由于a<b+c,所以第一堆拿完的时候,第2,3堆中至少还有一堆有石子
  • 这时第2,3堆的石子数量关系只有三种情况:x,x; x,x+1; x,x-1
    即要么一样多,要么数量只差一个。如果一样多,显然能把石子拿完,如果数量相差一个,那么最后还剩一个石子,即答案为(a+b+c)//2
8

I good vegetable a.

4

第一题不排序也行吧,遍历一遍,如果降序的地方<2就说明可以轮转得到

3

第一题直接遍历就行没那么复杂,
第二题大根堆 每次取两个即可

2

啊啊啊第一次参赛居然AK了,开心一下

2

第四题直接分组二进制枚举然后二分查找的,时间复杂度O(2n/2log(2n/2)))O(2^{n/2} log(2^{n/2})))

class Solution {
public:

    
    int minAbsDifference(vector<int>& nums, int goal) {
        int n=(int)nums.size();
        vector<int> a,b;
        long long ans=1e18;
        for(int i=0;i<n/2;i++) a.push_back(nums[i]);
        for(int i=n/2;i<n;i++) b.push_back(nums[i]);
        
        int na=(int)a.size();
        int nb=(int)b.size();
        
        vector<long long> sa;
        vector<long long> sb;
        for(int i=0;i<(1<<na);i++){
            long long tp=0;
            for(int j=0;j<na;j++){
                if((i>>j)&1) tp+=a[j]; 
            }
            sa.push_back(tp);
        }
        for(int i=0;i<(1<<nb);i++){
            long long tp=0;
            for(int j=0;j<nb;j++){
                if((i>>j)&1) tp+=b[j]; 
            }
            sb.push_back(tp);
        }
        
        sort(sa.begin(),sa.end());
        sort(sb.begin(),sb.end());
        
        for(auto v:sa){
            int id=lower_bound(sb.begin(),sb.end(),goal-v)-sb.begin();
            if(id<(int)sb.size()) ans=min(ans,abs(goal-(sb[id]+v)));
            if(id) ans=min(ans,abs(goal-(sb[id-1]+v)));
            if(id+1<(int)sb.size())  ans=min(ans,abs(goal-(sb[id+1]+v)));
        }
        return ans;
    }
};
2

超时超时还是超时

2