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

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

image.png

3 分 - K 进制表示下的各位数字总和
4 分 - 最高频元素的频数
5 分 - 所有元音按顺序排布的最长子字符串
6 分 - 最高建筑高度

4
共 74 个回复

Leetcode 第238场周赛题解

Problem A - K 进制表示下的各位数字总和

模拟。

  • 时间复杂度O(log⁡kN)\mathcal{O}(\log_kN)。
  • 空间复杂度O(1)\mathcal{O}(1)。
class Solution {
public:
    int sumBase(int n, int k) {
        int ans = 0;
        while (n) {
            ans += n % k;
            n /= k;
        }
        return ans;
    }
};

Problem B - 最高频元素的频数

排序+双指针。

因为只有+1操作,所以我们只可能获得更多的大元素。因此,我们首先将数组升序排列。

之后,我们采用双指针来考虑操作次数的限制。如果将当前区间内的元素全都变为区间右端点所需的操作次数超过kk,我们就将区间左端点右移。

  • 时间复杂度O(Nlog⁡N)\mathcal{O}(N\log N),因为我们需要对数组进行排序。
  • 空间复杂度O(1)\mathcal{O}(1)。
using ll = long long;

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int ans = 0, n = nums.size();
        ll sum = 0;
        int l = 0;
        for (int r = 0; r < n; ++r) {
            sum += nums[r];
            while (1LL * nums[r] * (r - l + 1) - sum > k) {
                sum -= nums[l];
                l++;
            }
            ans = max(ans, r - l + 1);
        }
        return ans;
    }
};

Problem C - 所有元音按顺序排布的最长子字符串

模拟。如果当前有串,并且当前字母可以接到当前的串后,就接上。如果不能接上,但当前字母为a,则可以利用其作为新串的起点。

  • 时间复杂度O(∣S∣)\mathcal{O}(|S|)。
  • 空间复杂度O(1)\mathcal{O}(1)。
class Solution {
public:
    int longestBeautifulSubstring(string word) {
        string ref = "aeiou";
        int ans = 0;
        int start = -1;
        int now = 0;
        for (int i = 0; i < word.size(); ++i) {
            if (start == -1) {
                if (word[i] != 'a')
                    continue;
                else {
                    start = i;
                    now = 0;
                }
            } else {
                if (now < 4 && word[i] == ref[now + 1]) 
                    now++;
                else if (word[i] != ref[now]) {
                    if (word[i] == 'a')
                        start = i, now = 0;
                    else
                        start = -1;
                }
            }
            
            if (start != -1 && now == 4)
                ans = max(ans, i - start + 1);
        }
        
        return ans;
    }
};

Problem D - 最高建筑高度

首先,我们将所有限制条件按照坐标升序排列。

我们首先从左到右,计算每个受限位置只考虑来自左边的约束时能取得的最大高度;然后从右到左,计算每个受限位置只考虑来自右边的约束时能取得的最大高度。

这样我们就得到了每一个受限位置处的最大高度。这时,我们考虑相邻两个受限位置中间的区域能够取得的最大高度。假设左边的高度为LL,右边的高度为RR,中间的距离为DD,则我们在这段区间能取得的最大高度必须满足H−L+H−R≤DH-L+H-R\leq D,从而H≤L+R+D2H\leq\dfrac{L+R+D}{2}。

需要注意的是,最右边的一个区间需要单独考虑,因为它只受到左约束,而没有右约束。

  • 时间复杂度O(Mlog⁡M)\mathcal{O}(M\log M),因为我们需要对限制条件进行排序。
  • 空间复杂度O(M)\mathcal{O}(M)。
