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

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

image.png

3 分 - 到目标元素的最小距离
4 分 - 将字符串拆分为递减的连续值
5 分 - 邻位交换的最小次数
6 分 - 包含每个查询的最小区间

7
共 56 个回复

Leetcode 第239场周赛题解

Problem A - 到目标元素的最小距离

模拟。

  • 时间复杂度O(N)\mathcal{O}(N)。
  • 参考代码的空间复杂度为O(N)\mathcal{O}(N),实际只需要保存当前最优结果,所以最优的空间复杂度是O(1)\mathcal{O}(1)。
class Solution:
    def getMinDistance(self, nums: List[int], target: int, start: int) -> int:
        return min([abs(i - start) for i in range(len(nums)) if nums[i] == target])

Problem B - 将字符串拆分为递减的连续值

回溯+剪枝。

  • 时间复杂度O(∣S∣⋅2∣S∣)\mathcal{O}(|S|\cdot2^{|S|}),但实际上会远远小于这一上界。
  • 空间复杂度O(∣S∣)\mathcal{O}(|S|)。
class Solution:
    def dfs(self, s: str, start: int, last: int):
        if self.ans:
            return
        
        n = len(s)
        if start == n:
            self.ans = True
            return
        
        now = 0
        hi = n if start != 0 else n - 1
        for i in range(start, hi):
            now = now * 10 + ord(s[i]) - ord('0')
            if start == 0 or now == last - 1:
                self.dfs(s, i + 1, now)
            if start != 0 and now >= last:
                return
    
    def splitString(self, s: str) -> bool:
        if len(s) == 1:
            return False
        
        self.ans = False
        self.dfs(s, 0, 0)
        return self.ans

Problem C - 邻位交换的最小次数

方法一:模拟

  1. 利用next_permutation求出目标排列。
  2. 贪心进行交换。
  • 时间复杂度O(∣S∣2+∣S∣K)\mathcal{O}(|S|^2+|S|K)。
  • 空间复杂度O(∣S∣)\mathcal{O}(|S|)。
class Solution {
public:
    int getMinSwaps(string num, int k) {
        string target(num);
        for (int i = 0; i < k; ++i)
            next_permutation(target.begin(), target.end());
        
        int ans = 0, n = num.size();
        for (int i = 0; i < n; ++i) {
            if (num[i] != target[i]) {
                int j = i + 1;
                while (num[j] != target[i])
                    j++;
                for (; j > i; --j)
                    swap(num[j], num[j - 1]), ans++;
            }
        }
        
        return ans;
    }
};

方法二:平衡树

在求第KK个之后的排列和最后的交换次数的过程中,均可以使用平衡树,从而将时间复杂度优化到O(∣S∣log⁡∣S∣)\mathcal{O}(|S|\log|S|),但过程会比较繁琐。

Problem D - 包含每个查询的最小区间

和昨天双周赛的最后一题如出一辙,将区间和查询分别排序,然后离线处理。

  • 时间复杂度O(Nlog⁡N+Qlog⁡Q+Qlog⁡N)\mathcal{O}(N\log N+Q\log Q+Q\log N)。
  • 空间复杂度O(N)\mathcal{O}(N)。
class Solution {
public:
    vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
        int n = intervals.size(), q = queries.size();
        vector<int> ans(q);
        
        vector<int> order(q);
        for (int i = 0; i < q; ++i)
            order[i] = i;
        sort(order.begin(), order.end(), [&](int i, int j){
            return queries[i] < queries[j]; 
        });
        
        sort(intervals.begin(), intervals.end());
        set<pair<int, int>> s;
        int ptr = -1;
        
        for (int i : order) {
            int qi = queries[i];
            while (ptr + 1 < n && intervals[ptr + 1][0] <= qi) {
                ptr++;
                s.emplace(intervals[ptr][1] - intervals[ptr][0] + 1, intervals[ptr][1]);
            }
                
            while (!s.empty() && s.begin()->second < qi)
                s.erase(s.begin());
            
            if (s.empty())
                ans[i] = -1;
            else
                ans[i] = s.begin()->first;
        }
        
        return ans;
    }
};
21

好难啊...

15

居然还有next_permutation这种东西。。。

6

假

5

下一个排列是自带的😅歪日,我这一个小时在想下一个排列怎么写

2

最后一道题就最后个点T了,我就看着时间慢慢流逝,却无可奈何,盯着一堆stl,不知如何优化╥﹏╥...

2

周赛题解

5746. 到目标元素的最小距离

思路:模拟。

代码:

class Solution {
public:
    int getMinDistance(vector<int>& nums, int target, int start) {
        int res = 100000;
        for(int i = 0; i < nums.size(); ++i) if(nums[i] == target) res = min(res, abs(i - start));
        return res;
    }
};

5747. 将字符串拆分为递减的连续值

思路:dfs

