正文索引 [隐藏]

传送门

T1重新格式化电话号码

思路

周赛经典的字符串处理题。难倒是不难，但是处理起来感觉比往期的签到题麻烦不少啊…

主要思路就是replace掉’-‘与空格，然后每三个一组分片，塞进列表，最后再对单出来的元素特殊处理。

代码

class Solution:
    def reformatNumber(self, number: str) -> str:
        number = number.replace('-', '').replace(' ', '')
        ans, N = [], len(number)
        for i in range(0, N, 3):
            ans.append(number[i:i+3])
        if len(ans[-1]) == 1:
            last = ans.pop()
            sec_last = ans.pop()
            ans.append(sec_last[:2])
            ans.append(sec_last[-1]+last)
        return '-'.join(ans)

字符串的题害得看我py。

T2 删除子数组的最大得分

思路

很标准的滑动窗口，很类似LeetCode003题，参考博文：LeetCode-003：无重复字符的最长子串。

枚举右边界，如果当前右指针指向的值已经在set里了，就从左往右去erase，一直erase到右指针指向的值已经不在set里了，这时集合中的值一定是无重复的。用cnt记录当前子区间的区间和，窗口每次滑动结束去维护一个最大的ans就行了。

代码

class Solution {
public:
    int maximumUniqueSubarray(vector<int>& nums) {
        unordered_set<int> mys;
        
        int cnt = 0;
        int ans = 0;
        int l = 0;
        
        for(int r = 0; r < nums.size(); r++) {
            while(mys.find(nums[r]) != mys.end()) {
                mys.erase(nums[l]);
                cnt -= nums[l];
                l++;
            }
            mys.insert(nums[r]);
            cnt += nums[r];
            ans = max(ans, cnt);
        }
        
        return ans;
    }
};

T3跳跃游戏 VI

思路

显然是一道dp。设dp[i]表示位置i上能获取的最大价值，显然dp[i]=max{dp[i-1],dp[i-2],…,dp[i-k]}+nums[i]。

for (int i = 1; i < nums.size(); i++) {
            for (int j = max(0, i - k); j < i; j++) {
                dp[i] = max(dp[i], dp[j]);
            }
            dp[i] += nums[i];
        }

但是这道题n与k能达到1e5的复杂度，直接O(n²)枚举显然超时，所以要另取巧。

因为要动态获取一个当前位置的最大值，考虑用大根堆。定义一个pair，以(dp[i],i)为关键字，维护一个此pair的大根堆，每次循环弹出所有越界(i – pair.second > k)元素，然后堆顶就是我们需要的动态最大值。

for(int i = 1; i < n; i++) {
            // 移除越界元素
            while(i - que.top().second > k) que.pop();

            dp[i] = que.top().first + nums[i];
            que.emplace(dp[i], i);
        }

这个方法的时间复杂度是优越的，但空间还可以优化。显然，在这种做法下，当前状态的dp值不需要单独用一个数组去存，它们被抛入堆中动态维护，所以可以用一个变量来存当前状态下的答案：

for(int i = 1; i < n; i++) {
            // 移除越界元素
            while(i - que.top().second > k) que.pop();

            ans = que.top().first + nums[i];
            que.emplace(ans, i);
        }

这样时空复杂度都是优秀的，LC上也能做到双百。

代码

class Solution {
public:
    int maxResult(vector<int>& nums, int k) {
        const int n = nums.size();
        
        priority_queue< pair<int, int> > que;
        que.emplace(nums[0], 0);
        int ans = nums[0];

        for(int i = 1; i < n; i++) {
            // 移除越界元素
            while(i - que.top().second > k) que.pop();

            ans = que.top().first + nums[i];
            que.emplace(ans, i);
        }

        return ans;
    }
};