class Solution {
public:
    int maxBuilding(int n, vector<vector<int>>& restrictions) {
        int m = restrictions.size();
        if (m == 0)
            return n - 1;
        restrictions.push_back({1, 0});
        m++;
        sort(restrictions.begin(), restrictions.end());
        vector<int> l(m), r(m);
        l[0] = 0;
        for (int i = 1; i < m; ++i) {
            int left = l[i - 1];
            int dist = restrictions[i][0] - restrictions[i - 1][0];
            l[i] = min(restrictions[i][1], left + dist);
        }
        r[m - 1] = restrictions[m - 1][1];
        for (int i = m - 2; i >= 0; --i) {
            int right = r[i + 1];
            int dist = restrictions[i + 1][0] - restrictions[i][0];
            r[i] = min(restrictions[i][1], right + dist);
        }
        int ans = 0;
        for (int i = 0; i < m - 1; ++i) {
            int lh = min(l[i], r[i]);
            int rh = min(l[i + 1], r[i + 1]);
            int dist = restrictions[i + 1][0] - restrictions[i][0];
            ans = max(ans, (lh + rh + dist) / 2);
        }
        ans = max(ans, n - restrictions[m - 1][0] + min(l[m - 1], r[m - 1]));
        
        return ans;
    }
};
29

前两次都做出了两题,还以为自己变强了,不说了,接着努力

6

画一下就知道了,每个限制是个向上走45度的线,来回拐只会越拐越高。

2

第 238 场周赛

题目1:K 进制表示下的各位数字总和

思路:模拟

代码:

class Solution {
public:
    int sumBase(int n, int k) {
        int ret = 0;
        while(n) {
            ret += n % k;
            n /= k;
        }
        return ret;
    }
};

复杂度分析:

  • 时间复杂度为 O(lgn)O(lgn)
  • 空间复杂度为 O(1)O(1)

题目2:最高频元素的频数

思路:二分 + 贪心

  • 二分最大频数,每次判断当前频数 midmid 是否能被满足。
  • 由于我们每次只能对一个元素的值加 11 ,所以对于给定的下标 indexindex,我们贪心地将 [index−mid+1,index][index - mid + 1, index] 区间的元素都变为 nums[index]nums[index],这里通过提前维护前缀和,可以判断能否在不超过 kk 次操作中完成该转换。

代码:

class Solution {
    using ll = long long;
public:
    int maxFrequency(vector<int>& a, int k) {
        int n = a.size();
        sort(a.begin(), a.end());
        
        vector<ll> sum(n + 1, 0);
        for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i - 1];
        
        int l = 1, r = n;
        while(l <= r) {
            int mid = l + (r - l) / 2;
            
            bool ok = false;
            
            for(int i = n; i >= mid; i--) {
                // 以 i 结尾
                if((sum[i] - sum[i - mid] + k) >= (ll)a[i - 1] * mid) {
                    ok = true;
                    break;
                }
            }
            
            if(ok) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return r;
    }
};

复杂度分析:

  • 时间复杂度为 O(nlgn)O(nlgn),二分最大频数复杂度 O(lgn)O(lgn),每次判断是否满足复杂度 O(n)O(n)
  • 空间复杂度为 O(n)O(n),维护了前缀和数组

题目3:所有元音按顺序排布的最长子字符串

思路:模拟

  • 题目要求连续子字符串中,元音字母按字典序出现。所以遍历数组,利用双指针维护一个合理区间,如果当前区间内出现了非字典序升序的排列,则直接清空。若区间满足五种元音字母均出现,且按字典序升序,则更新最大长度。

代码:

class Solution {
public:
    int longestBeautifulSubstring(string s) {
        int n = s.size();
        int l = 0, r = 0;
        int ret = 0;
        map<char, int> mp;
        map<int, char> pm;
        mp['a'] = 0, mp['e'] = 1, mp['i'] = 2, mp['o'] = 3, mp['u'] = 4;
        pm[0] = 'a', pm[1] = 'e', pm[2] = 'i', pm[3] = 'o', pm[4] = 'u';
        map<char, int> mm;
        while(r < n) {
            mm[s[r]]++;
            bool ok = true;
            // 判断当前区间是否合法
            //要保证当前字母之前的元音字母均已出现
            //且后面的元音字母均未出现
            for(int i = 0; i < mp[s[r]]; i++) {
                if(!mm[pm[i]]) {
                    ok = false;
                    break;
                }
            }
            for(int i = mp[s[r]] + 1; i < 5; i++) {
                if(mm[pm[i]]) {
                    ok = false;
                    break;
                }
            }
            
            if(ok && s[r] == 'u') {
                ret = max(ret, r - l + 1);
            }
            if(!ok) {
                l = r;
                for(int i = 0; i < 5; i++) {
                    mm[pm[i]] = 0;
                }
                mm[s[r]]++;
            }
            r++;
        }
        return ret;
    }
};

