leetcode 第 273 场算法比赛

作者: | 更新日期:

面对初始化的复杂度,这次想出了一个延迟回收的算法。

本文首发于公众号:天空的代码世界,微信号:tiankonguse

零、背景

这次比赛题目都很简单。

最后一题其他人我不知道都是怎么做的。

我是暴力做的,面对初始化导致复杂度退化问题,我想出一个延迟回收的算法,强烈推荐给大家,实际项目中可能也用得到。

一、反转两次的数字

题意:给一个数字,不断的反转,每次反转都去掉前导0,问最后得到的数字是否和原始数字相等。

思路:输入没有前导0,只需要判断有没有后缀0 即可。

注意实现:0 是特殊情况。

二、执行所有后缀指令

题意:给一个坐标、起始位置、移动命令列表。
问所有移动命令列表的后缀列表中,每个后缀最多可以执行多少个命令。

思路:按照题意分别判断即可。

三、相同元素的间隔之和

题意:给一个数组,问每个元素与其他相同元素的距离之和。

思路:不同元素没关系,先分组得到相同元素的下标列表。

对于一组下标列表,预处理出第一个下标的答案。
之后的可以通过左移一位,根据左边的个数与右边的个数,修正出答案来。

算是动态规划吧,转移方程如下:

sum +=  l * d - r * d

四、还原原数组

题意:给一个数组 arr 和一个正整数 k,可以分别生成两个数组。
第一个数组称为小数组,是 arr 中所有数字减去 k 得到。
第二个数组称为大数组,是 arr 中所有数字加上 k 得到。
现在没有原数组,只有大数组和小数组所有数字混合得到的集合,问是否可以构造出原数组。

思路:原先想搜索的,但是发现可以构造出特殊 case,把搜索卡爆。

然后突然意识到,如果枚举的话,复杂度可能不会超时。

具体来说就是枚举 K,判断给的集合是否可以拆分为小数组和大数组,可以了返回原数组。

假设 K 固定了,最小值肯定是小数组的,从而可以推算出大数组的最小值。
这样第一个数组就确定了。
之后的数字与最小值的逻辑类似,不断循环即可。

复杂度:O(N * (初始化复杂度 + N))

这里唯一的问题是初始化复杂度不能太高。

好吧,我想多了,直接无脑暴力就行了。
初始化复杂度最坏是 O(N)

我这里把 N 看成 10^5 了,所以在想办法降低初始化的复杂度。

于是定义了一个结构:

struct Node{
    int k = 0;
    int num = 0;
    int use = 0;
    void Reset(int K){
        if(k == K) return;
        k = K;
        use = 0;
    }
    bool Empty(){
        return use == num;
    }
    void Use(){
        use++;
    }
};

枚举 K 的时候,状态上保存这个 K。
每次使用一个数据时,判断这个状态是否是上次的,是了就使用时初始化下。

唉,看错题,过度设计了。

五、最后

现在看来,四道题都是简单题,第三题还需要动态规划,最后一题直接暴力就过了。

《完》

-EOF-

本文公众号:天空的代码世界
个人微信号:tiankonguse
公众号ID:tiankonguse-code

本文首发于公众号:天空的代码世界,微信号:tiankonguse
如果你想留言,可以在微信里面关注公众号进行留言。

点击查看评论

关注公众号,接收最新消息

tiankonguse +
穿越