按照题目要求模拟即可,但要注意以下几点:

  1. 字符串的长度最大为 2020,会超出 3232 位整数的范围,甚至超出 6464 位整数的范围。为此可以采用一个折衷的办法:用 6464 位整数存储数字,并注意到不会有任何一个合法的拆分,其中存在超出 1111 位的整数,因此可以排除掉,不会爆掉 long long。
  2. 需要注意类似 "321000"\texttt{"321000"} 这样的用例,如果发现一个分割为 "3" "2" "1" "0" "0" "0"\texttt{"3" "2" "1" "0" "0" "0"} 是一个不合法的分割,但是不要立即返回 falsefalse,因为 "3" "2" "1" "000"\texttt{"3" "2" "1" "000"} 是一个合法的分割。

代码:

class Solution {
public:
    bool judge(string& s, long start, int p, int c) {
        if(p == s.size()) return c > 1;
        long cur = 0;
        if(start == -1) {
            for(int j = p; j < s.size(); ++j) {
                cur = cur * 10 + (s[j] - '0');
                if(judge(s, cur, j + 1, c + 1)) return true;
                if(cur > 1e15) break;
            }
            return false;
        }
        for(int j = p; j < s.size(); ++j) {
            cur = cur * 10 + (s[j] - '0');
            if(cur == start - 1) {
                return judge(s, cur, j + 1, c + 1);
            }
            if(cur > start) return false;
        }
        return false;
    }
    bool splitString(string s) {
        return judge(s, -1, 0, 0);
    }
};

5749. 邻位交换的最小次数

思路:贪心算法+模拟

  1. 不难发现,题意中所叙述的 最小妙数 就是 下一个排列,直接调用 C++ 的 \texttt{next_permutation} 库函数即可。由于 每次调用时间复杂度为 O(n)O(n),故这部分的复杂度为 O(kn)O(kn),不会超时。
  2. 下面的问题是求使两个字符串 ss 和 tt 相等所需 ss 的最少交换次数。在这里使用的是贪心算法:
    • 如果 s[i]=t[i]s[i] = t[i],则 i=i+1i = i + 1,跳过;
    • 如果 s[i]≠t[i]s[i] \neq t[i],则寻找满足 j>ij > i 且 s[j]=t[i]s[j] = t[i] 的 最小的(也就是最近的)jj,然后逐次进行两两交换,将 s[j]s[j] 前提到 s[i]s[i] 的位置上来。总的交换次数为 j−ij - i。

代码:

class Solution {
public:
    int getMinSwaps(string t, int k) {
        string s = t;
        for(int i = 0; i < k; ++i) next_permutation(t.begin(), t.end());
        int res = 0;
        for(int i = 0; i < s.size(); ++i) {
            if(s[i] == t[i]) continue;
            for(int j = i; j < s.size(); ++j) if(s[j] == t[i]) {
                res += j - i;
                for(int k = j - 1; k >= i; --k) swap(s[k + 1], s[k]);
                break;
            }
        }
        return res;
    }
};

5748. 包含每个查询的最小区间

思路:离线处理+扫描+multiset

  1. 题目已经给定所有的查询(离线查询),因此可以先对查询按照从小到大的顺序排个序。

  2. 我们从小到大处理查询,如果 “遇到” 区间 ii 的左端点 leftileft_i,则向 multiset 中添加其长度;如果 "遇到" 区间ii 的结束点(右端点 righti+1right_i + 1 ),则从 multiset 中移除其长度。

    具体实现可以用一个保存 (pos,val)(pos, val) 的二元组的优先队列解决,其中 pospos 表示 “事件” 发生的位置,val>0val > 0 表示增加长度为 valval 的区间,val<0val < 0 表示移除长度为 valval 的区间。

代码:

class Solution {
public:
    vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& q) {
        int k = q.size();
        vector<int> idxs(k);
        for(int i = 0; i < k; ++i) idxs[i] = i;
        sort(idxs.begin(), idxs.end(), [&](int a, int b) {return q[a] < q[b];});
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> qu;
        for(auto& v : intervals) {
            qu.emplace(v[0], v[1] - v[0] + 1);
            qu.emplace(v[1] + 1, -(v[1] - v[0] + 1));
        }
        multiset<int> s;
        vector<int> res(k);
        for(int _ = 0; _ < k; ++_) {
            int i = idxs[_];
            while(qu.size()) {
                auto [pos, val] = qu.top();
                if(pos > q[i]) break;
                if(val > 0) s.insert(val);
                if(val < 0) s.erase(s.find(-val));
                qu.pop();
            }
            if(s.size()) res[i] = *s.begin();
            else res[i] = -1;
        }
        return res;
    }
};
2

第四题果然怎么样都在超时。。。哭了

2

《难》

1

第三题他妈还真的是要求出来第几个排列再交换,我真的日了狗了。我以为有啥简便方法

1