复杂度分析:

  • 时间复杂度为 O(n)O(n)
  • 空间复杂度为 O(n)O(n)。

题目4:最高建筑高度

思路:二分 + 模拟

  • 由于 nn 在 10910^9 数量级,所以我们需要二分最大可能高度 midmid,每次判断是否合法。
  • 由于高度限制数组中,可能出现互相限制的情况,例如对于 restriction=[[2,1],[3,5]]restriction = [[2, 1], [3, 5]] 的情况,第二、三栋建筑相差一格,所以第三栋建筑最大高度只能为 22;针对这类情况,我们提前从左向右和从右向左遍历高度限制数组,根据可能出现的“互相限制”情况对数组进行更新。
  • 二分过程判断合法过程中,根据相邻的两个限制条件可以计算出这两栋建筑之间可以形成的最高建筑高度。特别地,最后一个限制条件的建筑可以向右一直增长到第 nn 栋建筑。

代码:

class Solution {
    using ll = long long;
public:
    int maxBuilding(int n, vector<vector<int>>& v) {
        v.push_back({1, 0});
        sort(v.begin(), v.end());
        int m = v.size();
        // 从左向右遍历一遍
        int k = 0, index = 0;
        while(k + 1 < m) {
            int a = v[index][0], x = v[index][1], b = v[k + 1][0], y = v[k + 1][1];
            if(y - x >= b - a) {
                v[k + 1][1] = x + b - a;
            } else {
                index = k + 1;
            }
            k++;
        }
        
        
        // 从右向左遍历一遍
        k = m - 1, index = m - 1;
        while(k >= 1) {
            int a = v[index][0], x = v[index][1], b = v[k - 1][0], y = v[k - 1][1];
            if(y - x >= a - b) {
                v[k - 1][1] = x + a - b;
            } else {
                index = k - 1;
            }
            k--;
        }
        
        
        // 二分最大高度
        ll l = 1, r = INT_MAX;
        while(l <= r) {
            ll mid = l + (r - l) / 2;

            bool ok = false;

            for(int i = 0; i < m - 1; i++) {
                ll a = v[i][0], x = v[i][1], b = v[i + 1][0], y = v[i + 1][1];
                if(mid * 2 <= y + x + b - a) {
                    ok = true;
                    break;
                }
            }
            
            if(mid - v[m - 1][1] <= n - v[m - 1][0]) {
                ok = true;
            }

            if(ok) {
               l = mid + 1; 
            } else {
                r = mid - 1;
            }
        }
        
        
        return r;
    }
};

复杂度分析:

  • 时间复杂度为 O(mlgm)O(mlgm),其中 mm 为限制条件。排序和二分的复杂度均为 O(mlgm)O(mlgm)
  • 空间复杂度为 O(1)O(1)
3

前30有奖励,31名是种怎样的体验

2

无趣,以前都是三题打卡,这次两个题

2

老哥,咱们进前三十了

1

为啥积分还没更新

1

T3简易。状态到5说明符合条件,如果不对应就直接找到下一个a的位置。

class Solution {
public:
    int longestBeautifulSubstring(string word) {
        int i = 0, j = 0;
        unordered_map<char,int> idx = {{'a',1},{'e',2},{'i',3},{'o',4},{'u',5}};
        int cur = 0;
        int ans = 0;
        while(j < word.size()){
            if(idx[word[j]] == cur + 1) {
                j++;
                cur++;
            }else if(idx[word[j]] == cur){
                j++;
            }else {
                while(j < word.size() && idx[word[j]] != 1) j++;
                i = j;
                cur = 0;
            }
            if(cur == 5)ans = max(j-i,ans);
        }
        return ans;
    }
};
1

第二题竟然想用差分做,过了63个用例

1